Operazioni sui cifrari a blocchi

In questo paragrafo continueremo la discussione sui cifrari simmetrici, in particolare vedremo che ci sono diversi modi di applicare i cifrari a blocco a testi in chiaro (plaintext).

Cifratura multipla e triple DES
...

Poiché si è scoperto che DES è vulnerabile ad attacchi di tipo bruteforce, DES è stato largamente sostituito da schemi di cifrature più forti. Sono stati utilizzati come spunto due approcci:

  • il primo: progettare un nuovo algoritmo che resiste alla crittoanalisi e al bruteforce: AES ne è un esempio;
  • il secondo: utilizzare diverse cifrature di DES stesso, con diverse chiavi.

Double DES
...

La forma più semplice di crittazione multipla ha due stadi e due chiavi. Dato un plaintext P e due chiavi di cifratura e , il testo cifrato C è generato come: Ovvero viene prima crittato P con e poi il risultato di tale cifratura viene crittato con .
La decrittazione è applicata in ordine inverso: Per DES, questo schema sembra includere una lunghezza della chiave che sia di bit e questo dovrebbe incrementare di molto la forza crittografica dell'algoritmo. Ma per verificarlo dopo esaminare l'algoritmo da più vicino.

Supponiamo vero che per DES, per tutte le chiavi di 56 bit, date due chiavi e possa essere possibile trovare una terza chiave in modo che: Se fosse vero che esiste una chiave che equivale la crittazione fatta con diverse chiavi, allora qualsiasi numero di crittazioni (DES) sarebbe inutile e sarebbe come crittare con una singola chiave da 56 bit. A prima vista, non sembra che l'equazione sopra regga.
Considera che la crittazione con DES è una mappatura di blocchi di 64 bit a blocchi di 64 bit. Infatti, la mappatura può essere vista come una permutazione. Se consideriamo tutti i possibili possibili blocchi in input, la crittazione con DES con una specifica chiave mapperà ogni blocco in un unico blocco a 64 bit. Altrimenti, se, dati due blocchi in input mappati verso stesso blocco di output, allora la decrittazione per recuperare il plaintext originale sarebbe impossibile, poiché ci sarebbe un singolo blocco di output, che corrisponde a più blocchi di input: si creerebbe un'ambiguità.

Con possibili input, quante differenti mappature ci sono che generano una permutazione dei blocchi di input? D'altra parte, DES definisce una mappatura per ogni chiave diversa, essendo una chiave lunga 56 bit, significa che ci sono: Dato che il numero di mappature possibili ottenute con due applicazioni di DES con chiavi diverse () è molto più grande del numero di mappature definite da una singola applicazione di DES, è ragionevole supporre che utilizzando DES due volte, con chiavi diverse, si otterrà una delle molte mappature che non possono essere ottenute con una singola applicazione. Ci furono molte prove a sostegno di questa ipotesi, ma la dimostrazione matematica è stata fornita solo nel 1992.

Attacco a double DES
...

L'uso di double DES restituisce una mappatura che non è equivalente ad una singola applicazione di DES. Ma c'è un modo per attaccare lo schema. L'algoritmo di attacco è noto come attacco meet-in-the-middle ed è basato sull'osservazione che:allora Pasted image 20230721113305.png

Noti dove P è il testo in chiaro e C il testo cifrato con double DES, l'attacco procede come segue:

  • prima viene crittato P per tutte i valori di (semplicemente viene crittato P, per la prima volta, con tutte le possibili chiavi generate da 56 bit). I risultati vengono salvati in una tabella e ordinati per i valori di X (cioè i risultati della cifratura). L'obiettivo di questo passo è ottenere l'output intermedio delle cifratura doppia.
  • Poi, C viene decifrato usando tutte le combinazioni possibili di bit di . Per ogni decifratura risultante viene controllato se si verifica una corrispondenza con i valori raccolti al primo passo in tabella, se si verifica una corrispondenza, l'attaccante ha trovate una chiave per la fase 1 di cifratura, e una chiave per la fase 2 che utilizzate insieme produrrebbero il testo cifrato C.

Double DES utilizza una chiave di 112 bit, quindi ci sono possibili chiavi, inoltre per un certo plaintext P, il massimo numero di chiavi diverse a 112 bit che potrebbe produrre un dato ciphertext C è: ovvero ci sono più chiavi che potrebbero produrre lo stesso testo cifrato, ed esse sono (in base al calcolo sopra): . Quindi l'attacco sopra descritto potrebbe causare diversi falsi positivi, appunto . In ogni caso l'attacco sopra riduce drasticamente il numero di chiavi in cui cercare. Inoltre se, l'attacco viene effettuato su diversi blocchi di testo in chiaro, il numero di chiavi in cui cercare si riduce ancor di più. Questo mostra che effettivamente utilizzare double DES, non porta una vantaggio in termini di sicurezza, ma anzi un peggioramento della sicurezza.

