Criptoanaliza

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Mașina de criptare Lorenz-SZ42

Prin criptanaliză (din grecescul kryptós , „ascuns”, și analýein , „a descompune”), sau criptanaliză , ne referim la studiul metodelor de obținere a semnificației informațiilor criptate fără a avea acces la informațiile secrete care sunt de obicei necesare pentru efectuați operațiunea. Criptoanaliza este „contrapartea” criptografiei , adică studiul tehnicilor de ascundere a unui mesaj și împreună formează criptologia , știința scrierilor ascunse.

Criptanaliza se referă nu numai la metodele de spargere a unui cifru , ci și la orice încercare de a ocoli securitatea algoritmilor criptografici și a protocoalelor criptografice, de exemplu prin utilizarea canalului lateral .

Istorie

Criptanaliza clasică

Prima pagină a manuscrisului lui Al-Kindi al secolului al IX-lea numită Manuscris pentru descifrarea mesajelor criptate

Deși termenul este relativ recent (a fost inventat de William Friedman în 1920 ), metodele de rupere a criptării și a cifrelor criptografice sunt mult mai vechi. Prima explicație scrisă cunoscută a criptanalizei datează din secolul al IX-lea și este opera geniului arab Abu Yusuf Yaqub ibn Ishaq al-Sabbah Al-Kindi (cunoscut și în Europa cu numele latinizat de Alchindus ): acesta este Manuscrisul de pe descifrarea mesajelor criptate . Acest tratat include o descriere a unei metode de analiză a frecvenței ( Ibrahim Al-Kadi , 1992-ref-3).

