Kryptografia II stopień

Schemat jako krotka algorytmów

Najpierw określamy, co można zrobić i z jakimi danymi. Posiadacz klucza podpisującego ma tworzyć podpisy. Odbiorca ma je sprawdzać bez dostępu do tego sekretu. Inny mechanizm pozwoli każdemu zaszyfrować wiadomość dla odbiorcy, lecz tylko odbiorcy odczytać jej treść. To różne funkcjonalności. Jeszcze nie musimy wiedzieć, czy zrealizujemy je potęgowaniem, działaniami na krzywej czy operacjami na bitach.

Schemat nie jest pojedynczym równaniem. Jest krotką, czyli uporządkowanym zestawem algorytmów o uzgodnionych wejściach i wyjściach. Definicja wskazuje, kto wykonuje każdy algorytm, jakie dane musi posiadać i co otrzymuje. Następnie określa wymagania poprawności oraz osobne wymagania bezpieczeństwa. Sama lista nazw algorytmów nie zapewnia żadnego z tych warunków.

Parametry publiczne oznaczamy przez $pp$, od public parameters. Określają m.in. dopuszczalne rozmiary kluczy, przestrzeń wiadomości $\mathcal M_{pp}$ i sposób kodowania obiektów. Zapis $1^\lambda$ oznacza ciąg $\lambda$ jedynek, nie potęgę liczby 1. Jest standardowym wejściem opisującym parametr bezpieczeństwa. Klucz publiczny to $pk$ (public key), a klucz tajny to $sk$ (secret key). Nazwy algorytmów opisują ich rolę. Ich konkretne obliczenia poznamy przy poszczególnych konstrukcjach.

Setup oznacza ustalenie parametrów, a KeyGen generowanie kluczy. Oddzielamy je, aby publicznych parametrów nie mylić z tajnym kluczem użytkownika. Setup może wskazywać ustalony profil albo losować parametry. Nie oznacza automatycznie zaufanej instytucji ani ceremonii z tajnym stanem. W części publikacji Setup jest włączony do KeyGen lub Gen. Jest to różnica zapisu interfejsu, którą trzeba odróżnić od zmiany algorytmu.

Algorytm, funkcja i pojedyncze wykonanie

Algorytm opisuje sposób wykonania obliczenia. Wywołanie uruchamia go na konkretnych argumentach. Zapis $\sigma\leftarrow\mathsf{Sign}(pp,sk,m)$ oznacza odebranie podpisu, a nie przesłanie klucza do innej osoby. Urządzenie może przechowywać $sk$ wewnątrz i przyjmować od aplikacji tylko wiadomość oraz identyfikator klucza.

Algorytm deterministyczny dla tych samych wejść zwraca ten sam wynik. Algorytm losowy korzysta dodatkowo z własnych losowych bitów. Gdy chcemy je pokazać jawnie, zapisujemy $\mathsf{Sign}(pp,sk,m\mid\rho)$, gdzie $\rho$ oznacza wszystkie losowe bity tego wykonania. Po ustaleniu także $\rho$ wynik jest wyznaczony. Dwa wywołania Sign dla tej samej wiadomości mogą dać różne poprawne podpisy. Nie wymagamy, aby podpis był jednostajnie losowy w całej przestrzeni możliwych ciągów.

W protokole interaktywnym wynik jednego kroku obejmuje również stan do następnego kroku. Sama funkcja od pojedynczego komunikatu do odpowiedzi nie opisuje wtedy całego uczestnika. Musimy wskazać klucze, pamięć sesji, kolejność komunikatów i moment podjęcia decyzji.

Podpis: od interfejsu do przebiegu

Wprowadzamy podpis z dołączoną wiadomością. Wiadomość $m$ pozostaje osobnym wejściem weryfikatora, a $\sigma$ jest podpisem tej wiadomości. Przestrzeń podpisów oznaczamy przez $\mathcal S_{pp}$. Bit decyzji $b$ ma wartość 1 przy akceptacji i 0 przy odrzuceniu.

