Re: Un ibrido tra CRC e HASH?

Ciao,
riformulo il problema in modo pi=F9 preciso, cos=EC ci possiamo chiarire
meglio.

Supponiamo, ad esempio, 5 utenti:

  1. Me
  2. Alice
  3. Bob
  4. Carol
  5. Dennis

Supponiamo inoltre che ci siano 4 messaggi, a cui Me =E8 interessato: X
Y W Z (per Me sono incognite)
Gli utenti 2, 3, 4, 5 sono a conoscenza di uno o pi=F9 messaggi.

Ogni utente 2, 3, 4, 5 mi trasmette un messaggio xorando[1] due
messaggi (scelti a caso):
M =3D X xor Y
N =3D Y xor Z
O =3D Z xor W
P =3D W xor X

[1] Usare l'operazione di XOR non =E8 un requisito fondamentale, si
potrebbe anche utilizzare mod n o un altro criterio.

Ottengo, in ricezione, un sistema di 4 equazioni. Le mie incognite,
come detto sopra, sono X Y W Z.
Inoltre, so con quali pezzi originali =E8 stato creato M, cio=E8 so che M
=E8 stato creato da X xor Y etc. (mi viene detto da chi invia questi
pezzi).
A questo punto, per risolvere il sistema, si procede (ad esempio) in
questo modo (si fa xor, casualmente, con i pezzi ricevuti):
X =3D M xor N
Y =3D P xor Z
W =3D N xor Y
Y =3D O xor X

Supponiamo che l'utente Alice (2) sia malintenzionato. Crea il blocco
M con del rumore e facendo crede a Me (1) che mi sta inviando X xor Y.
Mi trasmette quindi un blocco M che io riesco a decodificare.

Il problema nasce dal fatto che io ricostruisco i dati originali
usando un pezzo M che =E8 corrotto: =E8 come in un'equazione matematica:
la soluzione =E8 ammissibile, ma il risultato che ottengo =E8 sbagliato.

=C8 importante poter decidere se un blocco ricevuto contiene dei
messaggi corretti (oppure no) SENZA effettuare la decodifica. Se un
messaggio =E8 sbagliato si deve identificare il colpevole ed eliminare
quanto prima il messaggio corrotto.

Inoltre, quando qualcuno ha ricevuto della spazzatura, non ha modo di
sapere chi gliel'ha mandata - si accorge che c'=E8 qualcosa che non va
solo dopo la decodifica. A posteriori io non so che Alice =E8 l'utente
malintenzionato e che mi ha inviato dei blocchi corrotti, n=E8 so qual =E8
il pezzo corrotto (M) che mi ha compromesso la decodifica (che mi ha
"falsato" il risultato).

In sintesi, abbiamo identificato due problemi:
- identificazione del bad user, cio=E8 chi mi manda i dati sbagliati
- identificazione del pezzo sbagliato, cio=E8 il pezzo che mi impedisce
la decodifica. Devo capire se un pezzo P =E8 proprio ci=F2 che deve
essere, in modo che l'informazione decodificata a partire da P sia
valida; se P non =E8 valido posso evitare di decodificare inutilmente e
posso punire chi tenta di impedire la fruizione delle informazioni.

Possibili soluzioni
1) non posso usare le firme (ad esempio un hash, oppure
un'informazione sulla validit=E0, correttezza) di tutti i possibili
blocchi che si possono generare xorando 2 messaggi: se ci sono N
messaggi da cui si parte a generare i blocchi da inviare, si
dovrebbero avere 2^N possibili firme (una per ogni combinazione di
messaggio, in virt=F9 del fatto che si codificano blocchi casuali). Se N
=3D 100, pubblicare tutti gli hash diventa impossibile.

Ci si deve quindi "inventare" un meccanismo per la validazione dei
messaggi xorati.
Un'idea:
messaggio ricevuto: M =3D X xor Y
controllo: f(M) =3D f(X) xor f(Y)

dove f =E8 una funzione opportunamente scelta, propriet=E0 desiderabile =E8
che sia distributiva rispetto allo XOR (vedi pi=F9 avanti).

Gli hash degli N messaggi (quelli da cui si generano i messaggi da
inviare) sono pubblicati e sono disponibili a tutti; in questo modo
posso decodificare il messaggio ricevuto (se so da quali messaggi =E8
composto) e controllare se il singolo pezzo ricevuto =E8 corretto o meno
controllando il suo hash (ma rimane comunque il problema
dell'identificazione di chi mi ha mandato un blocco il cui hash non
corrisponde).

1a) Scelta di f:
- CRC La scelta risolve il problema del controllo della validit=E0 dei
messaggi ricevuti: se il messaggio ricevuto ha un CRC errato, i dati
che contiene sono sicuramente errati, e quindi lo scarto. Questo
perch=E9 la funzione CRC =E8 distributiva rispetto allo XOR.
Svantaggio: un utente malintenzionato potrebbe creare un messaggio
costruito appositamente per avere un CRC uguale a quello di un
messaggio "corretto": in realt=E0 il messaggio creato ad hoc contiene
spazzatura e non contenuto informativo desiderato.

Esiste un CRC che non soffre di questo problema?

- hash (ad esempio SHA256). In generale, la funzione non =E8
distributiva rispetto allo XOR, e quindi non posso controllare la
correttezza del messaggio ricevuto. Per alcune implementazioni di hash
mandare un fake di un digest =E8 possibile (stesso problema di CRC).

Esiste una funzione hash che sia distributiva rispetto allo XOR (o a
mod n, oppure a qualche altra operazione) ma che garantisca
l'integrit=E0 dei dati e l'unicit=E0 del digest creato?

2) Trovare alcuni rilassamenti ai requisiti che ci permettono di
trovare una soluzione pi=F9 semplice.

Riuscite a vederne qualcuno?
Grazie.

Ciao

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