Newsgroup: it.comp.sicurezza.crittografia
Titolo: Isomorph 2^10 known plaintext attack

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Salve a tutti.
L'altro giorno, girando per la Wikipedia[1] sono incappato in una
modifica riguardante un algoritmo di cifratura (cito[2] traducendo
dall'inglese) "totalmente sicuro", "può cifrare più dati di quelli
contenuti nell'universo", inoltre "può quasi operare sul cono di luce
del messaggio" (questa caratteristica mi ricorda vagamente la
descrizione della velocità limite di un messaggio nel vuoto, ma non sono
certo di cosa significhi se applicata a un cifrario).
Mi sono ovviamente detto: che bello, vediamo come funziona!
Il sito, fortunatamente contiene una spiegazione abbastanza
dettagliata[3], completa di animazione flash[4].
Il sistema è abbastanza chiaro, riassumo molto brevemente per chi non
sapesse l'inglese:
1. creo una tantum 1024 chiavi da 1024 bit
   (per un totale di 1MiB di dato segreto, che scambio con il ricevente)
2. per ogni messaggio P (di max 1024 bit) che voglio inviare scelgo
   casualmente 512 chiavi delle 1024 che ho; le combinazioni possibili
   sono circa 10^300 (cito il sito), quindi non rischio di esaurirle
3. faccio lo XOR di tutte queste 512 chiavi e del mio messaggio P
4. invio al destinatario l'elenco delle chiavi X che ho usato e il
   valore C appena ottenuto
5. il destinatario (che già possiede K) estrae le chiavi giuste, fa a
   sua volta lo XOR tra loro e con C, ottenendo P
L'attaccante non ha modo di farlo. O almeno: questo dice il sito.
Passiamo, quindi, ai fatti.
La prima cosa che l'occhio attento può notare in [3] è la presenza di un
link "more detail" che porta nientemeno che ad un PDF [5] con analisi
della sicurezza di Isomorph, il che è un ottimo segno: dopo tanti nuovi
cifrari "rivoluzionari" che non ha controllato nessuno, questo almeno è
stato verificato con attenzione.
Il suddetto PDF contiene moltissima statistica che spiega quanto il
numero di possibili chiavi sia enorme e gigantesco e che sia
fondamentalmente impossibile per l'attaccante fare un attacco
"statistico" al sistema. Devo francamente ammettere che ho saltato tutto
per leggere il paragrafo "conclusioni" (pag. 10).
Le conclusioni fanno sempre affermazioni importanti e anche questa volta
non sono stato deluso: affermano difatti che questo cifrario non è
importante tanto per la sua sicurezza che il sito definisce "assoluta",
quanto per la sua velocità: difatti la chiave di decifrazione può essere
calcolata anticipatamente e poter quindi decifrare il messaggio
nell'istante stesso in cui viene ricevuto.
Altra nota importante, nella pagina precedente, è che la sicurezza del
sistema si basa sul fatto che l'attaccante non venga a conoscenza di
coppie (testo in chiaro, testo cifrato) perché questa interessante
possibilità non è stata analizzata ed è da riservarsi per studi successivi.
Per mio personale parere queste due ultime affermazioni risultano
vagamente scorrelate dal mondo della crittografia moderna: difatti se si
vuole pre-calcolare un *qualsiasi* cifrario basta utilizzarlo in
modalità CTR. Inolte affermare che un cifrario è sicuro quando non
resiste ad attacco known-plaintext è quantomeno sospetto.
Passiamo quindi all'attacco known-plaintext:
1. l'attaccante deve come prima cosa procurarsi una certa quantità di
   coppie plaintext-ciphertext, nello specifico circa 1024 - 1028
2. si procede poi a creare una matrice definita in GF(2) dove ogni
   elemento X(i,j) vale 0 o 1 a seconda se la chiave i è stata usata per
   cifrare il messaggio j
3. si calcola il rango della matrice X, per matrici così grandi è molto
   probabile che questo sia completo (1024), in caso contrario si
   sostituiscono le ultime 2-3 righe con altri messaggi possibili
4. si inverte la matrice non singolare X così ottenuta
5. si moltiplica la matrice inversa per lo XOR di messaggi cifrati e non
   ottenendo così la matrice delle chiavi
