Kryptografia II stopień

Od zagrożenia do mechanizmu ochrony

Wyobraź sobie usługę podpisującą dokumenty. Użytkownik przesyła dokument, urządzenie używa tajnego klucza, a odbiorca sprawdza podpis. Poprawny podpis powinien przejść weryfikację. To jednak dopiero początek. Czy ktoś, kto dostał podpis pod jednym dokumentem, może przenieść go na inny? Czy podpis wiąże kwotę, odbiorcę i rodzaj operacji? Co się stanie, gdy urządzenie po restarcie powtórzy losowość?

Kryptografia odpowiada na precyzyjne pytanie, nie na ogólne życzenie „ma być bezpiecznie”. Najpierw ustalamy, co chronimy, kto może zaszkodzić i jakie ma możliwości. Potem projektujemy mechanizm. Na końcu sprawdzamy, czy mechanizm spełnia cel mimo tych możliwości. Ten sposób myślenia będzie wracał przy szyfrach, identyfikacji, podpisach i obliczeniach na cudzych urządzeniach.

Nie zakładamy wcześniejszego kursu kryptografii. Zaczynamy od scenariuszy i małych obliczeń. Pojęcia algebraiczne wprowadzamy wtedy, gdy stają się potrzebne. Formalne definicje nie mają zastępować intuicji. Pozwalają sprawdzić, czy intuicja uwzględniła wszystkie dozwolone zachowania.

Od potrzeby do kryptosystemu

Każda z poniższych konstrukcji odpowiada na inne pytanie. Najpierw określamy funkcjonalność i interfejs algorytmów. Ustalamy, co ma się udać uczciwym uczestnikom i czego nie powinien osiągnąć przeciwnik. Dopiero potem dobieramy konkretne obliczenia i dowodzimy, że spełniają te wymagania. Nazwa algorytmu będzie oznaczała zamkniętą procedurę, nie luźną sugestię „teraz coś zaszyfruj”.

PRF

pseudorandom function. Funkcja pseudolosowa.

AES

Advanced Encryption Standard. Standard szyfrowania blokowego. Liczby 128, 192 i 256 oznaczają długości klucza w bitach.

AEAD

Authenticated Encryption with Associated Data. Uwierzytelnione szyfrowanie z danymi dodatkowymi.

MAC

Message Authentication Code. Kod uwierzytelnienia wiadomości, sprawdzany przy użyciu klucza.

RSA

Rivest–Shamir–Adleman. Nazwiska autorów kryptosystemu z kluczem publicznym.

To kolejność uczenia się, nie twierdzenie, że każdy schemat szyfrowania zawiera protokół AKE albo że każdy podpis powstaje z identyfikacji. Wspólne narzędzia pozwalają porównać konstrukcje, ale ich cele pozostają różne. Na przykład podpis nie ukrywa wiadomości, a szyfrowanie do odbiorcy samo nie potwierdza nadawcy.

AKE

Authenticated Key Exchange. Uwierzytelniona wymiana klucza.

Pięć pytań przed wyborem algorytmu

1. Zasób i właściciel. Czy chronimy treść dokumentu, prawo do jego podpisania, tożsamość, klucz sesji czy wynik obliczenia?
2. Cel naruszenia. Czy porażką jest odczyt, zmiana treści, podszycie się, wskazanie autora czy akceptacja błędnego wyniku?
3. Dostęp przeciwnika. Czy tylko obserwuje? Czy wybiera dokumenty, zmienia wiadomości, uruchamia sesje albo odczytuje stan urządzenia?
4. Granica zaufania. Gdzie znajdują się klucze? Które obliczenia wykonuje niezaufany program, a które chroniony komponent?
5. Wniosek i warunki. Jakie dokładnie zdarzenie ma być rzadkie i przy jakich założeniach?

Bezpieczeństwo systemu jest szersze niż kryptografia

Podpis może wykryć zmianę dokumentu, ale nie zapobiega usunięciu całej bazy. Szyfrowanie może ukryć treść, lecz pozostawić widoczną długość i porę wysłania. Uwierzytelniony kanał może kończyć się w przejętej aplikacji. Żaden z tych przykładów nie przeczy poprawnemu twierdzeniu kryptograficznemu. Pokazuje cel, którego to twierdzenie nie obejmowało.

