Algorytm klucza publicznego HFE Enigma 2000, Warszawa

Algorytm klucza publicznego HFE

slajdy i dodatkowe materiały: http://www.univ-tln.fr/∼courtois/myresearch.html

Nicolas Tadeusz Courtois

Uniwersytet Paryż 6 i Uniwersytet w Toulon. courtois@univ-tln.fr

IV Krajowa Konferencja Zastosowań Kryptografii, Enigma 2000 Warszawa, 22-25 maja 2000.

Plan

1. Podstawy matematyczne

2. Algorytm ‘basic HFE’ i szczegóły implementacji

3. Kryptologiczne wyzwania na HFE (2× 500$)

4. Najlepsze znane ataki na ‘HFE Challenge 1’:

⋄ [Shamir-Kipnis 1999], 2^{152}.

⋄ [Courtois 1999], 2^{62}.

5. Najkrótsze na świecie podpisy cyfrowe (≤ 80 bitów !).

Nicolas Tadeusz Courtois 2

O kryptografii wielu zmiennych i HFE.

RSA opiera siȩ na jednym równaniu modularnym z jedna̧ zmienna̧. Naturalnym uogólnieniem tego podejścia jest rozważanie systemów wielu

równań z wieloma zmiennymi (...)

Uważa siȩ że HFE jednym z najsilniejszych kryptosystemów tego typu (...)

Adi Shamir

Wszyscy matematycy wiedza̧ że przejście z jednej do wielu zmiennych to nagły ‘skok’ któremu towarzysza̧ wielkie trudności (...)

Jean Dieudonné

Ciała skończone i ich rozszerzenia

K - ciało skończone, K = IF_{q}, q (niekoniecznie) pierwsza ∃ jedyne ciało skończone IF_{q^{n}}, konstrukcja: IF_{q^{n}} = K[X]/P (X) gdzie P jest wielomianem nierozkładalnym stopnia n nad K.

Reprezentacje jednej/wielu-zmiennych

Każdy element x ∈ IF_{q^{n}} można zakodować jako n wspólczynników wielomianu x ∈ K[X] wziȩtego modulo P (X). Jeżeli x = x_{1} + x_{2} · X + … + x_{n} · X^{n−1}, piszemy w skrócie x = (x_{1}, …, x_{n}). IF_{q^{n}} - przestrzeń wektorowa, wymiar n nad K, K^{n} ≡ IF_{q^{n}}.

Nicolas Tadeusz Courtois 4

Reprezentacje jedno/wielo-zmienne funkcji

Każda̧ funkcjȩ f : K^{n} → K^{n} można napisać jako: ⋄ wielomian jednej zmiennej x ∈ IF_{q^{n}} ≡ K^{n} ⋄ n wielomianów n zmiennych f_{1}(x_{1}, …, x_{n}), …, f_{n}(x_{1}, …, x_{n}).

Stopień w reprezentacji jednej/wielu zmiennych.

⋄ Funkcja o postaci b = f(a) = a^{q^{s}} daje w reprezentacji wielu zmiennych: b_{i} = f_{i}(a_{1}, …, a_{n}), gdzie f_{i} sa̧ K-liniowe. ⋄ Jeżeli f(a) = a^{q^{s}+q^{t}}, funkcje f_{i} sa̧ drugiego stopnia nad K. ⋄ Funkcja jest postaci f(a) = ∑_{i} λ_{i}a^{q^{si} +q^{ti}}, λ_{i} ∈ IF_{q^{n}}, wtedy i tylko wtedy jeżeli wszystkie f_{i} sa̧ drugiego stopnia nad K.

Algorytm klucza publicznego HFE Enigma 2000, Warszawa

Przykład.

K = IF_{2} = {0, 1}, n = 3, P (X) = X^{3} + X^{2} + 1, K^{n} = IF_{2^{3}} = K[X]/X^{3} + X^{2} + 1 b = f(a) = a + a^{3} + a^{5} = (a_{2}X^{2} + a_{1}X + a_{0}) + (a_{2}X^{2} + a_{1}X + a_{0})^{3}+ (a_{2}X^{2} + a_{1}X + a_{0})^{5} mod X^{3} + X^{2} + 1 = (...) = (a_{2}+a_{2}a_{1}+a_{2}a_{0}+a_{1})X^{2}+(a_{2}a_{1}+a_{1}a_{0}+a_{2})X+(a_{0}+a_{2}+a_{1}a_{0}+a_{2}a_{0})

