Zum Inhalt springen
Zurück zu den Suchergebnissen

Lineare Kryptoanalyse

Eingeführt von
Mitsuru Matsui
Jahr
1993
Typ
linear approximation attack
Familie
Cryptanalytic technique

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

Die lineare Kryptoanalyse ist ein Angriff mit bekanntem Klartext (engl. known-plaintext attack), der lineare Approximationen der nichtlinearen Transformationen einer Chiffre ausnutzt, um geheime Schlüsselbits wiederherzustellen.

Die 1993 von Mitsuru Matsui eingeführte lineare Kryptoanalyse ermöglicht praktische Angriffe auf Chiffren wie DES mit einer Rechenkomplexität, die geringer ist als die Brute-Force-Methode. Die Technik analysiert statistische Verzerrungen in der Beziehung zwischen linearen Kombinationen von Klartext- und Chiffretextbits und Schlüsselbits, wodurch die Schlüsselwiederherstellung mit reduziertem Datenbedarf ermöglicht wird.

Die Intuition hinter der Methode

Die lineare Kryptoanalyse findet lineare Gleichungen, die Klartextbits, Chiffretextbits und Schlüsselbits in Beziehung setzen. Aufgrund der nicht perfekten Mischung in den Chiffrierrunden gelten diese linearen Gleichungen mit einer Wahrscheinlichkeit, die geringfügig besser ist als zufällig. Durch das Sammeln vieler Klartext-Chiffretext-Paare und die Beobachtung, welche Schlüsselwerte diese Gleichungen häufiger erfüllen, kann der Angreifer den korrekten Schlüssel eingrenzen.

Geschichte

Die lineare Kryptoanalyse wurde 1993 von Matsui als Angriff mit bekanntem Klartext auf DES eingeführt. 1994 demonstrierte Matsui die erste experimentelle Kryptoanalyse des DES-Standards unter Verwendung der linearen Kryptoanalyse, wobei ein Schlüssel mit 2^43 bekannten Klartexten wiederhergestellt wurde. Dieser Durchbruch zeigte praktische Angriffe gegen einen eingesetzten Standard und beeinflusste die Entwicklung von AES mit nachweisbaren Widerstandsgrenzen.

Wann wird sie eingesetzt?

Die lineare Kryptoanalyse wird in der Kryptanalyseforschung und bei der Bewertung von Chiffre-Designs eingesetzt. Sie leitet Chiffre-Designer bei der Auswahl von S-Boxen und Transformationen an, die linearen Approximationen widerstehen. Moderne Chiffren werden mit nachgewiesenen Grenzen für die Stärke linearer Approximationen entworfen.

Grenzen und Hinweise

  • Moderne Chiffren (AES) sind sorgfältig konzipiert, um linearer Kryptoanalyse mit nachweisbaren Grenzen zu widerstehen
  • Erfordert bekannte Klartext-Chiffretext-Paare, die möglicherweise nicht in allen Szenarien verfügbar sind
  • Rechen- und Datenanforderungen können für gut konzipierte Chiffren die praktische Machbarkeit übersteigen
  • Das Auffinden starker linearer Approximationen für moderne Chiffren ist extrem schwierig

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Praktischer Angriff auf DES, der 2^43 Klartext-Chiffretext-Paare und 2^39 Operationen erfordert
  • Gut formalisierter mathematischer Rahmen (Piling-Up-Lemma) zur Analyse von Approximationsverzerrungen
  • Ergänzt die differentielle Kryptoanalyse und findet Schwachstellen, die die differentielle Analyse möglicherweise übersieht
  • Formt die Anforderungen an das Chiffre-Design für die S-Box-Auswahl und Rundentransformation

Anwendungen

  • Kryptoanalyse von Blockchiffren zur Bewertung von Sicherheitseigenschaften in Forschung und Standardisierung
  • Chiffre-Design und S-Box-Auswahl zur Sicherstellung adäquater linearer Approximationsgrenzen
  • Validierung kryptographischer Standards (NIST, ETSI), die eine lineare Widerstandsanalyse erfordert
  • Bewertung von Legacy-Chiffren für Entscheidungen zur Außerbetriebnahme und zum Ersatz

So funktioniert es

So funktioniert es

1

Finden Sie lineare Approximationen: lineare Beziehungen zwischen Klartextbits, Chiffretextbits und Schlüsselbits, die mit einer Wahrscheinlichkeit signifikant abweichend von 0,5 gelten.

2

Schätzen Sie die Verzerrung (Abweichung von 0,5) jeder linearen Approximation mithilfe statistischer Analyse der Rundentransformationen.

3

Zählen Sie für Kandidatenschlüsselwerte, wie oft die lineare Approximation in bekannten Klartext-Chiffretext-Paaren zutrifft. Der korrekte Schlüssel lässt die Approximation am häufigsten zutreffen.

4

Verifizieren Sie wiederhergestellte Schlüsselbits durch Entschlüsselung des Chiffretextes und Überprüfung der Korrektheit.

Häufige Fallstricke

  • Annahme, dass alle linearen Approximationen ausnutzbar sind; schwache Approximationen bieten minimalen Vorteil
  • Unterschätzung der praktischen Angriffsschwierigkeit, wenn theoretische Datenanforderungen vernünftig erscheinen
  • Vernachlässigung der Interaktion zwischen linearen und differentiellen Eigenschaften bei der Chiffreanalyse

Häufig gestellte Fragen

Was ist das Piling-Up-Lemma?

Das Piling-Up-Lemma bietet eine Methode zur Berechnung der Verzerrung linearer Approximationen über mehrere Runden hinweg, indem die Verzerrungen individueller Rundenapproximationen kombiniert werden. Es ist grundlegend für die lineare Kryptoanalyse.

Wie widersteht AES der linearen Kryptoanalyse?

AES verwendet S-Boxen, die so gewählt sind, dass die maximale lineare Approximationswahrscheinlichkeit minimiert wird, und eine Diffusionsschicht, die eine schnelle Diffusion linearer Verzerrungen über die Runden hinweg gewährleistet. Nachweisbare Grenzen garantieren keine praktischen linearen Approximationen.

Was ist der Unterschied zwischen linearer und differentieller Kryptoanalyse?

Die differentielle Analyse untersucht Eingabe-Ausgabe-Differenzen, während die lineare Analyse lineare Approximationen (XOR von Klartext- und Chiffretextbits) untersucht. Beide nutzen strukturelle Schwachstellen in Chiffren aus.

Kann die lineare Kryptoanalyse moderne Chiffren brechen?

Praktisch nicht. Moderne Chiffren wie AES haben nachweisbare Grenzen für lineare Approximationen, die Angriffe rechnerisch undurchführbar machen.

Wie bewerte ich den linearen Widerstand in meinem Chiffre-Design?

Analysieren Sie die linearen Approximationstabellen der S-Box und berechnen Sie die maximale Verzerrung über die Runden hinweg mithilfe des Piling-Up-Lemmas. Stellen Sie sicher, dass die maximale Verzerrung über alle möglichen linearen Approximationen hinweg vernachlässigbar ist.

Verwandte Methoden

Quellen

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

    DOI-Referenz öffnen
    Kopiert.
  2. Matsui, M. (1994). The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO 1994, LNCS 839, pp. 1-11.

    DOI-Referenz öffnen
    Kopiert.