To interfejs, jeszcze nie konkretna konstrukcja. Wewnątrz Sign nie ma na razie wskazanego równania. Wiemy już jednak, co można przekazać do Verify: wynik $\sigma$ wraz z tą samą wiadomością, parametrami i pasującym kluczem publicznym. Sam podpis nie wystarcza. Nie wolno też podmienić klucza weryfikacji na inny i uważać, że sprawdzamy tego samego autora.

Weryfikator może wykonać swoją czynność później i bez kontaktu z podpisującym. Diagram nie oznacza zatem obowiązkowego połączenia sieciowego. Para $(m,\sigma)$ może zostać zapisana w pliku. Powiązanie $pk$ z właściwą osobą musi być ustalone poza samym Verify. Algorytm sprawdza zgodność z podanym kluczem, nie nazwisko na stronie internetowej.

Poprawność: wyniki algorytmów pasują do siebie

Poprawność mówi o uczciwym wykonaniu. Dla każdych parametrów zwracanych przez Setup, każdej pary kluczy zwracanej przez KeyGen dla tych parametrów i każdej dozwolonej wiadomości wynik Sign ma być akceptowany przez Verify. Przy doskonałej poprawności zapisujemy:

W tym wzorze $pp,pk,sk,m$ są ustalone zgodnie z poprzednim zdaniem. Prawdopodobieństwo dotyczy wewnętrznej losowości Sign. Verify jest tu deterministyczny. Gdy określony schemat dopuszcza zaniedbywalny błąd poprawności, zapisujemy i uzasadniamy taką granicę osobno. Nie ukrywamy jej pod słowem „działa”.

Zgodność typów jest konieczna, ale nie wystarcza. Verify musi umieć odczytać format zwracany przez Sign, lecz musi też zaakceptować uczciwy wynik. Dla szyfrowania wymaganie ma inną postać: Dec ma odzyskać dokładnie wiadomość podaną do Enc. Dla uzgadniania klucza uczciwe, prawidłowo komunikujące się strony mają zakończyć protokół ze zgodnymi kluczami. Każda funkcjonalność ma własny warunek poprawności.

Bezpieczeństwo: czego nie osiągnie przeciwnik

Przeciwnik zna algorytmy i publiczne dane. Nie otrzymuje klucza tajnego atakowanego użytkownika. Nie wystarczy powiedzieć, że nie potrafi wywołać Sign z właściwym kluczem. Może próbować znaleźć akceptowany podpis dowolną inną metodą, również bez odzyskiwania klucza. Definicja bezpieczeństwa ma obejmować każdą wydajną strategię zgodną z modelem.

Może także otrzymać poprawne podpisy od prawdziwego podpisującego. Ich ponowne pokazanie nie jest nowym fałszerstwem. Dlatego potrzebujemy dwóch warunków jednocześnie: akceptacji pod atakowanym kluczem i nowej wiadomości. W modelu z dostępem do podpisywania wygląda to następująco:

1. Prowadzący eksperyment uruchamia Setup i KeyGen. Przeciwnik $\mathcal A$ otrzymuje $pp,pk$, lecz nie $sk$.
2. Przeciwnik może wybierać wiadomości $m_i$ i otrzymywać wyniki $\mathsf{Sign}(pp,sk,m_i)$. Zbiór $Q$, początkowo pusty, zapamiętuje wszystkie wiadomości, o których podpisanie zapytano. Kolejne pytania mogą zależeć od poprzednich odpowiedzi.
3. Przeciwnik zwraca parę $(m^\star,\sigma^\star)$. Gwiazdka oznacza jego końcową próbę. Nie wskazuje, że do jej utworzenia użyto Sign.
4. Eksperyment sprawdza format, przynależność $m^\star\in\mathcal M_{pp}$ i poniższy warunek wygranej.

Schemat jest niepodrabialny w tym modelu, jeśli dla każdego przeciwnika PPT istnieje zaniedbywalna funkcja $\nu_{\mathcal A}$ ograniczająca $\Pr[\mathsf{Win}]$ w zależności od $\lambda$. Prawdopodobieństwo obejmuje losowania parametrów, kluczy, podpisów oraz samego przeciwnika. Czas pracy i liczba zapytań są wielomianowo ograniczone. Nie jest to obietnica, że fałszerstwo jest logicznie niemożliwe. Jest to granica szans jego wydajnego znalezienia.

