Criptografia simetrică Securitatea sistemelor şi a...

Securitatea sistemelor şi a aplicaţiilor

Cursul 3. Introducere în criptografie (II)

Marius JoldoşU.T. Cluj-Napoca

SSA cursul 3 - M. Joldos - T.U. Cluj 2

Criptografia simetrică

♦ Ideea generală– EK (M) = C E=cifrare(encrypt); K=cheia folosită; M=mesaj– DK (C) = M D=descifrare(decrypt); C=text cifrat– DK (EK (M)) = M– Procesul de cifrare şi cel de descifrare folosesc aceeaşi cheie– Aceasta nu înseamnă că procesele de cifrare şi descifrare sunt

întotdeauna acelaşi "algoritm". • Cel mai bine este ca ele să fie privite ca inverse unul pentru celălalt

♦ Advantaje– De obicei algoritmii se execută foarte repede

♦ Dezavantaje– Schimbul de chei iniţial şi în continuare– Poate fi folosit pentru semnături digitale (autenticitate), dar numai

cu arbitrare (o a treia parte în care au încredere ambele părţi)Temă: Pentru ca N oameni să comunice în siguranţă fiecare cu

fiecare, de câte chei este nevoie


Modelul cifrului simetric

Intrare text clar Algoritm de criptare

(d.e. DES)

Cheie secretă partajată de emiţător şi receptor

Cheie secretă partajată de emiţător şi receptor

Algoritm de decriptare (inversul algoritmului de

criptare)

Ieşire text clar

Text cifrat transmis


Criptografia cu cheie simetrică: DESDES: Data Encryption Standard♦ Cifru standard în SUA [NIST 1993]♦ Cheie simetrica de 56 (64) biţi, text clar de 64 biţi♦ Cifru produs (substituţie+transpoziţie pe biţi)♦ Cât de sigur este DES?

– Provocarea pentru DES: o frază cifrată cu o cheie de 56 biţi (“Strong cryptography makes the world a safer place”) descifrată (forţă brută) în 4 luni

♦ Cum poate fi făcut mai sigur DES– Prin folosirea a trei chei una după alta (3-DES) pe fiecare

element de date– Prin folosirea înlănţuirii blocurilor cifrate


♦ Permutare iniţială♦ 16 "runde" identice

de aplicare a funcţiei, fiecare folosind alţi 48 biţi ai cheii

♦ Permutare finală♦ Descifrarea foloseşte

cheile de rundă în ordine inversă

Criptografia cu cheie simetrică: DES

Cum operează DES


Înlănţuirea blocurilor cifrate

♦ Cum sa cifrăm un mesaj lung– Dorim integritate

♦ Cifrare:– Ci = E[Mi ⊕ Ci-1]

♦ Descifrare:– Mi = D[Ci] ⊕ Ci-1

♦ Posibilităţi de funcţionare necorespunzătoare:– Pierdere– Reordonare/ integritate


♦ Se împarte textul în blocuri♦ SAU EXCLUSIV a rundei precedente de text

cifrat cu noul text clarBloc 1

IV

DES

Cifru 1

Bloc 2

DES

Bloc 3

DES

Bloc 4

DES

+

Cifru 2 Cifru 3 Cifru 4

+++

Înlănţuirea blocurilor cifrate [Cipher block

chaining (CBC)]

IV=vector de initializare


DES în modul "înlănţuire a blocurilor cifrate" (CBC)♦ CBC. (a) Cifrare. (b) Descifrare.


Performanţele DES

♦ DES se bazează pe confuzie şi difuzie– Nu s-a demonstrat matematic ca sunt sigure

♦ Mai sigur : 3DES (triplu DES) cu Cipher block chaining (CBC)

♦ Produse 3DES pentru securitatea IP *

– ~10 Mb/s în software– ~100 Mb/s în hardware

♦ Ambele părţi trebuie să cunoască cheia secretă şi să o menţină secretă

* sursa: http://www.ietf.org/proceedings/01dec/slides/ipsec-11.pdf


AES (Advanced Encription Standard)

♦ Rijndael: rezultat al unei competiţii deschise♦ Dimensiunea blocului şi lungimea cheii poate

fi 128, 192 sau 256 bit♦ Număr variabil de runde (de obicei 9)♦ Aranjare în pătrate a blocurilor, amestecare

pe octeţi – (cf. csrc.nist.gov/encryption/aes şi

www.esat.kuleuven.ac.be/˜ rijmen/rijndael)


Rundele AES

