poniedziałek, 16 września 2013

Kryptolodzy zabierają głos w sprawie NSA

W bulwersującej sprawie działań NSA i GCHQ ujawnionych przez Edwarda Snowdena głos zabrali kryptologowie akademiccy. Zwrócili oni uwagę, że postępowanie tych służb łamie prawa obywatelskie oraz długofalowo osłabia, a nie wzmacnia bezpieczeństwo narodowe USA i Wielkiej Brytanii (pisaliśmy o tym tydzień temu). 

Oświadczenie w tej sprawie wydał między innymi prof. Phillip Rogaway z Uniwersytetu Kalifornijskiego w Davis [link] oraz grupa naukowców brytyjskich [link].

Słowo o szyfrowaniu funkcyjnym


Tym razem opowiemy o szyfrowaniu funkcyjnym, które jest współczesnym, już XXI-wiecznym, rozszerzeniem standardowych schematów klucza publicznego.  Początki kryptografii klucza publicznego sięgają prac Diffie'ego i Hellmana, a także Rivesta, Shamira i Adelmana, które zrewolucjonizowały świat bezpieczeństwa komputerowego w drugiej połowie lat 70. XX wieku.

W klasycznym ujęciu opisanym w powyższych pracach, osoba prywatna o imieniu Alicja generuje samodzielnie parę kluczy $(PK,SK)$ i udostępnia światu ich publiczną część $PK$, która następnie może być wykorzystana przez jej potencjalnych internetowych rozmówców do zaszyfrowania wiadomości $M$, w postaci szyfrogramu $C = Enc(PK,M)$.  Alicja, będąc w posiadaniu tajnej informacji $SK$ - odpowiadającej $PK$, wykorzystuje algorytm deszyfracji $Dec(SK,C)$ w celu odzyskania całej wiadomości $M$.  Oczywiście wymagamy również, żeby żadna osoba nieznająca $SK$ nie mogła poznać $M$ na podstawie $C$.

Wyobraźmy sobie teraz, że Alicja jest pracownikiem działu ochrony środowiska dużej agendy rządowej, a jej koleżanka Barbara pracuje w dziale analiz finansowych.  Ich organizacja wydała kompleksowy raport $R$ zawierający poufne informacje dotyczące zarówno finansów, jak i spraw związanych z zanieczyszczeniem środowiska.  Raport ten został zaszyfrowany publicznym kluczem ich firmy $PK_{agenda}$ i udostępniony wszystkim pracownikom w postaci $C = Enc(PK_{agenda},R)$.  Jak teraz poradzić sobie z sytuacją, w której Alicja i Barbara, ze względu na miejsce swojego zatrudnienia, powinny mieć dostęp do innych części zaszyfrowanego raportu? Oczywiście dział bezpieczeństwa ich firmy, nie może im udostępnić klucza prywatnego $SK_{agenda}$, gdyż to pozwoliłoby Alicji zdeszyfrować cały raport i uzyskać dane dotyczące spraw finansowych.  Odpowiedzią na nasze pytanie jest właśnie szyfrowanie funkcyjne, które pozwala na dywersyfikację możliwości kluczy prywatnych.  Dział bezpieczeństwa może udostępnić Alicji klucz $SK_{eko}$, a Barbarze $SK_{fin+kadry}$, co pozwoli im odpowiednio: poznać dane dotyczące ochrony środowiska oraz wydobyć informacje finansowe i kadrowe.  Zwróćmy uwagę, że istnienie zaufanego działu bezpieczeństwa jest tutaj niezbędne.  Gdyby Alicja generowała klucz samodzielnie, jak w wyżej opisanej sytuacji klasycznej, mogłaby w szczególności stworzyć sobie klucz do spraw finansowych.

W pełnej ogólności protokoły szyfrowania funkcyjnego pozwalają działowi bezpieczeństwa wystawić klucz $SK_f$ dający możliwość uzyskania wyłącznie informacji $f(M) = Dec(SK_f,C)$, będąc w posiadaniu szyfrogramu $C = Enc(PK,M)$.  W zarysowanym przed chwilą scenariuszu dotyczącym agendy rządowej rolę $f$ pełniły funkcje wydobywające dane związane z odpowiednimi działami organizacji.  W szczególnym przypadku, gdy funkcja $f$ sprawdza czy wiadomość jest opatrzona odpowiednim nagłówkiem wskazującym na jej adresata, otrzymujemy schemat tzw. szyfrowania opartego o tożsamość (Identity-Based Encryption).  Implementacja tego schematu, wykonana przez firmę Voltage Security należącą do jednego z twórców szyfrowania funkcyjnego Dana Boneha, okazała się być dużym sukcesem komercyjnym.

