Newsgroup: it.comp.sicurezza.crittografia
Titolo: Known Plain-Text Attack

Ho implementato una cosa di questo tipo:
codifica: 
1) prendo il testo in chiaro
2) lo codifico con base64_encode (per esigenze mie)
3) inizializzo il PRNG mersenne twister con una password
4) faccio un random sort del testo al punto 2 utilizzando il PRNG
decodifica:
1) prendo il testo codificato
2) inizializzo il PRNG con la stessa password della codifica
3) faccio il random sort al contrario (perche', se in codifica avevo
scambiato, per esempio, gli elementi 1,2 e 2,3, in decodifica devo
scambiare 2,3 e poi 1,2)
4) faccio un base64_decode
Una persona X avra' in mano sia il risultato della codifica che quello
della decodifica.
E' possibile, da questi due elementi, ottenere la password?
-- 
http://e-0.org

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Buttha wrote:
| 4) faccio un random sort del testo al punto 2 utilizzando il PRNG
In questo modo applichi da "diffusione" ma non la "confusione" (citando
Shannon), che non è praticolarmente una buona idea, comunque questo poco
c'entra con la tua domanda...
| 3) faccio il random sort al contrario (perche', se in codifica avevo
| scambiato, per esempio, gli elementi 1,2 e 2,3, in decodifica devo
| scambiare 2,3 e poi 1,2)
Quindi devi tenere in memoria l'intero set degil scambi suppongo, dato
che è difficile convincere il PRNG a dare l'output al contrario 0=)
(questo limita la lunghezza dei messaggi cifrabili, ma anche questo poco
c'entra con la tua domanda...)
| Una persona X avra' in mano sia il risultato della codifica che quello
| della decodifica.
| E' possibile, da questi due elementi, ottenere la password?
A partire dall'insieme degli scambi direi che si può teoricamente
ricavare il seed che li genera (il sito di MT specifica che non è adatto
a scopi critotgrafici quindi suppongo che sia invertibile con meno
lavoro che il caso di un PRNG ideale).
Arrivare da "plaintext+ciphertext" all'insieme degli scambi è operazione
"relativamente" facile, al limite bisogna fare delle prove per ogni
possibile coppia di caratteri uguali (ad esempio se vedo "aabb" ->
"abab" non so se lo scambio è stato 1234->1324 o 1432 o 3214 o 3412).
Ho risposto in modo un po' "abbondantemente" perché non ho capito bene
lo scopo della tua domanda, comunque nel più ci sta il meno, in teoria ^_^""
- --
L a p o   L u c h i n i
l a p o @ l a p o . i t
w w w . l a p o . i t /
http://www.megatokyo.it
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (Cygwin)
Comment: Using GnuPG with Mozilla - 
http://enigmail.mozdev.org
iEYEARECAAYFAj/fIIMACgkQaJiCLMjyUvsN/gCg+YLGZAGv9tuZJ4RGeRYUkfE4
7V0An3UTYxufPxFiKrcap8WgKvNdintb
=KhN/
-----END PGP SIGNATURE-----

"abab" non so se lo scambio è stato 1234->1324 o 1432 o 3214 o 3412).
Effettivamente, e' un procedimento abbastanza semplice arrivare alle
possibili sequenze di scambi. Considera, pero', che se di scambi ne
facessi tanti, allora, per arrivare da ab a ba, potrei si fare 12->21,
ma anche 12->21->12->21, ecc...
Visto, pero', che, in questo caso, il numero di scambi e' limitato
superiormente dalla grandezza del messaggio, allora lo spazio di
manovra e' limitato.
Piu' che altro mi resta il dubbio che, anche sapendo la sequenza
esatta degli scambi, non sia possibile arrivare univocamente al seed,
perche' credo che una sequenza random breve tipo (1,5,7,3,5,4,8,10)
possa essere generata da piu' seed.
-- 
http://e-0.org

 possa essere generata da piu' seed.
Per un lcg, no, ma per MT, ovviamente sì (come potresti ottenere un periodo
di 2^19937-1 con soltanto 2^32 numeri?).
Cristiano

essere sicuro; il condizionale è d'obbligo! :-)
massi', piu' che altro ho il php senza il supporto di mcrpyt
(
http://62.149.227.152/a9Y2DVbVhH5Bec9NWLc00vbWCl2hub=i1bwRyHyo0ZnXLi0unBlAmLobaMA=
)
e non avevo voglia di ricompilarlo solo per fare una minchiatina come
l'url che ho appena postato :))
Comunque, grazie a tutti e due per le considerazioni.
-- 
http://e-0.org


|>credo che una sequenza random breve tipo (1,5,7,3,5,4,8,10)
|>possa essere generata da piu' seed.
| Per un lcg, no, ma per MT, ovviamente sì (come potresti ottenere un
periodo
| di 2^19937-1 con soltanto 2^32 numeri?).
Che c'entra il periodo con il numero di numeri che lo compongono? Si
*può* ottenere  qualcosa con periodo ben più lungo del numero di numero
che lo compongono ^_^
Esempio: 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
ha periodo 24 ma contiene 2 soli numeri
Comunque se la password contiene più di 32 bit di entropia (e sarebbe
auspicabile...) conviene usare la "nuova" iniziailzzazione di MT "da
array", che permette di usare il suo intero spazio di valori.
(la vecchia versione usava solo seed da 32 bit, di default)
- --
L a p o   L u c h i n i
l a p o @ l a p o . i t
w w w . l a p o . i t /
http://www.megatokyo.it
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (Cygwin)
Comment: Using GnuPG with Mozilla - 
http://enigmail.mozdev.org
iEYEARECAAYFAj/hu7sACgkQaJiCLMjyUvtF/QCfcd5C1ceTPiFG13ioxlT3afwQ
8wgAoMjhzdd1jRDp8skXaMklQrXHXwHi
=hfC3
-----END PGP SIGNATURE-----