binder 1

riptografie si Securitate

- Prelegerea 3 -Principiile de baza ale criptografiei moderne

Adela Georgescu, Ruxandra F. Olimid

Facultatea de Matematica si InformaticaUniversitatea din Bucuresti

1

Cuprins

1. Principiul 1 - Formularea riguroasa a definitiilor de securitate

2. Principiile 2 & 3 - Prezumptii si demonstratii de securitate

Criptografie si Securitate 2/8 ,

2

Criptografia moderna

I reprezinta o trecere de la criptografia (istorica) ca arta (panain anii 75) la criptografia ca stiinta (dupa anii 75)

I trei principii importartante pe care se bazeaza criptografiamoderna spre deosebire de criptografia clasica (istorica)

I Principiul 1 - orice problema criptografica necesita o definitieclara si riguroasa

I Principiul 2 - securitatea primitivelor criptografice se bazeazape prezumptii clare de securitate (de regula, probleme dificile)

I Principiul 3 - orice constructie criptografica trebuie sa fieinsotita de o demonstratie de securitate conform principiiloranterioare


3

Principiul 1 - Formularea riguroasa a definitiilor desecuritate

Necesitatea definitiilor exacte:

I vrem sa construim un sistem de criptare sigur; daca nu stimexact ce vrem sa obtinem, cum ne putem da seama daca saucand ne-am atins scopul?

I vrem sa folosim o schema de criptare ntr-un sistem mai mare;cum stim ce schema sa alegem sau care ni se potriveste?

I fiind date doua scheme, cum le putem compara? eficienta nueste un criteriu suficient;

I NU ne putem baza pe o idee intuitiva a ceea ce nseamnasecuritatea;

I Atentie! Formalizarea definitiilor NU este o sarcina triviala.


4

Un exemplu: criptarea sigura

I Cum ati defini notiunea de schema de criptare sigura?Posibile raspunsuri:(sunt corecte?)

1. Nici un adversar nu poate gasi cheia secreta fiind dat un textcriptat.

2. Nici un adversar nu poate gasi textul clar corespunzator unuitext criptat.

3. Nici un adversar nu poate determina nici macar un caracter (olitera) din textul clar corespunzator unui text criptat.

4. Nici un adversar nu poate determina informatii cu sens dintextul clar corespunzator unui text criptat.

Raspuns corect:

I Nici un adversar nu poate calcula nici o functie de textul clarpornind de la textul criptat.


5

I Definitia corecta de securitate prezentare matematica siformala

I Trebuie sa cuprinda:

(a) ce inseamna a sparge o schema de criptare - vezi slide-ulanterior

(b) de ce putere dispune adversarul:ce actiuni are voie sa intreprinda + putere computationala

Definitie

O schema de criptare este sigura daca nici un adversar avandputerea specificata nu poate sparge schema n modul specificat.


6

Principiul 2 - prezumptii de securitate si Principiul 3 -demonstratii de securitate

I majoritatea constructiilor criptografice moderne nu pot fidemonstrate ca fiind sigure neconditionat

I fara o demonstratie riguroasa, intuitia ca o schema estecorecta poate avea consecinte dezastruoase

I majoritatea demonstratiilor folosesc o abordare reductionista

Teorema

Constructia Y este sigura conform definitiei daca prezumptia Xeste adevarata.

I demonstratia va arata cum un adversar care sparge schema Ypoate ncalca prezumptia X.


7

Important de retinut!

I Criptografia clasica abordare ad-hocI Criptografia moderna abordare riguroasa


8


- Prelegerea 4 -Securitate perfecta



9

Cuprins

1. Definitie

2. One Time Pad


10

Securitate perfecta

I Primul curs: Sisteme de criptare istorice (substitutie,transpozitie, etc.) care pot fi sparte cu efort computationalfoarte mic

I Cursul de azi: Scheme perfect sigure care rezista n fata unuiadversar cu putere computationala nelimitata

I Insa...limitarile sunt inevitabile


11

Securitate perfecta (Shannon 1949)

Definitie

O schema de criptare peste un spatiu al mesajelor M este perfectsigura daca pentru orice probabilitate de distributie peste M,pentru orice mesaj m M si orice text criptat c pentru carePr [C = c] > 0, urmatoarea egalitate este ndeplinita:

Pr [M = m|C = c] = Pr [M = m]

I Pr [M = m] - probabilitatea a priori ca Alice sa aleaga mesajulm;

I Pr [M = m|C = c] - probabilitatea a posteriori ca Alice saaleaga mesajul m, chiar daca textul criptat c a fost vazut;

I securitate perfecta - daca Oscar afla textul criptat nu are niciun fel de informatie n plus decat daca nu l-ar fi aflat.


12

Securitate perfecta (Shannon 1949)

Definitie echivalenta

O schema de criptare (Enc ,Dec) este perfect sigura daca pentruorice mesaje m0,m1 M cu |m0| = |m1| si c C urmatoareaegalitate este ndeplinita:

Pr [Enck(m0) = c] = Pr [Enck(m1) = c]

unde k K este o cheie aleasa uniform.

I fiind dat un text criptat, este imposibil de ghicit daca textulclar este m0 sau m1

I cel mai puternic adversar nu poate deduce nimic despre textulclar dat fiind textul criptat


13

Un exemplu de cifru sigur - One Time Pad (OTP)

I Patentat in 1917 de Vernam (mai poarta denumirea de CifrulVernam)

I Algoritmul:1. Fie l > 0 iar M = C = K = {0, 1}l

2. Cheia k se alege cu distributie uniforma din spatiul cheilor K

3. Enc: data o cheie k {0, 1}l si un mesaj m {0, 1}l , ntoarcec = k m.

4. Dec: data o cheie k {0, 1}l si un mesaj criptat c {0, 1}l ,ntoarce m = k c .


14

Un exemplu de cifru sigur - One Time Pad (OTP)

mesaj: 0 1 1 0 0 1 1 1 1 cheie: 1 0 1 1 0 0 1 1 0

text criptat: 1 1 0 1 0 1 0 0 1

I avantaj - criptare si decriptare rapide

I dezavantaj - cheia foarte lunga (la fel de lunga precum textulclar)

I Este OTP sigur?


15

Teorema

Schema de criptare OTP este perfect sigura.

I securitatea perfecta nu este imposibila dar...

I cheia trebuie sa fie la fel de lunga precum mesajul

I incoveniente practice (stocare, transmitere)

I cheia trebuie sa fie folosita o singura data - one time pad - dece?

Exercitiu Ce se ntampla daca folosim o aceeasi cheie de doua oricu sistemul OTP ?


16

Limitarile securitatii perfecte

Teorema

Fie (Enc ,Dec) o schema de criptare perfect sigura peste un spatiual mesajelor M si un spatiu al cheilor K. Atunci |K| |M|.

Sau altfel spus:

Teorema

Nu exista nici o schema de criptare (Enc ,Dec) perfect sigura ncare mesajele au lungimea n biti iar cheile au lungimea (cel mult)n 1 biti.


17


I Schema OTP are securitate perfecta, dar este nepracticapentru majoritatea aplicatiilor;