Il discorso appena fatto si estende per diversi tipi di cifrature simili che applicano l'algoritmo di cifratura in due fasi.

Triple DES
...

Un contraccolpo all'attacco meet-in-the-middle è dato dall'utilizzo di tre stadi di cifratura con tre chiavi diverse. Questo approccio applicato a DES origina un algoritmo di cifratura noto come 3DES o triple-DES (TDES). Ci sono due versioni di 3DES:

  • una utilizza due chiavi
  • l'altra ne utilizza tre

Pasted image 20230724115253.png

L'algoritmo ha la seguente forma, nota come EDE: Encryption-Decription-Encryption.
Ovvero per effettuare il 3DES viene applicata una cifratura, una decifratura e un'altra cifratura. Questa scelta non porta nessun vantaggio crittografico, il motivo per cui viene utilizzata è per rendere i messaggi scambiati con 3DES compatibili con DES semplice.

In 3DES con due chiavi, avremmo che vengono utilizzate due solo due chiavi. Nel caso in cui si dovesse decifrare un messaggio con DES semplice, basterebbe applicare il procedimento con due chiavi identiche per decifrare.

3DES con due chiavi


Per ricondurlo al DES semplice:

Questo algoritmo (3DES con due chiavi) è abbastanza popolare e non sono noti attacchi di forza bruta o di crittoanalisi.

Triple DES con tre chiavi
...

Rispetto a 3DES con due chiavi, come abbiamo detto, non sono noti attacchi, con questo volevamo dire che non sono noti attacchi pratici, sono stati proposti alcuni possibili attacchi a questo schema, ma che non sono realizzabili nella realtà, e dunque sono possibili solo teoricamente. Un'alternativa ancora più forte a questo schema è 3DES con tre chiavi.
Per renderlo compatibile con DES è necessario che o .
Diverse applicazioni web adottano 3DES con tre chiavi.

Electronic Codebook (ECB)
...

Un cifrario a blocchi prende un blocco con una lunghezza fissata di b bit e una chiave in input e produce un blocco di b bit di ciphertext. Se la quantità di testo in chiaro da cifrare è maggiore di b bit, allora la cifratura a blocchi può ancora essere utilizzata dividendo il testo in chiaro in blocchi di b bit. Quando più blocchi di plaintext sono cifrati usando la stessa chiave, diversi problemi di sicurezza si palesano. Per utilizzare un cifrario a blocchi su diverse applicazioni sono stati definiti cinque modalità di funzionamento dal NIST (National Istitute of Standards and Technology).
In breve, una modalità di funzionamento è una tecnica per migliorare l'effetto di un algoritmo di cifratura o per adattarlo ad un'applicazione. Le cinque modalità di funzionamento coprono una vasta gamma di applicazioni in cui un cifrario a blocchi può essere utilizzato per crittografare i dati.

Ecco le modalità in tabella:

ModalitàDescrizioneApplicazione tipica
Electronic Codebook(ECB)Ogni blocco di plaintext in bit è codificato indipendentemente utilizzando la stessa chiaveTrasmissioni sicure di valori singoli (una chiave di cifratura)
Cipher Block Chaining (CBC)L'input per l'algoritmo di cifratura è il risultato in XOR del blocco di plaintext successivo e quello precedente (cifrato)Trasmissioni orientata ai blocchi con scopo generico e autenticazione
Cipher Feedback (CFB)L'input è processato s bit alla volta. Il blocco precedente (cifrato) è utilizzato come input per l'algoritmo di cifratura per produrre un output pseudo-casuale, che è messo in XOR con il plaintext per produrre la successiva unità di testo cifratoTrasmissioni orientate allo stream con scopo
Output Feedback (OFB)Simile al CFB, eccetto che l'input all'algoritmo di cifratura è l'output della cifratura precedente. Non viene generato un output pseudo-casuale ed esso non viene messo in XOR con niente (come avviene invece in CFB).Trasmissioni orientate allo stream su canali disturbati (comunicazioni via satellite)
Counter (CTR)Ogni blocco di plaintext è messo in XOR con un contatore crittografico cifrato. Il contatore viene incrementato per ogni blocco successivo del plaintextTrasmissioni orientate ai blocchi con scopo generico e utile quando l'alta velocità di cifratura è un requisito del sistema o applicazione

La modalità più semplice è l'electronic codebook (ECB) in cui il plaintext è gestito un blocco alla volta e ogni blocco di plaintext è crittato usando la stessa chiave. Per un plaintext più lungo di b bit la procedura prevede di dividere il plaintext in più blocchi, aggiungendo del padding (bit posti a 0) se necessario. La decrittazione è applicata in maniera inversa, un blocco alla volta, usando la stessa chiave.

Di seguito nella figura, è schematizzato il funzionamento di ECB.
Pasted image 20230725091917.png

