Crittoanalisi

Da Wikipedia, l'enciclopedia libera.
La macchina per cifrare Lorenz-SZ42

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. Tipicamente si tratta di trovare una chiave segreta. 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. Anche se la crittanalisi di solito esclude metodi di attacco che non sono 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, ne sono comunque un'importante componente.

Anche se il fine è sempre lo stesso, i metodi e le tecniche di crittanalisi sono drasticamente cambiate 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.

Storia della crittanalisi[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi Storia della crittografia.

La crittanalisi si è evoluta di pari passo con la crittografia: nuovi cifrari venivano introdotti per rimpiazzare quelli violati, e nuove tecniche di crittanalisi venivano inventate per violare i nuovi schemi. In pratica, sono due facce della stessa medaglia: per poter creare una tecnica crittografica sicura bisogna pensarla capace di resistere alla crittanalisi.

Crittanalisi classica[modifica | modifica wikitesto]

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

Anche se la parola "crittanalisi" è relativamente recente (fu coniata 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: è lecito supporre che 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, l'automazione fu introdotta per la prima volta alla crittanalisi in quell'epoca 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 crittanalisi moderna[modifica | modifica wikitesto]

Replica di un calcolatore Bomba

La computazione 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 di prima. Considerata nel suo insieme, la moderna crittografia è divenuta molto più difficile da crittanalizzare con i sistemi penna-e-carta del passato, tanto che alla fine sta lentamente prendendo il sopravvento sulla crittanalisi pura.

Lo storico David Kahn afferma che "i crittosistemi offerti oggigiorno dalle centinaia di venditori in circolazione che non possono essere violati da nessuno dei metodi noti di crittanalisi sono molti. 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].

I risultati della crittanalisi[modifica | modifica wikitesto]

Il Telegramma Zimmermann decifrato.

Diverse volte i successi della crittanalisi 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 crittanalisi dei cifrari tedeschi, inclusi la macchina Enigma ed il cifrario 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 crittanalisi 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 crittanalisi nel campo dello spionaggio, sia militare che diplomatico, ed hanno stabilito organizzazioni appositamente votate alla cifratura dei codici e dei 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 che sia stata usata solo crittanalisi pura o anche altre tecniche meno ortodosse)[3].

Caratterizzazione degli attacchi[modifica | modifica wikitesto]

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:

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

Conoscenza primaria: scenari della crittanalisi[modifica | modifica wikitesto]

La crittanalisi può essere condotta su un numero di assunti riguardanti quanto può essere osservato o scovato sul sistema da attaccare. Come base di partenza di solito si assume che, per gli scopi dell'analisi, l'algoritmo generale è 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).

Altri assunti 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: come per l'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 correlato 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[modifica | modifica wikitesto]

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à[modifica | modifica wikitesto]

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.

Nella crittografia accademica una debolezza o una rottura in uno schema è di solito definita in maniera abbastanza conservativa. Bruce Schneier riassumendo questo approccio: "Rompere un cifrario significa semplicemente trovare una debolezza nello stesso che può essere sfruttata con una complessità minore della forza bruta. Non importa che forza bruta richieda 2128 cifrature: un attacco che richiedesse 2110 cifrature sarebbe considerato una rottura... in parole povere, una rottura 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 tutta 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 la crittanalisi alla ricerca matematica in una nuova maniera.

Gli schemi asimmetrici sono disegnati 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 1012 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[modifica | modifica wikitesto]

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.

Tecniche di crittanalisi[modifica | modifica wikitesto]

Crittanalisi classica:

Algoritmi simmetrici:

Funzioni di hash:

Modelli di attacco:

Attacchi del canale laterale:

Attacchi alle reti:

Attacchi esterni:

Voci correlate[modifica | modifica wikitesto]

Generale[modifica | modifica wikitesto]

Crittanalisti storici[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Note[modifica | modifica wikitesto]

  1. ^ Annotazioni sul 50º anniversario della National Security Agency, 01/11/2002
  2. ^ Come violare una connessione WEP in meno di un minuto
  3. ^ Violazione dei codici iraniani

Bibliografia[modifica | modifica wikitesto]