Ciao, riformulo il problema in modo più preciso, così 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 è interessato: X Y W Z (per Me sono incognite) Gli utenti 2, 3, 4, 5 sono a conoscenza di uno o più messaggi. Ogni utente 2, 3, 4, 5 mi trasmette un messaggio xorando[1] due messaggi (scelti a caso): M = X xor Y N = Y xor Z O = Z xor W P = W xor X [1] Usare l'operazione di XOR non è 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 è stato creato M, cioè so che M è 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 = M xor N Y = P xor Z W = N xor Y Y = 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 è corrotto: è come in un'equazione matematica: la soluzione è ammissibile, ma il risultato che ottengo è sbagliato. È importante poter decidere se un blocco ricevuto contiene dei messaggi corretti (oppure no) SENZA effettuare la decodifica. Se un messaggio è 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'è qualcosa che non va solo dopo la decodifica. A posteriori io non so che Alice è l'utente malintenzionato e che mi ha inviato dei blocchi corrotti, nè so qual è 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è chi mi manda i dati sbagliati - identificazione del pezzo sbagliato, cioè il pezzo che mi impedisce la decodifica. Devo capire se un pezzo P è proprio ciò che deve essere, in modo che l'informazione decodificata a partire da P sia valida; se P non è 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à, 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ù del fatto che si codificano blocchi casuali). Se N = 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 = X xor Y controllo: f(M) = f(X) xor f(Y) dove f è una funzione opportunamente scelta, proprietà desiderabile è che sia distributiva rispetto allo XOR (vedi più 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 è composto) e controllare se il singolo pezzo ricevuto è 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à dei messaggi ricevuti: se il messaggio ricevuto ha un CRC errato, i dati che contiene sono sicuramente errati, e quindi lo scarto. Questo perché la funzione CRC è 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à 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 è 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 è 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à dei dati e l'unicità del digest creato? 2) Trovare alcuni rilassamenti ai requisiti che ci permettono di trovare una soluzione più semplice. Riuscite a vederne qualcuno? Grazie. Ciao ________________________________________________________ http://www.sikurezza.org - Italian Security Mailing List
