- Prelegerea 8 - Sisteme de criptare blocruxandraolimid.weebly.com/uploads/2/0/1/0/20109229/... ·...

Transcript of - Prelegerea 8 - Sisteme de criptare blocruxandraolimid.weebly.com/uploads/2/0/1/0/20109229/... ·...

riptografie şi Securitate

- Prelegerea 8 -Sisteme de criptare bloc

Adela Georgescu, Ruxandra F. Olimid

Facultatea de Matematică şi InformaticăUniversitatea din Bucureşti
Cuprins

1. Definiţie

2. Construcţie

3. Moduri de utilizare

4. Exemple

Criptografie şi Securitate 2/37 ,
Criptografia simetrică

I Am studiat sisteme simetrice care criptează bit cu bit -sisteme de criptare fluide;

I Vom studia sisteme simetrice care criptează câte n biţisimulan - sisteme de criptare bloc;

Sisteme bloc vs. sisteme fluide


... d.p.d.v. al modului de criptare:

Sisteme fluide

I criptarea biţilor serealizează individual

I criptarea unui bit din textulclar este independentă deorice alt bit din textul clar

Sisteme bloc

I criptarea se realizează ı̂nblocuri de câte n biţi

I criptarea unui bit din textulclar este dependentă debiţii din textul clar careaparţin aceluiaşi bloc


... d.p.d.v. tradiţional, ı̂n practică:

Sisteme fluide

I necesităţi computaţionalereduse

I utilizare: telefoane mobile,dispozitive ı̂ncorporate,PDA

I par să fie mai puţin sigure,multe sunt sparte

Sisteme bloc

I necesităţi computaţionalemai avansate

I utilizare: internet

I par să fie mai sigure,prezintă ı̂ncredere mai mare

Sisteme bloc

I Introducem noţiunea de permutare pseudoaleatoare sauPRP(PseudoRandom Permutation)

I În analogie cu ce ştim deja:

I PRP sunt necesare pentru construcţia sistemelor bloc

asa cum

I PRG sunt necesare pentru construcţia sistemelor fluide

Sisteme bloc




asa cum


Sisteme bloc




asa cum


Sisteme bloc

Sisteme fluide Sisteme bloc

PRP

I Ramâne să definim noţiunea de permutare pseudoaleatoaresau PRP (PseudoRandom Permutation);

I Acesta este o funcţie deterministă şi bijectivă care pentru ocheie fixată produce la ieşire o permutare a intrării ...

I ... indistinctibilă faţă de o permutare aleatoare;

I În plus, atât funcţia cât şi inversa sa sunt eficient calculabile.

PRP





PRP





PRP





PRP

Definitie

O permutare pseudoaleatoare definită peste (K,X ) este o funcţiebijectivă

F : X ×K → X

care satisface următoarele proprietăţi:

1. Eficienţă: ∀k ∈ K, x ∈ X ,∃ algoritmi determinişti PPT carecalculează Fk(x) şi F

−1k (x)

2. Pseudoaleatorism: ∀ algoritm PPT D, ∃ o funcţie neglijabilănegl a.̂ı.:

|Pr [D(r) = 1]− Pr [D(Fk(·)) = 1]| ≤ negl(n)

unde r ←R Perm(X ), k ←R K

Notaţii

I Fk(x) = F (k , x)o cheie este ı̂n general (aleator) aleasă şi apoi fixată

I Perm(X ) = mulţimea tuturor funcţiilor bijective de la X la X

I X = {0, 1}n

I D = Distringuisher care are acces la oracolul de evaluare afuncţiei

PRF

I Introducem noţiunea de funcţie pseudoaleatoare sau PRF(PseudoRandom Function)...

I ... ca o generalizare noţiunii de permutare pseudoaleatoare;

I Acesta este o funcţie cu cheie care este indistinctibilă faţă deo funcţie aleatoare (cu acelaşi domeniu şi mulţime de valori).

PRF