I Securitate perfecta lungimea cheii lungimea mesajului.


18


- Prelegerea 5 -Criptografie computationala



19

Cuprins

1. Securitate perfecta vs. Criptografie Computationala

2. Criptografie computationala


20

Securitate perfecta vs. Criptografie computationala

I Am vazut scheme de criptare care pot fi demonstrate ca fiindsigure n prezenta unui adversar cu putere computationalanelimitata;

I Se mai numesc si informational-teoretic sigure;

I Adversarul nu are suficienta informatie pentru a efectua unatac;

I Majoritatea constructiilor criptografice moderne securitatecomputationala;

I Schemele moderne pot fi sparte daca un atacator are ladispozitie suficient spatiu si putere de calcul.


21

Securitate perfecta vs. Criptografie computationala

I Securitatea computationala mai slaba decat securitateainformational-teoretica;

I Prima se bazeaza pe prezumptii de securitate; a doua esteneconditionata;

I Intrebare: de ce renuntam la securitatea perfecta?

I Raspuns: datorita limitarilor practice!

I Preferam un compromis de securitate pentru a obtineconstructii practice.


22

Securitate computationala

I Ideea de baza: principiul 1 al lui Kerckhoffs

Un cifru trebuie sa fie practic, daca nu matematic,indescifrabil.

I Sunt de interes mai mare schemele care practic nu pot fisparte desi nu beneficiaza de securitate perfecta;

1. Sunt sigure n fata adversarilor eficienti care executa ataculntr-un interval de timp realizabil/fezabil;

2. Adversarii pot efectua un atac cu succes cu o probabilitatefoarte mica;

3. Se impune un noua modalitate de a defini securitatea:

Definitie

O schema este sigura daca orice adversar care dispune de timp polinomialn n (parametrul de securitate) efectueaza un atac cu succes numai cu oprobabilitate neglijabila.


23

Neglijabil si ne-neglijabil

I Intrebare: de ce nu cerem ca probabilitatea de succes aadversarului sa fie 0 (ci cerem sa fie neglijabila)?

I Raspuns: pentru ca adversarul poate sa ghiceasca (cheia,mesajul clar, etc.)


24


I n practica: este scalar si

I ne-neglijabil daca 1/230

I neglijabil daca 1/280I n teorie: este functie : Z0 R0 si p(n) este o functie

polinomiala n n (ex.: p(n) = nd , d constanta)

I ne-neglijabia n n daca p(n) : (n) 1/p(n)I neglijabila n n daca p(n),nd a.. n nd : (n) < 1/p(n)


25


I Intrebare: de ce aceasta definitie si nu alta?

(n) negl. n n p(n),nd a.. n nd : (n) < 1/p(n)I Raspuns:

I Atacul are loc cu probabilitate (n) ...

I ... deci trebuie repetat de aprox. 1/(n) ori ca sa reuseasca

I Dar din definitie 1/(n) > p(n) ...

I ... deci necesita un timp super-polinomial n n

Definitia semnifica faptul ca sistemul ramane sigur pentru unadversar PPT (Probabilistic Polinomial n Timp)


26


I Securitate perfecta vs. securitate computationala

I Neglijabil vs. ne-neglijabil


27


- Prelegerea 6 -Sisteme fluide



28

Cuprins

1. Definitie

2. Securitate

3. Moduri de utilizare

4. Exemple


29

Sisteme fluide

I Am vazut ca securitatea perfecta exista, dar nu este practicaccesibila - OTP;

I Facem un compromis de securitate, dar obtinem o solutieutilizabila n practica - sisteme de criptare fluide;

I Sistemele fluide sunt similare OTP, cu diferenta ca secventaperfect aleatoare de biti cu care se XOR-eaza mesajul clareste nlocuita de o secventa pseudoaleatoare de biti.


30

Pseudoaleatorismul

I Un sir pseudoaleator arata similar unui sir uniform aleatordin punct de vedere al oricarui algoritm polinomial;

I Altfel spus: un algoritm polinomial nu poate face diferentantre o secventa perfect aleatoare si una pseudoaleatore(decat cu probabilitate neglijabila);

I Sau: o distributie a secventelor de lungime l estepseudoaleatoare daca este nedistinctibila de distributiauniforma a secventelor de lungime l ;

I Mai exact: nici un algoritm polinomial nu poate spune daca osecventa de lungime l este esantionarea unei distributiipseudoaleatoare sau este o secventa total aleatoare delungime l .


31

Pseudoaleatorismul

I In analogie cu ce stim deja:

I pseudoaleatorismul este o relaxare a aleatorismului perfect

asa cum

I securitatea computationala este o relaxare a securitatiiperfecte


32

Sisteme fluide

I Revenind la criptarea fluida...

I ... aceasta presupune 2 faze:

I Faza 1: se genereaza o secventa pseudoaleatoare de biti,folosind un generator de numere pseudoaleatoare (PRG)

I Faza 2: secventa obtinuta se XOR-eaza cu mesajul clar

I Atentie! De multe ori cand ne referim la un sistem de criptarefluid consideram doar Faza 1


33

Sisteme fluide

OTP (One Time Pad) Sisteme fluide


34

PRG

I Ramane sa definim notiunea de generator de numere aleatoaresau PRG (PseudoRandom Generator);

I Acesta este un algoritm determinist care primeste osamanta relativ scurta s (seed) si genereaza o secventapseudoaleatoare de biti;

I Notam |s| = n, |PRG (s)| = l(n)I PRG prezinta interes daca:

l(n) n

(altfel NU genereaza aleatorism)


35

PRG

Definitie

Fie l() un polinom si G un algoritm polinomial determinist a..n {0, 1}n, G genereaza o secventa de lungime l(n).G se numeste generator de numere pseudoaleatoare (PRG) daca sesatisfac 2 proprietati:

1. Expansiune: n, l(n) n2. Pseudoaleatorism: algoritm PPT D, o funtie neglijabila

negl a..:

|Pr [D(r) = 1] Pr [D(G (s)) = 1]| negl(n)

unde r R {0, 1}l(n), s R {0, 1}nl(n) se numeste factorul de expansiune al lui G


36

Notatii

I D = DistringuisherI PPT = Probabilistic Polynomial Time

I x R X = x este ales uniform aleator din XI negl(n) = o functie neglijabila n (parametrul de securitate) n

In plus:

I Vom nota A un adversar (Oscar / Eve), care (n general) areputere polinomiala de calcul


37

Sisteme fluide

Definitie

Un sistem de criptare (Enc , Dec) definit peste (K,M, C) senumeste sistem de criptare fluid daca:

1. Enc : K M C

c = Enck(m) = G (k)m2. Dec : K C M

m = Deck(c) = G (k) cunde G este un generator de numere pseudoaleatoare cu factorulde expansiune l , k {0, 1}n, m {0, 1}l(n)


38

Securitate - interceptare unica

Teorema

Daca G este PRG, atunci sistemul fluid definit anterior este unsistem de criptare simetric de lungime fixa computational sigurpentru un atacator pasiv care care poate intercepta un mesaj.