Polityka mówi, co ma być dozwolone. Protokół określa komunikaty i sprawdzenia. Implementacja realizuje protokół. Wdrożenie dostarcza klucze, uprawnienia, urządzenia i procedury odtwarzania po awarii. Błąd na dowolnym z tych poziomów może zniszczyć ochronę. Dlatego nie zaczynamy od pytania, czy użyto AES, ale od pytania, czy cała operacja odpowiada właściwej polityce.

Przykład: podpis pod tekstem „100” jest poprawny matematycznie. Aplikacja interpretuje go jako zgodę na przelew 100 zł do dowolnego odbiorcy. Podpisujący zamierzał zatwierdzić wpłatę na własne konto. Nie doszło do złamania podpisu. Nie określono jednoznacznie, co podpis oznacza. Naprawa dotyczy formatu wiadomości: rodzaju operacji, kwoty, waluty, odbiorcy i identyfikatora zlecenia.

Model nie jest całą rzeczywistością

Model wybiera z rzeczywistości te właściwości, które są istotne dla badanego celu. Nie opisuje każdego tranzystora. Musi jednak obejmować zdarzenia, przed którymi naprawdę chcemy się chronić. Gdy pozwolimy przeciwnikowi na nową czynność, poprzedni dowód może przestać mieć zastosowanie. To nie oznacza automatycznie istnienia ataku. Oznacza obowiązek nowej analizy.

Model urządzenia jest równie ważny jak model sieci. HSM (hardware security module) to sprzętowy moduł wykonujący określone operacje kryptograficzne w chronionym środowisku. „Klucz nie opuszcza HSM” nie wystarczy, jeśli niezaufany program może żądać podpisania dowolnej operacji bez autoryzacji. Z drugiej strony chroniony, odpowiednio ograniczony interfejs może zachować użyteczną gwarancję mimo częściowego przejęcia hosta. W rozdziale o identyfikacji zobaczymy, jak zmienia się rachunek, gdy ujawniona zostaje losowość jednego wykonania.

Zapis, losowanie i rachunek na bitach

Zanim opiszemy przeciwnika i jego szanse, ustalmy język przykładów. Nie trzeba znać żadnego protokołu. Potrzebujemy ciągów bitów, kilku działań i sposobu zapisywania losowania.

Bity i operacje na ciągach

Bit ma wartość 0 albo 1. Zbiór $\{0,1\}^n$ zawiera wszystkie ciągi dokładnie $n$ bitów. Jest ich $2^n$. Zapis $\{0,1\}^*$ dopuszcza dowolną skończoną długość. Symbol $|m|$ oznacza długość ciągu, a $|S|$ liczbę elementów zbioru, gdy $S$ jest zbiorem.

XOR, zapisywany $\oplus$, daje 1 wtedy i tylko wtedy, gdy bity są różne. Dla ciągów tej samej długości działa osobno na każdej pozycji. Konkatenacja $x\|y$ dokleja drugi ciąg do pierwszego. Nie jest działaniem XOR.

XOR

exclusive OR. Alternatywa wykluczająca. Wynik to 1 dokładnie wtedy, gdy dwa bity są różne.

Na przykład $1010\oplus0110=1100$, natomiast $10\|01=1001$. Zawsze $x\oplus x=0^n$ i $(m\oplus k)\oplus k=m$. Symbol $0^n$ oznacza ciąg $n$ zer, nie potęgę liczby zero. Ta odwracalność wyjaśni działanie pierwszego szyfru.

Losowa zmienna i konkretna wartość

$X\overset{\$}{\leftarrow} S$ oznacza jednostajne losowanie elementu skończonego zbioru $S$. Znak dolara przy strzałce wskazuje losowanie. Każdy element ma prawdopodobieństwo $1/|S|$. Na przykład $r\overset{\$}{\leftarrow}\mathbb Z_q$ wybiera jedną z reszt $0,\ldots,q-1$, każdą z prawdopodobieństwem $1/q$. Dla pierwszego $q$ zapis $r\overset{\$}{\leftarrow}\mathbb Z_q^*$ wyklucza zero i daje każdej z pozostałych reszt prawdopodobieństwo $1/(q-1)$. W protokołach te reszty będą skalarami. Gdy losujemy kilka wartości, są to niezależne losowania, chyba że jawnie podano inny związek.

Zwykła strzałka oznacza przypisanie, np. $y\leftarrow f(x)$, albo odebranie wyniku algorytmu, np. $k\leftarrow\mathsf{Gen}(1^\lambda)$. Algorytm może wewnętrznie korzystać z losowości. Sam zapis jego wywołania nie stwierdza jednak, że wynik jest jednostajny. Nie utożsamiamy też losowania z warunkiem przynależności $r\in\mathbb Z_q$, który jedynie określa, gdzie leży dana wartość.