Per messaggi lunghi ECB potrebbe essere non sicuro. Poiché se, per esempio, è noto che i messaggi scambiati iniziano sempre con la stessa espressione, si lascia spazio alla crittoanalisi.

Cipher Block Chaining (CBC)
...

Per superare le difficoltà di ECB, vorremmo una tecnica in cui lo stesso blocco di plaintext, se ripetuto, produca differenti blocchi cifrati. Un metodo semplice per soddisfare questa caratteristica è CBC. In questo schema, l'input all'algoritmo di cifratura è lo XOR tra il blocco di testo in chiaro corrente e il blocco di testo cifrato precedente. Viene utilizzata la stessa chiave per ogni blocco.
Anche CBC richiede che vi sia, eventualmente, del padding per l'ultimo blocco.

Di seguito nella figura, è schematizzato il funzionamento di CBC.
Pasted image 20230725092721.png

Si noti che per decifrare, ogni blocco cifrato è passato all'algoritmo di decifratura (usando la chiave). Il risultato ottenuto è messo in XOR con il precedente blocco cifrato per produrre il blocco in chiaro.

Questa modalità non presenta i problemi di ECB e risulta essere la modalità di cifratura più utilizzata per un cifrario a blocchi. Nell'immagine appare il simbolo che rappresenta un vettore di inizializzazione (Initialization Vector) lungo quanto il blocco. è noto ad entrambi gli estremi della comunicazione, ma è (e deve essere) impredicibile da terze parti.

Problema di CBC

Un errore di trasmissione anche su un singolo bit rende impossibile decifrare il corrispondente blocco e il blocco immediatamente successivo. Inoltre per la natura di CBC, prima di iniziare il processo di cifratura, bisognerebbe che siano noti tutti i blocchi del messaggio da cifrare, se esso è troppo lungo, potrebbe essere richiesto diverso tempi per la cifratura di tutti i blocchi che lo compongono.

Cipher Feedback (CFB)
...

Per qualsiasi cifrario a blocchi, la cifratura viene applicata a blocchi di b bit. Nel caso di DES, b = 64 bit nel caso di AES, b = 128 bit. È sempre possibile far comportare un cifrario a blocchi come un cifrario a flusso (stream cipher) utilizzando una delle seguenti modalità: cipher feedback, output feedback, counter (che non tratteremo).

Una proprietà interessante che un cifrario a flusso deve avere è che il testo cifrato deve essere della stessa lunghezza del testo in chiaro. Se vengono trasmessi caratteri a 8 bit, ogni carattere crittato deve avere una lunghezza di 8 bit.

La figura mostra lo schema per la cifratura di CFB.
Pasted image 20230725103515.png
Nella figura si assume che l'unità di trasmissione sia di s bit, un valore comune per s è 8 bit.
Come in CBC, le unità di plaintext sono incatenata tra di loro, in modo che il ciphertext prodotto sia funzione dei precedenti ciphertext. In questo caso invece di blocchi di b bit, il plaintext è diviso in segmenti di s bit.
L'input per la cifratura è un registro a scorrimento di b bit che è inizialmente impostato a qualche vettore di inizializzazione (). Gli s bit più a sinistra dell'output della funzione di cifratura sono messi in XOR con i primi segmenti del plaintext per produrre la prima unità di testo cifrato , che viene trasmessa. Il vettore viene shiftato di s bit, e viene posizionato negli s bit più a destra in . Questo processo continua fino a che tutti le unità di testo in chiaro non vengono cifrate.

Pasted image 20230725104518.png
Per la decifratura è utilizzato lo stesso schema, eccetto che l'unità di ciphertext ricevuto è messa in XOR con l'output della funzione di cifratura per produrre l'unità di plaintext. Si noti che è usata la funzione di cifratura e non di decifratura.

Problema

È meno efficiente di CBC.
Un errore di trasmissione di un bit nel testo cifrato si propaga per diversi blocchi, dunque risulteranno indecifrabili il blocco successivo e alcuni dei blocchi che lo seguono.

Output Feedback (OFB)
...

La modalità Output Feedback (OFB) è simile nella struttura a CFB. Per OFB, l'output della cifratura viene restituito per diventare l'input necessario alla cifratura del successivo blocco di plaintext. In CFB, l'output dello XOR è restituito per diventare l'input per la cifratura del blocco successivo. Un'altra differenza è che OFB opera su tutti i blocchi di plaintext e ciphertext, mentre CFB opera su segmenti di dimensioni di s bit.

La figura riassume lo schema di funzionamento di OFB.
Pasted image 20230725111352.png

Problema

È meno efficiente di CBC.
Un errore di trasmissione di un singolo bit può avere un effetto limitato sull'intero testo cifrato. In particolare, rende indecifrabile solo il gruppo di bit nella posizione dell'errore, mentre il resto del testo cifrato può ancora essere decifrato correttamente.