39

Demonstratie intuitiva

I OTP este perfect sigur;

I Criptarea fluida se obtine din OTP prin nlocuirea pad cuG (k);

I Daca G este PRG, atunci pad si G (k) sunt indistinctibilepentru orice A adversar PPT;

I In concluzie, OTP si sistemul de criptare fluid suntindistinctibile pentru A.


40

Securitate - interceptare multipla

I Un sistem de criptare fluid n varianta prezentata estedeterminist: unui text clar i corespunde ntotdeauna acelasimesaj criptat;

I In consecinta, utilizarea unui sistem fluid n forma prezentatapentru criptarea mai multor mesaje (cu aceeasi cheie) estenesigura;

I Un sistem de criptare fluid se foloseste n practica n 2moduri: sincronizat si nesincronizat.


41

Moduri de utilizare

I modul sincronizat: partenerii de comunicatie folosesc pentrucriptarea mesajelor parti succesive ale secventeipseudoaleatoare generate;

I modul nesincronizat: partenerii de comunicatie folosesc pentrucriptarea mesajelor secvente pseudoaleatoare diferite.

Atentie!PRG va necesita 2 intrari: cheia k si un vector de initializare IV .


42

Modul sincronizat


43

Modul nesincronizat


44

Moduri de utilizare

Modul sincronizat

I mesajele sunt criptate nmod succesiv (participantiitrebuie sa stie care parti aufost deja folosite)

I necesita pastrarea starii

I mesajele succesive pot fipercepute ca un singurmesaj clar lung, obtinutprin concatenareameasajelor succesive

I se preteaza unei singuresesiuni de comunicatii

Modul nesincronizat

I mesajele sunt criptate nmod independent

I NU necesita pastrarea starii

I valorile IV1, IV2, . . . suntalese uniform aleator pentrufiecare mesaj transmis

I valorile IV1, IV2, . . . (dar siIV n modul sincronizat)fac parte din mesajulcriptat(sunt necesare pentrudecriptare)


45

Proprietati necesare ale PRG n modul nesincronizat

Fie G (s, IV ) un PRG cu 2 intrari:

I s = seed

I IV = Initialization Vector

PRG trebuie sa se satisfaca (cel putin):

1. G (s, IV ) este o secventa pseudoaleatoare chiar daca IV estepublic (i.e. securitatea lui G consta n securitatea lui s);

2. daca IV1 si IV2 sunt valori uniform aleatoare, atunci G (s, IV1)si G (s, IV2) sunt indistinctibile.


46

Exemple

I RC4 (Rons Cipher 4):I definit de R.Rivest, n 1987I utilizat n WEPI initial secret !

I WEP (Wired Equivalent Privacy):I standard IEEE 802.11, 1999 (retele fara fir)I nlocuit n 2003 de WPA (Wi-Fi Protected Access), 2004

WPA2 - IEEE 802.11i


47

Exemple

I A5/1:I definit n 1987 pentru Europa si SUAI A5/2 definit n 1989 ca o varianta mai slaba pentru alte zone

geograficeI utilizat n retelele de telefonie mobila GSMI initial secret !

I SEAL (Software-Optimized Encryption Algorithm)I definit de D.Coppersmith si P.Rogaway, n 1993I prezinta o implementare foarte eficienta pe procesoarele pe 32

de bitiI versiunea curenta (SEAL 3.0) este patentata IBM


48


I Notiunile de pseudoaleatorism, PRG

I OTP vs. Sisteme fluide

I Transpunerea sistemelor fluide n practica


49


- Prelegerea 6.1 -RC4



50

Cuprins

1. Informatii generale

2. Descriere

3. Securitate


51

Informatii generale

RC4 este:

I introdus de R. Rivest la MIT (1987);

I nregsitrat ca marca a RSA Data Security;

I pastrat secret pana n 1994 cand a devenit public;

I utilizat n WEP, SSL/TLS.


52

DescriereI RC4 este un sistem de criptare fluid pe octeti:

m {0, 1}8, c {0, 1}8I Ramane de definit PRG...


53

DescriereI 2 faze:

I initializare: determina starea interna, fara sa produca cheifluide;

I generare de chei fluide: modifica starea interna si genereaza unoctet (cheia fluida) care se XOR-eaza cu m pentru a obtine c ;

I Starea interna:I un tablou S de 256 octeti: S [0], . . . , S [255];I 2 indici i si j ;

I Toate operatiile se efectueaza pe octeti (i.e. (mod 256)).


54

Descriere

Faza 1. Initializare

I n = numarul octetilor din cheie, 1 n 256I j 0

for i = 0 to 255 doS [i ] i

end forfor i = 0 to 255 do

j j + S [i ] + k[i (mod n)]swap (S [i ], S [j ])

end fori 0j 0


55

Descriere

Faza 2. Generarea cheii fluide

I cheia se obtine octet cu octetI i i + 1

j j + S [i ]swap (S [i ], S [j ])return S [S [i ] + S [j ]]


56

Descriere

Detalii de implementare:

I 5 n 16 40 |k| 256;I memorie: 256 octeti (pentru S) si cateva variabile byte;

I operatii simple, rapid de executat.


57

Securitate

I primii octeti generati drept cheie fluida sunt total ne-aleatorisi ofera informatii despre cheie (Fluhrer, Mantin and Shamir2001)

I RC4 pe 104 biti (utilizat pentru WEP pe 128 biti) a fost spartn aprox. 1 min (algoritm al lui Tews, Weinmann, Pychkine2001, bazat pe idea lui Klein 2005)

I un atac recent arata ca pot fi determinati primii aprox. 200octeti din textul clar criptat cu RC4 n TLS cunoscand[228 232] criptari independente (Royal Holloway, 2013)


58


I RC4 - sistem de criptare fluid


59


- Prelegerea 6.2 -WEP



60

Cuprins

1. Informatii generale

2. Descriere

3. Securitate


61

Informatii generale

WEP este:

I definit ca standard IEEE 802.11 n 1999;

I folosit pentru criptare n cadrul retelor fara fir;

I nlocuit de WPA, apoi WPA2.


62

DescriereI WEP utilizeaza RC4;I Introduce n plus (Cyclic Redundancy Check) cu rolul de a

detecta eventuale erori de transmisiune;I IV este transmis catre destinatar, mpreuna cu c (IV ||c), fiind

necesar pentru decriptare .


63

Descriere

Detalii de implementare:

I |IV | = 24 (biti)I IV se utilizeaza n counter mode (0, 1, 2, . . . )


64

Securitate - Problema 1

Problema 1: Utilizarea multipla a lui IV

I Intrebare: Ce efect imediat are utilizarea multipla a lui IVpentru o cheie fixata k?

I Raspuns: Se obtine ntotdeauna aceeasi cheie fluida kr

IV1 = IV2 = IV kf 1 = kf 2 = PRG (IV ||k)I Intrebare: Sistemul ramane sigur n aceste conditii?

I Raspuns: NU!

c1 = m1 kf 1, c2 = m2 kf 2 c1 c2 = m1 m2Exemplu:

I daca A cunoaste m1, atunci poate determina m2I A poate determina m1 si m2 folosind analiza statistica


65


I Intrebare: Cate valori posibile poate lua IV?

I Raspuns: 224

I Cum un AP (Access Point) trimite aproximativ 1000pachete/s, valoarea lui IV se repeta la cel mult la cateva ore!

I Mai mult, exista echipamente care reseteaza IV la fiecarerepornire!


66

Securitate - Problema 2Problema 2: Liniaritatea

I Intrebare: Facand abstractie de CRC, A poate modificamesajul criptat transmis dupa bunul sau plac?

I Raspuns: DA!

(m1 m2) kf = (m1 kf )m2Exemplu:

I A intercepteaza c1 si l transforma n c2


67


I CRC poate detecta erorile de transmisiune (neintentionate)dar nu si modificarile premeditate (intentionate)

I In aceste conditii, A poate modifica mesajele transmise:I prin XOR-are cu secvente (convenabile) de biti

I prin amestecarea bitilor din mesajul interceptat


68


I O proasta implementare / utilizare poate diminua considerabilsecuritatea unui sistem!


69


- Prelegerea 7 -Securitate semantica



70

Cuprins

1. Securitate - interceptare simpla

2. Securitate - interceptare multipla


71

Securitate semantica - interceptare simpla

I Reamintim: (Enc ,Dec) peste spatiul (K,M, C) este perfectsigura dacam0,m1 M cu |m0| = |m1| are loc egalitatea

{Enck(m0)} = {Enck(m1)}

(distributiile sunt identice)

pentru k R K;I Incercam o relaxare:m0,m1 M cu |m0| = |m1| are loc

{Enck(m0)} {Enck(m1)}

(distributiile sunt indistinctibile computational)

pentru k R K;Insa adversarul trebuie sa aleaga m0 si m1 explicit.


72


I Vom defini securitatea semantica pe baza unui experiment deindistinctibilitate Priv eavA,pi(n) unde pi = (Enc ,Dec) este schemade criptare iar n este parametrul de securitate al schemei pi

I Personaje participante: adversarul A care ncearca sa spargaschema si un provocator (challenger).

I Trebuie sa definim capabilitatile adversarului: n contextulsistemelor de criptare fluide, el poate vedea un singur textcriptat cu o anume cheie, fiind un adversar pasiv care poaterula atacuri n timp polinomial.


73

Experimentul Priv eavA,pi(n)


74



75



76



77


I Output-ul experimentului este 1 daca b = b si 0 altfel. DacaPriv eavA,pi(n) = 1, spunem ca A a efectuat experimentul cusucces.


78


Definitie

O schema de criptare pi = (Enc ,Dec) este indistinctibila nprezenta unui atacator pasiv daca pentru orice adversar A exista ofunctie neglijabila negl asa ncat

Pr[Priv eavA,pi(n) = 1] 12 + negl(n).

I Un adversar pasiv nu poate determina care text clar a fostcriptat cu o probabilitate semnificativ mai mare decat daca arfi ghicit (n sens aleator, dat cu banul).


79

Securitate pentru interceptare multipla

I In definitia precedenta am considerat cazul unui adversar careprimeste un singur text criptat;

I In realitate, n cadrul unei comunicatii se trimit mai multemesaje pe care adversarul le poate intercepta;

I Definim ce nseamna o schema sigura chiar si n acesteconditii.


80

Experimentul PrivmultA,pi (n)


81



82



83



84


I Output-ul experimentului este 1 daca b = b si 0 altfel;I Definitia de securitate este aceeasi, doar ca se refera la

experimentul de mai sus.

I Securitatea pentru interceptare simpla nu implica securitatepentru interceptare multipla!


85

Securitate pentru interceptare multipla

Definitie

O schema de criptare pi = (Enc ,Dec) este indistinctibila nprezenta unui atacator pasiv daca pentru orice adversar A exista ofunctie neglijabila negl asa ncat

Pr[PrivmultA,pi (n) = 1] 12 + negl(n).

Teorema

O schema de criptare (Enc ,Dec) unde functia Enc estedeterminista nu are proprietatea de securitate la interceptaremultipla conform cu definitia de mai sus.


86

Demonstratie

I Intuitiv, am vazut ca schema OTP este sigura doar cand ocheie este folosita o singura data;

I La sistemele fluide se ntampla acelasi lucru;

