Atak XSL - XSL attack

W kryptografii The eXtended Rzadki linearyzacji (XSL) atak jest sposób kryptoanalizy do szyfrów blokowych . Atak został po raz pierwszy opublikowany w 2002 roku przez badaczy Nicolasa Courtoisa i Josefa Pieprzyka . Wywołało to pewne kontrowersje, ponieważ twierdzono, że może złamać szyfr AES ( Advanced Encryption Standard ) , znany również jako Rijndael , szybciej niż wyczerpujące wyszukiwanie . Ponieważ AES jest już szeroko stosowany w handlu i administracji do przesyłania tajnych informacji, znalezienie techniki, która może skrócić czas potrzebny do odzyskania tajnej wiadomości bez posiadania klucza, może mieć szerokie konsekwencje.

Metoda ma wysoki współczynnik pracy, który, o ile nie zostanie zmniejszony, oznacza, że ​​technika nie zmniejsza wysiłku związanego z przerwaniem AES w porównaniu z wyczerpującym wyszukiwaniem. W związku z tym nie wpływa na bezpieczeństwo szyfrów blokowych w świecie rzeczywistym w najbliższej przyszłości. Niemniej jednak atak spowodował, że niektórzy eksperci wyrazili większy niepokój z powodu algebraicznej prostoty obecnego AES.sub to Flaming Destruction

Podsumowując, atak XSL polega najpierw na przeanalizowaniu elementów wewnętrznych szyfru i wyprowadzeniu systemu równoczesnych równań kwadratowych . Te układy równań są zazwyczaj bardzo duże, na przykład 8 000 równań z 1600 zmiennymi dla 128-bitowego AES. Znanych jest kilka metod rozwiązywania takich układów. W ataku XSL do rozwiązania tych równań i odzyskania klucza stosowany jest następnie wyspecjalizowany algorytm zwany rozszerzoną rzadką linearyzacją .

Atak wyróżnia się tym, że do wykonania wymaga tylko kilku znanych tekstów oskarżenia ; wcześniejsze metody kryptoanalizy, takie jak kryptoanaliza liniowa i różnicowa , często wymagają nierealistycznie dużej liczby znanych lub wybranych tekstów jawnych .

Rozwiązywanie wielowymiarowych równań kwadratowych

Rozwiązywanie wielowymiarowych równań kwadratowych (MQ) na skończonym zbiorze liczb jest NP-trudnym problemem (w ogólnym przypadku) z kilkoma zastosowaniami w kryptografii. Atak XSL wymaga wydajnego algorytmu do zwalczania MQ. W 1999 roku Kipnis i Shamir wykazali, że szczególny algorytm klucza publicznego , znany jako schemat równań ukrytego pola (HFE), można zredukować do nadmiernie określonego układu równań kwadratowych (więcej równań niż niewiadomych). Jedną z technik rozwiązywania takich układów jest linearyzacja , która polega na zastąpieniu każdego członu kwadratowego zmienną niezależną i rozwiązaniu wynikowego układu liniowego za pomocą algorytmu, takiego jak eliminacja Gaussa . Aby odnieść sukces, linearyzacja wymaga wystarczającej liczby liniowo niezależnych równań (w przybliżeniu równej liczbie składników). Jednak w przypadku kryptoanalizy HFE było zbyt mało równań, więc Kipnis i Shamir zaproponowali ponowne linearyzację , technikę, w której po linearyzacji dodaje się dodatkowe równania nieliniowe, a wynikowy układ rozwiązuje się przez drugie zastosowanie linearyzacji. Ponowna linearyzacja okazała się na tyle ogólna, że ​​można ją było zastosować w innych schematach.

W 2000 roku Courtois i wsp. zaproponowali ulepszony algorytm MQ znany jako XL (dla eXtended Linearization ), który zwiększa liczbę równań poprzez pomnożenie ich przez wszystkie jednomiany określonego stopnia . Szacunki złożoności wykazały, że atak XL nie zadziała przeciwko równaniom wyprowadzonym z szyfrów blokowych, takich jak AES. Jednak utworzone układy równań miały specjalną strukturę, a algorytm XSL został opracowany jako udoskonalenie XL, które mogło wykorzystać tę strukturę. W XSL równania mnoży się tylko przez starannie dobrane jednomiany i zaproponowano kilka wariantów.

Badania nad wydajnością XL i jego pochodnych algorytmów wciąż trwają (Yang i Chen, 2004).