Na zakończenie opiszemy krótko historię protokołów szyfrowania funkcyjnego.  Prekursorem ogólnego szyfrowania funkcyjnego było wspomniane wyżej szyfrowanie oparte o tożsamość.  Pierwszy w pełni bezpieczny protokół, realizujący ten szczególny przypadek, pojawił się w pracy Boneh'a i Franklina "Identity-Based Encryption from the Weil Pairing" (co ciekawe było to również jedno z pierwszych zastosowań odwzorowań dwuliniowych Weila w kryptografii).  Ogólna idea szyfrowania funkcyjnego została zarysowana przez Sahai'a i Watersa w pracy "Fuzzy Identity-Based Encryption", a w pełni sformalizowana przez Boneh'a, Sahai'a i Watersa w "Functional Encryption: Definitions and Challenges".
Pierwsze protokoły realizujące oczekiwaną funkcjonalność w całkowitej ogólności pojawiły się dopiero ostatnio, w 2013 roku (np. w S. Goldwasser i inni "Reusable Garbled Circuits and Succinct Functional Encryption"). 

Nasz warszawski zespół kryptograficzny gościł ostatnio Vincenzo Iovino, kryptografa z Uniwersytetu w Salerno, którego ostatnia praca "On the achievability of Simulation-Based Security for Functional Encryption" dotyczy bezpieczeństwa protokołów szyfrowania funkcyjnego. W ostatnim tygodniu mieliśmy przyjemność wysłuchać jego referatu właśnie na ten temat.

Bibliografia:

  1. D. Boneh, M.K. Franklin, "Identity-Based Encryption from the Weil Pairing" Proceedings of CRYPTO 2001, http://www.iacr.org/archive/crypto2001/21390212.pdf
  2. A. Sahai, B. Waters "Fuzzy Identity-Based Encryption" Proceedings of Eurocrypt 2005, http://eprint.iacr.org/2004/086.pdf
  3. D. Boneh, A. Sahai, B.Waters "Functional Encryption: Definitions and Challenges", Proceedings of TCC 2011, http://eprint.iacr.org/2010/543.pdf
  4. S. Goldwasser, Y. Kalai and R.A. Popa, V. Vaikuntanathan, N. Zeldovich, "Reusable Garbled Circuits and Succinct Functional Encryption", Proceedings of STOC 2013, http://eprint.iacr.org/2012/733.pdf
  5. V. Iovino, A. De Caro, A. Jain, A. O'Neill, O. Paneth, G. Persiano, "On the Achievability of Simulation-Based Security for Functional Encryption", Proceedings of Crypto 2013, http://eprint.iacr.org/2013/364.pdf


piątek, 6 września 2013

Czy NSA podsłuchuje cały internet?

Wczoraj wieczorem doszło do kolejnego aktu w trwającej od paru tygodni aferze związanej z ujawnieniem przez Edwarda Snowdena tajnych dokumentów National Security Agency (NSA). Dzienniki New York Times, Guardian oraz strona internetowa ProPublica ujawniły nowe szczegóły dotyczące zakresu inwigiliacji użytkowników internetu przez NSA oraz brytyjską agencję Government Communications Headquarters (GCHQ). Sensacyjnie brzmi już sam początek artykułu w Guardianie:
Amerykańskie i brytyjskie agencje wywiadowcze złamały dużą część szyfrowania używanego w sieci przez miliony ludzi do zabezpieczenia prywatności ich osobistych danych, transakcji internetowych oraz emaili.
Arytykuły nie dostarczają niestety dokładnych informacji technicznych na temat tego co zostało złamane. Najprawdopodobniej nie mamy do czynienia ze złamaniem szyfrów na poziomie matematycznym. Sam Snowden stwierdził wyraźnie: 

