riptografie si Securitate

- Prelegerea 11 -Coduri de autentificare a mesajelor

Adela Georgescu, Ruxandra F. Olimid

Facultatea de Matematica si InformaticaUniversitatea din Bucuresti

Cuprins

1. Necesitatea autentificarii

2. Definitie MAC

3. Securitate MAC

4. CBC-MAC

Criptografie si Securitate 2/42 ,

Comunicare sigura si integritatea mesajelor

Un scop de baza al criptografiei este sa asigure comunicareasigura de-a lungul unui canal public de comunicare;

Am vazut cum putem obtine aceasta cu ajutorul schemelor decriptare;

Insa, nu ne intereseaza doar ca adversarul sa nu aiba acces lamesajele trimise, ci...

Vrem sa garantam integritatea mesajelor (sau autentificareamesajelor)

Aceasta nseamna ca mesajul primit de Bob este exact mesajultrimis de Alice.

Criptografie si Securitate 3/42 ,

Comunicare sigura si integritatea mesajelor

Iata un exemplu:

Sa consideram cazul n care un mare lant de supermarket-uritrimite o comanda pe email catre un furnizor pentru aachizitiona 10.000 bax-uri de apa minerala;

Odata primita comanda, furnizorul trebuie sa verificeurmatoarele:

1. Comanda este autentica? A fost trimisa cu adevarat de unsupermarket sau de catre un adversar care a furat contul deemail al clientului respectiv ?

2. Daca s-a convins de autenticitatea comenzii, trebuie verificatdaca detaliile ei sunt cele originale sau au fost modificate peparcurs de un adversar.

Criptografie si Securitate 4/42 ,

Comunicare sigura si integritatea mesajelor

In exemplul precedent, problema este doar de integritate amesajelor, si nu de confidentialitate (comanda nu e secreta);

In general nu ne putem baza pe ncredere n ceea ce privesteintegritatea mesajelor transmise, indiferent ca ele sunt:

comenzi efectuate online

operatiuni bancare online

email, SMS

Vom vedea cum putem folosi tehnici criptografice pentru apreveni modificarea nedectata a mesajelor transmise.

Criptografie si Securitate 5/42 ,

Criptare vs. autentificarea mesajelor

Criptarea, n general, NU ofera integritatea mesajelor!

Daca un mesaj este transmis criptat de-a lungul unui canal decomunicare, nu nseamna ca un adversar nu poatemodifica/altera mesajul asa ncat modificarea sa aiba sens ntextul clar;

Verificam, n continuare, ca nici o schema de criptare studiatanu ofera integritatea mesajelor;

Criptografie si Securitate 6/42 ,

Criptare vs. autentificarea mesajelor

Criptarea folosind sisteme fluide

Enck(m) = G (k)m, unde G este un PRG;

Daca modificam un singur bit din textul criptat c , modificarease va reflecta imediat n acelasi bit din textul clar;

Consecintele pot fi grave: de pilda, sa consideram transferulunei sume de bani n dolari criptate, reprezentata n binar;

Modificarea unui bit poate schimba suma foarte mult (al 11lsb schimba suma cu mai mult de 1000$);

Acelasi atac se poate aplica si la OTP.

Criptografie si Securitate 7/42 ,

Criptare vs. autentificarea mesajelor Criptarea folosind sisteme bloc

Intrebare: Atacul de mai sus se poate aplica si pentru sistemelebloc cu modurile de operare studiate?

(a) ECB (b) CBC

(c) OFB (d) CTR

Criptografie si Securitate 8/42 ,

Criptare vs. autentificarea mesajelor

Raspuns: Atacul se aplica identic pentru modurile OFB siCTR;

Pentru modul ECB, modificarea unui bit din al i-lea bloccriptat afecteaza numai al i-lea bloc clar, dar este foarte greude prezis efectul exact;

Mai mult, ordinea blocurilor la ECB poate fi schimbata;

