On the security of 2-key triple DES

Questo documento evidenzia che la sicurezza del 2-key triple DES è significativamente inferiore alle stime precedenti a causa di un nuovo attacco crittografico, suggerendo che il margine di sicurezza è esiguo e che la sostituzione con la variante a tre chiavi dovrebbe essere affrontata con urgenza.

L'essenziale

🕵️‍♂️ Il Mistero del "Triplo DES": Perché la vecchia chiave non è più sicura

Immagina che 2-key Triple DES sia come una vecchia cassaforte bancaria molto famosa, usata da decenni per proteggere i soldi delle carte di credito. Per aprirla, serve una chiave speciale composta da due pezzi (chiamiamoli Chiave A e Chiave B).

Per anni, gli esperti hanno detto: "Non preoccupatevi, questa cassaforte è sicura. Anche se qualcuno prova a forzare la serratura, ci vorrebbero 80 anni di tentativi infiniti per aprirla. Inoltre, se cambiate la chiave ogni tanto, siete al sicuro."

Tuttavia, il nuovo studio di Chris J. Mitchell (l'autore del paper) arriva con una notizia sconvolgente: quella cassaforte ha un difetto di progettazione che rende la "sicurezza" molto più fragile di quanto pensassimo.

Ecco come funziona la scoperta, spiegata con tre metafore semplici:

1. La Metafora del "Cacciatore di Chiavi" (L'attacco generalizzato)

Immagina un ladro che vuole trovare la chiave della cassaforte.

• La vecchia teoria: Il ladro deve rubare 4 miliardi di documenti cifrati (messaggi) che sono stati tutti chiusi con la stessa identica chiave. Se riesce a fare questo, può provare a indovinare la chiave. È difficile, ma teoricamente possibile.
• La nuova scoperta: Mitchell dice: "Ehi, non serve rubare documenti della stessa chiave! Posso rubare documenti di mille cassaforti diverse, tutte chiuse con chiavi diverse, ma che usano lo stesso tipo di serratura."
  • L'analogia: È come se il ladro non avesse bisogno di trovare una chiave specifica per una porta. Può raccogliere milioni di chiavi di diverse case, provarle tutte insieme e, grazie a un trucco matematico, capire quale di quelle chiavi apre la sua porta target.
  • Il risultato: Cambiare la chiave regolarmente (come consigliavano gli esperti) non ferma più il ladro. Il ladro può semplicemente raccogliere i dati di molte chiavi diverse e trovare quella giusta comunque.

2. Il Trucco dello Specchio (La proprietà di complementazione)

Il DES (il cuore di questo sistema) ha una strana proprietà: se prendi una chiave e la "specchi" (inverti tutti i suoi bit, come se fosse un negativo di una foto), funziona quasi esattamente come la chiave originale.

• L'analogia: Immagina di avere un lucchetto. Se provi a girare la chiave a destra, si apre. Mitchell scopre che se provi a girare la chiave "al contrario" (specchio), il lucchetto si apre comunque (o quasi).
• Il vantaggio: Questo permette al ladro di raddoppiare i suoi tentativi senza fare più fatica. È come se avesse due mani invece di una: ogni volta che prova una chiave, ne prova automaticamente anche la "copia speculare". Questo dimezza il tempo necessario per trovare la chiave giusta.

3. Il Puzzle con Pezzi Mancanti (Plaintext parzialmente noto)

Spesso, quando rubiamo dei dati, non sappiamo tutto. Sappiamo che un messaggio inizia con "Conto Corrente 12345..." ma non sappiamo la cifra finale (il PIN).

• La vecchia teoria: Il ladro aveva bisogno di sapere esattamente cosa c'era scritto prima di poter provare ad aprire la serratura. Se mancava anche solo una lettera, il tentativo falliva.
• La nuova scoperta: Mitchell dice: "Non importa se non sappiamo tutto! Possiamo indovinare le parti mancanti."
  • L'analogia: Immagina di dover indovinare una password di 8 caratteri, ma ne conosci già 7. Invece di fermarti, provi a inserire tutte le 10 possibilità per l'ultimo carattere (0, 1, 2... 9). Il sistema lo accetta come un tentativo valido. Anche se 9 su 10 sono sbagliati, il sistema non si blocca; il ladro continua a provare finché non trova quella giusta.
  • Il risultato: Questo rende l'attacco possibile anche in scenari reali dove i dati non sono perfetti, come nei sistemi bancari che usano PIN o codici account.

📉 Cosa significa tutto questo per noi?

1. La "sicurezza da 80 bit" è un'illusione: Prima si pensava che 2-key Triple DES fosse sicuro quanto una chiave a 80 cifre. Ora sappiamo che, grazie a questi trucchi, è molto più debole. È come se avessimo una cassaforte che pensavamo avesse un muro di 80 metri di spessore, ma in realtà ne ha solo 40.
2. Cambiare la chiave non basta: Il consiglio di "cambiare la chiave spesso" era dato per evitare che un ladro accumulasse troppi dati. Ora che il ladro può usare dati di molte chiavi diverse, questo consiglio perde gran parte della sua efficacia.
3. È ora di andare via: Il paper conclude che, anche se la cassaforte non è "rotta" al 100% (cioè non si apre con un coltellino), il margine di sicurezza è così sottile che è pericoloso continuare a usarla.

🚀 La Conclusione: Cosa dobbiamo fare?

Il messaggio è chiaro: Smettiamola di usare 2-key Triple DES.
Dobbiamo passare subito a:

• La versione a 3 chiavi (che è più robusta).
• O meglio ancora, a sistemi moderni come AES (il nuovo standard), che sono come cassaforti di nuova generazione, progettate per resistere anche ai computer del futuro (inclusi i computer quantistici).

In sintesi: quella vecchia cassaforte ha funzionato bene per 40 anni, ma ora i ladri hanno trovato un nuovo modo per scassinare le serrature senza nemmeno dover aspettare che la chiave cambi. È ora di cambiarla davvero.

Sommario tecnico

Titolo: Sulla sicurezza del Triple DES a 2 chiavi

Autore: Chris J. Mitchell (Royal Holloway, University of London)
Data: Febbraio 2016 (Revisione luglio 2016)

---

1. Il Problema

Il Triple DES a 2 chiavi (2-key 3DES) è stato a lungo considerato una soluzione crittografica robusta, offrendo una sicurezza stimata di 80 bit, nonostante l'uso di chiavi DES a 56 bit. Sebbene il NIST abbia ritirato il supporto per questa variante alla fine del 2015, essa rimane ampiamente utilizzata, specialmente nel settore dei pagamenti (es. standard EMV per carte di credito/debito) e come standard ISO/IEC.

Il problema centrale affrontato dal paper è che la stima di sicurezza di 80 bit, spesso considerata conservativa, potrebbe essere eccessivamente ottimistica. L'opinione diffusa secondo cui il cambio frequente delle chiavi mitigherebbe efficacemente i rischi crittografici viene messa in discussione. L'autore dimostra che il margine di sicurezza è molto più sottile di quanto si pensasse, rendendo l'attacco pratico in scenari più ampi di quelli precedentemente considerati.

2. Metodologia

L'autore analizza e generalizza l'attacco noto come attacco di van Oorschot-Wiener (1990), che era stato il metodo più efficace contro il 2-key 3DES per 25 anni. La metodologia si basa su tre principali estensioni e ottimizzazioni di questo attacco originale:

1. Generalizzazione a più chiavi: L'attacco originale richiedeva un gran numero di coppie (piano testo, cifrato) generate tutte con la stessa coppia di chiavi. L'autore dimostra che l'attacco funziona efficacemente anche se le coppie provengono da molteplici chiavi diverse, purché siano raggruppate correttamente durante l'analisi.
2. Sfruttamento della proprietà di complementazione del DES: Il DES possiede una proprietà nota (se si complementano sia il testo in chiaro che la chiave, il testo cifrato risulta complementato). Questa proprietà viene utilizzata per raddoppiare l'efficienza dell'attacco, permettendo di testare due valori contemporaneamente.
3. Utilizzo di testo in chiaro parzialmente noto: L'attacco viene modificato per gestire casi in cui non si conosce l'intero blocco di testo in chiaro, ma solo una parte (es. blocchi PIN dove il numero di conto è noto ma il PIN no). L'autore mostra come generare coppie "fittizie" basate sulle parti note senza aumentare significativamente la complessità computazionale.

3. Contributi Chiave

Il paper introduce i seguenti avanzamenti tecnici:

• Generalizzazione dell'attacco van Oorschot-Wiener: Viene dimostrato che l'attacco non fallisce se le chiavi cambiano nel tempo. Se un attaccante raccoglie $n$ coppie di dati da diverse chiavi, può comunque recuperare una delle chiavi con la stessa complessità computazionale, riducendo l'efficacia della strategia di "cambio frequente delle chiavi" come misura difensiva primaria.
• Ottimizzazione tramite Complementazione: Sfruttando la proprietà $E_K(P) = \overline{E_{\overline{K}}(\overline{P})}$, la complessità temporale dell'attacco viene dimezzata, passando da $2^{121-t}$a$2^{120-t}$operazioni DES (dove$n=2^t$ è il numero di coppie).
• Gestione del Testo Parzialmente Conosciuto: Viene presentata una tecnica per incorporare coppie dove solo $64-w$ bit del testo in chiaro sono noti. Questo espande drasticamente i vettori di attacco, rendendo fattibile l'analisi di dati reali (come i blocchi PIN nelle transazioni bancarie) dove il testo in chiaro è spesso parzialmente strutturato o noto.
• Analisi dell'ANSI Retail MAC: L'autore applica la versione generalizzata dell'attacco all'algoritmo di autenticazione dei messaggi (MAC) utilizzato nell'industria dei pagamenti (ANSI Retail MAC / CBC-MAC-Y), dimostrando che anche questo schema è vulnerabile se vengono raccolti sufficienti messaggi/MAC, anche generati con chiavi diverse.

4. Risultati

I risultati quantitativi e qualitativi principali sono:

• Complessità dell'Attacco:
  • Con $n = 2^{32}$ (circa 4 miliardi) di coppie di testo in chiaro/cifrato (note o parzialmente note), la chiave può essere scoperta con circa $2^{88}$ operazioni DES (grazie all'ottimizzazione di complementazione).
  • Senza l'ottimizzazione di complementazione, la complessità sarebbe $2^{89}$.
  • La complessità spaziale è $O(2^t)$ o $O(2^{t+w})$ a seconda della conoscenza parziale.
• Impatto sulla Stima di Sicurezza: La stima di 80 bit di sicurezza non è più considerata conservativa. Il margine di sicurezza è "esile".
• Invalidazione delle Contromisure: La pratica di cambiare le chiavi regolarmente non impedisce l'attacco; limita solo l'impatto (quantità di dati decifrabili) una volta che una chiave è stata compromessa, ma non riduce la probabilità di successo dell'attacco stesso.
• Vulnerabilità del MAC: L'attacco generalizzato rende vulnerabile l'ANSI Retail MAC anche quando il numero di messaggi generati con una singola chiave è basso (sotto la soglia richiesta dagli attacchi precedenti come quello di Preneel-van Oorschot), purché si abbiano molti messaggi totali da chiavi diverse.

5. Significato e Conclusioni

Il paper conclude che il 2-key Triple DES è praticamente rotto in scenari realistici, specialmente nel settore dei pagamenti dove grandi volumi di dati sono disponibili e le chiavi possono essere parzialmente note.

• Urgenza di Migrazione: L'autore raccomanda con urgenza di sostituire il 2-key 3DES con la variante a 3 chiavi o, preferibilmente, con algoritmi moderni come l'AES.
• Riflessione sulla Sicurezza: La sicurezza di 80 bit è insufficiente nell'era moderna, considerando che 56 bit (DES singolo) erano già considerati rischiosi 30 anni fa.
• Implicazioni Future: L'uso di algoritmi come l'AES permetterebbe l'adozione di chiavi a 256 bit, offrendo protezione anche contro futuri attacchi basati sul calcolo quantistico.

In sintesi, il lavoro di Mitchell dimostra che la sicurezza percepita del 2-key 3DES è un'illusione basata su modelli di attacco obsoleti, e che le attuali pratiche di mitigazione (cambio frequente delle chiavi) sono insufficienti a proteggere i sistemi critici che ancora dipendono da questo standard.