3.Designul rational

Cele trei criterii avute in vedere la elaborarea algoritmului Rijndael sunt:
- resistenta la toate atacurile cunoscute;
-viteza si modul compact de implementare pe foarte multe platforme
- simplicitatea designului
In marea majoritate a cazurilor de programe de criptografie transformarea de baza are Structura Feistel. In cazul acestei structuri partea principala a bitilor ale starii intermediare sunt pur si simplu transpusi neschimbati in alta pozitie. Transformarea de baza a lui Rijndael nu are Structura Feistel. Astfel transformarea de baza este compusa din trei transformari uniforme numite layers. Prin "uniform" se intelege ca fiecare bit din stare este tratat intr-un mod similar.
Diferitele alegeri pentru layers sunt pentru o mare parte bazate pe aplicabilitatea Strategiei Wide Trail o metoda de design care asigura rezistenta pentru criptanaliza liniara si diferentiala. In cazul Strategiei Wide Trail,fiecare layer are propria sa functie:
- layerul combinativ liniar : garanteaza un grad mare de difuzie in mai multe cazuri;
- layerul non-liniar : aplicatiile paralele de S-boxes care au proprietati de nonliniaritate optime
- layerul de adaugare chei : un simplu EXOR al cheii in starea intermediara Inainte de prima etapa un layer de adaugere chei este aplicat. Motivatia acestei actiuni este urmatoarea : orice layer dupa ultima adaugare de cheie in cifru (sau inainte de prima in contextul atacurilor cunoscute) poate fi simplu eliminat fara a se cunoaste cheia iar acest lucru nu este util pentru securitatea cifrului. Pentru a face cifrul si inversarea sa mai similare in structura,layerul combinativ liniar al ultimei etape este diferit fata de cazul celorlaltor etape. se poate demonstra ca acest lucru nu sporeste si nici nu reduce securitatea cifrului in nici un mod. Aceast lucru este similar cu cel de absenta a operatiei de swap in ultima etapa a DES.

4.Specificatii:

Rijndael este un algoritm de criptare bloc-iterativ cu bloc si lungime a cheii variabile. Lungimea blocului si a cheii pot fi specificate independent la 128,192 sau 256 biti.
Rezultatele intermediare ale cifrului poarta numele de stare. Aceasta poate fi desenata ca o matrice patratica de bytes. Aceasta matrice are 4 linii iar numarul de coloane este egal cu lungimea blocului impartita la 32.

a) O etapa de transformare este impartita in 4 transformari. In pseudo C avem:
Round(State,RoundKey)
{
ByteSub(State);
ShiftRow(State);
MixColumn(State);
AddRoundKey(State,RoundKey);
}

Etapa finala a cifrului este diferita :
FinalRound(State,RoundKey)
{
ByteSub(State) ;
ShiftRow(State) ;
AddRoundKey(State,RoundKey);
}

In aceasta notatie, "functiile" (Round, ByteSub, ShiftRow, …) opereaza pe tablouri (arrays) spre care pointeri (State,RoundKey) sunt prevazuti.

b)Cheile din fiecare etapa sunt derivate din cheile cifrului cu ajutorul schemelor de chei. Aceasta consta in 2 componente :
- expansiunea cheilor
- etapa de selectare a cheilor

Principiul de baza este urmatorul:
- numarul total de biti al etapei de selectare a cheilor este egal cu lungimea blocului inmultita cu numarul de etape plus 1
- cheia cifrului este transformata intr-o cheie expandata
- cheile etapelor sunt preluate din aceasta cheie expandata astfel : cheia din prima etapa consta in primele Nb cuvinte, a doua consta din urmatoarele Nb cuvinte etc. unde Nb este egal cu lungimea blocului impartita la 32.

c)Cifrul Rijndael transpus in pseudo C arata astfel :
Rijndael(State,CipherKey)
{
KeyExpansion(CipherKey,ExpandedKey) ;
AddRoundKey(State,ExpandedKey);
For( i=1 ; i<Nr ; i++ ) Round(State,ExpandedKey + Nb*i) ;
FinalRound(State,ExpandedKey + Nb*Nr);
}

