Criptarea cu 3DES, Blowfish, Rijndael si RC4

Criptarea cu 3DES, Blowfish, Rijndael si RC4

(referat aditional programului PHP de trimitere/receptionare

de mesaje criptate)

Rezumat: Referatul prezinta cei 4 algoritmi folositi in programul de trimitere si receptionere de mesaje criptate. Sunt continute si referiri la istoria algoritmilor si unde sunt folositi in practica. Se prezinta in detaliu algoritmul DES, impreuna cu cateva definitii necesare. Deoarece ceilalti algorimi contin elemente comune cu DES, descrierea lor se va face pe scurt.

Cuprins

Introducere 1

Cifruri-bloc 1

Moduri de criptare 2

3DES 3

Istoric DES 3

Elemente teoretice pentru DES  3

Algoritmul DES 4

Obtinerea cheilor DES  5

Algoritmul DES efectiv  6

3DES 9

Blowfish 10

Rijndael 11

RC4 13

1. Introducere

Toti cei 4 algoritmi de criptare sunt algoritmi de criptare simetrica. Conform preceptelor criptografice, in criptarea simetrica este recomandat ca algoritmii sa fie publici (pentru a putea fi supusi evaluarii comunitatii stiintifice internationale si a se dovedi algoritmi robusti). Singurul lucru care trebuie sa fie secret este cheia.

3DES, Blowfish si RC4 sunt cifruri bloc (criptarea se face pe blocuri) iar Rijndael (sau AES) este un cifru sir (stream cipher). In paragrafele urmatoare se defineste cifrul bloc. In cazul steam cipherelor datele de intrare sunt criptati pe rand iar transformarile datelor de intrare succesive variaza in timpul criptarii. Un nume alternativ pentru stream-ciphere este cifru de stare deoarece criptarea fiecarui digit este dependenta de starea actuala. In practica digitii sunt biti sau bytes.

2. Cifruri-bloc

Def. - un cifru bloc (block cipher) este o functie E: V_n x V_n,astfel incat pentru fiecare cheie K Ê, E(P,K) este o mapare invertibila (functia de criptare pentru K) din V_n in V_n, scrisa E_K (P).Maparea inversa este functia de decriptare, scrisa D_K (C). C=E_K (P) este ciphertextul C, rezultat din criptarea plaintextului P sub K. K este cheia; Ê este spatiul cheilor format din toti vectorii V_k de k-biti; n este marimea in biti a blocurilor plaintextului.

2.1. Moduri de criptare 

Un block-cipher cripteaza blocuri de plaintext de marime n-biti fixa (de multe ori n=64). Pentru mesaje ce depasesc n biti, cea mai simpla varianta este de a imparti mesajul in blocuri de n-biti si de a le cripta separat. Acesta este modul de criptare ECB (Electronic Codebook). Exista mai multe moduri de criptare. Pentru programul nostru am folosit mereu modul CBC (Cipher-block Chaining), descris mai jos. Alte moduri folosite sunt CFB (Cipher feedback), OFB (Output feedback).

Modul de criptare CBC

Modul de criptare CBC presupune utilizarea unui vector de initializare format din n-biti, vector numit in cele ce urmeaza IV (initialization vector). E_K reprezinta functia de criptare a bloc-chiperului E parametrizat de cheia K, iar E_K^-1reprezintadecriptarea. Se presupune ca un plaintext x= x₁ x_t este format din blocuri de n-biti.

Algoritmul 1 (mod de criptare CBC)

Intrare: cheie de k-biti; vector de initializare IV de n-biti; blocuri de plaintext x₁, , x_t de n-biti fiecare.

Sumar: produce blocuri de ciphertext c₁, , c_t; decriptarea lor duce la obtinerea plaintextului.

