💻 computer science

Analyzing Linear Layers in Related-Differential Cryptanalysis

Dieser Artikel untersucht systematisch das Vorhandensein von verwandten Differentialstrukturen in linearen Schichten AES-ähnlicher Chiffren, beweist, dass solche Schwachstellen für alle nicht-MDS-Matrizen, alle symmetrischen MDS-Matrizen ungerader Ordnung und die meisten zirkulanten Matrizen unvermeidbar sind, und liefert gleichzeitig eine vollständige Charakterisierung für $3 \times 3$ -MDS-Matrizen über $\mathbb{F}_{2^m}$ .

Ursprüngliche Autoren: Yogesh Kumar, Akshay Ankush Yadav, Susanta Samanta

Veröffentlicht 2026-05-28

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Yogesh Kumar, Akshay Ankush Yadav, Susanta Samanta

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie bauen einen hochsicheren Tresor (ein digitales Schloss), um Ihre Geheimnisse zu schützen. Um sicherzustellen, dass niemand ihn knacken kann, verwenden Sie eine spezielle Mischmaschine namens Lineare Schicht. Diese Maschine nimmt Ihre Daten, verwirbelt sie und verteilt sie so, dass eine winzige Änderung am Eingang eine riesige, chaotische Änderung am Ausgang bewirkt. Dies wird als „Diffusion" bezeichnet.

Seit Jahrzehnten verwenden Kryptografen eine bestimmte Art von Mischmaschine, die MDS-Matrix genannt wird, weil sie der „Goldstandard" für eine perfekte Verteilung ist. Sie dachten: „Wenn wir eine MDS-Matrix verwenden, sind wir sicher."

Dieser Artikel jedoch enthüllt einen versteckten Fehler in dieser Denkweise. Es stellt sich heraus, dass selbst wenn Ihre Mischmaschine der „Goldstandard" (MDS) ist, sie dennoch eine geheime Schwäche namens Verwandte Differentiale haben könnte.

Hier ist die Aufschlüsselung dessen, was die Autoren entdeckt haben, unter Verwendung einfacher Analogien:

1. Der „Goldstandard" reicht nicht aus

Stellen Sie sich die MDS-Eigenschaft als Garantie vor, dass Ihre Mischmaschine einen Tintentropfen über eine ganze Papierseite verteilt.

Der alte Glaube: Wenn die Maschine die Tinte perfekt verteilt (MDS), ist sie sicher.
Die neue Entdeckung: Die Autoren bewiesen, dass, wenn eine Maschine die Tinte nicht perfekt verteilt (Nicht-MDS), sie garantiert eine geheime Schwäche aufweist.
Die Analogie: Stellen Sie sich vor, Sie versuchen, eine geheime Nachricht in einem Raum zu verstecken. Wenn der Raum klein und überfüllt ist (Nicht-MDS), kann ein Dieb leicht ein Muster finden, um sich hineinzuschleichen. Die Autoren bewiesen, dass nur ein perfekt geräumiger, organisierter Raum (MDS) eine Chance hat, sicher zu sein. Doch allein das Vorhandensein des geräumigen Raums garantiert keine Sicherheit; die Form des Raums ist ebenfalls entscheidend.

2. Die „Symmetrie-Falle"

Viele Mischmaschinen sind so konstruiert, dass sie symmetrisch sind, was bedeutet, dass sie gleich aussehen, wenn man sie umdreht (wie ein Schmetterling). Dies ist beliebt, weil sie einfach zu bauen sind.

Die Entdeckung: Die Autoren fanden heraus, dass eine symmetrische Maschine mit einer ungeraden Anzahl von Teilen (wie 3x3 oder 5x5) immer anfällig ist.
Die Analogie: Stellen Sie sich einen Tanzboden mit einer ungeraden Anzahl von Tänzern vor. Egal wie sehr sie versuchen, sich zu paaren, ein Tänzer steht immer in der Mitte zurück und erzeugt ein vorhersehbares Muster. Die Autoren bewiesen, dass für jede symmetrische Maschine mit ungerader Größe es immer ein „übrig gebliebenes" Muster gibt, das ein Hacker ausnutzen kann. Es spielt keine Rolle, wie gut Sie sie gebaut haben; die ungerade Zahl macht sie inhärent schwach gegen diese spezifische Art von Angriff.

