Crittoanalisi

Per crittoanalisi (dal greco kryptós, "nascosto", e analýein, "scomporre"), o crittanalisi, si intende lo studio dei metodi per ottenere il significato di informazioni cifrate senza avere accesso all'informazione segreta che è di solito richiesta per effettuare l'operazione. La crittoanalisi è la "controparte" della crittografia, vale a dire lo studio delle tecniche per occultare un messaggio, ed assieme formano la crittologia, la scienza delle scritture nascoste.

Con crittanalisi ci si riferisce non solo ai metodi per violare un cifrario, ma anche ad ogni tentativo di eludere la sicurezza di algoritmi crittografici e protocolli crittografici, ad esempio usando il canale laterale.

Storia

Crittoanalisi classica

La prima pagina del manoscritto di Al-Kindi del IX secolo intitolato Manoscritto sulla decifrazione dei messaggi crittati

Anche se il termine è relativamente recente (fu coniato da William Friedman nel 1920), i metodi per violare il codice crittato ed i cifrari crittografici sono molto più vecchi. La prima spiegazione scritta nota della crittanalisi risale al IX secolo ed è opera del genio arabo Abu Yusuf Yaqub ibn Ishaq al-Sabbah Al-Kindi (noto anche in Europa con il nome latinizzato di Alchindus): si tratta del Manoscritto sulla decifrazione dei messaggi crittati. Questo trattato include una descrizione di un metodo di Analisi delle frequenze (Ibrahim Al-Kadi, 1992- rif-3).