Criptare: c₀ IV. Pentru 1 j ≤ t, c_j E_K (c_j-1 x_j

Decriptare: c₀ IV. Pentru 1 j ≤ t, x_j c_j-1 E_K^-1(c_j-1

Criptare Decriptare.

Figura 1 - Mod de criptare CBC

2. 3DES

2.1. Istoric

DES este cifrul selectat in 1976 ca Federal Information Processing Standard (FIPS) in SUA. La inceput a avut elemente secrete si a fost banuit de o "usa din spate-backdoor" pe care NSA (National Security Agency) ar fi avut-o in algoritm. Printre cei neconvinsi se aflau si Martin Helman si Whitfield Diffie. In timp insa a fos supus evaluarilor internationale si si-a dovedit eficientza. Datorita lui a evoluat mult cercetarea block-cipherurilor. DES mai apare si sub numele de DEA (Data Encryption Algorithm).

In prezent DES este considerat nesigur pentru majoritatea aplicatiilor. Asta in special datorita cheii de 56 biti. Trebuie specificat faptul ca desi cei ce de la IBM (care au propus cipherul) precum si ceilalti evaluatori initiali ai algoritmului au recomandat o cheie mai lunga. La recomandarea NSA, s-a optat pentru o varianta scurta, probabil tocmai pentru ca NSA sa poata descifra toate informatiile trimise folosind DES. Un alt element interesant in constructia DES sunt asa numitele cutii-S care au fost proiectate de IBM in anii 1970 conform criptanalizei diferentiale, desi aceasta a aparut in comunitatea stiintifica doar in anii 90. In 1998, un atac prin forta bruta a demonstrat ca algoritmul poate fi spart in mai putin de 24 de ore si astfel a aparut necesitatea unuia nou.

O varianta considerata sigura este forma 3DES (Triple-DES), desi si la adresa acestuia exista atacuri teoretice.

2.2. Elemente teoretice pentru DES

Designul lui DES este legat de doua concepte generale: ciphere produs si ciphere Feinstel. Fiecare presupune o iterare a unei secvente sau a unei rotatii de operatii.

Ideea de baza a unul cipher produs este de a construe o functie complexa de criptare prin compunerea catorva operatii simple care ofera prin complementaritate protectie (dar nu si individual). Operatiile include transpozitii, translatii (XOR) si transformari liniare, operatii aritmetice, multiplicare modulo si substitutii simple.

Def. - Un cipher produs combina una sau mai multe transformatii intr-o maniera care intentioneaza ca cipherul rezultat sa fie mai sigur decat componentele individuale.

Def. - O retea SP (substitutie-permutatie) este un cipher produs compus dintr-un numar de stagii, fiecare implicand substitutii si permutatii.

Figura 2 - retea SP

Multe retele SP sunt cifruri iterate conform definitiei urmatoare:

Def. - Un cifru-bloc (block-cipher) iterat este un bloc cipher care presupune repetitia secventiala a unei functii interne numite functie round. Parametrii include numarul rundelor r, marimea in biti a blocului n, marimea in biti k a cheii de intrare K de unde sunt derivate r subchei K_i. Pentru inversabilitate (care permite decriptare unica), pentru fiecare valoare K_i, functia round este o bijectie pe runda de intrare.

Def. - Un cifru Feistel este un cifru iterat care mapeaza un plaintext (L₀, R₀) de 2t-biti pentru blocurile de t-biti L₀ si R₀, pe un ciphertext (L_r, R_r), printr-un proces in r runde, unde r>=1. Pentru i ≤ r, runda i mapeaza dupa cum urmeaza: , unde fiecare sub-cheie este derivata din cheia K a cifrului.

De obicei intr-un cifru Feinstel, r>=3, si de cele mai multe ori este par. Figura 4 arata cum runde succesive ale unui cifru Feinstel opereaza pe jumatati alternative are ciphertextului, in timp ce cealalte raman constante.

3.3. Algoritmul DES

DES este un cifru Feinstel care proceseaza blocuri de plaintext de n=64 biti, producand blocuri de ciphertext de 64 de biti. Marimea efectiva a cheii secrete K este k= 56 biti; mai exact, cheia de intrare K este specificata ca fiind o cheie de 64 biti, 8 biti (bitii 8, 16, , 64) dintre acestia putand fi folositi ca biti de paritate. Cele 2⁵⁶ chei implementeza (cel mult) 2⁵⁶ dintre cele 2⁶⁶ de bijectii posibile pe blocuri de 64 de biti. O opinie generala este ca bitii de paritate au fost introdusi pentru a reduce marimea efectiva a cheii de la 64 la 56 de biti pentru a reduce intentionat costul unei cautari exhaustive a cheii cu un factor de 256 (de catre NSA, dupa cum am spus si in introducere).

Figura 3 - Intrare/Iesire DES

Algoritmul 3 da detalii complete despre DES. Urmeaza intai o privire de ansamblu. Criptarea are loc in 16 stagii sau runde. Din cheia de intrare K, sunt generate 16 subchei K_i de 48 de biti fiecare, cate una pentru fiecare runda. In fiecare runda sunt folosite 8 mapari S_i prin substitutii fixe (alese cu grija) de la 6 la 4 biti (cutii-S) numite colectiv S. Plaintextul de 64 de biti este impartit in jumatati de 32 de biti L₀ si R₀. Fiecare runda este echivalenta din punct de vedere functional, luandu-se intrari de 32 de biti L_i-1 si R_i-1 din runda anterioara si producandu-se iesiri de 32 de biti L_i si R_i pentru i ≤ 16, precum urmeaza:

ecuatiile (1) si (2)

Aici E este o permutare de expansiune fixa care mapeaza R_i-1 din 32 de biti in 48 de biti (toti bitii sunt folositi o data si cativa de doua ori). P este o alta permutare fixa pe 32 de biti. O permutare initiala de biti (IP) precede prima runda. Dupa ultima runda, jumatatile dreapta si stanga sunt permutate si in final sirul rezultat este bit-permutat de inversa lui IP. Decriptarea presupune aceeasi cheie si acelasi algoritm, dar cu subcheile aplicate rundelor interne in ordinea inversa.

Simplificat, putem spune ca jumatatea dreapta a fiecarei runde (dupa expandarea intrarii de 32 de biti la 8 caractere a cate 6 biti fiecare) indeplineste o subsitutie dependenta de cheie pe fiecare dintre cele 8 caractere, iar apoi foloseste o transpozitie de biti fixa pentru a redistribui bitii caracterelor rezultate pentru a produce iesiri de 32 de biti.

3.3.1. Algoritmul 2 Obtinerea cheilor DES

Intrare: o cheie de 64 de biti K= k₁ k₆₄ (inclusiv 8 biti de paritate).

Iesire: 16 chei de 48 de biti K_i , i

1. fie dupa cum urmeaza: pentru si pentru celelalte cazuri.
2. . T se reprezinta ca jumatati de 28 de biti. (se foloseste PC1 din Tabelul 1 pentru a se selecta bitii din K. .
Pentru i de la 1 la 16, se calculeaza K_i dupa cum urmeaza: (Se foloseste PC2 din Tabelul 1 pentru a selecta 48 de biti din concatenarea din C_i si D_i: inseamna shiftare circulara la stanga.

Tabelul 1 - Selectia bitilor pentru calcularea cheilor DES (PC1 si PC2)

Tabelul 2. - Permutarile initiale si inverse DES (IP si IP^-1)

Tabelul 3. - functiile round DES: expansiunea E si permutarea P

Algoritmul 3 Algoritmul DES efectiv

Intrare: plaintextul m₁ m₆₄; o cheie de 64 de biti K= k₁ k₆₄ (inclusiv 8 biti de paritate).

Iesire: ciphertextul C= c₁ c₆₄

1. (obtinerea cheii). Se calculeaza 16 chei de 48 de biti K_i din K (folosind algoritmul 1);
2. . Se foloseste IP din tabelul 2 pentru permutarea bitilor. Rezultatul se imparte in jumatatile stanga si dreapta de cate 32 de biti fiecare: .
3. (16 runde). Pentru i de la 1 la 16, se calcueaza si folosind ecuatiile (1) si (2) de mai sus, calculandu-se dupa cum urmeaza:

a)              Se expandeaza din 32 in 48 de biti, folosind E din tabelul 2. . Avem:

b)              . se reprezinta ca 8 siruri de caractere de 6 biti. .

c)              . (aici mapeaza pe pe linia de intrare de 4 biti r si coloana c a lui  din tabelul 3 unde este reprezentarea radix-2 a lui Astfel, arata r=1, c=13 si iesirea 5, pentru binarul 0101).

d)              . Se foloseste P din tabelul 3 pentru a permuta cei 32 de biti ai lui si a obtine .

