riptografie si Securitate

- Prelegerea 10 -Securitate CPA si CCA

Adela Georgescu, Ruxandra F. Olimid

Facultatea de Matematica si InformaticaUniversitatea din Bucuresti

Cuprins

1. Scenarii de atac

2. Securitate CPA

3. Securitate CCA

Criptografie si Securitate 2/38 ,

Scenarii de atac

Reamintim cateva dintre scenariile de atac pe care le-am maintalnit:

Atac cu text criptat: Atacatorul stie doar textul criptat - poatencerca un atac prin forta bruta prin care se parcurg toatecheile pana se gaseste cea corecta;

Atac cu text clar: Atacatorul cunoaste una sau mai multeperechi (text clar, text criptat);

Atac cu text clar ales: Atacatorul poate obtine criptarea unortexte clare alese de el;

Atac cu text criptat ales: Atacatorul are posibilitatea sa obtinadecriptarea unor texte criptate alese de el.

Criptografie si Securitate 3/38 ,

Scenarii de atac

Ultimele 2 scenarii de atac ofera adversarului putere crescuta;

Acesta devine un adversar activ, care primeste abilitatea de aobtine criptarea si / sau decriptarea unor mesaje, respectivtexte criptate alese de el;

In plus, adversarul poate alege mesajele sau textele criptate nmod adaptiv n functie de raspunsurile primite precedent.

Criptografie si Securitate 4/38 ,

Notiuni de securitate

Definim astfel 2 notiuni de securitate:

CPA (Chosen-Plaintext Attack): adversarul poate sa obtinacriptarea unor mesaje alese de el;

CCA (Chosen-Ciphertext Attack): adversarul poate sa obtinacriptarea unor mesaje alese de el si decriptarea unor textecriptate alese de el.

Criptografie si Securitate 5/38 ,

Securitate CPA

Capabilitatile adversarului: el poate interactiona cu un oracolde criptare, fiind un adversar activ care poate rula atacuri ntimp polinomial;

Adversarul poate transmite catre oracol orice mesaj m siprimeste napoi textul criptat corespunzator;

Daca sistemul de criptare este nedeterminist, atunci oracolulfoloseste de fiecare data o valoare aleatoare noua si neutilizataanterior.

Criptografie si Securitate 6/38 ,

Securitate CPA

Consideram ca securitatea este impactata daca adversarulpoate sa distinga ntre criptarile a doua mesaje aleatoare;

Vom defini securitatea CPA pe baza unui experiment deindistinctibilitate Priv cpa

A,pi(n) unde pi = (Enc ,Dec) este schema

de criptare iar n este parametrul de securitate al schemei pi;

Personajele participante: adversarul A care ncearca sasparga schema si un provocator (challenger);

Criptografie si Securitate 7/38 ,

Experimentul Priv cpaA,pi(n)

Pe toata durata experimentului, A are acces la oracolul decriptare Enck()!

Criptografie si Securitate 12/38 ,

Experimentul Priv cpaA,pi(n)

Output-ul experimentului este 1 daca b = b si 0 altfel. DacaPriv cpa

A,pi(n) = 1, spunem ca A a efectuat experimentul cu

succes.

Criptografie si Securitate 13/38 ,

Experimentul Priv cpaA,pi(n)

Definitie

O schema de criptare pi = (Enc ,Dec) este CPA-sigura daca pentruorice adversar PPT A exista o functie neglijabila negl asa ncat

Pr[Priv cpaA,pi

(n) = 1] 12 + negl(n).

Un adversar nu poate determina care text clar a fost criptatcu o probabilitate semnificativ mai mare decat daca ar fi ghicit(n sens aleator, dat cu banul), chiar daca are acces la oracolulde criptare.

Criptografie si Securitate 14/38 ,

Securitate CPA

Intrebare: Un sistem de criptare CPA-sigur este ntotdeaunasemantic sigur?

Raspuns: DA! Experimentul Priv eavA,pi

(n) este Priv cpaA,pi

(n) n careA nu foloseste oracolul de criptare.

Intrebare: Un sistem de criptare determinist poate fiCPA-sigur?

Raspuns: NU! Adversarul cere oracolului criptarea mesajuluim0. Daca textul criptat este egal cu c , atunci b

= 0, altfelb = 1. In concluzie, A castiga cu probabilitate 1.

