Czy NSA manipulowała standardem SHA-3?

Tydzień temu pisaliśmy o ujawnieniu przez Edwarda Snowdena manipulacji NSA w procesie standardyzacji generatorów pseudolosowych. Ponieważ mało kto myśli, że działalność NSA ograniczała się tylko do tych generatorów, kryptolodzy zastanawiają się w czym jeszcze agenci NSA maczali swoje palce. 

Logo konkursu na funkcję haszującą SHA-3

Jednym z podejrzanych jest funkcja haszującą SHA-3. Przypomnijmy, że funkcja SHA-3 została wybrana spośród ponad 60 kandydatów w organizowanym przez NIST otwartym konkursie odbywającym się w latach 2008-2012. Podczas tego konkursu zgłoszone funkcje były drobiazgowo analizowane przez kryptologów i znalezienie ataku (nawet teoretycznego) oznaczało automatyczną dyskwalifikację. Cały ten proces miał gwarantować, że bezpieczeństwo zwycięzcy (a jest nim funkcja Keccak) nie budziło niczyjej wątpliwości. W podobny sposób wybrano wcześniej np. standard szyfrowania AES.

O ile mało kto kwestionuje bezpieczeństwo Keccaka, to wątpliwości budzi fakt, że już po zakończeniu konkursu funkcję tę poddano pewnym modyfikacjom, mającym oficjalnie na celu m.in. zwiększenie jej wydajności. Tak więc SHA-3 nie jest w stu procentach tą samą funkcją którą analizowano podczas konkursu! W przeszłości zapewne społeczność naukowa przeszłaby nad tym do porządku dziennego, ale w obecnej atmosferze nie trzeba być wyznawcą teorii spiskowych aby podejrzewać, że modyfikacje te wprowadzono na żądanie NSA. Więcej na ten temat można przeczytać w tym artykule.

---

Aktualizacja z 3.10.2013:

Parę dni po ukazaniu się powyższego postu tematem zajął się też Bruce Schneier na swoim blogu. Warto poczytać dyskusję toczącą się w komentarzach.  

Furtka NSA w generatorze pseudolosowym

Jedną z najszerzej komentowanych informacji pochodzących od Edwarda Snowdena jest ta o manipulowaniu przez NSA standardami NIST dotyczącymi generatorów pseudolosowych. Choć dokumenty ujawnione przez Snowdena nie podają o który generator dokładnie chodzi, to przypuszcza się, że jest to generator Dual_EC_DRBG, który od początku przyjmowany był przez kryptologów ze sporym sceptycyzmem. 

Sceptycyzm ten wynikał z kilku powodów. Przede wszystkim, generator ten jest o kilka rzędów wielkości wolniejszy od innych generatorów, co jest konsekwencją faktu, że jego działanie oparte jest na krzywych eliptycznych. Taka niska wydajność niekoniecznie dyskwalifikuje algorytm. Czasami użytkownicy są gotowi pogodzić się z wolniejszym działaniem systemu, o ile zwiększa to jego bezpieczeństwo. Tak jest np. w przypadku kiedy bezpieczeństwo to może być formalnie dowiedzione w oparciu o jakieś wiarygodne założenia dotyczące trudności konkretnych problemów algorytmicznych. O dziwo generator Dual_EC_DRBG nie został poparty żadnym takim dowodem, co od razu powinno wydawać się podejrzane. Początkowo cześć inżynierów uważała jednak te wątpliwości za kaprysy teoretyków. Portal Ars Technica cytuje (anonimowo) jednego z nich:

Wyobrażałem sobie matematyka zirytowanego brakiem teoretycznych podstaw generatora pseuodolosowego marudzącego na temat standardów NIST.

