One Time Pads

From UIC

One Time Pads

Infos
Author:	quequero
Email:
Website:	http://quequero.org
Date:	21/04/2007 (dd/mm/yyyy)
Level:
Language:	Italian
Comments:	Non sono pigro, ho solo un'alta energia di attivazione...

Introduzione

Nel corso di questo articolo illustrerò il funzionamento degli OTP e principalmente quali sono i pericoli associati al riutilizzo del keystream. Questo secondo punto sarà il cardine dell'articolo poiché nella letteratura tradizionale si parla sempre di non-riutilizzo, ma mai se ne mostrano i rischi concreti.
Infine, per rendere il gioco più interessante, ho creato una piccola sfida con cui potrete cimentarvi dopo aver letto questo paper, ed il premio sono sicuro che vi piacerà.

Tools & Files

• OTP - OTP Encrypter/Decrypted
• OTP Bruteforcer - Programma per il bruteforcing degli OTP
• Messaggi Cifrati - I messaggi che decifreremo nel corso del paper
• Wordlist - Una wordlist con tutte le parole italiane
• Final Challenge - Il gioco a premi, risolvetelo e come ricompensa otterrete...
• Una calcolatrice capace di calcolare lo Xor

One Time Pads

OTP è l'acronimo che identifica i One Time Pads (o blocchi mono-uso se preferite l'italiano), si tratta essenzialmente di un cifrario di Vernam, il cui funzionamento è semplice: si genera una chiave casuale lunga quanto il testo da cifrare, e poi si xora questa chiave con il testo. Il ricevente, grazie alle proprietà dello Xor, non dovrà far altro che xorare la stessa chiave col blocco cifrato per riottenere il testo. Il procedimento è assolutamente identico a quello adottato nella cifratura con RC4, ovvero:

1. Definiamo come K un byte della chiave.
2. Definiamo come P un byte del testo da cifrare (plaintext).
3. Definiamo come C un byte del test cifrato (ciphertext).

La cifratura avviene in questo modo:

• P ^ K = C

E l'operazione inversa sarà ovviamente:

• C ^ K = P

Quindi nulla di nuovo, stiamo semplicemente applicando la proprietà commutativa dello xor. Per quanto semplice possa sembrare, sappiate che questo genere di cifrari è l'unico che è stato matematicamente dimostrato¹ come sicuro, per la precisione fu il grande Shannon a pubblicarne nel 1948 la dimostrazione nel suo A mathematical theory of communication. Si, anche RSA è sicuro, il problema è che con un computer potente è sempre possibile fattorizzare la chiave, e non è detto che in futuro non si scopra un algoritmo in grado di scomporre un numero in fattori primi. Nel caso degli OTP il discorso è diverso, non importa infatti la potenza del computer perché il testo cifrato non espone assolutamente nulla del testo in chiaro, e poi ad ogni keystream corrisponde un plain-text differente. L'ulteriore vantaggio è che non sarà possibile distinguere una trasmissione di dati random dalla trasmissione di un flusso cifrato con un OTP... A differenza di quanto abbiamo visto con RC4.

Keystream Reuse

Abbiamo detto che la chiave per la cifratura deve essere necessariamente casuale, se non fosse casuale... Significherebbe che si tratta di una sequenza predicibile, oppure biased in modo identificabile, per cui sarebbe semplice risalire al keystream, e da lì al contenuto in chiaro (parleremo di questo nella crittanalisi della funzione random()). La generazione di una chiave random non è un problema banale, qualunque sistema software difficilmente sarà in grado di produrre una distribuzione univoca ed uniforme, se non supportata da un apposito impianto di generazione hardware. Ma anche l'impianto di generazione hardware potrebbe non essere affidabile, fino a pochi anni fa, ed a volte anche oggi, si consigliava di utilizzare come sorgente di rumore bianco l'ingresso di una presa microfonica, senza il microfono inserito. Si tratta di una scelta pessima perché quel genere di rumore è semplice da modellare e prevedere, per cui la qualità della chiave ottenuta con questi metodi è bassissima. Attualmente possiamo generare una chiave realmente casuale soltanto in due modi:

1. Utilizzando una sorgente radioattiva, e misurando accuratamente il tempo tra due eventi di decadimento (tramite un contatore Geiger ad esempio).
2. Sparando un fotone su uno specchio semi-trasparente e vedendo se viene riflettuto o se attraversa lo specchio.

Il secondo metodo è estremamente accurato, ed esistono in commercio svariate schede PCI (che costano però abbastanza, dai 600$ in su) per generare numeri random ad alta velocità, tuttavia non utilizzano la tecnologia a singolo fotone, ma ne sparano un fascio e fanno la media sui sensori... Non è il massimo, ma la qualità dello stream ottenuta è comunque buona. Tutte le altre sorgenti di rumore, inclusi i generatori presenti sulle schede madri (che sono a tutti gli effetti dei sensori termici), sono in varia misura sempre abbastanza predicibili, ed in crittografia anche una predicibilità minima può compromettere seriamente qualunque algoritmo.
Detto questo, e supponendo di avere uno stream effettivamente casuale (potete usare /dev/random se non disponete di un generatore hardware), vediamo cosa succede se cifriamo due differenti messaggi con la stessa chiave:

• C₁ = K ^ P₁
• C₂ = K ^ P₂

Spostiamo K al primo membro da entrambe le equazioni:

• K = C₁ ^ P₁
• K = C₂ ^ P₂

E quindi proviamo a ricavarlo:

• C₁ ^ P₁ = C₂ ^ P₂

Guardate cosa succede:

• C₁ ^ C₂ = P₁ ^ P₂

Interessante! Se effettuiamo lo xor dei due testi cifrati, otteniamo lo xor dei due testi in chiaro. Ecco, qui è dove si fermano tutti quelli che parlano di OTP, ma vi dovreste chiedere: anche avendo lo xor dei due testi, cosa ci facciamo?

NSA vs KGB

Durante la guerra fredda le truppe Russe (probabilmente memori del fallimento di Enigma) scambiavano messaggi in questo modo: il messaggio veniva cifrato con un cifrario a sostituzione ed il risultato veniva di nuovo cifrato con un OTP. Veniva fornito agli operatori un libro contenente la soluzione del cifrario a sostituzione, ed un libro contenente una serie di caratteri casuali (in verità non erano il massimo della casualità, visto che venivano generati da una serie di operatori che pigiavano alla rinfusa su delle macchine da scrivere) che utilizzavano come chiave in maniera incrementale. La stragrande maggioranza di questi messaggi non venne mai decifrata dalla NSA (o meglio dal team del progetto Venona), nonostante la distribuzione dei byte della chiave non fosse realmente uniforme, tuttavia in alcuni casi ci riuscirono, ma come? Principalmente a causa dell'incuria degli operatori che reagivano in maniera errata alle richieste di ritrasmissione o che, semplicemente, riutilizzavano più volte la stessa chiave. C'e' da dire che le tecniche per risalire ad ogni singolo plain-text sono tutt'ora classificate, per cui non sappiamo cosa venisse effettivamente utilizzato per la crittanalisi dei messaggi. Ma poco importa, studieremo un nostro metodo e vedremo che ne esistono di altamente efficienti.

Crittanalisi

Abbiamo visto che xorare due messaggi cifrati con la stessa chiave porta, come risultato, ad avere i due plain-text cifrati tra loro, ma lo stesso principio vale se abbiamo n messaggi cifrati con la stessa chiave, quindi:

• C₁ ^ C₂... ^ C_n = P₁ ^ P₂... ^ P_n