Criptografie si Securitate 15/38 ,

Securitate CPA - Criptare multipla

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

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

Definim ce nseamna o schema sigura chiar si n acesteconditii.

Criptografie si Securitate 16/38 ,

Experimentul Priv cpaA,pi(n)

Pe toata durata experimentului, A are acces la oracolul decriptare Enck()!

Criptografie si Securitate 20/38 ,

Experimentul Priv cpaA,pi(n)

Output-ul experimentului este 1 daca b = b si 0 altfel;

Definitia de securitate este aceeasi, doar ca se refera laexperimentul de mai sus.

Securitatea pentru criptare simpla implica securitate pentrucriptare multipla!

Criptografie si Securitate 21/38 ,

Securitate CCA

Capabilitatile adversarului: el poate interactiona cu un oracolde criptare si cu un oracol de decriptare, fiind un adversaractiv care poate rula atacuri n timp polinomial;

Adversarul poate transmite catre oracolul de criptare oricemesaj m si primeste napoi textul criptat corespunzator saupoate transmite catre oracolul de decriptare anumite mesaje csi primeste napoi mesajul clar corespunzator;

Daca sistemul de criptare este nedeterminist, atunci oracolulde criptare foloseste de fiecare data o valoare aleatoare nouasi neutilizata anterior.

Criptografie si Securitate 22/38 ,

Securitate CCA

Consideram ca securitatea este impactata daca adversarulpoate sa distinga ntre criptarile a doua mesaje aleatoare;

Vom defini securitatea CCA pe baza unui experiment deindistinctibilitate Priv cca

A,pi(n) unde pi = (Enc ,Dec) este schema

de criptare iar n este parametrul de securitate al schemei pi;

Personajele participante: adversarul A care ncearca sasparga schema si un provocator (challenger);

Criptografie si Securitate 23/38 ,

Experimentul Priv ccaA,pi(n)

Pe toata durata experimentului, A are acces la oracolul decriptare Enck() si la oracolul de decriptare Deck() curestrictia ca nu poate decripta c!

Criptografie si Securitate 28/38 ,

Experimentul Priv ccaA,pi(n)

Output-ul experimentului este 1 daca b = b si 0 altfel. DacaPriv cca

A,pi(n) = 1, spunem ca A a efectuat experimentul cu

succes.

Criptografie si Securitate 29/38 ,

Experimentul Priv ccaA,pi(n)

Definitie

O schema de criptare pi = (Enc ,Dec) este CCA-sigura daca pentruorice adversar PPT A exista o functie neglijabila negl asa ncat

Pr[Priv ccaA,pi

(n) = 1] 12 + negl(n).

Un adversar nu poate determina care text clar a fost criptatcu o probabilitate semnificativ mai mare decat daca ar fi ghicit(n sens aleator, dat cu banul), chiar daca are acces laoracolele de criptare si decriptare.

Criptografie si Securitate 30/38 ,

Securitate CCA

Intrebare: Un sistem de criptare CCA-sigur este ntotdeaunaCPA-sigur?

Raspuns: DA! Experimentul Priv cpaA,pi

(n) este Priv ccaA,pi

(n) n careA nu foloseste oracolul de decriptare.

Intrebare: Un sistem de criptare determinist poate fiCCA-sigur?

Raspuns: NU! Sistemul nu este CPA-sigur, deci nu poate fiCCA-sigur.

Criptografie si Securitate 31/38 ,

Securitate CCA - Criptare multipla

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

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

Definim ce nseamna o schema sigura chiar si n acesteconditii.

Criptografie si Securitate 32/38 ,

Experimentul Priv ccaA,pi(n)

Pe toata durata experimentului, A are acces la oracolul decriptare Enck() si la oracolul decriptare Deck() cu restrictiaca nu poate decripta c1, . . . , ct !

Criptografie si Securitate 36/38 ,

Experimentul Priv ccaA,pi(n)

Output-ul experimentului este 1 daca b = b si 0 altfel;

Definitia de securitate este aceeasi, doar ca se refera laexperimentul de mai sus.

Criptografie si Securitate 37/38 ,

Important de retinut!

Securitate CCA securitate CPA securitate semantica

Schemele deterministe nu sunt semantic / CPA / CCA sigure

Criptografie si Securitate 38/38 ,