Facultatea De Matematica Iasi - Câteva protocoale criptograficecriptografie/note_curs_2019/... ·...

Functii de trunchiere Protocoale Cina Cina SSp SSh SB PM Schimbul de chei Autentificarea Autentificare cu schimb de chei

Cateva protocoale criptografice

Anul II

Aprilie 2019


Functii de trunchiere (Hash functions)

In criptografie sunt importante, pentru a combina eficienta sisiguranta criptarii, functii f : x 7→ h care:

sunt usor calculabile

lungimea lui x este mare, iar cea a lui h este semnificativ maiscurta (ex: x are 106 biti, iar h mai putin de 200 biti)

dat fiind un h, nu este posibil din punct de vederecomputational determinarea unui x a.i. h = f (x) (sens unic)

dat fiind x1, nu este posibil din punct de vedere computationaldeterminarea unei valori x2 6= x1 a.i. f (x2) = f (x1) (rezistentala coliziuni ın sens slab)

nu este posibil din punct de vedere computationaldeterminarea unor valori x1 6= x2 a.i. f (x1) = f (x2) (rezistentala coliziuni ın sens tare)

Astfel de functii sunt folosite pentru garantarea integritatiimesajelor, autentificare, in scheme de semnatura digitala.



Fie A alfabetul folosit si A∗ multimea tuturor mesajelor posibile.

Definitie

O functie de trunchiere (functie hash) este o functie

f : A∗ −→ An

unde n ∈ N fixat.

Exemplu

A = {0, 1}, n = 1

(εk−1 . . . ε1ε0)2 7→ εk−1 ⊕ . . .⊕ ε1 ⊕ ε0.

Definitie

O functie de compresie este o functie f : Am −→ An undem, n ∈ N fixate, m > n.



O coliziune a unei functii h : D → D ′ este o pereche de elementex1, x2 ∈ D, x1 6= x2, cu proprietatea h(x1) = h(x2).Functiile de trunchiere si functiile de compresie au ıntotdeaunacoliziuni deoarece nu sunt injective.

Definitie

Spunem ca functia h este rezistenta la coliziuni ın sens slab daca,dat fiind x1 ∈ D, este imposibil, din punct de vederecomputational, de determinat o coliziune (x1, x2) a lui h.

Definitie

Spunem ca functia h este rezistenta la coliziuni ın sens tare dacaeste imposibil, din punct de vedere computational, de determinat ocoliziune (x1, x2) a lui h.

Observatie. In criptografie sunt importante functiile de trunchierecu sens unic, rezistente la coliziuni.


Protocoale criptografice

Un protocol criptografic este un algoritm cu pasi care specificaactiunile ce trebuiesc indeplinite de una sau mai multe entitati pen-tru a atinge un anumit obiectiv de securitate a datelor.

Primitivele unui protocol sunt pasii acestui algoritm.



Exemplu: Key agreement protocol

Alice si Bob doresc sa comunice, printr-un canal nesecurizat, folosindun criptosistem simetric S. Pentru aceasta ei trebuie sa stabileascao cheie a acestuia.

1 Bob construieste o schema de criptare SP cu cheie publica sitrimite lui Alice cheia sa publica.

2 Alice genereaza o cheie K a criptosistemului simetric S.

3 Alice cripteaza cheia K ın schema SP folosind cheia publica alui Bob si ıi trimite acestuia rezultatul obtinut.

4 Bob decripteaza mesajul primit folosind cheia sa privata siobtine cheia K .

5 Alice si Bob ıncep sa comunice folosind criptosistemul S sicheia K .



Esecul unui protocol se produce atunci cand acesta esueaza ınındeplinirea obiectivelor de securitate, ıntr-o maniera ın careadversarul nu dezabiliteaza algoritmii specifici primitivelor, cimanipuleaza ınsusi protocolul.

Exemplu

Alice si Bob comunica folosind un criptosistem simetric de tip flux.Se cunoaste faptul ca primii douazeci de biti ai unui mesaj reprezintainformatia referitoare la o suma de bani. Un adversar (Claire) poateintercepta mesajul si realiza un XOR al primilor douazeci de biti cu osuccesiune oarecare de biti, ınainte de a repune mesajul ın circulatie,schimband astfel valoarea sumei de bani. Desi Claire nu a fostcapabila sa descifreze mesajul, ea a produs un esec al protocoluluiutilizat de Alice si Bob. Metoda de criptare nu a fost compromisa,dar conditia de integritate a datelor nu a fost satisfacuta.



Cauze de esec ale unui protocol:

slabiciuni ale unei primitive particulare, care pot fi amplificatede protocol

