Teza de licenta [629242]

Universitatea ”A.I.Cuza” Iasi
Facultatea de Informatica
Teza de licenta
Alina-Elena BRINZA
Criptografie si Securitate
Generarea, derivarea, schimbul si
managementul de chei
Indrumatorul de licenta: Ferucio Laurentiu Tiplea
Specializarea: Criptografie si Securitatea informatiei
Iasi, Romania, Iulie 2017

Contents
Introduction 3
1 Necesitate in contextul protocoluilui SSL/TLS 4
1.1 Scurt istoric si context . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Initiere in termeni ciptografici si de securitate . . . . . . . . . . . 5
1.2.1 Sistem de criptare / Criptosistem . . . . . . . . . . . . . . 5
1.2.2 Securitate . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.3 Criptografie simetrica . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Criptografie asimetrica / cu chei publice . . . . . . . . . . 6
1.2.5 Bit Security . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.6 Securitate IND-CPA . . . . . . . . . . . . . . . . . . . . . 7
1.2.7 Constructie scheme IND-CPA . . . . . . . . . . . . . . . . 7
1.2.8 Functii hash . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.9 Numar random . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Evolutie intr-o axa a timpului . . . . . . . . . . . . . . . . . . . . 8
1.4 SSL/TLS – scurta prezentare a protocolului . . . . . . . . . . . . 10
1.4.1 SSL&TLS: Autentificarea . . . . . . . . . . . . . . . . . . 11
1.4.2 SSL&TLS: Confidentialitatea . . . . . . . . . . . . . . . . 11
1.4.3 SSL&TLS: Handshake . . . . . . . . . . . . . . . . . . . . 11
2 Generarea cheilor 12
2.1 Generarea cheilor simetrice . . . . . . . . . . . . . . . . . . . . . . 1 2
2.2 Generarea cheilor asimetrice . . . . . . . . . . . . . . . . . . . . . 1 3
2.3 Generatori pseudo-random . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Functii pseudo-random . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 RC4 – Generator Pseudo Random . . . . . . . . . . . . . . . . . . 14
2.5.1 RC4: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.6 AES & DES – Functii Pseudo Random . . . . . . . . . . . . . . . 18
2.7 Bune practici si standarde in generarea cheilor . . . . . . . . . . . 18
3 Derivarea cheilor 19
3.1 Descriere generala a KDF(key derivation function) . . . . . . . . . 19
3.2 PBKDF2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 HKDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.4 ConcatKDFHash – ConcatKDFHMAC . . . . . . . . . . . . . . . 24
3.5 X963KDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.6 KBKDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.7 Scrypt KDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Conclusion 27
Bibliography 28
List of Tables 29
List of Abbreviations 30
1

Attachments 31
2

Introduction
3

1. Necesitate in contextul
protocoluilui SSL/TLS
1.1 Scurt istoric si context
Necesitatea existentei si studierii generarii, derivarii, schimbului si managemen-
tului de chei este argumentata de asigurarea securitatii in formatice peste diverse
protocoale de securitate, unde putem aminti de:
•SSL – Secure Socket Layer (nivelul transport)
•TLS – transport Layer Security (nivelul transport)
•IPsec – Internet Protocol cu elemente de securitate (nivelu l retea)
•HTTPS – Hypertext Transfer Protocol cu elemente de securitate (nivelul
aplicatie)
•PGP/S-MIME – Pretty Good Privacy / Multiple Internet Mail Ex tensions
cu elemente de securitate
•SSH – Secure Shell
Cele doua domenii arii ce stau la baza unui sistem compact si s igur sunt Crip-
tografia si Securitatea informatiei. Cea din urma este cladi ta pe primitivele crip-
tograficesialgoritmicriptografici,ceseaflaintr-ocontin uadezvoltaresicercetare,
punand bazele principiilor securitatii informatice:
•Integritate: protejarea informatiilor de posibile modific ari pe care unele
parti neautorizate le pot aduce
•Confidentialitate: protejarea datelor in expunerea la part i neautorizate
•Autenticitate: asigurarea accesului partilor autorizate l a informatii
•Controlul accesului: acces restrictiv bazat pe reguli, pen tru diferite parti
ale sistemului
•Securitatea in retea: masuri hardware si software pentru pr otectia retelei
•Managementul securitatii: generare, stocare, schimb de ch ei si securitate
intre parti
•Disaster recovery (Recuperare de date) : recuperarea datel or pierdute in
caz de atac
Pentru a putea intra in termeni stiintifici si exacti, ne prop unem sa inintiem citi-
torul intr-o scurta, dar foarte importanta, introducere in criptografie.
4

