Criptanaliza diferențială

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 3 ianuarie 2020; verificările necesită 5 modificări .

Criptanaliza diferențială este o metodă de criptoanaliza a cifrurilor bloc simetrice (și a altor primitive criptografice , în special, funcțiile hash și cifrurile de flux ).

Criptanaliza diferențială se bazează pe studiul transformării diferențelor dintre valorile criptate în diferite runde de criptare . Ca diferență, de regulă, se utilizează operația de însumare pe biți modulo 2 , deși există atacuri cu calculul diferenței modulo . Este un atac statistic. Aplicabil pentru spargerea DES , FEAL și a altor cifruri, de regulă, dezvoltate mai devreme de începutul anilor 90. Numărul de runde de cifruri moderne ( AES , Camellia etc.) a fost calculat ținând cont de securitate , inclusiv de criptoanaliza diferențială. $2^{32}$

Istorie

Criptanaliza diferențială a fost propusă în 1990 de experții israelieni Eli Biham și Adi Shamir pentru a sparge criptosisteme precum DES. În munca lor, ei au arătat că algoritmul DES s-a dovedit a fi destul de rezistent la această metodă de criptoanaliza și orice cea mai mică modificare a structurii algoritmului îl face mai vulnerabil.

În 1994, Don Coppersmith de la IBM a publicat un articol [1] în care afirmă că metoda de criptoanaliza diferențială era cunoscută de IBM încă din 1974, iar unul dintre obiectivele dezvoltării DES a fost protejarea împotriva acestei metode. IBM avea secretele sale. Coppersmith a explicat:

Designul a profitat de anumite metode criptoanalitice, în special metoda „criptanaliza diferențială”, care nu a fost publicată în literatura de specialitate. După discuții cu NSA , s-a decis că dezvăluirea procesului de proiectare ar dezvălui și o metodă de criptoanaliza diferențială a cărei putere ar putea fi folosită împotriva multor cifruri. Acest lucru, la rândul său, ar reduce avantajul SUA față de alte țări în domeniul criptografiei.

DES sa dovedit a fi rezistent din punct de vedere criptografic la criptoanaliza diferențială, spre deosebire de alte cifruri. Deci, de exemplu, cifrul FEAL s -a dovedit a fi vulnerabil . Un FEAL-4 cu 4 runde poate fi spart cu doar 8 texte clare alese și chiar și un FEAL cu 31 de runde este vulnerabil la atac.

DES Hacking Scheme

În 1990, Eli Biham și Adi Shamir , folosind criptoanaliza diferențială, au găsit o modalitate de a sparge DES care era mai eficientă decât forța brută. Lucrând cu perechi de texte cifrate ale căror texte clare au anumite diferențe, oamenii de știință au analizat evoluția acestor diferențe pe măsură ce textele clare trec prin etapele DES .

Analiza unei singure runde

Metoda de bază a criptoanalizei diferențiale este atacul de text simplu ales adaptiv , deși are o extensie pentru atacul de text clar . Pentru a efectua atacul, se folosesc perechi de texte clare legate printr-o anumită diferență. Pentru sistemele DES și asemănătoare DES, este definit ca SAU exclusiv (XOR) . La decriptare, este necesară doar valoarea perechilor de text cifrat corespunzătoare.

Diagrama prezintă funcția Feistel . Fie și o pereche de intrări care diferă cu . Ieșirile corespunzătoare acestora sunt cunoscute și egale cu și , diferența dintre ele este . Permutația cu extensie și -bloc sunt de asemenea cunoscute, prin urmare, și sunt , de asemenea, cunoscute . și sunt necunoscute, dar știm că diferența lor este , deoarece diferențele c și sunt neutralizate. Singurele elemente neliniare din circuit sunt blocurile. Pentru fiecare -bloc, puteți stoca un tabel, ale cărui rânduri sunt diferențele la intrarea blocului -, coloanele sunt diferențele la ieșire, iar la intersecție - numărul de perechi care au dat intrare și ieșire. diferențe și undeva unde să stocați aceste perechi în sine. $X$ $X'$ $\Delta X$ $Y$ $tu$ $\Delta Y$ $P$ $\Delta A$ $\Delta C$ $B$ $B'$ $\Delta A$ $XOR\ K_{{i}}$ $A$ $A'$ $S$ $S$ $S$

