Przejdź do treści
Wróć do wyników wyszukiwania

Kryptanaliza różnicowa

Autor metody
Eli Biham
Rok
1990
Typ
statistical attack on block ciphers
Rodzina
Cryptanalytic technique

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Kryptanaliza różnicowa to technika statystycznego ataku na symetryczne szyfry blokowe, która analizuje różnice w danych wejściowych i wyjściowych w celu odzyskania tajnych kluczy.

Wprowadzona przez Eli Bihama i Adi Shamira w 1990 roku, kryptanaliza różnicowa była pierwszym praktycznym atakiem na DES, który przewyższał siłowe przeszukiwanie. Technika ta wykorzystuje nielosowe właściwości transformacji szyfru, badając, jak małe zmiany w tekście jawnym propagują się przez rundy szyfrowania. Kryptanaliza różnicowa kształtuje projektowanie szyfrów od trzech dekad.

Intuicja stojąca za metodą

Kryptanaliza różnicowa działa poprzez badanie par tekstów jawnych o określonych różnicach i obserwowanie, jak te różnice ewoluują przez rundy szyfrowania. Jeśli pewne różnice mają większe prawdopodobieństwo propagacji w określony sposób, tę nielosowość można wykorzystać do odzyskania bitów klucza. Atakujący wybiera pary tekstów jawnych zaprojektowane tak, aby zmaksymalizować prawdopodobieństwo użytecznych różnic wyjściowych, a następnie wykorzystuje obserwowane różnice wyjściowe do zawężenia możliwych kluczy.

Historia

Kryptanaliza różnicowa została wprowadzona w 1990 roku przez Bihama i Shamira, ujawniając praktyczne ataki na DES wymagające 2^47 operacji i 2^47 par tekst jawny-szyfrogram. Atak wykazał, że DES był słabszy niż oczekiwano i pobudził przyjęcie bardziej rygorystycznych kryteriów projektowych. AES i inne nowoczesne szyfry zostały celowo zaprojektowane z myślą o odporności różnicowej, znacząco podnosząc poprzeczkę dla tej klasy ataków.

Kiedy stosować

Kryptanaliza różnicowa jest wykorzystywana w badaniach kryptanalizy do oceny siły szyfru. Projektanci szyfrów używają analizy różnicowej do weryfikacji odporności na ataki różnicowe. Nowoczesne szyfry zawierają rundy i transformacje specjalnie zaprojektowane, aby oprzeć się kryptanalizie różnicowej.

Ograniczenia i uwagi

  • Wymaga dużych ilości znanych par tekst jawny-szyfrogram, często niepraktyczne
  • Nowoczesne szyfry (AES) są starannie zaprojektowane, aby oprzeć się kryptanalizie różnicowej
  • Koszt obliczeniowy przeprowadzania ataków może być zaporowo wysoki
  • Skuteczność zależy od odkrycia silnych charakterystyk różnicowych, co staje się trudniejsze dla dłuższych liczb rund

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Praktyczny atak na niektóre szyfry, wymagający mniej niż 2^64 operacji (przewyższający siłowe przeszukiwanie dla kluczy 64-bitowych)
  • Dobrze zrozumiana podstawa matematyczna umożliwiająca rygorystyczną analizę bezpieczeństwa szyfru
  • Ukierunkowane projektowanie szyfrów; odporność na kryptanalizę różnicową jest standardowym celem projektowym
  • Ujawnia słabości strukturalne w projekcie szyfru, które inne techniki mogą przeoczyć

Zastosowania

  • Kryptanaliza szyfrów blokowych w badaniach kryptograficznych i publikacjach naukowych
  • Projektowanie i ocena szyfrów, zapewniająca odpowiednią liczbę rund i transformacji przeciwko atakom różnicowym
  • Walidacja kryptograficzna w organach standaryzacyjnych (NIST, ETSI) wymagająca analizy odporności
  • Ocena bezpieczeństwa starszych szyfrów identyfikująca słabości i informująca o decyzjach o wycofaniu

Jak to działa

Jak to działa

1

Identyfikacja charakterystyk różnicowych: sekwencji różnic przez rundy szyfrowania z wysokim prawdopodobieństwem wystąpienia dla dowolnego klucza.

2

Oszacowanie liczby par tekstów jawnych wymaganych do odróżnienia szyfru od losowego i odzyskania bitów klucza.

3

Wykorzystanie par tekst jawny-szyfrogram wykazujących pożądaną różnicę do testowania kandydackich wartości klucza, eliminując klucze niespójne z obserwacjami.

4

Analiza kosztu obliczeniowego i wymaganego wolumenu danych. Praktyczne ataki równoważą te czynniki z siłowym przeszukiwaniem klucza.

Częste pułapki

  • Niedoszacowanie trudności w znalezieniu charakterystyk dla nowoczesnych szyfrów
  • Przeszacowanie praktycznej wykonalności ataku, gdy teoretyczne wymagania dotyczące danych są niepraktycznie duże
  • Zakładanie, że bezpieczeństwo wymaga jedynie odporności na kryptanalizę różnicową; należy uwzględnić wiele wektorów ataku

Najczęściej zadawane pytania

Czym jest charakterystyka różnicowa?

Charakterystyka różnicowa to sekwencja różnic wejściowych i wyjściowych w każdej rundzie szyfrowania z określonym prawdopodobieństwem. Znalezienie charakterystyk o wysokim prawdopodobieństwie jest kluczem do przeprowadzenia skutecznych ataków różnicowych.

Jak AES opiera się kryptanalizie różnicowej?

AES wykorzystuje transformacje (podstawienie i mieszanie), które zapewniają, że każda jednolite różnica wejściowa propaguje się do co najmniej 25 bitów wyjściowych już po trzech rundach. Ta szybka dyfuzja sprawia, że ataki różnicowe są niewykonalne.

Czy kryptanaliza różnicowa może złamać nowoczesne szyfry?

Nie praktycznie. Nowoczesne szyfry, takie jak AES, wymagają zaporowo dużych ilości tekstu jawnego i zasobów obliczeniowych znacznie przekraczających siłowe przeszukiwanie klucza.

Czy kryptanaliza różnicowa jest tym samym co kryptanaliza liniowa?

Nie. Analiza różnicowa bada różnice wejścia-wyjścia, podczas gdy analiza liniowa bada aproksymacje liniowe. Obie są ważnymi klasami ataków; szyfry muszą być odporne na obie.

Jak ocenić odporność szyfru na ataki różnicowe?

Analizuj tablice S i transformacje rund szyfru pod kątem maksymalnego prawdopodobieństwa różnicowego. Użyj narzędzi automatycznych i analizy ręcznej do znalezienia charakterystyk. Publikuj wyniki w recenzowanych czasopismach w celu przeglądu przez społeczność.

Pokrewne metody

Źródła

  1. Biham, E., & Shamir, A. (1990). Differential cryptanalysis of DES-like cryptosystems. In Advances in Cryptology - CRYPTO 1990, LNCS 537, pp. 2-21.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Knudsen, L. R. (2005). Block ciphers and public key cryptosystems. In Information Security and Cryptography, pp. 1-25.

    Otwórz odnośnik do publikacji
    Skopiowano.