Validazione di messaggi (era: Un ibrido tra CRC e HASH?)

Quoting Stefano Zanero <[email protected]>:

> Questa cosa rientra nella classe dei problemi bizantini.
> http://en.wikipedia.org/wiki/Byzantine_fault_tolerance
>
> E di conseguenza lo dovresti reimpostare partendo dalle spalle dei
> giganti, perche' di letteratura sull'argomento ce ne sono armadi
> interi...
>

Ciao,
ho ragionato sulle risposte che mi avete dato. Tante persone mi hanno
consigliato meccanismi di protezione quali HMAC, MAC e/o cifrari
simmetrici o asimmetrici.
Usando queste soluzioni NON risolvo. Provo a spiegarvi il perch=E9.

Supponiamo che ci sia un file. Lo divido in N pezzi. Calcolo l'hash di
ogni singolo pezzo degli N, e li metto a disposizione degli utenti
della rete.

Esempio:
divido il file in X, Y, Z. Supponiamo che ora ci sia un canale
condiviso, sul quale gli utenti si scambiano i messaggi, codificati
come segue. Come codifico i pezzi?
La codifica sceglie dei pezzi random e ne calcola lo XOR (operazione ^)
Ad esempio:
A =3D X^Y, B =3D X^Y^Z, D =3D Y^Z

Sul canale condiviso si inviano soltanto A, B, D.
La decodifica =E8 immediata: X =3D B^D, Y =3D A^B^D, Z =3D A^B

Chi legge il canale sa A PRIORI:
- la scelta random, cio=E8 i pezzi "originali" (x, y, z nel nostro
esempio) che sono stati scelti per creare i messaggi codificati.
- un'informazione AFFIDABILE (ad esempio gli hash pubblici che dicevo
sopra) per verificare se i pezzi "originali" sono corretti o meno

Il problema =E8 il seguente: supponiamo che un utente invii A' che NON
contiene X^Y, ma N^M o qualsiasi altra cosa a cui non sono interessato.
La decodifica ritrova X, Y, Z scorretti (e mi accorgo soltanto DOPO che
controllo l'informazione sicura, cio=E8 il loro hash, nonostante li abbia
decodificati senza problemi!).

Vorrei poter trovare un meccanismo per il quale si possa validare un
messaggio codificato (nell'esempio: A, B, D) per poterlo immediatamente
marcare come corretto (nell'esempio A) oppure scorretto (nell'esempio
A').
Utilizzare le soluzioni di crittografia pubblica o privata non serve:
non =E8 importante la segretezza del messaggio!
E se usassimo HMAC o MAC il problema non cambierebbe: se un attaccante
inviasse A' il MAC o HMAC =E8 comunque verificato, non ci sono state
modifiche dopo l'invio ma la decodifica dei pezzi originali =E8 comunque
sbagliata.

Le soluzioni a cui ho pensato sono le seguenti:
- pubblicare (come informazione affidabile disponibile a tutti gli
utenti di cui parlavo sopra) tutte le possibili combinazioni dei pezzi
originali. Ora, se N =3D 100, dovremmo pubblicare 2^N possibili hash.
Soluzione impraticabile
- CRC: tale che CRC(A) =3D CRC(X^Y) =3D CRC(X) ^ CRC(Y) (distributivit=E0=
 del
CRC su XOR)
In questo caso l'informazione AFFIDABILE che dicevo sopra sarebbe la
funzione CRC. Ma =E8 facile creare un A' tale che CRC(A) =3D CRC(A').
Quindi =E8 una soluzione inutilizzabile
- Hash: Hash(A) =3D Hash(X^Y) MA NON =C8 VERO CHE: Hash(X^Y) =3D Hash(X) =
^
Hash(Y). Soluzione inutilizzabile.
- Hash Universali: a quanto ho capito sono distributivi rispetto allo
XOR. Ma sono hash crittograficamente sicuri, vi fidereste ad usarli?
- Problemi bizantini (come suggeriva Zanero) e hash (un hash sicuro,
tipo SHA-256).
In pratica:
- Alice riceve da Bob A =3D X^Y, chiede ad un altro utente (Charlie, da
cui NON ha ricevuto A!) l'hash di X^Y e calcola l'hash del blocco A
ricevuto da Bob. A questo punto li confronta:
	* Se l'hash corrisponde, allora sono relativamente sicuro che A =E8
corretto
	* Se l'hash calcolato non corrisponde, c'=E8 qualcosa che non va:
		. o Charlie ha mandato un hash falso
		. oppure Bob ha mandato un blocco falso (A' al posto di A).
	Come posso verificare? Ripeto il processo di verifica.
	Alice chiede a Dave l'hash di X^Y:
		. Se corrisponde all'hash del blocco ricevuto da Bob, allora Charlie
ha inviato un hash falso
		. Se corrisponde all'hash ricevuto da Charlie, allora il blocco
mandato da Bob =E8 falso (Bob ha mandato A')
		. Se non corrisponde allora Alice deve ripetere il processo di
verifica chiedendo ad un altro utente l'hash del blocco e verificare
chi sta dicendo il falso

Punto di forza: =E8 difficile per chi invia blocchi sapere l'utente a cui
si chieder=E0 l'eventuale verifica (quindi, per avere una ragionevole
probabilit=E0 di inquinare la rete, un attaccante dovrebbe avere un
numero di alleati nella rete superiore alla met=E0 degli utenti della
rete stessa.

Problema: non =E8 che questa verifica costa parecchio?
Se tutti gli utenti si devono scambiare richieste di hash dei messaggi
(anche se la lunghezza di un hash =E8 di pochi bit e quindi potrebbe
essere trascurabile) si pu=F2 correre il rischio di un "intasamento" ?
Oppure un attaccante potrebbe realizzare un DDoS continuando a
richiedere la computazione di hash e/o l'invio di hash.

Spero che in questo modo il problema sia un po' pi=F9 chiaro. Che cosa ne
pensate?

Grazie


________________________________________________________
http://www.sikurezza.org - Italian Security Mailing List