Integral kryptoanalys

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 15 juni 2014; kontroller kräver 14 redigeringar .

Integral kryptoanalys är en kryptoanalysmetod som kombinerar ett antal attacker på symmetriska blockkrypteringsalgoritmer . Till skillnad från differentiell kryptoanalys , som tar hänsyn till effekten av en algoritm på ett par klartexter, involverar integrerad kryptoanalys studiet av att kartlägga en uppsättning klartexter till en chiffertext . Ansöktes första gången 1997 av Lars Knudsen .

Historik

I vetenskapliga artiklar föreslogs termen " integral cryptanalysis " 1999 i publikationen Integral cryptanalysis of SAFER + (engelska) . Själva konceptet uttrycktes först av Lars Knudsen när han analyserade Square -chifferet 1997. Av denna anledning används ofta termen "Kvadratisk-liknande attacker" eller helt enkelt "Square-attack" i litteraturen. För 2011 finns det inga revolutionerande framsteg när det gäller Square-attacken inom området integrerad kryptoanalys.

Den teoretiska grunden för metoden

Låt vara en ändlig abelsk grupp . Sedan, med det första blocket som en uppsättning möjliga chiffertexter (i det allmänna fallet bestäms det av det valda alfabetet och blockstorleken), kan vi överväga en grupp av följande form, med samma gruppoperation: . Uppsättningen av n-dimensionell rymd som på så sätt konstrueras är mängden av alla möjliga chiffertexter. Följaktligen är rymdelementet en viss chiffertext, komponenterna i denna vektor är värdet på chiffertextblocken. Vi antar att summan av vektorer är en vektor vars komponenter är lika med summan av motsvarande komponenter i termerna. Mängdintegralen är summan av alla vektorer som ingår i : . $(G,+)$ $G$ $G$ $G^{n}=G\times ...\times G$ $v=(v_{1},...,v_{n}),v\in G$ $S\subseteq G$ $S$ $\int S=\summa _{v\in S}v$

Framgångsrik integrerad kryptoanalys bör minska antalet nyckelgissningsiterationer . För att göra detta försöker vi gruppera klartextvektorerna så att alla mönster kan hittas baserat på grupperingen. Det är bekvämt att studera algoritmer baserade på följande partition:

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

var är ett fast tal, (vektor) $i$ $c,c'=const\in G$

Följande sats [1] spelar en nyckelroll :

Låt vara en ändlig abelsk grupp . Beteckna , och ordningen på g är lika med 1 eller 2. Definiera . Sedan . Vidare, $(G,+)$ $H=\{g\in G:g+g=0\}$ $s(G)=\summa _{g\in G}g$ $s(G)=\summa _{h\in H}h$ $s(G)+s(G)=0$

