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