I Vom considera un adversar A care ataca schema (n sensulexperimentului PrivmultA,pi (n)


87

Demonstratie


88

Demonstratie


89

Demonstratie


90

Demonstratie


91

Demonstratie

I Daca c1 = c2, atunci A ntoarce 0, altfel A ntoarce 1.I Analizam probabilitatea ca A sa ghiceasca b: daca b = 0,

acelasi mesaj este criptat mereu (m10 = m20) iar c1 = c2 si deci

A ntoarce mereu 0;I Daca b = 1, atunci (m11 6= m21) iar c1 6= c2 si deci A ntoarce

mereu 1.


92


I Securitate - interceptare simpla ; securitate - interceptaremultipla

I Schemele deterministe nu sunt sigure la interceptare multipla


93


- Prelegerea 8 -Sisteme de criptare bloc



94

Cuprins

1. Definitie

2. Constructie

3. Moduri de utilizare

4. Exemple


95

Criptografia simetrica

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

I Vom studia sisteme simetrice care cripteaza cate n bitisimulan - sisteme de criptare bloc;


96





97





98

Sisteme bloc vs. sisteme fluide


99


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

Sisteme fluide

I criptarea bitilor serealizeaza individual

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

Sisteme bloc

I criptarea se realizeaza nblocuri de cate n biti

I criptarea unui bit din textulclar este dependenta debitii din textul clar careapartin aceluiasi bloc


100


... d.p.d.v. traditional, n practica:

Sisteme fluide

I necesitati computationalereduse

I utilizare: telefoane mobile,dispozitive ncorporate,PDA

I par sa fie mai putin sigure,multe sunt sparte

Sisteme bloc

I necesitati computationalemai avansate

I utilizare: internet

I par sa fie mai sigure,prezinta ncredere mai mare


101

Sisteme bloc

I Introducem notiunea de permutare pseudoaleatoare sauPRP(PseudoRandom Permutation)


I PRP sunt necesare pentru constructia sistemelor bloc

asa cum

I PRG sunt necesare pentru constructia sistemelor fluide


102

Sisteme bloc




asa cum



103

Sisteme bloc




asa cum



104

Sisteme bloc

Sisteme fluide Sisteme bloc


105

PRP

I Ramane sa definim notiunea de permutare pseudoaleatoaresau PRP (PseudoRandom Permutation);

I Acesta este o functie determinista si bijectiva care pentru ocheie fixata produce la iesire o permutare a intrarii ...

I ... indistinctibila fata de o permutare aleatoare;

I In plus, atat functia cat si inversa sa sunt eficient calculabile.


106

PRP






107

PRP






108

PRP






109

PRP

Definitie

O permutare pseudoaleatoare definita peste (K,X ) este o functiebijectiva

F : X K Xcare satisface urmatoarele proprietati:

1. Eficienta: k K, x X , algoritmi deterministi PPT carecalculeaza Fk(x) si F

1k (x)

2. Pseudoaleatorism: algoritm PPT D, o functie neglijabilanegl a..:

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

unde r R Perm(X ), k R K


110

Notatii

I Fk(x) = F (k, x)o cheie este n general (aleator) aleasa si apoi fixata

I Perm(X ) = multimea tuturor functiilor bijective de la X la XI X = {0, 1}n

I D = Distringuisher care are acces la oracolul de evaluare afunctiei


111

PRF

I Introducem notiunea de functie pseudoaleatoare sau PRF(PseudoRandom Function)...

I ... ca o generalizare notiunii de permutare pseudoaleatoare;

I Acesta este o functie cu cheie care este indistinctibila fata deo functie aleatoare (cu acelasi domeniu si multime de valori).


112

PRF




Criptografie si Securitate ,

113

PRF





114

PRF

Definitie

O functie pseudoaleatoare definita peste (K,X ,Y) este o functiebijectiva

F : X K Ycare satisface urmatoarele proprietati:

1. Eficienta: k K, x X , algoritm PPT care calculeazaFk(x)

2. Pseudoaleatorism: algoritm PPT D, o functie neglijabilanegl a..:

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

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


115

Notatii

I Fk(x) = F (k, x)o cheie este n general (aleator) aleasa si apoi fixata

I Func(X , Y ) = multimea functiilor de la X la YI X = {0, 1}n, Y = {0, 1}n

consideram n general ca PRF pastreaza lungimea

I D = Distringuisher care are acces la oracolul de evaluare afunctiei


116

PRP PRF

I Intrebare: De ce PRF poate fi privita ca o generalizare aPRP?

I Raspuns: PRP este PRF care satisface:

1. X = Y

2. este inversabila

3. calculul functiei inverse este eficient


117

PRP PRF



1. X = Y

2. este inversabila



118

PRP PRF



1. X = Y

2. este inversabila



119

Constructii

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

Intrebare: Care dintre aceste constructii este triviala?


120

Constructii







121

Constructii







122

Constructii







123

Constructii







124

Constructii

Raspuns: PRP PRF

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

1. X = Y2. este inversabila



125

Constructii

Raspuns: PRP PRF

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

1. X = Y2. este inversabila



126

Constructii



I PRP PRF Pornind de la PRP se poate construi PRF



127

PRF PRG

I Consideram 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 Intrebare: De ce este G sigur?

I Raspuns: Fk() este indistinctibila fata de o functie aleatoare G (k) este indistinctibila fata de o secventa aleatoare delungime ln.

I Avantaj: Constructia este paralelizabila


128

PRF PRG

I Consideram 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)





129

PRF PRG


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





130

PRF PRG


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


I Raspuns: Fk() este indistinctibila fata de o functie aleatoare

G (k) este indistinctibila fata de o secventa aleatoare delungime ln.



131

PRF PRG


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





132

PRF PRG


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





133

Constructii

I PRF PRG Pornind de la PRF se poate construi PRG





134

PRG PRFI Consideram G : K K2 PRG cu |K| = n:

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

G0(k) si G1(k) sunt prima si a doua jumatate a iesirii din PRG

I Construim F : K {0, 1} K PRF :Fk(0) = G0(k), Fk(1) = G1(k)

Fk(0) ntoarce prima jumatate a secventei pseudoaleatoare G(k)

Fk(1) ntoarce a doua jumatate a secventei pseudoaleatoare G(k)

I Intrebare: De ce este F sigura?I Raspuns: G (k) este indistinctibila fata de o secventa aleatoare

de lungime 2n G0(k) si G1(k) sunt indistinctibile fata de o secventaaleatoare de lungime n pentru k R {0, 1}, Fk() este indistinctibila fata de ofunctie aleatoare.


135


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








136


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





I Intrebare: De ce este F sigura?

I Raspuns: G (k) este indistinctibila fata de o secventa aleatoarede lungime 2n G0(k) si G1(k) sunt indistinctibile fata de o secventaaleatoare de lungime n pentru k R {0, 1}, Fk() este indistinctibila fata de ofunctie aleatoare.


137


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






de lungime 2n

G0(k) si G1(k) sunt indistinctibile fata de o secventaaleatoare de lungime n pentru k R {0, 1}, Fk() este indistinctibila fata de ofunctie aleatoare.


138


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






de lungime 2n G0(k) si G1(k) sunt indistinctibile fata de o secventaaleatoare de lungime n

pentru k R {0, 1}, Fk() este indistinctibila fata de ofunctie aleatoare.


139


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








140

PRG PRFI Constructia pentru un singur bit de intrare...


141

PRG PRFI ...se poate generaliza pentru un numar oarecare de biti


142

PRG PRF

I Constructia poate fi reprezentata ca un arbore binar cu cheiak radacina;

I Pentru un nod de valoare k , copilul stang ia valoarea G0(k )si copilul drept ia valoare G1(k

);

I Valoarea functiei Fk(x) = Fk(x0, . . . , xn1) este obtinuta prinparcurgerea arborelui n functie de x ;

I Adancimea arborelui este liniara n n (n);

I Dimensiunea arborelui este exponentiala n n (2n);

I NU se utilizeaza n practica din cauza performantei scazute.


143

PRG PRF



);






144

PRG PRF



);






145

PRG PRF



);






146

PRG PRF



);






147

PRG PRF



);






148

Constructii


I PRG PRF Pornind de la PRG se poate construi PRF




149

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 Constructia foloseste runde Feistel, pe care le vom prezentantr-un curs ulterior.


150

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 Constructia foloseste runde Feistel, pe care le vom prezentantr-un curs ulterior.


151

Moduri de utilizare

I Sa continuam cu ceva mai practic...

I Intrebare: Ce se ntampla daca lungimea mesajului clar estemai mica decat dimensiunea unui bloc?

I Raspuns: Se completeaza cu biti: 1 0 . . . 0;

I Intrebare: Ce se ntampla daca lungimea mesajului clar estemai mare decat lungimea unui bloc?

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

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


152

Moduri de utilizare








153

Moduri de utilizare








154

Moduri de utilizare








155

Moduri de utilizare








156

Moduri de utilizare








157

Modul ECB (Electronic Code Book)


158


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 Intrebare: Ce informatii poate sa ofere modul de criptare ECBunui adversar pasiv?

I Raspuns: Un adversar pasiv detecteaza repetarea unui bloc detext clar pentru ca se repeta blocul criptat corespunzator;

I Modul ECB NU trebuie utilizat n practica!


159










160










161










162










163










164










165

Modul CBC (Cipher Block Chaining)


166


I IV este o ales n mod aleator la criptare;

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


I Este secvential, un dezavantaj major daca se poate utilizaprocesarea paralela.


167







168







169







170

Modul OFB (Output FeedBack)


171


I Genereaza o secventa pseudoaleatoare care se XOR-eazamesajului clar;



I Fk nu trebuie neaparat sa fie inversablia;