3. Das Problem des „kreisförmigen Musters"

Ein anderes beliebtes Design ist die Zirkulante Matrix. Stellen Sie sich ein Förderband vor, bei dem sich das Muster der Zahnräder im Kreis wiederholt. Dies ist effizient und schnell.

Die Entdeckung: Die Autoren untersuchten diese kreisförmigen Maschinen und fanden eine Regel basierend auf ihrer Größe (genannt $n$ $n$ ).
- Wenn die Größe des Kreises ein Vielfaches von 3 ist (wie 3, 6, 9) oder ein Vielfaches von 4 (wie 4, 8, 12), ist sie anfällig.
- Tatsächlich bewiesen sie, dass es, es sei denn, die Größe eine sehr spezifische Zahl ist (nämlich Zahlen, die nicht 2 oder 10 von einem Vielfachen von 12 entfernt sind), die Maschine anfällig ist.
Die Analogie: Denken Sie an ein Zifferblatt. Wenn Sie versuchen, in Schritten von 3 oder 4 um das Zifferblatt zu gehen, werden Sie schließlich immer wieder auf dieselben Stellen stoßen, und zwar auf eine vorhersehbare Weise. Die Autoren zeigten, dass bei den meisten kreisförmigen Designs ein Hacker einen „Abkürzungsweg" durch die Zahnräder finden kann, der die Sicherheit umgeht.

4. Das „perfekte Rezept" für 3x3-Maschinen

Schließlich konzentrierten sich die Autoren auf die kleinste und häufigste Größe: 3x3-Matrizen.

Das Problem: Frühere Versuche, eine „sichere" 3x3-Maschine zu finden, waren unvollständig. Sie lieferten ein Rezept, dem einige Zutaten fehlten.
Die Lösung: Die Autoren schrieben ein vollständiges Rezept auf, das aus 15 spezifischen Regeln (mathematischen Gleichungen) besteht.
Die Analogie: Stellen Sie sich vor, Sie backen einen Kuchen. Frühere Köche sagten: „Verwenden Sie kein Salz." Die Autoren sagten: „Tatsächlich müssen Sie Salz, Zucker, Mehl, Eier, Milch und 11 weitere spezifische Zutaten in exakten Kombinationen vermeiden." Sie lieferten eine Checkliste mit 15 Dingen, die zu vermeiden sind. Wenn Ihre 3x3-Maschine alle 15 Regeln befolgt, ist sie sicher. Wenn sie auch nur eine bricht, ist sie anfällig.
Das Ergebnis: Sie zählten, wie viele 3x3-Maschinen existieren und wie viele tatsächlich sicher sind. Sie stellten fest, dass die „sicheren" viel seltener sind als gedacht.

Zusammenfassung der Erkenntnis

Dieser Artikel ist wie ein Sicherheitsinspektor für digitale Schlösser. Sie sagten uns:

Nicht-MDS-Maschinen sind definitiv unsicher. (Sie müssen MDS verwenden).
Symmetrische Maschinen mit ungerader Größe sind definitiv unsicher. (Verwenden Sie keine ungeraden Zahlen, wenn Sie Symmetrie wünschen).
Die meisten kreisförmigen Maschinen sind unsicher. (Es sei denn, die Größe ist sehr spezifisch).
Für 3x3-Maschinen ist hier die genaue Checkliste, um sicherzustellen, dass Sie kein schwaches Schloss bauen.

Die Autoren erfanden kein neues Schloss; sie gaben uns lediglich eine bessere Möglichkeit zu prüfen, ob die Schlösser, die wir bereits bauen, versteckte Risse haben.

Technischer Zusammenfassung: Analyse linearer Schichten in der verwandten-differentiellen Kryptoanalyse