garantii de securitate supraevaluate sau neclar ıntelese

neluarea in seama a unor principii de securitate aplicabile unorclase largi de primitive (ex.: pentru toate primitivele ceconstau in criptarea datelor, clasa mesajelor ın clar trebuie safie suficient de ampla pentru a ımpiedica un atac prin cautareexhaustiva)



In proiectarea unui protocol trebuiesc incluse urmatoarele etape:

identificarea tuturor ipotezelor si conditiilor ın care vafunctiona fiecare din pasii acestuia

pentru fiecare dintre aceste ipoteze si conditii, determinareaefectului pe care ıl va avea o eventuala violare a acesteiaasupra obiectivelor de securitate ale protocolului.


Cina criptografilor

XOR (suma disjuncta)

a b a⊕ b

0 0 01 0 10 1 11 1 0


Cina criptografilor

David Chaum (1985).”Security without identification: transaction systems to make bigbrother obsolete”Protocol care are ca obiectiv comunicarea ın retele, cu expeditoranonim si detectarea intrusilor.

Trei criptografi (A1, A2, A3) iau cina ıntr-un restaurant. Lasfarsitul mesei chelnerul ıi anunta ca nota de plata este dejaachitata. Plata a fost facuta fie de unul dintre ei, fie de firma careıi angajeaza.

cei trei ısi respecta reciproc dreptul de plati ın mod anonim;

ei vor totusi sa stie daca masa a fost platita de firma.


Cina criptografilor

PROTOCOL

1 Fiecare pereche dintre cei trei stabileste, ın secret fata de altreilea, un bit de comun acord (de exemplu prin aruncareaunei monede, fara ca al treilea sa poata vedea rezultatul).Astfel, criptograful A1 a stabilit bitul ε12 cu A2 si bitul ε13 cuA3; similar A2 are stabiliti bitii ε21 si ε23, iar A3 bitii ε31 si ε32;

εij = εji .

2 Fiecare criptograf Ai anunta public :ai = εij ⊕ εik , {i , j , k} = {1, 2, 3}, daca el nu a platit cina;ai = εij ⊕ εik ⊕ 1, {i , j , k} = {1, 2, 3}, daca el a platit cina.

3 Daca a1 ⊕ a2 ⊕ a3 = 0, cei trei stiu ca cina a fost platita defirma;daca a1 ⊕ a2 ⊕ a3 = 1, cei trei stiu ca cina a fost platita deunul dintre ei.

4 In al doilea caz, o persoana care nu a platit nu poate sti cinedin ceilalti doi este autorul platii.


Secret splitting (divizarea secretului)

Un secret M trebuie comunicat unui cerc restrans de colaboratori.Conditii:

Fiecare colaborator va detine un “fragment” al secretului, careizolat este inutilizabil.

M este reconstituit daca se cunosc toate fragmentele.

Exemplu

1 Alice genereaza aleatoriu un sir de biti R de aceeasi lungimecu M

2 Alice calculeaza S := M ⊕ R

3 Alice trimite R lui Bob

4 Alice trimite S lui Claire

Reconstituirea: M = S ⊕ R

Problema: Pentru a recupera M este nevoie de toate informatiilepartiale.


Secret sharing (partajarea secretului)

Un secret M trebuie impartit in n informatii partiale(shadows=umbre). Conditii:

Fiecare umbra izolata este inutilizabila.

M este reconstituit daca se cunosc toate umbrele din oricesubmultime a umbrelor cu m < n elemente.

daca se cunosc oricare m− 1 umbre, nu se poate reconstitui M


Secret sharing (partajarea secretului)

Protocolul Shamir1 se alege un numar prim p mai mare decat orice secret si decat

orice posibila umbra (p este public)2 se genereaza un polinom

F (x) = am−1xm−1 + . . .+ a1x + M

cu ai ∈ Zp arbitrari3 se aleg n valori arbitrare xi4 se calculeaza si se distribuie umbrele si := F (xi ); se pastreaza

xi ; se distruge F

daca se cunosc m umbre, din conditiile si = F (xi ) se obtineun sistem cu m ecuatii si m necunoscute (am−1, . . . , a1,M),care duce la determinarea lui M

daca se cunosc mai putin de m umbre, sistemul are mai multenecunoscute decat ecuatii si deci nu are solutie unica.


F = a19X19 + a18X

18 . . .+ a1X + N

ai ∈ N, N = numarul contului.Aleg x1, . . . , x30 ∈ N distincti si calculeaza

si = F (xi ) , i ∈ {1, 2, . . . , 30}.

