Appunti completi corso Crittografia

Partenza con il corso di crittografia

Il significato antico della crittografia era rendere un testo incomprensibile a chi non è il destinatario. La crittografia di oggi è una vera e propria scienza che, insieme alla crittanalisi (che studia come rompere i cifrari), forma la crittologia.

Codici crittografici prima degli anni '70

Prima degli anni '70 i codici crittografici seguivano tutti lo stesso ciclo di vita: si inventava un nuovo codice segreto, spacciato come unbreakable, ma la segretezza era misurata rispetto ad un umano, perché tutti gli algoritmi andavano eseguiti manualmente. Veniva usato da generali, spie, ambasciatori per comunicare informazioni riservate finché un qualche nemico riusciva a crackare il sistema e decifrare i messaggi, rendendo quel codice non più sicuro.

Difetti dei sistemi crittografici antichi

I difetti cruciali dei sistemi crittografici antichi risiedevano nel fatto che mancavano teorie matematiche rigorose, c'era negligenza degli utenti (erano tutti eseguiti a mano...) e si basavano sulla segretezza dell'algoritmo…

La crittologia moderna

Solo negli anni '70 viene definito DES come cifrario standard, poi i signori Diffie-Hellman parlano della crittografia asimmetrica e nello stesso decennio arriva RSA che ne è la prima implementazione. Ma soprattutto la crittologia moderna (dagli anni '70 in poi) si basa su un principio completamente diverso dal passato. Il principio di Kerckhoff dice che un cifrario dev'essere sicuro anche se è completamente noto il suo funzionamento, a parte un parametro che è la chiave. Un altro principio importante è che le primitive crittografiche devono essere implementate in modo efficiente su software e hardware, cioè in modo da minimizzare possibili errori dell'utente e la negligenza degli operatori.

Sicurezza dei crittosistemi

La sicurezza di un crittosistema si studia matematicamente e in base all'information leakage dato dall'implementazione. Sai che ci stanno anche i side channel attack a cui pensare… un sistema si può definire sicuro secondo quattro modelli di sicurezza:

• Unconditional security: un attaccante ha potenza computazionale illimitata, bisogna dimostrare che l’attaccante non ha nessun metodo per indovinare la chiave o avere qualche informazione sul messaggio.
• Computational security: assume che tutti gli avversari siano limitati computazionalmente (ed è così nella realtà) e si pone un lower bound per il best method che rompe il cifrario.
• Provable security: si dimostra che rompere il crittosistema è tanto difficile quanto risolvere un problema computazionale difficile.
• Applied security: riguarda la resistenza di un’implementazione del crittosistema in una certa piattaforma, cioè misura quanto il crittosistema è sicuro di fronte a degli implementation flaws che permettono l’uso di side channel attacks.

Proprietà richieste da un crittosistema

La crittografia opera su ogni sistema dove non c'è universal trust. Da questa frase arrivano le proprietà che un crittosistema deve fornire:

• Confidentiality: fornisce informazioni crittate. Questo servizio rende ogni testo non leggibile da uno che non sia il ricevente. Qui secrecy è sinonimo di confidentiality, da non confondere invece con privacy che è abusato. È un termine più generico, ha un concetto completamente diverso. Riguarda i diritti della singola persona di fornire proprie informazioni agli altri.
• Authentication: è un meccanismo che un sistema usa per identificare i suoi utenti. Risponde alle domande "Chi è l’utente?" e "L’utente o la sua controparte sono veramente chi dicono di essere?". Le parti possono identificare se stesse nel protocollo (si parla di entity authentication), ma magari le parti vogliono assicurarsi che i dati siano scambiati tra le persone giuste, cioè che non ci sia qualcuno nel mezzo (e si parla di data origin authentication). Da non confondere anche qui con authorization, cioè le azioni ammesse per un utente che è già autenticato. Si definiscono dei modelli di controllo degli accessi. Quelli famosi sono il Discretionary Access Control in cui il proprietario dell’oggetto dice chi lo può usare e come (per esempio i famosi rwx di Unix), mentre nel Mandatory Access Control il sistema (non gli utenti) specifica la clearance degli oggetti (del tipo Top Secret, Secret, Confidential, Classified, Unclassified) e la clearance degli utenti che possono leggere questi oggetti.
• Data integrity: controlla che i dati scambiati non siano stati modificati. Per modifica intendiamo aggiunta, rimozione, sostituzione dei dati (che siano memorizzati o in transito in una comunicazione).
• Non-repudiation: il sistema evita che un’entità rinneghi azioni precedenti nel futuro. Cioè? Se due tizi stanno comunicando, Alice dice che vuole comprare delle crocchette per gatti e poi dice che non l’ha mai fatto, serve una terza parte che possa "testimoniare" su cosa sia realmente successo.

