riptogra e ˘si Securitate -...

riptografie si Securitate

- Prelegerea 6 -Sisteme fluide

Adela Georgescu, Ruxandra F. Olimid

Facultatea de Matematica si InformaticaUniversitatea din Bucuresti

Cuprins

1. Definitie

2. Securitate

3. Moduri de utilizare

4. Exemple

Criptografie si Securitate 2/22 ,

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.

Sisteme fluide

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 diferentaıntre 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 .

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

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

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

Sisteme fluide

OTP (One Time Pad) Sisteme fluide

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

I Acesta este un algoritm determinist care primeste o”samanta” 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”)

l(n) ≥ n

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) ≥ n

2. Pseudoaleatorism: ∀ algoritm PPT D, ∃ o funtie neglijabilanegl a.ı.:

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

unde r ←R {0, 1}l(n), s ←R {0, 1}n

l(n) se numeste factorul de expansiune al lui G

Notatii

I D = Distringuisher

I PPT = Probabilistic Polynomial Time

I x ←R X = x este ales uniform aleator din X

I 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

Notatii

I D = Distringuisher

I PPT = Probabilistic Polynomial Time

I x ←R X = x este ales uniform aleator din X

I 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

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)⊕m

2. Dec : K × C →M

m = Deck(c) = G (k)⊕ c

unde G este un generator de numere pseudoaleatoare cu factorulde expansiune l , k ∈ {0, 1}n, m ∈ {0, 1}l(n)

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.

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.

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.

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 .

Modul sincronizat

Modul nesincronizat

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)

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.

Exemple

I RC4 (Ron’s 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

Exemple

I RC4 (Ron’s 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

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

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

Important de retinut!

I Notiunile de pseudoaleatorism, PRG

I OTP vs. Sisteme fluide

I Transpunerea sistemelor fluide ın practica

riptogra e ˘si Securitate -...

Documents

Transcript of riptogra e ˘si Securitate -...