4. . Se schimba blocurile finale .
. (se face transpunere folosind IP^-1 din tabelul 2; ).

Figura 4 - Functia interna f a lui DES

Figura 5 - Calea computationala DES

Tabelul 4 - Celebrele cutii S ale algoritmului DES.

3.4. 3DES (sau Triple-DES)

3DES este definit ca fiind format dintr-o criptare DES cu o cheie k1, o decriptare DES cu o cheie k2 si apoi inca o criptare DES cu o cheie k3.

C = DES_k3(DES^-1_k2(DES_k1(P))). Cheile k1, k2, k3 au 56 de biti fiecare. Asadar cheia pentru 3DES are 168 de biti dar din cauza unui atac posibil, are o lungime efectiva de 112 de biti. Exista si o varianta in care k1=k3, insa acest mod de folosire este mai susceptibil la atacuri. Problema cu 3DES este viteza. Designul DES a fost gandit pentru implementari hardware eficiente.. si de aceea 3DES aste un algoritm greoi de criptare. Blowfish de exemplu este de cateva ori mai rapid pentru un nivel echivalent de securitate.

4. Blowfish

Blowfish este un cifru bloc simetric. A fost propus in 1993 de catre Bruce Schneier si este in prezent inclus in multe produse ce necesita cifruri. Aceasta se datoreaza faptului ca Bruce Schneier nu a patentat algoritmul si a permis ca acesta sa poata fi folosit de oricine doreste. Blowfish a fost creat pentru a inlocui imbatranitul DES si pentru ca se dorea inlocuirea problemelor aduse de alti algoritmi.

