Re: One time key

On Wed, Jan 31, 2001 at 09:36:13PM +0100, Sorrow The Prince wrote:
> la mia idea e' questa:
> 
> 1) Key n bits (grossa, anche qualche centinaio di K)
> 2) KeyStream = RAND (Key, offset, len)
> 3) C = M xor keyStream

Il punto 2 non e' molto logico.
Se tu hai una segreto puoi generare il keystream senza
affidarti ad offset e lunghezze utilizzando un block
cipher o una funzione ad una via in counter mode
o in qualche modo che ha un feedback interno se vuoi
la propagazione dell'errore (dipende dal goal).
In questo modo potete scambiarvi un ammontare di bytes
uguale al periodo nel quale la keystream non si ripete.

> io e il ricevente ci passiamo la chiave in maniera sicura, magari
> vedendoci =) ce la passiamo grossa in modo da sfruttarla il piu'
> possibile, visto che e' difficile vedersi spesso...

Alla fine devi usare una larghezza del blocco che e' quella
di un block cipher o di una one-way hash function per generare
il tuo keystream, dunque anche questo non mi e' chiaro.
O passi tante chiavi grandi quanto la dimensione del blocco
del cipher che userai o non avrai alcun modo di utilizzare
tutti quei bytes. Dunque se mi dici "n bits" di chiave
io suppongo n/m chiavi in cui m e' la dimensione del blocco
del tuo cipher.

> quando devo criptare un messaggio M, uso un pezzo di quella chiave,
> a partire da offset per la lunghezza len (magari questa poi sara'
> fissa...)... generando quindi il KeyStream...

vedi sopra

> faccio lo XOR del messaggio con il KeyStream...
> a questo punto dovrei avere la sicurezza dell'One Time Pad: senza
> chiave non mi decripti :)

Assolutamente no :)

Se tu usi uno stream cipher il segreto e' quello che conta.
Se qualcuno fa brute force sul tuo segreto e prova a fare
l'xor con il tuo ciphertext alla fine otterra' un messaggio
in chiaro riconoscibile facilmente.

Con la one time pad questo problema non eisiste.
Poiche' la chiave e' grande quanto il messaggio stesso
l'attacker puo' inventarsi tutte le chiavi che vuole
che decifreranno in tutti i possibili messaggi di quella
lunghezza, ma non sapra' mai qual'e' la vera.
Per questo la OTP e' "perfect security".

> o magari affidandomi ad un RSA con key grossa come l'universo :)
> sempre sperando che qualcuno non abbia trovato un sistema veloce per
> fattorializzare (si dice cosi'? perdonatemi :p) un numero...
> ma le speranze... sono spesso vane =)

Utilizzare una chiave troppo grande e' semplicemente un overkill.
Se tu utilizzi una chiave di 4096 bit, e la difficolta' di fattorializzare
e' molto alta, sei gia' alla massima sicurezza che puoi ottenere.
Se potrebbero fattorializzare una chiave cosi' grande c'e' qualche
problema di fondo ed una chiave piu' grande non ti aiuta.
Ed ancora: se il problema fosse la key RSA grande l'attacker potrebbe
semplicemente attaccare il segreto del tuo cipher, che e' piu' piccolo.

> ovviamente la sicurezza sta nel generatore e nella key...
> se trovassi un generatore che sono certo non crei numeri predicibili
> dopo tot passi (avevo letto che i generatori di numeri pseudo-casuali
> che sfruttano i registri a retroazione lineare si ripetono dopo un
> toto di passi...) e, nel caso, *so* dopo quanto si ripetono o sono
> predicibili, orbene, so quanto il mio messaggio puo' essere lungo al
> massimo...

Puoi fare questo utilizzando un block cipher in counter mode
o una one-way function sicuro che non avrai una ripetizione
prima di 2^n dove n e' il numero di bits dell'output.
Una delle proprieta' di un block cipher ad esempio e' che
per ogni blocco in plain-text sara' generato un diverso blocco
in cipher text, dunque se cifri un blocco che contiene un
numero progressivo da 0 a 2^n-1 sei sicuro che il periodo
e' 2^n. Piu' grande e' il blocco piu' lungo il periodo.