Edward Snowden
Szyfrowanie działa. Właściwie zaimplementowana kryptografia jest jedną z niewielu rzeczy na których można polegać.

Aby zrozumieć o co chodzi kluczowe jest odpowiednie zinterpretowanie drugiego zdania w powyższym cytacie. Kryptografia jest bezpieczna o ile jest właściwie zaimplementowana.  Prawie na pewno NSA odnalazła jedynie dziury w protokołach wykorzystujących algorytmy kryptograficzne, zwłaszcza w protokole TLS, albo w konkretnych jego implementacjach. O ile "matematyczne" złamanie szyfrów używanych w internecie byłoby prawdziwym szokiem, to znalezienie luk w TLSie jest o wiele mniej zaskakujące, tym bardziej, że luki takie znajdowano już w przeszłości. NSA i GCHQ jako organizacje dysponujące dużymi budżetami mają z pewnością możliwości odkrycia tych luk na długo za nim zostaną one opisane publicznie i załatane.

Autorzy artykułów podają też szereg innych, ciekawych informacji. W szczególności potwierdzają od dawna pojawiające się plotki, że NSA aktywnie działała w celu osłabienia bezpieczeństwa nowych standardów kryptograficznych oraz nakłania producentów sprzętu i oprogramowania do celowego instalowania w nich dziur i ukrytych drzwi umożliwiających NSA przejęcie nad nimi kontroli. Ten ostatni fakt jest szczególnie kontrowersyjny gdyż nie jest wykluczone, że dziury te mogą być wykorzystywane nie tylko przez NSA ale też przez przestępców. Paradoksalnie więc, agencja która w nazwie ma "bezpieczeństwo" może działać wbrew bezpieczeństwu obywateli których ma chronić.

piątek, 30 sierpnia 2013

Crypto 2013: dzień czwarty


Czwarty dzień zaczął się od prezentacji dra Macieja Obremskiego na temat pracy członków zespołu CryptoUW pt. "Non-malleable codes from two-source extractors" (współautorami są: dr hab. Stefan Dziembowski oraz niżej podpisany). Ponieważ pewnie nie wypada skupiać się właśnie na tym, napiszę co mnie zainteresowało poza tą prezentacją.

Moją uwagę przykuł referat "Optimal Coding for Streaming Authentication and Interactive Communication". Autorzy wracają w nim do znanego problemu przesyłania wiadomości przez zaszumiony kanał. Istotą komunikacji w takim warunkach jest automatycznia korekcja błędu wysyłanych komunikatów. Istnieją już dobre rozwiązania tego problemu: polegają na przesyłaniu pewnej redundantnej informacji, która ułatwia odczytanie częściowo (być może złośliwie) zmienionej informacji.

To, co nowego, zrobili autorzy, to rozwiązali problem przy ogólniejszych założeniach. Dotychczas zakładano, że długość wiadomości $n$ jest z góry znana, a wysyłający od razu wie, jaką wiadomość chce wysłać. W referowanej pracy, te założenia osłabiono: pokazano protokół dla komunikacji strumieniowej, potencjalnie nieskończonej.

Aby zachęcić do sięgnięcia po wersję papierową wystąpienia, dodam, że rozwiązanie jest wysoce nietrywialne. Łatwo chociażby zauważyć, że blokowe wysyłanie kolejnych fragmentów wiadomości długości $n$ jakimś znanym wcześniej kodowaniem nie może działać - zgubienie jednego bloku jest niewielkim (a więc dopuszczalnym) zaszumieniem, a przecież uniemożliwia odtworzenie całej wiadomości.

Na sam koniec pozwolę sobie (jak to ja) na uwagę natury bardziej filozoficznej. Tendencja, aby robić wyniki już znane, ale przy słabszych założeniach, jest zauważalna na całej konferencji. To chyba dobry kierunek. Przykładem takiego myślenia jest cała gałąź kryptografii, którą zajmuje się CryptoUW, tzn. wycieki (ang. leakage).

Crypto 2013: dzień drugi


Najciekawszą prezentacją drugiego dnia, moim zdaniem, była "Key Homomorphic PRFs and Their Applications".  Autorami pracy są Dan Boneh, Kevin Lewi, Hart Montgomery(prezentujący) i Ananth Raghunathan, wszyscy z Uniwerytetu Stanforda. 