PRF




PRF

Definitie

O funcţie pseudoaleatoare definită peste (K,X ,Y) este o funcţiebijectivă

F : X ×K → Y

care satisface următoarele proprietăţi:

1. Eficienţă: ∀k ∈ K, x ∈ X ,∃ algoritm PPT care calculeazăFk(x)

2. Pseudoaleatorism: ∀ algoritm PPT D, ∃ o funcţie neglijabilănegl a.̂ı.:

|Pr [D(r) = 1]− Pr [D(Fk(·)) = 1]| ≤ negl(n)

unde r ←R Func(X ,Y ), k ←R K

Notaţii

I Fk(x) = F (k , x)o cheie este ı̂n general (aleator) aleasă şi apoi fixată

I Func(X ,Y ) = mulţimea funcţiilor de la X la Y

I X = {0, 1}n, Y = {0, 1}nconsiderăm ı̂n general că PRF păstrează lungimea

I D = Distringuisher care are acces la oracolul de evaluare afuncţiei

PRP ⊆ PRF

I Întrebare: De ce PRF poate fi privită ca o generalizare aPRP?

I Răspuns: PRP este PRF care satisface:

1. X = Y

2. este inversabilă

3. calculul funcţiei inverse este eficient

PRP ⊆ PRF



1. X = Y



PRP ⊆ PRF



1. X = Y



Construcţii

I PRF⇒ PRGPornind de la PRF se poate construi PRG

I PRG⇒ PRFPornind de la PRG se poate construi PRF

I PRP⇒ PRFPornind de la PRP se poate construi PRF

I PRF⇒ PRPPornind de la PRF se poate construi PRP

Întrebare: Care dintre aceste construcţii este trivială?

Construcţii






Construcţii






Construcţii






Construcţii






Construcţii

Răspuns: PRP⇒ PRF

PRP este o particularizare a PRF : X ×K → Y care satisface:

1. X = Y



Construcţii

Răspuns: PRP⇒ PRF

PRP este o particularizare a PRF : X ×K → Y care satisface:

1. X = Y



Construcţii



I PRP⇒ PRF√

Pornind de la PRP se poate construi PRF


PRF ⇒ PRG

I Considerăm F : K × {0, 1}n → {0, 1}n PRF;

I Construim G : K → {0, 1}nl PRG sigur:

G (k) = Fk(0)||Fk(1)|| . . . ||Fk(l − 1)

I Întrebare: De ce este G sigur?

I Răspuns: Fk(·) este indistinctibilă faţă de o funcţie aleatoare⇒ G (k) este indistinctibilă faţă de o secvenţă aleatoare delungime ln.

I Avantaj: Construcţia este paralelizabilă

PRF ⇒ PRG



G (k) = Fk(0)||Fk(1)|| . . . ||Fk(l − 1)




PRF ⇒ PRG



G (k) = Fk(0)||Fk(1)|| . . . ||Fk(l − 1)




PRF ⇒ PRG



G (k) = Fk(0)||Fk(1)|| . . . ||Fk(l − 1)


I Răspuns: Fk(·) este indistinctibilă faţă de o funcţie aleatoare

⇒ G (k) este indistinctibilă faţă de o secvenţă aleatoare delungime ln.


PRF ⇒ PRG



G (k) = Fk(0)||Fk(1)|| . . . ||Fk(l − 1)




PRF ⇒ PRG



G (k) = Fk(0)||Fk(1)|| . . . ||Fk(l − 1)




Construcţii

I PRF⇒ PRG√

Pornind de la PRF se poate construi PRG


I PRP⇒ PRF√



PRG ⇒ PRFI Considerăm G : K → K2 PRG cu |K| = n:

G (k) = (G0(k),G1(k))

G0(k) şi G1(k) sunt prima şi a doua jumătate a ieşirii din PRG

I Construim F : K × {0, 1} → K PRF :

Fk(0) = G0(k),Fk(1) = G1(k)