I Este secvential, nsa secventa pseudoaleatoare poate fipre-procesata anterior decriptarii.


172








173








174








175








176

Modul CTR (Counter)


177

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 In plus, secventa pseudoaleatoare poate fi pre-procesataanterior decriptarii.


178

Modul CTR (Counter)








179

Modul CTR (Counter)








180

Modul CTR (Counter)








181

Modul CTR (Counter)








182

Modul CTR (Counter)








183

Exemple

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

(lungime cheie = 64 biti, lungime bloc = 64 biti)I spart prin cautare exhaustiva n 1997

I AES (Advanced Encryption Standard):I algoritmul Rijndael propus de J. Daemen si V.RijmanI adoptat ca standard NIST n 2001

(lungime cheie = 128, 192, 256 biti, lungime bloc = 128 biti)


184

Exemple

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

(lungime cheie = 64 biti, lungime bloc = 64 biti)I spart prin cautare exhaustiva n 1997

I AES (Advanced Encryption Standard):I algoritmul Rijndael propus de J. Daemen si V.RijmanI adoptat ca standard NIST n 2001

(lungime cheie = 128, 192, 256 biti, lungime bloc = 128 biti)


185


I Sisteme bloc vs. sisteme fluide

I Notiunile de PRP, PRF

I Constructii specifice PRG, PRF, PRP

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


186


- Prelegerea 9 -Constructii practice pentru PRP



187

Cuprins

1. Sisteme bloc ca PRP

2. Retele de substitutie - permutare

3. Retele Feistel


188

Sisteme bloc ca PRP

I Am vazut ca sistemele de criptare bloc folosesc PRP;


189

Sisteme bloc ca PRP

I In criteriile de evaluare pentru adoptarea AES s-a mentionat:

The security provovided by an algorithm is the most importantfactor... Algorithms will be judged on the following factors...

The extent to which the algorithm output isindistinguishable from a random permutation on the

input block.

I Intrebare: Cum se obtin PRP n practica?


190

Sisteme bloc ca PRP

I Ideal ar fi sa se utilizeze o permutare aleatoare pe n biti;

I Ar fi necesari n 2n biti pentru stocare;I Pentru n = 50 este necesara o capacitate de stocare de 200TB !

I Sistemele bloc au n general n 64 sau n 128 biti;I In consecinta, NU se poate utiliza o (singura) permutare

aleatoare!


191

Claude Elwood Shannon (1916 - 2001)

I Shannon propuneutilizarea mai multorpermutari de dimensiunemai mica;

I Acesta este al doilearezultat al lui Shannonpe care l studiem, dupasecuritatea perfecta.

[Wikipedia]


192

Retele de substitutie - permutare

I Se construieste permutarea F , pe baza mai multor permutarialeatoare fi de dimensiune mai mica;

I Consideram F pe 128 biti si 16 permutari aleatoare f1, . . . , f16pe cate 8 biti;

I Pentru x = x1|| . . . ||x16, x {0, 1}128 xi {0, 1}8:

Fk(x) = f1(x1)|| . . . ||f16(x16)

I Spunem ca {fi} introduc confuzie n F .


193


I Intrebare: Considerand capacitatea necesara de stocare, esteF fesabila?

I Raspuns: DA.

I Fiecare fi necesita 8 28 biti pentru stocare;I Sunt 16 functii {fi}, deci n total F necesita pentru stocare 16 8 28 32KB.


194


I Intrebare: Este F PRP?

I Raspuns: NU.

I Fie x si x 2 intrari care difera numai prin primul bit:

msb(x) 6= msb(x )

I Atunci Fk(x) si Fk(x ) difera numai prin primul byte;

I In cazul unei permutari aleatoare, acest lucru nu se ntampla.


195


I F se transforma n PRP n 2 pasi:I Pasul 1: se introduce difuzie prin amestecarea (permutarea)

bitilor de iesire;

I Pasul 2: se repeta o runda (care presupune confuzie sidifuzie) de mai multe ori;

I Repetarea confuziei si difuziei face ca o modificarea unuisingur bit de intrare sa fie propagata asupra tutoror bitilor deiesire;

I Un exemplu pentru 2 runde si intrarea x :I x = Fk(x);I x1 se obtine prin reordonarea bitilor din x

;I x 1 = Fk(x1);I x2 se obtine prin reordonarea bitilor din x

1.


196


I O retea de substitutie-permutare este o implementare aconstructiei anterioare de confuzie-difuzie n care functiile {fi}sunt fixe (i.e. nu depind de cheie);

I {fi} se numesc S-boxes (Substitution-boxes);I S-box-urile raman n continuare permutari;

I Cum nu mai depind de cheie, aceasta este utilizata n alt scop;

I Din cheie se obtin mai multe chei de runda (sub-chei) nurma unui proces de derivare a cheilor (key schedule);

I Fiecare cheie de runda este XOR-ata cu valorile intermediaredin fiecare runda.


197



198


I Exista 2 principii de baza n proiectarea retelelor de substitutie- permutare:

I Principiul 1: Inversabilitatea S-box-urilor;

I Principiul 2: Efectul de avalansa.


199

Principul 1: Inversabilitatea S-box

I O retea de substitutie-permutare trebuie sa fie inversabila;

I Daca fiecare runda este inversabila, atunci reteaua esteinversabila;

I Intr-o runda:I XOR este inversabil;I Permutarea finala a bitilor de iesire este inversabila;

I In concluzie, daca toate S-box-urile sunt inversabile, atuncireteaua este inversabila;

I Principiul 1 - necesitate functionala (pentru decriptare).


200

Principul 2: Efectul de avalansa

I Un singur bit modificat la intrare trebuie sa afecteze toti bitiidin secventa de iesire;

I Efectul de avalansa apare ntr-o retea de substitutie-permutaredaca:

1. S-box-urile sunt proiectate a.. un singur bit schimbat laintrare sa schimbe cel putin 2 biti de la iesire;

2. Permutarea este proiectata a.. bitii de la iesirea unui S-box safie mpartiti ntre intrarile n S-box-uri diferite la rundaurmatoare.

I Principiul 2 - necesitate de securitate.


201

Principul 2: Efectul de avalansa

I Intrabare: De ce sunt suficiente cele 2 proprietati pentruobtinerea efectului de avalansa?

I Presupunem 2 intrari care difera printr-un singur bit;

I Dupa Runda 1, iesirile difera prin 2 biti (Proprietatea 1);

I La intrarea n Runda 2, bitii care difera sunt intrari nS-box-uri diferite (Proprietatea 2);

I Dupa Runda 2, iesirile difera prin 4 biti (Proprietatea 1);

I Urmand acest rationament, dupa Runda r , iesirile difera prinaproximativ 2r biti;

I In concluzie, un sistem bloc cu intrarea de n = 2r biti obtineefectul de avalansa dupa cel putin r runde.


202

Retele Feistel

I Se aseamana retelelor de substitutie-permutare n sensul capastreaza aceleasi elementele componente: S-box, permutare,procesul de derivare a cheii, runde;

I Se diferentiaza de retelele de substitutie-permutare prinproiectarea de nivel nalt;

