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

Quoting Stefano Zanero <zanero@xxxxxxxxxxxxxx>:

> 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é.

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 = X^Y, B = X^Y^Z, D = Y^Z

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

Chi legge il canale sa A PRIORI:
- la scelta random, cioè 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 è 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è 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 è importante la segretezza del messaggio!
E se usassimo HMAC o MAC il problema non cambierebbe: se un attaccante
inviasse A' il MAC o HMAC è comunque verificato, non ci sono state
modifiche dopo l'invio ma la decodifica dei pezzi originali è 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 = 100, dovremmo pubblicare 2^N possibili hash.
Soluzione impraticabile
- CRC: tale che CRC(A) = CRC(X^Y) = CRC(X) ^ CRC(Y) (distributività del
CRC su XOR)
In questo caso l'informazione AFFIDABILE che dicevo sopra sarebbe la
funzione CRC. Ma è facile creare un A' tale che CRC(A) = CRC(A').
Quindi è una soluzione inutilizzabile
- Hash: Hash(A) = Hash(X^Y) MA NON È VERO CHE: Hash(X^Y) = 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 = 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 è
corretto
	* Se l'hash calcolato non corrisponde, c'è 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 è 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: è difficile per chi invia blocchi sapere l'utente a cui
si chiederà l'eventuale verifica (quindi, per avere una ragionevole
probabilità di inquinare la rete, un attaccante dovrebbe avere un
numero di alleati nella rete superiore alla metà degli utenti della
rete stessa.

Problema: non è che questa verifica costa parecchio?
Se tutti gli utenti si devono scambiare richieste di hash dei messaggi
(anche se la lunghezza di un hash è di pochi bit e quindi potrebbe
essere trascurabile) si può 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ù chiaro. Che cosa ne
pensate?

Grazie