Dato che la mente fa spesso brutti scherzi, facendo pensare come
"banali" passaggi che banali non sono, ho confermato la mia idea con del
codice octave[6] (Octave è praticamente la versione opensource di
Matlab), che allego:
# setup
N = 1024;
K = gf(randint(N, N));
X = message_matrix(N);
P = gf(randint(N, N));
# encryption
C = P + K * X;
# cryptanalysis
Ka = (C + P) / X;
all(all(K == Ka))
La parte più complessa e lunga è proprio il calcolo e la verifica di una
matrice 1024x1024 di indici casuali X, con verifica di rango come
descritto prima:
function M = message_matrix (N)
  M = gf(randint(N, N));
  do
    r = rank(M);
    if(r < N)
      M(:, r:N) = randint(N, N-r+1);
    endif
  until(r == N)
endfunction
Tutte le operazioni sono svolte in matrici GF(2) anziché vettori
GF(2^1024) per il solo fato che Octave non supporta campi di Galois con
esponente maggiore di 16.
Questa soluzione non è certo il massimo di velocità e di efficienza (si
pensi anche solo al fatto che le matrici K, X e P dovrebbero occupare
1MiB ognuna ma essendo immagazzinate un bit per cella occupano invece
32MiB, più altri overhead di Octave) ma nonostante questo il passo
fondamentale, quello dell'inversione di X, occupa circa 45 secondi su un
processore AMD64 3800+; la memoria occupata è di circa 88MiB.
Potrebbe essere fatto, suppongo, perfino su un 486, in qualche ora.
Il punto essenziale è che conoscere 1024 coppie ciphertext-plaintext non
è affatto pretenzioso (numerosi cifrari vengono considerati
"irrimediabilmente rotti" quando servono 2^40 o più coppie, in questo
attacco ne bastano 2^10) e questo è semplicemente un risultato
approssimativo e abbastanza grezzo ottenuto in una notte di lavoro.
Modificandolo opportunamente si può probabilmente ricavare qualcosa di
utile anche conoscendo solo una piccola parte di ogni messaggio
(tipicamente, l'header del protocollo interno) oppure ottenere alcune
delle chiavi con un numero inferiore di messaggi.
Alla fin fine, la cifratura si riduce all'equazione lineare:
  C = P + K * X
e non stupirà certo se si afferma che il suo inverso è:
  K = (C + P) / X
Link:
1. 
http://it.wikipedia.org/
2. 
http://www.isomorph.it/crypto_overview.htm
3. 
http://www.isomorph.it/crypto_results.htm
4. 
http://www.isomorph.it/flash/crypto_isomorph.htm
5. 
http://www.isomorph.it/paper_crypt.pdf
6. 
http://www.octave.org/
- --
Lapo Luchini
la...@lapo.it
 (OpenPGP & X.509)
www.lapo.it
 (ICQ UIN: 529796)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (Cygwin)
Comment: Using GnuPG with Thunderbird - 
http://enigmail.mozdev.org
iEYEARECAAYFAkNMTccACgkQaJiCLMjyUvtqiACg7dZo1UbWTRFBKKuv/US2h4TZ
fzYAoIJs3OctgFP/IHw2fV0Cx/+1HsIH
=puC8
-----END PGP SIGNATURE-----

   (per un totale di 1MiB di dato segreto, che scambio con il ricevente)
---SNIP
E qui magari c'e' il problema di scambiarle con sicurezza. 

[CUT]	
Sono rimasto scioccato dalla tua spiegazione .. sai davvero analizzare 
bene i dati in tuo possesso :) complimenti ;)
hai + dato un'occhiata al mio di algoritmo .. mi piacerebbe se potessi 
fare una stessa analisi .. ;)
grazie
-- 
[CapoBecchino]
Il becchino si sposa: in abito rigorosamente nero, con la sposa accanto 
parte in auto (nera) con le classiche bare attaccate al paraurti posteriore.
La sera, dopo cena, lei lo aspetta semisdraiata su letto, in un negligé 
che sembra una nuvola. Lui si prepara in bagno ed esce impeccabile: 
pigiama nero con i risvolti oro, viso impassibile, passo bilanciato; si 
avvicina alla moglie e dice:
- Signora, vuol baciarlo prima di metterlo dentro? (da Barzellette.it)