Criptanaliza integrală

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 15 iunie 2014; verificările necesită 14 modificări .

Criptanaliza integrală este o metodă de criptoanaliza care combină o serie de atacuri asupra algoritmilor criptografici bloc simetric . Spre deosebire de criptoanaliza diferențială , care ia în considerare efectul unui algoritm asupra unei perechi de texte clare, criptoanaliza integrală implică studiul mapării unui set de texte clare într-un text cifrat . Aplicat pentru prima dată în 1997 de către Lars Knudsen .

Istorie

În articolele științifice, termenul de „ criptanaliza integrală ” a fost propus în 1999 în publicația Integral cryptanalysis of SAFER + (engleză) . Conceptul în sine a fost exprimat pentru prima dată de Lars Knudsen când a analizat cifrul Square în 1997. Din acest motiv, termenul „Square-like attacks” sau pur și simplu „Square-atack” este adesea folosit în literatură. Pentru 2011, nu există un progres revoluționar în ceea ce privește atacul Square în domeniul criptoanalizei integrale.

Baza teoretică a metodei

Fie un grup abelian finit . Apoi, luând blocul 1 ca ansamblu de texte cifrate posibile (în cazul general, acesta este determinat de alfabetul ales și dimensiunea blocului), putem considera un grup de forma următoare, cu aceeași operațiune de grup: . Mulțimea spațiului n-dimensional astfel construit este mulțimea tuturor textelor cifrate posibile. În consecință, elementul spațiu este un anumit text cifrat, componentele acestui vector sunt valoarea blocurilor de text cifrat. Presupunem că suma vectorilor este un vector ale cărui componente sunt egale cu sumele componentelor corespunzătoare ale termenilor. Integrala multime este suma tuturor vectorilor incluși în : . $(G,+)$ $G$ $G$ $G^{n}=G\times ...\times G$ $v=(v_{1},...,v_{n}),v\in G$ $S\subseteq G$ $S$ $\int S=\sum _{v\in S}v$

Criptanaliza integrală de succes ar trebui să reducă numărul de iterații de estimare a cheii . Pentru a face acest lucru, încercăm să grupăm vectorii de text simplu, astfel încât, pe baza grupării, să poată fi găsite orice tipare. Este convenabil să studiezi algoritmii bazați pe următoarea partiție:

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

unde este un număr fix, (vector) $i$ $c,c'=const\in G$

Următoarea teoremă [1] joacă un rol cheie :

