AES

AES (de la Advanced Encryption Standard – în traducere literală din engleză, Standard Avansat de Criptare), cunoscut și sub numele de Rijndael, este un algoritm standardizat pentru criptarea simetrică, pe blocuri, folosit astăzi pe scară largă în aplicații și adoptat ca standard de organizația guvernamentală americană NIST.^[1][2]

Ilustrare grafică a operațiilor ce compun algoritmul Rijndael

AES este o variantă a cifrului pe blocuri Rijndael,^[3] dezvoltat de doi criptografi belgieni, Joan Daemen și Vincent Rijmen, care au depus la NIST o propunere^[4] în cadrul procesului de selecție AES^⁠(d).^[5] Rijndael este o familie de cifruri cu diferite dimensiuni ale cheilor^⁠(d) și ale blocurilor^⁠(d). Pentru AES, NIST a selectat trei membri ai familiei Rijndael, fiecare cu blocuri de 128 de biți, dar cu trei lungimi diferite ale cheii: 128, 192 și 256 de biți.

AES a fost adoptat de guvernul SUA. El a luat locul lui Data Encryption Standard (DES),^[6] care fusese publicat în 1977. Algoritmul descris de AES este un algoritm cu chei simetrice^⁠(d), adică aceeași cheie este folosită și pentru criptarea datelor, și pentru decriptarea lor.

În Statele Unite, AES a fost anunțat de NIST ca FIPS PUB 197 (FIPS 197) pe 26 noiembrie 2001.^[2] Acest anunț a venit după un proces de standardizare de cinci ani în care au fot prezentate și evaluate cincisprezece designuri concurente, înainte ca cifrul Rijndael să fie selectat drept cel mai adecvat.

AES este inclus în standardul ISO/IEC 18033-3^⁠(d). AES a devenit efectiv standard al guvernului american pe 26 mai 2002, după ce a fost aprobat de secretarul american al comerțului^⁠(d) Donald Evans^⁠(d). AES este disponibil în multe pachete diferite de criptare și este primul (și singurul) cifru^⁠(d) accesibil public și aprobat de National Security Agency (NSA) pentru informații clasificate la nivel top secret când se folosește într-un modul criptografic aprobat de NSA.

Origine

Vincent Rijmen, coautor al algoritmului Rijndael

Deoarece DES devenise vulnerabil din cauza lungimii prea mici a cheii, NIST a recomandat utilizarea 3DES, un algoritm care constă în esență în aplicarea de trei ori a DES. Deși 3DES s-a dovedit a fi un algoritm puternic, el este relativ lent în implementările software,^[7] motiv pentru care NIST a lansat în 1997 o cerere de propuneri pentru un algoritm care să-l înlocuiască. S-a pornit de la 21 de propuneri acceptate inițial, apoi prin eliminări numărul lor a fost redus la 15, și apoi la 5, din care a fost ales în cele din urmă algoritmul propus de doi criptografi belgieni, Joan Daemen și Vincent Rijmen. La votarea finală, algoritmul, denumit de autorii săi Rijndael, a învins la vot patru alte propuneri, printre care și algoritmul RC6^⁠(d), propus de o echipă de criptografi în care se afla și reputatul informatician Ron Rivest.

Criteriile pe baza cărora au fost evaluate propunerile pentru AES au fost securitatea (rezistența la atacuri criptanalitice), costurile (eficiența computațională, complexitatea spațială, precum și licențierea liberă și gratuită) și particularitățile algoritmului (flexibilitatea, simplitatea, și ușurința de realizare a implementărilor atât software cât și hardware).^[8]

Algoritm

În propunerea avansată NIST, cei doi autori ai algoritmului Rijndael au definit un algoritm de criptare pe blocuri în care lungimea blocului și a cheii puteau fi independente, de 128 de biți, 192 de biți, sau 256 de biți. Specificația AES standardizează toate cele trei dimensiuni posibile pentru lungimea cheii, dar restricționează lungimea blocului la 128 de biți.^[9] Astfel, intrarea și ieșirea algoritmilor de criptare și decriptare este un bloc de 128 de biți. În publicația FIPS numărul 197, operațiile AES sunt definite sub formă de operații pe matrice, unde atât cheia, cât și blocul sunt scrise sub formă de matrice.^[10] La începutul rulării cifrului, blocul este copiat într-un tablou denumit stare (în engleză state), primii patru octeți pe prima coloană, apoi următorii patru pe a doua coloană, și tot așa până la completarea tabloului.^[10]