Deschiderea tastei rotunde se bazează pe faptul că, pentru o anumită valoare, nu toate valorile sunt la fel de probabile, dar combinația dintre și ne permite să asumăm valorile și . Pentru cunoscut și acest lucru ne permite să determinăm . Cu excepția tuturor informațiilor necesare pentru ultima rundă, sunt conținute în perechea finală de texte cifrate. $\Delta A$ $\Delta C$ $\Delta A$ $\Delta C$ $A\ XOR\ K_{{i}}$ $A'\ XOR\ K_{{i}}$ $A$ $A'$ $K_{{i}}$ $\Delta C$

După determinarea cheii rotunde pentru ultimul ciclu, devine posibilă decriptarea parțială a textelor cifrate și apoi utilizarea metodei de mai sus pentru a găsi toate cheile rotunde.

Caracteristici

Pentru a determina posibilele diferențe ale textelor cifrate primite la runda a I-a, se folosesc caracteristicile rotunde .

Caracteristica N-rundă este un tuplu , compus din diferențe de text simplu , diferențe de text cifrat și un set de diferențe în rezultatele de criptare intermediare pentru fiecare rundă trecută. $\Omega \ =\ (\Omega _{{P)),\Omega _({\Lambda )),\Omega _{{T)))$ $\Omega _{{P}}$ $\Omega _{{T}}$ $\Omega _{{\Lambda }}\ =\ (\Lambda _{{1}},\Lambda _{{2}},\ ...\ ,\Lambda _{{n}})$

Caracteristicii i se atribuie o probabilitate egală cu probabilitatea ca o pereche aleatorie de texte clare cu o diferență ca urmare a criptării cu chei aleatoare să aibă diferențe rotunde și diferențe de text cifrat care se potrivesc cu cele specificate în caracteristică. O pereche de texte deschise corespunzătoare caracteristicii se numește „corect” . Perechile de texte deschise care nu corespund caracteristicii sunt numite „incorecte” . $\Omega _{{P}}$

Să luăm valoarea diferenței de texte la ieșirea penultimului ciclu, utilizată la determinarea posibilei subchei a ultimei runde, . Într-un astfel de caz, perechea „corectă” de texte determină cheia corectă, în timp ce perechea „greșită” determină o cheie aleatorie. $\Delta A=\Omega _{{T}}$

Într-un atac, mai multe caracteristici sunt de obicei utilizate simultan. Structurile sunt utilizate în mod obișnuit pentru a conserva memoria.

Un cvartet este o structură de patru texte, care conține simultan două perechi de texte pentru două caracteristici diferite. Vă permite să salvați 1/2 din memorie pentru texte simple.
Octet - o structură de 16 texte care conțin 8 perechi, câte 4 pentru fiecare caracteristică. Vă permite să salvați 2/3 din memorie pentru texte simple.

Raportul semnal-zgomot

Pentru toate opțiunile cheie, puteți crea contoare, iar dacă vreo pereche sugerează această opțiune ca o cheie validă, vom crește contorul corespunzător. Cheia care corespunde celui mai mare numărător are o mare probabilitate de a fi corectă.

Pentru schema noastră de calcul, raportul dintre numărul de perechi corecte S și valoarea medie a contorului N va fi numit raport semnal-zgomot și va fi notat cu . $S/N$

Pentru a găsi cheia corectă și a vă asigura că sunt prezente perechile corecte, trebuie să:

caracteristică cu probabilitate suficientă;
suficiente perechi.

Numărul de perechi necesare este determinat de:

probabilitatea caracteristicii;
numărul de biți cheie (biții pe care vrem să-i definim);
nivelul de identificare a perechilor eronate (perechile nu contribuie la contoare, deoarece acestea sunt aruncate mai devreme).

Lăsați dimensiunea cheii să fie k biți, atunci avem nevoie de contoare. În cazul în care un: $2^k$

m este numărul de perechi utilizate;
$\alfa$ - adunarea medie la contoare pentru o pereche;
$\beta$ este raportul dintre perechile care contribuie la contoare la toate perechile (inclusiv cele aruncate),

atunci valoarea medie a contorului N este:

N={\frac {m\cdot \alpha \cdot \beta }{2^{{k))))

Dacă este probabilitatea caracteristicii, atunci numărul de perechi corecte S este egal cu: $p$

S=m\cdot p.

Atunci raportul semnal-zgomot este:

S/N={\frac {m\cdot p}{m\cdot \alpha \cdot \beta /2^{{k))))={\frac {2^{{k))\cdot p}{ \alpha \cdot \beta }}.

Rețineți că pentru schema noastră de proiectare, raportul semnal-zgomot nu depinde de numărul total de perechi. Numărul de perechi valide necesare este, în general, o funcție a raportului semnal-zgomot . Sa stabilit experimental că dacă S/N=1-2 , sunt necesare 20-40 de apariții ale perechilor corecte. Dacă raportul este mult mai mare, atunci chiar și 3-4 perechi corecte pot fi suficiente. În sfârșit, când este mult mai mic, numărul de perechi necesar este enorm.

S/N	Numărul de perechi necesar
mai putin de 1	Veliko
1-2	20-40
mai mult de 2	3-4

Eficiența hackurilor

Odată cu creșterea numărului de runde, complexitatea criptoanalizei crește, dar rămâne mai mică decât complexitatea căutării exhaustive atunci când numărul de cicluri este mai mic de 16.

Dependență de numărul de runde
Numărul de runde	Complexitatea atacului
$patru$	$2^{{4}}$
$6$	$2^{{8}}$
$opt$	$2^{16}$
$9$	$2^{26}$
$zece$	$2^{{35}}$
$unsprezece$	$2^{{36}}$
$12$	$2^{43}$
$13$	$2^{{44}}$
$paisprezece$	$2^{{51}}$
$cincisprezece$	$2^{{52}}$
$16$	$2^{{58}}$

Designul S-box-urilor afectează, de asemenea, în mod semnificativ eficiența criptoanalizei diferențiale. Cutiile DES S, în special, sunt optimizate pentru rezistența la atac.

Comparație cu alte metode

Consultați Atacurile cunoscute asupra DES

Criptanaliza diferențială și sisteme asemănătoare DES

În timp ce DES complet cu 16 runde a fost proiectat inițial pentru a fi rezistent la criptoanaliza diferențială, atacul s-a dovedit de succes împotriva unui grup larg de cifruri asemănătoare DES [2] .

Lucifer , scurtat la opt runde, se întrerupe folosind mai puțin de 60 de texte cifrate.
FEAL -8 este spart folosind mai puțin de 2000 de texte cifrate.
FEAL-4 este spart folosind 8 texte cifrate și un text simplu .
FEAL-N și FEAL-NX pot fi sparte cu . $N\leq 31$

Criptanaliza diferențială este aplicabilă și împotriva funcțiilor hash .

După publicarea lucrărilor despre criptoanaliza diferențială la începutul anilor 1990, cifrurile ulterioare au fost concepute pentru a fi rezistente la acest atac.

Dezavantajele metodei

Metoda criptoanalizei diferenţiale este în mare măsură o realizare teoretică. Aplicarea sa în practică este limitată de cerințe mari de timp și volum de date.

Fiind în primul rând o metodă de atac aleasă în text simplu, criptoanaliza diferențială este dificil de implementat în practică. Poate fi folosit pentru a ataca cu text clar cunoscut, dar în cazul unui DES cu 16 runde, acest lucru îl face chiar mai puțin eficient decât un atac cu forță brută.

Metoda necesită o cantitate mare de memorie pentru a stoca cheile candidate. Eficiența metodei depinde, de asemenea, puternic de structura cutiilor S ale algoritmului piratat.

Vezi și

Note

↑ Calămarul, Don. Standardul de criptare a datelor (DES) și puterea sa împotriva atacurilor // IBM Journal of Research and Development : jurnal. - 1994. - Mai ( vol. 38 , nr. 3 ). — P. 243 . - doi : 10.1147/rd.383.0243 . (este necesar abonament)
↑ Biham E. , Shamir A. Criptoanaliza diferențială a criptosistemelor asemănătoare DES . - 1990. - P. 7 .

Literatură

Bruce Schneier. Criptografia aplicată. Protocoale, algoritmi, texte sursă în limbaj C.
Panasenko, S. „Metode moderne pentru spargerea algoritmilor de criptare, partea 3” . Chief Information Officer - 2006 . Arhivat pe 15 ianuarie 2010 la Wayback Machine
Biham E. , Shamir A. Criptoanaliza diferențială a standardului de codificare a datelor.
Biham E. , Shamir A. Criptoanaliza diferențială a criptosistemelor asemănătoare DES (engleză) . — 1990.