.. meta:: :language: it :description language=it: Crittografia moderna :description language=en: Modern Encryption :keywords: IT Security, modern encryption :author: Luciano De Falco Alfano 03 Crittografia moderna ============================== .. contents:: :local: [*Lezione del 10 ott 2019*] Ricordiamo che abbiamo necessità di: * rendere inefficaci gli attacchi *brute force*; * nascondere la natura del linguaggio; * impedire operazioni inverse della cifratura (cifratura non lineare). Cifre a blocchi rispetto quelle a stream ------------------------------------------ In una cifra a blocchi si processano gruppi di lettere del plaintext per produrre un ciphertext di uguale lunghezza. Lo scopo consiste nel nascondere le statistiche del linguaggio del plaintext. La dimensione di un blocco tipicamente è di 64 o 128 bit. Le cifre a stream trattano il plaintext come una sequenza continua di singoli caratteri. Per questo sono meno efficaci delle cifre a blocchi. Molte cifre moderne sono a blocchi, da cui l'importanza di questa tecnologia. Una cifra a blocchi può essere usata per produrre lo stesso effetto di una cifra a stream. Cifre a blocchi ----------------- Una cifra a blocchi opera contemporaneamente su un plaintext di n bit e produce un ciphertext di n bit. Affinché la trasformazione da plaintext a ciphertext sia reversibile, deve essere una funzione, quindi deve mappare univocamente i :math:`2^n` possibili valori del plaintext sui :math:`2^n` possibili valori del ciphertext. Ad esempio, con due digit binari, la seguente è una mappatura reversibile: +-----------+------------+ | plaintext | ciphertext | +===========+============+ | 00 | 11 | +-----------+------------+ | 01 | 01 | +-----------+------------+ | 10 | 00 | +-----------+------------+ | 11 | 10 | +-----------+------------+ Mentre la seguente è una mappatura non reversibile. Si nota come i ciphertext *00* e *01* sono presenti due volte: +-----------+------------+ | plaintext | ciphertext | +===========+============+ | 00 | 00 | +-----------+------------+ | 01 | 01 | +-----------+------------+ | 10 | 00 | +-----------+------------+ | 11 | 01 | +-----------+------------+ in questa condizione quando si incontra *00* nel ciphertext non si sa se associarvi lo *00* o il *10* nel plaintext. Quindi non tutte le tabelle di trasformazione sono accettabili. La quantità di tabelle reversibili è data dalle permutazioni delle :math:`2^n` righe, meno la mappatura plaintext -> plaintext. Ovvero :math:`2^n! - 1`. D'altro canto pensare di utilizzare le tabelle di trasformazione non è agevole perché: * se il blocco (*n*) è piccolo, le strutture linguistiche sopravvivono; * se il blocco è grande dovremmo trasmettere una chiave formata da :math:`2^n` righe; ad esempio per blocchi di 128 bit, la chiave sarebbe formata da una tabella con :math:`3.4 \cdot 10^{38}` righe di 128 bit; * infine, ricordiamo che la relazione tra plaintext e ciphertext non deve essere lineare. Struttura della cifra Feistel ------------------------------ Molti degli attuali algoritmi di encrypt a blocchi derivano dal lavoro di Feistel, impiegato in IBM, del 1973. Feistel descrisse una applicazione pratica di un meccanismo di cifra proposto nel 1945 da Claude Shannon. Meccanismo che alternava il concetto di **diffusione** con quello di **confusione**. *Diffusione* consiste nel diluire la struttura statistica del linguaggio del plaintxt in quella del ciphertext. Ciò si ottiene applicando ripetutamente una permutazione seguita da una funzione, facendo in modo che più bit del plaintext contribuiscano ad un singolo bit del ciphertext. *Confusione* significa rendere non lineare la relazione tra chiave, plaintext e ciphertext. Si ottiene utilizzando un algoritmo di sostituzione complesso. Feistel ha proposto la seguente struttura: * dato un plaintex si divide in due parti uguali: sinistra (:math:`L_0`) e destra (:math:`R_0`); quindi si entra in un blocco di calcolo come segue: #. :math:`R_0` e parte della chiave (:math:`K_0`) sono argomento di una funzione non lineare: :math:`F(R_0, K_0)`; #. il risultato di :math:`F(R_0, K_0)` è posto in *XOR* con :math:`L_0`: :math:`L_0 \oplus F(R_0, K_0)`; #. l'uscita di questo blocco è formato da due parti [#]_: a sinistra :math:`L_1 = R_0`, e a destra :math:`R_1 = L_0 \oplus F(R_0, K_0)`; * a questo punto si iterano le fasi 1. 2. e 3. con i nuovi input e un nuovo pezzo di chiave: :math:`k_1`; l'uscita sarà, come prima, composta di due parti: a sinistra :math:`L_2 = R_1` e a destra :math:`R_2 = L_1 \oplus F(R_1, K_1)`; * si prosegue in questo modo per più blocchi di calcolo successivi, ognuno con un nuovo pezzo di chiave. I parametri che influiscono sul processo di progettazione sono parecchi: * dimensione del blocco di plaintext - maggiore dimensione significa maggiore sicurezza; * dimensione della chiave - anche qui: maggiore dimensione, maggiore sicurezza; * numero di cicli - più cicli aumentano la diffusione; * algoritmo di generazione delle sottochiavi - più è complesso maggiore è la *confusione*. D'altro canto vi è la velocità di esecuzione dell'algoritmo: più si aumentano i parametri predetti in cerca di maggiore sicurezza, più diventa lento. Data Encryption Standard (DES) ---------------------------------- IBM nel 1971 creò LUCIFER che utilizzava blocchi di 128 bit. DES è un algoritmo semplificato derivato da LUCIFER e con blocchi di dimensione di 58 bit [#]_. Utilizza la struttura di Feistel. Si è dimostrato un ottimo algoritmo di cifratura. Per forzarlo, nel 1998, è stato impiegato, un computer speciale: il *DES cracker*. Il crack è avvenuto con un attacco brute force *known-plaintext* e ha richiesto tre giorni di elaborazione. DES è tuttora ampliamente in uso, aumentando la dimensione del blocco a 168 bit. L'algoritmo opera come segue. * Si opera una permutazione iniziale del plaintext e della chiave; * la chiave viene shiftata circolarmente a sinistra, permutata nuovamente; * si esegue il round con la struttura di Feistel; * le precedenti due fasi sono eseguite 16 volte; * l'uscita dal 16° round è invertita (i 32 bit a destra sono posti a sinistra e viceversa); * il risultato precedente subisce una permutazione inversa alla iniziale operata nella prima fase, ottenendo il ciphertext. Le permutazioni della chiave nelle 16 diverse fasi sono uguali, solo la prima permutazione, prima dell'inizio del ciclo di 16 round, è diversa. Infatti la sicurezza è assicurata dalla chiave, non dall'algoritmo (permutazioni incluse). Maggiori dettagli riguardo l'algoritmo di DES sono consultabili in `wikipedia `_ o in `questo articolo `_. DES con chiave a 58 bit non è *computationally secure*, ma aumentando la dimensione del blocco, e di conseguenza della chiave, i tempi per forzare la cifra salgono considerevolmente. Con l'ipotesi di 1E6 decrypt/microsec abbiamo: +------------------+--------------------------+ | dim.chiave (bit) | tempo per forzare (anni) | +==================+==========================+ | 56 | 10E-3 | +------------------+--------------------------+ | 128 | 10E18 | +------------------+--------------------------+ | 168 | 10E30 | +------------------+--------------------------+ Triple DES ------------ Per aumentare la resistenza di DES utilizzando chiavi di dimensioni superiori, senza modificare radicalmente l'algoritmo, si è progettato il **Triple DES** (3DES o TDES). 3DES consiste nell'usare tre chiavi DES e utilizzare l'algoritmo DES 3 volte in cascata, come segue: .. math:: C = E_{K3}(D_{K2}(E_{K1}(P))) dove *C* è ciphertext, *P* plaintext, :math:`E_K(X)` è l'algoritmo di encryption con la chiave *K* sul testo *X*, e :math:`D_K(Y)` è l'algoritmo di decryption con la chiave *K* sul testo *Y*. In pratica: si effettua encryption con la chiave K1, si decripta il risultato con la chiave K2 e si cripta di nuovo con la chiave K3. Il processo di decryption è inverso: .. math:: P = D_{K1}(E_{K2}(D_{K3}(C))) Il vantaggio del 3DES consiste nel fatto che usando tre chiavi da 56 bit, si ottiene una chiave complessiva di 168 bit, con relativa (molto) maggiore sicurezza. Gli svantaggi consistono in: * pesantezza computazionale, che la rende poco utilizzabile con HW non performante; * può avere problemi di sicurezza in relazione all'uso di blocchi di 64 bit. Altre cifre a blocchi, simmetriche ----------------------------------- Esistono altre cifre a blocchi, simmetriche. **International Data Encryption Algorithm** (**IDEA**). Usa una chiave a 128 bit. Utilizzata in PGP **Blowfish**. Questo è un algoritmo leggero, facile da implementare, veloce e che gira in 5Kb di memoria. **Advanced Encryption Standard** (**AES**, o **Rijndael**, pronunciato /ˈrɛindaːl/). Con chiavi di 128, 192 o 256 bit. La dimensione del blocco di plaintext è di 128 bit. Modalità d'operazione ----------------------- Dato l'algoritmo DES (o un qualunque algoritmo di cifratura a blocchi) come base per l'attività di en/decryption, esistono modi diversi di segmentare il plaintext, detti *modalità d'operazione*. **Electronic Codebook** Mode (**ECB**). Consiste nel suddividere il plaintext in blocchi di 64 bit. Ogni blocco viene criptato separatamente, utilizzando la stessa chiave. Analogamente per decrittare. .. image:: ./images/02_ECB.svg Siccome il plaintext deve essere un multiplo di 64 bit, può essere necessario effettuarne il padding. Svantaggio: è possibile che vi siano piccoli blocchi di testo ripetuti, creando così gli stessi ciphertext. In plaintext abbastanza lunghi, ciò può condurre all'emersione di pattern statistici, attaccabili con la criptoanalisi. **Cipher Block Chaining** Mode (**CBC**). Segmenta come EBC, ma l'uscita di una operazione di encrypt viene posta in *XOR* con l'ingresso della operazione successiva. La prima operazione di encrypt usa il primo blocco di plaintext in *XOR* con una chiave iniziale aggiuntiva *IV* (*initialization vector*). .. image:: ./images/33_CBC.svg Si noti bene. Come la chiave *K*, anche la *IV* deve essere conosciuta a chi invia e a chi riceve il messaggio. E, come *K*, anche *IV* deve essere protetta. Per decrittare è necessario rovesciare l'algoritmo. Si decritta il ciphertext e poi lo si pone on *XOR* con il ciphertext dello stadio precedente. Il primo stadio usa *IV* come parametro per l'operazione *XOR* con il risultato del decrypt del primo blocco di ciphertext. CBC non è più utilizzato, proprio a causa della necessità di mantenere segreto *IV*. **Chipher Feedback** Mode (**CFB**). Questo è uno *stream cipher* basato su *block cipher*. Poco utilizzato. In questo caso l'uscita dell'encryption è messa in *XOR* con il plaintext e passata allo stadio di elaborazione successivo come input destro. .. image:: ./images/34_CFB.svg Il diagramma mostrato è semplificato perché non mostra le operazioni di shift e di troncamento per lavorare in streaming su *s* bits per volta. Esiste anche un *Output Feedback* Mode (**OFB**) schematizzato qui di seguito .. image:: ./images/35_OFB.svg In questo caso si lavora a blocchi, non a streaming. **Counter Mode** (**CTR**). Questo è molto utilizzato. Consiste nell'utilizzare un contatore, messo in encrypt con la chiave. L'uscita di questa encrypt viene posta in *XOR* con il plaintext per produrre il ciphertext. Il contatore, che può partire da un qualsiasi valore, viene incrementato di uno per ogni stadio di encrypt, mentre la chiave *K* è costante. .. image:: ./images/36_CTR.svg Si noti che non si cripta il testo, ma un contatore. Il fatto che questo cambi in continuazione permette di trattare con testi lunghi senza problemi. CTR è utilizzato il ATM, IPsec, SSL ed altri. Differential cryptanalysis ---------------------------- DES è un buon algoritmo, per questo per attaccarlo spesso si ricorre alla cryptoanalisi per differenze (*differential cryptoanalysis*). Questa modalità di analisi è stata sviluppata per forzare le cifre a blocchi. Usualmente si effettua un attacco *chosen plain text*, in cui si usano coppie di plaintxt con differenze conosciute, e si studiano i relativi ciphertext per rilevare pattern statistici. Asymmetric encryption ------------------------ Finora abbiamo visto algoritmi di encryption con chiave simmetrica, ovvero la stessa chiave è utilizzate per crittare e decrittare. Esistono sistemi di encrytpion asimmetrici, ovvero le chiavi sono diverse. Comparando i due sistemi possiamo osservare: +----------------------------------------------------+---------------------------------------------------+ | symmetric key system | public key system | +====================================================+===================================================+ | sender e receiver condividono la stessa chiave | ogni entità ha una chiave pubblica e una privata | +----------------------------------------------------+---------------------------------------------------+ | la stessa chiave è usata per crittare e decrittare | si usano chiavi diverse per crittare e decrittare | +----------------------------------------------------+---------------------------------------------------+ | hanno buone performance | possono richiedere più tempo | +----------------------------------------------------+---------------------------------------------------+ | un esempio: AES | un esempio: RSA | +----------------------------------------------------+---------------------------------------------------+ Il processo di creazione e scambio del messaggio avviene così: * il destinatario ha una chiave pubblica e una privata; * il destinatario condivide la sua chiave pubblica con il mittente; * il mittente usa la chiave pubblica per crittare il messaggio, ed invia il messaggio al destinatario; * il destinatario utilizza la sua chiave privata per decrittare il messaggio. Il fatto che la chiave pubblica sia condivisa non è un problema per la sicurezza: non può essere utilizzata per decrittare un messaggio crittografato. L'uso del *brute force* per forzare il messaggio non è ragionevole. Eistono più di 2.8E700 possibili chiavi. Si calcola un tempo di elaborazione superiore alla genesi della Terra. Asymmetric key: RSA ------------------------ Rivest, Shamir, Adleman (**RSA**) non è stato il primo algoritmo a chiave asimmetrica [#]_. Il primo probabilmente è stato il Diffie-Hellman, ma RSA è il più utilizzato. Primo passo per l'uso dell'agoritmo RSA è la generazione delle chiavi, per usarle successivamente per gestire i messaggi. Per la generazione delle chiavi, si procede come segue: #. si scelgono due numeri primi *p* e *q*, ad es. 7 e 5; #. quindi si calcolano due numeri di riferimento: :math:`n = p \cdot q` [#]_, ad es. :math:`n = 7 \cdot 5 = 35`, #. e :math:`z = (p - 1) \cdot (q - 1)`, ad es. :math:`z = 6 \cdot 4 = 24`; #. si sceglie un intero *e* [#]_ tale che: #. :math:`1 < e < z` #. *e* e *z* non hanno divisori comuni salvo *1*; #. ad es. :math:`e = 5`; 5. si determina *d* [#]_ tale che :math:`e \cdot d - 1` sia esattamente divisibile per *z*. Ad es. :math:`d = 5` perché :math:`5 \cdot 5 - 1 = 24` L'algoritmo per generare gli esponenti delle chiavi è piuttosto complesso. Se i due numeri primi sono grandi, occorrono secondi per generare una coppia di chiavi, e questo rente l'attacco *brute force* ancora meno proponibile. In queste condizioni, se si vuole (de)crittare il dato *p* valgono: .. math:: \begin{align} \text{encryption:} \quad c& = p^e \: mod \, n \\ \text{decryption:} \quad p& = c^d \: mod \, n \end{align} dove *c* è il ciphertext, e *p* è il plaintext. Ad es. se :math:`p = 4`, abbiamo: .. math:: \begin{align} c& = 4^5 \: mod \, 35 = 9\\ p& = 9^5 \: mod \, 35 = 4 \end{align} Con *p* e *q* di 48 bit, abbiamo un numero di chiavi possibili dell'ordine di 2.81E700. Ottenendo un sistema *computationally secure*. Per attaccare RSA si sono utilizzati i **time attack**. Ovvero si è analizzato il tempo necessario per eseguire la cifratura. In tal modo è possibile dedurre: * il tipo di cifra; * i parametri di sicurezza. Ad esempio un network-based timing attack su SSL è stato basato su una vulnerabilità conseguenza di ottimizzazioni effettuate per velocizzare l'implementazione del RSA. L'uso di RSA è pervasivo. È usato: * per generare certificati digitali; * SSL; * blockchain; * ... -------------- .. [#] Si noti lo scambio: R va a sinistra e L va a destra, questo avviene ad ogni blocco di calcolo successivo. .. [#] La letteratura parla di 64 bit, ma in realtà il codice di DES ne usa solo 58. Wikipedia, per il `DES `_ menziona 56 bit. .. [#] RSA è del 1978. .. [#] *n* è il modulo. .. [#] *e* è l'esponente della chiave pubblica. .. [#] *d* è l'esponente della chiave privata.