> ipotizziamo che questo algoritmo esista...
> allora l'unico punto "debole" e' la chiave, cioe' la sua lunghezza...
> perche' un brute force dovrebbe provare 2^n (dove n e' la lunghezza in
> bit della chiave) chiavi e quindi generare 2^n KeyStream da poi
> provare con il messaggio criptato...

Infatti, ecco perche' questa _non_ e' una OTP.
Ti ricordo inoltre che cio' e' identico a cifrare con.. che so.. DES
e scambiare la chiave di persona. O scambiare N chiavi per potersi
scambiare piu' messaggi.

> teoricamente un attacco intelligente sarebbe crearsi tutti i KeyStream
> possibili, in modo da averli pronti per decriptare ogni messaggio
> cifrato utilizzando lo XOR...

Questo presuppone capacita' di immagazzinamento proibitive.

> quindi mi chiedo: quanto lunga dovrebbe essere il seme per assicurarmi
> che un attacco del genere impieghi anni luce per essere portato a
> termine?

Va benissimo la grandezza del blocco di SHA1, presupponendo che SHA1
sia non crittoanalizzabile. E' inconcepibile un brute force in quel
caso.

> non c'e' modo di trasformare questa linearita' della generazione del
> KeyStream in qualcosa di piu' complesso (ad esempio due chiavi di n
> bits in ingresso al RAND generator, in modo che un brute force debba
> fare (2^n * 2^n) tentativi per creare un KeyStream valido)?

Be, dipende. Puoi generare due keystream invece che uno se le chiavi
sono completamente non correlate, ma poi rimane da provare che il tuo
keystream cosi' ottenuto non sia lo stesso ottenibile con un solo
keystream ed una chiave diversa dalle tue due chiavi. Vedi gli argomenti
a proposito di 3DES e cose del genere per sapere di piu' sull'argomento.
In ogni caso non rischiare, e' molto piu' facile che abbassi la sicurezza
del tutto con cose di questo tipo.

> a> Questo e' uno "stream cipher". La chiave e' il seme, non quello che generi
> a> per fare l'xor, quello e' il key stream. La sicurezza di una cifratura
> a> di questo tipo sta tutta nella lunghezza della chiave e nella bonta'
> a> della generazione dei numeri pseudo casuali. Puoi usare un block cipher
> a> in counter mode per fare questo, o una funzione crittografica ad una via.
> ho gia' implementato questo schema usando blowfish e
> 
> Hi = E(Mi)[H(i-1)] XOR H(i-1)
> 
> cioe' criptando con kiave Mi il predente blocco e xorandolo con lo
> stesso (w i neologismi :)

Ups no, evita cio'. Usa un normale counter mode ed un "modo" dell'algoritmo
gia' presente in letteratura.

> a> C'e' un attacco abbastanza insidioso pero':
> a> 1) Non puoi controllare l'integrita' dei dati senza un HMAC
> beh potrei fare un SHA del messaggio in chiaro e poi criptarlo con il
> messaggio... non andrebbe bene?
> or che ci penzo, se uno un po' +stardo dentro mi modificasse uno dei
> byte iniziali, lo SHA non tornerebbe mai...
> senza che il ''ardo (^^) sia stato in grado di decifrare, puo'
> comunque arrecarmi danno...
> avresti un'idea? =)
> 
> a> 2) Se io penso che nel tuo testo sia presente all'inizio la parola
> a>    "Caro" posso fare l'Xor dei primi quattro bytes con "Caro" ed
> a>    ottengo quel pezzo di key stream, poi faccio l'xor tra questo
> a>    ed il testo che voglio "spooffare", ed ottengo un ciphertext valido.
> ecco... verissimo...
> ad esempio la signature... se un tizio sapesse che metto la signature
> nel messaggio cifrato, avrebbe la possibilita' di generare tre righe
> valide ma spoofate (con una o due efe? :)))
> 
> di certo io starei attento a ripetere del testo, ma un ipotetico
> utente no... forze che con la questione di prima si risolve anche
> questa?

Ti serve un modo per firmare il messaggio. Un HMAC che utilizza una
parte diversa del segreto o altre cose del genere.

ciao,
antirez

-- 
Salvatore Sanfilippo              |                      <antirez@invece.org>
http://www.kyuzz.org/antirez      |      PGP: finger antirez@tella.alicom.com

--------------------------------------------------------------------------
informazioni sui comandi supportati da questa ml: http://www.sikurezza.org