Analiza frecvenței este o metodă de bază pentru spargerea multor cifre clasice. În limbile naturale, anumite litere ale alfabetului apar mai frecvent decât altele. De exemplu, în italiană literele „ A ” și „ E ” sunt cele care apar cel mai frecvent în orice mesaj în format text simplu: dacă un mesaj a fost criptat cu un cifru de substituție mono-alfabetic (în care fiecare literă este pur și simplu înlocuită cu un ' altele), este sigur să presupunem că cele mai frecvente litere care apar în textul cifrat sunt candidați pentru „A” sau „E”.

În practică, analiza de frecvență se bazează foarte mult pe cunoștințele lingvistice , deoarece se bazează pe statistici , dar pe măsură ce cifrele au devenit mai complexe, matematica a devenit mai importantă în criptanaliză. Această schimbare a fost deosebit de evidentă în timpul celui de-al doilea război mondial, când încercările de a sparge cifrele Puterilor Axei au necesitat noi niveluri de rafinament matematic. De asemenea, în acel moment automatizarea a fost introdusă pentru prima dată în criptanaliză cu computerul polonez Bomba , cu utilizarea dispozitivelor de tip punch card și în Colossus , unul dintre primele computere (posibil primul computer digital electronic programabil).

Criptanaliza modernă

Replica unui computer Bomb

Procesarea automată, aplicată cu un profit mare criptanalizei în timpul celui de-al doilea război mondial, a determinat producerea de noi tehnici criptografice cu câteva ordine de mărime mai complexe decât cele anterioare. Luată în ansamblu, criptografia modernă a devenit mult mai dificilă de criptat cu sistemele de stilou și hârtie din trecut, atât de mult încât are un avantaj față de criptanaliza pură.

Istoricul David Kahn afirmă că „există multe criptosistemele astăzi, oferite de sute de furnizori de acolo, care nu poate fi încălcat prin oricare dintre metodele cunoscute de criptanaliza. De fapt, pe aceste sisteme chiar și un atac plaintext ales , în care o special mesajul text selectat este comparat cu textul cifrat echivalent, nu vă permite să preluați cheia care deblochează alte mesaje. Într-un anumit sens, deci, criptanaliza este moartă. Dar acesta nu este sfârșitul poveștii: să fii mort, ci, pentru a folosi metafora mea, există mai multe modalități de a jupui o pisică " [1] . Kahn continuă să menționeze oportunitățile crescute de interceptare , bug - ul (sau bug-urile),atacurile canalului lateral și criptografia cuantică sunt înlocuitori valabili ai semnificațiilor tradiționale ale criptanalizei.

Poate că Kahn a fost prea grăbit în a respinge criptanaliza ca fiind moartă: cifrele slabe sunt departe de a fi dispărute, iar metodele criptanalitice utilizate de agențiile de informații rămân încă în mare parte necunoscute. În domeniul academic, mulți cărturari prezintă în mod regulat noi sisteme criptografice, care sunt adesea rapid sparte: cifrul bloc Madryga , publicat în 1984, a fost găsit sensibil la atacurile numai cu text cifrat în 1998 ; FEAL-4 , propus ca înlocuitor al DES , a fost demolat de o serie de atacuri lansate de comunitatea academică, dintre care multe sunt pe deplin viabile în practică.

Chiar și în industrie, multe cifre nu sunt lipsite de puncte slabe: de exemplu, algoritmii A5 / 1 , A5 / 2 și CMEA , utilizați în tehnologia telefoniei mobile , pot fi sparte în ore, minute sau chiar în timp real folosind computerele la îndemână. mulți. În 2001 s- a demonstrat că protocolul WEP , utilizat pentru securizarea conexiunilor Wi-Fi , era nesigur și un atac legat de cheie ar putea permite recuperarea cheii în câteva ore. În 2005, s-a găsit chiar o modalitate de a sparge o conexiune securizată WEP în mai puțin de un minut [2] .

Evoluțiile din secolul al XX-lea

Telegrama Zimmermann descifrată.

De mai multe ori succesele criptanalizei au influențat istoria: capacitatea de a citi presupusele gânduri și planurile secrete ale altor oameni poate fi un avantaj decisiv, mai ales în perioade de război. De exemplu, în timpul primului război mondial , încălcarea telegramei Zimmermann a accelerat intrarea în conflictul Statelor Unite ale Americii . În cel de-al doilea război mondial, criptanaliza cifrelor germane, inclusiv a mașinii Enigma și a cifrului Lorenz , este, conform cercetătorilor, unul dintre punctele care au scurtat sfârșitul conflictului din Europa cu câteva luni (vezi ULTRA ). Statele Unite au beneficiat, de asemenea, de criptanoaliză datorită faptului că, cu aceasta, puteau decripta multe dintre comunicațiile secrete ale armatei japoneze , care erau criptate de o mașină numită PURPLE de către americani (echivalentul japonez al Enigmei germane).

Guvernele țărilor au recunoscut de mult beneficiile indubitabile ale criptanalizei în domeniul spionajului , atât militar, cât și diplomatic, și au înființat organizații dedicate în mod special încălcării codurilor și cifrelor altor națiuni, precum GCHQ britanic sau NSA SUA, organizații care sunt active și astăzi. În 2004, s-a dezvăluit știrea că Statele Unite ale Americii au încălcat cifrele iraniene (deși rămâne necunoscut dacă s-a folosit doar criptanaliză pură sau alte tehnici mai puțin ortodoxe) [3] .

Descriere și utilizare

Criptoanaliza exclude de obicei metodele de atac care nu sunt îndreptate către punctele slabe inerente ale metodei care trebuie încălcată, cum ar fi luarea de mită , constrângerea fizică , furtul , ingineria socială . Aceste tipuri de atacuri, adesea mai productive decât criptanaliza tradițională, sunt totuși o alternativă importantă la criptanaliză.

În timp ce scopul este întotdeauna același, metodele și tehnicile de criptanaliză s-au schimbat drastic de-a lungul istoriei criptografiei, adaptându-se la eficiența tot mai crescută a criptografiei , începând cu metodele din stilou și hârtie din trecut, trecând prin mașini. Enigma celui de- al doilea război mondial , pentru a ajunge la schemele computerizate ale prezentului. Împreună, rezultatele criptanalizei s-au schimbat, de asemenea: nu mai este posibil să se obțină un succes nelimitat în încălcarea codurilor și, prin urmare, se întocmește o clasare a rezultatelor obținute prin atacuri. La mijlocul anilor 1970 , a fost introdusă o nouă clasă criptografică: criptografia asimetrică . Metodele de încălcare a acestei clase sunt foarte diferite de cele utilizate în trecut și implică de obicei rezolvarea unor probleme matematice extrem de complexe, cum ar fi binecunoscuta descompunere a numărului prim .

Caracteristicile atacurilor

Atacurile criptanalitice variază în ceea ce privește puterea și capacitatea de a reprezenta o amenințare pentru criptosistemele din lumea reală. O slăbiciune certificabilă este un atac teoretic care este puțin probabil să se aplice într-o situație reală; majoritatea rezultatelor obținute de cercetările criptanalitice moderne sunt de acest tip. În esență, importanța practică a unui atac depinde de răspunsurile la următoarele întrebări:

  1. ce cunoștințe și abilități sunt necesare ca premise?
  2. Cât de multe informații secrete suplimentare sunt deduse?
  3. Cât efort este necesar (adică, care este complexitatea de calcul )?

Cunoștințe primare: scenarii de criptanaliză

Atacurile pot fi clasificate în funcție de tipul de informații disponibile atacatorului despre sistemul de atacat. Ca punct de plecare, se presupune de obicei că, în scopul analizei, algoritmul general este cunoscut: acesta este principiul lui Kerckhoffs , care afirmă că inamicul cunoaște sistemul . Principiul Kerckhoffs este o presupunere rezonabilă, dat fiind că istoricul raportează nenumărate cazuri de algoritmi secreți despre care se crede că sunt siguri, care s-au dovedit a fi încălcate de îndată ce au devenit publice, de exemplu din cauza spionajului , trădării și ingineriei inverse . (Ocazional, cifrele au fost reconstituite prin deducție simplă: de exemplu, codul Lorenz menționat anterior și codul Purple , precum și o varietate de scheme clasice).

Unele scenarii tipice de atac sunt:

  • numai text cifrat : atacatorul are acces doar la o colecție de text cifrat.
  • Text clar cunoscut : atacatorul are un set de text cifrat din care cunoaște textul clar corespunzător.
  • Text clar ales ( text cifrat ales ): atacatorul poate obține text cifrat (text clar) corespunzător unui set arbitrar de text clar (text cifrat) la alegere.
  • Adaptiv cu textul clar ales : La fel ca în cazul atacului text ales, cu excepția faptului că atacatorul poate alege secvențe de text simplu pe baza informațiilor obținute din analiza mesajelor criptate anterioare. Asemănător cu acesta este atacul adaptiv cu text cifrat ales .
  • Atac legat de cheie : similar atacului cu text simplu ales, cu excepția faptului că atacatorul poate obține text cifrat criptat cu două chei diferite. Cheile sunt necunoscute, dar relația dintre ele este cunoscută: de exemplu, două taste care diferă doar cu 1 bit.

Aceste tipuri de atacuri diferă de cât de plauzibil este să le pui în practică. Deși unele atacuri sunt mai probabile decât altele, criptografii abordează adesea problema de securitate cu o abordare conservatoare și își imaginează cel mai rău caz atunci când proiectează algoritmi, argumentând că, dacă o schemă este sigură chiar și împotriva amenințărilor nerealiste, atunci ar trebui să reziste la mai mult decât bine pentru criptanaliza lumii reale.

Presupunerile sunt adesea mai realiste decât s-ar putea imagina la prima vedere. Pentru un atac cunoscut în text clar, criptanalistul poate cunoaște sau poate obține o parte din textul clar, cum ar fi o literă criptată care începe cu „Stimate domn” sau o sesiune terminală care începe cu „ LOGIN: ”. Un atac cu text clar ales este mai puțin probabil decât alte atacuri, dar este adesea plauzibil: de exemplu, ați putea convinge pe cineva să vă trimită un mesaj pe care i l-ați dat, dar în formă criptată. Atacurile legate de cheie sunt în mare parte teoretice, deși pot fi foarte realiste în unele situații: de exemplu, atunci când un cifru bloc este utilizat pentru a implementa o funcție hash .

Clasificarea succeselor în criptanaliză

Rezultatele criptanalizei pot varia, de asemenea, ca utilitate. De exemplu, criptograful Lars Knudsen ( 1998 ) a clasificat diferite tipuri de atacuri de cifrare în bloc pe baza cantității și calității informațiilor secrete descoperite:

  • încălcare totală : atacatorul deduce cheia secretă;
  • deducere globală : atacatorul descoperă un algoritm echivalent funcțional pentru criptare și decriptare, dar fără să știe cheia;
  • deducere locală : atacatorul descoperă un text clar (sau text cifrat) suplimentar, care nu a fost cunoscut anterior;
  • deducerea informațiilor : atacatorul obține unele informații de la Shannon pe textul clar (sau text cifrat) necunoscut anterior;
  • algoritm discriminator : atacatorul poate distinge cifrul de o permutare aleatorie.

Considerații similare se aplică atacurilor asupra altor tipuri de algoritmi criptografici.

Complexitate

Atacurile pot fi, de asemenea, caracterizate prin cantitatea de resurse de care au nevoie. Acestea pot fi sub forma:

  • Timp: numărul de operații primitive care trebuie efectuate. Aceste date sunt destul de generice: operațiile primitive ar putea fi instrucțiuni de bază pentru computer, cum ar fi adăugarea, XOR , schimbarea de biți și așa mai departe, precum și metode de criptare întregi;
  • Memorie - Cantitatea de spațiu de stocare necesară pentru a efectua atacul.
  • Date: cantitatea de text clar și text cifrat necesară.

Este adesea dificil să se prevadă cu precizie aceste cantități. Criptografia academică tinde cel puțin să ofere o estimare a ordinii de mărime a dificultății atacului. Bruce Schneier observă că chiar și atacurile care sunt impracticabile din punct de vedere al calculului pot fi considerate încălcări: „ Forțarea unui cifru înseamnă pur și simplu găsirea unei slăbiciuni care poate fi exploatată cu o complexitate mai mică decât forța brută . Nu contează că forța brută. Necesită 2 128 cifre. : un atac care necesită 2 110 cifre ar fi considerat o încălcare ... pe scurt, o încălcare poate fi pur și simplu o slăbiciune certificabilă: dovada faptului că cifrul nu se comportă așa cum se intenționează. "(Schneier, 2000).

Criptanaliza criptografiei asimetrice

Criptografia asimetrică sau criptografia cu cheie publică este un tip de criptografie care se bazează pe utilizarea a două chei, una privată și una publică. Aceste cifre își bazează securitatea pe probleme matematice dificile, deci un punct evident de atac este să dezvolte metode pentru rezolvarea acestor probleme. Securitatea criptografiei asimetrice cu două chei se bazează pe probleme matematice care de obicei nu sunt abordate de criptografia cu o singură cheie și, în consecință, leagă criptanaliza într-un mod nou de cercetarea matematică.

Schemele asimetrice sunt concepute pe dificultatea (conjecturată) de a rezolva diverse probleme matematice. Dacă se găsește un algoritm mai bun care poate rezolva problema, atunci sistemul este slăbit. De exemplu, securitatea schemei de schimb de chei Diffie-Hellman depinde de dificultatea de a calcula un logaritm discret . În 1983 Don Coppersmith a conceput un mod mai rapid de a găsi logaritmi discreți (în anumite grupuri), forțând astfel criptografii să utilizeze grupuri mai mari (sau diferite tipuri de grupuri). Siguranța RSA depinde (în parte) de dificultatea de a lua în calcul primii mari: un pas înainte în problema factorizării ar submina siguranța RSA.

În 1980 , un număr de 50 de cifre ar putea fi luat în calcul la costul a 10 12 operațiuni elementare. Până în 1984 , progresul în arta algoritmilor de scriere a factorizării a atins un astfel de punct încât un număr cu 75 de cifre ar putea fi luat în calcul prin aceleași operații. Mai mult, avansarea tehnicii a făcut posibilă efectuarea aceluiași număr de operații mult mai rapid. Legea lui Moore prezice că viteza computerelor va crește constant - tehnicile de factoring vor face același lucru, dar se vor baza și pe creativitatea și intuiția matematică, niciuna dintre ele nu poate fi prevăzută cu succes. Numerele de 150 de biți, odată folosite în RSA, au fost luate în considerare: efortul a fost mai mare decât imaginat, dar cu siguranță nu a fost dincolo de acoperirea computerelor rapide și moderne. De fapt, la începutul secolului 21 , numerele de 150 de cifre nu mai erau considerate suficient de lungi pentru tastele RSA. Numerele cu câteva sute de cifre sunt încă considerate greu de luat în calcul, deși metodele vor continua să se îmbunătățească în timp, necesitând lungimi cheie capabile să reziste noilor algoritmi care vor fi utilizați.

O altă caracteristică distinctivă a schemelor asimetrice este că, spre deosebire de criptosistemele simetrice, orice criptanaliză are posibilitatea de a utiliza cunoștințele acumulate din cheia publică.

Aplicarea computerelor cuantice la criptanaliză

Calculatoarele cuantice , care sunt încă în primele etape de dezvoltare, ar fi foarte utile în criptanaliză. De exemplu, algoritmul lui Shor ar putea factoriza un număr mare în timp polinomial , ceea ce înseamnă că în practică ar putea fi încălcate unele forme de criptografie cu cheie publică.

Folosind algoritmul de căutare al lui Grover pe un computer cuantic, o căutare cu forță brută pentru o cheie ar putea fi efectuată cu o viteză care este pătrată cu cea exprimată de computerele obișnuite. Evident, acest lucru ar putea fi contracarat prin creșterea lungimii cheii.

Tehnici de criptanaliză

Criptanalizatori istorici

Notă

  1. ^ Agenția Națională de Securitate Note de 50 de ani , 01/11/2002
  2. ^ Cum să hack o conexiune WEP în mai puțin de un minut
  3. ^ Încălcarea codurilor iraniene

Bibliografie

Elemente conexe

Alte proiecte

linkuri externe

Controlul autorității Tezaur BNCF 47225 · GND (DE) 4830502-9
Adus de la „ https://it.wikipedia.org/w/index.php?title=Cryptoanalysis&oldid=119785398 ”