♦ O rundă obişnuită în AES constă din :1. Substituţie (cu o S-box fixată)2. Deplasarea rândurilor (permutare fixată a

octeţilor) (rândul cel mai de sus neschimbat, al doilea deplasat cu o poziţie, al treilea cu două şi al patrulea cu trei poziţii

3. Amestecarea coloanelor (altă substituţie): patru octeţi dintr-o coloană sunt amestecaţi folosind o înmulţire de matrici

4. Se adaugă runda de cheie (simplu SAU-EX)


AES♦ Generarea subcheii:

– Fiecare subcheie este derivată din cea precedentă şi din original

– Se adaugă o constanta specifica rundei

♦ AES rezistă la mai multe feluri de atacuri

♦ Schimbarea unui singur bit din intrare poate afecta întregul bloc după doar două runde

♦ Sunt disponibile mai multe implementări gratuite


Algoritmul AES


Criptografie. Implementări gratuite

♦ GNU Crypto - GNU Project - Free Software Foundation (FSF)

♦ JaVi v1.0 - Manual

♦ Encrypt And Decrypt In Java : Cryption, PDF Encrypt & Decrypt, Virtual Encrypter/decrypter, TCryptFile ...

♦ Java - AES Implementation

♦ dsCrypt [AES/Rijndael file encryption software with simple, multi-file, drag-and-drop operations]

♦ SimpleCryptographer.zip


Criptografie asimetrică♦ Ideea generală

– Ideea folosirii unei perechi cheie privată/publicăpentru a realiza cifrarea şi descifrarea.

– Cheia privată se păstrează secretă– Cheia publică este oferită tuturor.– Se bazează pe o capcană matematică.

♦ Folosire pentru:– Confidenţialitate:

• Cifrare cu cheia publică• Descifrare cu cheia privată

– Integritate/authentificare: • Cifrare cu cheia privată• Descifrare cu cheia publică

Criptografia asimetrică

♦ Cerinţe1. Să fie uşor computaţional de cifrat /

descifrat un mesaj fiind dată cheia corespunzătoare

2. Să fie nefezabil computaţional de derivat cheia privată din cea publică

3. Să fie nefezabil computaţional de determinat cheia privată dintr-un atac cu text clar ales



Criptografia asimetrică♦ Avantaje

– Permite conversaţii între părţi care nu au mai discutat anterior, şi nu au schimbat chei private

– Oferă suport pentru semnături digitale

♦ Dezavantaje– Algoritmii tind să fie mai lenţi– Sunt subiect pentru atacuri asupra textului cifrat– Atacurile "forţă brută" sunt supuse fezabilităţii rezolvării

problemelor dificile (adică factorizarea numerelor mari)

♦ Utilizări– Semnături digitale (autentificare)– Distribuţia cheilor de sesiune care să fie folosite în algoritmii

simetrici (secretizare)– Secretizarea şi autentificarea sunt furnizate de algoritmi

diferiţi

Diffie-Hellman

♦ Se calculează o cheie comună, partajată– Protocol de schimb de cheie simmetrică

♦ Se bazează pe problema logaritmului discret– Fiind daţi întregii n şi g şi numărul prim p,

să se calculeze k a.î. n = g k mod p– Se cunosc soluţii pentru p mic– Soluţiile nu sunt fezabile computaţional pe

măsură ce p devine mare


Diffie-Hellman. Algoritmul ♦ Constante cunoscute participanţilor

– Numărul prim p, întregii g ≠ 0, 1, p–1♦ Alice

– Alege cheia privată kAlice, – Calculează cheia publică key KAlice =

g kAlice mod p♦ Pentru a comunica cu Bob,

– Alice calculează Kshared = KBob kAlice mod p♦ Pentru a comunica cu Alice,

– Bob calculează Kshared = KAlicekBob mod p


Diffie-Hellman. Exemplu♦ Presupunem că p = 53 şi g = 17♦ Alice alege kAlice = 5

– Atunci KAlice = 175 mod 53 = 40♦ Bob alege kBob = 7

– Atunci KBob = 177 mod 53 = 6♦ Cheia partajată:

– KBobkAlice mod p = 65 mod 53 = 38– KAlicekBob mod p = 407 mod 53 = 38


RSA. Rivest, Shamir, Adelman

♦ Cifru de exponenţiere♦ Se bazează pe dificultatea determinării numărului de

numere relativ prime cu un întreg mare, n♦ Funcţia lui Euler (totient) φ(n)

– Numărul de întregi pozitivi < n şi relativi primi cu n• Relativ prim = nu au factori comuni cu n

♦ Exemplu: φ(10) = 4– 1, 3, 7, 9 sunt relativ primi cu 10

♦ φ(77) ?♦ φ(p) ?

– Când p este prim♦ φ(pq) ?

– Când p şi q sunt numere prime


RSA. Algoritmul

♦ Se aleg două numere prime mari p, q– Fie n = pq; atunci φ(n) = (p–1)(q–1)– Se alege e < n relativ prim cu φ(n).– Se calculează d a.î. ed mod φ(n) = 1

♦ Cheia publică: (e, n); cheia privată: d♦ Cifrarea: c = m e mod n♦ Descifrarea: m = c d mod n


Exemplu. RSA pentru confidenţialitate♦ Luăm p = 7, q = 11, astfel că n = 77 şi φ(n) = 60

♦ Alice alege e = 17, făcând d = 53– 17*53 mod 60 = ?

♦ Bob doreşte să trimită lui Alice mesajul secret HELLO (07 04 11 11 14)– 0717 mod 77 = 28– 0417 mod 77 = 16– 1117 mod 77 = 44– 1117 mod 77 = 44– 1417 mod 77 = 42

♦ Bob trimite textul cifrat [28 16 44 44 42]


Exemplu. RSA pentru confidenţialitate♦ Alice primeşte [28 16 44 44 42]♦ Alice îşi foloseşte cheia privată, d = 53, ca să

descifreze mesajul:– 2853 mod 77 = 07 H– 1653 mod 77 = 04 E– 4453 mod 77 = 11 L– 4453 mod 77 = 11 L– 4253 mod 77 = 14 O

♦ Nimeni altcineva nu putea citi mesajul deoarece doar Alice îşi cunoaşte cheia privată necesară pentru descifrare


Exemplu. RSA pentru integritate + autentificare♦ Se ia p = 7, q = 11, a.î. n = 77 şi φ(n) = 60♦ Alice alege e = 17, ceaa ce face ca d = 53♦ Alice doreşte să trimită lui Bob mesajul HELLO (07 04

11 11 14) astfel încât Bob să ştie că Alice i-a trimis mesajul (fără modificări în tranzit şi autentificat)– 0753 mod 77 = 35– 0453 mod 77 = 09– 1153 mod 77 = 44– 1153 mod 77 = 44– 1453 mod 77 = 49

♦ Alice trimite 35 09 44 44 49


Exemplu. RSA pentru integritate + autentificare♦ Bob primeşte 35 09 44 44 49♦ Bob foloseşte cheia publică a lui Alice, e = 17, n = 77,

pentru a descifra mesajul:– 3517 mod 77 = 07 H– 0917 mod 77 = 04 E– 4417 mod 77 = 11 L– 4417 mod 77 = 11 L– 4917 mod 77 = 14 O

♦ Alice l-a trimis, deoarece doar Alice îşi cunoaşte cheia privată, a.î. nimeni altcineva nu putea cifra mesajul

♦ Dacă blocurile (cifrate) ale mesajului (literele) s-ar fi alterat în tranzit, atunci nu s-ar fi descifrat corect


Exemplu. Confidenţialitate + autentificare♦ Alice doreşte să-i trimită lui Bob mesajul HELLO atât

cifrat cât şi autentificat (verificat d.p.d.v. al integrităţii)– Cheile lui Alice: publică (17, 77); privată: 53– Cheile lui Bob: publică: (37, 77); privată: 13

♦ Alice cifrează HELLO (07 04 11 11 14):– (0753 mod 77)37 mod 77 = 07– (0453 mod 77)37 mod 77 = 37– (1153 mod 77)37 mod 77 = 44– (1153 mod 77)37 mod 77 = 44– (1453 mod 77)37 mod 77 = 14

♦ Alice trimite 07 37 44 44 14


Exemplu. RSA pentru integritate+ autentificare

– Cheile lui Alice: publică (17, 77); privată: 53– Cheile lui Bob: publică: (37, 77); privată: 13

♦ Bob descifrează (07 37 44 44 14):– (0713 mod 77)17 mod 77 = 07 H– (3713 mod 77)17 mod 77 = 04 E– (4413 mod 77)17 mod 77 = 11 L– (4413 mod 77)17 mod 77 = 11 L– (1413 mod 77)17 mod 77 = 14 O



RSA: Criptare, decriptare. Recomandări0. Fiind date (n,e) şi (n,d) calculate cum s-a arătat

1. Pentru a coda m, calculămc = m e mod n

2. Pentru a decoda mesajul recepţionat, c, calculăm

m = c d mod nm = (m e mod n )d mod n

♦Recomandări:−p şi q trebuie să conţină cel puţin 100 de poziţii şi trebuie să fie de acelaşi ordin.−768 biţi pentru chei pe termen scurt, personale−2048 biţi pentru chei valoroase, pe termen lung şi pentru certificate


Securitatea în reţele de calculatoare

♦ Notaţii importante– Ka (cheia lui A)– Kab (cheia comună (partajată) a lui A şi B)– Kapriv (cheia privata a lui A)– Kapub (cheia publică a lui A )– M (mesaj, text în clar)– {M}K (cifrează mesajul cu cheia K) – [M]K (decriptează mesajul cu cheia K)– n (număr mare, produs a două prime mari)– H (valoarea de dispersie)

Servicii de securitate♦ Confidenţialitate

– Doar proprietarul cheii private o ştie, a.î. textul cifrat cu cheia sa publică nu poate fi citit de nimeni altcineva decât ded către proprietarul cheii private

♦ Autentificare– Doar proprietarul cheii private o ştie, a.î. textul cifrat cu

cheia sa privată trebuie să fi fost generat de către proprietar♦ Integritate

– Litrerele cifrate nu pot fi modificate nedectabil fără a şti cheia privată

♦ Ne-Repudiere– Mesajul cifrat cu cheia privată a provenit de la cineva care

ştia cheia

SSA cursul 3 - M. Joldos - T.U. Cluj 31 SSA cursul 3 - M. Joldos - T.U. Cluj 32

Criptografia asimetrică

Semnătură digitală (DS)♦ O verificare pentru nealterarea mesajului.♦ În general, DS este peste un rezumat (digest) nu

peste întregul mesaj– Un rezumat (Digest) este o valoare de lungime fixă

calculată cu o funcţie de dispersie♦ Leagă identitatea la documentCaracteristicile unei funcţii de rezumat (digest) sigure1. Fiind dat M, este uşor de calculat h2. Fiind dat h, este greu de calculat M3. Fiind dat H(M), ar trebui să fie foarte greu de găsit

H(M)=H(M-1)Exemple: MD5 şi SHA


Probleme cu RSA♦ Probarea

– Dacă avem e(m), putem verifica dacă m=m’– Soluţia: random pad

♦ Eficienţa: Concepte cheie– xe mod n = (x * x) mod n * xe-1 mod n– x2(e/2) = deplasarea la stânga a lui x(e/2)

♦ Generarea cheilor este costisitoare– Se aleg numere prime mari– Se găseşte e relativ prim cu (p-1)(q-1)

• În practică, e=65537

♦ Orice x<n este o semnătură validă– De asemenea, fiind date semnăturile pentru m1,

m2; se pot calcula semnăturile pentru (câteva) alte mesaje


Algoritmi pentru funcţii de dispersie

♦ Suma de control Internet ar fi o modalitate slabă de rezumare a mesajelor– E prea uşor de găsit

două mesaje cu aceeaşi sumă de control.

♦ Ideea funcţiilor de dispersie seamănă cu tehnica “sumei de control”

♦ Detectează dacă un document a fost alterat în timpul transmiterii

♦ Este larg folosită funcţia de dispersie MD5. – Calculează un rezumat de

mesaj pe 128 biţi printr-un proces în 4 paşi.

– Fiind dat un şir arbitrar de 128biţi, x, se pare că este dificil de construit mesajul m al carui valoare de dispersie MD5 să fie egala cu x.

♦ Se foloseşte şi SHA-1.– Standard SUA– Rezumat de mesaj pe 160 biţi

Notaţia

♦ X → Y : { Z || W } kX,Y– X trimite luiY mesajul produs prin concatenarea lui

Z cu W cifrat cu cheia kX,Y, partajată de utilizatorii Xşi Y

♦ A → T : { Z } kA || { W } kA,T– A trimite lui T un mesaj care constă din

concatenarea lui Z cifrat cu cheia kA, chiea lui A şi Wcifrat cu cheia kA,T, cheia partajata de A şi T

♦ r1, r2 nonces (numere aleatoare care nu se repetă)


Cheile de sesiune şi schimb (interchange)♦ Alice vrea să-i trimită lui Bob un mesaj, m

– Presupunem cifrare cu cheie publică– Alice generează o cheie criptografică aleatoare ks şi

o foloseşte la cifrarea mesajului m• Se foloseşte numai pentru acest mesaj• Se numeşte cheie de sesiune

– Alice cifrează ks cu cheia publică lui BobkB• kB cifrează toate cheile de sesiune pe care Alice le

foloseşte pentru a comunica cu Bob• Se numeşte cheie de inter-schimb

– Alice trimite { m } ks { ks } kB


Beneficii

♦ Limitează cantitatea de trafic cifrată cu o singură cheie– Este o practica standard, pentru a scădea cantitatea

de trafic pe care o poate obţine un atacator

♦ Previne unele atacuri– De exemplu: Alice va trimite lui Bob un mesaj care

este fie “BUY” sau “SELL”. Eve calculează textele cifrate posibile {“BUY”} kB şi {“SELL”} kB. Eve intercepteză mesajul cifrat, îl compară şi obţine o dată textul în clar


Algoritmi pentru inter-schimbul de chei♦ Scopul: Alice şi Bob să obţină cheia partajată

– Cheia nu poate fi trimisă în clar• Atacatorul poate asculta• Cheia se poate trimite cifrat, sau derivată din datele

schimbate între corespondenţi plus date necunoscute cuiva care ascultă

– Alice, Bob pot avea încredere într-o a treia parte– În toate criptosistemele şi protocoalele cunoscute

public• Singurele info secrete sunt cheile, info anterioară

cunoscută doar de Alice şi Bob necesară pentru derivarea cheilor

• Orice se transmite se presupune că se poate ascultaSSA cursul 3 - M. Joldos - T.U. Cluj 38

Inter-schimbul de chei clasic

♦ Problema începerii: cum încep Alice şiBob– Alice nu-i poate trimite lui Bob cheia în

clar!

♦ Se presupune că există o a treia parte, de încredere, Cathy– Alice şi Cathy partajează cheia secretă kA

– Bob şi Cathy partajează cheia secretă kB

♦ Folosesc aceste cheie pentru a schimba între ei cheia ks


Un protocol simplu


Alice Cathy{ cerere de cheie de sesiune de la Bob } kA

Alice Cathy{ ks } kA || { ks } kB

Alice Bob{ ks } kB

Probleme ale protocolului simplu

♦ Cum ştie Bob că discută cu Alice?– Atac prin reluare: Eve înregistrează mesajul de la

Alice spre Bob şi îl reia mai târziu; Bob poate crede că discută cu Alice, dar nu-i aşa

– Refolosirea cheii de sesiune: Eve reia mesajul de la Alice la Bob, astfel că Bob refoloseşte cheia de sesiune

♦ Protocoalele trebuie să ofere autentificare şi apărare împotriva atacurilor prin reluare


Protocolul Needham-Schroeder


Alice CathyAlice || Bob || r1

Alice Cathy{ Alice || Bob || r1 || ks || { Alice || ks } kB } kA

Alice Bob{ Alice || ks } kB

Alice Bob{ r2 } ks

{ r2 – 1 } ks

1

2

3

5

4

Argumentare: Alice vorbeşte cu Bob

♦ Al doilea mesaj – Cifrat folosind cheia pe care o ştie doar Cathy

• Deci Cathy l-a cifrat

– Răspuns la primul mesaj• Deoarece r1 din el se potriveşte cu r1 din primul mesaj

♦ Al treilea mesaj– Alice ştie că doar Bob îl poate citi

• Deoarece doar Bob poate deriva cheia de sesiune din mesaj

– Orice mesaje cifrate cu acea cheie sunt de la Bob


2

3

Argumentare: Bob vorbeşte cu Alice♦ Al treilea mesaj

– Cifrat cu cheia pe care doar Bob şi Cathy o ştiu• Deci l-a cifrat Cathy

– O numeşte pe Alice, cheia de seciune• Cathy care a furnizat cheia de sesiune spune că Alice

este cealaltă parte

♦ Al patrulea mesaj– Foloseşte cheia de sesiune pentru a determina dacă

este reluare de la Eve• Dacă nu, Alice va răspunde corect în al cincilea mesaj• Dacă da, Eve nu poate descifra r2 şi astfel nu poate

răspunde sau răspunde greşit


3

4

Modificarea Denning-Sacco

♦ Supoziţie: toate cheile sunt secrete♦ Poate atunci Eve să obţină cheia de sesiune?

Cum afectează asta protocolul– În cele ce urmează, Eve cunoaşte ks


Eve Bob{ Alice || ks } kB

Eve Bob{ r2 } ks

{ r2 – 1 } ks

Soluţia

♦ În protocolul anterior, Eve se dă drept Alice♦ Problema: reluarea în pasul al treilea

– Primul pas pe slide anterior

♦ Soluţia: se foloseşte ştampila de timpT pentru detectarea reluarii

♦ Slăbiciune: dacă ceasurile nu sunt sincronizate, se pot fie accepta fie refuza mesaje– Părţile care au fie ceasuri rapide, fie lente sunt

vulnerabile la reluare– Resetarea ceasurilor nu elimină vulnerabilitatea


Protocolul Needham-Schroeder cu modificarea Denning-Sacco


Alice CathyAlice || Bob || r1

Alice Cathy{ Alice || Bob || r1 || ks || { Alice || T || ks } kB } kA

Alice Bob{ Alice || T || ks } kB

Alice Bob{ r2 } ks

Alice Bob{ r2 – 1 } ks

Sumele de control criptografice (CC)♦ Funcţii matematice de generare a unui set de

k biţi dintr-un set de n biţi (unde k ≤ n).– k este mai mic ca n cu excepţia situaţiilor

neobişnuite– CC cu cheie: are nevoie de o cheie criptografică

h = CK(M)

– CC fără cheie: nu are nevoie de o cheie criptografică Funcţie de rezumare de mesaj (Message Digest) sau funcţie de dispersie cu un singur sens (One-way Hash)

h = H(M)

♦ Se pot folosi la autentificarea mesajului– Se numesc şi Message Authentication Code (MAC)


Caracteristici matematice♦ Fiecare bit al funcţiei de rezumre este poteţial

influenţat de fiecare bit din intrarea sa♦ Dacă bit dat din intrarea funcţiei se schimbă,

atunci fiecare bit din ieşire are 50% şanse sa se schimbe

♦ Fiind dat un fişier de intrare şi rezumatul de mesaj corespunzator, ar trebui să fie nefezabil computaţional să se găsească un alt fişier cu aceeaşi valoare de rezumat


Definiţie♦ Funcţie sumă de control criptografică h:

A→B:1. Pentru oricare x ∈ A, h(x) este uşor de calculat

– Uşurează implementarea hardware/software

2. Pentru oricare y ∈ B, este nefezabil computaţional să se găsească x ∈ A a.î. h(x) = y– Proprietatea de singur sens

3. Este nefezabil computaţional să se găsească x, x´∈ A a.î. x ≠ x´ şi h(x) = h(x´)

3’. Forma alternativă (mai tare): Fiind dat oricare x∈ A, este nefezabil computaţional să se găsească un alt x´ ∈ A a.î. h(x) = h(x´).


Coliziuni

♦ Dacă x ≠ x´ şi h(x) = h(x´), x şi x´constituie o coliziune– Principiul cuibului de porumbel: dacă sunt

n containere pentru n+1 obiecte, atunci cel puţin unul va avea 2 obiecte în el.

– Applicaţi: presupunem că n = 5 şi k = 3. Atunci există 32 elemente ale lui A şi 8 elemente ale lui of B, a.î. Cel puţin un element al lui B are cel puţin 4 elemente corespondente ale lui A


Chei

♦ Sumă criptografică cu cheie: necesită o cheie criptografică– DES în modul înlănţuit: se cifrează mesajul,

se folosesc ultimiin biti. Are nevoie de o cheie de cifrare, asa că este o sumă criptografică cu cheie

♦ Sumă criptografică fara cheie: nu necesită o cheie criptografică– MD5 şi SHA-1 sunt cele mai cunoscute;

altele: MD4, HAVAL şi Snefru


Rezumat pentru mesaj (Message Digest)♦ MD2, MD4, MD5 (Ronald Rivest)

– Produce un rezumat de 128 biti; – MD2 este probabil cel mai sigur şi mai greu de aclculat (de aceea

este rar folosit)– MD4 – alternativa rapidă; MD5 este MD4 modificat

♦ SHA, SHA-1 (Secure Hash Algorithm)– Înrudit cu MD4; folosit la semnătura digitală NIST– Produce un rezumat de 160 biti;– SHA-1 poate fi mai bun

♦ SHA-256, SHA-384, SHA-512– 256-, 384-, 512 funcţii de dispersie destinate folosirii împreună cu

Advanced Encryption Standards (AES)

♦ Exemplu:– MD5(There is $1500 in the blue bo) =

f80b3fde8ecbac1b515960b9058de7a1– MD5(There is $1500 in the blue box) =

a4a5471a0e019a4a502134d38fb64729


Hash Message Authentication Code (HMAC)♦ Creează sume criptografice cu cheie din cele fără

cheie♦ h funcţie de sumă criptografică fără cheie care ia

datele în blocuir de b octeţi şi produce blocuri de locteţi. k´ este cheia criptografică de lungime b octeţi– Dacă e prea scurtă se completează cu octeţi de 0; dacă e

prea lunga se cauculează o valoarew de dispersie de lungime b

♦ ipad este 00110110 repetat de b ori♦ opad is 01011100 repetat de b ori♦ HMAC-h(k, m) = h(k´ ⊕ opad || h(k´ ⊕ ipad || m))

– ⊕ sau exclusiv, || concatenare



SHA-1

♦ Mi are 512 biţi, Mi = Wi, 0 … Wi, 15, fiecare Wi, jare 32 biţi

♦ f(0) = (H0, H1, H2, H3 , H4), unde Hi sunt constante predefinite, pe 32 biţi

♦ G are O(80) paşi:– a. Împarte Mi în 16 cuvinte Wi, o ,…, Wi, 15, unde Wi,

0 este cuvântul cel mai din stânga.– b. Expandează Mi de la 16 la 80 cuvinte:

For t := 16 to 79 doWt := Wt−3 Wt−8 Wt −14 Wt −16

– c. (A, B, C, D, E) := (H0, H1, H2, H3 , H4).


SHA-1– d. For t := 0 to 79 do

Tmp := S5(A) + ft(B, C, D) + E +Wt + Kt;E := D; D := C; C := S30(B); B := A; A := Tmp;

– e. H0 = H0 + A, H1 = H1 + B, H2 = H2 + C,H3 = H3 + D, H4 = H4 + E.

♦ După prelucrarea lui Mn , rezumatul mesajului este şirul de 160 biţi reprezentat de cele 5 cuvinte (H0, H1, H2, H3 , H4).

♦ Demonstraţie şi implementare în Javascript http://pajhome.org.uk/crypt/md5


MD5 pentru integritatea mesajelor

♦ MD5 codat– Presupunem ca expeditorul şi destinatarul

partajează cheia secretă k

– Expeditorul: m + MD5(m + k) (+ reprezintă aici concatenare)

– Destinatarul calculează MD5(m + k) şi verifică dacă se potriveşte


MD5. Cum operează

♦ Ideea de bază: actualizarea continuă a valorii de dispersie la blocuri de 512 biţi de mesaj– Valoarea de dispersie iniţială pe 128 biţi– Operaţii pe biţi pentru “comprimare”

♦ Funcţia de compresie: actualizează dispersia pe 128 biţi cu blocul pe 512 biţi– Pas 1: Pe baza biţilor din primul cuvânt se aleg biţii din cel

de al doilea sau din cel de al treilea cuvânt– Pas 2: Se repetă, alegerea bazata pe ultimul cuvânt– Pas 3: sau exclusiv cu biţii din cuvinte– Pas 4: y sau-ex (x sau ~z)

♦ Exemplu


Semnătura digitală = rezumat de mesaj semnat

Bob trimite mesajul semnat digital:

Alice verifică semnătura şi integri-tatea mesajului digital semnat:


MD5 cu semnătură RSA

♦ MD5 cu semnătură RSA– expeditor: m + E(MD5(m), privată)

– destinatar: compară MD5(m) cu D(sumă-de-control, publică)

Suma de control


Semnături digitale cu chei publice

1. A:B M, S2. B decriptează S cu Kapub => H(M); calculează H(M) şi

compară

A generează Kapub şiKapriv (Face disponibilă Kapub)

A calculează rezumatulM => H(M); S= {H(M)}Kapriv

Semnare

Verificare

Semnare

Document semnat


Semnături cu cost redus cu cheie secretă partajată

1. A generează K; o trimite lui B (în siguranţă)2. A calculează h=H(M+K) (aceasta constituie o MAC)3. A:B M,h4. B calculează H(M+K) şi compară

Semnare

Verificare


Certificate♦ Certificat

– Un document semnat de către un principal de încredere

♦ Lanţ de certificate– O ierarhie de încredere

♦ Cerinţe pentru certificate– Format standardizat– Construcţie agreată a lanţului– Problemă: revocarea (rezolvată cumva cu

ajutorul datelor de expirare)


Certificate

Standarde şi autorităţi pentru certificate♦ X.509

– Oferă formatul standard; leagă cheia publică de un subiect pe baza unei semnături de încredere

– Include o perioadă de validitate♦ Încrederea?

– Furnizată de o autoritate de certificare– Verisign …


Standardul X509♦ Câmpuri standard

Câmpul Semnificaţia

Versiunea versiunea lui X.509

Numărul de serie Acest număr plus numărul CA identifică unic certificatul

Algoritmul de semnătură

Emitent Numele X.50O al CA

Perioada de valabilitate Timpii de început şi sfârşit ai perioadei de valabilitate

Numele subiectului Entitatea a cărei cheie se certifică

Cheia publică Cheia publică a subiectului şi ID-ul algoritmului care o foloseşte

ID-ul emitentului Un ID opţional care identifică unic pe emitentul certificatului

ID-ul subiectului Un ID opţional care identifică unic pe subiectul certificatului

Extensii Au fost definite mai multe extensii

Semnătura Semnătura certificatului (semnat cu cheia privată a CA)


Infrastructuri de chei publice (Public-Key Infrastructures – PKI)♦ PKIs sunt o modalitate de structurare a

certificatelor♦ (a) PKI ierarhică. (b) Lanţ de certificate.


Infrastructura de chei publice♦ Oferă funcţionalitatea unei semnături “reale”:

– identificarea semnatarului– originalitatea documentului– contract, înţelegere referitoare la conţinut– Accent pe importanţă

♦ Probleme: semnături falsificate, fax-uri, maşini pentru semnături

♦ Ierarhie de autorităţi de certificare (martori, notari etc)

♦ Semnăturile digitale: probleme asemănătoare♦ Măsuri:

– Ierarhie de autorităţi de certificare (centre de încredere)– Personalizarea cheii private (smart cards, ID fotografic)– Inhibarea publicării sau transferului cheii private prin

• black lists• Penaltăţi• Măsuri legale


Certificate. Certificat cu cheie publica pentru banca lui Bob

1. Tipul certificatului: Cheie publică2. Numele: Banca lui Bob3. Cheia publică: KBpub

4. Autoritatea de certificare: Fred – The Bankers Federation5. Semnătura: {Rezumat (câmp 2 + câmp3)}

KF priv


Protocolul de autentificare cu cheie secretă partajată Needham–Schroeder

Antet Mesaj Observaţii

1. A->S: A, B, NA A solicită lui S să-i furnizeze o cheie pentru comunicarea cu B

2. S->A: {NA , B, KAB,

{KAB, A}KB}KA

S întoarce un mesaj cifrat cu cheia secretă a lui A,şi care conţine o cheie nou generată KAB şi un ‘tichet’ cifrat cu cheia secretă a lui B. Nonce* NAdemonstrează că mesajul a fost trimis ca răspuns la cel precedent. A crede că S a trimis deoarece doar S cunoaşte cheia secreta a lui A.

3. A->B: A trimite ‘tichetul’ lui B.

4. B->A: B descifrează tichetul şi foloseşte noua cheie KABpentru a cripta o altă nonce NB.

{KAB, A}KB

{NB}KAB

*Nonce = identificator unic de mesaj care nu a mai fost folosit anterior în protocol.


Arhitectura sistemului Kerberos

ServerClient

DoOperation

Bază de datede autentificare

Setupsesiune de login

Serviciude acor-dare de

Tichete, T

Centrul de distribuire de chei Kerberos

Setupsesiuneserver

Serviciude auten-tificare A

1. Cerere deTichet TGS

2. TichetTGS

3. Solicitare detichet server

4. Tichet server 5. Solicitare

de serviciu

Solicitare cifrată cu cheia de sesiune

Răspuns cifrat cu cheia de sesiune

Funcţia de servire

Pasul B

Pasul A

Pasul C

C S


Kerberos♦ Kerberos – extensia

MIT a protocoluluiN&S.

– L = durata de viaţă (validitate) a cheii

– N = nonce– T = tichet– kXS = cheia secreta a lui X– kAB = cheia partajată de A

şi B

De citit

♦ Pfleeger, Security in Computing, cap.2



Rezumat

♦ Criptografia simetrică– Modelul cifrului simetric– DES, AES

♦ Criptografia asimetrică– Algoritmi de criptare cu cheie publică – Diffie-

Helman, RSA, SHA-1– MD5– Semnătură digitala– Certificate– Infrastructuri de chei publice (PKI)

♦ Protocolul Needham-Schroeder. Kerberos

Criptografia simetrică Securitatea sistemelor şi a...

Documents

Transcript of Criptografia simetrică Securitatea sistemelor şi a...