Dowód bezpieczeństwa

W bezpieczeństwa udowodnienia, możemy mierzyć jakość z atakującego jego korzyść , to znaczy prawdopodobieństwo, że uda mu się łamie właściwości zabezpieczeń (na przykład wytwarzającą fałszerstwa dla podpisów cyfrowych ). W redukcji bezpieczeństwa zaczynamy od atakującego przeciwko własności bezpieczeństwa, mając w ten sposób rzekomą przewagę , i dochodzimy do atakującego przeciwko hipotezie bezpieczeństwa , z wielomianowo słabszą przewagą. To właśnie badanie tego wielomianu jest ważne, ponieważ w systemie wielu użytkowników redukcja może zależeć od liczby użytkowników, przy czym klasyczna metoda ogólna polega na przykład na odgadnięciu, który użytkownik zostanie zaatakowany przez użytkownika. przeciwnika przed zastosowaniem ochrony systemu pojedynczego użytkownika do tego użytkownika docelowego. Daje to rzekomą przewagę ε dla systemu pojedynczego użytkownika , co oznacza, że ​​dla sieci internetowej w 2016 roku występuje utrata bezpieczeństwa rzędu 2⁴¹, co oznacza, że ​​dla multi-security - użytkownika 80- bitowego , potrzebujesz zabezpieczenia pojedynczego użytkownika wynoszącego 121 bitów, co odpowiednio zwiększa rozmiar kluczy (na przykład rozmiar liczb pierwszych wybranych dla podpisu RSA , a tym samym rozmiar podpisu). ε/|użytkowników|{\ displaystyle \ varepsilon / | {\ tekst {użytkowników}} |}

Praca nad lepszym oszacowaniem utraty bezpieczeństwa zwiększa w ten sposób naszą wiedzę na temat bezpieczeństwa systemów kryptograficznych , aw najlepszym przypadku (stała utrata bezpieczeństwa) kryptolodzy twierdzą, że dowody są w porządku .

Dowód w grach

Dowód na grę jest czasami używany, gdy definicja bezpieczeństwa jest podana przez grę kryptograficzną, którą wygrywa przeciwnik . Tak jest na przykład w przypadku semantycznego bezpieczeństwa schematów szyfrujących. Celem jest przejście krok po kroku od pierwotnej gry, którą musi wygrać atakujący, przekształcenie jej krok po kroku w grę, której przeciwnik nie może wygrać, na przykład dlatego, że jest to rozwiązanie trudnego problemu lub dlatego, że już go nie ma. informacje o pierwotnej wiadomości. Przejście z jednego etapu do drugiego może zmienić tylko przewagę i punkt widzenia przeciwnika w znikomym stopniu w porównaniu z poprzednią partią. W taki sposób, że stosując różne transformacje, kończymy grę, której przeciwnik nie jest w stanie wygrać, w znikomym dystansie od koncepcji bezpieczeństwa, którą chcemy zademonstrować.

Zaletą takich dowodów jest to, że są łatwe do zweryfikowania, ponieważ przejścia od jednego kroku do następnego są jasno określone, a zatem argument można zweryfikować krok po kroku. Korzyść przeciwnika w dokładnej ocenie współczynnika przybliżenia redukcji.

W ten sposób możemy przeformułować dowód istnienia kryptosystemu ElGamal za pomocą gier kryptograficznych.

W dalszej części relacja „   ” oznacza, że ​​dwa rozkłady są statystycznie lub obliczeniowo bliskie; a Adv i oznacza przewagę przeciwnika. W przypadku bezpieczeństwa semantycznego chodzi o ilość . ≈{\ displaystyle \ ok}Wrev=|12-Pr[W wygrywa]|{\ Displaystyle Adv = \ lewo | {\ Frac {1} {2}} - \ Pr [{\ mathcal {A}} {\ mbox {wygrywa}}] \ prawo |}