Fk(0) ı̂ntoarce prima jumătate a secvenţei pseudoaleatoare G(k)

Fk(1) ı̂ntoarce a doua jumătate a secvenţei pseudoaleatoare G(k)

I Întrebare: De ce este F sigură?I Răspuns: G (k) este indistinctibilă faţă de o secvenţă aleatoare

de lungime 2n⇒ G0(k) şi G1(k) sunt indistinctibile faţă de o secvenţăaleatoare de lungime n⇒ pentru k ←R {0, 1}, Fk(·) este indistinctibilă faţă de ofuncţie aleatoare.


G (k) = (G0(k),G1(k))



Fk(0) = G0(k),Fk(1) = G1(k)






G (k) = (G0(k),G1(k))



Fk(0) = G0(k),Fk(1) = G1(k)



I Întrebare: De ce este F sigură?

I Răspuns: G (k) este indistinctibilă faţă de o secvenţă aleatoarede lungime 2n⇒ G0(k) şi G1(k) sunt indistinctibile faţă de o secvenţăaleatoare de lungime n⇒ pentru k ←R {0, 1}, Fk(·) este indistinctibilă faţă de ofuncţie aleatoare.


G (k) = (G0(k),G1(k))



Fk(0) = G0(k),Fk(1) = G1(k)




de lungime 2n

⇒ G0(k) şi G1(k) sunt indistinctibile faţă de o secvenţăaleatoare de lungime n⇒ pentru k ←R {0, 1}, Fk(·) este indistinctibilă faţă de ofuncţie aleatoare.


G (k) = (G0(k),G1(k))



Fk(0) = G0(k),Fk(1) = G1(k)




de lungime 2n⇒ G0(k) şi G1(k) sunt indistinctibile faţă de o secvenţăaleatoare de lungime n

⇒ pentru k ←R {0, 1}, Fk(·) este indistinctibilă faţă de ofuncţie aleatoare.


G (k) = (G0(k),G1(k))



Fk(0) = G0(k),Fk(1) = G1(k)





PRG ⇒ PRFI Construcţia pentru un singur bit de intrare...

PRG ⇒ PRFI ...se poate generaliza pentru un număr oarecare de biţi

PRG ⇒ PRF

I Construcţia poate fi reprezentată ca un arbore binar cu cheiak rădăcină;

I Pentru un nod de valoare k ′, copilul stâng ia valoarea G0(k′)

şi copilul drept ia valoare G1(k′);

I Valoarea funcţiei Fk(x) = Fk(x0, . . . , xn−1) este obţinută prinparcurgerea arborelui ı̂n funcţie de x ;

I Adâncimea arborelui este liniară ı̂n n (n);

I Dimensiunea arborelui este exponenţială ı̂n n (2n);

I NU se utilizează ı̂n practică din cauza performanţei scăzute.

PRG ⇒ PRF








PRG ⇒ PRF








PRG ⇒ PRF








PRG ⇒ PRF








PRG ⇒ PRF








Construcţii

I PRF⇒ PRG√

Pornind de la PRF se poate construi PRG

I PRG⇒ PRF√

Pornind de la PRG se poate construi PRF

I PRP⇒ PRF√



PRF ⇒ PRP

Teorema (Luby-Rackoff ’85)

Dacă F : K × {0, 1}n → {0, 1}n este PRF , se poate construiF ′ : K × {0, 1}2 → {0, 1}2 PRP.

I Construcţia foloseşte runde Feistel, pe care le vom prezentaı̂ntr-un curs ulterior.

PRF ⇒ PRP

Teorema (Luby-Rackoff ’85)

Dacă F : K × {0, 1}n → {0, 1}n este PRF , se poate construiF ′ : K × {0, 1}2 → {0, 1}2 PRP.

I Construcţia foloseşte runde Feistel, pe care le vom prezentaı̂ntr-un curs ulterior.

Moduri de utilizare

