Crittanalisi differenziale

La crittanalisi differenziale è una forma generale di crittanalisi, applicabile principalmente ai cifrari a blocchi ma anche ai cifrari a flusso ed alle funzioni crittografiche di hash. Nel senso più ampio del termine, la crittanalisi differenziale di una funzione crittografica è lo studio di come le differenze nei dati forniti in ingresso alla funzione possono incidere sulle differenze risultanti in uscita dalla stessa. Nel caso di un cifrario a blocchi, si riferisce ad un insieme di tecniche per tracciare le differenze attraverso la rete delle trasformazioni che l'algoritmo opera durante la sua esecuzione, scoprendo dove il cifrario mostra comportamenti non casuali, permettendo di sfruttare tali proprietà per recuperare la chiave segreta.

Storia

La scoperta della crittanalisi differenziale è generalmente attribuita ad Eli Biham e Adi Shamir alla fine degli anni ottanta, che pubblicarono un numero di attacchi contro diversi cifrari a blocchi e funzioni di hash, inclusa una debolezza teorica del DES.

James Bamford, giornalista e scrittore statunitense particolarmente interessato agli affari governativi, scrisse nel suo libro The Puzzle Palace del 1982 che il DES era sorprendentemente resistente alla crittanalisi differenziale, nel senso che anche piccole modifiche apportate all'algoritmo lo avrebbero reso suscettibile di un attacco. Ciò faceva pensare che i progettisti IBM che realizzarono il DES fossero a conoscenza di questa tecnica di attacco già negli anni settanta.

Nel 1994 Don Coppersmith, membro del gruppo originale di sviluppo del DES, pubblicò un documento in cui affermava che la crittanalisi differenziale era nota ad IBM già dal 1974, e che uno degli obiettivi perseguiti durante la stesura del DES era proprio quello di renderlo sicuro contro tale attacco.

Secondo lo scrittore Steven Levy, IBM aveva scoperto la crittanalisi differenziale per proprio conto, e la National Security Agency (che visionò il DES prima della sua pubblicazione) ne era evidentemente a conoscenza, tant'è che consigliò ad IBM di tenere la cosa segreta, come ammise lo stesso Coppersmith a Levy:

«Dopo alcune discussioni con l'NSA, fu deciso che la divulgazione delle considerazioni sulla struttura del DES avrebbe rivelato la crittanalisi differenziale, una tecnica molto potente che poteva essere utilizzata contro molti cifrari. Questo avrebbe indebolito il vantaggio in campo crittografico degli Stati Uniti d'America nei confronti degli altri Paesi..»

All'interno di IBM la crittanalisi differenziale era nota come T-attack o "Tickle attack".

Mentre il DES era progettato con l'intento di resistere alla crittanalisi differenziale, molti altri cifrari contemporanei ne risultano ancora vulnerabili. Uno dei primi bersagli di questo attacco fu il cifrario a blocchi FEAL: la versione originale dell'algoritmo, basata su 4 passaggi (FEAL-4), può essere violata utilizzando soltanto 8 testi in chiaro scelti, e anche una versione con 31 passaggi del FEAL è sensibile a questo attacco.

Meccanismi di attacco

La crittanalisi differenziale è di solito un attacco con testo in chiaro scelto, vale a dire che l'attaccante deve essere in grado di ottenere i messaggi cifrati relativi a testi in chiaro di sua scelta. Lo schema può crittanalizzare con successo il DES con l'uso di 2⁴⁷ testi in chiaro scelti. Ci sono, peraltro, delle estensioni che permetterebbero l'uso di testo in chiaro noto oppure un attacco con solo testo cifrato.

Il metodo base utilizza coppie di testo in chiaro relazionate da una costante detta differenza: la differenza può essere definita in vari modi, ma l'operazione più usata è generalmente l'OR esclusivo (XOR). L'attaccante può calcolare le differenze dei corrispondenti testi cifrati, sperando di intercettare dei motivi statistici nella loro distribuzione. La coppia risultante delle differenze è detta una differenziale. Le loro proprietà statistiche dipendono dalla natura delle S-box usate per la cifratura, così che l'attaccante analizza le differenziali $(\Delta _{X},\Delta _{Y})$, dove $\Delta _{Y}=S(X)\oplus S(X\oplus \Delta _{X})$ ($\oplus$ denota un OR esclusivo) vale per ognuna delle S-box $S$.

Nell'attacco base ci si attende che una particolare differenza nei testi cifrati sia abbastanza frequente; in questo modo, il cifrario può essere distinto dal caso. Varianti dell'attacco più sofisticate permettono di recuperare la chiave più velocemente della ricerca esaustiva di tutte le possibili combinazioni.

Nella forma più semplice del recupero della chiave tramite crittanalisi differenziale, un attaccante richiede il testo cifrato per un gran numero di coppie di testi in chiaro, e poi assume che la differenziale tenga per almeno r-1 passaggi, dove r è il numero totale di passaggi del cifrario. L'attaccante poi deduce quali sotto-chiavi (per il passaggio finale) sono possibili tenendo conto della differenza tra i blocchi prima che l'ultimo passaggio sia completato: quando le sotto-chiavi sono corte, ciò può essere fatto in modo semplice, decifrando esaustivamente le coppie di testo cifrato con un passaggio del cifrario ed ogni possibile sotto-chiave. Quando una sotto-chiave è stata montata come potenziale sotto-chiave molto più spesso rispetto a qualsiasi altra chiave, allora si assume che essa sia la sotto-chiave corretta.

Per ogni particolare cifrario, la differenza dell'input deve essere selezionata accuratamente se l'attacco deve avere successo. Si intraprende allora un'analisi accurata della struttura interna dell'algoritmo: il metodo standard è quello di tracciare un percorso di differenze altamente probabili attraverso i vari passaggi del processo di cifratura, denominato caratteristica differenziale.

Dato che la crittanalisi differenziale è divenuta di pubblico dominio, è divenuta anche una preoccupazione di base dei crittografi (coloro che progettano gli algoritmi crittografici): ci si aspetta infatti che i nuovi sistemi siano accompagnati da un'analisi da cui si evinca che l'algoritmo è resistente a questo tipo di attacco, e per molti di essi, incluso il noto AES, è stato matematicamente provato che lo sono.

Voci correlate

• Crittanalisi
• Crittanalisi lineare

Tipi particolari di crittanalisi differenziale

• Crittanalisi differenziale di alto ordine
• Crittanalisi differenziale troncata
• Crittanalisi differenziale impossibile
• Attacco a boomerang

Collegamenti esterni

• Un tutorial sulla crittanalisi differenziale (e lineare), su engr.mun.ca.
• Selezione di collegamenti sulla crittanalisi differenziale raccolti da Helger Lipmaa, su research.cyber.ee. URL consultato il 20 novembre 2008 (archiviato dall'url originale il 29 gennaio 2009).
• Una descrizione dell'attacco applicato al DES, su home.earthlink.net. URL consultato il 20 novembre 2008 (archiviato dall'url originale il 19 ottobre 2007).
• Eli Biham, diapositive da "How to Make a Difference: Early History of Differential Cryptanalysis" - 850KiB - Fast Software Encryption 2006