Ten cel nazywa się EUF-CMA, od existential unforgeability under chosen-message attack, czyli egzystencjalna niepodrabialność przy ataku z wybranymi wiadomościami. Słowo „egzystencjalna” oznacza, że wystarczy choć jedna nowa poprawnie podpisana wiadomość wybrana przez przeciwnika. Boneh–Shoup, §13.1 i eksperyment 13.1.

Dwa ważne rozróżnienia. Wygenerowanie własnej pary kluczy i podpisanie dokumentu własnym kluczem nie łamie tego wymagania. Sprawdzamy podpis pod konkretnym atakowanym $pk$. Z kolei zmiana podpisu pod wiadomością już należącą do $Q$ nie jest sukcesem w tej grze. Silniejszy cel, który wyklucza także nową parę podpis–wiadomość dla wcześniej podpisywanej wiadomości, poznamy przy podpisach.

Kontrprzykład: poprawność bez ochrony. Wyobraź sobie celowo błędny wariant. Sign zawsze zwraca jeden bit 0, a Verify akceptuje ten bit dla każdej wiadomości i ignoruje klucz. Uczciwy podpis zawsze przechodzi kontrolę. Przeciwnik bez żadnego zapytania również podaje 0 dla dowolnej wiadomości i wygrywa z prawdopodobieństwem 1. Formalne wejście $sk$ w nagłówku algorytmu niczego nie zabezpiecza, jeśli konstrukcja go nie wykorzystuje do zapewnienia właściwej gwarancji.

Różne funkcjonalności, różne cele ochrony

Rozdzielenie dostępnych i niedostępnych danych jest punktem wyjścia. Nie każda własność bezpieczeństwa sprowadza się jednak do wytworzenia niedostępnego wyniku. Czasem chcemy uniemożliwić rozpoznanie, skąd dany wynik pochodzi albo jaką wiadomość ukrywa.

Później dodamy także anonimowość. Poprawne Verify może potwierdzać udział kogoś z dopuszczalnego zbioru, a osobna gra pytać, czy da się rozpoznać konkretną osobę. Ten sam interfejs może mieć kilka niezależnych wymagań bezpieczeństwa.

Jeden sekret, dwa klucze, rozmowa

• Szyfrowanie symetryczne używa tego samego tajnego klucza $k$ po obu stronach. KeyGen zwraca $k$, a interfejsy mają postać $\mathsf{Enc}(pp,k,m)$ oraz $\mathsf{Dec}(pp,k,C)$. Mechanizmy z nonce i uwierzytelnianymi danymi mają dodatkowe jawne argumenty, które wprowadzimy przy ich definicjach.
• Szyfrowanie publiczne używa $pk$ do szyfrowania i $sk$ do odszyfrowania. Nadawca nie musi znać sekretu odbiorcy.
• Podpis używa $sk$ do podpisania i $pk$ do sprawdzenia. Nie jest „szyfrowaniem kluczem prywatnym”.
• Identyfikacja interaktywna jest rozmową dowodzącego z weryfikatorem. Oprócz kluczy opisujemy kolejność wiadomości, stany stron i warunek akceptacji. Nie zastępujemy tej rozmowy pojedynczym wywołaniem Sign.

Parametry $pp$ będziemy czasem pomijać w zapisie, gdy są już ustalone dla całego fragmentu. Analogicznie $\mathsf{Gen}(1^\lambda)$ w skróconym eksperymencie oznacza przygotowanie parametrów i kluczy, z parametrami publicznymi dostępnymi uczestnikom. Nie oznacza innego sposobu generowania sekretu. Schemat i reguły jego użycia muszą pasować do eksperymentu bezpieczeństwa.

Pełne interfejsy znajdują się przy swoich rodzinach: identyfikacja, podpis, AKE i szyfrowanie publiczne. W każdym przypadku odróżnimy algorytm od jego wykonania w urządzeniu. Algorytm określa rachunek. Urządzenie przechowuje klucz i stan oraz egzekwuje reguły dostępu. Nie każda aplikacja uprawniona do żądania podpisu powinna móc odczytać klucz.