Fiecare participant Ai primeste “fragmentul” si . Valorilex1, . . . , x30 sunt pastrate de toata lumea, iar polinomul F estedistrus (inclusiv N).


Daca se reunesc 20 de participanti cu fragmentele respective, sepoate forma un sistem de ecuatii liniare:

si = a19x19i + a18x

18i . . .+ a1xi + N , 1 ≤ i ≤ 20

care are 20 de ecuatii si 20 de necunoscute (coeficientiipolinomului). Rezolvarea lui duce la determinarea acestora, inclusiva lui N!Sistemul are solutie unica, deoarece determinantul sau este de tipVandermonde cu coloane distincte.Daca se reunesc n < 20 de participanti, sistemul are mai multenecunoscute decat ecuatii si este nedeterminat. Oricare 20− ndintre necunoscute (printre care si N) pot fi desemnate caparametri in functie de care se determina celelalte, iar acestiparametri (deci si N) pot lua orice valoare!


Secret broadcasting (difuzarea secretului)

Se urmareste trimiterea unui secret catre mai multi utilizatori,astfel incat identitatea destinatarilor sa ramana secreta.

Mesajul se cripteaza si este trimis mai multor utilizatori. Incontinut este inclus un mecanism care permite doar unora dindestinatari sa descifreze si sa citeasca mesajul. Ceilalti primesc unmesaj neinteligibil, ei stiu ca a fost trimis un mesaj, dar nu stiucare din cei ce au primit mesajul sunt adevaratii destinatari.


Secret broadcasting (difuzarea secretului)

Protocol Alice vrea sa trimita mesajul M lui B1, . . . ,Br . Aliceutilizeaza cate un criptosistem cu functia de criptare fCi

cu fiecaredin utilizatorii Ci (i = 0, 1, . . . , n cu n >> r). Printre utilizatorii Ci

se regasesc si B1, . . . ,Br . Fie fk o functie de criptare/decriptarecare depinde de o cheie k.

1 Alice genereaza aleatoriu o cheie k si cifreaza cheia k cufB1 , . . . fBr

2 Alice trimite fiecarui utilizator Ci mesajul

fk(M) , fB1(k), . . . , fBr (k)

3 Doar B1, . . . ,Br pot determina cheia k si obtine apoi M.


Poker mental / protocol de distribuire acheilor

Alice si Bob utilizeaza un criptosistem cu cheie publica, avandfunctiile de criptare fA, fB (publice) si functiile de decriptare(secrete) f −1A , f −1B . Este necesar ca aceste functii sa comute:fA(fB(m)) = fB(fA(m)).

Alice cripteaza, cu cheia sa publica, si trimite lui Bob 52mesaje distincte, fA(m1), . . . , fA(m52).

Bob alege cinci din mesajele primite si le cripteaza cu cheia sapublica:

fB(fA(mi1)), . . . , fB(fA(mi5))

dupa care le trimite lui Alice.

Alice aplica cheia sa secreta mesajelor primite si trimiterezultatul lui Bob.

Bob aplica acestora cheia sa secreta si astfel a ales 5 dinmesajele initiale, fara a sti a priori continutul acestora .


Poker mental / protocol de distribuire acheilor

Aplicatie: distribuirea unor chei ce sunt fabricate de un arbitru.Nimeni (nici macar arbitrul) nu trebuie sa stie cine este in final inposesia unei anumite chei.

Alice genereaza o pereche de chei pentru un criptosistem cucheie publica si le pastreaza pe ambele secrete.

Arbitrul (Key Distribution Center) genereaza in mod continuuo multime de chei si le cripteaza cu propria sa cheie publica.

Arbitrul trimite cheile criptate in retea.

Alice alege la intamplare o cheie dintre acestea si o cripteazacu propria sa cheie publica.

Alice asteapta un timp inainte de a trimite arbitrului cheiadublu criptata.

Arbitrul aplica cheia sa secreta si trimite rezultatul lui Alice.

Alice aplica cheia sa secreta si obtine cheia generata de KDC.


Schimbul de chei

Exemplu: Protocolul Diffie-Hellman cu 3 sau mai multi participanti

subiectii cad de acord asupra unui numar prim p si a unuigenerator g ∈ Z∗pAlice alege a si trimite lui Bob x := ga (mod p)

Bob alege b si trimite lui Claire y := gb (mod p)

Claire alege c si trimite lui Alice z := g c (mod p)

Alice trimite lui Bob z ′ := za (mod p) [= g ca (mod p)]

Bob trimite lui Claire x ′ := xb (mod p) [= gab (mod p)]

Claire trimite lui Alice y ′ := y c (mod p) [= gbc (mod p)]

Alice, Bob si Claire pot calcula cheia k := gabc


