Criptanaliza diferențială

Criptanaliza diferențială este o formă generală de criptanaliză , aplicabilă în principal pentru blocarea cifrelor, dar și pentru fluxurile de cifrări și funcțiile hash criptografice . În sensul cel mai larg al termenului, criptanaliza diferențială a unei funcții criptografice este studiul modului în care diferențele din datele furnizate la intrarea funcției pot afecta diferențele rezultate la ieșirea sa. În cazul unui cifru de bloc, se referă la un set de tehnici pentru a urmări diferențele din rețeaua transformărilor pe care algoritmul le operează în timpul execuției sale, descoperind unde cifrul prezintă comportamente non- aleatorii , permițând exploatarea acestor proprietăți pentru recuperare cheia secretă .

Istorie

Descoperirea criptanalizei diferențiale este în general atribuită lui Eli Biham și Adi Shamir la sfârșitul anilor 1980 , care au publicat o serie de atacuri împotriva diferitelor cifrări bloc și funcții hash, inclusiv o slăbiciune teoretică a DES ^[1] .

James Bamford, un jurnalist și scriitor american cu un interes deosebit în afacerile guvernamentale, a scris în cartea sa din 1982 The Puzzle Palace că DES a fost surprinzător de rezistent la criptanaliza diferențială, în sensul că chiar și mici modificări aduse algoritmului l-ar face susceptibil la atac. . Acest lucru a sugerat că proiectanții IBM care au creat DES erau conștienți de această tehnică de atac încă din anii șaptezeci ^[2] .

În 1994, Don Coppersmith , membru al echipei originale de dezvoltare DES, a publicat o lucrare în care afirma că criptanaliza diferențială a fost cunoscută de IBM încă din 1974 și că unul dintre obiectivele urmărite în timpul scrierii DES a fost tocmai acela de a o face sigură împotriva un astfel de atac ^[3] .

Potrivit scriitorului Steven Levy , IBM a descoperit singură criptanaliza diferențială, iar Agenția Națională de Securitate (care a văzut DES înainte de publicarea sa) era evident conștientă de ea, atât de mult încât a sfătuit IBM să o păstreze secretă. el însuși a recunoscut la Levy:

„După unele discuții cu ANS, s-a decis că dezvăluirea considerațiilor structurii DES ar dezvălui criptanaliza diferențială, o tehnică foarte puternică care ar putea fi folosită împotriva multor cifre. Acest lucru ar fi slăbit avantajul criptografic al Statelor Unite ale Americii față de alte țări .. "

În cadrul IBM, criptanaliza diferențială a fost cunoscută sub numele de atac T sau „atac de gâdilare” ^[4] .

În timp ce DES a fost conceput cu intenția de a rezista criptanalizei diferențiale, multe alte cifre contemporane sunt încă vulnerabile la aceasta. Una dintre primele ținte ale acestui atac a fost cifrarea cu blocuri FEAL : versiunea originală cu 4 treceri a algoritmului (FEAL-4) poate fi piratată folosind doar 8 text clar ales și, de asemenea, o versiune cu 31 de treceri a FEAL este sensibilă la acest atac.

Mecanisme de atac

Analiza criptografică diferențială este, de obicei, un atac în format text ales , ceea ce înseamnă că atacatorul trebuie să poată obține mesajele în text clar criptate la alegere. Schema poate cripta cu succes DES cu utilizarea de 2 ⁴⁷ plaintext ales. Există, totuși, unele extensii care ar permite utilizarea unui text clar cunoscut sau a unui atac numai cu text cifrat .

Metoda de bază folosește perechi de text simplu legate de o constantă numită diferență : diferența poate fi definită în diferite moduri, dar cea mai utilizată operație este, în general, exclusiv OR (XOR) . Atacatorul poate calcula diferențele textelor cifrate corespunzătoare, sperând să intercepteze motive statistice în distribuția lor. Perechea de diferențe rezultată se numește diferențial . Proprietățile lor statistice depind de natura casetelor S utilizate pentru criptare, astfel încât atacatorul analizează diferențialele $(\Delta _{X},\Delta _{Y})$ ${\ displaystyle (\ Delta _ {X}, \ Delta _ {Y})}$ ${\ displaystyle (\ Delta _ {X}, \ Delta _ {Y})}$ , unde este $\Delta _{Y}=S(X)\oplus S(X\oplus \Delta _{X})$ ${\ displaystyle \ Delta _ {Y} = S (X) \ oplus S (X \ oplus \ Delta _ {X})}$ ${\ displaystyle \ Delta _ {Y} = S (X) \ oplus S (X \ oplus \ Delta _ {X})}$ ( $\oplus$ ${\ displaystyle \ oplus}$ $\ oplus$ denotă un OR exclusiv) este valabil pentru fiecare dintre casetele S. $S.$ ${\ displaystyle S}$ $S.$ .