I Introduc avantajul major ca S-box-urile NU trebuie sa fieinversabile;

I Permit asadar obtinerea unei structuri inversabile folosindelemente neinversabile.


203

Horst Feistel (1915 - 1990)

[Wikipedia]

I Structurile simetriceutilizate n constructiasistemelor bloc poartanumele lui Feistel;

I Munca sa de cercetare laIBM a condus la sistemulde criptare Lucifer si maitarziu la DES.


204

Retele Feistel


205

Retele Feistel

I Intrarea n runda i se mparte n 2 jumatati: Li1 si Ri1 (i.e.Left si Right);

I Iesirile din runda i sunt:

Li = Ri1

Ri = Li1 fi (Ri1)

I Functiile fi depind de cheia de runda, derivand dintr-o functiepublica fi :

fi (R) = fi (ki ,R)


206

Retele Feistel

I Retelele Feistel sunt inversabile indiferent daca functiile fi suntinversabile sau nu;

I Fie (Li ,Ri ) iesirile din runda i ;

I Intrarile (Li1,Ri1) n runda i sunt:

Ri1 = Li

Li1 = Ri fi (Ri1)


207

Constructii

Am omis n cursurile anterioare ultima constructie:


I PRG PRF Pornind de la PRG se poate construi PRF




208

PRF PRP

I Revenim acum asupra constructiei, cand cunoastem notiuneade runda Feistel;

I Consideram o singura runda Feistel pentru care f1(x) = Fk(x),cu F PRF;

I Intrebare: Este aceasta constructie PRP?


209

PRF PRPI Raspuns: NU.

I Constructia este o permutare pe {0, 1}n,...I ... este inversabila,...

I ... dar iesirea nu este o secventa pseudoaleatoare: primii n/2biti de iesire sunt egali cu ultimii n/2 biti de intrare;

I Se mareste numarul de runde Feistel, pastrand fi (x) = Fki (x),unde ki sunt chei independente;

I Pentru i = 3 se obtine PRP;

I Altfel spus, o retea Feistel de 3 runde construita folosind 3PRF f1(x) = Fk1(x), f2(x) = Fk2(x) si f3(x) = Fk3(x) cuk1, k2 si k3 independente este PRP.


210


I Retele de substitutie-permutare

I Retele Feistel


211


- Prelegerea 9.1 -Data Encryption Standard - DES



212

Cuprins

1. Scurt istoric

2. DES cu numar redus de runde

3. Securitatea sistemului DES


213

DES - Data Encryption Standard

I 1970 - Horst Feistel proiecteaza Lucifer, o familie de cifruribloc, la IBM, cu lungime cheie = 128 biti si lungime bloc =128 biti;

I 1973 - NIST initiaza o cerere pentru propuneri n vedereastandardizarii cifrurilor bloc n SUA;IBM trimite o varianta de Lucifer.

I 1976 - NIST adopta Lucifer modificat ca standard DES culungime cheie = 56 biti si lungime bloc = 64 biti.

I 1997 - DES este spart prin cautare exhaustiva (forta bruta).

I 2001 - NIST adopta Rinjdael ca noul standard AES n locul luiDES.


214

DES


215

Descriere DES

I DES este o retea de tip Feistel cu 16 runde si o cheie pe 56biti;

I Procesul de derivare a cheii (key schedule) obtine o sub-cheiede runda ki pentru fiecare runda pornind de la cheia master k ;

I Functiile de runda fi (R) = f (ki ,R) sunt derivate din aceeasifunctie principala f si nu sunt inversabile;

I Fiecare sub-cheie ki reprezinta permutarea a 48 biti din cheiamaster;

I Intreaga procedura de obtinere a sub-cheilor de runda este fixasi cunoscuta, singurul secret este cheia master .


216

Functia f (ki ,R)


217

Functia f (ki ,R)

I Functia f este, n esenta, o retea de substitutie-permutare cudoar o runda.

I Pentru calculul f (ki ,R) se procedeaza astfel:

1. R este expandat la un bloc R de 48 biti cu ajutorul uneifunctii de expandare R = E (R).

2. R este XOR-at cu ki iar valoarea rezultata este mpartita n 8blocuri de cate 6 biti.

3. Fiecare bloc de 6 biti trece printr-un SBOX diferit rezultand ovaloare pe 4 biti.

4. Se concateneaza blocurile rezultate si se aplica o permutare,rezultand n final un bloc de 32 biti.

I De remarcat: Toata descrierea lui DES, inclusiv SBOX-urilesi permutarile sunt publice.


218

SBOX-urile din DESI Formeaza o parte esentiala din constructia DES;I DES devine mult mai vulnerabil la atacuri daca SBOX-urile

sunt modificate usor sau daca sunt alese aleatorI Primul si ultimul bit din cei 6 de la intrare sunt folositi pentru

a alege linia din tabel, iar bitii 2-5 sunt folositi pentru coloana;output-ul va consta din cei 4 biti aflati la intersectia liniei sicoloanei alese.

I Modificarea unui bit de la intrare ntotdeauna afecteaza celputin doi biti de la iesire.


219

Efectul de avalansa

I DES are un puternic efect de avalansa generat de ultimaproprietate mentionata mai sus si de permutarile folosite;

I Pentru a vedea aceasta, vom urmari diferenta ntre valorileintermediare dintr-un calcul DES a doua valori de intrare caredifera printr-un singur bit;

I Notam cele doua valori cu (L0,R0) si (L0,R0) unde R0 = R0;

I Dupa prima runda, valorile (L1,R1) si (L1,R1) nca diferaprintr-un singur bit, desi acum diferenta e n partea dreapta;

I In a doua runda DES, R1 si R1 trec prin functia f ;


220

Efectul de avalansaI Presupunand ca bitul n care R1 si R1 difera nu este duplicat

n pasul de expandare, ele nca difera printr-un bit nainte deaplicarea SBOX-ului;

I Dupa SBOX, valorile intermediare difera n cel putin doi biti;

I (L2,R2) si (L2,R2) difera n trei biti: 1-bit diferenta ntre L2si L2

si 2-biti diferenta ntre R2 si R2;

I Permutarea din f mprastie diferenta dintre R2 si R2 ndiferite regiuni ale lor;

I La urmatoarea runda fiecare bit care difera va fi folosit caintrare ntr-un SBOX diferit, rezultand o diferenta de 4 bitintre jumatatile drepte ale valorilor intermediare;

I Efectul este exponential si dupa 7 runde toti cei 32 biti vor fimodificati.


221

Efectul de avalansa

I Dupa 8 runde toti bitii din jumatatea stanga vor fi modificati;

I DES are 16 runde deci efectul de avalansa este atins foarterepede;

I Deci DES aplicat pe doua intrari similare ntoarce iesiricomplet diferite si independente;

I Efectul se datoreaza si permutarilor alese cu grija (esteverificat faptul ca permutari aleatoare nu ofera acelasi efectputernic de avalansa).


222

Atacuri pe DES cu numar redus de runde