Nu se cunoaste nici o metoda care sa "sparga" algoritmul, singura varianta fiind metoda fortei brute. Este un algoritm rapid in executie care insa are o amprenta in memorie de 4 kilobytes. Acest lucru il face de neutilizat in smartcarduri si embedded systems.

Algoritm (Blowfish)

Blowfish lucreaza pe blocuri de 64 biti si are o cheie cu lungimea intre 32 si 448 biti. Este un cifru Feinstel cu 16 runde (ca si DES) si foloseste cutii-S dependente de cheie (la DES cutiile S sunt fixe).

Figura 6 - Diagrama Blowfish.

In diagrama din figura 6 fiecare linie reprezinta 32 de biti. Algoritmul pastreaza doua siruri de subchei: sirul P de 18 intrari si patru cutii-S de 256 de intrari. Cutiile S accepta intrari de 8 biti si produc iesiri de 32 de biti. O intrare a sirului P este folosita la fiecare runda si, dupa runda finala, fiecare jumatate a blocului de date sufera o operatie XOR cu una dintre cele doua intrari P ramase nefolosite.

Figura 7 - Functia Feistel a lui Blowfish

Functia Feistel (F) a lui Blowfish imparte intrarile de 32 de biti in patru sferturi de opt biti si foloseste sferturile ca intrare pentru cutiile S. Iesirele sunt adunate modulo 2³² si XOR-ate pentru a produce apoi rezultatul final pe 32 de biti.

Deoarece Blowfish este o retea Feistel, el poate fi inversat simplu prin XOR-area P17 si P18 in blocurile de ciphertext si apoi prin folosirea intrarilor P in ordine inversa.