Z trzech powodów było to niezwykle mile spędzone 20 minut: po pierwsze praca porusza niezmiernie ciekawe problemy, po drugie prezentowane rozwiązania są wyjątkowo eleganckie, w końcu po trzecie sama prezentacja była dobrze przemyślana i zrozumiała dla chyba wszystkich niezależnie od tematyki jaką się zajmują.

Nie chcę wchodzić zbytnio w szczegóły techniczne i nie zaprezentuję samej konstrukcji zamiast tego skupię się na jednym dość ciekawym zastosowaniu.

Niech $f(k,x)$ będzie funkcją pseudolosową, to znaczy, że jeśli nie znamy klucza $k$ wartości $f(k, \, )$ będą dla nas nieodróżnialne od kompletnie losowych. Na przykład jeśli poznamy $f(k,1)$, $f(k,2)$, $f(k,3)$ to bez znajomości klucza nie mamy szans na zgadnięcie $f(k,4)$.

Załóżmy, że chcemy połączyć się z jakimś serwerem. Zarówno serwer jak i my jesteśmy w posiadaniu tajnego klucza (ciągu bitów) $k$. Pierwszą fazą w nawiązywaniu połączenia jest udowodnienie serwerowi, że my to my (tj. że jesteśmy w posiadaniu klucza $k$). 

Jak to zrobić?

Może wyślijmy do serwera nasz klucz i serwer sprawdzi czy wszystko się zgadza? Niestety, jeśli ktoś podsłucha transmisje to wejdzie w posiadanie tajnego klucza. Potrzebujemy zatem lepszego rozwiązania.

Może niech serwer wybierze dowolną wartość $x$ i poprosi byśmy odpowiedzieli wartością $f(k,x)$? Nawet jeśli nasza transmisja zostanie podsłuchana przeciwnik pozna jedynie poprawną odpowiedź na jedno, konkretne, pytanie, jest niezwykle mało prawdopodobne, że serwer następnym razem zapyta o tę samą liczbę. Takie rozwiązanie jest poprawne.

Autorzy pracy dostrzegają jednak istotny minus takiej konstrukcji. Jeśli jakiś haker złamie zabezpieczenia serwera to za jednym zamachem otrzyma cały nasz klucz $k$ składowany na serwerze i będzie się mógł pod nas podszywać. Odpowiedzią na ten problem jest następujący pomysł autorów pracy.

Skonstruujmy trochę lepszą funkcję pseudolosową: jeśli $k=k_1+k_2$ to niech $f(k,x)=f(k_1,x)+f(k_2,x)$. Pomysł jest więc taki, by nasz klucz $k$ podzielić na wiele części $k_1, k_2, k_3,…,k_n$ i każdą z nich składować na innym serwerze.

Uwierzytelnianie (dowodzenie, że ja to ja) będzie wtedy wyglądało następująco. Serwer prosi o wartość funkcji w $x$, my odpowiadamy $f(k,x)$ teraz serwer prosi o kolejne wartości $f(k_i,x)$ kolejne serwery (w żadnym momencie klucze nie opuszczają serwerów na których są składowane), teraz wystarczy że serwer sprawdzi czy przesłane przez nas $f(k,x)$ jest równe $f(k_1,x)+f(k_2,x)+ f(k_3,x)+…+f(k_n,x)$.

Przewagą tego rozwiązania nad poprzednim jest to, że teraz haker musi włamać się do wszystkich serwerów by móc podszywać się pod nas co jest niewątpliwie znacznie trudniejsze niż włamanie do pojedynczego serwera. 

Wszystko pięknie, tylko czy taka funkcja istnieje? Nie tylko istnieje. Dzięki "Key Homomorphic PRFs and Their Applications" znamy jej konstrukcję!

Autor: dr Maciej Obremski
Uwaga: artykuł ma charakter popularnonaukowy i zawiera pewne uproszenia

czwartek, 22 sierpnia 2013

Crypto 2013: dzień trzeci

Dzisiaj swój wykład miał zwycięzca konkursu na najlepszą pracę konferencji. Wygrał Gologlu et al z pracą "One the Function Field Sieve and the Impact of Higher Splitting". Praca dotyczyła teorii liczb, ogólnie była chwalona. Nie jest to jednak moja działka, więc nie chcę wypowiadać się ekspercko na temat tego rezultatu.