Trzy poziomy opisu

1. Funkcjonalność i interfejs. Co chcemy umożliwić? Jak nazywają się algorytmy, co przyjmują, co zwracają i kto ma ich argumenty?
2. Wymagania. Co ma zachodzić po uczciwych wywołaniach? Co widzi przeciwnik, jakie usługi otrzymuje i co oznacza jego sukces? Poprawność oraz bezpieczeństwo zapisujemy osobno, zanim ocenimy konstrukcję.
3. Konstrukcja i uzasadnienie. Jakie dokładnie obliczenia wykonują algorytmy? Dlaczego zapewniają poprawność? Przy jakich założeniach spełniają zdefiniowany cel bezpieczeństwa? Schnorr wykorzysta równanie w grupie, a AES operacje na bajtach. Matematyka realizuje określoną funkcjonalność, nie zastępuje jej definicji.

Każdą kolejną konstrukcję czytaj w tej kolejności. Najpierw znajdź jej algorytmy. Prześledź, jak wynik jednego staje się argumentem następnego. Dopiero potem wejdź w rachunek w poszczególnych boksach. Test wykonania sprawdza konkretny przypadek. Dowód uzasadnia wymaganie dla wszystkich przypadków objętych twierdzeniem.

Sprawdź rozumienie: które dane są potrzebne do Verify, ale nie są wynikiem Sign? Dlaczego otrzymanie prawdziwego podpisu nie łamie niepodrabialności? Czy Verify akceptujący wszystko byłby poprawny? Czy byłby bezpieczny? Zastosuj ten podział w C0.6–7 i przy projektowaniu interfejsów w laboratorium.

Definicje ogólne i rozróżnienie szyfrowania oraz podpisów: Boneh–Shoup, rozdziały 11 i 13. Do tych samych interfejsów wrócimy w eksperymentach: wyrocznia podpisująca będzie wykonywała Sign, a wyrocznia deszyfrująca Dec. Przeciwnik otrzyma wynik dozwolonego wywołania, nie całą pamięć urządzenia.

Przeciwnik, eksperyment i wyrocznie

Adwersarz, czyli przeciwnik, to algorytm opisujący strategię ataku. Nie ograniczamy go do pomysłów autora systemu. Może zapamiętywać wcześniejsze odpowiedzi, wybierać następne kroki na ich podstawie i losować własne wartości. Słowo „adaptacyjny” oznacza właśnie taki dobór działań po uzyskaniu nowych informacji.

Siłę przeciwnika opisujemy przez interfejs, budżet i cel. Interfejs mówi, co wolno zrobić. Budżet ogranicza czas, pamięć, liczbę sesji i zapytań. Cel określa, kiedy uznajemy atak za udany. Nawet bardzo szybki algorytm nie ma prawa korzystać z sekretu, którego jego interfejs nie ujawnia.

API

Application Programming Interface. Interfejs programistyczny, czyli określony zestaw dostępnych operacji.

Jak czytać skróty modeli ataku

Angielskie nazwy będą wracać w rysunkach i publikacjach. Skrót opisujący dostęp przeciwnika nie jest jeszcze deklaracją bezpieczeństwa. Najpierw ustalamy, co przeciwnik może zrobić. Osobno podajemy, czego mimo tego nie powinien osiągnąć.

W nazwach związanych z szyfrowaniem plaintext oznacza tekst jawny, czyli wiadomość przed zaszyfrowaniem. Ciphertext to szyfrogram, czyli wynik szyfrowania. Słowo chosen oznacza, że dane wybiera przeciwnik, a known, że je zna, lecz nie musi mieć wpływu na ich wybór.

Cyfry 1 i 2 w CCA1 i CCA2 oznaczają warianty dostępu, nie liczbę zapytań. Historyczna nazwa non-adaptive przy CCA1 nie zabrania uzależnienia kolejnego zapytania od wcześniejszej odpowiedzi. Wskazuje, że pytań o deszyfrowanie nie można już dostosować do otrzymanego wyzwania. Handbook of Applied Cryptography, §7.2, Bellare i in., definicja 2.1.