Problemstellung
Bei SPN-basierten Blockchiffren (z. B. AES) wird die lineare Diffusionsschicht typischerweise unter Verwendung von Maximum Distance Separable (MDS)-Matrizen implementiert, um optimale Verzweigungszahlen und Widerstandsfähigkeit gegen klassische differentielle und lineare Kryptoanalyse zu gewährleisten. Neuere Arbeiten von Daemen und Rijmen (2009) sowie Bardeh und Rijmen (2022) haben jedoch aufgezeigt, dass MDS-Matrizen dennoch „verwandte-differentielle" Strukturen aufweisen können. Diese Strukturen ermöglichen die Konstruktion verwandter-differentieller Charakteristiken, die in Angriffen ausgenutzt werden können, wie beispielsweise dem 7-Runden-Schlüsselwiederherstellungsangriff auf AES-128. Während frühere Studien verwandte Differentiale in spezifischen Instanzen identifiziert haben (z. B. 4×4-zirkulante Matrizen, 3×3-involutionäre Matrizen), bleibt ein systematisches Verständnis davon, welche linearen Schichtstrukturen diese Differentiale inhärent vermeiden oder zulassen, unvollständig. Dieser Beitrag untersucht die Bedingungen, unter denen lineare Schichten über endlichen Körpern verwandte Differentiale vermeiden, mit dem Ziel, Matrixklassen zu identifizieren, die inhärent gegen diesen spezifischen kryptoanalytischen Vektor resistent sind.

Methodik
Die Autoren wenden einen theoretisch-algebraischen Ansatz über endliche Körper der Charakteristik 2 ( $\mathbb{F}_{2^m}$ ) an. Die Methodik umfasst:

Definition verwandter Differentiale: Nutzung der Definitionen von Daemen und Rijmen, wonach zwei Differentiale $(u, Mu)$ und $(v, Mv)$ „verwandt" sind, wenn das Eingabepaar $(u, v)$ und das Ausgabepaar $(Mu, Mv)$ die Bedingung $x_i \cdot y_i \cdot (x_i \oplus y_i) = 0$ für alle Koordinaten erfüllen.
Strukturelle Analyse: Untersuchung des Zusammenhangs zwischen Matrixeigenschaften (MDS-Status, Symmetrie, zirkulante Struktur) und dem Vorhandensein nichttrivialer verwandter Differentialpaare.
Polynomzerlegung: Für zirkulante Matrizen bilden die Autoren die Matrixoperationen auf Polynommultiplikation im Quotientenring $\mathbb{F}_{2^m}[X]/\langle X^n - 1 \rangle$ ab. Sie zerlegen das Transformationspolynom basierend auf der modularen Arithmetik der Exponenten (modulo 2, 3 und 4), um spezifische Eingabedifferenzpaare zu konstruieren, die verwandte Ausgabedifferenzen erzeugen.
Fallweise Enumeration: Für den Fall $3 \times 3$ nutzen die Autoren die Zerlegung jeder MDS-Matrix in eine repräsentative Form $M = D_1 M_1 D_2$ (wobei $D_i$ diagonal und $M_1$ ein spezifischer Repräsentant ist). Sie analysieren systematisch alle möglichen Hamming-Gewichtsmuster von Eingabedifferenz-Tripeln $(u, v, u \oplus v)$ , um notwendige und hinreichende algebraische Bedingungen für das Fehlen verwandter Differentiale abzuleiten.

Hauptbeiträge und Ergebnisse

