Integral kryptoanalyse

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 15. juni 2014; checks kræver 14 redigeringer .

Integral kryptoanalyse er en kryptoanalysemetode , der kombinerer en række angreb på symmetriske blokkryptografiske algoritmer . I modsætning til differentiel kryptoanalyse , som overvejer effekten af en algoritme på et par klartekster, involverer integreret kryptoanalyse studiet af at kortlægge et sæt klartekster til en chiffertekst . Anvendt første gang i 1997 af Lars Knudsen .

Historie

I videnskabelige artikler blev udtrykket " integral cryptanalysis " foreslået i 1999 i publikationen Integral cryptanalysis of SAFER + (engelsk) . Selve konceptet blev første gang udtrykt af Lars Knudsen , da han analyserede Square -chifferet i 1997. Af denne grund bruges udtrykket "Square-lignende angreb" eller blot "Square-angreb" ofte i litteraturen. For 2011 er der ingen revolutionerende fremskridt med hensyn til Square-angrebet inden for integreret kryptoanalyse.

Metodens teoretiske grundlag

Lad være en endelig abelsk gruppe . Så tager vi den 1. blok som et sæt af mulige chiffertekster (i det generelle tilfælde bestemmes det af det valgte alfabet og blokstørrelse), kan vi overveje en gruppe af følgende form med samme gruppeoperation: . Det således konstruerede sæt af n-dimensionelt rum er mængden af alle mulige chiffertekster. Derfor er rumelementet en bestemt chiffertekst, komponenterne i denne vektor er værdien af chiffertekstblokkene. Vi antager, at summen af vektorer er en vektor, hvis komponenter er lig med summen af de tilsvarende komponenter i vilkårene. Mængdeintegralet er summen af alle vektorer inkluderet i : . $(G,+)$ $G$ $G$ $G^{n}=G\ gange ...\ gange G$ $v=(v_{1},...,v_{n}),v\in G$ $S\subseteq G$ $S$ $\int S=\sum _{v\in S}v$

Vellykket integreret krypteringsanalyse skulle reducere antallet af nøglegæt iterationer . For at gøre dette forsøger vi at gruppere klartekstvektorerne, så der, baseret på grupperingen, kan findes eventuelle mønstre. Det er praktisk at studere algoritmer baseret på følgende partition:

$v_{i}=c,\forall v\in S$
$\{v_{i}:v\in S\}=G$
$\sum _{v\in S}=c'$ ,

hvor er et fast tal, (vektor) $jeg$ $c,c'=const\in G$

Følgende sætning [1] spiller en nøglerolle :

Lad være en endelig abelsk gruppe . Betegn , og rækkefølgen af g er lig med 1 eller 2. Definer . Så . Desuden, $(G,+)$ $H=\{g\in G:g+g=0\}$ $s(G)=\sum _{g\in G}g$ $s(G)=\sum _{h\in H}h$ $s(G)+s(G)=0$