Pentru modul CBC, schimbarea bitului j din IV va schimbabitul j din primul bloc;

Toate celelalte blocuri de text clar raman neschimbate(mi = F

1k (ci ) ci1 iar blocurile ci si ci1 nu au fost

modificate).

Criptografie si Securitate 9/42 ,

Coduri de autentificare a mesajelor - MAC

Asa cum am vazut, criptarea nu rezolva problemaautentificarii mesajelor;

Vom folosi un mecanism diferit, numit cod de autentificare amesajelor - MAC (Message Authentication Code);

Scopul lor este de a mpiedica un adversar sa modifice unmesaj trimis fara ca partile care comunica sa nu detectezemodificarea;

Vom lucra n continuare n contextul criptografiei cu cheiesecreta unde partile trebuie sa prestabileasca de comun acordo cheie secreta.

Criptografie si Securitate 10/42 ,

MAC - Definitie

Alice si Bob stabliesc o cheie secreta k pe care o partajeaza;

Cand Alice vrea sa i trimita un mesaj m lui Bob, calculeazamai ntai un tag t pe baza mesajului m si a cheii k si trimiteperechea (m, t);

Criptografie si Securitate 11/42 ,

MAC - Definitie

Tag-ul este calculat folosind un algoritm de generare atag-urilor numit Mac;

La primirea perechii (m, t) Bob verifica daca tag-ul este valid(n raport cu cheia k) folosind un algoritm de verificare Vrfy;

In continuare prezentam definitia formala a unui cod deautentificare a mesajelor.

Criptografie si Securitate 12/42 ,

MAC - Definitie

Definitie

Un cod de autentificare a mesajelor (MAC) definit peste(K,M, T ) este format dintr-o pereche de algoritmi polinomiali(Mac,Vrfy) unde:

1. Mac : K M T este algoritmul de generare a tag-urilort Mack(m);

2. Vrfy : K M T {0, 1}este algoritmul de verificare ce ntoarce un bitb = Vrfyk(m, t) cu semnificatia ca:

b = 1 nseamna valid b = 0 nseamna invalid

a. : m M, k K Vrfyk(m,Mack(m)) = 1.

Criptografie si Securitate 13/42 ,

Securitate MAC - discutie

Intuitie: nici un adversar polinomial nu ar trebui sa poatagenera un tag valid pentru nici un mesaj nou care nu a fostdeja trimis (si autentificat) de partile care comunica;

Trebuie sa definim puterea adversarului si ce nseamnaspargerea sau un atac asupra securitatii;

Adversarul lucreaza n timp polinomial si are acces la mesajeletrimise ntre parti mpreuna cu tag-urile aferente.

Adversarul poate influenta continutul mesajelor (direct sauindirect), fiind deci un adversar activ.

Criptografie si Securitate 14/42 ,

Securitate MAC - formalizare

Formal, i dam adversarului acces la un oracol Mack();

Adversarul poate trimite orice mesaj m dorit catre oracol siprimeste napoi un tag corespunzator t Mack(m);

Consideram ca securitatea este impactata daca adversarul estecapabil sa produca un mesaj m mpreuna cu un tag t asancat:

1. t este un tag valid pentru mesajul m: Vrfyk(m, t) = 1;

2. Adversarul nu a solicitat anterior (de la oracol) un tag pentrumesajul m.

Criptografie si Securitate 15/42 ,

Securitate MAC - formalizare

Despre un MAC care satisface nivelul de securitate de mai susspunem ca nu poate fi falsificat printr-un atac cu mesaj ales;

Aceasta nseamna ca un adversar nu este capabil sa falsificeun tag valid pentru nici un mesaj ...

... desi poate obtine tag-uri pentru orice mesaj ales de el,chiar adaptiv n timpul atacului.

Pentru a da definitia formala, definim mai ntai un experimentpentru un MAC pi = (Mac,Vrfy), n care consideram unadversar A si parametrul de securitate n;

