Curs 4 - Metode si protocoale criptografice

1. Scop

Activitati posibile ale intrusilor:

• se conecteaza la un server, dandu-se drept altcineva
• asculta comunicatia intre doua entitati
• impersoneaza serverul in momentul conectarii clientului (clientul are impresia ca se conecteaza la serverul adevarat, cand de fapt s-a conectat la intrus; serverul adevarat nu stie nimic).
• intercepteaza o comunicatie deschisa si poate modifica mesajele schimbate intre cele doua entitati (captureaza un mesaj, il face sa nu ajunga la destinatie sau il trimite modificat la destinatie, sau insereaza mesaje noi).

Deziderate:

• confidentialitate - un mesaj sa nu poata fi inteles decat de catre destinatarul indreptatit
• autentificare - o entitate sa poata sa verifice daca entitatea cu care comunica este cine pretinde ca este
• verificarea integritatii - sa se poata verifica daca un mesaj este asa cum a fost trimis de expeditor si nu a fost modificat de un intrus
• non-repudiabilitate - expeditorul unui mesaj sa nu poata renega ulterior trimiterea (si continutul) mesajului (nu se adreseaza intrusilor, ci relei-vointe a unuia dintre parteneri)

2. Mijloace

2.1. Criptografia clasica

2.1.1. Ce este

Criptarea: m -> c(m) ; m=mesajul in clar, c=functia de criptare, c(m)=mesajul criptat

Decriptarea: c(m) -> d(c(m))=m ; d=functia de decriptare

Decriptarea trebuie sa fie inversa criptarii, adica pentru orice mesaj in clar m trebuie ca d(c(m))=m.

Conceperea si implementarea unui algoritm de criptare este dificila, de aceea la nevoie se schimba doar un parametru al algoritmului: cheia. Deci c=c[k] si d=d[k]. Trebuie ca pentru orice cheie k si pentru orice mesaj in clar m sa avem d[k](c[k](m))=m.

Deoarece siguranta nu se bazeaza pe secretul algoritmului ci pe secretul cheii, algoritmul poate fi facut public. Avantaj: daca eu folosesc un algoritm public pe care nu l-a spart nimeni pana acum, e foarte putin probabil ca la mine sa fie spart algoritmul; mai ales daca acelasi algoritm este folosit si de altii, care au de pazit lucruri mai importante.

2.1.2. Cat de tare este un algoritm de criptare ?

Consideram substitutia monoalfabetica: cheia este o permutare a alfabetului; mesajul criptat se construieste substituind fiecare litera din mesajul in clar cu corespondenta ei prin permutarea cheie.

Numarul de chei: 26!=403291461126605635584000000.

Spargerea prin forta bruta: presupunem ca avem 1000000 calculatoare, fiecare necesita 1ns/combinatie; pentru a incerca toate combinatiile avem nevoie de 12788 ani.

Atac statistic: daca mesajul cifrat este ceva mai lung, atunci literele ce corespund literelor mai frecvente in texte in limba respectiva vor avea numar mai mare de aparitii. In felul acesta, un mesaj poate fi spart fara dificultate in cateva minute.

Moduri de atac de luat in considerare:

• atac cu text cifrat: se da doar mesajul cifrat;
• atac cu text clar si text cifrat: se dau cateva mesaje in clar impreuna cu mesajele cifrate corespunzatoare (de exemplu din transmisii mai vechi), plus un mesaj cifrat cu aceeasi cheie; acesta din urma trebuie descifat;
• atac cu text clar ales: ca si precedenta, dar mesajele in clar pentru cunoscute pentru care se cunoaste mesajul cifrat corespunzator sunt la alegerea spargatorului.

Un algoritm de criptare util practic trebuie sa reziste cu succes la toate atacurile de mai sus.

Un algoritm absolut sigur de criptare este urmatorul: presupunem ca mesajul in clar este un sir de n biti. Cheia va fi un sir aleator de n biti. Mesajul criptat se construieste prin sau exclusiv pe bit intre mesajul in clar si cheie. Algoritmul este sigur pentru ca orice mesaj in clar de lungime n ar fi putut fi sursa unui mesaj cifrat dat, si cu egala probabilitate; spargatorul nu are nici o metoda de-a decide intre aceste posibilitati. Problema este ca trebuie o cheie de lungime egala cu a mesajului in clar, si cheia nu este refolosibila.

2.1.3. Algoritmi de criptare pe bloc

Majoritatea algoritmilor de criptare folositi cripteaza un sir de biti de lungime fixa (ex. 64 biti, sau 128 biti). Pentru ca un astfel de algoritm sa nu fie o mare substitutie monoalfabetica, se foloseste in modul urmator:

• ECB (Electronic Code Book) este modul normal, cu slabiciunea sus-amintita
• CBC (cipher block chaining): se transmite intai un bloc construit aleator; apoi fiecare bloc de mesaj in clar se supune unui sau exclusiv cu rezultatul criptarii blocului precedent si se cripteaza rezultatul
• CFB (Cipher Feedback Mode) se foloseste pentru a putea transmite cate un octet o data (fara sa fie nevoie sa se completeze cate un bloc intreg). Se ia un registru de deplasare de exact un bloc; valoarea initiala este aleasa aleator si transmisa destinatarului. Apoi, pentru a coda un octet, se ia rezultatul criptarii registrului de deplasare, se selecteaza ultimul octet si se face sau exclusiv intre acesta si octetul de transmis. Rezultatul operatiei sau exclusiv se transmite efectiv, si totodata se introduce in registrul de deplasare.

2.1.4. Probleme de rezolvat

• generarea cheilor
• transmiterea cheilor

