AES

AES (de la Advanced Encryption Standard - în limba 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] Standardul oficializează algoritmul dezvoltat de doi criptografi belgieni, Joan Daemen și Vincent Rijmen și trimis la NIST pentru selecție sub numele Rijndael.

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,^[2] 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, 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).^[3]

Algoritmul

Î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.^[4] 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.^[5] 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.^[5]

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:^[6]

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.^[7]

Descrierea algoritmului AES

•AES operează cu matrici de 4x4 octeți.

•Pentru criptare, fiecare rundă AES execută următorii pași:

1.SubBytes() – substituție în care fiecare octet este înlocuit cu un altul cu ajutorul unei “look-up table”

2.ShiftRows() – transpoziție ciclică cu un anumit număr de pași

3.MixColumns – o operație de amestec ce folosește o funcție polinomială

4.AddKeyRound() – fiecare octet este combinat cu o cheie specifică rundei, ce a fost în prealabil calculată din cheia inițială

Pasul SubBytes

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:

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.^[8] 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.^[9]

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.^[10] 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.^[11]

Pasul MixColumns

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

{\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 $s_{i}^{\prime }$ sunt elementele de pe un vector coloană rezultate în urma înmulțirii, iar $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).^[13] Acești doi pași, împreună, sunt principala sursă de difuzie î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.^[13]

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 rundă (o cheie care este unică pentru fiecare iterație, 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 rundă (Key Schedule), precum și a celorlalți pași ai algoritmului.^[14]

Cheia de rundă este calculată după algoritmul următor:^[15]

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 $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.^[16] RotWord este o rotație ciclică la stânga cu un octet a octeților dintr-un cuvânt.^[16] Cu Rcon[i] se notează în algoritm un cuvânt format din octeții $\left[2^{i-1},\{00\},\{00\},\{00\}\right]$ . Operația de ridicare la putere este aici cea valabilă în corpul Galois $F_{2^{8}}$ .^[16] Tabloul w conține la finalul prelucrării cuvintele de pe coloanele cheilor de rundă, în ordinea în care urmează să fie aplicate.

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.^[17]

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.^[18]

Note

^ „NIST reports measurable success of Advanced Encryption Standard - News Briefs - National Institute of Standards and Technology - Brief Article”. Journal of Research of the National Institute of Standards and Technology, May-June, 2002.
^ Stallings, p. 137
^ Stallings, p. 138
^ Stallings, p. 140
^ ^a ^b FIPS PUB 197, cap. 3.2, p. 9
^ FIPS PUB 197, cap. 5.1, p. 15
^ FIPS PUB 197, cap. 5, p. 14
^ FIPS PUB 197, cap. 5.1.1, p. 15
^ FIPS PUB 197, cap. 5.1.1, p. 16
^ FIPS PUB 197, cap. 5.1.2, p. 17
^ Stallings, p. 150
^ FIPS PUB 197, cap. 5.1.3, pp. 16-17
^ ^a ^b Stallings, p. 154
^ Stallings, p. 155
^ FIPS PUB 197, cap. 5.2, p. 20
^ ^a ^b ^c FIPS PUB 197, cap. 5.2, p. 19
^ „National Policy on the Use of the Advanced Encryption Standard (AES) to Protect National Security Systems and National Security Information” (PDF) (în engleză). Comitetul pentru Sisteme de Securitate Naționale, SUA. iunie 2003. Arhivat din original (PDF) la 27 septembrie 2007. Accesat în 27 mai 2008.
^ John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner, Doug Whiting (2000). „Improved Cryptanalysis of Rijndael, Fast Software Encryption Workshop”. Springer-Verlag. Accesat în 27 mai 2008.

Bibliografie

William Stallings (2005). Cryptography and Network Security, 4th edition. Prentice Hall. ISBN 0-13-187319-3 Verificați valoarea |isbn=: checksum (ajutor).
„Publicația FIPS 197” (PDF) (în engleză). Federal Information Processing Standards. 26 noiembrie 2001. Accesat în 26 mai 2008. Verificați datele pentru: |date= (ajutor)

[1] „NIST reports measurable success of Advanced Encryption Standard - News Briefs - National Institute of Standards and Technology - Brief Article”. Journal of Research of the National Institute of Standards and Technology, May-June, 2002.

[2] Stallings, p. 137

[3] Stallings, p. 138

[4] Stallings, p. 140

[fips197_9-5] FIPS PUB 197, cap. 3.2, p. 9

[6] FIPS PUB 197, cap. 5.1, p. 15

[7] FIPS PUB 197, cap. 5, p. 14

[8] FIPS PUB 197, cap. 5.1.1, p. 15

[9] FIPS PUB 197, cap. 5.1.1, p. 16

[10] FIPS PUB 197, cap. 5.1.2, p. 17

[11] Stallings, p. 150

[12] FIPS PUB 197, cap. 5.1.3, pp. 16-17

[stallings154-13] Stallings, p. 154

[14] Stallings, p. 155

[15] FIPS PUB 197, cap. 5.2, p. 20

[fips19-16] FIPS PUB 197, cap. 5.2, p. 19

[17] „National Policy on the Use of the Advanced Encryption Standard (AES) to Protect National Security Systems and National Security Information” (PDF) (în engleză). Comitetul pentru Sisteme de Securitate Naționale, SUA. iunie 2003. Arhivat din original (PDF) la 27 septembrie 2007. Accesat în 27 mai 2008.

[improved-18] John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner, Doug Whiting (2000). „Improved Cryptanalysis of Rijndael, Fast Software Encryption Workshop”. Springer-Verlag. Accesat în 27 mai 2008.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]