L'analisi delle frequenze è un metodo base per violare molti cifrari classici. Nei linguaggi naturali certe lettere dell'alfabeto appaiono più frequentemente di altre. Ad esempio, in italiano le lettere "A" ed "E" sono quelle che appaiono più frequentemente in un qualunque messaggio in chiaro: se un messaggio è stato cifrato con un cifrario a sostituzione monoalfabetica (in cui ogni lettera è semplicemente rimpiazzata da un'altra), è lecito supporre che le lettere più frequenti che appaiono nel testo cifrato siano candidate per la "A" o la "E".

In pratica, l'analisi delle frequenze si basa molto sulla conoscenza linguistica, dato che si appoggia sulla statistica, ma non appena i cifrari diventarono più complessi la matematica divenne più importante nella crittanalisi. Questo cambiamento è stato particolarmente evidente durante la seconda guerra mondiale, quando i tentativi di violare i cifrari delle Potenze dell'Asse richiesero nuovi livelli di sofisticazione matematica. Inoltre in quell'epoca fu introdotta per la prima volta l'automazione nella crittanalisi con il calcolatore polacco Bomba, con l'uso di dispositivi a schede perforate e nel Colossus, uno dei primi computer (forse il primo computer digitale elettronico programmabile).

La crittoanalisi moderna

Replica di un calcolatore Bomba

L'elaborazione automatica, applicata con grande profitto alla crittanalisi durante la seconda guerra mondiale, spinse alla produzione di nuove tecniche di crittografia diversi ordini di grandezza più complesse delle precedenti. Considerata nel suo insieme, la moderna crittografia è divenuta molto più difficile da crittanalizzare con i sistemi penna-e-carta del passato, tanto da apparire in vantaggio sulla crittanalisi pura.

Lo storico David Kahn afferma che "sono molti oggigiorno i crittosistemi, offerti dalle centinaia di venditori in circolazione, che non possono essere violati da nessuno dei metodi noti di crittanalisi. Infatti su quei sistemi anche un attacco con testo in chiaro scelto, in cui un messaggio in chiaro appositamente selezionato è comparato con l'equivalente testo cifrato, non permette di recuperare la chiave che sblocca altri messaggi. In un certo senso, quindi, la crittanalisi è morta. Ma questa non è la fine della storia: la crittanalisi può anche essere morta ma, per usare una mia metafora, c'è più di un modo per scuoiare un gatto"^[1]. Kahn prosegue menzionando le cresciute opportunità di intercettazione, le microspie (o cimici), gli attacchi del canale laterale e la crittografia quantistica sono validi sostituti dei tradizionali significati di crittanalisi.

Forse Kahn è stato troppo affrettato nel dare per morta la crittanalisi: i cifrari deboli sono tutt'altro che estinti, ed i metodi crittanalitici utilizzati dalle agenzie di intelligence rimangono tuttora per lo più ignoti. In campo accademico, molti studiosi presentano regolarmente nuovi sistemi crittografici, che spesso sono velocemente violati: il cifrario a blocchi Madryga, pubblicato nel 1984 fu trovato sensibile agli attacchi con solo testo cifrato nel 1998; il FEAL-4, proposto come sostituto del DES, fu demolito da una serie di attacchi sferrati dalla comunità accademica, molti dei quali sono completamente attuabili in pratica.

Anche nell'industria molti cifrari non sono esenti da debolezze: per esempio, gli algoritmi A5/1, A5/2 e CMEA, usati nella tecnologia della telefonia mobile, possono essere violati in ore, minuti o anche in tempo reale utilizzando computer alla portata di molti. Nel 2001 fu dimostrato che il protocollo WEP, utilizzato per rendere sicure le connessioni Wi-Fi, era insicuro ed un attacco correlato alla chiave poteva permettere di recuperare quest'ultima in poche ore. Nel 2005 è stato addirittura trovato un modo per violare una connessione protetta da WEP in meno di un minuto^[2].

Le evoluzioni a partire dal XX secolo

Il Telegramma Zimmermann decifrato.

Diverse volte i successi della crittoanalisi hanno influenzato la storia: l'abilità di leggere i presunti pensieri ed i piani segreti di altre persone può essere un vantaggio che si rivela decisivo, soprattutto in tempo di guerra. Per esempio, durante la prima guerra mondiale, la violazione del Telegramma Zimmermann accelerò l'ingresso nel conflitto degli Stati Uniti d'America. Nella seconda guerra mondiale, la crittoanalisi dei cifrari tedeschi, inclusi la macchina Enigma e la cifrante di Lorenz, è a detta degli studiosi uno dei punti che hanno accorciato di alcuni mesi la fine del conflitto in Europa (vedi ULTRA). Anche gli Stati Uniti beneficiarono della crittanoalisi grazie al fatto che con essa poterono decifrare molte delle comunicazioni segrete dell'esercito giapponese, che venivano cifrate da una macchina chiamata PURPLE dagli americani (l'equivalente nipponico della tedesca Enigma).

I Governi dei Paesi hanno a lungo riconosciuto gli indubbi benefici della crittoanalisi nel campo dello spionaggio, sia militare che diplomatico, ed hanno istituito organizzazioni appositamente dedite a violare i codici e i cifrari di altre Nazioni, quali ad esempio il GCHQ inglese o l'NSA statunitense, organizzazioni che sono ancora attive oggi. Nel 2004 è stata divulgata la notizia che gli Stati Uniti d'America hanno violato i cifrari iraniani (anche se resta ignoto il fatto se sia stata usata solo crittoanalisi pura o anche altre tecniche meno ortodosse)^[3].

Descrizione ed utilizzo

La crittoanalisi di solito esclude metodi di attacco che non siano diretti alle debolezze intrinseche al metodo da violare, come ad esempio la corruzione, la coercizione fisica, il furto, l'ingegneria sociale. Questi tipi di attacco, spesso più produttivi della crittanalisi tradizionale, sono comunque un'importante alternativa alla crittanalisi.

Anche se il fine è sempre lo stesso, i metodi e le tecniche di crittanalisi sono drasticamente cambiati durante la storia della crittografia, adattandosi al continuo aumentare dell'efficienza della crittografia, iniziando dai metodi basati su carta e penna del passato, passando per le macchine crittografiche come l'Enigma della seconda guerra mondiale, per arrivare agli schemi basati sui computer del presente. Insieme sono cambiati anche i risultati della crittanalisi: non è più possibile ottenere un successo illimitato nella violazione dei codici e si stila perciò una graduatoria dei risultati conseguiti dagli attacchi. A metà degli anni settanta fu introdotta una nuova classe crittografica: la crittografia asimmetrica. I metodi per violare questa classe sono ben diversi da quelli utilizzati in passato e normalmente coinvolgono la risoluzione di problemi matematici altamente complessi, come la ben nota scomposizione in numeri primi.

Caratteristiche degli attacchi

Gli attacchi crittanalitici variano nella forza e nella capacità di rappresentare una minaccia per i crittosistemi del mondo reale. Una debolezza certificabile è un attacco teorico che è improbabile possa essere applicabile in una situazione reale; la maggioranza dei risultati ottenuti dalla moderna ricerca crittanalitica è di questo tipo. Essenzialmente l'importanza pratica di un attacco dipende dalle risposte alle seguenti domande:

quali conoscenza e capacità sono richieste come prerequisiti?
Quante informazioni segrete addizionali sono dedotte?
Quanto impegno è richiesto (vale a dire, qual è la complessità computazionale)?

Conoscenza primaria: scenari della crittanalisi

Gli attacchi possono essere classificati in base alla tipologia delle informazioni disponibili all'attaccante sul sistema da attaccare. Come base di partenza di solito si assume che, per gli scopi dell'analisi, l'algoritmo generale sia noto: questo è il principio di Kerckhoffs, il quale afferma che il nemico conosce il sistema. Il Principio di Kerckhoffs è un assunto ragionevole, dato che la storia riporta innumerevoli casi di algoritmi segreti ritenuti sicuri, rivelatisi violabili non appena divenuti di pubblico dominio, a causa ad esempio di spionaggio, tradimento e ingegneria inversa. (Occasionalmente i cifrari sono stati ricostruiti attraverso la semplice deduzione: ad esempio, i già citati cifrario di Lorenz e codice Purple, oltre ad una varietà di schemi classici).

Alcuni scenari tipici di attacco sono:

solo testo cifrato: l'attaccante ha accesso solo ad una collezione di testi cifrati.
Testo in chiaro noto: l'attaccante ha un insieme di testi cifrati dei quali conosce i corrispondenti testi in chiaro.
Testo in chiaro scelto (Testo cifrato scelto): l'attaccante può ottenere i testi cifrati (testi in chiaro) corrispondenti ad un insieme arbitrario di testi in chiaro (testi cifrati) di sua scelta.
Adattivo con testo in chiaro scelto: come per l'attacco con testo in chiaro scelto, eccetto che l'attaccante può scegliere sequenze di testo in chiaro basandosi su informazioni acquisite dall'analisi dei precedenti messaggi cifrati. Simile a questo è l'attacco adattivo con testo cifrato scelto.
Attacco correlato alla chiave: analogo all'attacco con testo in chiaro scelto, eccetto che l'attaccante può ottenere testi cifrati crittati con due differenti chiavi. Le chiavi sono ignote ma la relazione fra esse è nota: ad esempio, due chiavi che differiscono solo di 1 bit.

Questi tipi di attacco differiscono su quanto sia plausibile metterli in pratica. Anche se alcuni attacchi sono più probabili di altri, i crittografi affrontano spesso il problema della sicurezza con un approccio conservativo ed immaginano il peggiore dei casi quando progettano gli algoritmi, ragionando che se uno schema è sicuro anche contro le minacce irrealistiche allora dovrebbe resistere più che bene alla crittanalisi del mondo reale.

Le ipotesi sono spesso più realistiche di quanto si potrebbe immaginare a prima vista. Per un attacco con testo in chiaro noto, il crittanalista potrebbe conoscere, o essere in grado di entrarne in possesso, una parte del testo in chiaro, come ad esempio una lettera cifrata che inizia con "Egregio Signore" o una sessione su terminale che inizia con "LOGIN:". Un attacco con testo in chiaro scelto è meno probabile di altri attacchi ma è spesso plausibile: ad esempio, potreste convincere qualcuno a trasmettervi un messaggio che avete dato loro, ma in forma cifrata. Gli attacchi correlati alla chiave sono per lo più teorici, anche se possono essere molto realistici in alcune situazioni: ad esempio, quando viene utilizzato un cifrario a blocchi per realizzare una funzione di hash.

Classificazione dei successi in crittanalisi

I risultati della crittanalisi possono variare anche in utilità. Ad esempio, il crittografo Lars Knudsen (1998) classificò vari tipi di attacco ai cifrari a blocchi in base alla quantità e qualità delle informazioni segrete che venivano scoperte:

violazione totale: l'attaccante deduce la chiave segreta;
deduzione globale: l'attaccante scopre un algoritmo funzionalmente equivalente per la cifratura e la decifratura, ma senza conoscere la chiave;
deduzione locale: l'attaccante scopre testi in chiaro (o testi cifrati) addizionali non noti in precedenza;
deduzione dell'informazione: l'attaccante ottiene alcune informazioni di Shannon sui testi in chiaro (o sui testi cifrati) non note precedentemente;
algoritmo discriminante: l'attaccante può distinguere il cifrario da una permutazione casuale.

Simili considerazioni si applicano agli attacchi ad altri tipi di algoritmi crittografici.

Complessità

Gli attacchi possono anche essere caratterizzati dalla quantità di risorse che essi richiedono. Queste possono essere nella forma di:

Tempo: il numero di operazioni primitive che devono essere eseguite. Questo dato è abbastanza generico: le operazioni primitive potrebbero essere istruzioni di base del computer, come ad esempio addizioni, XOR, spostamenti di bit e così via, come interi metodi di cifratura;
Memoria: la quantità di spazio di memorizzazione richiesto per eseguire l'attacco.
Dati: la quantità di testi in chiaro e testi cifrati richiesti.

Spesso è difficile predire con precisione queste quantità. Nella crittografia accademica si tende almeno a fornire una stima dell'ordine di grandezza della difficoltà dell'attacco. Bruce Schneier nota che anche degli attacchi che siano impraticabili dal punto di vista computazionale possono essere considerati delle violazioni: "Forzare un cifrario significa semplicemente trovare una debolezza nello stesso che può essere sfruttata con una complessità minore della forza bruta. Non importa che la forza bruta richieda 2¹²⁸ cifrature: un attacco che richiedesse 2¹¹⁰ cifrature sarebbe considerato una violazione... in parole povere, una infrazione può essere semplicemente una debolezza certificabile: la prova che il cifrario non si comporta come previsto." (Schneier, 2000).

Crittanalisi della crittografia asimmetrica

La crittografia asimmetrica o crittografia a chiave pubblica è un tipo di crittografia che si basa sull'utilizzo di due chiavi, una privata ed una pubblica. Questi cifrari basano la loro sicurezza su problemi matematici di difficile soluzione, per cui un ovvio punto di attacco è sviluppare metodi per risolvere questi problemi. La sicurezza della crittografia asimmetrica a due chiavi dipende da questioni matematiche che in genere non sono tenute in considerazione dalla crittografia a singola chiave, e di conseguenza collega in nuovo modo la crittanalisi alla ricerca matematica.

Gli schemi asimmetrici sono progettati sulla difficoltà (congetturata) di risolvere vari problemi matematici. Se viene trovato un miglior algoritmo che può risolvere il problema, allora il sistema è indebolito. Per esempio, la sicurezza dello schema di scambio delle chiavi Diffie-Hellman dipende dalla difficoltà di calcolare un logaritmo discreto. Nel 1983 Don Coppersmith ideò un modo più veloce di trovare logaritmi discreti (in determinati gruppi), costringendo così i crittografi ad utilizzare gruppi più grandi (o tipi differenti di gruppi). La sicurezza dell'RSA dipende (in parte) dalla difficoltà della fattorizzazione di grandi numeri primi: un passo in avanti nel problema della fattorizzazione incrinerebbe la sicurezza dell'RSA.

Nel 1980 si poteva fattorizzare un numero a 50 cifre al costo di 10¹² operazioni elementari. Nel 1984 il progresso nell'arte della scrittura di algoritmi di fattorizzazione aveva raggiunto un punto tale che con le stesse operazioni si poteva fattorizzare un numero con 75 cifre. Inoltre l'avanzamento della tecnica permetteva di eseguire lo stesso numero di operazioni molto più velocemente. La legge di Moore predice che la velocità dei computer aumenterà costantemente: le tecniche di fattorizzazione faranno altrettanto, ma si baseranno anche sulla creatività e sull'intuizione matematiche, nessuna delle quali può essere predetta con successo. I numeri a 150 bit, utilizzati un tempo nell'RSA, sono stati fattorizzati: lo sforzo è stato superiore a quanto immaginato ma non è stato certo al di fuori della portata dei veloci e moderni computer. Difatti, all'inizio del XXI secolo, i numeri a 150 cifre non erano più considerati abbastanza lunghi per le chiavi RSA. I numeri con diverse centinaia di cifre sono ancora considerati difficili da fattorizzare, anche se i metodi probabilmente continueranno a migliorare nel tempo, richiedendo lunghezze delle chiavi capaci di reggere ai nuovi algoritmi che saranno utilizzati.

Un'altra caratteristica distintiva degli schemi asimmetrici è che, a differenza dei crittosistemi simmetrici, qualsiasi crittanalisi ha l'opportunità di fare uso delle conoscenze acquisite dalla chiave pubblica.

Applicazione dei computer quantici alla crittanalisi

I computer quantistici, che sono ancora nelle primissime fasi di sviluppo, sarebbero utilissimi nella crittanalisi. Ad esempio, l'algoritmo di Shor potrebbe fattorizzare grandi numeri in un tempo polinomiale, vale a dire in pratica che si potrebbero violare alcune forme di crittografia a chiave pubblica.

Utilizzando l'algoritmo di ricerca di Grover su un computer quantistico, la ricerca di una chiave con la forza bruta potrebbe essere eseguita con una velocità che è il quadrato di quella espressa dai normali computer. Ovviamente, ciò potrebbe essere contrastato incrementando la lunghezza della chiave.