Algoritmul de obtinere a sub-cheilor Blowfish incepe prin initializarea sirului P si a cutiilor S cu valori derivate din cifrele hexazecimale ale lui pi (care nu contin un pattern clar). Cheia secreta este apoi XOR-ata cu intrarile din P in ordine (daca e necesar se cicleaza cheia). Apoi un bloc de 64 de biti plin cu 0 este criptat cu algoritmul. Ciphertextul rezultat inlocuieste P1 si P2. Ciphertextul este apoi din nou criptat cu noile sub-chei si P3 si P4 sunt inlocuite de noul ciphertext. Acest lucru continua, inlocuind intregul sir P si toate intrarile din cutiile S. In total algoritmul Blowfish va rula de 521 de ori pentru a genera toate subcheile (aproximativ 4KB de date sunt procesate).

5. AES (Rijndael)

Advanced Encryption Standard (AES), cunoscut si sub numele de Rijndael, este un cifru bloc adoptat ca un standard de criptare de catre guvernul SUA si este de asteptat sa fie folosit pe larg in intreaga lume la fel ca si succesorul sau DES. A fost adoptat de National Institute of Standards and Technology (NIST) in noiembrie 2001 dupa 5 ani de standardizare.

Cifrul a fost dezvoltat de catre doi criptografi belgieni, Joan Daemen si Vincent Rijmen si a fost trimis la procesul de selectie pentru AES sub numele de "Rijndael". Spre deosebire de DES, Rijndael este o retzea SP, nu o retzea Feistel. AES este rapid atat in software cat si in hardware, este relativ usor de implementat si necesita putina memorie.

Algoritm (AES)

AES opereaza pe blocuri fixe de 128 de biti si are o cheie de 128, 192 sau 256 biti. Majoritatea calculilor pentru AES sunt facute in domeniul finit. AES opereaza pe o matrice 4x4 de bytes, denumita stare. Pentru criptare, fiecare runda de AES (cu exceptia ultimei runde) consta din 4 stadii:

1. SubBytes - o substitutie non-lineara unde fiecare byte este inlocuit cu un altul conform cutiei S specifice.
2. ShiftRows - un pas de transpozitie unde fiecare linie a starii este shiftata ciclic un anumit numar de pasi.
3. MixColumns - operatiune de mixare care opereaza pe coloanele starii, combinand cei 4 bytes din fiecare coloana folosind o transformare liniara.
4. AssRoundKey - fiecare byte al starii este combinat cu cheia de runda; fiecare cheie de runda este derivata din cheia cifrului folosind un algoritm de obtinere a sub-cheilor.

Runda finala sare peste stadiul 3.

Pasul SubBytes

In pasul SubBytes, fiecare byte din sir este actualizat folosind o cutie S de 8 biti. Aceasta operatie furnizeaza non-liniaritatea cifrului.

Pasul ShiftRows

Pasul ShiftRows opereaza pe liniile starii. El shifteaza ciclic byte-ii din fiecare linie cu un anumit offset. Pentru AES, prima linie este lasata neschimbata. Fiecare byte al celei ce-a doua linii este shiftat cu unu la stanga. In mod similar, a treia si a patra linie sunt shiftate cu offseturi de 2 si respectiv 3. In acest fel, fiecare coloana a starii de iesire din pasul ShiftRows este compusa din bytes din fiecare coloana a starii de intrare.

Pasul MixColumns

In pasul MixColumns, cei patru biti ai fiecarei coloane a starii sunt cimbinati folosind o transformare liniara invertibila. Functia MixColumns ia patru bytes ca intrare si scoate patru bytes, si fiecare byte de intrare afecteaza toti cei patru bytes de iesire. Impreuna cu ShiftRows, MixColumn furnizeaza difuzie in cifru.

Pasul AddRoundKey

In pasul AddRoundKey, subcheia este combinata cu starea. Pentru fiecare runda, o subcheie este derivata din cheia principala folosind algoritmul de obtinere a cheii; fiecare subcheie are aceeasi marime ca si starea. Subcheia este adaugata prin combinarea fiecarui byte al starii cu byte-ul corespunzator al cheii folosindu-se XOR pe biti.

Pana in 2005 nu se cunosc atacuri cu succes asupra lui AES. In Junie 2003, guvernul SUA a anuntat ca AES poate fi folosit nu doar pentru aplicatii publice dar si pentru informatie secreta.