Wielka litera często oznacza zmienną losową, a mała jej konkretną wartość. $\Pr[X=x]$ to prawdopodobieństwo otrzymania właśnie $x$.

$\Pr[E\mid F]$ czytamy „prawdopodobieństwo zdarzenia $E$, pod warunkiem $F$”. Zakładamy $\Pr[F]>0$. Dwa niezależne losowania nie wpływają na swoje rozkłady. Powtórne odczytanie zapamiętanej wartości nie jest niezależnym losowaniem.

Mały rachunek. Losujemy niezależne bity $X,Y$. Pary 00, 01, 10, 11 są równie prawdopodobne. Stąd $\Pr[X=0]=1/2$, ale $\Pr[X=0\mid X=Y]=1/2$ liczymy już tylko wśród par 00 i 11. Jeśli zamiast losować $Y$ przypiszemy $Y=X$, te same wartości brzegowe nadal mają szansę $1/2$, lecz zmienne nie są niezależne.

Funkcje, sumy i arytmetyka

$f:S\to T$ określa zbiór wejść i zbiór wyników funkcji. Złożenie $(f\circ h)(x)=f(h(x))$ wykonuje najpierw $h$. Odwrotna funkcja $f^{-1}$ odwraca bijekcję, czyli przyporządkowanie jeden do jednego. Zapis $f^2$ dla permutacji oznacza dwukrotne złożenie. Kontekst odróżnia go od kwadratu liczby.

$\sum_{i=1}^t a_i=a_1+\cdots+a_t$, a $\prod_{i=1}^t a_i=a_1\cdot\ldots\cdot a_t$. Silnia $n!$ jest iloczynem liczb od 1 do $n$ i liczy permutacje $n$ różnych obiektów. Rachunek modulo $q$ zachowuje resztę z dzielenia. Na przykład $17+9\equiv3\pmod{23}$. Odwrotność modulo nie jest zwykłym ułamkiem. Warunki jej istnienia wprowadzimy przed protokołami grupowymi w W6.

Jak czytać oznaczenia eksperymentu

$\mathcal A$ będzie algorytmem przeciwnika, $\mathcal B$ algorytmem redukcji, a $\lambda$ parametrem bezpieczeństwa. Zapis $\mathcal A^{\mathsf{Sign}}$ oznacza dostęp do usługi podpisującej. Nie jest potęgą algorytmu. Wynik $\bot$ oznacza odrzucenie, nie pustą wiadomość.

Parametr $\lambda$ wybiera rodzinę rozmiarów instancji. Algorytm wydajny w sensie asymptotycznym działa w czasie wielomianowym w $\lambda$. W ocenie konkretnego systemu podajemy też czas, pamięć, liczbę zapytań i prawdopodobieństwo powodzenia. Samo słowo „wielomianowy” nie dobiera kluczy dla rzeczywistego urządzenia.

Prawdopodobieństwo zaniedbywalne maleje szybciej niż odwrotność dowolnego wielomianu. Precyzyjnie, funkcja $\nu(\lambda)\ge0$ jest zaniedbywalna, jeśli dla każdego dodatniego wielomianu $p$ od pewnego parametru zachodzi $\nu(\lambda)<1/p(\lambda)$. Przykładem jest $2^{-\lambda}$. Funkcja $1/\lambda^{10}$ nie jest zaniedbywalna, choć dla dużych parametrów ma małe wartości. PPT, od probabilistic polynomial time, oznacza probabilistyczny czas wielomianowy. Algorytm PPT może korzystać z losowości, a jego czas pracy jest ograniczony wielomianem parametru bezpieczeństwa. „Bezpieczny przeciw wydajnym przeciwnikom” oznacza więc wymaganie dla każdego takiego algorytmu, nie tylko dla testów, które wykonaliśmy. To język definicji asymptotycznych. Dla ustalonego rozmiaru klucza nadal potrzebujemy konkretnej granicy kosztu i szans ataku.

Sprawdź rozumienie: policz $(1010\oplus0110)\oplus0110$. Czy trzykrotne odczytanie jednej wylosowanej wartości daje trzy niezależne próbki? Te dwa pytania wrócą przy szyfrowaniu i wyroczni losowej.