Aplikacja do szyfrów blokowych

Courtois i Pieprzyk (2002) zauważyli, że AES (Rijndael), a częściowo także Serpent, można wyrazić jako układ równań kwadratowych. Zmienne reprezentują nie tylko tekst jawny , tekst zaszyfrowany i bity klucza, ale także różne wartości pośrednie w algorytmie. Wydaje się, że S-box AES jest szczególnie podatny na tego typu analizę, ponieważ opiera się na algebraicznie prostej funkcji odwrotnej . Następnie zbadano inne szyfry, aby zobaczyć, jakie układy równań można utworzyć ( Biryukov i De Cannière, 2003), w tym Camellia , KHAZAD , MISTY1 i KASUMI . W przeciwieństwie do innych form kryptoanalizy, takich jak kryptoanaliza różnicowa i liniowa , wymagany jest tylko jeden lub dwa znane teksty jawne .

Algorytm XSL jest dostosowany do rozwiązywania typów tworzonych układów równań. Courtois i Pieprzyk szacują, że „optymistyczna ocena pokazuje, że atak XSL może być w stanie złamać Rijndael [z] 256 bitami i Serpent dla długości klucza [z] 192 i 256 bitów”. Ich analiza nie jest jednak powszechnie akceptowana. Na przykład:

Uważam, że dzieło Courtoisa – Pieprzyka jest wadliwe. Przekraczają liczbę liniowo niezależnych równań. Rezultat jest taki, że w rzeczywistości nie mają one wystarczającej liczby równań liniowych do rozwiązania układu, a metoda nie łamie Rijndaela… Metoda ma pewne zalety i jest warta zbadania, ale nie łamie Rijndaela w obecnej postaci.

Na konferencji AES 4, Bonn 2004, jeden z wynalazców Rijndaela, Vincent Rijmen , skomentował: „Atak XSL nie jest atakiem. To sen”. Courtois szybko odpowiedział: „XSL może być snem. Może też być bardzo złym snem i zamienić się w koszmar”. Jednak żaden późniejszy dokument ani żadne działania NSA lub NIST nie dają żadnego poparcia dla tej uwagi Courtois.

W 2003 roku Murphy i Robshaw odkryli alternatywny opis AES, osadzając go w większym szyfrze zwanym „BES”, który można opisać za pomocą bardzo prostych operacji na pojedynczym polu , GF (2 8 ). Atak XSL zamontowany w tym systemie daje prostszy zestaw równań, który złamałby AES ze złożonością około 2100 , jeśli analiza Courtois i Pieprzyk jest poprawna. W 2005 roku Cid i Leurent wykazali, że w proponowanej formie algorytm XSL nie zapewnia wydajnej metody rozwiązywania układu równań AES; jednakże Courtois zakwestionował ich ustalenia. Na FSE 2007 Chu-Wee Lim i Khoongming Khoo pokazali, że nie może działać tak, jak zostało to przedstawione.

Nawet jeśli XSL działa przeciwko niektórym nowoczesnym algorytmom, atak stanowi obecnie niewielkie zagrożenie pod względem praktycznego bezpieczeństwa. Podobnie jak w przypadku wielu współczesnych wyników kryptoanalitycznych, byłaby to tak zwana „słabość certyfikacyjna”: chociaż jest szybsza niż atak brutalnej siły , wymagane zasoby są nadal ogromne i jest bardzo mało prawdopodobne, aby systemy w świecie rzeczywistym mogły zostać naruszone przy jej użyciu. Jednak przyszłe ulepszenia mogą zwiększyć praktyczność ataku. Ponieważ ten typ ataku jest nowy i nieoczekiwany, niektórzy kryptografowie wyrazili niepokój z powodu algebraicznej prostoty szyfrów, takich jak Rijndael. Bruce Schneier i Niels Ferguson piszą: „Mamy jedną krytykę AES: nie do końca ufamy bezpieczeństwu… Najbardziej niepokoi nas w AES jego prosta struktura algebraiczna… Żaden inny szyfr blokowy, o którym wiemy, nie ma tak prostej reprezentacji algebraicznej . Nie mamy pojęcia, czy prowadzi to do ataku, czy nie, ale brak wiedzy jest wystarczającym powodem, aby być sceptycznym co do korzystania z AES ”. ( Practical Cryptography , 2003, s. 56–57)

Bibliografia

Linki zewnętrzne