6. RC4

RC4 (sau ARCFOUR) este cel mai folosit software cifru-stream in protocoale precum SSL sau WEP. Din pacate RC4 nu se ridica la standardele inalte de securitate actuale si cateva metode de folosire a lui duc la criptosisteme foarte nesigure (inclusivWEB).

RC4 a fost proiectat in 1987 de catre Ron Rivest (de la RSA security). Desi in mod oficial numele sau este "Rivest Cipher 4", acronimul RC este de multe ori inteles ca venind de la "Ron´s Code".

RC4 a fost la inceput tinut secret, chiar si numele fiid patentat. Insa in Septembrie 1994, a aparut o descriere a sa pe o lista in internet si in curand a fost afisat in tot internetul. In prezent, din punct de vedere legal, implementarile sale "ne-oficiale" sunt legale, dar nu pot folosi numele de "RC4". De aceea este de multe ori referit ca "ARCFOUR". A devenit o parte comuna din WEP, WPA si SSL.

Algoritm (RC4)

RC4 genereaza un sir de biti pseudorandom (numit "keystream", sir-cheie) care, pentru criptare, este combinat cu plaintextul folosind XOR. Decriptarea se efectueaza in acelasi mod. Pentru a genera sirul, cifrul foloseste o stare interna care consta din doua parti:

1. O permutare a tuturor celor 256 de bytes posibili (numita "S" mai jos).
2. Doi pointeri de index de 8 biti (numiti "i" si "j").

Permutarea este initializata cu o cheie de marime variabila, in mod normal intre 40 si 256 de biti, folosind algoritmul de obtinere a cheii de mai jos. Odata ce acest lucru a luat sfarsit, sirul de biti este generat folosind algoritmul de generare pseudo-random.

Algoritmul de generare pseudo-random

Byte-ul de iesire este selectat prin cautarea valorilor S(i) si S(j), adunarea lor modulo 256 si apoi prin cautarea sumei in S; S(S(i)+S(j)) este folosita ca un byte in sirul-cheie K.

Pentru atatea iteratii cat este nevoie, algoritmul modifica starea si scoate cate un byte al sirului-cheie. In fiecare iteratie, algoritmul incrementeaza i-ul, adauga valoarea S pointata catre i la j, interchimba valorile S(i) si S(j), si apoi scoate valoarea lui S in locatia S(i)+S(j) (modulo 256). Fiecare valoare a lui S este schimbata cel putin o data la fiecare 256 de iteratii.

Pseudocodul:

i := 0
j := 0
while GeneratingOutput:
i := (i + 1) mod 256
j := (j + S[i]) mod 256
swap(S[i],S[j])
output S[(S[i] + S[j]) mod 256]

Algoritmul de obtinere a cheii

Algoritmul de obtinere a cheii este folosit pentru a initialize permutarea din sirul "S". "l" este definit ca numarul de bytes din cheie si poate fi in zona 1 ≤ l ≤ 256, in mod normal intre 5 si 16, corespunzator unei chei de lungime intre 40 si 128 de biti. In primul rand, sirul "S" este initializat. S este apoi procesat prin 256 de iteratii intr-un mod similar cu algoritmul de generare pseudo-random dar si adauga in acelasi timp bytes ai cheii.

Pseudocodul:

for i from 0 to 255
S[i] := i
j := 0
for i from 0 to 255
j := (j + S[i] + key[i mod l]) mod 256
swap(S[i],S[j])

Implementarea

Multe cifruri-stream sunt bazate pe linear feedback shift registers (LFSR) si prin urmare sunt foarte eficiente in hardware, lucru care nu se poate spune despre implementarile software. Insa designul lui RC4 este diferit si este ideal pentru implementari software deoarece necesita doar manipulari de marimea unui byte. Foloseste 256 de bytes pentru sirul de stare, de la S(0) la S(255), n bytes de memorie pentru cheie, de la key(0) la key(n-1), si variabilele integer i, j si k. Efectuarea unui modulo 256 se poate face cu un AND bitwise cu 255.