PROGRAMMIAMO
File - Crittoanalisi
Crittoanalisi

Col termine crittoanalisi si intende l'analisi di un testo cifrato nel tentativo di decodificarlo, pur non conoscendo l'algoritmo e/o la chiave di decifratura. La crittoanalisi è in sostanza l'altra faccia della crittografia e viene usata da coloro che cercano di "rompere" un codice segreto (break a code) ovvero di "violare" il cifrario: per esempio i nemici che intercettano i messaggi inviati.

Prendiamo come esempio nuovamente il cifrario di Cesare di cui abbiamo parlato nella lezione precedente.

Metodo della forza bruta

Se il crittoanalista sa che il messaggio è stato cifrato col cifrario di Cesare, esso può facilmente decifrarlo anche senza conoscerne la chiave. Infatti, considerando le lettere dell'alfabeto inglese, ci sono solo 26 trasposizioni possibili. In pratica il valore massimo della chiave che è possibile usare è 26. Infatti per esempio usare una chiave di cifratura pari a 27, equivale a sommare a ogni carattere la chiave 1 (dal momento che le lettere dell'alfabeto vengono considerate ciclicamente).

In termini matematici, se x è il carattere da cifrare e s è la chiave, il carattere cifrato En(x) è dato da:

 

dove mod 26 è l'operazione di resto della divisione intera per 26. Per esempio, cifrando la lettera C con chiave 4 si ottiene:

En(C) = (3 + 4) mod 26 = 7 mod 26 = 7 → G

Se usassimo come chiave il numero 30 (26 + 4), il risultato precedente non cambierebbe in quanto il resto della divisione intera di 30 diviso 26 è sempre 7 (che corrisponde alla lettera G):

En(C) = (3 + 30) mod 26 = 33 mod 26 = 7  → G

In pratica, se si sa in partenza che il testo è criptato col cifrario di Cesare, è sufficiente fare al massimo 26 prove (26 trasposizioni) per indovinare il testo nascosto (se si usa il cifrario di Cesare con i codici ASCII dei caratteri, il numero di tentativi necessari aumenta, ma il concetto è lo stesso). In realtà, siccome la chiave 26 equivale a non cifrare il messaggio, il numero di tentativi possibili è solo 25.