Tymczasem dość szybko wyszło na jaw, że Dual_EC_DRBG ma wady, które powinny zainteresować nie tylko teoretyków ale i praktyków. Po pierwsze, okazało się, że z prawdopodobieństwem około 0.1% lepszym od 0.5 da się przewidzieć kolejny bit wygenerowany przez Dual_EC_DRBG na podstawie bitów poprzednich (0.1% to zdecydowanie za dużo w kryptografii). Po drugie, Dual_EC_DRBG zawiera arbitralnie ustalone, wpisane stałe do standardu, parametry.  Jeśli parametry te zostały wybrane losowo, to generator wydaje się w miarę bezpieczny (poza problemem opisanym powyżej). Kryptologom udało się jednak pokazać, że twórcy generatora są w stanie wybrać te parametry w taki sposób by wyglądały one na losowe, a jednak dawały tym twórcom możliwość całkowitego złamania bezpieczeństwa generatora -- krótko mówiąc w generatorze tym można zamontować tzw. furtkę (ang. backdoor)! Wzbudziło to oczywiście podejrzenia, że NSA manipulowało tymi parametrami, a rewelacje Snowdena tylko te podejrzenia potwierdziły. Więcej na temat szczegółów technicznych ataków na Dual_EC_DRBG można poczytać w artykule Matthew Greena.

Warto dodać, że Dual_EC_DRBG jest używany w szeregu produktów kryptograficznych. Podkreślmy też, że dobra losowość jest bardzo ważna w kryptografii -- jest chociażby potrzebna do generacji kluczy, oraz niezbędna jest w wielu algorytmach szyfrujących (np. popularny szyfr ElGamala jest zupełnie złamany jeśli przeciwnik może przewidzieć losowość użytą w procesie szyfrowania).

NIST oczywiście zaprzecza, że w Dual_EC_DRBG zainstalowano furkę. Mało kto jednak w te zapewnienia wierzy. O tym jak poważna jest sytuacji świadczy fakt, że firma RSA Security wydała właśnie zalecenie dla swoich klientów aby jak najszybciej zaprzestali używania Dual_EC_DRBG. 

---

Aktualizacja z 25.09.2013:
W magazynie "Wired" ukazał się właśnie bardzo dobry artykuł na powyższy temat.

Festiwal Eurowizji wygrywa z Eurocryptem

Na stronie konferencji Eurocrypt 2014 (jednego z dwóch czołowych corocznych sympozjów kryptologicznych) pojawiła się informacja, że daty konferencji ulegają zmianie ze względu na kolizję z konkursem piosenki Eurowizji. Obydwie imprezy planowane były w tych samych dniach w Kopenhadze. Choć daty Eurocryptu były ustalone wcześniej niż daty konkursu Eurowizji, to kryptologowie ustąpili miejsca piosenkarzom. Zapewne kluczowym argumentem były przewidywana zmniejszona dostępność miejsc hotelowych w tym okresie. Może jednak zamiast przenosić konferencję należało połączyć obie te imprezy? Jak okazało się na ostatniej konferencji Crypto w Santa Barbara kryptolodzy ze śpiewaniem radzą sobie całkiem nieźle:

Nawiasem mówiąc, nie jest to pierwszy przypadek kiedy kryptolodzy muszą ustąpić miejsca innym. W roku 2010 Eurocrypt był w ostatniej chwili przeniesiony z Nicei do Monte Carlo ponieważ hotel konferencyjny został przejęty przez prezydenta Sarkozy'ego na Szczyt Francusko-Afrykański.

Kryptograficzna kartografia

Ciekawostka: Pratyay Mukherjee z Uniwersytetu w Aarhus stworzył mapę grup badawczych zajmujących się kryptografią.  

The Economist o aferze NSA

O aferze NSA pisze też ostatni The Economist. Warto przeczytać zwłaszcza końcówkę artykułu, w której autor koncentruje się na stratach gospodarczych jakie ta sprawa przyniesie amerykańskim firmom informatycznym.  Artykuł kończy się zdaniem:

Poprzez szarganie reputacji tych firm, amerykański aparat bezpieczeństwa strzelił sobie samobójczego gola.

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

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ć.