Criptoanaliza

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

Pentru criptanaliză (din limba greacă Kryptos, „ascuns”, și analýein, „factoring”), sau criptanaliză, este studiul metodelor de obținere a semnificației informațiilor criptate fără a fi nevoie de „accesul la informații secrete care în mod normal sunt necesare pentru a efectua operațiunea. Criptanaliza este „contrapartea” criptării , și anume studiul tehnicilor de ascundere a unui mesaj și formează împreună Criptologia , știința înregistrărilor ascunse.

Cu criptanaliza se referă nu numai la metode de încălcare a unui cifru , ci și la orice încercare de a ocoli securitatea algoritmilor criptografici și a protocoalelor criptografice, de exemplu folosind canalul 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 codului criptat ș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 clar: 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ă pe cunoștințele lingvistice , dat fiind că 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 încălca cifrele Puterilor Axei au cerut noi niveluri de rafinament matematic. De asemenea , la acel moment a fost introdus pentru prima dată în automatizarea criptanaliza cu computerul polonez Bomba , cu utilizarea de dispozitive pentru cartele perforate și Colossus , unul dintre primul computer (probabil primul calculator 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ă recuperați cheia care deblochează alte mesaje. Într-un anumit sens, prin urmare, criptanaliza este moartă. Dar acesta nu este sfârșitul poveștii: a fi 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 da criptanalizei moarte: cifrele slabe sunt departe de a fi dispărute, iar metodele criptanalitice folosite de agențiile de informații rămân în continuare în mare parte necunoscute. În domeniul academic, mulți cercetători au în mod regulat noi sisteme criptografice, care sunt adesea încălcate rapid: cifrul bloc Madryga , publicat în 1984 a fost găsit sensibil la atacuri doar text cifrat în 1998 ; FEAL-4 , propus ca înlocuitor al DES , a fost demolat de o serie de atacuri din partea comunității academice, dintre care mulți sunt complet fezabili î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 arătat că protocolul WEP , care este utilizat pentru securizarea conexiunilor Wi-Fi , era nesigur și o cheie aferentă atacului putea fi recuperată de acesta din urmă în câteva ore. În 2005 , a găsit chiar o modalitate de a sparge un acces protejat WEP în mai puțin de un minut [2] .

Evoluțiile din secolul al XX-lea

Telegrama Zimmermann a 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 război a 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 cunoscută cercetătorilor unul dintre punctele care au scurtat cu câteva luni războiul încheiat în Europa (vezi ULTRA ). Chiar și Statele Unite, datorită faptului că au beneficiat de crittanoalisi, au putut descifra multe dintre comunicările secrete ale armatei japoneze , care au fost 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 au încălcat cifrele Iranului (deși rămâne necunoscut dacă s-a folosit doar criptanaliză pură sau chiar alte tehnici mai puțin ortodoxe) [3] .

Descriere și utilizare

Criptanaliza exclude de obicei alte metode de atac decât cele directe către punctele slabe inerente ale metodei de intrare, cum ar fi corupția , 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ă.

Chiar dacă sfârșitul este întotdeauna același, metodele și tehnicile de criptanaliză s-au schimbat drastic în timpul istoriei criptografiei, adaptându-se pentru a crește continuu eficiența criptării , începând cu stilourile și metodele de pe hârtie din trecut, prin mașini criptografice precum ' Enigma celui de- al doilea război mondial , pentru a ajunge la schemele bazate pe computerul 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 șaptezeci a fost introdusă o nouă criptografie de clasă: criptografia asimetrică . Metodele de a încălca această clasă sunt destul de diferite de cele utilizate în trecut și implică în mod normal rezolvarea problemelor matematice extrem de complexe, cum ar fi descompunerea binecunoscută în numere prime .

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, de obicei se presupune că, în scopul analizei, algoritmul este în general cunoscut: acesta este principiul lui Kerckhoffs , care afirmă că inamicul cunoaște sistemul. Principiul Kerckhoffs este o presupunere rezonabilă, deoarece istoria arată nenumărate cazuri de algoritmi secreți considerați siguri, dovediți inviolabili imediat ce au intrat în domeniul public, de exemplu din cauza spionajului , trădării și ingineriei inverse . (Ocazional, cifrele au fost reconstituite prin simpla deducție: de exemplu, codul Lorenz și Purple menționat mai sus, în plus față de o varietate de scheme clasice).

Unele scenarii tipice de atac sunt:

  • numai text cifrat : atacatorul are acces doar la o colecție de texte cifrate.
  • Text simplu cunoscut : atacatorul are un set de text criptat din care cunoaște textul clar corespunzător.
  • Text simplu ales (text cifrat ales ): atacatorul poate obține textele cifrate (texte simple) corespunzătoare unui set arbitrar de texte simple (texte cifrate) la alegere.
  • Adaptiv cu textul în formă aleasă ales : la fel ca în cazul atacului cu text în formă aleasă, cu excepția faptului că atacatorul poate alege secvențe de text în clar pe baza informațiilor obținute din analiza mesajelor criptate anterioare. Asemănător cu acesta este „ atacul adaptat al textului cifrat .
  • Atac legat de cheie : atac similar cu text clar ales, cu excepția faptului că atacatorul poate obține texte cifrate criptate 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 de tip text cunoscut, criptanalistul ar putea cunoaște sau poate fi în posesia unei părți din textul clar, cum ar fi o literă criptată care începe „Stimate domn” sau sesiunea- terminal î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ă. Cheia legată de atacuri este în cea mai mare parte teoretică, deși poate fi foarte realistă în unele situații: de exemplu, atunci când se utilizează un cifru bloc 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 atac asupra cifrelor bloc în funcție de cantitatea și calitatea informațiilor secrete descoperite:

  • Încălcări totale: atacatorul deduce cheia secretă;
  • Deducere globală: atacatorul descoperă un algoritm echivalent funcțional pentru criptare și decriptare, dar fără cheie;
  • Deducție locală: atacatorul descoperă texte în clar (sau texte cifrate) care nu erau cunoscute anterior;
  • deducerea informațiilor: atacatorul câștigă unele informații Shannon despre texte simple (sau pe texte cifrate) care nu erau cunoscute anterior;
  • algoritm discriminant: 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. Această cifră este destul de generică: operațiile primitive ar putea fi instrucțiuni de bază ale computerului, cum ar fi adăugări, XOR , deplasări de biți și așa mai departe, ca metode de criptare întregi;
  • Memorie - Cantitatea de spațiu de stocare necesară pentru a efectua atacul.
  • Date: cantitatea de texte simple și textele cifrate necesare.

Este adesea dificil să se prezică cu precizie aceste cantități. În cadrul academiei de criptare tinde să ofere cel puțin o estimare a ordinii de mărime a dificultății atacului. Bruce Schneier observă că 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 în sine care poate fi exploatată cu o complexitate mai mică a forței brute . Nu contează că forța brută necesită 2128 criptări: un atac care ar necesita 2 110 criptări ar fi considerat o încălcare ... cu alte cuvinte, o încălcare poate fi pur și simplu o slăbiciune certificabilă: dovezi că cifrul nu se comportă așa cum era de așteptat. "(Schneier, 2000).

Criptanaliza criptografiei asimetrice

Criptarea asimetrică sau criptarea cheii publice este un tip de criptare 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 depinde de probleme matematice care de obicei nu sunt abordate de criptografia cu o singură cheie și, în consecință, corelează analiza criptografică cu cercetarea matematică într-un mod nou.

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 calculării unui logaritm discret . În 1983 Don Coppersmith a conceput o modalitate 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 numerele prime mari: un pas înainte în problema factoringului erodează securitatea RSA.

În 1980 , ar putea calcula un număr până la 50 de cifre la un cost de 10 12 operațiuni elementare. În 1984, progresul în arta scrisului în algoritmii de factorizare a atins un astfel de punct încât aceeași operație ar putea factoriza un număr cu 75 de cifre. 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 computerului va crește constant: tehnicile de factorizare vor face același lucru, dar, de asemenea, se vor baza pe creativitate și intuiție matematică, niciuna dintre ele nu poate fi prezisă 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 al XXI-lea , numerele de 150 de cifre nu mai erau suficient de lungi pentru a permite tastele RSA. Numerele cu câteva sute de cifre sunt încă considerate dificil de luat în considerare, deși metodele vor continua să se îmbunătățească în timp, necesitând lungimi cheie care pot rezista 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 utile în criptanaliză. De exemplu, algoritmul „ Shor ” ar putea factoriza un număr mare într-un timp polinomial , adică în practică, care ar putea încălca unele forme de criptografie cu cheie publică.

Prin utilizarea algoritmului de căutare Grover pe un computer cuantic, căutarea unei chei prin forță brută ar putea fi efectuată cu o viteză care este pătratul celei exprimate de computerul normal. Evident, acest lucru ar putea fi contracarat prin creșterea lungimii cheii.

Tehnici de criptanaliză

Criptanalisti istorici

Notă

  1. ^ Observații cu privire la a 50-a aniversare a Agenției Naționale de Securitate , 01/11/2002
  2. ^ Întrucât încalcă 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=Crittoanalisi&oldid=119785398 ”