Newsgroup: it.comp.sicurezza.crittografia
Titolo: Decifrazione OTP

L'OTP, se non sbaglio, è noto per essere indecifrabile, se usato
correttamente. Tutti gli altri, invece, è possibile decifrarli, è "solo"
questione di tempo.
Quando si dice che è questione di tempo, a meno di rotture dell'algoritmo,
ci si riferisce al fatto che bisogna provare tutte le chiavi possibili?
Perchè questa cosa non è possibile con l'OTP, in fondo anche qui si usa
una chiave per cifrare il messaggio.
Grazie, Giubbe
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

  [X.509 available]
Linux Reg. User: #263663 / Machine: #216144 (Arch Linux/Wombat)
On the Web: 
http://www.quaqo.org
 - My OpenPGP KeyID: 0x5539D8E4
On ICQ: 48618109 - On Jabber: 
qu...@jabber.org/@jabber.linux.it

 significati anche cambiando qualche lettera. ;-)
Ehm, invece io non ci arrivo.
In una frase ci sono più parole ed ogni frase ha un senso compiuto, non
solo, la singola frase e tutta la lettera devono avere un senso logico.
Per ogni parola è facile trovarne più di una senso compiuto, ma è più
difficile trovare tutte parole estranee che legono tra di loro e ancora più
difficile che le frase estranee abbiano un senso logico. Senza contare che
tutta la lettera deve seguire un filo logico.
Secondo me che da un testo cifrato posso tirare fuori due lettere di senso
compiuto e logico è già troppo, perchè sbaglio?
bye

 compiuto e logico è già troppo, perchè sbaglio?
