💻 computer science

Analyzing Linear Layers in Related-Differential Cryptanalysis

Dit artikel onderzoekt systematisch het bestaan van gerelateerde differentiaalstructuren in lineaire lagen van AES-achtige cijfers, bewijst dat dergelijke kwetsbaarheden onvermijdelijk zijn voor alle niet-MDS-matrices, alle symmetrische MDS-matrices van oneven orde en de meeste circulaire matrices, en biedt tegelijkertijd een volledige karakterisering voor $3 \times 3$ MDS-matrices over $\mathbb{F}_{2^m}$ .

Oorspronkelijke auteurs: Yogesh Kumar, Akshay Ankush Yadav, Susanta Samanta

Gepubliceerd 2026-05-28

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yogesh Kumar, Akshay Ankush Yadav, Susanta Samanta

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een hoogbeveiligde kluis (een digitale vergrendeling) bouwt om je geheimen te beschermen. Om ervoor te zorgen dat niemand hem kan kraken, gebruik je een speciale mengmachine die een Lineaire Laag wordt genoemd. Deze machine neemt je data, verwart deze en spreidt deze uit, zodat een kleine verandering in de invoer een enorme, chaotische verandering in de uitvoer veroorzaakt. Dit wordt "diffusie" genoemd.

Decennialang hebben cryptografen een specifiek type mengmachine gebruikt, een MDS-matrix, omdat dit de "gouden standaard" is voor het perfect spreiden van dingen. Ze dachten: "Als we een MDS-matrix gebruiken, zijn we veilig."

Echter, dit artikel onthult een verborgen gebrek in dat denken. Het blijkt dat zelfs als je mengmachine de "gouden standaard" (MDS) is, deze nog steeds een geheime zwakheid kan hebben die Gerelateerde Differentiënten wordt genoemd.

Hier is de uiteenzetting van wat de auteurs hebben ontdekt, met eenvoudige analogieën:

1. De "Gouden Standaard" is niet genoeg

Stel je het MDS-eigenschap voor als een garantie dat je mengmachine een druppel inkt over een heel vel papier verspreidt.

Het oude geloof: Als de machine de inkt perfect verspreidt (MDS), is het veilig.
De nieuwe ontdekking: De auteurs bewezen dat als een machine de inkt niet perfect verspreidt (Niet-MDS), deze garandeerd een geheime zwakheid heeft.
De analogie: Stel je voor dat je probeert een geheim bericht te verstoppen in een kamer. Als de kamer klein en rommelig is (Niet-MDS), kan een dief gemakkelijk een patroon vinden om binnen te sluipen. De auteurs bewezen dat alleen een perfect ruime, georganiseerde kamer (MDS) een kans heeft om veilig te zijn. Maar alleen het hebben van de ruime kamer garandeert geen veiligheid; de vorm van de kamer maakt ook uit.

2. De "Symmetrievalstrik"

Veel mengmachines zijn gebouwd om Symmetrisch te zijn, wat betekent dat ze er hetzelfde uitzien als je ze omdraait (zoals een vlinder). Dit is populair omdat het makkelijk te bouwen is.

De ontdekking: De auteurs ontdekten dat als een symmetrische machine een oneven aantal onderdelen heeft (zoals 3x3 of 5x5), deze altijd kwetsbaar is.
De analogie: Stel je een dansvloer voor met een oneven aantal dansers. Hoe ze ook proberen paren te vormen, er staat altijd één danser alleen in het midden, wat een voorspelbaar patroon creëert. De auteurs bewezen dat voor elke symmetrische machine met een oneven formaat er altijd een "overgebleven" patroon is dat een hacker kan exploiteren. Het maakt niet uit hoe goed je het hebt gebouwd; het oneven aantal maakt het inherent zwak tegen dit specifieke type aanval.

3. Het "Circulair Patroon"-probleem

Een ander populair ontwerp is de Circulante Matrix. Stel je een transportband voor waarbij het patroon van tandwielen in een cirkel herhaalt. Dit is efficiënt en snel.

De ontdekking: De auteurs keken naar deze circulaire machines en vonden een regel gebaseerd op hun formaat (genaamd $n$ $n$ ).
- Als het formaat van de cirkel een veelvoud is van 3 (zoals 3, 6, 9) of een veelvoud van 4 (zoals 4, 8, 12), is het kwetsbaar.
- In feite bewezen ze dat tenzij het formaat een zeer specifiek getal is (specifiek, getallen die niet 2 of 10 verwijderd zijn van een veelvoud van 12), de machine kwetsbaar is.
De analogie: Denk aan een klokgezicht. Als je probeert rond de klok te lopen in stappen van 3 of 4, zul je uiteindelijk steeds weer op dezelfde plekken terechtkomen op een voorspelbare manier. De auteurs toonden aan dat voor de meeste circulaire ontwerpen een hacker een "kortere weg" door de tandwielen kan vinden die de beveiliging omzeilt.

