Newsgroup: it.comp.sicurezza.crittografia
Titolo: Problemi degli hash incrementali (MDx e SHAx)

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Seconda parte di "cose interessanti che ho scoperto o approfondito
leggendo 'Pratical Cryptography' by Ferguson&Schneier".
Length Extensions:
questa possibilità di attacco squalifica l'hash in analisi da ogni uso
come MAC (ad esempiousando h(K|m) per autenticare il mittente del
messaggio), in quanto (come minimo) il messaggio potrebbe essere
modificato lasciando l'hash come valido, benché non si conosca la chiave
~ hashata prima del messaggio stesso.
L'idea è che ogni hash incrementale si basa su una formula di questo
tipo: len(m)=k_blocchi len(m')=1_blocco h(m|m')=h'(h(m),m')
In pratica conoscendo h(m) (anche inorando m!) si può creare un hash
valido di un "estensione in lunghezza" di m (ad esempio "m|m'") con
valore sempre valido. Questo attacco è imho "molto grave", anche se non
è applicabile in tutti gli usi delle funzioni di hash, ma (MI PARE) solo
quando l'input da hashare stesso è accompagnato dal'hash "validante".
Però è comunque da risolvere dato che, come dice il libro, se usiamo
"blocchi base" con ognuno i suoi "bug" alla fine nno possiamo
considerarli "blocchi indipendenti" ma si cera una reet di interferenze
e collaborazioni tra diversi bug e l'analisi della sicurezza del
problema diventa infattibile. Quindi sarebbe melgio che ogni blocco
elementare fosse "perfetto", in modo da poterlo usare poi senza pensaer
a suoi eventuali "modi di uso" (che peraltro si può dare per scontato
che l'implementatore prima o poi scorderà di controllare).
Partial-Message Collision:
Anche questo attacco dà problemi, come minimo, nell'uso come MAC e in
pratica rende possibile l'uso dell'attacco del compleanno (vengono
trovati ogni giorno più modi per usarlo, difatti uno dei consigli base
del libro è usaer COMUNQUE un hash lungo il doppio dei bit di
"sicurezza" richiesti dal progetto, dato che esiste - e quindi usare
*sempre* SHA-256 e non SHA-1 o MD5).
Poniamo che il MAC questa volta è h(m|K).
L'attaccante può precalcolare una collisione tra h(m1)=h(m2) in n/2
prove (attacco compleanno).
Facendo poi autenticare h(m1|K) al sistema può distribuire invece
h(m2|K) facendo credere che il sistema l'abbia autenticato.
(dato che h(m1)=h(m2) e l'hash è nicrementale anche h(m1|K)=h(m2|K))
Ovviamente se m1 e m2 fossero di puro testo sarebbe ben difficile
trovare una tale collisione con un m2 "sensato", ma se 'm' fosse una
chiave o qualche dato più "denso" si può capire come possa essere
facilmente abusato.
Soluzione "sicura" (ma inefficente)
Hdbl(m) := h(h(m)|m)
Ponendo l'hash del messaggio a inizio del secondo hash si fa in modo che
ogni bit del messaggio modifichi l'hash finale fin dall'inizio, evitando
quindi la proprietà di "incrementalità".
Grosso problema: 'm' non può essere uno "stream" ma deve essere
accessibile due volte, non sempre è possibile.
Problema minore: ci vuole il doppio del tempo.
Soluzione "efficente" (e con una sicurezza "pretty good")
Hd(m) := h(h(m)) definita con sicurezza n/2
Definire la sicurezza "ufficiale" a n/2 bit "risolve" ogni attacco
basato sul paradosso del compleanno (si pulò parlare di "soluzione"
perché almeno è estremamenet chiaro per l'implementatore che la
sicurezza è n/2 e non n).
Il problema dell'estensione di lunghezza viene invece "veramente"
risolto, dato che a fine hash viene compiuta un'operazione "diversa"
l'hash non è più strettamente "incrementale", benché sia comunque
calcolabile a velocità e spazio in memoria praticamente immutate.
(difatti l'hash esterno hasha solo il risultato dell'hash interno, molto
piccolo e non influente, rispetto al tempo necessario per hashare il
messaggio - che potrebbe essere molto lungo)
Il libro "Pratical Cryptography" by Ferguson&Schneier si pone come
obiettivo di creare dei "mattoncini del lego" da 128 bit di sicurezza (e
utilizzabili, per quanto possibile, senza "avvertenze" particolari),
quindi da quel capitolo in poi considera come hash "da usare"
esclusivamente SHAd-256(m) = SHA-256(SHA-256(m)).
La sua migliore resistenza agli attacchi unita alla sua fondamentale
equivalenza allo SHA-256 "semplice" in quanto a velocità lo rendono una
scelta "più tranquilla" e vincente.
Dicesi anche: non sarà forse perfetto, ma è (ovviamente) resistente
almeno quanto SHA-256, è veloce praticamente uguale, e sicuramente
risolve alcuni attacchi, quindi è "meglio".
Lapo
- --
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/W27EACgkQaJiCLMjyUvsk8ACgl77E5fxC7YptALASpGvKW6ns
GWkAoI+khXulDat7IxHCswiNrp8+EmPo
=yBIW
-----END PGP SIGNATURE-----

  [X.509 available]  ,''`.
Linux Reg. User #263663/NEW Machine: #216144 (Debian Sarge/SID) : :' :
On the Web: 
http://www.quagliata.eu.org
 - My GPG Key:0x5539D8E4 `. `'
On ICQ: 48618109 - On Jabber: 
qu...@jabber.org/@jabber.linux.it
   `-

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
quaqo wrote:
| Non ho ben capito che problemi si risolvono con un doppio hash
| SHA-256(e in che modo)...
Per dirlo in altre parole faccio un esempio:
'm' è il messaggio da hashare, composto da 4 blocchi (per esempio!)
~  m = m1|m2|m3|m4
ora una delle proprietà degli hash citati è di essere "incrementali",
ovvero poter calcolare una funzione tale che
~  H(a|b) = f(H(a), b)
e quindi ottenere l'hash di una stringa più lunga della precedente
basandosi sull'hash della stringa precedente.
L'idea "base" per fare un HMAC sarebbe il seguente (dove 'k' è la chiave
segreta che serve per autenticare l'autore del messaggio):
~  HMAC(k, m) = H(k|m)
Se l'hash H fosse ideale questo andrebbe benissimo.
con un hash incrementale questo invece è totalmente insufficente, perché
l'attaccante non impiega nulla, conoscendo H(k|m), a calcolare H(k|m|n)
anche *NON CONOSCENDO* 'k'.
Che il poter "allungare" un messaggio lasciando 'valido' il MAC è reso
ovvio da un messaggio come questo:
m = "Attaccare domani alle 2300"
m|k = "Attaccare domani alle 2300, solo dopo aver ricevuto conferma".
Questo è il "length extension" attack che il doppio hash risolve.
Perché lo risolve?
Perché applicare l'hash stesso sul proprio output compie un'operazione
"diversa" da f() sull'ultimo blocco, togliendo la possibilità di
considerare l'ultimo blocco un blocco come tanti e poterne quindi
aggiunerne altri.
PS: il libro non ne parla (stranamente! in genere non dà niente per
scontato) ma ovviamente l'ultimo blocco è già "un po' diverso" dagli
altri in quanto contiene il padding, ma questo non ferma l'attacco:
se 'p' è il padding non c'è comunque problema a estendere
~  K|m|p
in
~  K|m|p|n|p'
dove il padding 'originario' viene visto come un blocco qualsiasi a metà
messaggio. Certo nel caso di messaggi testuali non sempre 'p' avrà
senso, ma nel caso il messaggio sia binario è molto più facile farlo
passare per normali dati.
BTW: ovviamente i normali HMAC *non* usano questa modalità
"estendibile", perché si è sempre saputo che MDx e SHAx hanno questo
problema, però secondo la logica del libro *OGNI* blocco elementare deve
essere perfetto quanto possibile e non avere controindicazioni, in modo
da non poter essere abusato (per mero errore o per intenzione)
- --
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/XuUwACgkQaJiCLMjyUvvh8ACgp8kN4rYcUBEfQ1+NB+IG3rlR
i0sAoJE0toszpfwRQ0KXo5+ym2gBXmg7
=jn8D
-----END PGP SIGNATURE-----

 Perché lo risolve?
(snip)
Capito anche questo.
Grazie ancora,



Se guardi la funzione update_buffers() vedrai che:
1. "espande" il buffer W di 512 bit in 2048 bit [il primo for]
2. prende il valore precedente dell'hash [la definizione di int a,b,c..]
3. ci lavora un po' su (questa è f), basandosi sui dati del blocco
attuale (contenuto, in forma espansa, in W) [secondo for]
4. lo imposta come nuovo valore dell'hash [penultima riga]
5. imposta bufs (il numero di  blocchi del buffer usati) a 0
| O meglio... Come posso riprodurre tutto questo? (es. md5(m) + "ciao" dove
| m e` una stringa, etc...)
Vediamo se riesco a produrre un esempio...
Prendiamo ad esempio un messaggio mono-blocco
m = "012345789ABCDEF"
Da ora in poi "scriverò" sempre in hex:
m = { 30 31 32 33 34 35 36 37 38 39 41 42 43 44 45 46 }
Questi però sono 128 bit, un blocco SHA1 ha bisogno di 512 bit, quindi
viene paddato così: si aggiunge un bit a 1 poi tanti zeri ; a fine
blocco c'è il numero di bit "hashati" scritto come un long (la parte che
ho scritto <> è un long che dice "128 bit").
m1 = {
~  30 31 32 33 34 35 36 37 38 39 41 42 43 44 45 46
~  80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
~  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
~  00 00 00 00 00 00 00 00<00 00 00 00 00 00 00 80>
}
Questo monoblocco viene hashato in un valore 'h(m1)'
Immaginiamo ora che un attaccanet conosca 'h(m1)' e voglia ad esempio
calcolare l'hash del seguente messaggio (che termina per "Non e' vero
nulla"):
m' = {
~  30 31 32 33 34 35 36 37 38 39 41 42 43 44 45 46
~  80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
~  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
~  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 80
~  4E 6F 6E 20 65 27 20 76 65 72 6F 20 6E 75 6C 6C
~  61
}
Questo viene suddiviso e paddato così:
m'1 = {
~  30 31 32 33 34 35 36 37 38 39 41 42 43 44 45 46
~  80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
~  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
~  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 80
}
m'2 = {
~  4E 6F 6E 20 65 27 20 76 65 72 6F 20 6E 75 6C 6C
~  61 80 00 00 00 00 00 00 00 00 00 00 00 00 00 00
~  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
~  00 00 00 00 00 00 00 00 00 00 00 00 00 00 02 88
}
Però l'hash di m'1 lo conosce già (è h(m1)) e può calcolare l'hash
intero anche non conoscendo il messaggio 'm'.
BTW: mi spiace ma di esempi "pratici" (ad esempio con il comando
"sha1sum" da riga di comando non si può farne perché l'attaccante ha
bisogno di un hash "con valore iniziale specificato2, cosa che l'utility
da riga di comando ovviamente non permette ^_^"")
- --
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/a4CcACgkQaJiCLMjyUvu+PACgytxghUbXaDnpCqey9i7zqHQO
GU0An0bunVYmjvtp03WyL4U0Lv0fPr0P
=Fynp
-----END PGP SIGNATURE-----

 intero anche non conoscendo il messaggio 'm'.
Cioe` per gli hash incrementali fare l'hash di quei due blocchi
separati (paddati a dovere, etc...) equivale a farli assieme?
(In soldoni chiaramente :P)


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
quaqo wrote:
| Cioe` per gli hash incrementali fare l'hash di quei due blocchi
| separati (paddati a dovere, etc...) equivale a farli assieme?
| (In soldoni chiaramente :P)
In che senso "assieme"?
comunque il concetto è che l'hash di un messaggio lungo è ridotto a
calcoli sulll'hash del sotto-messaggio lungo un blocco di meno e
all'ultimo blocco stesso:
m=m1|m2|m3...|mk
H(m)=H(m1|m2|m3...|m(k-1), mk)
Questo di per sé non è un problema, il problema vero è che l'ultimo
blocco avrebbe avuto bisogno di qualche controllo "diverso".
La versione "d" fa proprio questo (calcolando l'hash come hash
dell'output dell'hash, calcolo che viene fatto alla fine e quindi fa da
"chiusura").
- --
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/cQDYACgkQaJiCLMjyUvs6oQCghN3jasoRGRSRrZcA411vW69S
qJoAoLrNlCSNDDFF29rE8TNq+8IIz17r
=JQTd
-----END PGP SIGNATURE-----

Il Sun, 14 Dec 2003 11:49:26 +0100, Lapo ha scritto:
[...]
Iufff.... Finalmente ho capito ! :)
Grazie !
Saluti,