Expansiunea cheii poate fi facuta dinainte iar Rijndael poate fi specificat in termenii Cheii Extinse :
Rijndael(State,ExpandedKey)
{
AddRoundKey(State,ExpandedKey);
For( i=1 ; i<Nr ; i++ ) Round(State,ExpandedKey + Nb*i) ;
FinalRound(State,ExpandedKey + Nb*Nr);
}

5.Aspecte ale implementarii:

Algoritmul Rijndael este proiectat pentru a putea fi implementat eficient pe o gama variata de procesoare si configuratii hard. Noi ne vom concentra insa asupra procesoarelor pe 8 biti tipice actualelor Smart Cards si asupra celor pe 32 biti tipice PC-urilor.

a) procesoare pe 8 biti
Pe un procesor pe 8 biti Rijndael poate fi programat prin simpla implementare a diferitelor transformari de componente. Acest lucru este deschis pentru RowShift si Round Key addition. Implementarea functiei ByteSub necesita o tabela de 256 bytes.

b) procesoare pe 32 biti
Diferitii pasi ai etapei de transformare pot fi combinati intr-un singur set de tabele permitand o implementare foarte rapida pe procesoare cu lungimea cuvantului de 32 sau mai mult. Cele mai multe operatii din expansiunea cheilor pot fi implementate prin EXOR-uri pe 32 biti. Transformarile aditionale sunt aplicatiile S-box si un shift ciclic peste 8 biti. Acesta poate fi implmentat foarte eficient.

6.Tabele de performanta:

1.1. procesoare pe 8 biti

Algoritmul Rinjdael a fost implementat in limbajul de asamblare pentru doua tipuri de microprocesoare, care sunt reprezentative pentru Smart Cards folosite in zilele noastre.
In aceste implementari, Cheile Rotunde sunt calculate intre cercurile cifrului si de aceea , cheia de program se repeta pentru fiecare executie a cifrului. Acest fapt inseamna ca nu este nevoie de timp in plus pentru a seta cheia sau pentru a schimba cheia. De asemenea, nu este nevoie de timp in plus pentru setarea algoritmului. Sunt implementate doar primele operatii ale cifrului. Eforturile depuse in implementare se alte persoane au indicat faptul ca cifrul invers se roteste cu 30% mai incet. Datorita acestui fapt este explicata in implementare.

1.1.1 Intel 8051

Rijndael a fost implementat pe procesorul Intel 8051 folosind uneltele dezvoltate de Keil Elektronik. Urmatorul tabel prezinta timpuri de executie pentru anumite lungimi de cod(1 ciclu=12 perioade de oscilare):

--------------------------------------------------------------------------------------------------
Lungimea cheii Numarul de cicluri Lungimea codului
(128,128)a) 4065 cicluri 768 byti
(128,128)b) 3744 cicluri 826 byti
(128,128)c) 3168 cicluri 1016 byti
(192,128) 4512 cicluri 1125 byti
(256,128) 5221 cicluri 1041 byti
--------------------------------------------------------------------------------------------------


1.1.2 Motorola 68HC08

Rijndael a fost implementat pe microprocesorul lui Motorola 68HC08 folosind uneltele dezvoltate de P&E Microcomputer Systems. Timpul de executie, lungimea codului si ramii necesari pentru un numar de implementari sunt date in tabelul urmator. Nu a fost asteptata nici o imbunatatire a lungimii de cod.

--------------------------------------------------------------------------------------------------
Lungimea cheii Numarul de cicluri Lungimea codului Ramii necesari
(128,128)a) 8390 cicluri 919 byti 36 byti
(192,128) 10780 cicluri 1170 byti 44 byti
(256,128) 12490 cicluri 1135 byti 52 byti
--------------------------------------------------------------------------------------------------



1.2 procesoare pe 32 biti

1.1.2 Optimizarea ANSI C