Odata cu dezvoltarea industriei si a automatizarii, oameni i de stiinta si cerc-
etatorii si-au pu problema securitatii datelor personale ( ale unui individ, grup de
indivizi, companie etc.).
Dupa Primul Razboi Mondial, incep asadar miscari masive in d ezvoltarea crip-
tografiei iar odata cu cel de-al Doilea Razboi Mondial, incep sa fie construite
primele masini de criptare: Enigma, Hagglliu (masini de crip tat prin substitutii),
desi semne teoretice de avansare in acest domeniu au aparut i n anii 1900 cand
Vernan propune o metoda de criptare de tip sir:
b1, b2, b3,.., bn⊕
k1,k2,k3,..,kn=
c1,c2,c3,..,cn
17 ani mai tarziu, acelasi om de stiinta demonstreaza ca schi mbarea random
(aleatoare) a cheii k1, k2, k3,.., kn de la text la text, aduce securitate absolu-
ta, iar in 1948 Shannon confirma ca schema lui Vernan atinge ”s ecret perfect”
=EntropieInformationala.
1.2 Initiere in termeni ciptografici si de securi-
tate
In acest scurt rezumat a ceea ce defineste domeniul criptogra fic, ne propunem
sa notam cele mai importante notiuni, ce vor fi aduse aminte ul terior, cat si sa
reprezentam pe o axa a timpului, evolutia si numele marcante in domeniu.
1.2.1 Sistem de criptare / Criptosistem
FieMo multime finita de mesaje (plaintext), |M|>1.
Un sistem de criptare peste Meste un 3-uplu S=(G,E,D) unde:
1.G= generator random de chei de criptare ( K= multimea cheilor de
criptare)
2.E= algoritm probabilist (executat de mai multe ori peste acelasi mesaj
m, output-ul c poate fi diferit. Pornind de la o cheie k si un mes aj m,
genereaza un criptotext c = E(k,m).
3.D= algoritm determinist de decriptare care, pornind de la un criptotext c
ǫCsiocheiekǫ Kdescopera mesajul initial m = D(k,c).
•Obs!Orice schema trebuie sa satisfaca proprietatea de corectit udine.
5

•Obs!Orice sistem de criptare este caracterizat prin trei distri butii de
probabilitate peste spatiile M,KsiC:
–O distributie de probabilitate peste M: indusa natural de alegerea
mesajelor care se cripteaza. P(m) = probabilitatea cu care e ste ales
mesajul m pentru a putea fi criptat.
–O distributie de probabilitate peste K: P(k) = probabilitatea cu care
este generata cheia k pentru a putea fi utilizata la criptare.
–O distributie de probabilitate peste C: indusa de distributiile
explicate anterior cat si de algoritmul de criptare E.
P(c/m) = probabilitatea ca c sa fie obtinut cu algoritmul de cr iptare care
primeste la intrare mesajul m.
P(c) =/summationtext
mP(c/m)·P(m)
P(m,k) = P(m)·P(k) unde P(m) si P(k) sunt distributii independente,
∀k,c,m,P (k)>0,P(c)>0,P(m)>0.
1.2.2 Securitate
Definita de doi parametri:
1. Indistingibilitate: fie m1, m2, |m1|=|m2|si c un criptotext = >
P(m1|c)≈P(m2|c)
2. Non-maleabilitate: fie m1 −> c1, si m2−> c2 un adevarsar, sistemul
este maleabil.
1.2.3 Criptografie simetrica
FieSun 3-uplu de forma ( G,E,D).
•G= algoritm probabilist de complexitate timp polinomiala care, pornind
de la parametrul de securitate λ, genereaza k <−G(λ).
•E= algoritm probabilist care, pornind de la o cheie k, si un mesaj m,
genereaza un criptotext c <−E(k,m).
•D= algoritm determinist de complexitate timp polinomiala care, pornind
de la o cheie k si un criptotext c, genereaza m <−D(k,c).
Obs!∀kǫG(1λ),∀mǫM, cǫE(k,m), m=D(k,c),λ=parametru de securitate, = >
|K|= f(λ),M=0,1l(λ), l=polinom, l( λ)≥λ
1.2.4 Criptografie asimetrica / cu chei publice
O schema de criptare cu chei publice este un sistem S= (G,E,D) unde:
•G= un algoritm probabilist de complexitate timp polonimiala ,G(1λ)
genereaza perechi de chei ( pk,sk).
•E= c<−E(pk,m)
6

•D= algoritm determinist, complexitate timp polinomiala , m<−D(sk,c)
Determinarea lui skpornind de la pksi 1λdevine o problema intractabila. De
asemenea, pkpoate fi facuta public fara a afecta in vreun fel securitatea.
1.2.5 Bit Security
Daca schema Sasigura indistingibilitate fata de adverasur pasiv = >niciun
algoritm probabilist nu poate decide o proprietate calcula bila polinomial asupra
mesajului de la care provine criptotextul = >securitate semantica.
1.2.6 Securitate IND-CPA
Presupunand ca avem un adversar activ, putem distinge dou ti puri de atacuri:
1. CPA (chosen plaintext attack) : adversarul poate obtine c riptarea pentru
un text/un numar de plaintexte alese de el.
2. CCA (chosen ciphertext attack) : adversar ce inglobeaza u n adversar
CPA, iar in plus poate obtine plaintextul unor criptotexte al ese de el.
1.2.7 Constructie scheme IND-CPA
Schemele IND-CPA se pot construi in doua modalitati. Fie prin PRF (functii
pseudo random) sau prin PRG (generatori pseudo random).
GENERATORI PSEUDO-RANDOM:
G−−−> x−−−>A
Un−−−> x−−−>A
Avand aceste relatii, ne punem urmatoarea intrebare: X este g enerat de Gsau
deUn?
FUNCTII PSEUDO-RADNOM:
Multimea de functii −−−>extragem Fk−−−>g−−−>A
Multimea tuturor functiilor −−−>extragem un f random uniform −−−>g
−−−>A
g =Fk|g=f
Avand aceste relatii, ne punem urmatoarea intrebare: Coinci de g cuFksau cu
f?
O schema de criptare simetrica S=IND-CPA este sigura daca pentru orice
algoritm Aavem:
|P(PrivCPA
A,S(λ) = 1)−1/2|este functie neglijabila in λundePrivCPA
A,S(λ) este
experimentul pentru adversarul A.
Exemple scheme :
•OTP+PRF
•ECB (Electronic Chainblock)
•CBC (Chaining Block)
•OFB (Offset Block)
7

•CTR (counter)
•CBC-MAC (CBC cu Message Authenticating Code)
•XCBC-MAC (XCBC cu Message Authenticating Code)
•Nested-MAC (Nested Message Authenticating Code)
1.2.8 Functii hash
O functie hash se defineste astfel: f:0,1∗−>0,1lunde l≥1 fixat.
Proprietati ale functiilor hash :
1. Rezistenta la coliziuni:
•intractabil a determina m1,m2ǫ0,1∗,m1/ne}ationslash=m2 astfel incat
h(m1)=h(m2), (m1,m2)=coliziune.
•datm1 sa fie intractabil a determina m2/ne}ationslash=m1a.i.(m1,m2)= coliziune
2. Functii one-way:
•f este usor de calculat dar greu de inversat
•dat yǫ0,1leste intractabil a determina x, f(x)=y.
Aplicatii ale functiilor hash: intergitatea mesajelor, sem naturi digitale .
1.2.9 Numar random
Domeniile Critpografie si Securitatea informatiei , folosesc frecvent conceptul de
numar random. (once = ⇒number once used). Extinzand, putem afirma ca o
secventa random este o secventa de numere random, unic utili zata.
al,a2,…,ak⇒ak+1nepredictibil din secventa generata anterior.
Un numar este random daca are proprietati statistice ”bune” ( test statistic
≥0.70).
O secventa random trebuie sa asigure impredictibilitate fo rward si backward.
1.3 Evolutie intr-o axa a timpului
Securitatea impreuna cu notiunile criptografice (schimb, g enerare, derivare,
management de chei) s-a impus ca modalitate de prevenire a:
1. Scurgerii de informatii catre persoane neautorizate (confidentialitate).
2. Modificare de date de catre persoane neautorizate (integritate).
3. Respingerea folosirii informatiilor proprii (denial of use, exemplu:
DDOS)(valabilitate).
In axa ce urmeaza, vom pune accentul atat pe punctele de inter es in evolutia
securitatii informatice cat si a criptografiei, incepand cu anul 1970 si pana in
prezent.
8