Questo metodo di decifrazione viene detto della forza bruta (brute force). In pratica si provano tutte le possibili sostituzioni di caratteri, finché non si indovina quella giusta. Siccome ci sono al massimo 25 possibilità diverse (tante quante le lettere dell'alfabeto inglese meno uno, dato che la chiave 26 non cifra il messaggio) il calcolo è davvero semplice.

Ai tempi di Giulio Cesare il metodo era ritenuto abbastanza sicuro, in quando la maggior parte delle persone non sapeva neppure leggere, né tanto meno aveva idea dell'esistenza di cifrari o di tecniche di crittoanalisi.  Al giorno d'oggi l'uso dei computer (in grado di fare un grande numero di tentativi in tempi brevissimi) rende questo tipo di cifrario assolutamente inutilizzabile.  

Di solito il metodo della forza bruta è l'ultima risorsa impiegata per forzare un codice, in quanto richiede generalmente un numero molto grande di tentativi (almeno con i metodi di cifratura moderni). Un parametro critico per l'applicabilità di un attacco a forza bruta è la lunghezza della chiave utilizzata: infatti più lunga è la chiave, maggiore è il numero di tentativi necessari per indovinarla.

 

Analisi in frequenza

I cifrari che usano le sostituzioni di caratteri (come il cifrario di Cesare e quello per sostituzione) sono facilmente attaccabili mediante un'analisi in frequenza. Se chi cerca di decifrare il testo non sa con quale chiave è stato cifrato il testo, esso può comunque tentare di indovinare il testo in chiaro, a condizione di conoscere la lingua in cui è stato scritto.

Infatti in ogni lingua ogni lettera ha in media una certa frequenza. Per esempio in italiano le lettere più frequenti sono la A e la E, che compaiono in media con una frequenza del 12%. In generale le lettere più usate sono le vocali, mentre le consonanti sono meno frequenti (la Z per esempio ha una frequenza solo dello 0,5%). La figura seguente mostra per esempio la distribuzione in frequenza delle lettere dell'alfabeto italiano nel primo capitolo dei Promessi Sposi:

Usando un'analisi della frequenza con cui si ripetono i vari simboli nel testo cifrato, il crittoanalista può dunque cercare di indovinare a quale lettera corrisponda ogni simbolo. Ciò vale in particolare se il testo cifrato è abbastanza lungo, poiché su testi breve le frequenze delle lettere potrebbero anche essere molto diverse da quelle medie della lingua - si pensi ad esempio al testo:

DA ZANZIBAR ALLO ZAMBIA LA SCARSEZZA DI OZONO SPINGE LE ZEBRE A ZIGZAGARE BIZZARRAMENTE

In questo caso la lettera Z è la più frequente e dunque ciò potrebbe confondere l'analisi in frequenza.

Se il crittoanalista non conosce la lingua in cui è stato scritto il testo, può ugualmente scoprirla analizzando la frequenza con cui compaiono i diversi simboli e confrontando tali frequenze con quelle delle varie lingue (sempre a condizione che il messaggio sia abbastanza lungo).

Per rendere più complessa l'analisi in frequenza, sono stati inventati dei cifrari in cui vengono inserite, in posizioni casuali, le cosiddette nulle. In pratica si tratta di simboli a cui non corrisponde nessun simbolo in chiaro, ma che vengono usati solo per confondere il testo e renderne difficile l'analisi in frequenza. Per esempio cifrando un testo in lingua italiana, potremmo sfruttare il fatto che alcune lettere (J, W, X, Y) non sono presenti nella nostra lingua. In pratica, usando un cifrario per sostituzione, possiamo lasciare inutilizzate 4 lettere qualsiasi e usare queste quattro lettere come nulle per confondere il messaggio.

Un'altra tecnica usata per rendere difficile l'analisi in frequenza del testo è quella di sostituire ogni simbolo del testo in chiaro non con un solo simbolo, ma con uno fra un gruppo di simboli diversi. Per esempio, supponendo di cifrare un messaggio associando a ogni lettera un numero intero da 0 a 100, una sostituzione semplice potrebbe usare un solo numero di cifratura in corrispondenza di ogni lettera:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
21 72 43 11 76 90 3 71 9 1 99 17 22 19 33 62 4 98 29 0 77 8 31 91 18 74

Questo tipo di sostituzione è facilmente attaccabile con l'analisi in frequenza, poiché i simboli più probabili (il numero 21 che corrisponde alla A e il numero 76 che corrisponde alla E) si presentano con una frequenza maggiore. Possiamo però cercare di confondere le idee all'attaccante usando più numeri diversi per cifrare i caratteri più probabili e scegliendo (a caso) uno fra i numeri possibili quando cifriamo. Si consideri l'esempio seguente (incompleto) nel quale le lettere più frequenti vengono cifrate usando uno a scelta fra più simboli diversi:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
21 72 43 11 76 90 3 71 9 1 99 17 22 19 33 62 4 98 29 0 77 8 31 91 18 74
88       13       10                                  
90       25       55                                  

 

Attacco con dizionario

L'attacco per mezzo di un dizionario cerca di indovinare la chiave di cifratura (o la password di un sistema di sicurezza) usando elenchi di parole chiave e di password comunemente usati.

In contrasto con un metodo forza bruta, dove tutte le possibili combinazioni sono provate, un attacco a dizionario prova solamente quelle ritenute più probabili, tipicamente contenute in una lista (detta dizionario). Generalmente, questi attacchi hanno successo perché la maggior parte delle persone ha la tendenza a scegliere password o chiavi di cifratura semplici da ricordare (e quindi semplici da scoprire: ad esempio il proprio nome, quello dei propri figli, date di nascita) e tendenzialmente sceglie parole prese dalla propria lingua nativa.

I dizionari, che sono normalmente semplici file composti da sequenze di parole divise da caratteri separatori, possono riferirsi a contenuti standard (dizionario della lingua inglese, della lingua italiana, dizionario dei nomi, ecc.) oppure essere creati appositamente a seconda del contesto di utilizzo.

E' ovviamente più efficiente del metodo della forza bruta, ma ha lo svantaggio che, se il dizionario non contiene la chiave, non sarà possibile indovinarla.

 

Attacco man-in-the-middle

In un attacco man-in-the-middle (abbreviato in MIM e traducibile in italiano con "uomo nel mezzo") l'attaccante è in grado di intercettare tutte le comunicazioni che avvengono fra le due parti comunicanti. Caratteristica di questo tipo di attacco è il non permettere che nessuna delle due sia in grado di sapere se il collegamento che li unisce reciprocamente sia stato effettivamente compromesso da una terza parte, ovvero appunto un attaccante. L'attaccante così è in grado di osservare, intercettare e replicare verso la destinazione prestabilita il transito dei messaggi tra le due vittime.

L'attacco man-in-the-middle è particolarmente efficace se intercetta lo scambio delle chiavi di cifratura fra le due parti (poiché in questo caso l'attaccante viene in possesso della chiave di cifratura).


Sicurezza di un sistema di cifratura

In generale un sistema di cifratura viene detto computazionalmente sicuro se il testo cifrato soddisfa uno dei seguenti criteri:

In generale un algoritmo si dice sicuro (o anche "non rotto") se l'attacco più efficace contro di esso è un attacco a forza bruta, cioè che consiste nel provare tutte le possibili chiavi. In questo caso la sicurezza dell'algoritmo dipende evidentemente dalla bontà della chiave scelta (es. chiavi lunghe sono più difficili da indovinare di chiavi brevi).

 

precedente - successiva

Sito realizzato in base al template offerto da

http://www.graphixmania.it