Nazwę własności bezpieczeństwa odczytujemy osobno:

• IND, od indistinguishability, to nierozróżnialność. W grze poufności przeciwnik próbuje rozpoznać, którą z dwóch wybranych wiadomości zaszyfrowano.
• EUF, od existential unforgeability, to egzystencjalna niepodrabialność. Sukcesem jest znalezienie choć jednej poprawnej pary wiadomość–podpis spełniającej warunek nowości. Nie trzeba podrobić konkretnego dokumentu wskazanego z góry przez inną osobę.

Dlatego IND-CPA rozwijamy jako indistinguishability under chosen-plaintext attack: nierozróżnialność przy ataku z wybranym tekstem jawnym. Analogicznie odczytujemy IND-EAV, IND-CCA1 i IND-CCA2, zmieniając zakres dostępu zgodnie z tabelą. Nazwa EUF-CMA oznacza existential unforgeability under chosen-message attack: egzystencjalną niepodrabialność przy ataku z wybranymi wiadomościami. W tym modelu końcowy podpis musi dotyczyć wiadomości, której wcześniej nie zlecono do podpisania.

IND-EAV

indistinguishability against eavesdropping. Nierozróżnialność przy podsłuchu.

IND-CCA1

indistinguishability under non-adaptive chosen-ciphertext attack. Nierozróżnialność przy dostępie do deszyfrowania tylko przed wyzwaniem.

IND-CCA2

indistinguishability under adaptive chosen-ciphertext attack. Nierozróżnialność przy adaptacyjnym ataku z wybranym szyfrogramem.

Eksperyment, nazywany też grą bezpieczeństwa

Słowo gra nie oznacza tu zręczności ani rywalizacji człowieka z komputerem. Oznacza precyzyjnie zdefiniowany eksperyment z wynikiem. Jedną stroną jest przeciwnik, drugą program prowadzący eksperyment, często nazywany challengerem. Prowadzący generuje klucze, odpowiada na dozwolone pytania i sprawdza końcowy warunek. Przeciwnik nie widzi całej pamięci prowadzącego.

Eksperyment można zapisać jako program. Wynik 1 znaczy, że przeciwnik osiągnął cel, a 0, że go nie osiągnął. Powtarzamy rozumowanie nad wszystkimi losowaniami kluczy, monet przeciwnika i pozostałych algorytmów. Prawdopodobieństwo sukcesu nie jest odsetkiem, który musimy koniecznie zmierzyć w przeglądarce. Jest wielkością matematyczną określoną przez ten eksperyment.

Przykład niepodrabialności podpisu. Prowadzący tworzy parę kluczy. Publiczny przekazuje przeciwnikowi. Przeciwnik może prosić o podpisy pod wybranymi dokumentami. Na końcu przedstawia nowy dokument i podpis. Wygrywa, jeśli podpis jest poprawny, a dokument nie należał do wcześniej podpisywanych. Warunek nowości wyklucza trywialne ponowne pokazanie otrzymanego podpisu. Nie zabrania analizy ani modyfikacji wcześniejszych odpowiedzi.

Na rysunku przeciwnika oznaczamy przez $\mathcal A$, a challengera przez $\mathsf{Ch}$. Challenger nie próbuje wygrać własną strategią. Wykonuje ustalone reguły, według których oceniamy przeciwnika. To model usługi i jej otoczenia, nie dodatkowy uczestnik rzeczywistego protokołu.

Algorytm $\mathsf{Gen}$ generuje klucz publiczny $pk$ i klucz tajny $sk$. Zapis $1^\lambda$ jest standardowym wejściem opisującym parametr bezpieczeństwa. Algorytm $\mathsf{Sign}$ podpisuje, a $\mathsf{Verify}$ sprawdza podpis i zwraca 1 przy akceptacji. Zbiór $Q$, początkowo pusty, gromadzi wiadomości przesłane do podpisania. Indeks $i$ numeruje zapytania. Gwiazdka w $(m^\star,\sigma^\star)$ oznacza końcową próbę fałszerstwa, nie operację na wiadomości.

