Sezamie otwórz się, krótko o dowodach z wiedzą zerową
Cześć!
Pamiętacie może dziecięce przepychanki w stylu „Wiem, ale nie powiem”? Dzisiaj zastanowimy się w jaki sposób projektanci kryptosystemów radzą sobie z podobnym problemem – jak udowodnić znajomość sekretu (np. tajnego klucza) bez ujawniania go nikomu
.
Analogia jaskini jako przykład dowodu o wiedzy zerowej
Możemy to zrobić korzystając ze swego rodzaju dowodu nie wprost, zanim jednak pokażę Wam to na przykładzie protokołu identyfikacji Schnorr’a, chciałbym żebyście przyjrzeli się pewnej dość obrazowej analogii. Spójrzcie na rysunek poniżej.
Wyobraźcie sobie, że ta grafika przedstawia plan kampusu NSA (amerykańskiej Agencji Bezpieczeństwa Narodowego). Drzwi 2 stanowią wejście do cywilnej części budynku podczas gdy drzwi 3 są dla personelu wojskowego. W bazie pod numerem 1 znajduje się pomieszczenie z klatką schodową prowadzącą do podziemnej serwerowni i jest to jedyne bezpośrednie przejście pomiędzy częścią cywilną a wojskową. Wejścia na klatkę od obu stron zabezpieczone są kartą magnetyczną z PIN’em. Część personelu wojskowego zajmująca się sprzętem komputerowym ma dostęp do serwerowni oraz obu części budynku… Chociaż tak między Bogiem i prawdą, Kevin Mitnick we wspomnianej kiedyś książce „Sztuka Infiltracji” opisywał, że największe uprawnienia dostępu fizycznego mają zazwyczaj sprzątaczki 😉.
Główną bohaterką opowiadania będzie żona jednego z pracowników. Teraz wszędzie jest moda na szukanie ruskich agentów więc założymy, że została ona podkupiona przez rosyjskie służby aby ustalić czy jej mąż posiada dostęp do serwerowni. Ponieważ nie jest ona drugim Jamesem Bondem wynajęła do pomocy prywatnego detektywa. Na szczęście mąż też nie jest na tyle rozgarnięty aby pamiętać, którymi drzwiami danego dnia wchodził 😉.
Przejścia są pilnowane przez portiera, aby nikt nie uprawiał tzw. tailgating’u, tj. wchodzenia na ogonie jednak doświadczony detektyw wie, że skoro jest on średnio rozgarnięty (agent w stylu Johnny’ego English’a) nie da rady pilnować się zawsze – przyjęto za okres obserwacji 3 miesiące. W końcu udało się i na sam koniec pracy z teleobiektywem w ręce dojrzał mężczyznę wchodzącego drzwiami 2 i wychodzącymi 3.
Zmienimy teraz nieco tę historię – przez 3 miesiące mężczyzna się pilnował a żony nie jest stać na dalszą obserwację bo męża zdziwi saldo na koncie. Żona wykazała się wręcz szatańską pomysłowością. Otóż pani, nazwijmy ją Twardowska (w końcu amerykanie nie rozróżniają polskich od rosyjskich nazwisk), wymyśliła sobie grę. Umówiła się z mężem, że nie będzie pilnować jak pan Twardowski wchodzi ale będzie mówić mężowi którymi drzwiami ma wyjść 😊. I tego dopilnuje… Jak powiedziała tak zrobiła. W końcu musi obserwować go tylko przez godzinę czy dwie a nie musi płacić pełnej dniówki detektywowi. A biorąc pod uwagę, że mąż wie, że nie ujawni informacji, którymi drzwiami wszedł mówi: „Dobra, zacznijmy zabawę!”. Czy mąż wyciągnął prawidłowe wnioski?
Odpowiedzmy sobie na pytanie – jakie jest prawdopodobieństwo, że mężczyzna zna PIN przy jednej próbie? Prawdopodobieństwo, to wynosi . Spójrzcie na tabelkę poniżej – jedynka oznacza, że wybrał on dokładnie to samo wyjście co żona.
| Wybrane przez żonę wyjście | |||
| Lewe drzwi | Prawe drzwi | ||
| Losowo wybrane przez męża wejście | Lewe drzwi | 1 | 0 |
| Prawe drzwi | 0 | 1 | |
Sprawdźmy jakie będzie prawdopodobieństwo, że w tydzień, stosując tą, grę poznamy prawdę? Prawdopodobieństwo, że przez tydzień zarówno wchodził jak i wychodził jest… pewne czyli wynosi 1. Przeprowadźmy krótkie rachunki:
Zdarzenie to jest więc niemal pewne. Zwróćcie uwagę, że poznaliśmy informację czy mąż zna PIN a nie zdradził nam samej informacji. Czy da się zrealizować coś podobnego wykorzystując matematykę? Bajeczka może i jest dość mocno naciągana ale pokażę Wam teraz protokół Schnorr’a dzięki któremu jedna osoba może udowodnić drugiej znajomość tajnego klucza nie zdradzając go.
Protokół identyfikacji Schnorr’a
Zacznijmy z kolejną historią – łatwiej będzie przedstawić mi protokół, jeśli naszym bohaterom nadamy imiona 😉 Nazwijmy ich Alicja (będzie ona posiadaczką tajnego klucza) i Bob (będzie miał informację potrzebną do weryfikacji). Alicja chce udowodnić Bobowi znajomość sekretu – aby to zrobić musi przeprowadzić z nim wymianę kilku wiadomości. Spójrzcie na diagram poniżej, jednak najpierw parę założeń:
- g jest parametrem znanym zarówno przez Alicję i Bob’a,
- Alicja jest posiadaczką klucza prywatnego
i przekazała Bob’owi wartość
,
- Liczby a oraz c są losowymi liczbami naturalnymi.
W jaki sposób to równanie zdradza nam, że Alicja zna hasło? Odpowiedź tkwi w matematyce jeszcze z lat szkolnych. Dowód jest następujący:
Równość jest tylko wtedy prawdziwa, gdy Alicja zna klucz prywatny. Pozostało jeszcze pytanie czy jest on bezpieczny. Dowodzimy tego z wykorzystaniem tzw. modelu z wyrocznią losową.
Dowody z wyrocznią losową
Cały pomysł dowodu inspirowany jest wyrocznią delficką. W starożytnej Grecji, w miejscowości Delfy znajdowała się znana niegdyś w całym antycznym świecie wyrocznia. Za przepowiednie odpowiadała Pytia – siedząca na trójnogu, odurzone oparami ze szczeliny w ziemi dziewczyna, wychowywana od urodzenia w świątyni. W narkotycznym widzie odpowiadała ona luźnymi słowami, które później kapłani interpretowali jako przepowiednie. Wpływały one na wszystko, od polityki do zwykłych i codziennych spraw a jako, że specjalnie wiary w takie przepowiednie nie pokładam sądzę, że były one raczej losowe. W tym też charakterze będziemy wykorzystywać wyrocznię w naszym dowodzie.
Dowód ten może Wam przypominać dowody nie wprost z lekcji matematyki jednak na razie musimy postawić parę założeń:
(od Oracle) jest to wyrocznia, która wciela się w rolę strony weryfikującej tożsamość, zakładamy, że potrafi odróżnić wymagane przez protokół wartości od liczb zupełnie losowych,
(od Adversary) – nasz oponent, który poddaje się identyfikacji, zakładamy, że nie zna klucza prywatnego jednak ma strategię na prawidłową identyfikację.
- Potrafimy dokonać transkrypcji wszystkich zapisów protokołu.
Od czego zaczynamy dowód? Spójrzcie na rysunek poniżej:
Przedstawia on zapis dwóch przejść protokołu. Liczby ,
służą inicjacji protokołu (nazywamy te wiadomości commitment’ami, zobowiązaniem względem weryfikatora),
,
są wyzwaniami (challenge) rzuconymi przez wyrocznię,
,
są to dowody posiadania znajomości klucza prywatnego a
,
odpowiedzi wyroczni. Warto przypomnieć, że Adwersarz nie zna klucza prywatnego jednak potrafi wyciągnąć z kapelusza (albo mówiąc bardziej technicznie wylosować lub wygenerować) liczby, które umożliwią mu identyfikację przed wyrocznią. Przypuśćmy, że nasz oponent potrafi dokonać transkrypcji wszystkich przebiegów protokołu (oznaczymy tą liczbę literą
). Spójrzmy na ten zapis transkrypcji:
…
Jeśli jest dostatecznie duże (lub skrajnie – jako
zostaną wykorzystane wszystkie opcje) z pewnym prawdopodobieństwem powtórzy się któryś z wcześniej wykorzystanych commitment’ów (liczb
). Dla ułatwienia załóżmy, że
powtórzy się jako
i wyrocznia przekaże nowe wyzwanie
a adwersarz wykorzysta swoje moce by wygenerować nową wartość
. Jakie są tego konsekwencje?
Jeśli liczby i
były wcześniej wygenerowane z wykorzystaniem strategii Adwersarza i
wiemy, że
Wtedy adwersarz może obliczyć klucz prywatny z wykorzystaniem następującej formuły , gdyż zarówno wartości
,
,
,
są mu doskonale znane.
Czego to dowodzi? Protokół byłby możliwy do złamania, gdyby istniał adwersarz z nieskończoną pamięcią i czasem żeby przeszukać dostatecznie dużą część przestrzeni oraz potrafiący wylosować liczby zgodne z protokołem… Czego prawdopodobieństwo jest pomijalnie małe.
Czy Was ten dowód przekonuje? Mnie osobiście nie do końca… Przyjmujemy mało realne założenia, żeby dojść do oczywistych wniosków – w czasie studiów nazywałem tego typu dowody dowodami przez machanie rękami albo dowodami przez niemalże założenie tezy 😉. Przytaczam go przede wszystkim z poczucia kronikarskiego obowiązku .
Powrót do świata matematyki
O ile sam protokół działa to jest też niestety jest jeden drobny szkopuł. Matematycy lubią nieskończoność ale informatycy nie radzą sobie z nią najlepiej. O ile wyobraźnia potrafi wytrzymać nieskończenie wielką liczbę tak komputery nie mają pamięci by je przechowywać. Spójrzcie na zakresy poszczególnych typów całkowitoliczbowych w języku Rust na 64-bitowym procesorze Intel’a:
| Nazwa typu | Dolny zakres | Górny zakres |
| u8 | 0 | 255 |
| u16 | 0 | 65535 |
| u32 | 0 | 4294967295 |
| u64 | 0 | 18446744073709551615 |
| i8 | -128 | 127 |
| i16 | -32768 | 65535 |
| i32 | -2147483648 | 2147483647 |
| i64 | -9223372036854775808 | 9223372036854775807 |
Liczby typu u64 wydają się duże ale biorąc pod uwagę poziom bezpieczeństwa i fakt, że intensywnie wykorzystujemy potęgowanie potrafię sobie wyobrazić, że będzie to wartość zbyt mała i przekroczymy zakres wartości… Czy potrafimy sobie z tym poradzić?
Odpowiedź jest na szczęście pozytywna 😊 Naszym głównym problemem jest fakt, że mnożenie w pewnym momencie może nas wyprowadzić poza zbiór osiągalnych wartości. Powinniśmy skonstruować sobie operację matematyczną, która będzie zamknięta w sensownym zbiorze wartości. Na pomoc tutaj przychodzi nam algebra abstrakcyjna i teoria struktur algebraicznych. Zanim jednak o tym, przez chwilę poopowiadam Wam o liczbach pierwszych, które będą dla nas w pewnym momencie istotne.
Liczby pierwsze
Mam nadzieję, że się nie obrazicie za drobne przypomnienie, że liczby pierwsze są to liczby naturalne, które dzielą się tylko i wyłącznie przez 1 oraz samą siebie. Tak na marginesie jest nawet jeden dowcip z brodą jak u Albusa Dumbledora jak różni naukowcy sprawdzają czy liczby nieparzyste są pierwsze.
Studenci z różnych wydziałów dostali zadanie: udowodnij, że wszystkie liczby nieparzyste większe od 1 są pierwsze.
– Matematyk: Dla 3 – zgadza się. A dalej jakoś to pójdzie przez indukcję…
– Inżynier: Dla 3 – zgadza się, dla 5 – zgadza się, dla 7 – zgadza się…
– Chemik: Dla 3 – zgadza się, dla 5 – zgadza się, dla 7 – zgadza się, dla 9 – zgadza się…
– Fizyk: Dla 3 – zgadza się, dla 5 – zgadza się, dla 7 – zgadza się, 9 to błąd pomiarowy, dla 11 – zgadza się, dla 13 – zgadza się…
– Astronom: Dla 639547 – zgadza się, dla 979949 – zgadza się…
– Informatyk: Dla 3 – zgadza się, dla 3 – zgadza się, dla 3…
Na potrzeby protokołu będziemy potrzebowali wygenerować odpowiednio długie (tj. w zapisie wykorzystującym system dwójkowy) liczby pierwsze. Aby to zrobić możemy spróbować wykonać następujące działania:
- Wygenerować wszystkie liczby pierwsze z wykorzystaniem sita Eratostenesa, dopóki nie osiągniemy większego zbioru liczb z których możemy losować – rozwiązanie kiepskie bo wymaga za równo masę pamięci jak i czasu…
- Wylosować ciąg bajtów i sprawdzić czy liczba jest podzielna przez wszystkie liczby mniejsze od niej – rozwiązanie niewiele lepsze, ale wciąż czasochłonne.
Możemy pójść o krok dalej, że nie ma sensu sprawdzać wszystkich dzielników liczby a zatrzymać się na jej pierwiastku jednak przy dużych liczbach wciąż nie jest to oczekiwane, efektywne rozwiązanie problemu.
Rozwiązanie, które jest faktycznie wykorzystywane bazuje na losowości i statystyce nazywane testem Millera-Rabina. Poniżej znajduje się opis algorytmu:
Algorytm ten będzie częścią implementacji protokołu Schnorr’a, do której link znajdziecie na końcu artykułu a teraz możemy wrócić do tematu struktur algebraicznych.
Podstawowa struktura algebraiczna – grupa
Strukturą algebraiczną nazywamy zbiór oraz działania na nim określone, które spełniają pewne konkretne własności. Warto wspomnieć, że pomysł C++’owych szablonów, gdzie funkcja do działania potrzebuje aby argumenty spełniały jedynie wąsko określone wymagania formalne. Dobrze, ale przejdźmy do rzeczy i zajmijmy się najbardziej podstawową strukturą, która wkrótce będzie dla nas istotna.
Pierwszą i najważniejszą strukturę odkrył Evariste Galois w 1832 roku jest to grupa. Definiujemy ją jako parę , gdzie
jest to zbiór na którym określone jest dowolne działanie binarne (tzn. dwuargumentowe, podobnie jak dodawanie czy mnożenie). Poniżej przedstawiona jest lista własności, które musi spełniać działanie na grupie:
- Łączność:
,
- Identyczność (albo istnienie elementu neutralnego
:
lub
,
- Istnienie elementu przeciwnego
:
.
W zależności czy używamy notacji addytywnej (bazującej na dodawaniu) używamy zapisu
(i nazywamy elementem przeciwnym) a w przypadku multiplikatywnej (bazującej na dodawaniu) używamy zapisu (i nazywamy elementem odwrotnym). Co oznacza, zamkniętość działania
w grupie? Dla dowolnych dwóch elementów zbioru wynik działania
również należy do zbioru
.
Jeśli dodatkowo działanie to jest przemienne to taką grupę nazywamy abelową.
Jakie znamy przykłady grup?
– addytywna grupa liczb całkowitych, elementy są liczbami całkowitymi a operacją dodawanie,
– multiplikatywna grupa niezerowych reszt modulo 7, elementami są liczby od 1 do 6 a działaniem mnożenie modulo 7. Poniżej znajduje się tabela pokazująca „tabliczkę mnożenia”
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 2 | 4 | 6 | 1 | 3 | 5 |
| 3 | 3 | 6 | 2 | 5 | 1 | 4 |
| 4 | 4 | 1 | 5 | 2 | 6 | 3 |
| 5 | 5 | 3 | 1 | 6 | 4 | 2 |
| 6 | 6 | 5 | 4 | 3 | 2 | 1 |
– addytywna grupa liczb całkowitych modulo 6, elementami są liczby od 0 do 5 a działaniem dodawanie modulo 6. Można skonstruować podobną tabelkę do tej z poprzedniego przykładu, najprościej porównać dodawanie w tej grupie do liczenia godzin na zegarku 😊
Dlaczego – zbiór liczb całkowitych z mnożeniem nie jest grupą? Nie ma ani jednej liczby całkowitej, której odwrotność względem mnożenia należy również do liczb całkowitych.
Użyteczne dla nas będą jeszcze następujące pojęcia:
- Rzędem grupy nazywamy moc (inaczej liczbę elementów) zbioru elementów,
- Rzędem elementu nazywamy najmniejszą potęgę, która da element neutralny.
- Generatorem grupy nazywamy element, na którym powtarzając cały czas działanie wygenerujemy wszystkie elementy zbioru grupy – żeby wygenerować całą grupę
potrzebujemy dwie wartości
.
- Podgrupą nazywamy podzbiór zbioru
z działaniem, który też jest grupą.
Teraz wrócimy do obliczeń związanych z protokołem Schnorr’a.
Grupa Schnorr’a
Claus Schnorr zaproponował żeby wszystkie obliczenia dotyczące jego protokołu były przeprowadzane w pewnym wyspecyfikowanym matematycznym świecie, który nazywamy grupą Schnorr’a. Grupa ta jest podgrupą (rzędu dużej liczby pierwszej) multiplikatywnej grupy modulo , gdzie
jest liczbą pierwszą.
Żeby wygenerować taką grupę potrzebujemy liczby takie, że
i
są pierwsze i
. Następnie musimy wylosować
,
takie że . Liczba
z definicji musi być różna od 1 gdyż w przeciwnym wypadku
oraz
byłyby dwiema sąsiadującymi liczbami pierwszymi. Liczba
będzie generatorem naszej grupy a zarazem podstawą wszystkich potęg z protokołu. Teraz odpowiemy sobie dlaczego 😊. Warto wspomnieć, że jeśli
jest liczbą pierwszą to grupa multiplikatywna
jest cykliczna.
Po pierwsze, przy wykonywaniu protokołu wykonujemy bardzo wiele mnożeń i potęgowań (które de facto też jest złożeniem mnożeń) w związku z tym musimy mieć gwarancję, że wykonując te działania pozostaniemy w grupie. Liczba
mówi nam w uproszczeniu o tym jak duże wartości mogą potencjalnie znaleźć się w grupie, podczas gdy liczba
będąc rzędem grupy określa maksymalną liczbę mnożeń, którą potrzebujemy wykonać aby dojść do elementu neutralnego. Dlaczego chcemy wydłużać tą ścieżkę? Żeby obliczenia pozostały w podgrupie dla każdego wykonanego mnożenia nasza podgrupa musi być cykliczna – dłuższy cykl oznacza, większy czas potrzebny na przeszukanie podgrupy wygenerowanej przez generator.
Gdyby byłoby równe 1 oznaczałoby to, że nie nadaje się na generator gdyż podgrupa byłaby zdegenerowana – zawierałaby tylko jeden element, tj. liczbę 1.
Zakończenie
Kończąc podam Wam ostatnie założenia. Liczba powinna być od 1024-3072 bitowa podczas gdy
160-256 bitowe. Założenie to jest konieczne aby zabezpieczyć się przed atakiem na problem dyskretnego logarytmu (czyli próbę odzyskania wykładnika potęgi, co jest dla komputera kłopotliwym zadaniem) oraz atakom bazującym na małej podgrupie.
Planuję przygotować dla Was krótki artykuł na temat ataków na matematyczną stronę protokołów w którym omówię wskazane ataki.Na stronie repozytorium (DODAJ LINK) znajdziecie uproszczoną implementację protokołu Schnorr’a – uproszczenie polega na tym, że używam mniejszych liczb niż zalecane 😉 Możecie jednak zobaczyć, że matematyka, którą Wam przed momentem opisałem faktycznie działa!
Pozdrawiam,
Paweł Jarosz