Criptografie si Securitate 16/42 ,

Experimentul MacforgeA,pi (n)

Output-ul experimentului este 1 daca si numai daca:(1) Vrfyk(m, t) = 1 si (2) m / {m1, ...,mq};

Daca MacforgeA,pi

(n) = 1, spunem ca A a efectuat experimentulcu succes.

Criptografie si Securitate 22/42 ,

Securitate MAC

Definitie

Un cod de autentificare al mesajelor pi = (Mac,Vrfy) este sigur (nupoate fi falsificat printr-un atac cu mesaj ales) daca pentru oriceadversar polinomial A exista o functie neglijabila negl asa ncat

Pr[MacforgeA,pi

(n) = 1] negl(n).

Criptografie si Securitate 23/42 ,

Atacuri prin replicare

Intrebare: De ce este necesara a doua conditie de lasecuritatea MAC (un adversar nu poate ntoarce un mesajpentru care anterior a cerut un tag)?

Raspuns: Pentru a evita atacurile prin replicare n care unadversar copiaza un mesaj mpreuna cu tag-ul aferent trimisede partile comunicante;

Intrebare: Definitia MAC ofera protectie la atacurile prinreplicare efectuate chiar de partile comunicante?

Raspuns: NU! MAC-urile nu ofera nici un fel de protectie laatacurile prin replicare efectuate de partile comunicante.

Criptografie si Securitate 24/42 ,

Atacuri prin replicare

De exemplu: Alice trimite catre banca sa un ordin de transfera 1.000$ din contul ei n contul lui Bob;

Pentru aceasta, Alice calculeaza un tag MAC si l atasazamesajului asa ncat banca stie ca mesajul este autentic;

Daca MAC-ul este sigur, Bob nu va putea intercepta mesajulsi modifica suma la 10.000$;

Dar Bob poate intercepta mesajul si l poate replica de zeceori catre banca;

Daca banca l accepta, Bob va avea n cont 10.000$.

Criptografie si Securitate 25/42 ,

Atacuri prin replicare

Un MAC nu protejeaza mpotriva unui atac prin replicarepentru ca definitia nu ncorporeaza nici o notiune de stare nalgortimul de verificare;

Mai degraba, protectia mpotriva replicarii trebuie facuta lanivel nalt de catre aplicatiile care folosesc MAC-uri;

Doua tehnici comune de protejare mpotriva atacurilor prinreplicare folosesc secvente de numere sau stampila de timp;

Pentru secvente de numere, fiecare mesaj m are asignat unnumar i iar tag-ul este calculat pe mesajul i ||m;

Intrebare: De ce aceasta tehnica protejeaza mpotrivaatacurilor prin replicare?

Criptografie si Securitate 26/42 ,

Atacuri prin replicare

Raspuns: Pentru ca orice noua replicare a lui m trebuie saconstruiasca un tag pentru mesajul i ||m, unde i nu a maifost folosit niciodata;

Dezavantajul este ca trebuie stocata o lista cu numerelefolosite anterior

O alternativa ar fi folosirea stampilelor de timp: la receptiamesajului, destinatarul verifica daca stampila de timp inclusase afla ntr-un interval de timp acceptabil;

Aceasta presupune ca partile sa aiba ceasuri sincronizate;

In plus, daca un atac prin replicare este suficient de rapid, else poate desfasura cu succes chiar si n aceste conditii.

Criptografie si Securitate 27/42 ,

Constructia MAC-urilor sigure

Functiile pseudoaleatoare (PRF) sunt un instrument bunpentru a construi MAC-uri sigure;

Constructie

Fie F : {0, 1}n {0, 1}n {0, 1}n o PRF. Definim un MAC nfelul urmator:

Mac : pentru o cheie k {0, 1}n si un mesaj m {0, 1}n,calculeaza tag-ul t = Fk(m) (daca |m| 6= |k | nu ntoarcenimic);