Nu este acces la calculatoarele Pentium Pro. Viteza estimata pentru aceasta platforma, la inceput, a fost generata compiland codul cu EGCS si executandu-l pe un Pentium 200 MHz, utilizand linux. Oricum, de cand acel raport a fost publicat pentru prima oara, mai multe date suplimentare au devenit disponibile si cele publicate de Brian Gladman sunt date mai jos.
Figurile AES Cd sunt pentru ANSI C folosind NIST API. Figurile raportate de Brian Gladman sunt pentru procesoarele familiei Pentium Pro si Pentium || folosind o interfata mult mai eficienta. Aceste rezultate au fost obtinute cu ajutorul compilatorului Microsoft Visual C++, care furnizeaza instructiuni de rotatie mult mai rapide. Posibilitatea de a folosi aceste instructiuni cu codul in C furnizeaza performante substantiale castigate fara a aparea probleme importante de portabilitate, din moment ce multe compilatoare C ofera in zilele noastre facilitati echivalente. Figurile de viteza date in tabele prelucrate astfel incat sa fie similare cu cele care ar aparea pe o platforma de referinta Pentium Pro 200 MHg.
Setarea algoritmului nu necesita timp. Setarea cheii si schimbarea ei necesita exact acelasi timp: timpul pentru a genera cheia extinsa din cheia cifrului. Setarea cheii pentru cifrul invers necesita mai mult timp decat setarea cheii cifrului propriu zis.
Urmatorul tabel prezinta numarul de cicluri necesare pentru cheia extinsa:

--------------------------------------------------------------------------------------------------
cicluri AES CD (ANSI C) Brian Gladman(C++)
(lg cheii) Rijndael Rijndael -1 Rijndael Rijndael -1

(128,128) 2100 2900 305 1389
(192,128) 2600 3600 277 1595
(256,128) 2800 3800 374 1960
--------------------------------------------------------------------------------------------------

Cifrul si inversul necesita exact acelasi timp. Diferenta de performanta discutata in implementare este cauzata doar de diferenta in setarea cheii. Urmatorul tabel reda figurile pentru performantele cifrului si inversului, fara a tine cont de AES API:

--------------------------------------------------------------------------------------------------
lg cheii AES CD(ANSI C) Brian Galdman(C++)
viteza(Mbiti/sec) cicluri viteza(Mbiti/sec) cicluri
(128,128) 27.0 590 70.5 363
(192,128) 22.8 1125 59.3 432
(256,128) 19.8 1295 51.2 500
--------------------------------------------------------------------------------------------------

A fost acceptata cu recunostinta generoasa oferta din partea Cryptix de a produce implementarea in Java. Oricum, Cryptix nu ofera nici o figura de performanta. Estimarile noastre sunt bazate pe timpul de executie al codului KAT si MCT pe un Pentium 200 MHg, ruland sub Linux. A fost folosit compilatorul JDK1.1.1 Java. Tabelul urmator reda performantele implementarii in Java(nu se pot da estimari pentru setarea cheii sau a algoritmului):

--------------------------------------------------------------------------------------------------
lungime cheie viteza cicluri pt Rijndael
(128,128) 1100 Kbit/s 23.0 Kcicluri
(192,128) 930 Kbit/s 27.6 Kcicluri
(256,128) 790 Kbit/s 32.3 Kcicluri
--------------------------------------------------------------------------------------------------


7.Motivatia alegerii designului:

1.polinomul de inmultire m(x)
Polinomul m(x) (‘11B’) pentru inmultire in GF(2^8) este primul din lista polinoamelor ireductibile de gradul 8

2.S-box pentru ByteSub
Criteriul designului pentru S-box este inspirat de criptanaliza liniara si diferentiala pe de o parte si atacurile care folosesc manipulari algebrice pe de alta parte :
- inversabilitate
- minimizarea marii corelari intre combinatiile liniare de input si de output
- minimizarea marii valori in tabela EXOR
- complexitatea expresiei sale algebrice in GF
- simplicitatea descrierii

3.transformarea MixColumn
MixColumn a fost aleasa din spatiul transformarilor de 4 pe 4 bytes in conformitate cu urmatoarele criterii:
- inversabilitate
- liniaritate in GF
- putere mare de difuzie
- viteza pe procesoarele pe 8 biti
- simetrie
- simplicitate a descrierii