Table 1.1 Event
1970•Bell La Padula gandeste o politica de determinare al control ului
accesului pentru domeniul militar.
1970•Retelele Feistel = ⇒un bloc de mesaje este criptat repetand asupra lui
un numar de transformari identice, parametrizate dupa chei de sesiune.
1970•Se pune accentul pe securitatea computerelor si pe indeplin irea
fiabilitatii.
1976•Diffie, Hellman, Merkle – aduc o solutie pentru distributia de c hei.
1977•Diffie, Hellman, (Merkle), criptosistem bazat pe problema ruc sacului.
1978•DES – primul criptosistem construit pe baza retelelor Feist el
1978•Rivest, Shamir, Adleman (RSA) – primul sistem de cheie publica
construit, luand nastere criptografia cu chei publice, rezo lvandu-se
astfel problema schimbului de chei.
1980•Se trece de la ideea securizarii computerelor la securizare a informatiilor
stocate pe acestea. Se pune accentul pe confidentialitate si
izolarea datelor .
1984•Modelul schematic ce se situeaza intre TG (Take Grant) si ACM .
1984•Apare criptografia bazata pe identitate.
1990•Mediul internetului si includerea calculatoarelor in acea sta intr-un mod
sigur. Se pune accentul pe integritate si valabilitatea datelor .
1996•Schneier pune accentul pe nepredictibilitate si nereproductibilitate in
timp fezabil in ceea ce priveste generarea de chei.
1998•masina cu mai mult de 5000 procesoare legate in paralel, comp usa
pentru un atac brute-force asupre DES.
2000•Internetul devine ceva indispensabil. Se pune problema sec urizarii
datelor dar de aceasta data si in retea. Se pune punctul pe
non-repudiere , posesia datelor si autenticitatea datelor.
2001•Criptare bazata pe reziduuri patratice, criptare bazata pe aplicatii
biliniare.
2001•Atac asupra RC4.
2002•AES inlocuieste DES care fusese decriptat in 1998 in 22 ore.
2002•Primalitate poate fi rezolvata polinomial (AKS).
2010•Plus de securitate adusa in primul rand datorita exploziei r etelelor
sociale: cyber security , transparenta , eficientizare costuri ,
eficientizarea securizarii .
2014•Atac puternic asupra RC4 (*dezvoltat in capitolul urmator)
9

1.4 SSL/TLS – scurta prezentare a protocolului
SSL=Secure Socket Layer si TLS=Transport Layer Security sunt protocoale ce
asigura securitatea comunicarii in retea.
Aplicatiile de baza ale acestor protocoale sunt: cautare pe b rowser, posta
electronica (e-mail), mesagerie instanta etc.
Conexiunea privata este asigurata de criptarea simetrica f olosita in criptarea
datelor trimise, ajutata de ceea ce numim TLS handshake unde cheile sunt
generate la fiecare noua conexiune, pe baza unui secret parta jat, ce asigura
securitate fata de ∀adversar, ce doreste modificarea / coruperea datelor.
∀atacuri pot fi asadar detectate, asigurandu-se confidential itate, integritate si
valabilitate.
Pasi importanti:
1. Key Exchange Key agreement :
(Schimb de chei si agreare de chei criptografice)
Inainte de a avea loc transferul de date, partile cad de comun acord
asupra unei chei de criptare K, generata de generatori precu m:
RSAPub K,RSAPriv K, Diffie Hellman efemer ,
Diffie Hellman pe curbe eliptice , Diffie Hellman efemer pe curbe eliptice ,
Diffie Hellman anonim , etc.(TLS RSA, TLD DH, TLS DHE, TLS ECDH)
dintre care doar Diffie Hellman efemer (TLS DHE) si TLS ECDH asigura
secret forward si nu sunt vulnerabile la atacul Man-In-The- Middle.
2. Cipher:
(Algoritmi ce prevad atat criptare cat si decriptare)
In cadrul acestui pas amintim de: AES, DES, CBC, SEED CBC, RC2,
CBC pentru block cipher si de RC4 pentru stream cipher.
3. Integritatea datelor:
•MAC (Message Authentication Code) : folosit pentru integrit atea
datelor
•HMAC : folosit pentru CBC
•AEAD : folosit pentru criptare autentificata
10

