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
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
Finden Sie lineare Approximationen: lineare Beziehungen zwischen Klartextbits, Chiffretextbits und Schlüsselbits, die mit einer Wahrscheinlichkeit signifikant abweichend von 0,5 gelten.
Schätzen Sie die Verzerrung (Abweichung von 0,5) jeder linearen Approximation mithilfe statistischer Analyse der Rundentransformationen.
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.
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
Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397.
DOI-Referenz öffnenKopiert.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 öffnenKopiert.