Algoritmul modifică la fiecare pas acest tablou de numere denumit state, și îl furnizează apoi ca ieșire. Funcționarea sa este descrisă de următorul pseudocod:^[11]

Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
  begin
    byte state[4,Nb]
    state = in
    AddRoundKey(state, w[0, Nb-1])
    for round = 1 step 1 to Nr–1
       SubBytes(state)
       ShiftRows(state)
       MixColumns(state)
       AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])
    end for
    SubBytes(state)
    ShiftRows(state)
    AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])
    out = state
  end

Aici, Nb este numărul de coloane al stării, în varianta standardizată acesta fiind întotdeauna 4. Se observă din descrierea algoritmului că o anumită secvență este realizată iterativ, de un număr de Nr ori. Acest Nr depinde de lungimea cheii și este 10, 12 sau 14, pentru chei pe 128, 192, respectiv 256 biți.^[12]

Descriere generală a pașilor

1. KeyExpansion – se calculează cheile de iterație din cheia de cifru folosind AES key schedule^⁠(d). AES necesită cât un bloc de 128 de biți, cheia de iterație, pentru fiecare iterație, plus încă unul.
2. Integrarea inițială a cheii de iterație:
   1. AddRoundKey – fiecare octet al stării este combinat cu un octet al cheii de iterație folosind XOR pe biți^⁠(d).
3. 9, 11 sau 13 iterații:
   1. SubBytes – un pas de substituție neliniar în care fiecare octet este înlocuit cu un altul conform unei tabele de corespondență^⁠(d).
   2. ShiftRows – un pas de transpoziție în care ultimele trei rânduri ale stării sunt deplasate ciclic de un anumit număr de ori.
   3. MixColumns – o operațiune liniară de amestec care operează pe coloanele stării, combinând cei patru octeți din fiecare coloană.
   4. AddRoundKey
4. Iterația finală (aducând numărul total la 10, 12 sau 14):
   1. SubBytes
   2. ShiftRows
   3. AddRoundKey

Pasul SubBytes

La pasul SubBytes, fiecare octet din blocul state este înlocuit cu un altul, conform unui cifru cu substituție

Pasul SubBytes este un cifru cu substituție, fără punct fix, denumit Rijndael S-box, care rulează independent pe fiecare octet din state. Această transformare este neliniară și face astfel întreg cifrul să fie neliniar, ceea ce îi conferă un nivel sporit de securitate.

Fiecare octet este calculat astfel:

${\displaystyle b_{i}^{\prime }=b_{i}\oplus b_{(i+4)mod8}\oplus b_{(i+5)mod8}\oplus b_{(i+6)mod8}\oplus b_{(i+7)mod8}\oplus c_{i}}$

unde b_i este bitul corespunzător poziției i din cadrul octetului, iar c_i este bitul corespunzător poziției i din octetul ce reprezintă valoarea hexazecimală 63, sau, pe biți, 01100011.^[13] Maparea octeților se poate reține într-un tabel, explicitat în FIPS PUB 197, în care este specificat rezultatul operației de mai sus efectuată pe fiecare din cele 256 de valori posibile reprezentabile pe un octet.^[14]

Pasul ShiftRows

Pasul ShiftRows

Pasul ShiftRows operează la nivel de rând al matricii de stare state. Pasul constă în simpla deplasare ciclică a octeților de pe rânduri, astfel: primul rând nu se deplasează; al doilea rând se deplasează la stânga cu o poziție; al treilea rând se deplasează la stânga cu două poziții; al patrulea se deplasează la stânga cu trei poziții.^[15] Rezultatul acestui pas este că fiecare coloană din tabloul state rezultat este compusă din octeți de pe fiecare coloană a stării inițiale. Acesta este un aspect important, din cauză că tabloul state este populat inițial pe coloane, iar pașii ulteriori, inclusiv AddRoundKey în care este folosită cheia de criptare, operațiile se efectuează pe coloane. Se evită astfel criptarea independentă a coloanelor.^[16]

Pasul MixColumns

În pasul MixColumns, fiecare coloană este înmulțită cu un polinom, notat în figură cu c(x)

În acest pas, fiecare coloană a tabloului de stare este considerată un polinom de gradul 4 peste corpul Galois ${\displaystyle F_{2^{8}}}$. Fiecare coloană, tratată ca polinom, este înmulțită, modulo ${\displaystyle x^{4}+1}$ cu polinomul ${\displaystyle a(x)=3x^{3}+x^{2}+x+2}$. Operația se poate scrie ca înmulțire de matrice astfel:^[17]