Fie un grup abelian finit . Notați , iar ordinea lui g este egală cu 1 sau 2. Definiți . Apoi . În plus, $(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$

Este de remarcat un rezultat important al teoremei: dacă ), atunci , deoarece ${\displaystyle G=GF(2^{s))$ $s(G)=0$ $H=\{0\}$

Remarcăm o serie de notații care sunt adesea folosite în publicațiile despre atacuri bazate pe criptoanaliza integrală:

Dacă se notează i -a componentă a integralei , aceasta înseamnă că în toți termenii sumei integrale, i -a componentă este aceeași ${\mathcal {C}}$
În mod similar , arată că componenta corespunzătoare diferă în toți termenii. $\mathcal{A}$
$\mathcal{S}$ arată că componenta dată a integralei poate fi prezisă.
? arată că este imposibil de prezis componenta integralei.

Principiul general al căutării vulnerabilităților pe exemplul rețelei Feistel

Luați în considerare modul în care integralele peste S se schimbă dacă toate elementele acestei mulțimi sunt alimentate la intrarea rețelei Feistel. Fie S un set de texte cifrate în care toate blocurile corespunzătoare, cu excepția unuia, sunt aceleași (pot diferi unul de celălalt). În exemplu, textul cifrat este de 16 blocuri dispuse în 2 linii. Pentru cifrurile precum AES , este de asemenea important să se ia în considerare faptul că textul cifrat este dat de o matrice, deoarece folosesc operații diferite pentru rânduri și coloane. Luați în considerare efectul celulelor Feistel în etape:

Presupunând că celulele Feistel produc mapări bijective , este evident că aceleași blocuri dintre textele cifrate vor intra în aceleași blocuri între textele cifrate convertite (cu toate acestea, este aproape sigur că valorile vechi și noi vor diferi). Astfel, putem scrie că prima celulă a mapat o mulțime dintr-o clasă de mulțimi cu componente identice în set cu o mulțime din aceeași clasă.
Deoarece valoarea tuturor blocurilor la ieșirea unei celule Feistel depinde de valoarea fiecărui bloc la intrare, impactul unui singur bloc modifică fiecare bloc al textului cifrat la ieșire. Astfel, valorile componentelor integralei nu devin mai mult decât previzibile [2] . $\mathcal{A}$
Deoarece la intrarea pentru fiecare bloc aparținând textului cifrat de intrare, setul de valori nu coincide cu setul de valori posibile de bloc, suma lor poate să nu fie păstrată în timpul transformării bijective, astfel încât orice poate fi obținut la ieșire din celula.

Chiar și aplicabil exemplului descris, este posibil să se reducă semnificativ numărul de iterații pentru selecție sau să se furnizeze informații suplimentare pentru diferite tipuri de criptoanaliza.

Comparație cu criptoanaliza diferențială

Ca și în cazul criptoanalizei diferențiale, atacurile bazate pe integrale pot fi clasificate ca un tip de atac bazat pe text simplu ales adaptiv .

Lars Knudsen a remarcat, de asemenea, asemănarea cu atacul diferențial trunchiat , care are ideea de a lua în considerare comportamentul nu a întregii diferențe, ca în criptoanaliza diferențială, ci a părților sale. Mai mult, criptoanaliza integrală are superioritate în capacitatea sa de a considera a treia stare a rezultatului - , în timp ce atacul diferenţialelor trunchiate distinge doar două. $\mathcal{S}$

Pentru a ataca diferențialele de ordin înalt , puteți vedea că în câmpul Galois, expresia pentru diferența de ordin al s -lea este similară cu integrala [3] . Astfel, se poate încerca să generalizeze unele metode de criptoanaliza diferențială la cele integrale. $GF(2^{s})$

Este de remarcat faptul că atacurile diferențialelor trunchiate și diferențialele de ordin înalt au fost, de asemenea, publicate pentru prima dată de Lars Knudsen în 1994, tot la conferința FSE [4]

Atacuri notabile

Atacurile asupra cifrurilor asemănătoare AES ( Rijndael , SQUARE , CRYPTON ) pot fi generalizate prin primul pas - luarea în considerare a integralelor după a treia rundă de criptare. Pașii suplimentari sunt încercările de îmbunătățire a atacului prin creșterea numărului de runde, folosind diverse ipoteze care inevitabil crește numărul de iterații ale căutării, prin urmare și complexitatea ruperii.

AES

Atacul asupra cifrului cu 4 runde

Punctele cheie ale criptării matricei de octeți sunt transformarea neliniară, deplasarea rândurilor, transformarea coloanei, adăugarea de text (matricea de octeți intermediară) cu matrice de cheie rotundă.

Luați în considerare un text simplu de șaisprezece octeți . Fie ca criptoanalistul să aibă la dispoziție 256 de texte cifrate cu următoarea proprietate: ele sunt obținute din matrice de octeți în care toți octeții cu excepția unuia sunt aceiași în mulțimea acestor texte cifrate. Datorită numărului lor, putem spune că un octet „inegal” va prelua toate valorile posibile pe un anumit set. Astfel, putem merge la notația de mai sus:

Stare initiala:

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

Luați în considerare starea textului după fiecare rundă:

Conversia neliniară din cauza bijectivității nu schimbă tipul de octet, ci doar valorile pentru texte individuale.
Deplasarea rândului nu afectează primul rând, restul sunt deplasați fără a schimba integrala.
Conversia coloanei face ca fiecare octet rezultat să fie dependent de toți cei 4 octeți ai coloanei originale, dar din nou, datorită bijectivității operației, obținem că fiecare octet al coloanei va prelua fiecare dintre valorile sale o singură dată.
Adăugarea cu o cheie nu va schimba tipurile de octeți.

Deci, după prima rundă:

După prima rundă:

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

Deplasarea rândului distribuie 1 octet în fiecare coloană cu tipul . $\mathcal{A}$
Ca și în runda 1, dacă există un octet în coloană și restul sunt , atunci toți octeții din coloană sunt convertiți în . Toate cele 4 coloane sunt convertite în acest mod. $\mathcal{A}$ ${\mathcal {C}}$ $\mathcal{A}$

După a doua rundă:

După a 2-a rundă:

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

Folosind rezultatul teoremei descrise în secțiunea de teorie, obținem valorile integralelor din fiecare octet ${\mathcal {S}}=0$

După runda a 3-a ,:

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

Deoarece în ultima rundă nu există o transformare a coloanei (conform specificației AES), iar transformările rămase sunt convertite în , atunci pentru schema cu patru runde, ca urmare a ultimei runde, valoarea integralei nu se modifică până la stadiul de adăugare binară cu o cheie rotundă. În acest caz, tot ce rămâne este ca fiecare octet să-și asume valoarea octetului corespunzător cheii rotunde, să obțină textul estimat al rundei a 3-a și să verifice dacă integrala blocului corespunzător este egală cu zero. Dacă este egal, atunci octetul cheie rotund poate fi considerat găsit. $\mathcal{A}$ $\mathcal{A}$

Extinderi după numărul de runde

Schema poate fi extinsă la o schemă cu șapte runde, luând în considerare ce depinde transformarea integralei de un anumit octet. Totuși, chiar și în cazul a 7 runde, numărul de iterații necesar este mare, în acest caz legăturile dintre cheile rotunde sunt căutate prin analiza schemei de generare a codului. [5]

Îmbunătățiri ale resurselor criptografului

Reduceți semnificativ timpul necesar pentru căutarea cheilor, datorită organizării speciale a condițiilor de căutare, folosind vectori de trei octeți, permite introducerea așa-numitei sume parțiale. O astfel de modificare pentru un cifru cu șase runde reduce puterea de enumerare de la la . O altă abordare este să folosiți faptul că integrala peste seturi cu altele diferite dispare și după râvnita rundă a treia. Această metodă necesită o cantitate imensă de resurse de memorie și deținerea unei baze foarte mari de text simplu - text cifrat. [6] $2^{{72}}$ $2^{{44}}$ ${\mathcal {C}}$

Folosind sume parțiale, este posibil să se implementeze un hack al sistemului cu opt runde, dar complexitatea acestui hack este chiar mai mare decât cea a enumerarii exhaustive .

Patrat

Atacul de bază asupra cifrului Square este practic același cu atacul în patru runde pe AES, de asemenea, vă permite să extindeți numărul de runde. Poate singura diferență semnificativă este prezența primei runde de criptare și, ca urmare, două metode de extindere (una spre ultima rundă, cealaltă către prima). Dezvoltatorii cifrului, în timp ce îl cercetau, au reușit să construiască un atac asupra criptării în șase runde .

Au fost publicate următoarele rezultate [7] :

Atacurile asupra pătratului:

Atac	Numărul de texte deschise	Timp	Costul memoriei
Pentru 4 runde	$2^{{9}}$	$2^{{9}}$	Puțini
Pentru 5 runde în primul mod	$2^{11}$	$2^{40}$	puţini
Pentru 5 runde în a 2-a cale	$2^{32}$	$2^{40}$	$2^{32}$
Pentru 6 reprize	$2^{32}$	$2^{{72}}$	$2^{32}$

Note

↑ Herstein, Topics in Algebra, ed. a 2-a, 1975, pag. 116
↑ Dolgov, Golovașici, Rujnțev. „Analiza puterii criptografice a cifrului Tornado” (2003), p. 7
↑ Lars Knudsen (2001). „Criptanaliză integrală (Rezumat extins), p. 118”
↑ Lars Knudsen (1994). „Diferenţiale trunchiate şi de ordin superior”
↑ Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner și Doug Whiting. „Criptanaliză îmbunătățită a lui Rijndael” (2001), pp. 2-3
↑ Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner și Doug Whiting. „Criptanaliză îmbunătățită a lui Rijndael” (2001), pp. 4-7
↑ Joan Daemen, Lars Knudsen, Vincent Rijmen. „The Block Cipher Square” (1997), p. 15

Link -uri

Lars Knudsen și David Wagner. Criptanaliză integrală (Rezumat extins) (neopr.) . — 2003.
Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner și Doug Whiting. Criptanaliză îmbunătățită a lui Rijndael (neopr.) . - 2001. Arhivat la 8 ianuarie 2009. Arhivat pe 8 ianuarie 2009 la Wayback Machine
Joan Daemen, Lars Knudsen, Vincent Rijmen (ianuarie 1997). The Block Cipher Square (PDF) . Al 4-lea Atelier internațional de criptare rapidă a software-ului (FSE '97), volumul 1267 din Note de curs în informatică. Haifa: Springer-Verlag. pp. 149-165.