• Gra 0 : Semantyczne bezpieczeństwo diagramu. Konkurent rozpoczyna się od generowania pary kluczy i przekazuje PK = (G, Q, G, H = g ) z napastnikiem. Atakujący następnie odsyła dwie wiadomości m₀ i m₁ . Wyzywający zajmuje trochę następnie σ monety i odnosi się do zaczepu zaszyfrowanej m Ď  : . Następnie przeciwnik zwraca nieco σ ' i wygrywa wtedy i tylko wtedy, gdy σ = σ' .VS=(mσ⋅godzb,solb){\ Displaystyle C = (m _ {\ sigma} \ cdot h ^ {b}, g ^ {b})}
• Gra 1 : Ponieważ wybór σ jest niezależny od poglądu atakującego, zmieniamy tutaj rywala tak, aby wyciągał bit σ przed obejrzeniem wiadomości. Nic się nie zmieniło, Adv₀ = Adv₁ .
• Gra 2 : Korzystając z hipotezy decyzyjnej Diffiego-Hellmana, która mówi, że dla a, b, c narysowanych równomiernie w ℤ q , możemy zastąpić szyfr C przez . W tym miejscu wykorzystano założenie bezpieczeństwa problemu decyzyjnego Diffiego-Hellmana .(sol,solw,solb,solwb)≈(sol,solw,solb,solvs){\ Displaystyle (g, g ^ {a}, g ^ {b}, g ^ {ab}) \ ok (g, g ^ {a}, g ^ {b}, g ^ {c})}(mσ⋅solvs,solb){\ Displaystyle (m _ {\ sigma} \ cdot g ^ {c}, g ^ {b})}|Wrev2-Wrev1| ≤ WrevrereH.{\ displaystyle \ scriptstyle | Adv_ {2} -Adv_ {1} | \ \ leq \ Adv ^ {DDH}}
• Gra 3 Teraz g c jest niezależne od klucza publicznego i dlatego całkowicie ukrywa wiadomość. Bez żadnej innej hipotezy, możemy zauważyć, że o rozkładzie równomiernym w G . Możemy zatem zastąpić C przez , co stanowi całkowicie losowy szyfr niezależny od bitu σ. W tej grze ponownie rozkład liczb w porównaniu z poprzednią grą pozostaje niezmieniony: Adv₃ = Adv₂ .mσ⋅solvs≈solr{\ displaystyle m _ {\ sigma} \ cdot g ^ {c} \ ok g_ {r}}solr{\ displaystyle g_ {r}}(solr,solb){\ Displaystyle (g_ {r}, g ^ {b})}

Wreszcie zauważamy, że w grze 3 żaden przeciwnik nie może wygrać z prawdopodobieństwem innym niż 1/2. Co więcej, jedyną transformacją, która zmienia to prawdopodobieństwo, jest Gra 2, w której używamy argumentu decyzji obliczeniowej Diffiego-Hellmana. Oznacza to, że w sumie przewaga przeciwnika w tym schemacie jest ograniczona przewagą przeciwnika przeciwko DDH; w rzeczy samej

Wrev0=|Wrev3-Wrev0|=|Wrev3-Wrev2+Wrev2-Wrev1+Wrev1-Wrev0|≤|Wrev3-Wrev2|+|Wrev2-Wrev1|+|Wrev1-Wrev0|=0+WrevrereH.+0=WrevrereH.{\ Displaystyle {\ rozpocząć {wyrównane} Adv_ {0} & = | Adv_ {3} -Adv_ {0} | \\ & = | Adv_ {3} -Adv_ {2} + Adv_ {2} -Adv_ {1} + Adv_ {1} -Adv_ {0} | \\ & \ leq | Adv_ {3} -Adv_ {2} | + | Adv_ {2} -Adv_ {1} | + | Adv_ {1} -Adv_ {0} | \\ & = 0 + Adv ^ {DDH} + 0 = Adv ^ {DDH} \ end {aligned}}}

Teoria złożoności

Ale co powinniśmy nazwać trudnym  ? Odpowiedzi na to pytanie daje teoria złożoności, z której zapożyczamy między innymi koncepcję redukcji między problemami. Teoria ta stara się sklasyfikować problemy według czasu obliczeniowego niezbędnego do ich rozwiązania i określa klasy „trudności”. W tym przypadku klasą, która nas interesuje, jest tzw. Wielomian niedeterministyczny (NP). Są to problemy, dla których dane rozwiązanie jest „łatwe” do zweryfikowania (sprawdza się w czasie wielomianowym ), ale istnieje ryzyko, że będzie trudne (potencjalnie w czasie nie wielomianowym) do znalezienia .

Przynależność do problemu w klasie NP nie oznacza , że nie da się go rozwiązać w czasie wielomianowym. Rzeczywiście, wszystkie problemy P są w NP, a fakt wiedzy, czy przeciwnie, istnieją problemy NP, które nie są w P, zwane Problemem P = NP, jest jednym z dużych otwartych pytań w matematyce.

W kryptografii teoretycznej bada się inne klasy złożoności, aby określić, co jest uważane za trudne, a co nie, takie jak AC⁰ lub NC¹, aby wiedzieć, co pozostanie w przypadku załamania się hierarchii wielomianów , wiemy na przykład, że jeśli istnieją funkcje , wtedy P ≠ NP , które w przypadku załamania unieważnią część kryptografii opartej na tej hipotezie roboczej.