4.offseturile ShiftRow
Alegerea din toate combinatiile posibile a fost facuta dupa urmatoarele criterii:
- cele 4 offseturi sunt diferite si C0=0
- rezistenta impotriva atacurilor care folosesc diferentiale trunchiate
- rezistenta impotriva atacurilor patratice
- simplicitate

5.expansiunea cheilor
Expansiunea cheilor specifica derivarea din Round Keys in termenii Cipher Key. Functia sa este aceea de a asigura resistenta impotriva urmatoarelor atacuri:
- atacul in partea lui Cipher Key cunoscuta criptanalistului
- atacul in care Cipher Key este cunoscuta sau poate fi aleasa
- atacurile referitoare la chei (nu trebuie sa existe 2 Cipher Keys care sa aiba in comun o mare parte de Round Keys)

8.Securitatea:

In aceasta parte, prezentam scopurile de securitate setate pentru Rijndael. Un atac criptanalitic va fi considerat cu succes de designeri daca se demonstreaza ca un astfel de scop de securitate descrisa mai jos nu rezista.

2.1 Definitia conceptului de securitate

Pentru a formula scopurile noastre, este nevoie sa definim mai intai cateva concepte relative la securitate.

2.1.1 Setul posibil de cifruri pentru o lungime de cheie data

Daca lungimea blocului este v, atunci cifrul va genera V=2k intrari. Daca lungimea cheii este u, atunci ea defineste un set de U=2k permutari peste (0,1).

2.1.2 K-Securitate

Definitie: Un bloc de cifru este K-sigur daca toate strategiile posibile de atac pentru acesta au acelasi factor asteptat de munca si aceleasi necesitati de stocare ca pentru majoritatea blocurilor de cifr cu aceeasi dimensiune. Acesta trebuie sa fie cazul pentru toate posibilele modele de acces pentru adversari si pentru orice cheie prioritara de distributie. K-securitate este o foarte importanta notiune de securitate. Se poate observa foarte usor ca, daca una dintre urmatoarele slabiciuni apar la un cifru, nu se mai poate numi k-sigur :
- existenta atacurilor cheilor recuperate mai rapid decat o cautare minutioasa;
- proprietati sigure de simetrie in circuite(ex. proprietatea de complementaritate);
- neglijarea claselor ne-neglijabile ale cheilor slabe(ca si in IDEA);
- atacurile cheilor relative;
K-securitatea este in esenta o masura relativa. Este foarte posibil sa se poata construi un bloc cifru k-sigur cu blocuri si lungimi de chei de 5 biti. Lipsa de securitate oferita de o asemenea schema este datorita dimensiunii sale mici, nu datorita faptului ca schema esueaza sa prinda cerintele impuse de aceste dimensiuni. Este foarte clar faptul cu cat este mai lunga cheia, cu atat securitatea cere conditii mai inalte.

2.1.3 Cifruri ermetice

Este posibil de imaginat cifruri care sigur au anumite slabiciuni si totusi sa fie k-sigure. Un exemplu de o asemenea slabiciune ar putea fi un bloc cifru cu o lungime de bloc mai mare decat lungimea de cheie si o singura cheie slaba, pentru care circuitul cifrului este liniar. Detectarea folosirii cheii ar lua cel putin cateva criptari, iar daca s-ar verifica folosirea cheii ar lua doar o singura criptare.
Daca acest cifru ar fi folosit pentru el insusi, aceasta singura cheie slaba nu ar pune nici o problema. Pe de alta parte, daca ar fi folosit ca si o componenta intr-o schema mai larga, de exemplu functia de compresie in functia hash, aceasta proprietate ar putea introduce poarta, cale care sa genereze coliziuni puternice. Pentru acest motiv, vom introduce un nou concept de securitate, denumit sub termenul ermetic.
Definitie: Un bloc cifru este ermetic daca nu are slabiciuni care sa nu fie prezente pentru majoritatea blocurilor cifru cu acelasi bloc sau aceeasi lungime a cheii.Informal, un bloc cifru este ermetic daca structura sa interna nu poate fi exploatata in orice alta aplicatie.
Pentru toate lungimile de chei si de blocuri definite, intrebarile legate de securitate sunt daca cifrul Rijndael este:
- k-sigur;
- ermetic;
Daca Rijndael supravietuieste dupa intrebarile proprii, forta impotriva oricarui atac, cunoscut sau necunoscut, este la fel de asteptat ca de la un bloc cifru cu dimensiunile date.

