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
SSA cursul 3 - M. Joldos - T.U. Cluj 3
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
SSA cursul 3 - M. Joldos - T.U. Cluj 4
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
SSA cursul 3 - M. Joldos - T.U. Cluj 5
♦ 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
SSA cursul 3 - M. Joldos - T.U. Cluj 6
Î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
SSA cursul 3 - M. Joldos - T.U. Cluj 7
♦ 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
SSA cursul 3 - M. Joldos - T.U. Cluj 8
DES în modul "înlănţuire a blocurilor cifrate" (CBC)♦ CBC. (a) Cifrare. (b) Descifrare.
SSA cursul 3 - M. Joldos - T.U. Cluj 9
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
SSA cursul 3 - M. Joldos - T.U. Cluj 10
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)
SSA cursul 3 - M. Joldos - T.U. Cluj 11
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)
SSA cursul 3 - M. Joldos - T.U. Cluj 12
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
SSA cursul 3 - M. Joldos - T.U. Cluj 13
Algoritmul AES
SSA cursul 3 - M. Joldos - T.U. Cluj 14
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
SSA cursul 3 - M. Joldos - T.U. Cluj 15
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
SSA cursul 3 - M. Joldos - T.U. Cluj 16
SSA cursul 3 - M. Joldos - T.U. Cluj 17
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
SSA cursul 3 - M. Joldos - T.U. Cluj 18
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
SSA cursul 3 - M. Joldos - T.U. Cluj 19
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
SSA cursul 3 - M. Joldos - T.U. Cluj 20
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
SSA cursul 3 - M. Joldos - T.U. Cluj 21
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
SSA cursul 3 - M. Joldos - T.U. Cluj 22
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]
SSA cursul 3 - M. Joldos - T.U. Cluj 23
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
SSA cursul 3 - M. Joldos - T.U. Cluj 24
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
SSA cursul 3 - M. Joldos - T.U. Cluj 25
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
SSA cursul 3 - M. Joldos - T.U. Cluj 26
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
SSA cursul 3 - M. Joldos - T.U. Cluj 27
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
SSA cursul 3 - M. Joldos - T.U. Cluj 28
SSA cursul 3 - M. Joldos - T.U. Cluj 29
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
SSA cursul 3 - M. Joldos - T.U. Cluj 30
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
SSA cursul 3 - M. Joldos - T.U. Cluj 33
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
SSA cursul 3 - M. Joldos - T.U. Cluj 34
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ă)
SSA cursul 3 - M. Joldos - T.U. Cluj 35
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
SSA cursul 3 - M. Joldos - T.U. Cluj 36
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
SSA cursul 3 - M. Joldos - T.U. Cluj 37
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
SSA cursul 3 - M. Joldos - T.U. Cluj 39
Un protocol simplu
SSA cursul 3 - M. Joldos - T.U. Cluj 40
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
SSA cursul 3 - M. Joldos - T.U. Cluj 41
Protocolul Needham-Schroeder
SSA cursul 3 - M. Joldos - T.U. Cluj 42
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
SSA cursul 3 - M. Joldos - T.U. Cluj 43
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
SSA cursul 3 - M. Joldos - T.U. Cluj 44
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
SSA cursul 3 - M. Joldos - T.U. Cluj 45
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
SSA cursul 3 - M. Joldos - T.U. Cluj 46
Protocolul Needham-Schroeder cu modificarea Denning-Sacco
SSA cursul 3 - M. Joldos - T.U. Cluj 47
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)
SSA cursul 3 - M. Joldos - T.U. Cluj 48
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
SSA cursul 3 - M. Joldos - T.U. Cluj 49
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´).
SSA cursul 3 - M. Joldos - T.U. Cluj 50
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
SSA cursul 3 - M. Joldos - T.U. Cluj 51
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
SSA cursul 3 - M. Joldos - T.U. Cluj 52
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
SSA cursul 3 - M. Joldos - T.U. Cluj 53
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
SSA cursul 3 - M. Joldos - T.U. Cluj 54
SSA cursul 3 - M. Joldos - T.U. Cluj 55
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).
SSA cursul 3 - M. Joldos - T.U. Cluj 56
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
SSA cursul 3 - M. Joldos - T.U. Cluj 57
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
SSA cursul 3 - M. Joldos - T.U. Cluj 58
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
SSA cursul 3 - M. Joldos - T.U. Cluj 59
Semnătura digitală = rezumat de mesaj semnat
Bob trimite mesajul semnat digital:
Alice verifică semnătura şi integri-tatea mesajului digital semnat:
SSA cursul 3 - M. Joldos - T.U. Cluj 60
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
SSA cursul 3 - M. Joldos - T.U. Cluj 61
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
SSA cursul 3 - M. Joldos - T.U. Cluj 62
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
SSA cursul 3 - M. Joldos - T.U. Cluj 63
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)
SSA cursul 3 - M. Joldos - T.U. Cluj 64
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 …
SSA cursul 3 - M. Joldos - T.U. Cluj 65
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)
SSA cursul 3 - M. Joldos - T.U. Cluj 66
Infrastructuri de chei publice (Public-Key Infrastructures – PKI)♦ PKIs sunt o modalitate de structurare a
certificatelor♦ (a) PKI ierarhică. (b) Lanţ de certificate.
SSA cursul 3 - M. Joldos - T.U. Cluj 67
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
SSA cursul 3 - M. Joldos - T.U. Cluj 68
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
SSA cursul 3 - M. Joldos - T.U. Cluj 69
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.
SSA cursul 3 - M. Joldos - T.U. Cluj 70
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
SSA cursul 3 - M. Joldos - T.U. Cluj 71
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
SSA cursul 3 - M. Joldos - T.U. Cluj 72
SSA cursul 3 - M. Joldos - T.U. Cluj 73
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