Det er værd at bemærke et vigtigt resultat af sætningen: hvis ), så , siden ${\displaystyle G=GF(2^{s))$ $s(G)=0$ $H=\{0\}$

Vi bemærker en række notationer, der ofte bruges i publikationer om angreb baseret på integreret kryptoanalyse:

Hvis den i -te komponent af integralet er betegnet , betyder det, at i alle termer af integralsummen, er den i -te komponent den samme ${\mathcal {C}}$
På samme måde viser det, at den tilsvarende komponent adskiller sig på alle måder. $\mathcal{A}$
$\mathcal{S}$ viser, at den givne komponent af integralet kan forudsiges.
? viser, at det er umuligt at forudsige komponenten af integralet.

Det generelle princip om at søge efter sårbarheder på eksemplet med Feistel-netværket

Overvej, hvordan integralerne over S ændres, hvis alle elementer i dette sæt føres til input fra Feistel-netværket. Lad S være et sæt af chiffertekster, hvor alle på nær én af de tilsvarende blokke er ens (de kan være forskellige fra hinanden). I eksemplet er chifferteksten 16 blokke arrangeret i 2 linjer. For chiffer som AES er det også vigtigt at overveje, at chifferteksten er givet af en matrix, da de bruger forskellige operationer for rækker og kolonner. Overvej effekten af Feistel-celler i trin:

Hvis vi antager, at Feistel-celler producerer bijektive kortlægninger , er det indlysende, at de samme blokke mellem chifferteksterne vil gå ind i de samme blokke mellem de konverterede chiffertekster (det er dog næsten sikkert, at de gamle og nye værdier vil være forskellige). Således kan vi skrive, at 1. celle afbildede et sæt fra en klasse af sæt med komponenter identiske i sæt med et sæt fra samme klasse.
Da værdien af alle blokke ved udgangen af en Feistel-celle afhænger af værdien af hver blok ved indgangen, ændrer virkningen af en enkelt blok hver blok i chifferteksten ved udgangen. Således bliver værdierne af integralets komponenter ikke mere end forudsigelige [2] . $\mathcal{A}$
Da værdisættet ved input for hver blok, der hører til inputchifferteksten, ikke er sammenfaldende med sættet af mulige blokværdier, bliver deres sum muligvis ikke bevaret under den bijektive transformation, så alt kan opnås ved output fra cellen.

Selv anvendeligt til det beskrevne eksempel er det muligt at reducere antallet af iterationer til udvælgelse betydeligt eller give yderligere information til forskellige typer kryptoanalyse.

Sammenligning med differentiel kryptoanalyse

Som med differentiel kryptoanalyse kan integralbaserede angreb klassificeres som en type angreb baseret på adaptivt valgt klartekst .

Lars Knudsen bemærkede også ligheden med det trunkerede differentialangreb , som har ideen om at overveje adfærden af ikke hele forskellen, som i differentiel kryptoanalyse, men dens dele. Desuden har integreret kryptoanalyse overlegenhed i sin evne til at overveje den tredje tilstand af resultatet - , mens angrebet af trunkerede differentialer kun skelner to. $\mathcal{S}$

For at angribe højordens differentialer kan du se, at i Galois-feltet ligner udtrykket for s -te ordens differentialet integralet [3] . Således kan man forsøge at generalisere nogle metoder til differentiel kryptoanalyse til integrale. $GF(2^{s})$

Det er bemærkelsesværdigt, at angrebene af trunkerede differentialer og højordens differentialer også først blev offentliggjort af Lars Knudsen i 1994, også på FSE-konferencen [4]

Bemærkelsesværdige angreb

Angreb på AES - lignende cifre ( Rijndael , SQUARE , CRYPTON ) kan generaliseres ved det første trin - overvejelse af integraler efter 3. krypteringsrunde. Yderligere trin er forsøg på at forbedre angrebet ved at øge antallet af runder ved at bruge forskellige antagelser, der uundgåeligt øge antallet af iterationer af søgningen, og derved også kompleksiteten ved at bryde .

AES

Angreb på 4-runds chiffer

Nøglepunkterne for bytematrixkryptering er ikke-lineær transformation, rækkeskift, kolonnetransformation, tilføjelse af tekst (mellembytematrix) med rund nøglematrix.

Overvej en seksten- byte klartekst . Lad kryptanalytikeren råde over 256 chiffertekster med følgende egenskab: de er hentet fra byte-matricer, hvor alle på nær én bytes er ens i sættet af disse chiffertekster. På grund af deres antal kan vi sige, at en "ulige" byte vil antage alle mulige værdier på et givet sæt. Således kan vi gå til ovenstående notation:

Oprindelig tilstand:

$\mathcal{A}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$

Overvej tekstens tilstand efter hver runde:

Ikke-lineær konvertering på grund af bijektivitet ændrer ikke typen af byte, kun værdierne for individuelle tekster.
Rækkeforskydningen påvirker ikke 1. række, resten forskydes uden ændring af integralet.
Kolonnekonvertering gør hver resulterende byte afhængig af alle 4 bytes i den oprindelige kolonne, men igen, på grund af operationens bijektivitet, får vi, at hver byte i kolonnen kun vil antage hver af dens værdier én gang.
Tilføjelse med en nøgle vil ikke ændre bytetyperne.

Så efter første runde:

Efter 1. runde:

$\mathcal{A}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
$\mathcal{A}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
$\mathcal{A}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
$\mathcal{A}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$

Rækkeskift fordeler 1 byte i hver kolonne med type . $\mathcal{A}$
Som i runde 1, hvis der er én byte i kolonnen og resten er , så konverteres alle bytes i kolonnen til . Alle 4 kolonner konverteres på denne måde. $\mathcal{A}$ ${\mathcal {C}}$ $\mathcal{A}$

Efter anden runde:

Efter 2. runde:

$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$
$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$
$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$
$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$

Ved at bruge resultatet af sætningen beskrevet i teoriafsnittet får vi værdierne af integralerne i hver byte ${\mathcal {S}}=0$

Efter 3. runde :

{\mathcal {S}}=0

$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$
$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$
$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$
$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$

Da der i sidste runde ikke er nogen kolonnetransformation (ifølge AES-specifikationen), og de resterende transformationer konverteres til , så ændres værdien af integralet ikke for fire-runde-skemaet som følge af den sidste runde. op til stadiet af binær addition med en rund nøgle. I dette tilfælde er der kun tilbage, at hver byte antager værdien af den tilsvarende byte af rundenøglen, får den estimerede tekst fra 3. runde og kontrollerer, om integralet af den tilsvarende blok er lig med nul. Hvis den er lig, kan den runde nøgle-byte betragtes som fundet. $\mathcal{A}$ $\mathcal{A}$

Udvidelser efter antal runder

Skemaet kan udvides til et syv-runders skema ved at overveje, hvad transformationen af integralet afhænger af en bestemt byte. Men selv i tilfælde af 7 runder er antallet af iterationer, der kræves, højt, i dette tilfælde søges forbindelserne mellem rundnøglerne ved at analysere kodegenereringsskemaet. [5]

Forbedringer af kryptografressourcer

Væsentlig reducere den tid, det tager at søge efter nøgler, på grund af den særlige organisering af søgebetingelserne, ved hjælp af tre-byte vektorer, tillader indførelsen af den såkaldte partielle sum. En sådan modifikation af en seks-rund chiffer reducerer opregningskraften fra til . En anden tilgang er at bruge det faktum, at integralet over sæt med forskellige også forsvinder efter den eftertragtede tredje runde. Denne metode kræver en enorm mængde hukommelsesressourcer og besiddelse af en meget stor base af almindelig tekst - chiffertekst. [6] $2^{{72}}$ $2^{{44}}$ ${\mathcal {C}}$

Ved at bruge delvise summer er det muligt at implementere et hack af otte-runde-systemet, men kompleksiteten af dette hack er endnu større end den udtømmende opregning .

Firkant

Det grundlæggende angreb på Square-chifferet er praktisk talt det samme som fire-runders angreb på AES, det giver dig også mulighed for at udvide antallet af runder. Måske er den eneste væsentlige forskel tilstedeværelsen af den første runde af kryptering og, som et resultat, to metoder til udvidelse (en mod den sidste runde, den anden mod den første). Udviklerne af chifferen var, mens de undersøgte det, i stand til at bygge et angreb på seks-runder kryptering .

Følgende resultater er blevet offentliggjort [7] :

Angreb på Square:

Angreb	Antal åbne tekster	Tid	Hukommelsesomkostninger
I 4 omgange	$2^{{9}}$	$2^{{9}}$	Få
I 5 omgange på 1. måde	$2^{11}$	$2^{40}$	få
Til 5 runder på 2. vej	$2^{32}$	$2^{40}$	$2^{32}$
I 6 omgange	$2^{32}$	$2^{{72}}$	$2^{32}$

Noter

↑ Herstein, Topics in Algebra, 2. udgave, 1975, side 116
↑ Dolgov, Golovashich, Ruzhentsev. "Analyse af kryptografisk styrke af Tornado-chifferet" (2003), s. 7
↑ Lars Knudsen (2001). "Integral kryptoanalyse (udvidet sammendrag), s. 118"
↑ Lars Knudsen (1994). "Trunkerede og højere ordens differentialer"
↑ Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner og Doug Whiting. "Improved Cryptanalysis of Rijndael" (2001), s. 2-3
↑ Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner og Doug Whiting. "Improved Cryptanalysis of Rijndael" (2001), s. 4-7
↑ Joan Daemen, Lars Knudsen, Vincent Rijmen. "The Block Cipher Square" (1997), s. 15