To model EUF-CMA: niepodrabialność przy dostępie do podpisywania wybranych wiadomości. Przeciwnik sam wybiera wiadomość, którą spróbuje podrobić. Może też nie zadawać żadnych pytań. Liczba pytań i czas pracy muszą mieścić się w budżecie przyjętym w twierdzeniu. Boneh–Shoup, eksperyment 13.1.

W tym przykładzie sukces mierzymy prawdopodobieństwem akceptacji fałszerstwa. W eksperymencie poufności będziemy zgadywać losowy bit. Tam naturalnym punktem odniesienia jest $1/2$. Nie każdy model ma tę samą definicję przewagi.

Wyrocznia jako dozwolona usługa

Wyrocznia podpisująca jest formalnym interfejsem: podaj wiadomość, odbierz podpis. W rzeczywistości odpowiada np. legalnej usłudze podpisu, z której przeciwnik może korzystać. Model może celowo przyznawać nawet szerszy dostęp niż konkretna aplikacja. Mocniejsza gwarancja jest przydatna, o ile interfejs nie czyni celu trywialnym.

Wyrocznia nie daje przeciwnikowi klucza tylko dlatego, że używa go wewnętrznie. Podobnie korzystanie z terminala płatniczego nie oznacza znajomości wszystkich jego sekretów. Osobne zapytanie o ujawnienie klucza to dodatkowa możliwość, którą trzeba jawnie dopuścić.

Liczba zapytań ma znaczenie. Sto podpisów to inny zasób niż miliard. Jeśli każde zgadywanie ma małą szansę powodzenia, suma szans rośnie wraz z liczbą prób. Gdy zapytanie zawiera bardzo długą wiadomość, do kosztu należy także jej przetworzenie. Interfejs nie oznacza nieograniczonego czasu ani nieskończenie dużych wejść.

Wyrocznia losowa jest innym pojęciem

ROM rozwijamy jako random oracle model, czyli model wyroczni losowej. To sposób idealizowania funkcji haszującej w analizie, a nie kolejny poziom dostępu typu CPA lub CCA. Możemy np. badać niepodrabialność EUF-CMA w modelu ROM.

Nie utożsamiamy wyroczni losowej z wyrocznią podpisującą. Pierwsza idealizuje publiczną funkcję haszującą. Druga używa sekretnego klucza do wykonywania algorytmu podpisu. Podpis może wewnętrznie korzystać z hasza, ale te dwa interfejsy mają inne zadania i inne wyjścia.

Wyrocznię losową wyobrażamy sobie jako nieskończoną, raz wylosowaną tabelę. Dla praktycznego opisu nie trzeba od razu wypełniać wszystkich wierszy. Przy pierwszym pytaniu losujemy odpowiedź. Zapamiętujemy ją. Powtórzone identyczne wejście zawsze dostaje tę samą odpowiedź. Nowe wejście dostaje niezależną odpowiedź. Dwa różne wejścia mogą przypadkowo dać ten sam wynik.

Na rysunku $\mathcal A$ oznacza przeciwnika, $m$ wiadomość, $\sigma$ podpis, a $sk$ tajny klucz usługi. Dla wyroczni losowej $\mathcal H$ zapytanie nazywamy $x$, odpowiedź $y$, a zapamiętane pary tworzą tabelę $T$. Zapis $T[x]=y$ oznacza wpis przypisujący temu wejściu tę odpowiedź. W animacji widzimy wnętrze modelu. Interfejs przeciwnika ujawnia tylko odpowiedź na zadane pytanie, nie całą tabelę.

Odpowiedz(x):
    jeśli tabela zawiera x: zwróć tabela[x]
    wylosuj y z zadeklarowanej dziedziny wyników
    tabela[x] = y
    zwróć y

To tzw. leniwe losowanie. Wyrocznia nie potrzebuje hasła ani klucza podpisującego. Dostęp ma przeciwnik i mają go uczciwe strony. W praktyce publiczny algorytm haszujący można obliczać lokalnie. Jego ideał w dowodzie pozwala precyzyjnie liczyć, które wejścia zostały sprawdzone i jaka niewiadoma pozostaje przed pierwszym zapytaniem.

Dlaczego tabela zachowuje się jak losowa funkcja