Dla mnie największe wrażenie zrobiła sesja nr 13, czyli zagadnienia obliczeń wielopodmiotowych. Zaczął Yuval Ishai. To jedna z tych osób, które ma zawsze świetne przygotowane wystąpienia. Jednoczeście wykład był wyjątkowy interesujący dla mnie. Autor mówił jak zrobić gadżet podobny do obwodu Yao, ale bardziej skompresowany. To jest o tyle ciekawe, że obwody Yao wykorzystywałem osobiście w pracy "One-Time Programs with Limited Memory". Mogę więc teraz zastanowić się, czy nie da się zastąpić tej nowo zaproponowanej konstrukcji w swej starej pracy. Dzięki temu pewnie poprawią się parametry. Po takich wykładach dokładnie rozumie się, co to znaczy "środowisko naukowe". Badania to praca zespołowa!

Jako drugi w tej sesji swą pracę przedstawiał Ron Rothblum. Wynik znowu ciekawy. Idea jest taka: ile trzeba "przekupić" osób, żeby czegoś się dowiedzieć w jakimś obliczeniu wielopodmiotowym? Ogólne oszacowania są znane. Ale co, gdy ograniczymy np. głębokość drzewiastą funkcji, którą obliczamy? Wtedy da się zrobić to lepiej.

wtorek, 20 sierpnia 2013

Crypto 2013: dzień pierwszy

Za nami pierwszy dzień bodaj najlepszej konferencji kryptograficznej, CRYPTO. Jak zawsze w Santa Barbara, w Południowej Kalifornii.

Tutaj każdy kryptograf czuje się jak w raju: przez kilka dni w jednym miejscu obcować można z pięknym miejscem, na pięknym kampusie, wśród pięknej fauny i flory, słuchając pięknych referatów. Surferzy na deskach na wysokich falach, szyfry symetryczne, wyrafinowane własności twierdzenia min-max, pelikany, szopy, kody niekowalne, podział sekretu, pelikany, szopy... Wszystko to miesza się jak w kalejdoskopie, a dusza i ciało mają ucztę w każdym sensie. Wszystkie poziomy potrzeb w kryteriach Maslowa wydają się być jednocześnie zaspakajane.

Może piszę trochę rzewnie, ale przecież inaczej się nie da. Żeby poczuć CRYPTO, trzeba zrozumieć, że tutaj wszystko się przeplata: rano śniadanie na tarasie De La Guerra, potem pospiesznie na pierwszą sesję wykładów. A tam Fully Homomorphic Encryption, czyli coś bardzo świeżego i aktualnego. Mi podobał się wykład Micciancio na temat swoich wyników z SIS i LWE - poprawił trochę parametry i pokazał pewne związki z Lossy Function Families. Nie mniej ciekawy był Alwen opowiadający o Learning with Rounding. Świetne tempo i balans między jasnością opisu a jego głębokością. Kluczowa definicja jest następująca:

$x\in Z_q, \lfloor x \rfloor_p := \lfloor \frac{xp}{q} \rfloor$.

Czemu to służy? Zachęcam do sięgnięcia po pełną pracę.

A dalej? A dalej spacer klifem wzdłuż brzegu oceanu. Krótki, bo zaraz kolejne wykłady.

Duże zainteresowanie wzbudził pierwszy duży wykład zaproszonego gościa - Cindy Cohn. Tematyka ocierała się o politykę, a więc o powszechne podsłuchiwane wszystkiego przez tajne służby. Dużo by pisać, na sali czuło się czasem gęstą atmosferę sprzeciwu przeciw niektórym praktykom agencji NSA. Nie będę rozwodził się na temat szczegółów technicznych. Zwrócę tylko uwagę, że to, co mnie osobiście najbardziej uderzyło to fakt, że politycy zdają się nie rozumieć, o co "w tym wszystkim chodzi". A NSA trochę działa jak państwo w państwie. Jak powiedziała prelegentka: w NSA jest dużo geeków, a po stronie polityków - mało. Jej zdaniem potrzeba jest zaangażować więcej geeków także po "jasnej stronie mocy". Sądzę, że wielu słuchaczy CRYPTO z tym się zgodziło.