A5 (algoritm de criptare)

A5  este un algoritm de criptare în flux folosit pentru a asigura confidențialitatea datelor transmise între telefon și stația de bază în sistemul european de comunicații digitale mobile GSM ( Groupe Spécial Mobile ).

Cifrul se bazează pe adăugarea pe biți modulo doi (operație XOR booleană) a secvenței pseudo-aleatoare generată și a informațiilor care trebuie criptate. În A5, o secvență pseudo-aleatorie este implementată pe baza a trei registre de deplasare cu feedback liniar . Registrele au 19, 22 și, respectiv, 23 de biți. Schimbările sunt controlate de un circuit special care organizează deplasarea a cel puțin două registre la fiecare pas, ceea ce duce la deplasarea neuniformă a acestora. Secvența este formată din operația XOR pe biții de ieșire ai registrelor.

Istoria creației și dezvoltării

Inițial, un cifru de flux a fost dezvoltat de criptografii militari francezi pentru a fi folosit exclusiv în scopuri militare. La sfârșitul anilor 80, standardul GSM a impus crearea unui sistem de securitate nou, modern. S-a bazat pe trei algoritmi secreti: autentificare - A3 , criptare flux - A5, generare cheie de sesiune - A8 . O dezvoltare franceză a fost folosită ca algoritm A5. Acest cifru a oferit un flux de securitate destul de bun și, prin urmare, confidențialitatea conversației. Inițial, exportul standardului din Europa nu era așteptat, dar curând a apărut nevoia. De aceea, A5 a fost redenumit A5 / 1 și a început să fie distribuit atât în ​​Europa, cât și în SUA. Pentru alte țări (inclusiv Rusia), algoritmul a fost modificat, scăzând semnificativ puterea criptografică a cifrului. A5/2 a fost conceput special ca o opțiune de export pentru țările din afara UE. Puterea criptografică a lui A5/2 a fost redusă prin adăugarea unui alt registru (17 biți) care controlează deplasările celorlalți. În A5 / 0, nu există deloc criptare. Algoritmul A5/3, bazat pe algoritmul Kasumi , a fost, de asemenea, dezvoltat și aprobat pentru utilizare în rețelele 3G. Aceste modificări sunt denumite A5/x.

Apariția în domeniul public

Oficial, această schemă cripto nu a fost publicată și structura ei nu a fost făcută publică. Acest lucru se datorează faptului că dezvoltatorii s-au bazat pe securitate în detrimentul obscurității , ceea ce înseamnă că algoritmii sunt mai greu de spart dacă descrierile lor nu sunt disponibile public. Datele au fost furnizate operatorilor GSM numai atunci când au fost necesare. Cu toate acestea, până în 1994, detaliile algoritmului A5 erau cunoscute: compania de telefonie britanică British Telecom a trimis toată documentația referitoare la standard la Universitatea din Bradford pentru analiză, fără a încheia un acord de confidențialitate . În plus, la una dintre conferințele din China au apărut materiale despre standard. Drept urmare, schema lui s-a scurs treptat în cercuri largi. În același an, oamenii de știință de la Cambridge Ross Anderson (Ross Anderson) și Michael Roe (Michael Roe) au publicat o schemă criptografică restaurată din aceste date și i-au evaluat puterea criptografică [1] . Algoritmul final a fost prezentat în lucrarea lui Jovan Golic la conferința Eurocrypt'97.

Structura A5

Algoritmul A5 este în prezent o întreagă familie de cifruri. Pentru descriere, să luăm A5/1 ca strămoș al acestei familii. Modificările în algoritmii derivați vor fi descrise separat.

Criptarea fluxului

În acest algoritm, fiecare caracter de text simplu corespunde unui caracter de text cifrat. Textul nu este împărțit în blocuri (ca în cifrul bloc ) și nu se modifică în dimensiune. Pentru a simplifica implementarea hardware și, prin urmare, a crește performanța, sunt folosite doar cele mai simple operații: adăugarea modulo 2 (XOR) și schimbarea registrului.

Secvența de ieșire este formată prin adăugarea fluxului de text sursă la secvența generată (gamma). Particularitatea operației XOR este că, aplicată de un număr par, duce la valoarea inițială. Prin urmare, mesajul este decodat prin adăugarea textului cifrat la o secvență cunoscută.

Astfel, securitatea sistemului depinde în întregime de proprietățile secvenței. În mod ideal, fiecare bit al gamma este o variabilă aleatorie independentă, iar secvența în sine este aleatorie. O astfel de schemă a fost inventată de Vernam în 1917 și a fost numită după el. După cum a demonstrat Claude Shannon în 1949, aceasta oferă securitate absolută. Dar utilizarea unei secvențe aleatorii înseamnă transmiterea pe un canal securizat a unui mesaj cu volum egal cu textul simplu, ceea ce complică foarte mult sarcina și practic nu este folosit nicăieri.