Na początku $T=\varnothing$. Sprawdzenie wpisu nie jest losowaniem. Jeżeli $x\in\operatorname{dom}(T)$, odczytujemy dokładnie poprzednie $T[x]$. W przeciwnym razie losujemy nową odpowiedź jednostajnie z zadeklarowanej, skończonej dziedziny wyników $\mathcal D$, niezależnie od odpowiedzi dla innych wejść. Zapisujemy ją przed wysłaniem. Symbol $\operatorname{dom}(T)$ oznacza zbiór wejść już zapisanych w tabeli.

Niech $R=|\mathcal D|$ będzie liczbą możliwych wyników. Dla nowego wejścia i każdego $y\in\mathcal D$, nawet po ustaleniu dotychczasowego widoku przeciwnika $V$, zachodzi

Widok $V$ zawiera dotychczasowe zapytania i odpowiedzi, nie przyszłe losowania. Przeciwnik może wybierać następne wejście zależnie od wcześniejszych wyników. Nowy, jeszcze niesprawdzony argument nadal otrzymuje niezależny wynik. Dla ponowionego argumentu odpowiedź jest natomiast całkowicie określona przez tabelę.

• Spójność: ta sama wiadomość zawsze daje ten sam hasz w jednym eksperymencie. Nowe losowanie przy każdym powtórzeniu nie modelowałoby funkcji.
• Nieprzewidywalność nowego wyniku: trafienie zadanej wartości w jednym świeżym zapytaniu ma prawdopodobieństwo $1/R$. W najwyżej $t$ świeżych próbach znalezienia obrazu równego ustalonemu celowi granica wynosi $t/R$.
• Kolizje: przy $t$ różnych wejściach prawdopodobieństwo co najmniej jednej kolizji nie przekracza $\min\{1,t\cdot(t-1)/(2R)\}$. Nie zakazujemy kolizji i nie odrzucamy losowania tylko dlatego, że wynik wystąpił już dla innej wiadomości.

To klasyczne granice dla dostępu przez zapytania, nie gwarancja braku kolizji. Dla wyników długości $n$ bitów mamy $R=2^n$. W demonstracji $R=101$, dlatego zbieżne wyniki nie są zaskoczeniem. Skrypt korzysta z generatora przeglądarki i losowania przez odrzucanie, aby nie wprowadzać obciążenia operacją modulo. Idealna niezależność należy do modelu matematycznego, nie do deklaracji o fizycznej losowości komputera.

Formalne podejście ROM wprowadza praca Bellare i Rogaway, Random Oracles are Practical: A Paradigm for Designing Efficient Protocols, ACM CCS 1993. Probabilistyka wyjaśnia własności idealnej funkcji. Bezpieczeństwo korzystającego z niej protokołu wymaga jeszcze osobnego dowodu.

ACM

Association for Computing Machinery. Międzynarodowe stowarzyszenie naukowe związane z informatyką.

CCS

Conference on Computer and Communications Security. Konferencja o bezpieczeństwie komputerów i komunikacji.

Granica idealizacji. SHA-256 jest konkretnym, skończonym algorytmem, a nie idealną losową funkcją. Dowód w modelu wyroczni losowej nie jest automatycznie dowodem po podstawieniu dowolnego hasza. Programowanie wyroczni przez symulator należy do narzędzi dowodu. Nie znaczy, że rzeczywisty przeciwnik może wybrać wynik SHA-256. Takie rozdzielenie modelu i implementacji pozwala czytać późniejsze dowody bez przypisywania stronom nierealnych uprawnień.

SHA-256

Secure Hash Algorithm. Algorytm bezpiecznego haszowania. W nazwie SHA-256 liczba oznacza 256-bitowy wynik.

Sprawdź rozumienie: jeżeli przeciwnik może poprosić o podpis dowolnej wiadomości, dlaczego nie wygrywa od razu? Co zmieni się, gdy po podpisie wolno mu również poznać jednorazową wartość losową używaną przy podpisywaniu, nazywaną nonce? Odpowiedź zależy od celu i ujawnień, a nie tylko od nazwy algorytmu.

Literatura: Goldwasser–Bellare, Boneh–Shoup.