Concetti basilari di matematica nella crittografia

Siccome la crittologia è una roba seria, dobbiamo specificare anche i concetti elementari della matematica. Beh si comincia dall’alfabeto A che sai già essere un insieme finito di simboli (per noi saranno semplicemente i due bit). Il message space M è l’insieme di stringhe su A e un suo elemento è detto plaintext. Il ciphertext space C è l’insieme di stringhe crittate su A ed un suo elemento è detto ciphertext. Il key space K è un insieme di chiavi e la sua cardinalità ci fornisce la qualità del crittosistema. Un’encryption transformation è una one-to-one mapping tra message space e cipher space data una certa chiave. La definiamo come funzione E : M → C con k la chiave usata. È una permutazione di message space e cipher space laddove i due insiemi usano lo stesso alfabeto. La decryption transformation è la funzione inversa D : C → M.

In generale un crittosistema è una tupla con sei elementi: {A, M, C, K, E_k, D_k} dove E_k e D_k sono a loro volta degli insiemi di funzioni dipendenti dalla chiave scelta. Come proprietà devono valere la correttezza (cioè il plaintext di un qualsiasi ciphertext è ottenibile attraverso una e una sola chiave), mentre le due funzioni D_k, E_k devono essere veloci da eseguire data una chiave come parametro, ma difficilissime (se non impossibili) da eseguire senza di essa (efficiency and strength).

Paradigmi di crittosistemi

Crittosistemi simmetrici

Ora possiamo parlare di tre diversi paradigmi di crittosistemi. Partiamo dai symmetric cryptosystem. Sono i più chiari da capire, cioè ogni utente ha una secret key di lunghezza fissata. Le funzioni D, E usano la stessa chiave. Possiamo fornire con essi confidentiality e authentication, ma non la non-repudiation perché non ci sono strumenti per implementarla. Le trasformazioni sono di tipo block cipher oppure stream cipher. Nei block cipher abbiamo blocchi di plaintext di lunghezza fissa, gli stream cipher usano plaintext di qualsiasi lunghezza. Questi sistemi sono computazionalmente efficienti, tuttavia la chiave va scambiata tra tutte le parti della comunicazione e su un canale sicuro. Se hai n utenti, ogni coppia ha bisogno di una chiave diversa e si parla di un totale di n(n-1)/2 chiavi da mandare in giro. Per non parlare poi di quando gli utenti entrano ed escono da un gruppo...

Crittosistemi asimmetrici

L’altro paradigma è l’asymmetric cryptosystem: ogni utente è legato ad una coppia di chiavi dette pubblica e privata. La pubblica è usata dagli altri utenti per crittare e mandare cose al proprietario della chiave, la privata per decrittare i dati ricevuti. Questo schema fornisce anche la non-repudiation. Utilizzano problemi matematici ben noti. RSA si basa sulla fattorizzazione dei numeri primi, DH si basa sul logaritmo discreto… Lo schema asimmetrico scala bene con più persone (puoi mettere la tua chiave pubblica in un repository accessibile a tutti). D’altra parte è molto più lento dei sistemi simmetrici e servono chiavi più lunghe per avere lo stesso livello di sicurezza degli schemi simmetrici. Si parla di migliaia di bit contro centinaia di bit. Soprattutto la public key richiede autenticazione, cioè chi ci assicura che quella chiave pubblica è realmente associata ad una certa identità?

Per la non-repudiation servono la digital signature e le certificate authority. La digital signature assicura l’associazione tra public key e messaggio, la firma si ottiene usando la decryption transformation sul plaintext e mandi la firma insieme al messaggio crittato. Siccome hai usato la chiave privata, chi ha la chiave pubblica può verificare l’autenticità del messaggio.

La certification authority è una terza parte di cui ci si fida ed associa la public key ad una certa persona. Essa firma digitalmente un documento con l’identità dell’utente, la sua chiave pubblica e vari metadati. Il certificato è a sua volta firmato da una CA… tu ottieni questo documento firmato dalla CA che garantisce identità e chiave pubblica del proprietario. Siccome le CA si firmano tra loro, abbiamo una vera e propria public key infrastructure. Ogni browser ha un grande insieme di digital certificates dalle CA più importanti, ma pure su Android li puoi vedere.