Det är värt att notera ett viktigt resultat av satsen: om ), då , sedan ${\displaystyle G=GF(2^{s))$ $s(G)=0$ $H=\{0\}$

Vi noterar ett antal notationer som ofta används i publikationer om attacker baserade på integrerad kryptoanalys:

Om den i -te komponenten av integralen betecknas betyder det att i alla termer av integralsumman är den i -te komponenten densamma ${\mathcal {C}}$
På samma sätt visar det att motsvarande komponent skiljer sig åt i alla termer. $\mathcal{A}$
$\mathcal{S}$ visar att den givna komponenten av integralen kan förutsägas.
? visar att det är omöjligt att förutsäga integralens komponent.

Den allmänna principen för att söka efter sårbarheter i exemplet med Feistel-nätverket

Tänk på hur integralerna över S förändras om alla element i denna uppsättning matas till Feistel-nätverkets ingång. Låt S vara en uppsättning chiffertexter där alla utom ett av motsvarande block är samma (de kan skilja sig från varandra). I exemplet är chiffertexten 16 block ordnade på 2 rader. För chiffer som AES är det också viktigt att tänka på att chiffertexten ges av en matris, eftersom de använder olika operationer för rader och kolumner. Tänk på effekten av Feistel-celler i steg:

Om vi antar att Feistel-celler producerar bijektiva mappningar är det uppenbart att samma block mellan chiffertexterna kommer att gå in i samma block mellan de konverterade chiffertexterna (det är dock nästan säkert att de gamla och nya värdena kommer att skilja sig åt). Således kan vi skriva att den första cellen mappade en uppsättning från en klass av uppsättningar med komponenter identiska i uppsättning med en uppsättning från samma klass.
Eftersom värdet av alla block vid utgången av en Feistel-cell beror på värdet av varje block vid ingången, ändrar effekten av ett enda block varje block i chiffertexten vid utgången. Således blir värdena för komponenterna i integralen inte mer än förutsägbara [2] . $\mathcal{A}$
Eftersom vid ingången för varje block som hör till den ingående chiffertexten, uppsättningen av värden inte sammanfaller med uppsättningen av möjliga blockvärden, kan deras summa inte bevaras under den bijektiva transformationen, så allt kan erhållas vid utgången från Cellen.

Även tillämpligt på det beskrivna exemplet är det möjligt att avsevärt minska antalet iterationer för urval eller tillhandahålla ytterligare information för olika typer av kryptoanalys.

Jämförelse med differentiell kryptoanalys

Precis som med differentiell kryptoanalys kan integralbaserade attacker klassificeras som en typ av attack baserad på adaptivt vald klartext .

Lars Knudsen noterade också likheten med den trunkerade differentiella attacken , som har idén att överväga beteendet hos inte hela skillnaden, som i differentiell kryptoanalys, utan dess delar. Dessutom har integrerad kryptoanalys överlägsenhet i sin förmåga att överväga resultatets tredje tillstånd - , medan attacken av trunkerade differentialer bara skiljer två. $\mathcal{S}$

För att attackera differentialer av hög ordning , kan du se att i Galois-fältet liknar uttrycket för differentialen av s - ordningen integralen [3] . Således kan man försöka generalisera vissa metoder för differentiell kryptoanalys till integral. $GF(2^{s})$

Det är anmärkningsvärt att attackerna av trunkerade differentialer och differentialer av hög ordning också först publicerades av Lars Knudsen 1994, också på FSE-konferensen [4]

Anmärkningsvärda attacker

Attacker på AES - liknande chiffer ( Rijndael , SQUARE , CRYPTON ) kan generaliseras genom det första steget - övervägande av integraler efter den 3:e omgången av kryptering. Ytterligare steg är försök att förbättra attacken genom att öka antalet omgångar, med olika antaganden som oundvikligen öka antalet iterationer av sökningen, och därmed också komplexiteten i att bryta .

AES

Attack mot 4-runds chiffer

Nyckelpunkterna för bytematriskryptering är icke-linjär transformation, radförskjutning, kolumntransformation, tillägg av text (mellanbytematris) med rund nyckelmatris.

Tänk på en klartext på sexton bytes . Låt kryptoanalytikern ha till sitt förfogande 256 chiffertexter med följande egenskap: de erhålls från bytematriser där alla utom en byte är lika i uppsättningen av dessa chiffertexter. På grund av deras antal kan vi säga att en "ojämn" byte kommer att anta alla möjliga värden på en given uppsättning. Således kan vi gå till ovanstående notation:

Initialtillstånd:

$\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}}$

Tänk på tillståndet för texten efter varje omgång:

Icke-linjär konvertering på grund av bijektivitet ändrar inte typen av byte, bara värdena för enskilda texter.
Radförskjutningen påverkar inte 1:a raden, resten skiftas utan att integralen ändras.
Kolumnkonvertering gör att varje resulterande byte är beroende av alla 4 byte i den ursprungliga kolumnen, men återigen, på grund av operationens bijeektivitet, får vi att varje byte i kolumnen bara kommer att anta vart och ett av dess värden en gång.
Tillägg med en nyckel kommer inte att ändra bytetyperna.

Så, efter första omgången:

Efter första omgången:

$\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}}$

Radförskjutning fördelar 1 byte i varje kolumn med typ . $\mathcal{A}$
Som i omgång 1, om det finns en byte i kolumnen och resten är , då konverteras alla byte i kolumnen till . Alla fyra kolumnerna konverteras på detta sätt. $\mathcal{A}$ ${\mathcal {C}}$ $\mathcal{A}$

Efter andra omgången:

$\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}$

Med hjälp av resultatet av satsen som beskrivs i teoriavsnittet får vi värdena för integralerna i varje byte ${\mathcal {S}}=0$