W praktyce

Wszystkie problemy używane przez kryptografię są w NP: „łatwo” jest zakodować wiadomość lub odszyfrować wiadomość, gdy masz klucz. Z drugiej strony, przy obecnym stanie wiedzy , wszystkie istniejące metody łamania tych kodów mają wykładniczy rozmiar klucza. To właśnie praktyczna dysproporcja między czasem kodowania lub dekodowania kluczem z jednej strony a złamaniem z drugiej strony sprawia, że ​​metody te są użyteczne.

Obecnie nie ma żadnych teoretycznych zastrzeżeń co do istnienia obecnie używanych algorytmów łamania kodu wielomianowego, a jedynie praktyczna obserwacja, że ​​problemy te opierały się nieustannym wysiłkom społeczności przez wystarczająco długi czas. Powinniśmy również zauważyć, że komputery kwantowe, jeśli uda nam się zbudować je o wystarczającej "wielkości" (liczbie qbitów), umożliwiłyby złamanie systemów takich jak RSA za pomocą algorytmu Shora .

Na koniec należy zauważyć, że dowody bezpieczeństwa należy traktować z ostrożnością. Na przykład system, który zawdzięczamy Ajtai i Dwork, wraz z teoretycznym dowodem bezpieczeństwa zakładającym jakiś trudny problem, został w praktyce uznany za uszkodzony przez Phonga Nguyena i Jacquesa Sterna .

Uwagi i odniesienia

1. Bellare, Micciancio i Warinschi 2003 .
2. Chaum i van Heyst 1991 .
3. Shannon 1949 .
4. Patrick Guignot, „  Keccak wygrywa przetarg i staje się SHA-3  ” , na Linuxfr
5. Pełny dowód jest dostępny w artykule ElGamal .
6. Galbraith, Malone-Lee i Smart 2002 .
7. liczba użytkowników Internetu na świecie w Journal du Net
8. Chatterjee, Menezes i Sarkar 2012 .
9. Shoup 2006 .
10. Degwekar, Vaikuntanathan i Vasudevan 2016 .
11. Koblitz i Menezes 2004 .
12. Nguyen i Stern 1998 .

Załączniki

Bibliografia

• [Bellare, Micciancio and Warinschi 2003] (en) Mihir Bellare, Daniele Micciancio i Bogdan Warinschi, „  Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions  ” , Eurocrypt ,2003, s.  614-629 ( DOI  10.1007 / 3-540-39200-9_38 )
• [Chatterjee, Menezes i Sarkar 2012] Sanjit Chatterjee, Alfred Menezes i Palash Sarkar, „  Another Look at Tightness  ”, Selected Area in Cryptography (SAC) ,2012( DOI  10.1007 / 978-3-642-28496-0_18 , czytaj online )
• [Chaum and van Heyst 1991] (en) David Chaum i Eugène van Heyst, »  Group Signatures  « , Eurocrypt ,1991, s.  257–265 ( DOI  10.1007 / 3-540-46416-6_22 )
• [Degwekar, Vaikuntanathan i Vasudevan 2016] Akshay Degwekar, Vinod Vaikuntanathan i Prashant Nalini Vasudevan, „  Fine-grained Cryptography  ”, Crypto ,2016( DOI  10.1007 / 978-3-662-53015-3_19 , czytaj online )
• [Galbraith, Malone-Lee i Smart 2002] Steven Galbraith, James Malone-Lee i Nigel P. Smart, „  Public key signatures in the multi-user setting  ”, Information Processing Letters ,2002( DOI  10.1016 / S0020-0190 (01) 00338-6 )
• [Koblitz and Menezes 2004] (en) Neal Koblitz i Alfred Menezes, „  Another Look at„ Provable Security ”  ” , raporty iacr ePrint ,2004( czytaj online )
• [Lamport 1979] (en) Leslie Lamport , „  Constructing digital signatures from a one-way function  ” , Technical Report CSL-98 ,1979( czytaj online )
• [Nguyen and Stern 1998] (en) Phong Nguyen i Jacques Stern, »  Cryptanalysis of the Ajtai-Dwork cryptosystem  « , Crypto ,1998( DOI  10.1007 / BFb0055731 )
• [Shannon 1949] (en) Claude Shannon, „  Komunikacyjna teoria systemów tajnych  ” , Bell System Technical Journal ,1949( czytaj online )
• [Shoup 2006] (en) Victor Shoup, „  Sekwencje gier: narzędzie do oswajania złożoności dowodów bezpieczeństwa  ” , raport iacr ePrint ,2006( czytaj online )

Powiązane artykuły

• Kryptanaliza
• Argument hybrydowy