${\displaystyle {\begin{bmatrix}s_{0}^{\prime }\\s_{1}^{\prime }\\s_{2}^{\prime }\\s_{3}^{\prime }\end{bmatrix}}={\begin{bmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{bmatrix}}{\begin{bmatrix}s_{0}\\s_{1}\\s_{2}\\s_{3}\end{bmatrix}}}$

unde ${\displaystyle s_{i}^{\prime }}$ sunt elementele de pe un vector coloană rezultate în urma înmulțirii, iar ${\displaystyle s_{i}}$ sunt elementele de pe același vector înaintea aplicării pasului.

Rezultatul are proprietatea că fiecare element al său depinde de toate elementele de pe coloana stării dinaintea efectuării pasului. Combinat cu pasul ShiftRows, acest pas asigură că după câteva iterații, fiecare octet din stare depinde de fiecare octet din starea inițială (tabloul populat cu octeții mesajului în clar).^[18] Acești doi pași, împreună, sunt principala sursă de difuzie^⁠(d) în algoritmul Rijndael. Coeficienții polinomului a(x) sunt toți 1, 2 și 3, din motive de performanță, criptarea fiind mai eficientă atunci când coeficienții sunt mici. La decriptare, coeficienții pasului corespunzător acestuia sunt mai mari și deci decriptarea este mai lentă decât criptarea. S-a luat această decizie pentru că unele din aplicațiile în care urma să fie folosit algoritmul implică numai criptări, și nu și decriptări, deci criptarea este folosită mai des.^[18]

Pasul AddRoundKey și planificarea cheilor

În pasul AddRoundKey, se efectuează o operație de sau exclusiv pe biți între octeții stării și cei ai cheii de rundă

Pasul AddRoundKey este pasul în care este implicată cheia. El constă într-o simplă operație de „sau” exclusiv pe biți între stare și cheia de iterație (o cheie care este unică la fiecare repetare, cheie calculată pe baza cheii secrete). Operația de combinare cu cheia secretă este una extrem de simplă și rapidă, dar algoritmul rămâne complex, din cauza complexității calculului cheilor de iterație (Key Schedule), precum și a celorlalți pași ai algoritmului.^[19]

Cheia de iterație este calculată după algoritmul următor:^[20]

KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk)
 begin
  word temp
  i = 0
  while (i < Nk)
   w[i] = word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3])
   i = i+1
  end while
  i = Nk
  while (i < Nb * (Nr+1)]
   temp = w[i-1]
   if (i mod Nk = 0)
     temp = SubWord(RotWord(temp)) xor Rcon[i/Nk]
   else if (Nk > 6 and i mod Nk = 4)
     temp = SubWord(temp)
   end if
   w[i] = w[i-Nk] xor temp
   i = i + 1
  end while
 end

Acest algoritm lucrează pe cheia algoritmului, de lungime Nk cuvinte de 4 octeți (4, 6 sau 8, conform standardului), populând un tabel de ${\displaystyle Nb\times (Nr+1)}$ cuvinte, Nb fiind numărul de cuvinte al blocului (în versiunea standardizată, 4), iar Nr numărul de runde (iterații), dependent de lungimea cheii. Algoritmul de planificare a cheilor folosește transformarea SubWord, care este o substituție a octeților identică cu cea din pasul SubBytes.^[21] RotWord este o rotație ciclică la stânga cu un octet a octeților dintr-un cuvânt.^[21] Cu Rcon[i] se notează în algoritm un cuvânt format din octeții ${\displaystyle \left[2^{i-1},\{00\},\{00\},\{00\}\right]}$. Operația de ridicare la putere este aici cea valabilă în corpul Galois ${\displaystyle F_{2^{8}}}$.^[21] Tabloul w conține la finalul prelucrării cuvintele de pe coloanele cheilor de rundă, în ordinea în care urmează să fie aplicate.

Optimizarea cifrului

Pe sisteme care operează pe cuvinte de 32 de biți sau mai mari, se poate accelera execuția acestui cifru combinând pașii SubBytes și ShiftRows cu pasul MixColumns, transformându-i într-o secvență de căutări într-un tablou. Aceasta necesită patru tablouri cu 256 de elemente de 32 de biți fiecare (ocupând în total 4096 de octeți). O iterație devine în acel moment un șir de 16 operații de adresare în acel tablou și 12 operații de sau exclusiv pe 32 de biți, urmate de patru operații de sau exclusiv pe 32 de biți în pasul AddRoundKey.^[22] Alternativ, în loc de patru tablouri se poate folosi doar unul, de 256 de elemente de 32 de biți fiecare (ocupând 1024 de octeți), adresarea în el fiind dublată de operațiile de rotație circulară.