4. Het "Perfecte Recept" voor 3x3-machines

Tot slot richtten de auteurs zich op het kleinste, meest voorkomende formaat: 3x3-matrices.

Het probleem: Eerdere pogingen om een "veilige" 3x3-machine te vinden waren onvolledig. Ze gaven een recept dat sommige ingrediënten miste.
De oplossing: De auteurs schreven een volledig recept op dat bestaat uit 15 specifieke regels (wiskundige vergelijkingen).
De analogie: Stel je voor dat je een taart bakt. Vorige chefs zeiden: "Gebruik geen zout." De auteurs zeiden: "Eigenlijk moet je zout, suiker, bloem, eieren, melk en 11 andere specifieke ingrediënten in exacte combinaties vermijden." Ze leverden een checklist van 15 dingen om te vermijden. Als je 3x3-machine alle 15 regels volgt, is het veilig. Als het zelfs maar één breekt, is het kwetsbaar.
Het resultaat: Ze telde hoeveel 3x3-machines er bestaan en hoeveel er echt veilig zijn. Ze ontdekten dat de "veilige" exemplaren veel zeldzamer zijn dan we dachten.

Samenvatting van de Kernboodschap

Dit artikel is als een veiligheidsinspecteur voor digitale vergrendelingen. Ze vertelden ons:

Niet-MDS-machines zijn absoluut onveilig. (Je moet MDS gebruiken).
Symmetrische machines met een oneven formaat zijn absoluut onveilig. (Gebruik geen oneven getallen als je symmetrie wilt).
De meeste circulaire machines zijn onveilig. (Tenzij het formaat zeer specifiek is).
Voor 3x3-machines is hier de exacte checklist om ervoor te zorgen dat je geen zwakke vergrendeling bouwt.

De auteurs hebben geen nieuwe vergrendeling uitgevonden; ze gaven ons gewoon een betere manier om te controleren of de vergrendelingen die we al bouwen verborgen scheuren hebben.

Technische Samenvatting: Analyse van Lineaire Lagen in Gerelateerde Differentiaal Cryptanalyse

Probleemstelling
In op SPN gebaseerde blokcijfers (bijv. AES) wordt de lineaire diffusielag doorgaans geïmplementeerd met behulp van Maximum Distance Separable (MDS)-matrices om optimale takgetallen en weerstand tegen klassieke differentiaal- en lineaire cryptanalyse te waarborgen. Echter, recent werk van Daemen en Rijmen (2009) en Bardeh en Rijmen (2022) toonde aan dat MDS-matrices toch "gerelateerde differentiaal"-structuren kunnen vertonen. Deze structuren maken het mogelijk om gerelateerde differentiaalcharactristieken te construeren die kunnen worden uitgebuit in aanvallen, zoals de 7-ronden sleutelherstel-aanval op AES-128. Hoewel eerdere studies gerelateerde differentiaten hebben geïdentificeerd in specifieke gevallen (bijv. 4×4 circulaire matrices, 3×3 involutorische matrices), blijft een systematisch begrip van welke lineaire-lagstructuren deze differentiaten inherent vermijden of toelaten onvolledig. Dit artikel onderzoekt de voorwaarden waaronder lineaire lagen over eindige velden gerelateerde differentiaten vermijden, met als doel matrixklassen te identificeren die inherent weerstand bieden tegen dit specifieke cryptanalytische vector.

Methodologie
De auteurs hanteren een theoretische algebraïsche aanpak over eindige velden met karakteristiek 2 ( $\mathbb{F}_{2^m}$ ). De methodologie omvat:

Definiëren van Gerelateerde Differentiaten: Gebruikmakend van de definities van Daemen en Rijmen, waarbij twee differentiaten $(u, Mu)$ en $(v, Mv)$ "gerelateerd" zijn als het inputpaar $(u, v)$ en outputpaar $(Mu, Mv)$ voldoen aan de voorwaarde $x_i \cdot y_i \cdot (x_i \oplus y_i) = 0$ voor alle coördinaten.
Structurele Analyse: Onderzoeken van de relatie tussen matrixeigenschappen (MDS-status, symmetrie, circulaire structuur) en het bestaan van niet-triviale paren van gerelateerde differentiaten.
Polynoomontbinding: Voor circulaire matrices mappingen de auteurs de matrixoperaties naar polynoomvermenigvuldiging in de quotiëntring $\mathbb{F}_{2^m}[X]/\langle X^n - 1 \rangle$ . Ze ontbinden het transformatiepolynoom op basis van modulaire rekenkunde van exponenten (modulo 2, 3 en 4) om specifieke input-differentieparen te construeren die gerelateerde outputdifferenties opleveren.
Voorbeeldsgewijze Enumeratie: Voor het $3 \times 3$ -geval maken de auteurs gebruik van de ontbinding van elke MDS-matrix in een representatieve vorm $M = D_1 M_1 D_2$ (waarbij $D_i$ diagonaal zijn en $M_1$ een specifieke representant is). Ze analyseren systematisch alle mogelijke Hamming-gewichtpatronen van input-differentie tripletten $(u, v, u \oplus v)$ om noodzakelijke en voldoende algebraïsche voorwaarden af te leiden voor het afwezig zijn van gerelateerde differentiaten.