Cum asigura SSL&TLS integritate, autenticitate si confiden tialitate?
•In timpul autentificarii, atat a clientului cat si a serverul ui, este necesara
criptarea datelor cu una din cheile din perechea de chei sime trice, si
decriptate cu cealalta cheie ramasa.
1.4.1 SSL&TLS: Autentificarea
AUTENTIFICARE:
Pentru autentificarea serverului:
Clientul foloseste PubKpentru a cripta informatiile care sunt necesare pentru a
calculaSecret K. Serverul poate genera o cheie secreta doar daca poate sa
decripteze informatiile cu PrivK.
Pentru autentificarea clientului:
Serverul foloseste PubKdin certificatul clientului pentru a decripta informatile
pe care clientul de trimite (certificatul). Schimbul de mesa je criptate cu Secret K
(Client ”finished”, Server ”finished”), confirma ca autentifi carea a fost completa.
Obs1Daca chiar si unul din pasii de autentificare de mai sus se term ina cu esec,
SSL handshake esueaza si sesiunea se termina.
Obs2Schimbul de certificate digitale in timpul SSL/TLS handshak e este o parte
a procesului de autentificare.
1.4.2 SSL&TLS: Confidentialitatea
CONFIDENTIALITATE:
•SSL&TLS foloseste o combinatie de criptari simetrice si asi metrice pentru
a asigura securitatea mesajelor.
•In timpul handshake-ului, clientul SSL&TLS si serverul, st abilesc un
algoritm de criptare Asi o cheie secreta Secret Kunica (per sesiune).
•Toate mesajele transmise intre clientul SSL&TLS si server s unt criptate
folosind algoritmul agreat A, asigurand faptul ca mesajele raman private
chiar si atunci cand sunt interceptate.
•Deoarece SSL&TLS foloseste criptare asimetrica la transpo rtul cheii
secreteSecret K, nu apare problema distributiei de chei.
1.4.3 SSL&TLS: Handshake
11

2. Generarea cheilor
In capitolul anterior am descris pe scurt, la nivelul protoc olului SSLTLS, faptul
ca generarea de chei se realizeaza pe baza unor algoritmi si g eneratori.
Capitolul 2 este menit sa prezinte tehnici de generare a chei lor atat in
schemeledecriptaresimetrica cat si in schemeledecriptareasimetrica .
Pentru a argumenta inca o data necesitatea studierii acestu i subiect, aducem
aminte de cateva aplicatii ale cheilor:
•semnaturi digitale
•verificarea de semnaturi digitale
•autentificare
•criptarea / decriptarea datelor
•transportul cheilor
•agrearea de chei
Criptografia asigura la nivelul generarii de chei, si mai dep arte in derivarea si
schimbul acestora, faptul ca informatia nu a fost modificata dupa ce a fost
trimisa, autentificand detinatorul informatiei, conserva ndu-se astfel principiile
de integritate, non-repudiere etc.
2.1 Generarea cheilor simetrice
Cheile simetrice sunt chei private PrivKce trebuie sa fie generate de una sau
mai multe entitati care o vor partaja pe aceasta, sau de o auto ritate centrala,
PrivKfiind ulterior utilizata pentru: criptare sau decriptare (AE S), generare de
MAC-uri (AES) [message authentication code], derivare de ch ei aditionale, etc.
PrivK−−−−−−−−− > entitate 1,entitate 2,…, entitate n
Entitatile pot/sunt autorizate se aduca modificari asupra c heii.
12

Mai jos vom lista o serie de utilizari / operatii posibile cu c heile simetrice,
operatii ce pot fi facute folosind: functii sau generatori ra ndom, pseudo-random,
functii de parole sau PIN, standarde de generare, generare de chei din alte chei,
key agreement etc.
•generarea directa a cheilor simetrice
•distribuirea cheii simetrice generate
•generare folosind scheme de key-management
•chei simetrice derivate din chei partajate
•chei simetrice derivate din parole
•chei simetrice rezultate din combinarea mai multor chei cu a lte date au
informatii
•inlocuirea cheilor simetrice
2.2 Generarea cheilor asimetrice
Cheile asimetrice sunt perechi de chei ( PubK,PrivK) ce sunt detinute de o
singura entitate, denumita si proprietarul perechii de che i, si sunt generate fie
de entitate fie de catre autoritatea centrala.
(PubK,PrivK)————————————————–entitate
Listam si aici cateva utilizari sau operatii posibile cu che ile asimetrice:
•pereche de chei pentru semnaturi digitale : ofera autenticitatea originii,
intergitatea datelor si non-repudierea (DSA, RSA, ECDSA).
•pereche de chei pentru stabilirea cheii : stabilirea unei chei presupune atat
key agreement (functie de informatii ale tuturor participantilor astfel incat
predeterminarea cheii sa fie imposibila tuturor) cat si key t ransport (o
entitate alege valoarea pentru cheia secreta Secret Kdupa care o distribuie
in mod sigur unei alte entitati) – RSA
•distribuirea perechii de chei : cheia privata PrivKtrebuie tinuta secreta,
cheia publica PubKpoate fi facuta publica insa intr-o maniera ce asigura
intergitatea.
Dupa aceasta scurta introducere, prezentam cititorului ur matoarele subiecte de
interes in acest capitol. Vom aborda generatorii si functii le pseudo-random,
criptosistemele stream si criptosistemele bloc, vom expli ca exemple de generare
de chei simetrice si asimetrice, dupa care vim incheia cu cat eva standarde si
bune practici in generarea cheilor.
13