\{ \begin{matrix}b_{2} & = & a_{2} + a_{2}a_{1} + a_{2}a_{0} + a_{1} \\ b_{1} & = & a_{2}a_{1} + a_{1}a_{0} + a_{2} \\ b_{0} & = & a_{0} + a_{2} + a_{1}a_{0} + a_{2}a_{0} \end{matrix}

Nicolas Tadeusz Courtois 6

Hidden Field Equation (HFE).

f(a) = ∑_{q^{s}+q^{t}≤d} γ_{st} a^{q^{s}+q^{t}}

• Napisać jako n funkcji drugiego stopnia n zmiennych: b_{1} = f_{1}(a_{1}, …, a_{n}), …, b_{n} = f_{n}(a_{1}, …, a_{n}).

• Zakamuflować strukturȩ algebraiczna̧ funkcji f : a ↦ b za pomoca̧ dwóch podstawień linowych (lub afinicznych) S i T, na przykład:

S : { a_{1} = x_{2} − x_{3} + 1 ; ⋮ T : { y_{1} = b_{1} + b_{2} − 1 ; ⋮

Niech g : x ↦ y, bȩdzie wynikiem podstawień, g = T ∘ f ∘ S.

Używanie ‘basic’ HFE

� �  � �_{klucz publiczny:} n równań drugiego stopnia

g : { y_{i} = g_{i}(x_{1}, …, x_{n}) }_{i=1..n} � � � �_{klucz prywatny:} Znajomość T, S i f. f jest funkcja̧ jednej zmiennej stopnia ≤ d. Fakt: można obliczyć f^{−1} (metody jednej zmiennej). ∃ wiele algorytmów, zaczynaja̧c od [Berlekamp 1967]. Sa̧ one dość wolne. Przykład: n=128, d=25, 0.17s na PIII-500.

Obliczanie g^{−1} z użyciem klucza prywatnego.

x ⟵^{S^{−1}} a ⟵^{f^{−1}} b ⟵^{T^{−1}} y

Nicolas Tadeusz Courtois 8

O trudności obliczenia g^{−1} bez klucza prywatnego.

Otrzymaliśmy funkcjȩ g : x ↦ y, bȩda̧c a złożeniem g = T ∘ f ∘ S. Dla osoby nie znaja̧cej klucza prywatnego: g ‘wygla̧da’ jak dowolny (losowy) układ równań drugiego stopnia.

Problem MQ (Multivariate Quadratic): rozwia̧zać układ n równań drugiego stopnia z n zmiennymi: ⋄ problem NP-zupełny. ⋄ Na małym ciele skończonym najlepszy znany algorytm nie jest szybszy niż ślepe przeszukiwanie (brute force attack). Patrz: N. Courtois, A. Shamir, J. Patarin, A. Klimov: “Efficient Algorithms for solving Overdefined Systems of Multivariate Polynomial Equations”, Eurocrypt’2000.

Zalecane implementacje HFE

Patrz http://www.univ-tln.fr/∼courtois/hfe.html ⋄ K = IF_{2} (operacje na bitach) ⋄ n ≥ 127, najlepiej liczba pierwsza ⋄ d ≥ 25, najlepiej w postaci 2^{k} + 1

Kryptologiczne wyzwania - 2*500 $

� �  � �_{Challenge 1} : K = IF_{2}, n = 80, d = 96.

Najlepszy znany atak [Courtois 99] - 2^{62}. � � � �_{Challenge 2:}K = IF_{16}, n = 36, d = 4352, tylko 32 na 36 równań sa̧ podane. Brak znanych ataków.

Atak HFE w/g Shamir-Kipnis [crypto 99].

Shamir i Kipnis sprowadzaja̧ złamanie HFE do problemu macierzowego MinRank(r), (NB. r = log d)

� �  � �_{MinRank(r):}Znaleźc (szczególna̧) kombinacjȩ liniowa̧ danych

maciarzy n × n, której rza̧d spada do r.

Potem okazało siȩ że:

⋄ MinRank jest NP-zupełny i b. trudny w praktyce ⋄ zawiera on w sobie wiele słynnych trudnych problemów ⋄ to chyba najtrudniejszy znany problem w kryptografii !

Fiasco ataku Shamir-Kipnis.

♣ Proponowana kontunuacja ataku (metoda re-linearyzacji) okazała siȩ niewypałem. Ulepszona relinearyzacja ⇝ algorytm XL [Courtois,Patarin,Shamir - Eurocrypt’2000].

Wtedy atak Shamir-Kipnis dla ‘HFE Challenge 1’ wymaga 2^{152} obliczeń,... >> 2^{80} (ślepe przeszukiwanie).

♣ Ulepszona wersja ataku Shamir-Kipnis wyraża MinRank za pomoca̧ podmacierzy [Courtois 1999].

Daje 2^{82} dla ‘HFE Challenge 1’.

Złożoność obliczeniowa ataku Shamir-Kipnis-Courtois:

Około n^{3 log d}.

Nicolas Tadeusz Courtois 12

Algorytm klucza publicznego HFE Enigma 2000, Warszawa

MinRank dowodzi solidności HFE ? Niezupełnie...

Złamać  ≠  ^{odzyskać klucz prywatny}

Historia kryptanalizy róznych kryptosystemów:

1. W niektórych przypadkach odzyskano S i T:

• D^{∗} [Courtois 97].

• ‘Balanced Oil and Vinegar’ [Kipnis, Shamir Crypto’98]

2. Wiele zostało złamanych bez odzyskania klucza prywatnego: • 2 propozycje Shamir’a. [Stern, Vaudenay, Coppersmith]

• 2 schematy Matsumoto-Imai: C^{∗}; [C] = HM [Patarin]

• D^{∗}, Little Dragon, S-boxes, C^{∗−} [Patarin, Goubin, Courtois]

Ataki bezpośrednie [Patarin Courtois].

Bardzo techniczne, używaja̧ fakt istnienia równań wia̧ża̧cych ze soba̧ bity wejścia i wyjścia o bardzo złożonej strukturze, na przykład dla Challenge 1:

Fakt eksperymentalny: Dla HFE stopnia d ≤ 128 istnieje ≥ n

równań typu: Σαi + Σβixi + Σγiyi + Σδij xixj + Σεijkxixj yk + Σζijkyiyj xk + Σθijkxixj yk + Σκijklxixj xkyl + Σλijklxixj ykyl = 0.

W praktyce - Challenge 1:

Powyzsze równania maja̧ 17 milionów wspólczynników. Metoda klasyczna (redukcja systemów liniowych) aby je odzyskać wymaga 33 Tera-bajtów pamiȩci RAM.

Atak ulepszony [Courtois 99] - czas 2^{62}, tylko 390 Go na dysku.

Algorytm klucza publicznego HFE Enigma 2000, Warszawa

Problem podpisu cyfrowego.

f - funkcja z zapadka̧ ‘(trapdoor function’), n bitów. Metoda klasyczna: � � � �_{σ = f^{−1}( H(m) )} H- funkcja mieszaja̧ca Existential Forgery: Atak paradoksu dnia urodzin:

1. Wygenerować 2^{n/2} wersji wiadomości do podpisania m_{1}, …, m_{2^{n/2}}, dodaja̧c spacje, przecinki, tekst itp...

2. Wygenerować listȩ 2^{n/2} wartości f(σ_{j}), dla losowych σ_{j}.

3. Posortować obie listy, istnieja̧ (i, j) takie że:

f(σ_{j}) = H(m_{i})

Nicolas Tadeusz Courtois 15 Algorytm klucza publicznego HFE Enigma 2000, Warszawa

Złamać podpis cyfrowy o długości 80 bitów ⇝ ok. 2^{40} obliczeń.

Ominiȩcie ataku [Patarin]

Metoda ulepszona z użyciem dwóch funkcji mieszaja̧cych H_{1},H_{2}:

� �  � �_{σ = f^{−1} ( H_{1}(m) + f^{−1} [H_{2}(m) + f^{−1}(H_{1}(m))] )}

Daje bezpieczne podpisy o długości 80 a nawet 64 bitów ! Porównanie długości typowych podpisów :

RSA ⇝ 1024 bitów
Krzywe Eliptyczne ⇝ 220 bitów
HFE + powyższa metoda ⇝ 80 bitów  (najkrótsze znane)

Nicolas Tadeusz Courtois 16

Jakie podpisy sa̧ bezpieczne ?

Pytania pułapki: Który najlepszy ?

Zalecamy pluralizm i kumulacje certyfikatów.

Scenarjusz pro-aktywny pozwala stopniowo wycofywać stare i wprowadzać nowe. Na przyklad w dniu kiedy RSA 768 zostanie złamany wygasłaby ważność podpisów RSA 1024. Przyładowy certyfikat RSA + ECC + HFE = 1024 + 256 + 128 bitów. RSA jest na tyle wolny i podpisy sa̧ na tyle długie że koszt całej reszty jest do pominiȩcia.

Stan wiedzy AD 2000, HFE vs. RSA.

⋄ Znane ataki na ‘basic’ HFE’ staja̧ siȩ nierealne dla dobrze wybranych parametrów n i d.

⋄ Najlepsze ataki w teorii: \begin{matrix}HFE & e^{log^{2}n} \\ RSA & e^{n^{\frac{1}{3}}} \end{matrix}

⋄ HFE może być o wiele szybszy i praktyczniejszy od RSA.

⋄ Łatwo jest zmodyfikować podstawowa̧ wersjȩ ‘basic’ HFE aby otrzymać kryptosystem nie maja̧cy żadnej znanej słabości, nawet teoretycznej:

HFE^{−} [Patarin, Asiacrypt’98], vHFE: [Patarin, Eurocrypt’99].

Kto za, kto przeciw...

“Jakikolwiek algorytm, który opiera swoje bezpieczeństwo na rozkładzie wielomianów na ciele skończonym, powinien być

rozważany co najmniej ze sceptycyzmem, jeżeli nie z podejrzeniem.”

[Bruce Schneier, Applied cryptography, p.318]

“...ska̧pość matematycznych fundacji kryptografii klucza publicznego jest bardzo niepokoja̧ca.” [p. 319]

Komu przeszkadzaja̧ monopole: ?SA

HFE: prawdziwa alternatywa Nicolas Tadeusz Courtois 19