9.Avantaje si limitari:

3.1 Avantaje

Aspecte legate de implementare:
- Rijndael poate fi implementat sa ruleze la viteze mult prea mari pentru un bloc cifru pe un Pentium Pro. Este o corelatie intre tabelele marime / performante;
- Rijndael poate fi implementat pe Smart Card intr-o mica cantitate de cod, folosind o mica cantitate de RAM si luand un mic numar de cicluri. Este o oarecare corelatie ROM / performante;
- transformarea rotunda este paralela prin design, un important avantaj pentru viitoarele procesoare si hard-urile dedicate;
- din moment ce cifrul nu efectueaza operatii aritmetice, arhitectura procesorului nu are inclinatie catre mic-mare indian;
Simplitatea disignului:
- cifrul are suport propriu in totalitate. Nu utilizeaza nici o alta componenta de criptare;
- cifrul nu isi bazeaza propria securitate, sau o parte din ea, pe obscuritate si pe interactiuni intre operatii aritmetice, nu foarte bine intelese;
- designul bine structurat al cifrului nu lasa loc pentru eventuale capcane ascunse;
Lungimea de bloc variabila:
- designul permite specificarea variantei cu lungimea de bloc si de cheie, impreuna, pe o raza de la 128 la 256 biti in pasi de 32 biti;
- desi numarul cercurilor Rijndael este fixat in specificare, poate modificat ca si un parametru in caz de probleme de securitate;

3.2 Limitari

Limitarile cifrului au legatura cu inversul sau:
- cifrul invers este mai putin potrivit sa fie implementat pe Smart Card decat cifrul insusi: necesita mai mult cod si mai multe cicluri (totusi, in comparatie cu alte cifruri, chiar si inversul este foarte rapid);
- in soft, cifrul si inversul sau folosesc coduri si / sau tabele diferite;
- in hard, cifrul invers poate doar partial sa refoloseasca circuitele care implementeaza cifrul;

10.Alte functionalitati:

In aceasta sectiune, vom mentiona cateva functii care pot fi executate cu blocul cifru Rijndael, altele decat criptarea.

4.1 MAC

Rijndael poate fi folosit ca si un algoritm MAC, folosindu-l ca si bloc cifru in algoritmul CBC-MAC.

4.2 Functiile hash

Rijndael poate fi folosit ca si o functie hash repetata, folosindu-l ca si o functie cerc. Aici este o posibila de implementare. Este recomandat sa se foloseasca o lungime de bloc si de cheie ambele egale cu 256 biti. Variabila lant va trece in "input" si mesajul de bloc trece in "cheia cifrului". Noua valoare a variabilei lant este data de vechea valoare EXORed impreuna cu iesirea cifrului.

4.3 Generatorul de numere pseudoaleatoare(PRNG)

Sunt mai multe metode in care Rijndael poate fi folosit sa formeze PRNG care satisface liniileghid, care sunt date pentru designul PRNG. Vom da un exemplu in care este folosit Rijndael cu o lungime de bloc de 256 si o lungime de cheie tot de 256.
Exista trei operatii:
Reset:
- cheia cifrului si starea sunt resetate la 0;
Samantarea:
- "bitii samanta" sunt colectati avand grija ca totalul lor sa aiba un minim de entropie. Ei sunt operati cu zerouri pana cand stringul rezultat are lungime multiplu de 256;
- o noua cheie de cifru este calculata criptand cu Rijndael un bloc de biti samanta folosind cheia cifru curenta. Aceasta este aplicata recursiv pana cand blocurile samanta sunt evacuate;
- starea este actualizata aplicand Rijndael, folosind noua cheie cifru;
Generarea numerelor pseudoaleatoare:
- starea este actualizata aplicand Rijndael, folosind noua cheie cifru. Primii 128 biti ai starii ies ca si numar pseudoaleator. Acest pas poate fi repetat de foarte multe ori.
Prin toate acestea AES:Rijndael este unul dintre cele mai puternic algoritm de cripatre .