Vrfy : pentru o cheie k {0, 1}n, un mesaj m {0, 1}n si untag t {0, 1}n, ntoarce 1 daca si numai daca t = Fk(m)(daca |m| 6= |k |, ntoarce 0).

Criptografie si Securitate 28/42 ,

Constructia MAC-urilor sigure

Teorema

Daca F este o functie aleatoare, constructia de mai sus reprezintaun cod de autentificare a mesajelor sigur (nu poate fi falsificat prinatacuri cu mesaj ales).

Criptografie si Securitate 29/42 ,

Demonstratie intuitiva

Daca un tag t este obtinut prin aplicarea unei functiipseudoaleatoare pe un mesaj m, atunci falsificarea unui tagaferent unui mesaj ne-autentificat anterior presupune caadversarul sa ghiceasca valoarea functiei ntr-un punct nou(i.e. mesaj);

Probabilitatea de a ghici valoarea unei functii aleatoare ntr-unpunct nou este 2n (unde n este lungimea iesirii functiei);

Prin urmare, probabilitatea de a ghici valoarea ntr-un punctnou pentru o functie pseudoaleatoare nu poate fi decatneglijabil mai mare.

Criptografie si Securitate 30/42 ,

MAC-uri pentru mesaje de lungime variabila

Constructia prezentata anterior functioneaza doar pe mesajede lungime fixa;

Insa n practica avem nevoie de mesaje de lungime variabila;

Aratam cum putem obtine un MAC de lungime variabilapornind de la un MAC de lungime fixa;

Fie (pi = (Mac,Vrfy)) un MAC sigur de lungime fixa pentrumesaje de lungime n;

Pentru a construi un MAC de lungime variabila, putem spargemesajul m n blocuri m1, ...,md si autentificam blocurilefolosind pi;

Iata cateva modalitati de a face aceasta:

Criptografie si Securitate 31/42 ,

MAC-uri pentru mesaje de lungime variabila

1. XOR pe toate blocurile cu autentificarea rezultatului :t = Mack(imi )

Intrebare: Este sigura aceasta metoda?

Raspuns: NU! Un adversar poate modifica mesajul original ma.. XOR-ul blocurilor nu se schimba, el obtinand un tag validpentru un mesaj nou;

Criptografie si Securitate 32/42 ,

MAC-uri pentru mesaje de lungime variabila

2. Autentificare separata pentru fiecare bloc :(t1, ..., td), unde ti = Mac

k(mi )

Intrebare: Este sigura aceasta metoda?

Raspuns: NU! Un adversar poate schimba ordinea blocurilor nmesajul m, el obtinand un tag valid pentru un mesaj nou;

Criptografie si Securitate 33/42 ,

MAC-uri pentru mesaje de lungime variabila

3. Autentificare separata pentru fiecare bloc folosind o secventa denumere:

(t1, ..., td), unde ti = Mack(i ||mi )

Intrebare: Este sigura aceasta metoda?

Raspuns: NU! Un adversar poate scoate blocuri de la sfarsitulmesajului: (t1, ..., td1) este un tag valid pentru mesajul(m1, ...,md1);Mai mult, daca (t1, ..., td) si (t

1, ..., t

d) sunt tag-uri valide

pentru mesajele m = m1, ...,md si m = m1, ...,m

d , atunci

(t1, t2, t3, t

4, ...) este un tag valid pentru mesajul

m1,m2,m3,m

4, ....

Criptografie si Securitate 34/42 ,

MAC-uri pentru mesaje de lungime variabila

O solutie pentru atacurile anterioare o reprezinta adaugareade informatie suplimentara n fiecare bloc, n afara numaruluide secventa:

un identificator aleator de mesaj - previne combinareablocurilor din mesaje diferite

lungimea mesajului - previne modificarea lungimii mesajelor

Criptografie si Securitate 35/42 ,

CBC-MAC

Solutia este ineficienta si greu de folosit n practica;

