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

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

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

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.

Criptografie si Securitate 3/22 ,

Pseudoaleatorismul

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

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

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

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 .

Criptografie si Securitate 4/22 ,

Pseudoaleatorismul

In analogie cu ce stim deja:

pseudoaleatorismul este o relaxare a aleatorismului perfect

asa cum

securitatea computationala este o relaxare a securitatiiperfecte

Criptografie si Securitate 5/22 ,

Sisteme fluide

Revenind la criptarea fluida...

... aceasta presupune 2 faze:

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

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

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

Criptografie si Securitate 6/22 ,

Sisteme fluide

OTP (One Time Pad) Sisteme fluide

Criptografie si Securitate 7/22 ,

PRG

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

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

Notam |s| = n, |PRG (s)| = l(n)

PRG prezinta interes daca:

l(n) n

(altfel NU genereaza aleatorism)

Criptografie si Securitate 8/22 ,

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

Criptografie si Securitate 9/22 ,

Notatii

D = Distringuisher

PPT = Probabilistic Polynomial Time

x R X = x este ales uniform aleator din X

negl(n) = o functie neglijabila n (parametrul de securitate) n

In plus:

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

Criptografie si Securitate 10/22 ,

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)

Criptografie si Securitate 11/22 ,

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.

Criptografie si Securitate 12/22 ,

Demonstratie intuitiva

OTP este perfect sigur;

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

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

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

Criptografie si Securitate 13/22 ,

Securitate - interceptare multipla

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

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

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

Criptografie si Securitate 14/22 ,

Moduri de utilizare

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

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 .

Criptografie si Securitate 15/22 ,

Modul sincronizat

Criptografie si Securitate 16/22 ,

Modul nesincronizat

Criptografie si Securitate 17/22 ,

Moduri de utilizare

Modul sincronizat

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

necesita pastrarea starii

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

se preteaza unei singuresesiuni de comunicatii

Modul nesincronizat

mesajele sunt criptate nmod independent

NU necesita pastrarea starii

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

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

Criptografie si Securitate 18/22 ,

Proprietati necesare ale PRG n modul nesincronizat

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

s = seed

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.

Criptografie si Securitate 19/22 ,

Exemple

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

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

WPA2 - IEEE 802.11i

Criptografie si Securitate 20/22 ,

Exemple

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

geografice utilizat n retelele de telefonie mobila GSM initial secret !

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

de biti versiunea curenta (SEAL 3.0) este patentata IBM

Criptografie si Securitate 21/22 ,

Important de retinut!

Notiunile de pseudoaleatorism, PRG

OTP vs. Sisteme fluide

Transpunerea sistemelor fluide n practica

Criptografie si Securitate 22/22 ,

SecuritateModuri de utilizare