Autentificarea

Un utilizator se conecteaza la un computer si trebuie sadovedeasca serverului identitatea.In mod “clasic”, se atribuie o parola ce ramane inmagazinata peserver.Este preferabil ca parolele sa nu fie stocate.Este suficient ca serverul sa poata decide daca parola este corectasau nu. Pe server pot fi stocate doar imaginile parolelor printr-o functiecu sens unic f .Protocol de autentificare:

1 Alice trimite parola P

2 serverul calculeaza f (P)

3 serverul confrunta f (P) cu baza de date a imaginilor parolelorstocate anterior


Autentificare: parola cu utilizare unica

Utilizatorul Alice poseda o lista de parole w1, . . . ,wn.Controlorul Bob stocheaza o lista f (w1), . . . , f (wn) aimaginilor acestora printr-o functie cu sens unic f . Alice alegeuna dintre parole, wi , pentru a se identifica, iar Bob verificadaca f (wi ) se gaseste in lista sa.

(Lamport) Alice si Bob folosesc o functie cu sens unic F

Alice alege un sir de caractere initiale w si un numar t (de ex.t = 100, sau t = 1000).Alice trimite lui Bob t si w0 = F t(w).Bob initializeaza un contor iA = 1 si stocheaza w0.La identificarea i , Alice trimite lui Bob (i ,wi = F t−i (w)).Bob verifica daca i = iA si F (wi ) = wi−1. Daca ambeleegalitati sunt verificate, accepta identificarea, modificaiA 7→ iA + 1 si stocheaza wi pentru identificarea urmatoare.


Autentificare: provocare / raspuns

Parola nu poate fi descoperita in avans de catre un adversar.Controlorul Bob pune o intrebare, provocarea, lui Alice, carecalculeaza raspunsul folosind cheia sa secreta. Bob verifica acestraspuns folosind cheia publica (daca se foloseste un criptosistem cucheie publicu a) sau aceeasi cheie secreta (daca se foloseste uncriptosistem simetric).


Autentificare: provocare / raspuns

Protocolul Fiat-ShamirEste un protocol cu divulgare nula. Utilizatorul dovedeste ca estein posesia unui secret, fara a-l divulga controlorului.Utilizatorul Alice alege doua numere prime mari p, q si calculeazan = pq. Alege apoi s, 1 ≤ s ≤ n− 1 si calculeaza v = s2 (mod n).Cheia sa publica este (v , n), cheia secreta s.

1. Angajarea Alice alege r ∈ {1, . . . n − 1}, calculeazax = r2 (mod n) pe care il trimite lui Bob.

2. Provocarea Bob alege la intamplare e ∈ {0, 1} pe care iltrimite lui Alice.

3. Raspunsul Alice trimite y = rse (mod n) lui Bob. Bobverifica daca y2 = xv e (mod n).

Daca primeste e = 0, Alice trimite y = r lui Bob. Bob verificadaca y2 = x (mod n).Daca primeste e = 1, Alice trimite y = rs lui Bob. Bobverifica daca y2 = xv (mod n).


Autentificare cu schimb de chei

Se asigura identitatea si o comunicare sigura intre 2 utilizatoriAlice si Bob.Protocolul Needham-SchroederParticipanti: Alice, Bob, un arbitru. Alice si arbitrul utilizeaza uncriptosistem simetric cu functia de criptare fA. Bob si arbitrulutilizeaza un criptosistem simetric cu functia de criptare fB .

1. Alice trimite arbitrului un mesaj cu propriul nume, cunumele lui Bob si cu un numar arbitrar RA: (A,B,RA).

2. Arbitrul genereaza aleator o cheie k , calculeaza fB(k ,A) sicalculeaza apoi fA(RA,B, k, fB(k ,A)); trimite aceastainformatie lui Alice


Autentificare cu schimb de chei

3. Alice descifreaza mesajul primit si obtine cheia k ; verifica siconfirma ca RA e identic cu numarul arbitrar trimis arbitruluila pasul 1; trimite lui Bob fB(k ,A).

4. Bob descifreaza si obtine cheia k ; genereaza un numararbitrar RB ; trimite lui Alice fk(RB).

5. Alice descifreaza mesajul primit, calculeaza RB − 1 sitrimite lui Bob fk(RB − 1).

6. Bob descifreaza si verifica faptul ca valoarea obtinuta esteRB − 1.

Facultatea De Matematica Iasi - Câteva protocoale criptograficecriptografie/note_curs_2019/... ·...

Documents

Transcript of Facultatea De Matematica Iasi - Câteva protocoale criptograficecriptografie/note_curs_2019/... ·...