În sistemele reale, este creată o cheie de o dimensiune dată, care este ușor transmisă pe un canal privat. Secvența este generată pe baza ei și este pseudo-aleatorie. O clasă mare de coduri de flux (inclusiv A5) sunt cifruri al căror generator de secvențe pseudo-aleatorie se bazează pe registre de deplasare cu feedback liniar.

RSLOS

Un registru de deplasare cu feedback liniar constă din registrul însuși (o secvență de biți de o lungime dată) și feedback. Pe fiecare ciclu, au loc următoarele acțiuni: bitul din stânga (bitul cel mai înalt) este extras, secvența este deplasată la stânga și valoarea funcției de feedback este scrisă în celula din dreapta goală (bitul cel mai puțin semnificativ). Această funcție este suma modulo doi a anumitor biți ai registrului și este scrisă ca un polinom, unde exponentul indică numărul de biți. Biții extrași formează secvența de ieșire.

Pentru LFSR, indicatorul principal este perioada secvenței pseudo-aleatoare. Acesta va fi maxim (și egal cu 2 n − 1) dacă polinomul de feedback este primitiv modulo 2 . Secvența de ieșire în acest caz se numește secvență M.

Sistem LFSR în A5

LFSR în sine se pretează cu ușurință la criptoanaliza și nu este suficient de puternic pentru a fi utilizat în criptare. Aplicațiile practice sunt sisteme de registre variabile de ceas cu lungimi diferite și funcții de feedback.

Structura algoritmului A5 este următoarea:

  • Trei registre (R1, R2, R3) au lungimi de 19, 22 și 23 de biți,
  • Polinoame de feedback:
    • X 19 + X 18 + X 17 + X 14 + 1 pentru R1,
    • X 22 + X 21 + 1 pentru R2 și
    • X 23 + X 22 + X 21 + X 8 + 1 pentru R3,
  • Cronometrarea este controlată de un mecanism special:
    • fiecare registru are biți de sincronizare: 8 (R1), 10 (R2), 10 (R3),
    • se calculează funcția F = x&y|x&z|y&z, unde & este boolean ȘI, | - OR boolean și x, y și z sunt biții de sincronizare R1, R2 și, respectiv, R3,
    • numai acele registre care au bitul de sincronizare egal cu F sunt deplasate,
    • de fapt, registrele al căror bit de sincronizare aparține majorității sunt deplasate,
  • Bitul de ieșire al sistemului este rezultatul operației XOR asupra biților de ieșire ai registrelor.

Funcționarea algoritmului A5

Să luăm în considerare caracteristicile funcționării algoritmului pe baza schemei cunoscute. Transmiterea datelor se realizează într-o formă structurată - împărțită în cadre (114 biți). Înainte de inițializare, registrele sunt resetate, cheia de sesiune (K - 64 de biți) formată din A8 și numărul de cadre (Fn - 22 de biți) sunt introduse în algoritm . În continuare, următorii pași sunt executați secvențial:

  • Inițializare:
    • 64 de cicluri, în care următorul bit al cheii este XOR cu bitul cel mai puțin semnificativ din fiecare registru, în timp ce registrele sunt deplasate pe fiecare ciclu,
    • similar cu 22 de cicluri, numai operația XOR este efectuată cu numărul de cadru,
    • 100 de cicluri cu control de schimbare a registrului, dar fără generare de secvențe,
  • 228 (114 + 114) cicluri funcționează, cadrul transmis este criptat (primii 114 biți) și cadrul primit este decriptat (ultimii 114 biți),
  • inițializarea ulterioară este efectuată din nou, este utilizat un nou număr de cadru.

Diferențele în algoritmii derivați A5/x

Un alt registru de 17 biți (R4) a fost adăugat la algoritmul A5 / 2 , care controlează mișcarea restului. Modificările structurii sunt după cum urmează:

  • a adăugat registrul R4 cu o lungime de 17 biți,
  • polinom de feedback pentru R4: ,
  • ceasul este controlat de R4:
    • R4 are biții de sincronizare 3, 7, 10,
    • funcția majoritară se calculează F = x&y|x&z|y&z (egal cu majoritatea), unde & este boolean ȘI, | - OR boolean și x, y și z sunt biții de sincronizare R4(3), R4(7) și respectiv R4(10),
    • R1 este deplasat dacă R4(10) = F,
    • R2 este deplasat dacă R4(3) = F,
    • R3 este deplasat dacă R4(7) = F,
  • bitul de ieșire al sistemului este rezultatul operațiunii XOR asupra biților înalți ai registrelor și funcțiilor majoritare din anumiți biți ai registrelor:
    • R1 - 12, 14, 15,
    • R2 - 9, 13, 16,
    • R3 - 13, 16, 18.

Modificările de funcționare nu sunt atât de semnificative și se referă doar la inițializare:

  • 64+22 de cicluri sunt umplute cu cheia de sesiune și numărul de cadru, de asemenea, R4,
  • 1 ciclu R4(3), R4(7) și R4(10) sunt umplute cu 1,
  • 99 de cicluri cu control de schimbare a registrului, dar fără generare de secvențe.