În atacul de bază, se așteaptă ca o diferență particulară în textul cifrat să fie destul de frecventă; în acest fel, cifrul se poate distinge de întâmplare . Variantele mai sofisticate ale atacului vă permit să preluați cheia mai repede decât căutarea exhaustivă a tuturor combinațiilor posibile.

În cea mai simplă formă de recuperare a cheii prin criptanaliză diferențială, un atacator solicită textul cifrat pentru un număr mare de perechi de text simplu și apoi presupune că diferențialul se menține pentru cel puțin r-1 trece, unde r este numărul total de treceri ale cifrului . Atacatorul deduce apoi ce sub-chei (pentru trecerea finală) sunt posibile ținând cont de diferența dintre blocuri înainte ca ultima trecere să fie finalizată: când sub-cheile sunt scurte, acest lucru se poate face într-un mod simplu, prin decriptare exhaustiv perechile de text cifrat cu o trecere a cifrului și fiecare sub-cheie posibilă. Când o subcheie a fost montată ca subcheie potențială mult mai des decât orice altă cheie, atunci se presupune că este subcheia corectă.

Pentru un anumit cifru, diferența de intrare trebuie selectată cu atenție pentru ca atacul să aibă succes. Apoi se efectuează o analiză exactă a structurii interne a algoritmului: metoda standard este de a urmări o cale de diferențe foarte probabile prin diferiți pași ai procesului de criptare, numită caracteristică diferențială .

Deoarece criptanaliza diferențială a devenit publică, a devenit, de asemenea, o preocupare de bază a criptografilor (cei care proiectează algoritmi criptografici): de fapt, noile sisteme sunt așteptate să fie însoțite de o analiză care sugerează că algoritmul este rezistent la acest tip de atac și pentru mulți dintre ei, inclusiv pentru cunoscutul AES , s-a dovedit matematic că sunt.

Notă

^ Eli Biham, Adi Shamir: diferentiala criptanaliza Full 16- a rundă DES Filed pe 05 aprilie 2005 în Internet Archive . - CRYPTO '92
^ James Bamford: The Puzzle Palace: a Report on America's Most Secret Agency ( 1982 ) - Houghton Mifflin - ISBN 0-14-006748-5
^ Don Coppersmith: Standardul de criptare a datelor (DES) și puterea sa împotriva atacurilor Arhivat 25 martie 2009 la Internet Archive . - IBM Journal of Research and Development, vol. 38, p. 243 - 1994
^ Matt Blaze: Re: Reverse Engineering and the Clipper chip " - grup de știri sci.crypt - 15.08.1996

Elemente conexe

Tipuri particulare de criptanaliză diferențială

linkuri externe

Un tutorial despre criptanaliza diferențială (și liniară) , pe engr.mun.ca.
Selecția de legături privind criptanaliza diferențială colectată de Helger Lipmaa , la research.cyber.ee . Adus la 20 noiembrie 2008 (arhivat din original la 29 ianuarie 2009) .
O descriere a atacului aplicată DES , la home.earthlink.net . Adus la 20 noiembrie 2008 (arhivat din original la 19 octombrie 2007) .
Eli Biham, diapozitive din „Cum să faci o diferență: istoria timpurie a criptanalizei diferențiale” - 850 KiB - Criptare rapidă a software-ului 2006

Portal de criptografie

Portal de securitate IT

[1] Eli Biham, Adi Shamir: diferentiala criptanaliza Full 16- a rundă DES Filed pe 05 aprilie 2005 în Internet Archive . - CRYPTO '92

[2] James Bamford: The Puzzle Palace: a Report on America's Most Secret Agency ( 1982 ) - Houghton Mifflin - ISBN 0-14-006748-5

[3] Don Coppersmith: Standardul de criptare a datelor (DES) și puterea sa împotriva atacurilor Arhivat 25 martie 2009 la Internet Archive . - IBM Journal of Research and Development, vol. 38, p. 243 - 1994

[4] Matt Blaze: Re: Reverse Engineering and the Clipper chip " - grup de știri sci.crypt - 15.08.1996

[1]

[2]

[3]

[4]