2.2. Functii sens unic

Exista functii (inversabile) usor de calculat, dar a caror inversa este foarte greu de calculat (nu se cunoaste un algoritm semnificativ mai eficient decat verificarea element cu element a domeniului functiei directe). Astfel de functii se numesc functii sens unic

De exemplu, f(b)=b^e mod n e usor de calculat (numarul de operatii e de ordinul patratul numarului de cifre ale lui n inmultit cu numarul de cifre a lui e, dar gasirea lui b cunoscand e, n si f(b) este extrem de dificila in general. De notat ca in practica se lucreaza cu numere de cateva sute de cifre zecimale.

2.3. Schimbul de chei Diffie-Hellman

Problema: se cere ca partenerii A si B sa cada de acord asupa unei chei, fara ca un intrus care asculta conversatia sa poata obtine cheia.

Solutie (metoda Diffie-Hellman):

1. A alege numerele b, n si x;
2. A transmite lui B valorile: b, n si b^x mod n
3. B alege numarul y
4. B trimite lui A valoarea b^y mod n
5. A calculeaza k=(b^y mod n)^x mod n = b^xy mod n
6. B calculeaza k=(b^x mod n)^y mod n = b^xy mod n

Vulnerabilitate: atacul man in the middle.

2.4. Criptografia asimetrica

Se mai numeste si criptografie cu cheie publica

Ideea:

• algoritmii de criptare si de decriptare folosesc chei diferite (desigur, impererecheate): d[kd](c[kc](m))=m
• cheia pentru criptare kc se obtine din cheia de decriptare kd printr-o functie sens unic: kc=f(kd)
• c[kc](m) este functie sens unic in raport cu m, altfel spus, dandu-se c[kc](m) si kc este dificil de gasit m

Aplicarea:

1. destinatarul alege kd si o tine secreta
2. destinatarul calculeaza kc=f(kd) si o face publica
3. expeditorul calculeaza c[kc](m) si il trimite destinatarului
4. destinatarul regaseste m=d[kd](c[kc](m))

Comunicarea este posibila intr-un singur sens. Daca se doreste comunicarea in celalalt sens, trebuie generata o alta pereche de chei.

Criptografia simetrica este foarte lenta, comparativ cu criptografia asimetrica. de aceea, in aplicatiile practice, comunicatia propriu-zisa se cripteaza cu o metoda simetrica, si doar cheia se transmite criptata cu o metoda asimetrica.

2.4.1. Semnatura electronica folosind criptografie asimetrica

Este necesar ca functia de criptare sa fie bijectiva (nu doar injectiva)

Metoda:

1. expeditorul A alege kd si o tine secreta
2. expeditorul A calculeaza kc=f(kd) si o face publica. kc va avea rolul de "specimen de semnatura"
3. daca expeditorul A doreste sa trimita un mesaj semnat, genereaza semnatura s=d[kd](m) si o trimite impreuna cu m destinatarului. De fapt, esential este sa trimita doar s si numele expeditorului. De remarcat ca mesajul va fi trimis "in clar"; daca este necesara confidentialitatea, atunci s trebuie transmis criptat, si pentru asta se va folosi o cheie independenta de kd si kc
4. destinatarul B recupereaza m=c[kc](s) si (daca m este inteligibil) poate fi sigur ca s a fost generat de posesorul lui kd; mai mult, chiar daca A reneaga trimiterea mesajului m, B poate dovedi in fata instantei ca m=c[kc](s) si deci s a fost creat de posesorul cheii secrete kd, adica de catre A.

2.5. Functii de dispersie criptografice

O functie de dispersie criptografica este o functie care ia ca intrare un sir de octeti de o lungime oarecare si calculeaza o valoare, de obicei pe 128 de biti, avand proprietatile urmatoare:

• functia sa se poata calcula usor
• este foarte dificil (imposibil de rezolvat in timp util) ca, dandu-se o valoare posibila a functiei, sa se calculeze un sir de biti care ar fi putiut genera acea valoare
• este foarte dificil sa se gaseasca doua siruri carora daca li se aplica functia se obtine acelasi rezultat

Utilitatea este aceea ca putem semna sau "tine la loc sigur" doar rezultatul ("suma de contrl") aplicarii unei functii de dispersie criptografice, si nu tot mesajul sau fisierul original; daca un intrus modifica mesajul, nu poate in mod practic sa genereze un mesaj care sa aiba aceeasi "suma de control".

2.6. Numere aleatoare

Utilitate:

• generare chei
• generare vectori de initializare pentru CBC si CFB

Generatorii de numere aleatoare pentru aplicatii criptografice trebuie ca, pe langa conditiile de distributie pe care trebuie sa le indeplineasca orice generator de numere aleatoare, sa nu fie predictibile. Daca generatorul este pseudo-aleator, starea interna a generatorului sau urmatorul numar generat trebuie sa nu fie previzibile chiar daca se cunoaste istoricul complet al numerelor generate.

Cea mai sigura metoda este folosirea unui generator adevarat, bazat pe un fenomen fizic suficient de aleator - de exemplu zgomotul termic sau dezintegrarea unei substante radioactive. In lipsa, se folosesc interactiunile utilizatorului - momentul cand apasa o tasta sau miscarile mouse-ului.

3. Chestiuni privind elaborarea protocoalelor

• redondanta pentru controlul integritatii (prevenirea atacului prin folosirea unor blocuri codate transmise anterior)
• prevenirea replicilor (actiunea unui pachet trebuie sa fie idempotenta): numerotarea pachetelor, introducerea datei in fiecare pachet, etc

Retele de calculatoare