Insa, am vazut ca putem construi MAC-uri sigure (chiarpentru mesaje de lungime variabila) pe baza functiilorpseudoaleatoare (intrare de lungime fixa);

Ceea ce nseamna ca putem construi MAC-uri sigure pornindde la cifruri bloc;

Dar, cu constructia de mai sus, rezultatul e foarte ineficient:pentru un tag aferent unui mesaj de lungime l n, trebuie saaplicam sistemul bloc de 4l ori iar tag-ul rezultat are (4l + 1)nbiti;

Criptografie si Securitate 36/42 ,

CBC-MAC

O solutie mult mai eficienta este sa folosim CBC-MAC;

CBC-MAC este o constructie similara cu modul CBC folositpentru criptare;

Folosind CBC-MAC, pentru un tag aferent unui mesaj delungime l n, se aplica sistemul bloc doar de l ori.

Criptografie si Securitate 37/42 ,

CBC-MAC

Definitie

Fie F o functie pseudoaleatoare. Un CBC-MAC este format dintr-opereche de algoritmi polinomiali probabilisti (Mac,Vrfy):

1. Mac: pentru o cheie k {0, 1}n si un mesaj m de lungime l:

Sparge m in m = m1, ...,ml , |mi | = n si noteaza t0 = 0n;

Pentru i = 1, ..., l , calculeaza ti = Fk(ti1 mi );

Intoarce tl ca tag-ul rezultat;

2. Vrfy : pentru o cheie k {0, 1}n, un mesaj m de lungime l, siun tag t de lungime n:ntoarce 1 daca si numai daca t = Mack(m).

Ramane valabila conditia de corectitudine:m M, k K, Vrfyk(m,Mack(m)) = 1.

Criptografie si Securitate 38/42 ,

Securitatea CBC-MAC

Teorema

Daca F este o functie pseudoaleatoare, constructia de mai susreprezinta un cod de autentificare a mesajelor sigur (nu poate fifalsificat prin atacuri cu mesaj ales) pentru mesaje de lungime l n.

Constructia prezentata este sigura numai pentru autentificareamesajelor de lungime fixa;

Avantajul acestei constructii fata de cea anterioara este ca eapoate autentifica mesaje de lungime mult mai mare;

Criptografie si Securitate 39/42 ,

CBC-MAC vc. Criptare in modul CBC

Criptare n mod CBC

IV este aleator pentru aobtine securitate;

toate blocurile ci constituiemesajul criptat.

CBC-MAC

IV = 0n este fixat pentru aobtine securitate;

doar iesirea ultimului blocconstituie tag-ul(ntoarcerea tuturorblocurilor intermediare ducela pierderea securitatii)

Criptografie si Securitate 40/42 ,

CBC-MAC pentru mesaje de lungime variabila

Putem modifica constructia anterioara n diverse moduri ca saobtinem o versiune de CBC-MAC pentru mesaje de lungimevariabila. Iata trei dintre ele care pot fi demonstrate ca fiind sigure:

1. Calculeaza kl = Fk(l); Apoi foloseste CBC-MAC cu cheia kl ;aceasta asigura faptul ca sunt folosite chei diferite pentru aautentifica mesaje de lungimi diferite;

2. Se adauga un bloc de mesaj (n fata primului bloc) carecontine |m| si se aplica CBC-MAC pe mesajul rezultat.

3. Se poate modifica schema asa ncat sa se aleaga doua cheik1, k2 {0, 1}

n; se autentifica mesajul m cu CBC-MACfolosind cheia k1 si se obtine t iar tag-ul rezultat va fit = Fk2(t).

Criptografie si Securitate 41/42 ,

Important de retinut!

MAC-urile ofera doua proprietati importante de securitate:integritatea mesajelor si autentificarea mesajelor;

Pentru constructia lor se folosesc functii pseudoaleatoare (npractica, sisteme bloc) fiind destul de rapide.

Criptografie si Securitate 42/42 ,