Notwendigkeit der MDS-Eigenschaft:
Der Beitrag beweist, dass die MDS-Eigenschaft eine notwendige Bedingung für die Vermeidung verwandter Differentiale ist. Insbesondere zeigt Satz 2, dass jede nicht-MDS-Matrix mindestens ein nichttriviales Paar verwandter Differentiale zulässt. Dies schränkt den Suchraum für resistente lineare Schichten strikt auf die Klasse der MDS-Matrizen ein.
Verwundbarkeit symmetrischer Matrizen:
Die Autoren stellen fest, dass Symmetrie in ungeraden Dimensionen eine inhärente Verwundbarkeit darstellt. Satz 4 beweist, dass jede symmetrische MDS-Matrix ungerader Ordnung verwandte Differentiale zulässt. Dieses Ergebnis schließt breite Familien von Konstruktionen aus, einschließlich MDS-Matrizen vom Typ 2 auf Cauchy-Basis und links-zirkulante Matrizen ungerader Ordnung (Korollare 2 und 3), da diese inhärent symmetrisch und somit verwundbar sind.
Verwundbarkeit zirkulanter Matrizen:
Der Beitrag liefert eine umfassende Charakterisierung für zirkulante Matrizen. Durch Analyse der modularen Eigenschaften der Matrixordnung $n$ beweisen die Autoren in Satz 5, dass eine zirkulante MDS-Matrix der Ordnung $n$ verwandte Differentiale zulässt, sofern $n \not\equiv \pm 2 \pmod{12}$ gilt. Dies verallgemeinert frühere Erkenntnisse für die Fälle $3 \times 3$ und $4 \times 4$ und identifiziert eine breite Klasse verwundbarer Ordnungen.
Vollständige Charakterisierung von $3 \times 3$ -Matrizen:
Unter Wiederaufnahme des Falls $3 \times 3$ leiten die Autoren eine vollständige algebraische Charakterisierung ab. Satz 7 liefert eine explizite Menge von 15 notwendigen und hinreichenden polynomiellen Einschränkungen für die Parameter einer repräsentativen $3 \times 3$ -MDS-Matrix. Wenn eine dieser 15 Bedingungen erfüllt ist, zulässt die Matrix verwandte Differentiale; wenn keine erfüllt ist, ist die Matrix resistent.
- Der Beitrag stellt fest, dass frühere Charakterisierungen (z. B. von Otal et al.) unvollständig waren.
- Unter Verwendung dieser Charakterisierung berechnen die Autoren die genaue Anzahl der $3 \times 3$ -MDS-Matrizen über verschiedenen endlichen Körpern ( $\mathbb{F}_{2^m}$ ), die keine verwandten Differentiale aufweisen, und zeigen, dass die Menge der resistenter Matrizen eine echte Teilmenge aller MDS-Matrizen ist (Tabelle I).

Bedeutung und Behauptungen
Der Beitrag beansprucht, eine systematische Untersuchung der strukturellen Voraussetzungen für den Widerstand gegen verwandte-differentielle Kryptoanalyse zu liefern. Seine primäre Bedeutung liegt in:

Festlegung von Grenzen: Beweis, dass die MDS-Eigenschaft allein für Widerstandsfähigkeit unzureichend ist und dass spezifische strukturelle Eigenschaften (Symmetrie ungerader Ordnung, bestimmte zirkulante Ordnungen) Verwundbarkeit garantieren.
Verfeinerung von Designkriterien: Bereitstellung einer konkreten, überprüfbaren Menge von 15 algebraischen Einschränkungen für $3 \times 3$ -Matrizen, die es Designern ermöglicht, resistente Matrizen in dieser Dimension umfassend zu verifizieren oder zu konstruieren.
Leitung zukünftiger Konstruktionen: Durch die Identifizierung, dass nicht-MDS-Matrizen inhärent verwundbar sind und viele gängige symmetrische Konstruktionen versagen, lenkt die Arbeit zukünftige Forschung auf die Konstruktion von MDS-Matrizen, die sowohl asymmetrisch (oder symmetrisch gerader Ordnung) sind als auch die spezifischen algebraischen Einschränkungen für Widerstandsfähigkeit erfüllen.

Die Autoren schließen, dass zwar der Fall $3 \times 3$ vollständig charakterisiert ist, die Erweiterung dieser Ergebnisse auf $4 \times 4$ -Matrizen und die Konstruktion leichter, effizienter MDS-Matrizen ohne verwandte Differentiale jedoch offene Herausforderungen bleiben. Sie weisen zudem darauf hin, dass die ungelösten Fälle für zirkulante Matrizen (wo $n \equiv \pm 2 \pmod{12}$ ) eine Vermutung für zukünftige Beweise darstellen.