Perché non devi vedere un messaggio cifrato OTP, come una sequenza di
*parole* cifrate, ma come un *unico testo* cifrato di cui sai solo la
lunghezza, ma non da quante parole è composto, né quanto queste siano
lunghe (dato che non sai dove sono gli spazi tra una parola e l'altra).
Il testo cifrato OTP:
"dH055DwxvnAKxql92GufXwI"
darà, in base alla chiave OTP utilizzata, *tutti* questi messaggi validi
(e non solo questi):
"Il tempo sta cambiando."
"E' davvero una stupida."
"Sono felice che ci sia."
"He is a little bad guy."
"Morte agli uomini rosa."
"Telefonami alle cinque."
Senza avere la chiave OTP, non puoi sapere quale di questi messaggi (o
delle infinite altre possibili combinazioni), possa essere quello valido
(pur essendo tutti di senso compiuto).
Immagina tutto ciò, applicato ad un testo più lungo, come possa essere,
ad esempio, tutto questo post. Ne sapresti solo la lunghezza.
Più che un vero algoritmo di crittografia, l'OTP è la sovrapposizione di
un "rumore" al testo in chiaro (in genere, mediante XOR).
La decodifica avviene "eliminando" tale rumore.
Ma, se il rumore che viene eliminato non è proprio *quello sovrapposto*
(ovvero, la chiave OTP), il risultato potrebbe dare origine a
informazioni differenti da quelle originali. Alcune di queste, con senso
compiuto.
Mentre un algoritmo "classico", se accoppiato a *tutte* le chiavi
possibili, non potrà (molto probabilmente) mai dare *tutti* i risultati
di quell'esempio, un testo OTP accoppiato a *tutte* le chiavi OTP, darà
sicuramente *tutti* quei risultati come validi (più altri risultati
validi e non validi).
Ciao,
un TJL73 che spera di non aver confuso le idee...
-- 
"Se lei si spiega con un esempio, non capisco piu` niente."
                                                        -- Ennio Flaiano

compiuto e logico è già troppo, perchè sbaglio?
E` sbagliato se non moooooooolto prematuro, che persone come te
abbiano un ragionamento che solo sfiora questioni di crittoanalisi.
Non offenderti, non ce l'ho con te, che hai posto gentilmente
il tuo sincero dubbio, ma con il senso critico nullo nella ponderazione
dell'implicazione _usata_ ("messaggio comprensibile" => e` il decifrato).
E` un metodo sbagliato usare implicazioni che non si conoscono a fondo,
si vede spesso e tanti piu` ragionano in quella maniera tanti piu` danni fanno.
Saluti,
MARco

 lunghe (dato che non sai dove sono gli spazi tra una parola e l'altra).
Scusa il ritardo nella risposta, tanto più che continua a sfuggirmi il
concetto.
Sei proprio sicuro che più il testo è lungo, più sono le possibili frasi
sensate che posso tirare fuori?
Capisco che non so dove sono divise le parole, ma è proprio così facile
avere intere lettere sensate?
Avevo sentito che esiste una dimostrazione scientifica che riguarda
l'indecifrabilità di OTP, tu ne sai qualcosa? magari leggendola mi convinco
di questo fatto. In alternativa conosci un programma che implementi l'OTP?
E uno che tenta una decifrazione? Così gli passo questo post e vedo quanti
post sensati tira fuori.
Grazie, Giubbe


In OTP il testo cifrato e' il risultato dello XOR del testo in chiaro con la 
chiave di codifica (che ha la stessa lunghezza del testo in chiaro).
Testo cifrato = Testo in chiaro originale XOR Chiave originale
Il problema e' che dato un testo cifrato con OTP questo potrebbe essere 
stato generato da qualunque testo in chiaro di pari lunghezza ci possa 
venire in mente, non puoi escluderne nessuno perche' per ogni testo fasullo 
esiste una chiave fasulla che dia come risultato lo stesso testo cifrato e 
questa chiave si puo' facilmente calcolare nel modo seguente:
Chiave fasulla = Testo in chiaro fasullo XOR Testo cifrato
Non potendo distinguere una chiave fasulla da quella originale non e' 
neanche possibile distingure il testo in chiaro originale da tutte le 
possibili alternative.
Alessandro.

Ciao,
esitavo... ma visto che lo chiedi tu, cerco di spiegarti formalmente 
perché una OTP è (se non riutilizzata) un sistema indecifrabile.
Per la prima volta è stato dimostrato da Shannon.
sia X il tuo plaintext e Y il tuo cyphertext
Prima parte:
dimostriamo che La "segretezza perfetta" è equivalente a H(X|Y) = H(X) 
ed è eqivalente a X,Y stat. indipendenti
(In paroloni, conoscere Y senza conoscere la chiave non ti da alcuna 
infomazione su X)
H(X|Y) = H(X,Y) - H(Y) <= H(X)
con uguaglianza se e solo se X ed Y sono indipendenti
quindi dire che H(X|Y) = H(X) equivale a dire che X,Y sono indip
"segretezza perfetta" vuol dire,
Pr(X=x,Y=y) / Pr(Y=y)  = Pr(X=x | Y=y) = Pr(X=x)
per ogni x,y
Inoltre, se H(X|Y) = H(X)   (Ossia conoscere Y non elimina incertezza su X)
X,Y sono indipendenti e dunque
  Pr(X=x | Y=y) = Pr(X=x,Y=y) / Pr(Y=y)  = Pr(X=x)
per ogni x,y
quindi hai "segretezza perfetta"
Il sistema di Vernam offre segretezza perfetta poiché
sia Y = X + Y  (dove + indica l'operazione di XOR binario)
Pr ( X=x,Y=y) = Pr(X=x,K=x+y) = Pr(X=x) * Pr(K=x+y) = Pr (X=x) * 2^-n
Sommando su tutte le x ottieni
Pr(Y=y) = 2^-n
Dunque Pr(X=x|Y=y)=Pr(X=x) per ogni x,y
quindi segretezza perfetta
Forse ho cercato di sintetizzartelo un po' troppo.
In ogni caso il risultato (che non ti ho dimostrato) che si usa è che 
segretezza perfetta ==> H(K) >= H(X)
(e questo è il risultato di Shannon del 1949)
Ma detto in paroloni, il succo di tutto è :
per avere segretezza perfetta devi avere un qualcosa (la chiave) che sia 
"incerto" almeno quanto il testo da cifrare
Se rispetti questa condizione, ottieni che "conoscere il testo cifrato 
non ti da informazioni sul testo originario".
Come diceva giustamente tjl,
se hai una stringa
y= 0010101001
non potrai mai sapere se è stata generata dalla coppia
x= 0010101000
k= 0000000001
oppure dalla coppia
x= 1110101001
k= 1100000000
ecc.
Tutte le sequenze saranno "plausibili"
Quindi la tua attenzione si focalizza sul tuo "oracolo" che ti dice se 
una data sequenza (di plaintext) è valida o meno.
Ma ancora una volta, essendo l' incertezza sulla chiave ( ossia H(K)  ) 
così grande, non avrai *nessuna* indicazione circa la plausibilità o 
meno del plaintext.
Mettiamola cosi
Pensa una parola ed una chiave. Pensati? Bene!
Ora cifrali e dimmi la parola cifrata.
Diciamo che esce 101001
Che possibilità ho di sapere da quale coppia è stata generata?
Posso trovare una chiave che fa si che possa dire che veniva dalla 
parola "000000" ? si.
posso immaginare invece che venisse da "111111"? si!
e cosi via!
Quindi, per assurdo, il tuo brute force attack ha complessità nulla... 
perché trovi subito una chiave "possibile" ma il problema risiede ora 
tutto nell'oracolo che ti dice quando una parola decifrata ha senso o no!
(immagina ad esempio quante sono le parole di senso compiuto di N 
lettee... bene, sono tutte possibili plaintext per un tuo cyphertext di 
N lettere...)
Ovviamente tutto il ragionamento viene a cadere se usi male la cifratura 
di Vernam (ad es riutilizzi la OTP)
Perdona la lunghezza, spero di averti chiarito un po' le idee!
Buona fortuna... e non ascoltare chi ti consiglia di lasciar stare! :)) 
Se mai si chiede mai si impara!
Ciao
Salva


Grazie a tutti per l'esauriente spiegazione. Ora mi è più chiaro.
Bye