Ed è abbastanza immediato capire che più sono i messaggi a nostra disposizione, più è semplice la fase di crittanalisi. Supponendo infatti di avere un messaggio cifrato, avremo una probabilità di 1/256 che pescando un carattere casuale e xorandolo col messaggio, otterremo il byte originale. Ma abbiamo la stessa probabilità anche sul secondo, terzo ed n-esimo carattere, quindi si tratta di una pesca decisamente complessa. La situazione non sembra cambiare molto nel caso si abbiano due messaggi cifrati con la stessa chiave, la probabilità che pescando un byte casuale, otterremo il byte originale, è sempre la stessa, ma con un bel vantaggio: se il byte pescato è quello giusto, otterremo non uno ma ben due byte di plain-text. Analogamente per n messaggi cifrati otterremo n byte di plain-text per ogni byte di chiave pescato bene. Ecco quindi che si apre uno spiraglio.
A questo punto possiamo fare una supposizione: il messaggio in chiaro sarà pur scritto in una lingua, quindi possiamo applicare al messaggio P₁ ^ P₂ ^ P_n le stesse procedure di analisi che applicheremmo ad un testo normale. Questa assunzione è abbastanza verosimile, perché se spiamo un avversario sappiamo anche il "tipo" di messaggi che lui invierà, ma vedremo a breve che gli stessi principi si applicano a qualunque distribuzione di dati non uniforme.

Decifriamo un Messaggio

Qui sotto troviamo due messaggi cifrati con la stessa chiave, sono gli stessi che trovate nel file: Messaggi Cifrati, chiaramente i byte che vedete qui sotto sono il corrispondente esadecimale di ogni carattere, visto che la maggior parte non sono stampabili:

La prima cosa che faremo sarà quella di xorare tra loro i due messaggi, in modo da ottenere, come risultato, lo xor dei due plain-text, da ora in poi il file risultante verrà chiamato: file finale. Per far questo useremo OTP, un piccolo programma che ho scritto appositamente per questo paper, compilatelo se siete su Linux (ci sono le istruzioni all'interno), oppure utilizzate l'exe se siete su Windows:

ed otterrete questo:

A questo punto una piccola digressione è necessaria...

Un po' di Statistica

Se eseguiamo un'analisi statistica su un testo italiano, possiamo vedere che alcune lettere appaiono con frequenza maggiore di altre, e questo vale anche per alcuni digrammi/trigrammi. Quella che vedete qui sotto è una tabella con le frequenze relative di tutte le lettere dell'alfabeto, se i punteggi differiscono di qualche decimo da quelli che trovate sul vostro libro di statistica non fateci caso, ho ricalcolato le frequenze utilizzando una serie di testi stilisticamente differenti (trattati storici, romanzi, testi di legge etc...). Non mi sono basato, come spesso si fa, sull'analisi di un singolo romanzo/opera, perché per mille motivi possono esserci dei bias dovuti allo stile dell'autore.

Le prime 4 lettere sono delle vocali e si distribuiscono in maniera uniforme tra loro, quindi non possiamo identificare una lettera predominante nella lingua italiana, come invece accade, ad esempio, per l'inglese con la lettera E. È da notare l'assenza delle lettere Y, K, W, X e J che sono presenti esclusivamente nei nomi di persone/località per lo più straniere. Passiamo ora all'analisi dei digrammi:

In questo caso il digramma ON spicca decisamente sugli altri, mentre tutte le altre coppie appaiono con frequenze molto simili tra loro. Passiamo ai trigrammi:

E quindi passiamo ai tetragrammi, visto che ci saranno comunque molto utili:

Il Grande Assente

Ma forse dovremmo notare l'assenza di qualcuno, ovvero lui: . Non lo vedete?
Giusto è invisibile, forse se faccio così ci riuscite, lui: ' '. Ora dovreste vederlo, si trova tra due apici... Bravi! È proprio lui, lo spazio! Si perché il suo ruolo è fondamentale, in tutte le lingue con alfabeto latino è infatti il carattere più presente, molto più presente delle vocali, appare all'incirca con una frequenza doppia rispetto alla lettera più usata. Per cui forse è il caso di introdurre le relative tabelle dove è incluso anche lui, ci tornerà ugualmente utile. Salteremo quella delle singole lettere perché abbiamo già detto qual'e' la sua frequenza, e partiremo dai digrammi, lo spazio è rappresentato da un punto:

Procediamo con i trigrammi:

I tetragrammi utili sono invece di meno:

All'attacco!

Digressione terminata, è tempo di tornare a noi! Date le statistiche appena riportate, possiamo fare delle assunzioni abbastanza importanti sulla natura dei messaggi che stiamo per esaminare. Per prima cosa sappiamo che lo spazio è il carattere predominante, per cui ogni volta che nel file finale troveremo uno 0, potremo assumere che si tratti, con maggior probabilità rispetto agli altri casi, di uno spazio in quella posizione in entrambi i plain-text. La seconda assunzione è anch'essa interessante: sappiamo che le lettere maiuscole possono assumere valori esadecimali che vanno da 0x41 (la A) a 0x5A (la Z), e sappiamo che lo spazio equivale a 0x20, xoriamo questi due valori con lo spazio:

• 0x41 ^ 0x20 = 0x61 (corrisponde al carattere: a)
• 0x5A ^ 0x20 = 0x7A (corrisponde al carattere: z)

Adesso eseguiamo lo xor tra la Z e la A:

• 0x5A ^ 0x41 = 0x1B

Il primo teorema degli spazi

Per la linearità dello xor possiamo quindi affermare che:

Teorema 1: una lettera maiuscola xorata con uno spazio, non può essere uguale a nessuna coppia di lettere maiuscole xorate tra loro.

Percio' se siamo in grado di identificare la posizione di una lettera maiuscola in un plain-text, siamo anche in grado di trovare lo spazio corrispondente nell'altro plain-text, senza contare che se il messaggio è inviato tutto in caratteri maiuscoli, allora abbiamo appena trovato un modo di isolare tutti gli spazi. Basterà cercare tutti i byte maggiori o uguali a 0x61 (a) e tutti i byte minori o uguale a 0x7A (z).

Il secondo teorema degli spazi

A ben guardare forse possiamo estendere il nostro teorema anche ai caratteri minuscoli, facciamo una dimostrazione:

• 0x61 ^ 0x20 = 0x41 (corrisponde al carattere: A)
• 0x7A ^ 0x20 = 0x5A (corrisponde al carattere: Z)

Adesso eseguiamo lo xor tra la z e la a:

• 0x7A ^ 0x61 = 0x1B

Passiamo quindi alla definizione del secondo teorema:

Teorema 2: una lettera minuscola xorata con uno spazio, non può essere uguale a nessuna coppia di lettere minuscole xorate tra loro.

Ecco quindi che siamo in grado di identificare gli spazi anche in un messaggio inviato in caratteri minuscoli. Semplificando vuol dire che quando nel file finale troveremo un carattere maiuscolo, potremo dire con certezza che si tratta di un carattere minuscolo in un plain-text, e di uno spazio nell'altro plain-text. Niente male! Certo, non abbiamo considerato la distribuzione della punteggiatura, ma quella la estrapoleremo dal contesto.

Fase 1

Prendiamo i primi 4 byte del file finale (ma possiamo iniziare da dovunque), troviamo soltanto 2 caratteri stampabili e si tratta di lettere maiuscole, quindi per il secondo teorema degli spazi, possiamo affermare che ognuno di questi caratteri è uno spazio:

non possiamo fare assunzioni sul primo carattere, cioe' non possiamo sapere se è minuscolo o meno, perché i due messaggi cifrati li ho presi casualmente da una serie di messaggi che avevo creato. Quindi neanche io so di cosa si tratti, ed in particolare non tutti i messaggi iniziavano con un carattere maiuscolo. L'unica assunzione che per il momento possiamo fare, è che il secondo e terzo byte difficilmente saranno due spazi consecutivi nello stesso messaggio, ma probabilmente si tratta di uno spazio nel file A e di uno spazio nel file B, in sostanza i messaggi si possono presentare in queste varianti:

Partiamo testando il caso 1. per il file A, e logicamente il caso 1. per il file B, perché non possiamo avere due volte la stessa configurazione, visto che spazio ^ spazio = 0, e noi non abbiamo zeri. Utilizzando la tabella della frequenza vediamo qual'e' il carattere singolo più frequente nella nostra lingua: la I. Assumiamo che sia maiuscola visto che si tratta della prima lettera, e scopriamo cosa viene fuori dal file A:

• 0x05 ^ 0x49 = 0x4C (L)

Abbiamo quindi ottenuto il primo byte del file A ed il primo del file B... Sempre che siano giusti ovviamente. Iniziamo a sostituirli e vediamo cosa viene fuori:

Ma a questo punto possiamo verificare la nostra ipotesi in maniera semplice, dal momento che certamente il secondo byte del file A è uno spazio... Allora possiamo ricavare anche il secondo byte del file B:

• 0x20 ^ 0x41 = 0x61 (0x41 è il secondo byte del file finale)

Quindi abbiamo:

Che in italiano potrebbe anche suonare bene. Non possiamo sapere a priori se realmente i primi due caratteri siano maiuscoli o minuscoli, ma questo non ci interessa perché non ci crea problemi se entrambi hanno lo stesso case. Avremmo invece avuto problemi nel caso in cui il primo carattere di A fosse stato maiuscolo e il primo di B minuscolo, o vice versa. Ma adesso possiamo ricavare, con lo stesso procedimento, anche il terzo byte del file A:

• 0x53 ^ 0x20 = 0x73 (s)

Risultato:

Fase 2

Ora proviamo a spostarci un po' avanti nel file, e vediamo se riusciamo a scoprire la fine della parola dopo "I ", o la fine della parola dopo "La ", potrebbe tornarci davvero utile. Spostiamoci al nono byte, ovvero dove troviamo un secondo probabile spazio. Le configurazioni possibili sono le seguenti:

Proviamo ad attaccare la prima parola del file B usando la tabella dei trigrammi senza gli spazi, vediamo infatti che il trigramma più comune che inizia con la S è STA, la s già la conosciamo, per cui proviamo a xorare le lettere TA sul file B facendo finta che la parola in A sia "sta...".

Niente, possiamo eliminare il trigramma STA perché la soluzione sembra poco plausibile. Proviamo con un altro approccio, nella lingua italiana possiamo fare l'assunzione sensata che ogni parola, più lunga di 3 lettere, finisce quasi sempre con una vocale. Prendiamo nuovamente la tabella delle frequenze, prendiamo il Caso 2 e supponiamo che l'ultima lettera della seconda parola sia una i, poi proveremo la e etc...

Giunti a questo punto abbiamo bisogno di un computer per velocizzare la nostra ricerca, cercheremo ora di ricavare la seconda parola del file A, e qualche byte successivo, partendo dalla seconda parola del file B con una sorta di bruteforce. Utilizzeremo OTP Bruteforcer una piccola utility che ho scritto per questo paper, il programma prende in input un file cifrato ed una lista di parole, xora ogni parola con il file cifrato, e se il risultato è scritto in caratteri stampabili, lo mostra a schermo. Potrebbe essere una buona idea quella di installare MinGW se siete su windows, in modo da avere a portata di mano utility indispensabili come less e grep. Scompattiamo quindi la wordlist italiana e creiamo un piccolo file, contenente soltanto i byte del file finale che vanno dal quarto al tredicesimo:

Chiamiamolo cipher.bin, quindi da riga di comando richiamiamo il bruteforcer:

Ci penserà il programma ad utilizzare soltanto le parole della giusta lunghezza. Guardiamo ora l'output perché troveremo una serie di stringhe, quasi tutte inutili ad eccezione di una:

Sappiamo che la prima lettera è la s perché l'avevamo scoperta già prima, quindi gli unici risultati utili sono: "sistemi in" per il file A e "richiesta" per il file B. Il che ci porta in questa situazione:

Lo spazietto dopo la seconda parola nel file B è abbastanza certo, per cui scopriamo un ulteriore byte:

Ma ora ci troviamo di fronte ad una piccola ambiguità, i byte 20 e 21 sono entrambi degli spazi, tuttavia non conosciamo la lunghezza esatta né della parola del file A né della parola del file B... Come facciamo? Faremo un paio di tentativi ancora con l'OTP Bruteforcer, tanto sappiamo che il primo spazio appartiene al primo o al secondo file, per cui la parola che cerchiamo avrà al massimo due forme:

Ma la radice inf- ci dice tanto, quindi potremo escludere molti casi. Terremo cifrata anche la radice, tra poco vedremo perché, ora creiamo nuovamente il nostro cipher.bin:

E bruteforziamo come prima, ma questa volta grepperemo tutte le parole che iniziano per inf- dal momento che siamo certi della presenza di questa particella... Ok non viene fuori niente, forse lo spazio che abbiamo incontrato è parte del secondo file e non del primo, quindi aggiungiamolo al nostro file cipher.bin

E ripetiamo il bruteforce:

Cool! l'abbiamo trovato! A questo punto possiamo ampliare ancora di più i nostri plain-text, e poi il testo ottenuto per il file A è un byte più lungo rispetto a quello ottenuto per il file B, per cui possiamo ricavare un nuovo byte per B dal byte supplementare in A:

Adesso le cose si complicano un pochino, se guardiamo ai byte successivi vediamo infatti che c'è un byte a 0x00, questo vuol dire che nel plain-text sono presenti due byte uguali, ma quali? Statisticamente si tratterà o di uno spazio o di una vocale... Ma se siamo sfortunati potrebbe trattarsi anche di un segno di punteggiatura. Supporre che si tratti di uno spazio potrebbe non essere errato perché nel file B la frase suggerisce poche alternative, la parola composta dalla a potrebbe essere: "a ", "ai ", "al ", "alle " etc... Quindi usiamo la statistica e supponiamo che quel byte a zero sia effettivamente lo xor di due spazi tra loro, ora dobbiamo scoprire da cosa è seguita la particella "a", potrebbe essere: "ai " oppure "al ", ma visto che la i è più comune della l, proviamo con questa e vediamo cosa otteniamo:

Direi di no, proviamo con "al":

Ok funziona, ora dobbiamo scoprire un byte sconosciuto e quindi dobbiamo trovare in quale dei due plain-text si trova lo spazio che segue la lettera. Senza dubbio deve appartenere al primo file perché qualcosa nella forma: "La richiesta rivolta ai a/e/i/o/u xxxxx" ha poco senso, sostituendo lo spazio otteniamo:

supponiamo di nuovo che il byte incognito nel file A sia una i, anche perché è difficile che si tratti di altro, otteniamo:

Forse possiamo ottenere un bel po' di byte, "for free" grazie al bruteforcer, abbiamo davanti a noi un altro spazio sicuro, ma abbiamo anche un byte a 0x00, speriamo non si tratti di nuovo di uno spazio, altrimenti dovremo tornare indietro. Creiamo un nuovo cipher.bin e dentro mettiamo i byte cifrati fino allo spazio:

Bruteforziamo e greppiamo tutte le stringhe che iniziano per "ti" (in verità grepperemo tutte le stringhe che contengono la sillaba "ti" per evitare di utilizzare script come awk che magari non avete installati).

Anche questa è trovata sostituiamo ai nostri plaintext:

Senza neanche dirlo, completiamo l'ultima parola del primo file:

Ora abbiamo nuovamente a che fare con uno spazio che molto probabilmente apparterrà al secondo file, sostituiamolo e scopriamo anche una nuova lettera, ma ci resta da scoprire la particella "ax" a cosa corrisponde. Non può trattarsi di "ai" perché altrimenti l'ultima parola del primo plain-text sarebbe: "ln....", quindi proviamo con "al":

Abbiamo di fronte una parola lunga almeno 11 caratteri nel file A, ma forse anche 14, quindi mettiamo mano al bruteforcer:

Niente male di nuovo, completiamo anche la parola del file B, verranno fuori altre parole, continuiamo a completarle fin dove possiamo e vediamo cosa ne esce:

Adesso sorge un problema, la parola "pux" potrebbe essere completata con una o con accento grave o acuto (un errore può sempre esserci). Ma abbiamo la certezza di uno spazio, quindi sostituiamolo e sostituiamo anche la "o" con accento corretto, ovvero quello grave (byte: 0xF2):

Abbiamo ancora una volta un'indecisione, la parola del file A potrebbe essere lunga sia 8 caratteri sia 11, perché abbiamo due spazi e non sappiamo quale dobbiamo utilizzare. Creiamo di nuovo il cipher.bin:

ma stavolta diremo al bruteforcer di mostrare tutti i caratteri alfanumerici, visto che è presente anche una lettera "speciale", ovvero la "ò":

Il punto iniziale è la "ò" che non viene mostrata, sostituiamo di nuovo e vediamo cosa è venuto fuori:

Ripetendo lo stesso procedimento per tutto il resto del file, ed utilizzando l'opzione "-A" del bruteforcer quando abbiamo a che fare con la punteggiatura, otteniamo finalmente tutto il messaggio:

Conclusione

Abbiamo visto che il riuso del keystream presenta un pericolo reale, non solo teorico. Gli OTP vengono normalmente utilizzati lì dove la segretezza è un requisito fondamentale, come ad esempio nello scambio di informazioni tra le intelligence etc... Un utente "normale" difficilmente farà uso di OTP, tuttavia non dobbiamo dimenticare che gli stream-cipher, come ad esempio RC4, non fanno altro che generare un keystream e sono utilizzati sia a livello di networking: WEP ed SSL ne sono l'esempio principale, sia a livello applicativo. RC4 è infatti un algoritmo ampiamente utilizzato per la cifratura dei dati, ed usare due volte la stessa chiave, significa usare due volte lo stesso keystream!!! La cifratura del vecchio Word ne era un esempio, infatti cifrando con la stessa password due file .doc e xorandoli tra loro, si otteneva proprio lo xor dei due plaintext.

È sempre possibile il recovery?

È stata dimostrata² la possibilità di recuperare qualunque genere di documento che segue un pattern non casuale. Ma questo è un concetto abbastanza intuitivo, possiamo infatti pensare che finché abbiamo a che fare con due messaggi, il cui contenuto non è preso da una distribuzione uniforme (cioe' non sono formati da dati random), possiamo predire i bias e riottenere i messaggi originali. Questo procedimento è tanto più semplice quanti più sono i messaggi cifrati con la stessa chiave. Nel caso analizzato nel corso del paper, se avessimo avuto 256 differenti messaggi cifrati con la stessa chiave, non avremmo avuto nessun byte incerto, cosa che invece è accaduta per il primo byte. Infatti non abbiamo alcun modo di sapere se le prime due lettere originali erano entrambe maiuscole, o entrambe minuscole. Da questo possiamo concludere che è sempre possibile risalire ai plain-text originali, a meno che i messaggi cifrati non siano degli stream casuali di dati. Quindi il monito è oramai ovvio: attenti, non riutilizzate la stessa chiave MAI, né con un OTP né con uno stream-cipher. In quest'ultimo caso concatenate sempre la chiave segreta ad un vettore di inizializzazione tramite una funzione di hash cyptographically-strong.

The Final Challenge

Prendete questo file, contiene due messaggi cifrati con la stessa chiave, il contenuto sono sicuro che vi interesserà parecchio. Dentro il readme.txt troverete qualche suggerimento. Chi riuscirà a crackarli, oltre ad ottenere accesso all'archivio che si trova nello zip, verrà menzionato qui sotto, ma i messaggi non saranno mai rivelati...

Special Mention

I nomi di coloro (se ce ne saranno) che sono riusciti a crackare la Final Challenge.

1. Faina
2. Saturn
3. teDDy (che ha anche fatto un magnifico script con OpenOffice :))

Bibliografia

1. C. E. Shannon. - A mathematical theory of communication.
2. J. Mason, K. Watkins, J. Eisner, A. Stubblefield - A Natural Language Approach to Automated Cryptanalysis of Two-time Pads

Disclaimer

Non usate mai la stessa chiave per cifrare due messaggi, sia se usate un OTP sia se usate uno stream-cipher.