I Să continuam cu ceva mai practic...

I Întrebare: Ce se ı̂ntâmplă dacă lungimea mesajului clar estemai mică decât dimensiunea unui bloc?

I Răspuns: Se completează cu biţi: 1 0 . . . 0;

I Întrebare: Ce se ı̂ntâmplă dacă lungimea mesajului clar estemai mare decât lungimea unui bloc?

I Răspuns: Se utilizează un mod de operare (ECB, CBC,OFB, CTR);

I Notăm cu Fk un sistem de criptare bloc (i.e. PRP) cu cheia kfixată.

Moduri de utilizare







Moduri de utilizare







Moduri de utilizare







Moduri de utilizare







Moduri de utilizare







Modul ECB (Electronic Code Book)


I Pare modul cel mai natural de a cripta mai multe blocuri;

I Pentru decriptare, Fk trebuie să fie inversabliă;

I Este paralelizabil;

I Este determinist, deci este nesigur;

I Întrebare: Ce informaţii poate să ofere modul de criptare ECBunui adversar pasiv?

I Răspuns: Un adversar pasiv detectează repetarea unui bloc detext clar pentru că se repetă blocul criptat corespunzător;

I Modul ECB NU trebuie utilizat ı̂n practică!

Modul CBC (Cipher Block Chaining)


I IV este o ales ı̂n mod aleator la criptare;

I IV se transmite ı̂n clar pentru ca este necesar la decriptare;


I Este secvenţial, un dezavantaj major dacă se poate utilizaprocesarea paralelă.

Modul OFB (Output FeedBack)


I Generează o secvenţă pseudoaleatoare care se XOR-eazămesajului clar;



I Fk nu trebuie neapărat să fie inversabliă;

I Este secvenţial, ı̂nsă secvenţa pseudoaleatoare poate fipre-procesată anterior decriptării.

Modul CTR (Counter)

Modul CTR (Counter)


I ctr este o ales ı̂n mod aleator la criptare;

I ctr se transmite ı̂n clar pentru ca este necesar la decriptare;



I În plus, secvenţa pseudoaleatoare poate fi pre-procesatăanterior decriptării.

Modul CTR (Counter)







Modul CTR (Counter)







Modul CTR (Counter)







Modul CTR (Counter)







Modul CTR (Counter)







Exemple

I DES (Data Encryption Standard):I propus de IBMI adoptat ca standard NIST ı̂n 1976

(lungime cheie = 64 biţi, lungime bloc = 64 biţi)I spart prin căutare exhaustivă ı̂n 1997

I AES (Advanced Encryption Standard):I algoritmul Rijndael propus de J. Daemen şi V.RijmanI adoptat ca standard NIST ı̂n 2001

(lungime cheie = 128, 192, 256 biţi, lungime bloc = 128 biţi)

Exemple

I DES (Data Encryption Standard):I propus de IBMI adoptat ca standard NIST ı̂n 1976

(lungime cheie = 64 biţi, lungime bloc = 64 biţi)I spart prin căutare exhaustivă ı̂n 1997

I AES (Advanced Encryption Standard):I algoritmul Rijndael propus de J. Daemen şi V.RijmanI adoptat ca standard NIST ı̂n 2001

(lungime cheie = 128, 192, 256 biţi, lungime bloc = 128 biţi)

Important de reţinut!

I Sisteme bloc vs. sisteme fluide

I Noţiunile de PRP, PRF

I Construcţii specifice PRG, PRF, PRP

I Transpunerea sistemelor bloc ı̂n practică - moduri de operare:ECB, CBC, OFB, CTR


DefinitieConstructieModuri de utilizareExemple

- Prelegerea 8 - Sisteme de criptare blocruxandraolimid.weebly.com/uploads/2/0/1/0/20109229/... ·...

Documents

Transcript of - Prelegerea 8 - Sisteme de criptare blocruxandraolimid.weebly.com/uploads/2/0/1/0/20109229/... ·...