Crittosistemi basati sull'identità

L’ultimo paradigma è l’identity based cryptosystem. Qualcosa di simile al public key, dove l’identity è qualsiasi informazione in qualche modo già bindata in precedenza con una persona (il numero del passaporto, una mail address…) e viene usata per creare la public key. La chiave non è una stringa di bit qualsiasi, ma è l’identità already bound to you. La private key cos’è qui? Viene assegnata da una trusted authority che combina l’identità e un master secret parameter per generare la private key. Ma qui c’è un problema… la trusted authority conosce la tua chiave privata. Ah. Perché qualcun altro te la costruisce. Mh… il pregio è che non servono digital certificates e non devi perciò gestirli (crearli, aggiornarli, revocarli anche…). Poi la stessa user identity può avere più chiavi private ed ottenere quindi più flessibilità nell’accesso ai dati. Però chiaramente il fatto che qualcuno conosca la tua chiave privata non mi piace, non si può usare nei sistemi aperti, ed usa funzioni ancora più complicate (le curve ellittiche…).

Tipi di attaccanti e metodi di attacco

Un attaccante che vuole leggere la roba si può definire come passivo quando solo monitora il canale di comunicazione. Minaccia solo la confidentiality. L’attaccante attivo cerca di modificare i dati trasmessi, quindi minaccia data integrity, authentication, oltre alla confidentiality.

Per il passive attacker vale sempre l’assunzione di Kerckhoff, cioè le funzioni D, E sono note a tutti nei dettagli. L’attacco più semplice è il bruteforce sull’insieme delle chiavi. Qual è il problema di questo metodo? L’attaccante deve saper distinguere il corretto plaintext da uno valido ma non corretto. Se provi tutte le chiavi, potresti trovare diversi plaintext che sono validi (cioè sono leggibili, hanno senso compiuto), ma uno solo è quello giusto. Tale metodo si può usare contro tutti i sistemi tranne quelli perfectly secure :) perché per costruzione in un perfectly secure cryptoscheme non puoi riconoscere un messaggio valido, cioè lo sono tutti.

Abbiamo poi come prossimo metodo il ciphertext only attack (COA). L’attaccante conosce il ciphertext di vari messaggi criptati con la stessa chiave, non conosce nessun plaintext. Un po’ come nei tempi antichi in cui avevi dei testi crittati e dovevi decifrarli in qualche modo. Tramite analisi statistica si cerca di ricostruire la chiave o il plaintext. Si assume comunque che conosci tutto del crittosistema, cosa non vera millenni fa.

Nel known plaintext attack (KPA), l’attaccante conosce delle coppie di plaintext e ciphertext crittati con la stessa chiave. I cifrari a permutazione si crackano meravigliosamente con questo metodo.

Nel chosen plaintext attack (CPA) l’attaccante può scegliere cosa far cifrare e in base ai ciphertext ottenuti cerca di riconoscere la chiave. L’attaccante ha più controllo di prima perché può scegliere di crittare tutti i plaintext che vuole. Se poi la scelta si può fare a runtime in base alle “scoperte” fatte in quel momento l’attacco è detto adattivo.

Si può fare l’opposto, con un chosen ciphertext attack (CCA): scegli quale testo cifrato far decrittare, magari una volta sola oppure più volte in base a quello che hai scoperto prima (adaptive). L’obiettivo è pian piano ottenere dati sul plaintext o la chiave.

Cifrari antichi e teoria dell'informazione

Per oggi si finisce qui, per fortuna perché abbiamo visto numerose definizioni che sono semplici ma è bene capirsi subito. Oggi vediamo i cifrari “antichi” ed altri principi fondamentali riguardo la teoria dell’informazione. Come detto i cifrari antichi si dovevano eseguire a mano e la difficoltà per romperli si misurava dal punto di vista dello sforzo umano necessario. Ma oggi abbiamo un punto di vista totalmente diverso, per cui il crittosistema è interamente noto nel suo funzionamento ad eccezione della chiave, è l’approccio moderno.

