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

Kryptanaliza liniowa

Autor metody
Mitsuru Matsui
Rok
1993
Typ
linear approximation attack
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 liniowa to atak ze znanym tekstem jawnym, który wykorzystuje liniowe aproksymacje nieliniowych transformacji szyfru do odzyskania bitów tajnego klucza.

Wprowadzona przez Mitsuru Matsui w 1993 roku, kryptanaliza liniowa umożliwia praktyczne ataki na szyfry takie jak DES z złożonością obliczeniową mniejszą niż atak siłowy. Technika ta analizuje statystyczne odchylenia w sposobie, w jaki liniowe kombinacje bitów tekstu jawnego i szyfrogramu odnoszą się do bitów klucza, umożliwiając odzyskanie klucza przy zmniejszonych wymaganiach dotyczących danych.

Intuicja stojąca za metodą

Kryptanaliza liniowa znajduje równania liniowe łączące bity tekstu jawnego, bity szyfrogramu i bity klucza. Ze względu na niedoskonałe mieszanie w rundach szyfru, te równania liniowe są spełnione z prawdopodobieństwem nieco lepszym niż losowe. Gromadząc wiele par tekst jawny-szyfrogram i obserwując, które wartości klucza sprawiają, że te równania są spełnione częściej, atakujący może zawęzić poszukiwania do poprawnego klucza.

Historia

Kryptanaliza liniowa została wprowadzona przez Matsui w 1993 roku jako atak ze znanym tekstem jawnym na DES. W 1994 roku Matsui zademonstrował pierwszą eksperymentalną kryptanalizę standardu DES za pomocą kryptanalizy liniowej, odzyskując klucz z 2^43 znanych tekstów jawnych. Ten przełom zademonstrował praktyczne ataki na wdrożony standard i wpłynął na rozwój AES z udowodnionymi granicami odporności.

Kiedy stosować

Kryptanaliza liniowa jest wykorzystywana w badaniach kryptograficznych i ocenie projektowania szyfrów. Pomaga projektantom szyfrów w wyborze S-skrzynek i transformacji, które są odporne na aproksymacje liniowe. Nowoczesne szyfry są projektowane z udowodnionymi granicami siły aproksymacji liniowych.

Ograniczenia i uwagi

  • Nowoczesne szyfry (AES) są starannie zaprojektowane, aby były odporne na kryptanalizę liniową z udowodnionymi granicami
  • Wymaga znanych par tekst jawny-szyfrogram, które mogą nie być dostępne we wszystkich scenariuszach
  • Wymagania obliczeniowe i dotyczące danych mogą przekraczać praktyczną wykonalność dla dobrze zaprojektowanych szyfrów
  • Odkrycie silnych aproksymacji liniowych dla nowoczesnych szyfrów jest niezwykle trudne

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

Mocne strony

  • Praktyczny atak na DES wymagający 2^43 par tekst jawny-szyfrogram i 2^39 operacji
  • Dobrze sformalizowane ramy matematyczne (lemat piling-up) do analizy odchyleń aproksymacji
  • Uzupełnia kryptanalizę różnicową, znajdując słabości, które analiza różnicowa mogłaby przeoczyć
  • Kształtuje wymagania projektowe szyfrów dotyczące wyboru S-skrzynek i transformacji rund

Zastosowania

  • Kryptanaliza szyfrów blokowych oceniająca właściwości bezpieczeństwa w badaniach i standaryzacji
  • Projektowanie szyfrów i wybór S-skrzynek w celu zapewnienia odpowiednich granic aproksymacji liniowych
  • Walidacja standardów kryptograficznych (NIST, ETSI) wymagająca analizy odporności liniowej
  • Ocena starszych szyfrów w celu podjęcia decyzji o wycofaniu i zastąpieniu

Jak to działa

Jak to działa

1

Znajdowanie aproksymacji liniowych: liniowych zależności między bitami tekstu jawnego, bitami szyfrogramu i bitami klucza, które są spełnione z prawdopodobieństwem znacząco różnym od 0.5.

2

Oszacowanie odchylenia (od 0.5) każdej aproksymacji liniowej za pomocą analizy statystycznej transformacji rund.

3

Dla kandydujących wartości klucza, zliczanie, jak często aproksymacja liniowa jest spełniona w znanych parach tekst jawny-szyfrogram. Prawidłowy klucz sprawia, że aproksymacja jest spełniona najczęściej.

4

Weryfikacja odzyskanych bitów klucza poprzez deszyfrowanie szyfrogramu i sprawdzanie poprawności.

Częste pułapki

  • Zakładanie, że wszystkie aproksymacje liniowe są możliwe do wykorzystania; słabe aproksymacje zapewniają minimalną przewagę
  • Niedoszacowanie praktycznej trudności ataku, gdy teoretyczne wymagania dotyczące danych wydają się rozsądne
  • Zaniedbywanie interakcji między właściwościami liniowymi i różnicowymi w analizie szyfrów

Najczęściej zadawane pytania

Czym jest lemat piling-up?

Lemat piling-up dostarcza metody obliczania odchylenia aproksymacji liniowych w wielu rundach poprzez łączenie odchyleń aproksymacji poszczególnych rund. Jest on fundamentalny dla kryptanalizy liniowej.

Jak AES jest odporny na kryptanalizę liniową?

AES wykorzystuje S-skrzynki wybrane tak, aby zminimalizować maksymalne prawdopodobieństwo aproksymacji liniowej, oraz warstwę dyfuzji zapewniającą szybkie rozprzestrzenianie się odchyleń liniowych w rundach. Udowodnione granice gwarantują brak praktycznych aproksymacji liniowych.

Jaka jest różnica między kryptanalizą liniową a różnicową?

Analiza różnicowa bada różnice wejścia-wyjścia, podczas gdy analiza liniowa bada aproksymacje liniowe (XOR bitów tekstu jawnego i szyfrogramu). Obie wykorzystują słabości strukturalne w szyfrach.

Czy kryptanaliza liniowa może złamać nowoczesne szyfry?

Nie, praktycznie. Nowoczesne szyfry, takie jak AES, mają udowodnione granice aproksymacji liniowych, co sprawia, że ataki są obliczeniowo niewykonalne.

Jak ocenić odporność liniową w moim projekcie szyfru?

Należy przeanalizować tabele aproksymacji liniowych S-skrzynek i obliczyć maksymalne odchylenie w rundach za pomocą lematu piling-up. Należy upewnić się, że maksymalne odchylenie jest pomijalne we wszystkich możliwych aproksymacjach liniowych.

Pokrewne metody

Źródła

  1. Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Matsui, M. (1994). The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO 1994, LNCS 839, pp. 1-11.

    Otwórz odnośnik DOI
    Skopiowano.