Efter den tredje omgången :

{\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}$

Eftersom det i den sista omgången inte förekommer någon kolumntransformation (enligt AES-specifikationen), och de återstående transformationerna konverteras till , så ändras inte värdet på integralen för fyrrundsschemat, som ett resultat av den sista omgången upp till stadiet av binär addition med en rund nyckel. I det här fallet återstår bara att varje byte antar värdet av motsvarande byte för rundtangenten, hämtar den uppskattade texten för den 3:e omgången och kontrollerar om integralen för motsvarande block är lika med noll. Om den är lika, kan den runda nyckelbyten anses hittad. $\mathcal{A}$ $\mathcal{A}$

Expansioner efter antal omgångar

Schemat kan utökas till ett schema med sju omgångar genom att överväga vad transformationen av integralen beror på en viss byte. Men även i fallet med 7 omgångar är antalet iterationer som krävs högt, i det här fallet letas länkarna mellan rundningsnycklarna genom att analysera kodgenereringsschemat. [5]

Förbättringar av kryptografresurser

Avsevärt minska tiden det tar att söka efter nycklar, på grund av den speciella organisationen av sökvillkoren, med hjälp av tre-byte vektorer, tillåter införandet av den så kallade partiella summan. En sådan modifiering för ett sexrunda chiffer minskar kraften i uppräkningen från till . Ett annat tillvägagångssätt är att använda det faktum att integralen över set med olika också försvinner efter den eftertraktade tredje ronden. Denna metod kräver en enorm mängd minnesresurser och innehav av en mycket stor bas av klartext - chiffertext. [6] $2^{{72}}$ $2^{{44}}$ ${\mathcal {C}}$

Med hjälp av delsummor är det möjligt att implementera ett hack av systemet med åtta rundor, men komplexiteten i detta hack är ännu större än den för uttömmande uppräkning .

Square

Den grundläggande attacken på Square-chifferet är praktiskt taget densamma som attacken i fyra rundor på AES, den låter dig också utöka antalet omgångar. Den kanske enda betydande skillnaden är närvaron av den första omgången av kryptering och, som ett resultat, två metoder för expansion (en mot den sista omgången, den andra mot den första). Utvecklarna av chifferet, medan de undersökte det, kunde bygga en attack på sex-runders kryptering .

Följande resultat har publicerats [7] :

Attacker på Square:

Ge sig på	Antal öppna texter	Tid	Minneskostnader
För 4 omgångar	$2^{{9}}$	$2^{{9}}$	Få
För 5 omgångar på 1:a sättet	$2^{11}$	$2^{40}$	få
För 5 omgångar på 2:a sättet	$2^{32}$	$2^{40}$	$2^{32}$
För 6 omgångar	$2^{32}$	$2^{{72}}$	$2^{32}$

Anteckningar

↑ Herstein, Ämnen i Algebra, 2:a upplagan, 1975, sidan 116
↑ Dolgov, Golovashich, Ruzhentsev. "Analys av kryptografisk styrka hos Tornado-chifferet" (2003), s. 7
↑ Lars Knudsen (2001). "Integral Cryptanalysis (Extended Abstract), s. 118"
↑ Lars Knudsen (1994). "Trunkerade och högre ordningsdifferentialer"
↑ Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner och Doug Whiting. "Improved Cryptanalysis of Rijndael" (2001), s. 2-3
↑ Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner och Doug Whiting. "Improved Cryptanalysis of Rijndael" (2001), s. 4-7
↑ Joan Daemen, Lars Knudsen, Vincent Rijmen. "The Block Chipher Square" (1997), s. 15

Länkar

Lars Knudsen och David Wagner. Integral kryptoanalys (Utökad sammanfattning) (neopr.) . – 2003.
Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner och Doug Whiting. Förbättrad kryptoanalys av Rijndael (neopr.) . - 2001. Arkiverad den 8 januari 2009. Arkiverad 8 januari 2009 på Wayback Machine
Joan Daemen, Lars Knudsen, Vincent Rijmen (januari 1997). Block Cipher Square (PDF) . Fjärde internationella workshopen om snabb mjukvarukryptering (FSE '97), volym 1267 av föreläsningsanteckningar i datavetenskap. Haifa: Springer-Verlag. pp. 149-165.