Partiamo dai cifrari per sostituzione che sono i più semplici per poi parlare del mitico Shannon. Il cifrario più semplice in assoluto è il monoalfabetico, più precisamente è una categoria di cifrari, tra i quali il più semplice è il cifrario di Cesare. Hai un insieme di lettere dell’alfabeto (latino in genere), ogni lettera è identificata da un numero. La chiave del cifrario è un numero tra 0 e 25 se il nostro alfabeto ha 26 lettere: la crittazione consiste nel sostituire una lettera con quella corrispondente a k posizioni più avanti (in modulo 26). E per decrittare prendi la lettera cifrata e ci sottrai k. Nel caso in cui l’alfabeto sia quello latino e la chiave sia 13, abbiamo il cosiddetto ROT13 in cui encryption e decryption sono la stessa cosa. Naturalmente un bruteforce è banalissimo da fare pure a mano. Lo spazio dei plaintext è composto da stringhe con una sola lettera!

In generale i cifrari monoalfabetici hanno un alfabeto di lettere su cui si basano sia lo spazio dei plaintext che quello dei ciphertext, e le cardinalità di questi due insiemi DEVONO essere uguali, perché quello che si calcola è una biezione fra i due insiemi. Di fatto la encryption transformation è una qualsiasi biezione fra questi due insiemi. Quante sono le possibili biezioni…? Dato che l’alfabeto ha 26 lettere, il numero di biezioni è 26! perché una volta fissata una corrispondenza per una lettera, le altre hanno un grado di libertà in meno.

Nella sostituzione monoalfabetica generica si possono usare tutte le biezioni possibili fra plaintext e ciphertext, quindi le chiavi possibili sono proprio 26! (all’incirca 2⁸⁸, mentre il cifrario di Cesare ne ha solo 26). Un altro cifrario famoso di questa categoria è Pigpen in cui ogni lettera è sostituita con un simbolo strampalato di un altro alfabeto, ma non è niente di che. Si cracka come nel gioco Cypher... I problemi della settimana enigmistica sono quelli che avevano i crittanalisti duemila anni fa.

Siccome ogni lettera del ciphertext è mappata SEMPRE sulla stessa lettera del plaintext, tali cifrari si possono bucare semplicemente con un COA (ciphertext only attack), senza fare nulla di trascendentale. Basta tenere conto della distribuzione statistica delle lettere nel ciphertext e della lingua del plaintext. Se poi hai già un pezzo di plaintext noto il cifrario è immediatamente rotto.

Sulle slide ci sono esempi bellissimi, tra cui Good Bug Cipher (cercalo).

Data questa semplicità, il prossimo passo è dato dai cifrari polialfabetici, utilizzano più di un cifrario di sostituzione. Succede quando lo spazio dei messaggi plaintext e ciphertext non contengono solo lettere, ma anche alcune parole. Se la chiave ha lunghezza n e l’alfabeto ha 26 lettere, le chiavi possibili sono (26!) che è un numero MOLTO grosso. Anziché avere una sola biezione fra plaintext e ciphertext, ne hai tante che si alternano. Un esempio classico è il cifrario di Vigenere, l’estensione polialfabetica del cifrario di Cesare. Lo scopo è risolvere il problema di avere la stessa lettera plaintext sostituita dalla stessa lettera ciphertext. Vigenere ha solo 26 chiavi, non quel numero gigante di prima :P

Come si cracka questo? Bisogna capire la lunghezza della chiave e pare che ci sia un metodo, un attacco di solo ciphertext funziona (ovviamente, altrimenti non ci sarebbe nel gioco Cypher). Una volta trovata la lunghezza L della chiave si semplifica tutto: dividi il ciphertext in sequenze di lunghezza L e fai un’analisi statistica come se stessi risolvendo tanti cifrari di Cesare distinti. Ma come trovi la lunghezza della chiave? Grazie al Kasiski test. AAAAAH interessante! Data una sequenza di lettere consecutive di lunghezza minore di L, se si ripetono nel plaintext potrebbero essere crittate dalla stessa porzione della chiave se sono ben allineate, e questo suggerisce che i due segmenti testuali abbiano una distanza che è multiplo della lunghezza L. In pratica bisogna trovare lettere consecutive uguali nel ciphertext con almeno 2 o 3 simboli. Trovati questi segmenti, ti registri le distanze fra loro e facendo il massimo comune divisore di queste distanze trovi la lunghezza della chiave, tenendo conto però che c’è il rischio che dei segmenti siano uguali solo per caso. Per velocizzare poi l’analisi statistica si può usare la distribuzione chi-quadro, ma è solo un boost, non è fondamentale per crackare un testo.