Într-o abordare orientată pe octeți, se pot combina pașii SubBytes, ShiftRows, și MixColumns într-o singură transformare de iterație.^[23]

Securitatea

Rijndael, ca și toți ceilalți algoritmi ajunși în etapa finală de selecție pentru standardul AES, a fost revizuit de NSA și, ca și ceilalți finaliști, este considerat suficient de sigur pentru a fi folosit la criptarea informațiilor guvernamentale americane neclasificate. În iunie 2003, guvernul SUA a decis ca AES să poată fi folosit pentru informații clasificate. Până la nivelul SECRET, se pot folosi toate cele trei lungimi de cheie standardizate, 128, 192 și 256 biți. Informațiile TOP SECRET (cel mai înalt nivel de clasificare) pot fi criptate doar cu chei pe 256 biți.^[24]

Atacul cel mai realizabil împotriva AES este îndreptat împotriva variantelor Rijndael cu număr redus de iterații. AES are 10 iterații la o cheie de 128 de biți, 12 la cheie de 192 de biți și 14 la cheie de 256 de biți. La nivelul anului 2008, cele mai cunoscute atacuri erau accesibile la 7, 8, respectiv 9 iterații pentru cele trei lungimi ale cheii.^[25]

Atacuri cunoscute

Pentru criptografi, o „spargere” se definește ca orice manevră mai rapidă decât un atac cu forța brută – adică încercarea decriptării cu toate cheile posibile. „Spargeri” pot fi astfel denumite și unele rezultate nefezabile cu tehnologia actuală. Deși sunt nepractice, astfel de spargeri teoretice pot uneori să ofere informații despre șabloanele de vulnerabilitate. Cel mai mare atac cu forță brută cunoscut public împotriva unui algoritm de criptare a fost împotriva unei chei RC5^⁠(d) pe 64 de biți efectuat de Distributed.net^⁠(d) în 2006.^[26]

Spațiul cheilor se dublează la fiecare bit adăugat la lungimea cheii, și toate valorile posibile ale cheii sunt echiprobabile; aceasta se traduce prin dublarea timpului de căutare într-un atac cu forță brută, la fiecare bit adițional adăugat la lungimea cheii. Aceasta implică faptul că costurile unei căutări cu forța brută cresc exponențial cu lungimea cheii. Singură, o cheie de lungime mare nu implică securitate în fața atacurilor, întrucât sunt cifruri cu chei foarte lungi, dar cărora li s-au descoperit vulnerabilități.

AES are un cadru algebric relativ simplu.^[27] În 2002, un atac teoretic, denumit „atacul XSL^⁠(d)”, a fost anunțat de Nicolas Courtois^⁠(d) și Josef Pieprzyk^⁠(d), care susțineau că expun o slăbiciune a algoritmului AES, parțial datorată complexității scăzute a componentelor sale neliniare.^[28] De atunci, alte lucrări au demonstrat că atacul, așa cum era prezentat inițial, nu este realizabil.

În cadrul procesului de selecție AES, dezvoltatorii algoritmilor concurenți au scris despre algoritmul Rijndael că „îngrijorează utilizarea lui ... în aplicații critice din punct de vedere al securității."^[29] În octombrie 2000 însă, la sfârșitul procesului de selecție, Bruce Schneier, dezvoltatorul algoritmului concurent Twofish^⁠(d), a scris că, deși credea că într-o bună zi se vor dezvolta atacuri academice reușite asupra lui Rijndael, el „nu cred[e] că va descoperi vreodată cineva un atac care să permită citirea traficului [criptat cu] Rijndael.”^[30]

Până în 2006, cele mai eficiente atacuri cunoscute erau pe 7 iterații pentru cheile pe 128 de biți, 8 iterații pentru cheile pe 192 de biți, și 9 iterații pentru cheile de 256 de biți.^[25]