Se poate observa că inițializarea durează același timp (100 de cicluri fără generare sunt împărțite în două părți).

Algoritmul A5/3 a fost dezvoltat în 2001 și ar trebui să înlocuiască A5/1 în a treia generație de sisteme mobile. Se mai numește și algoritmul Kasumi . Când a fost creat, cifrul MISTY al Mitsubishi Corporation a fost luat ca bază. În prezent, se consideră că A5/3 oferă rezistența necesară.

Algoritmul A5/0 nu conține criptare.

Securitate

Dezvoltarea standardului GSM a însemnat o mașină de criptare puternică care nu putea fi piratată (mai ales în timp real). Evoluțiile utilizate, cu o implementare adecvată, au asigurat criptarea de înaltă calitate a datelor transmise. Acesta este genul de informații care pot fi obținute de la companiile care distribuie acest standard. Dar merită remarcată o nuanță importantă: ascultarea conversațiilor este un atribut integral folosit de serviciile speciale. Erau interesați de posibilitatea interceptărilor telefonice în scopuri proprii. Astfel, s-au făcut modificări algoritmului, făcând posibilă spargerea într-un timp acceptabil. În plus, A5 a fost modificat pentru export în A5 / 2. MoU (Memorandum of Understand Group Special Mobile standard) recunoaște că scopul dezvoltării A5/2 a fost de a reduce puterea criptografică a criptării, cu toate acestea, rezultatele testelor oficiale spun că nu există deficiențe cunoscute ale algoritmului [2] .


Vulnerabilitati cunoscute

Odată cu apariția datelor pe standardul A5, au început încercările de a sparge algoritmul, precum și de a căuta vulnerabilități. Un rol uriaș l-au jucat caracteristicile standardului, care slăbesc drastic protecția, și anume:

  • 10 biți ai cheii sunt forțați la zero,
  • lipsa legăturilor încrucișate între registre (cu excepția controlului deplasării),
  • criptarea informațiilor de serviciu cunoscute de criptoanalist,
  • mai mult de 40% din chei duce la lungimea minimă a perioadei secvenței generate și anume [3]
  • la începutul sesiunii, se schimbă mesaje nule (un cadru la un moment dat),
  • aceeași umplutură pentru toate pachetele,
  • în A5/2 mișcarea se realizează printr-un registru separat de 17 biți.

Pe baza acestor „găuri” din algoritm, se construiesc scheme de hacking.

Atacuri notabile

Cheia este o cheie de sesiune pe 64 de biți, se presupune că numărul cadrului este cunoscut. Astfel, complexitatea unui atac cu forță brută este 2 64 .

Primele recenzii ale cifrului (lucrarea lui Ross Anderson) au dezvăluit imediat vulnerabilitatea algoritmului - datorită scăderii lungimii efective a cheii (la zero la 10 biți), complexitatea a scăzut la 245 (cu 6 ordine de mărime simultan ). ). Atacul lui Anderson se bazează pe presupunerea umplerii inițiale a registrelor scurte și pe rezultatul obținerii umplerii celui de-al treilea.

În 1997, Jovan Golic a publicat rezultatele analizei A5. El a propus o modalitate de a determina umplerea inițială a registrelor dintr-un segment cunoscut al gamma, lung de doar 64 de biți. Acest segment este obținut din zero mesaje. Atacul are o dificultate medie de 2 40 .

În 1999, Wagner și Goldberg au demonstrat cu ușurință că, pentru a deschide sistemul, este suficient să se determine umplerea inițială R4 prin enumerare. Verificarea se efectuează în detrimentul zero cadre. Complexitatea acestui atac este de 2 17 , deci este nevoie de câteva secunde pentru a sparge cifrul pe un computer modern.

În decembrie 1999, un grup de oameni de știință israelieni ( Adi Shamir , Alex Biryukov , iar mai târziu americanul Wagner metodă foarte nebanală, dar teoretic foarte eficientă pentru deschiderea A5 / 1:

Aceasta este o idee foarte complexă, una pe care o atacăm pe mai multe fronturi pentru a acumula câteva mici avantaje, dar puse împreună, fac o mare diferență.Adi Shamir

Note

  1. ↑ Anderson, Ross A5 - Algoritmul de criptare GSM  (ing.) (txt)  (link nu este disponibil) . sci.crypt (7 iunie 1994). Consultat la 24 noiembrie 2009. Arhivat din original pe 21 septembrie 2011.
  2. ↑ Quirke, Jeremy Securitatea în sistemul GSM (link indisponibil) . AusMobile (1 mai 2004). Arhivat din original pe 12 iulie 2004. 
  3. ↑ Preneel, Bart Fast software encryption  ( google book ) (decembrie 1994). — (pagina 26). Preluat: 24 noiembrie 2009.

Link -uri


 Criptosisteme simetrice
Cifruri în flux
Rețeaua Feistel
Rețeaua SP
Alte