2.3 Generatori pseudo-random
PRG (pseudo-random generator) algoritm determinist de com plexitate timp
polinomiala, care, pornind de la un seed, o samanta, de dimensiune k, s ǫ0,1k,
genereaza siruri wi, iǫ[1,l(k)].
Generatorul trebuie sa fie construit de asa natura incat unui posibil adversar A
sa ii fie indistingibil daca wiǫ0,1ka fost generat de un generator PRG sau daca
a fost ales random uniform din 0 ,1l(k).
0,1k−−−−−−−−−− >G(s)−−−−−−− >w
0,1l(k)−−−−−−−−−−−−−−−−−−− >w
A(w)= ?−−−−−−− >0,1k−−−−−−−− >PRG
A(w)= ?−−−−−−− >0,1l(k)−−−>random uniform
Definitie ! Fie n≥1 un numar natural ( ǫN) si l un polinom ( ǫP). Numim
generator pseudo-random (PRG), un algoritm determinist de complexitate timp
polinomiala (DPT) cu factorul de expansiune l daca:
1. l(n) n,∀nǫN
2. pentru∀algoritm PPT D, are loc si este neglijabila.
P(D)=1: r←0,1l(n))- P(D(G(s))=1: s←0,1n
•D(r)=1→D= un algoritm de test care decide daca r este ales random
uniform din 0 ,1l(n).
•D(G(s)=1→D= un algoritm de test care decide daca G(s) este ales
random uniform din 0 ,1l(n), sǫ0,1n.
2.4 Functii pseudo-random
Teorema ! Feste functie pseudo-random (PRF), atunci inseamna ca schem a
MAC (Message Authentication Code) este rezistenta la falsifi care.
Teorema ! DacaFeste o functie pseudo-random (PRF), atunci CBC-MAC este
rezistenta la falsificari.
Teorema ! DacaFeste functie pseudo-random (PRF), atunci X CBC-MAC este
rezistenta la falsificari.
2.5 RC4 – Generator Pseudo Random
Schema MAC:
1. F=(Fk)→o functie PRF (pseudo-random)
Presupunem Fk: 0,1n→0,1n
G = generator ce alege random uniform o cheie k
MAC(k,m) = Fk(m), unde k = cheie, m = mesaj, t = Fk(m)
Vrt(k,m,t) = 1⇔t =Fk(m)
14

2. F=(Fk)→o functie PRF (pseudo-random)
S=(G, MAC, Vrf)
G = generator ce alege random uniform o cheie k pentru F; presu punem
ca n este multiplu de 4
Fk: 0,1n→0,1n
m=m1,m2,.., ml,|mi|=n/4
l se scrie pe n/4 biti
Tag-ul pentru mise obtine prin : r ←0,1pow(n/4),ti=Fk(r||l||[i]||
mi)
t = (r,t1, …,tl) reprezinta tag-ul pentru m.
Dezavataje: tag scurt, pentru mesaje de lungime ∤(n/4)→padare.
Schema CBC-MAC:
1. Rezolva problema tag-urilor pentru mesaje de lungime var iabila fara
padare.
Presupunem
m = ..m1…….m2…….ml
0..0→⊕→⊕→ …→⊕
……….↓…..↓………..↓
……….t1 …t2 ……..tl
MAC(k,m)= tl
2. X CBC-MAC:
F=(Fk)→o functie PRF (pseudo-random)
3 chei:K1,K2siK3; ultimele doua fiind pentru padare
Cazul 1:|ml|=|ml−1|→nu necesita padare. tl=Fk(tl−1⊕ml⊕k2)
Cazul 2:|ml−1|>|ml|→se padeaza cu mlcu 10…0 tl=Fk(tl−1⊕ml
10..0⊕k3)
In cadrul generatorilor pseudo−random, putem aminti de RC4, criptosistem
stream mentionat in cadrul capitolului anterior, la sectiu nea protocolului
SSL&TLS, iar in cadrul functiilor pseudo−randomamintim de AES si DES,
criptosisteme bloc, mentionate de asemenea in cadrul capit olului anterior la
sectiunea protocolului SSL&TLS.
2.5.1 RC4:
RC4 (Rivest Cipher 4), este un criptosistem stream (de chei s imetrice) in care
plaintext-ul este combinat cu un numar pseudo-random, astf el incat fiecare bit
din plaintext impreuna cu bitul corespunzator al cheii, dau bitul corespunzator
criptosistemului.
RC4 mai este cunoscut si sub numele de ARC4 sau ARCFOUR.
15

Algoritmul :
i:=0
j:=0
while Generating Output:
—–i:=(i+1) mod 256
—–j:=(j+S[i]) mod 256
—–swap value of S[i] and S[j]
—–k:=S[S[i]+S[j]) mod 256
—–output k
endwhile
CRIPTAREA :
..Plaintext.. ⊕ ..Keystream..
→ ..Ciphertext..
EXEMPLU :
→Reset i=j=0, S=2,1,3,0
→i=i+1=1
→j=j+S[i]=0+1=1
→Swap S[i] and S[j] : S=2,1,3,0
→Output z=S(S[i]+S[j])=S[2]=3
→z=3 (0000 0011)
→H 0100 1000
→3 0000 0011⊕
→−−−−−−
→0100 1011
→i=1, j=1, S=2,1,3,0
→i=i+1=2
→j=i+S[i]=1+3 (mod 4) = 0
→Swap S[i] and S[j] : S=3,1,2,0
→Output z=S(S[i]+S[j])=S[1]=1
→z=1 0000 0001
→0100 1001
→0000 0001⊕
→−−−−−−
→0100 1000
Rezultat :
plaintext: 0100 1000 0100 1001
ciphertext:0100 1011 0100 1000
Proprietati :
•algoritm stream-cipher de cheie variabila ca dimensiune
•algoritm de generare pseudo-random
16

•algoritm de Key-scheduling
•returneaza numere pseudo-random ca byte streams
•testat hardware pentru criptare si decriptare
Avantaje :
•mai rapid ca DES
•spatiu de chei foarte mare ( ∼1700 biti)
•folosit la SSL pentru protejarea traficului de internet si in WEP (Wired
Equivalent Privacy) pentru securizarea retelelor wireles s. (Alte protocoale
bazate pe RC4: WPA – WiFi Protected Access, BitTorrent protoc ol
encryption, SSH – Secure Shell, RDP – Remote Desktop Protoco l,
Kerberos, etc)
Dezavantaje :
•primii 3 bytes ai output-ului dezvaluie informatii despre c heie
•numar mare de chei slabe (1/256)
•cheile slabe pot fi detectate si exploatate cu o probabilitat e ridicata
VarianteRC 4 :
1. RC4A: Varianta propusa de Souradyuti Paul si Bart Preneel, aduce doar o
imbunatatire a vitezei.
2. VMPC: Variably Modified Permutation Composition, itereaz a de 3 ori
mai mult decat RC4.
3. RC4+: key-schedule mai complex decat in RC4, mai greoi de 1 .7 decat
RC4.
4. Spritz: Ron Rivest si Jacob Schuldt, algoritmul poate fi fo losit atat ca
generator pseudo-random cat si ca functie hash.
Atacuri:
De-a lungul timpului au existat mai multe atacuri precum:
Fluher Mantin Shamir (2001), Klein (2005), Royal Holloway (2 013),
Bar-mitzwah (2015) cel din urma fiind NOMORE (2015).
In cele ce urmeaza, pentru a incheia capitolul curent, vom fa ce cunoscut
cititorului atacul NOMORE.
NOMORE = Numerous Occurrence MOnitoring and Recovery Exploit . Atacul
a fost facut datorita cercetatorilor in securitatea inform atiei din KU Leuven,
universitate din Belgia, cercetatori ce au prezentat noi at acuri impotriva RC4
atat asupra TLS cat si WPA-TKIP.
NOMORE este primul atac de acest gen pus in practica, asupra TL S-ului
17

decriptatnd un cookie HTTPS in 75 ore iar asupra WPA-TKIP permi tand
atacatorului sa decriptezesi sa injecteze pachete arbitra re in doar 1 ora.
O criptanaliza a RC4 arata ca in TLS si WPA descopera 220 din 25 6 bytes ai
plaintext-ului dupa trimiterea aceluiasi mesaj de 1.000.0 00.000.000 ori iar unii
bytes pot fi redobanditi abia dupa 16.000.000.000.000 trans misiuni.
2.6 AES & DES – Functii Pseudo Random
2.7 Bune practici si standarde in generarea
cheilor
18

3. Derivarea cheilor
3.1 Descriere generala a KDF(key derivation
function)
KDF=KeyDerivationFunction = o functie pseudo-random cu ajutorul
careia una / mai multe chei secrete (SK), apartinand unor par ole, master keys,
etc., sunt derivate.
Scopul KDF-urilor:
•asigura evitarea ”cheilor slabe”
•lungirea cheilor la o anumita dimensiune dorita
•obtinerea cheilor intr-un anumit format
•componente ale protocoalelor de key-agreement
KDF sunt de obicei utilizate impreuna cu parametri publici, pentru a preveni
un atacator sa obtina derivarea prin invatarea unor informa tii critice legate fie
de input-ul valorii secrete fie legate de alte chei derivate a nterior.
KS=KeyStretching = tehnica de securizare a posibilelor chei slabe (parole /
passphrase) impotriva atacurilor brute-force (*), prin cr esterea timpului de
testare a tuturor posibilitatilor unei chei. Key strengthe ning extinde cheia cu un
salt random si, spre deosebire de key stretching, sterge ult erior in mod sigur
saltul adaugat.
(*) (passwod cracking) =¿ Functiile sunt in mod deliberat gr eu de calculat (ca
timp) pentru prevenirea unor atacuri precum cel mentionat a nterior sau precum
dictionary attack.
DK = KDF ( Key , Salt , Iterations )
1. DK = cheie derivata
2. KDF = functie de derivare a cheii
3. Key = cheia initiala
4. Salt = parametru ne-secret , numar random (utilizarea ace stui parametru
previne precalcularea unui dictionar de chei derivate [dic tionary attack])
5. Iterations = numarul de iteratii al unei sub-functii (difi cultatea atacului
creste proportional cu numarul de iteratii)
19

Cel mai important uz al KDF-urilor este password hashing -¿ verificarea
parolelor, iar printre algoritmii de derivare a cheilor ava nd si proprietati de
password hashing, si care s-au remarcat, enumeram pe urmato rii:
1.Argon2 = castigatorul competitiei ”Password Hashing Competition”
2015.
Problemele dinaintea aparitiei algoritmului Argon 2 erau:
•Independente de input: in primele scheme, in care locatia me moriei
citite era cunoscuta in avans, a devenit vulnerabila la atac urile
time-space tradeoff – un atacator poate precalcula blocul li psa pana
acesta sa fie generat sau cerut de sistem.
•Dependente de input: vulnerabil la side-channel attack.
•Cat de mare ar trebui sa fie un bloc de memorie? Blocuri mici –
incetinire din cauza principiulului de cache CPU. Blocuri ma ri – greu
de procesat din cauza numarului limitat de registri lungi.
•Daca blocul de memorie este mare, cum sa alegem functia de
compresie?
•Cum sa exploatam core-uri multiple de procesor?
Solutia Argon2: arhitectura x86 ce exploateaza cache-ul si m emoria
procesoarelor Intel si AMD.
•Argon2d: mai rapid, utlizand accesul memoriei depinzand de date –
perfect pentru aplicatii fara amenintari din partea side-c hannel
timing attack
•Argon21: mai incet, efectuand mai multe operatii pe memorie pentru
a oferi securitate impotriva tradeoff attack.
2.Catena = primul password scrambler care satisface atat consumul de
memorie, prevazand in acelasi timp rezistenta impotriva at acurilor
cache-timing. Este un algoritm sigur, asigura indistingib ilitate la numerele
random si este rezistent la side-channel attack.
3.Lyra2= abilitatea de a configura cantitatea de memorie dorita, tim pul de
executie, gradul de paralelism [numarul de thread-uri], lu ngimea
output-ului etc.; decuplarea costului memoriei de costul t impului;
rezistent la time-memory trade-offs attack si side-channel attack.
4.Makwa = transforma un input de lungime variablia intr-un output de
lungime fixa. Ofera incetinire configurabila dar si salt-ing . Diferit fata de
ceilalti algoritmi prin faptul ca hashing-ul poate fi delega t unui sistem
extern nesigur. Ideea principala este ca acest sistem este v azut ca un
atacator pasiv, unde se vor aplica toate functiile necesare si se va incerca
observarea datelor de catre acest atacator pasiv, scopul fii nd cresterea
puterii computationale a password hashing-ului.
Scenarii de delegare: Password Authenticated Key Exchange a nd Small
Clients, Feeble Server and the Cloud, Heterogenous Clients.
20

5.Yescrypt = mass-user authentication: retele sociale, portaluri web ,
banca, cumparaturi online, servicii de plata, conturi de do meniu, derivare
de chei etc.
3.2 PBKDF2
DK = KDF ( PRF, Password , Salt , Iterations , dkLen )
•DK = cheia derivata
•KDF = functia de derivare a cheii
•PRF = functie pseudo-random
•Password = parola din care se deriveaza o cheie
•Salt = secventa random de biti
•Iterations = numarul dorit de iteratii
•dkLen = lungimea dorita a cheii derivate
DK =T1/bardblT2/bardbl…/bardblTdkLen/hLen
Ti= F (Password , Salt , Iterations , i )
F = XOR
Exemplu de derivare de cheie in protocolul WPA2 – Wifi-Protect ed Access:
DK = PBKDF2 ( HMACSHA1 , passphrase , ssid , 4096 , 256)
PBKDF2 poate fi implementat cu un circuit mic si putin RAM, ceea ce face ca
un atac brute-force sa fie ieftin, folosind circuite integra de sau unitati de
procesrare grafica.
In urma competitiei amintitite si in seciunea 3.1, ”Passwor d Hashing
Competition”, Argon2 a fost ales pentru derivare.
import os
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.kdf.pbkdf2 import
PBKDF2HMAC
from cryptography.hazmat.backends import default backend
backend = default backend()
# Salts should be randomly generated
salt = os.urandom(16)
# derive
kdf = PBKDF2HMAC(
… algorithm=hashes.SHA256(),
21

… length=32,
… salt=salt,
… iterations=100000,
… backend=backend
… )
key = kdf.derive(b"my great password")
# verify
kdf = PBKDF2HMAC(
… algorithm=hashes.SHA256(),
… length=32,
… salt=salt,
… iterations=100000,
… backend=backend
… )
kdf.verify(b"my great password", key)
3.3 HKDF
HKDF = HMAC-based Extract-and-Expand KDF
Transforma orice date slabe in material criptografic sigur ( exemplu: convertirea
secretelor pratajate Diffie-Hellman in material potrivit pen tru criptare,
verificare a integritatii sau pentru autentificare.
HMAC-based Extract and Expand KDF este deja utilizat in diver se protocoale
precum IKEv2 (Internet Key Exchange), PANA ( Protocol for Carr ying
Authentication for Network Access) si EAP-AKA (Extensible Authen tication
Protocol Method for 3rd Generation Authentication and Key Agr eement).
HKDF urmeaza paradigma ”extrage apoi extinde”, in care funct ia de derivare
a cheii este compusa din doua module:
1. Primul modul preia input-ul de material al cheii si extrag e din acesta o
cheie K pseudo-random de lungime fixa. (IKM = input keying mat erial ;
PRK = pseudorandom key)
HKDF-Extract(salt, IKM) →PRK
2. Al doilea modul extinde cheia K in mai multe chei pseudo-ran dom
aditionale, avand dimensiunea dorita. (info = informatii s pecifice aplicatiei
– optional ; L = lungimea output-ului ; OKM = output keying mat erial)
HKDF-Expand(PRK, info, L) →OKM
Aplicatii ale HKDF-ului:
22

•Construirea de generatori pseudo-random pentru surse impe rfecte de
randomness (RNG fizic)
•Construirea de generatori pseudo-random din surse slabe de randomness
(entropii colectate din evenimente ale sistemului)
•Derivarea de chei criptografice dintr-o valoare partajata D iffie-Hellman
intr-un protocol de key-agreement
•Derivarea de chei simetrice dintr-o chema hibrida de cripta re publica.
Teorema! Fie H functia hash Mercke-Damgard, construita pe o familie
pseudo-random de functii de compresie {hK}K. Fie S o colectie de distributii
de probabilitate comportandu-se ca o sursa de material de ch ei. Presupunand
ca instantierea HMAC-ului cu familia de functii de compresie prezentata mai
sus este un extractor computational sigur al sursei S, putem afirma ca HKDF
este o functie de derivare a cheilor sigura in relatie cu S.
import os
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.backends import default backend
backend = default backend()
salt = os.urandom(16)
info = b"hkdf-example"
hkdf = HKDF(
… algorithm=hashes.SHA256(),
… length=32,
… salt=salt,
… info=info,
… backend=backend
… )
key = hkdf.derive(b"input key")
hkdf = HKDF(
… algorithm=hashes.SHA256(),
… length=32,
… salt=salt,
… info=info,
… backend=backend
… )
hkdf.verify(b"input key", key)
23

3.4 ConcatKDFHash – ConcatKDFHMAC
INPUT :
•Z : byte string ce reprezinta un secret partajat
•keydatalen : integer ce defineste lungimea in biti a material ului secret de
cheie ce trebuie sa fie generat (ar trebui sa fie ≤hashlen * (232−1))
•OtherInfo : bit string egal cu concatenarile urmatoare:
AlgorithmID/bardblPartyUInfo/bardblPartyVInfo/bardblSuppPubInfo/bardblSuppPrivInfo
1. AlgorithmID = bit string ce indica cum va fi parsat materialu l
derivat de cheie si pentru ce algoritmi va fi folosit acest mat erial.
2. PartyUInfo = bit string continand informatii publice ceru te de
aplicatie folosind KDF ce contribuie la un tert U la procesul de
derivare a cheii.
3. PartyVInfo = bit string continand informatii publice ceru te de
aplicatie folosind KDF ce contribuie la un tert V in procesul de
derivare a cheii
4. SuppPubInfo = bit string continand aditional informatii publice
cunoscute mutual.
5. SuppPrivInfo = bit string continand aditional informati i private
cunoscute mutual (exemplu: cheie secreta simetrica partaj ata
comunicata intr-un canal separat)
OUTPUT :
DerivedKeyingMaterial = bit string de lungime keydatalen ( sau un indicator de
eroare in cazul esecului de derivare).
PROCES :
•reps = [keydatalen / hashlen]
•Daca reps≥(232−1)), atunci aborteaza, afiseaza un indicator de eroare si
opreste-te
•Initializeaza un bit string de 32 biti in big-endian ca 00000 001 in baza 16.
•daca counter/bardblZ/bardblOtherInfo este≥maxhashinputlen, atunci aborteaza
afiseaza un indicator de eroare si opreste-te
•pentru i=1:
–calculeaza Hi= H (counter/bardblZ/bardblOtherInfo)
–creste counter (modulo 232) tratandu=l ca un integer pe 32 biti
neasignat.
–fie Hhas un set de Hash reps daca (keydatalen / hashlen ) este un
integer; altfel, fie Hhash un set de (keydatalen mod hashlen) c ei mai
din stanga biti ai Hash reps.
24

–seteaza DerivedKeyingMaterial = H1/bardblH2/bardbl…/bardblHashreps−1/bardbl
Hhash
Nici ConcatKDFHash nici ConcatKDFHMAC nu ar trebui folosite pe ntru
stocarea parolelor.
ConcatKDFHash
import os
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.kdf.concatkdf import
ConcatKDFHash
from cryptography.hazmat.backends import default backend
backend = default backend()
otherinfo = b"concatkdf-example"
ckdf = ConcatKDFHash(
… algorithm=hashes.SHA256(),
… length=256,
… otherinfo=otherinfo,
… backend=backend
… )
key = ckdf.derive(b"input key")
ckdf = ConcatKDFHash(
… algorithm=hashes.SHA256(),
… length=256,
… otherinfo=otherinfo,
… backend=backend
… )
ckdf.verify(b"input key", key)
ConcatKDFHMAC
import os
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.kdf.concatkdf import
ConcatKDFHMAC
from cryptography.hazmat.backends import default backend
backend = default backend()
salt = os.urandom(16)
otherinfo = b"concatkdf-example"
ckdf = ConcatKDFHMAC(
… algorithm=hashes.SHA256(),
… length=256,
… salt=salt,
… otherinfo=otherinfo,
… backend=backend
… )
25

key = ckdf.derive(b"input key")
ckdf = ConcatKDFHMAC(
… algorithm=hashes.SHA256(),
… length=256,
… salt=salt,
… otherinfo=otherinfo,
… backend=backend
… )
ckdf.verify(b"input key", key)
3.5 X963KDF
3.6 KBKDF
3.7 Scrypt KDF
26

Conclusion
27

Bibliography
[1]Lamport, Leslie.LATEX: A Document Preparation System . 2. vyd´ an´ ı.
Massachusetts: Addison Wesley, 1994. ISBN 0-201-52983-1.
28

List of Tables
29

List of Abbreviations
30

Attachments
31