Până în mai 2009, singurele atacuri reușite publicate, împotriva lui AES complet, erau atacuri pe canal lateral^⁠(d) asupra anumitor implementări specifice. În 2009, s-a descoperit un nou atac cu cheie corelată^⁠(d) care exploatează simplitatea generatorului de chei din AES, și are o complexitate de 2¹¹⁹. În decembrie 2009, complexitatea a fost îmbunătățită la 2^99,5.^[31] Aceasta a fost continuarea unui atac descoperit tot în 2009 de către Alex Biryukov^⁠(d), Dmitry Khovratovich^⁠(d), și Ivica Nikolić, cu o complexitate de 2⁹⁶ pentru una din 2³⁵ de chei.^[32] Atacurile cu cheie corelată nu sunt însă de natură să provoace îngrijorări într-un protocol criptografic corect proiectat (adică în implementări software) care are grijă să nu permită chei corelate, în principal prin constrângerea modului în care își poate alege atactatorul cheile.

Un alt atac a fost anunțat de Bruce Schneier^[33] pe 30 iulie 2009, și publicat ca preprint^[34] pe 3 august 2009. Acest nou atac, al lui Alex Biryukov, Orr Dunkelman^⁠(d), Nathan Keller, Dmitry Khovratovich, și Adi Shamir, este împotriva unui AES-256 care folosește doar două chei corelate, în timp 2³⁹ pentru a recupera întreaga cheie pe 256 de biți a unei versiuni cu 9 iterații, sau în timp 2⁴⁵ pentru o versiune cu 10 iterații cu un tip mai puternic de atac cu subcheie corelată, sau timp 2⁷⁰ pentru o versiune cu 11 iterații. AES pe 256 de biți folosește 14 iterații, astfel că aceste atacuri nu au eficiență împotriva lui AES complet.

Practicitatea acestor atacuri cu chei corelate mai puternice a fost criticată,^[35] de exemplu, de articolul despre atacurile cu corelații de cheie aleasă la mijloc pe AES-128, scris de Vincent Rijmen în 2010.^[36]

În noiembrie 2009, a fost publicat ca preprint primul atac de distincție cu cheie cunoscută^⁠(d) împotriva unei versiuni reduse la 8 iterații a lui AES-128.^[37] Acest atac este o îmbuătățire a atacului start-from-the-middle, împotriva permutărilor similare lui AES, care văd două iterații consecutive ca aplicare a unui așa-numit Super-S-box. El funcționează pe versiunea cu 8 iterații a lui AES-128, cu o complexitate în timp de 2⁴⁸, și una în spațiu de 2³². AES pe 128 de biți folosește 10 iterații, astfel că acest atac nu este eficient împotriva lui AES-128 complet.

Primele atacuri cu recuperarea cheii^⁠(d) asupra lui AES complet au fost efectuate de Andrey Bogdanov, Dmitry Khovratovich, și Christian Rechberger, și au fost publicate în 2011.^[38] Este un atac biciclic^⁠(d) și este de circa patru ori mai rapid decât cel cu forță brută. Necesită 2^126.2 operații pentru recuperarea unei chei AES-128. Pentru AES-192 și AES-256, este nevoie de 2^190.2 și, respectiv, 2^254.6 operații. Acest rezultat a fost ameliorat apoi la 2^126.0 pentru AES-128, 2^189.9 pentru AES-192, și 2^254.3 pentru AES-256 de către Biaoshuai Tao și Hongjun Wu într-in articol publicat în 2015,^[39] și acestea rămân până astăzi cele mai bune rezultate în atacuri de recuperare a cheii împotriva lui AES.

Câștigul față de forța brută este foarte mic, întrucât o cheie pe 126 de biți (în loc de 128) ar putea fi găsită în miliarde de ani cu forța brută pe calculatoarele actuale sau realizabile în viitorul apropiat. În plus, autorii calculează că cel mai bun atac folosind tehnica lor asupra unui AES cu chei pe 128 de biți necesită stocarea a 2⁸⁸ biți de date, adică circa 38 de bilioane de teraocteți de date, adică mai mult decât toate datele stocate pe toate calculatoarele de pe Pământ la nivelul lui 2016.^[40] Un articol din 2015 a ameliorat puțin complexitatea în spațiu la 2⁵⁶ biți,^[39] adică doar 9007 teraocteți (complexitatea în timp rămânând de aproximativ 2¹²⁶).

Conform documentelor Snowden, NSA efectua cercetri pentru a afla dacă un atac criptografic bazat pe statistica tau^⁠(d) ar putea ajuta la spargerea lui AES.^[41]

În prezent, nu se cunoaște niciun atac practic care să permită cuiva care nu știe cheia să citească datele criptate cu AES într-o implementare corectă.