Belangrijkste Bijdragen en Resultaten

Noodzaak van de MDS-eigenschap:
Het artikel bewijst dat de MDS-eigenschap een noodzakelijke voorwaarde is voor het vermijden van gerelateerde differentiaten. Specifiek toont Stelling 2 aan dat elke niet-MDS-matrix ten minste één niet-triviaal paar van gerelateerde differentiaten toelaat. Dit beperkt de zoekruimte voor resistente lineaire lagen strikt tot de klasse van MDS-matrices.
Kwetsbaarheid van Symmetrische Matrices:
De auteurs stellen vast dat symmetrie in oneven dimensies een inherente kwetsbaarheid is. Stelling 4 bewijst dat elke symmetrische MDS-matrix van oneven orde gerelateerde differentiaten toelaat. Dit resultaat sluit brede families van constructies uit, waaronder Type 2 Cauchy-gebaseerde MDS-matrices en links-circulaire matrices van oneven orde (Corollarium 2 en 3), aangezien deze inherent symmetrisch en dus kwetsbaar zijn.
Kwetsbaarheid van Circulaire Matrices:
Het artikel biedt een uitgebreide karakterisering voor circulaire matrices. Door de modulaire eigenschappen van de matrixorde $n$ te analyseren, bewijzen de auteurs in Stelling 5 dat een circulaire MDS-matrix van orde $n$ gerelateerde differentiaten toelaat zolang $n \not\equiv \pm 2 \pmod{12}$ . Dit generaliseert eerdere bevindingen voor $3 \times 3$ en $4 \times 4$ gevallen, en identificeert een brede klasse van kwetsbare orden.
Volledige Karakterisering van $3 \times 3$ Matrices:
Door het $3 \times 3$ -geval opnieuw te bekijken, leiden de auteurs een volledige algebraïsche karakterisering af. Stelling 7 biedt een expliciete set van 15 noodzakelijke en voldoende polynoombeperkingen op de parameters van een representatieve $3 \times 3$ MDS-matrix. Als aan een van deze 15 voorwaarden wordt voldaan, laat de matrix gerelateerde differentiaten toe; als geen enkele wordt voldaan, is de matrix resistent.
- Het artikel merkt op dat eerdere karakterisering (bijv. door Otal et al.) onvolledig waren.
- Met behulp van deze karakterisering berekenen de auteurs het exacte aantal $3 \times 3$ MDS-matrices over diverse eindige velden ( $\mathbb{F}_{2^m}$ ) die geen gerelateerde differentiaten bezitten, en tonen aan dat de verzameling resistente matrices een strikte deelverzameling is van alle MDS-matrices (Tabel I).

Betekenis en Beweringen
Het artikel claimt een systematisch onderzoek te bieden naar de structurele pre-requisieten voor weerstand tegen gerelateerde differentiaal cryptanalyse. De primaire betekenis ligt in:

Grenzen Stellen: Bewijzen dat de MDS-eigenschap alleen onvoldoende is voor weerstand en dat specifieke structurele eigenschappen (symmetrie van oneven orde, specifieke circulaire orden) kwetsbaarheid garanderen.
Verfijnen van Ontwerpcriteria: Aanbieden van een concrete, verifieerbare set van 15 algebraïsche beperkingen voor $3 \times 3$ matrices, waardoor ontwerpers deze dimensie exhaustief kunnen verifiëren of resistente matrices kunnen construeren.
Sturen van Toekomstige Constructie: Door te identificeren dat niet-MDS-matrices inherent kwetsbaar zijn en dat veel gebruikelijke symmetrische constructies falen, richt dit werk toekomstig onderzoek op het construeren van MDS-matrices die zowel asymmetrisch (of symmetrisch van even orde) zijn als voldoen aan de specifieke algebraïsche beperkingen die voor weerstand zijn afgeleid.

De auteurs concluderen dat hoewel het $3 \times 3$ -geval volledig is gekarakteriseerd, het uitbreiden van deze resultaten naar $4 \times 4$ matrices en het construeren van lichtgewicht, efficiënte MDS-matrices zonder gerelateerde differentiaten open uitdagingen blijven. Zij merken ook op dat de onopgeloste gevallen voor circulaire matrices (waar $n \equiv \pm 2 \pmod{12}$ ) een conjectuur vormen voor toekomstig bewijs.