I Pentru a ntelege securitatea DES vom studia mai ntaicomportametul lui DES pe un numar redus de runde (maxim3);

I Sigur, DES cu 3 runde nu este o functie pseudoleatoarepentru ca efectul de avalansa nca nu e complet;

I Vom arata cateva atacuri cu text clar care gasesc cheia k ;

I Adversarul are deci acces la perechi de forma {(xi , yi )} cuyi = DESk(xi );

I In descrierea atacurilor, ne vom concentra asupra unei singureperechi (x , y).


223

DES cu o singura runda

I Cunoastem x = (L0,R0) si y = (L1,R1) unde

I L1 = R0I R1 = L0 f1(R0)

I De asemenea, f1(R0) = R1 L0


224

DES cu o singura runda

I Aplicand P1(R1 L0) obtinem o valoare intermediara carereprezinta iesirea din cele 8 SBOX-uri;

I Intrarea n SBOX-uri este E (R0) k1; R0 este cunoscut, la feliesirea din SBOX-uri;

I Pentru fiecare iesire din SBOX, exista 4 valori posibile aleportiunii corespunzatoare de 6 biti din cheia k1 care arconduce la acea valoare.


225

DES cu una sau doua runde

I Atac DES cu o singura runda

I Am redus numarul cheilor posibile de la 248 la 48 = 216;

I Acum se pot verifica pe rand toate variantele si recuperacomplet cheia.

I Atac DES cu doua runde

I Atacul gaseste cheile k1 si k2 n timp 2 216 atunci cand secunoaste o pereche text clar/text criptat.


226

DES cu trei runde

I Nu se cunosc R1, L2 si deci nicitoate intrarile/iesirile din fiecarefunctie f ;

I Atacul anterior nu functioneaza; unnou atac va explora relatiile dintreiesirile respectiv intrarile n f1 si f3;

I Atacul traverseaza spatiul cheilorpentru fiecare jumatate a cheiimaster si, n timp 2 228 vaproduce cate 212 variante pentrufiecare jumatate a cheii;

I Complexitatea timp totala este2 228 + 224 < 230.


227

Securitatea sistemului DES

I Inca de la propunerea sa, DES a fost criticat din doua motive:

1. Spatiul cheilor este prea mic facand algoritmul vulnerabil laforta bruta;

2. Criteriile de selectie a SBOX-urilor au fost tinute secrete si ar fiputut exista atacuri analitice care explorau proprietatilematematice ale SBOX-urilor, cunoscute numai celor care l-auproiectat.

I Cu toate acestea....

I Dupa 30 ani de studiu intens, cel mai bun atac practic ramanedoar o cautare exhaustiva pe spatiul cheilor;

I O cautare printre 256 chei este fezabila azi (dar netriviala);

I In 1977, un calculator care sa efectueze atacul ntr-o zi ar ficostat 20.000.000$;


228


I Primul atac practic a fost demonstrat n 1997 cand un numarde provocari DES au fost propuse de RSA Security sirezolvate;

I Prima provocare a fost sparta n 1997 de un proiect care afolosit sute de calculatoare coordonate prin Internet; a durat96 de zile;

I A doua provocare a fost sparta anul urmator n 41 de zile;

I Impresionant a fost timpul pentru a treia provocare: 56 de ore;

I S-a construit o masina n acest scop, Deep Crack cu un costde 250.000$


229


Figure: Deep Crack-construita pentru cautare exhaustiva DES n 1998

I Ultima provocare a fost sparta n 22 de ore (efort combinat dela ultimele doua provocari);

I Atacurile prin forta bruta pe DES au devenit un studiu de cazn ncercarea de a micsora costurile;


230


Figure: COPACABANA-Cost Optimized Parallel Code-Breaker

I In 2006, o echipa de cercetatori de la universitatile Bochum siKiel din Germania a construit masina COPACABANA (CostOptimized Parallel Code-Breaker) care permite gasirea cheiiDES cu un timp de cautare mediu de mai putin de 7 zile, laun cost de 10.000$.


231


I O alta problema a sistemului DES, mai putin importanta, estelungimea blocului relativ scurta (64 biti);

I Securitatea multor constructii bazate pe cifruri bloc depindede lungimea blocului;

I In modul de utilizare CTR, daca un atacator are 227 perechitext clar/text criptat, securitatea este compromisa cuprobabilitate mare;

I Concluzionand, putem spune ca insecuritatea sistemului DESnu are a face cu structura interna sau constructia in sine (careeste remarcabila), ci se datoreaza numai lungimii cheii preamici.


232

Criptanaliza avansata

I La sfarsitul anilor 80, Biham si Shamir au dezvoltat o tehnicanumita criptanaliza diferentiala pe care au folosit-o pentru unatac mpotriva DES;

I Atacul presupune complexitate timp 237 (memorie neglijabila)dar cere ca atacatorul sa analizeze 236 texte criptate obtinutedintr-o multime de 247 texte clare alese;

I Din punct de vedere teoretic, atacul a fost o inovatie, darpractic e aproape imposibil de realizat;

I La inceputul anilor 90, Matsui a dezvoltat criptanaliza liniaraaplicata cu succes pe DES;

I Desi necesita 243 texte criptate, avantajul este ca textele clarenu trebuie sa fie alese de atacator, ci doar cunoscute de el;

I Problema nsa ramane aceeasi: atacul e foarte greu de pus npractica.


233

Criptanaliza diferentiala

I Catalogheaza diferente specifice ntre texte clare care producdiferente specifice n textele criptate cu probabilitate mai maredecat ar fi de asteptat pentru permutarile aleatoare;

I Fie un cifru bloc cu blocul de lungime n si x ,y {0, 1}n;I Spunem ca diferentiala (x ,y ) apare cu probabilitate p

daca pentru intrari aleatoare x1, x2 cu

x1 x2 = xsi o alegere aleatoare a cheii k

Pr [Fk(x1) Fk(x2) = y ] = pI Pentru o functie aleatoare, probabilitatea de aparitie a unei

diferentiale nu e mai mare decat 2n;I La un cifru bloc slab, ea apare cu o probabilitate mult mai

mare;


234

Criptanaliza diferentiala

I Daca o diferentiala exista cu probabilitate p 2n, cifrul blocnu mai este permutare pseudoaleatoare;

I Ideea este de a folosi multe diferentiale cu p usor mai maredecat 2n pentru a gasi cheia secreta folosind un atac cu textclar ales;

I Criptanaliza diferentiala a fost folosita cu succes pentru aataca cifruri bloc (altele decat DES si AES), de pilda FEAL-8;


235

Criptanaliza liniara

I Metoda considera relatii liniare ntre intrarile si iesirile unuicifru bloc;

I Spunem ca portiunile de biti i1, , il si i1, , il au distantap daca pentru orice intrare aleatoare x si orice cheie k

Pr [xi1 xil yi 1 yi l = 0] = punde y = Fk(x).

I Pentru o functie aleatoare se asteapta ca p = 0.5;

I Matsui a aratat cum se poate folosi o diferenta p mare pentrua sparge complet un cifru bloc;

I Necesita un numar foarte mare

binder 1

Documents