Re: [ml] Un ibrido tra CRC e HASH?

On Thursday 06 March 2008, you wrote:
> 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
Questo vuol dire che ogni utente conosce tutti e 4 i messaggi che ti servono? 
Se sì , c'è un attacco molto efficace , vedi ---> 

> [1] Usare l'operazione di XOR non è un requisito fondamentale, si
> potrebbe anche utilizzare mod n o un altro criterio.
Serve un' operazione invertibile , dati 2 su 3 elementi di A op B =C ,
se restiamo in contesto di singola cifra binaria , le uniche 2 operazioni 
disponibili sono XOR e l' NOT(XOR).
 
> 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
No. M xor N = X xor Y xor Y xor Z = X xor Z.

> 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.
---> Non è detto. Se per caso (o per volontà di Alice) il rumore è in 
dipendenza lineare con una delle altre equazioni hai un sistema 
sottodefinito. E' necessario , per costruirlo volontariamente , che Alice 
conosca almeno 3 messaggi.

> È 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).
No. Posso semplicemente ri-computare le soluzioni del sistema escludendo via 
via una sola equazione. Quando ottengo un sistema coerente , l' esclusa è 
quella che ha generato l' inconsistenza.

> In sintesi, abbiamo identificato due problemi:
> - identificazione del bad user, cioè chi mi manda i dati sbagliati
Risolto con N computazioni di un sistema lineare di N-1 equazioni.

> - 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.
Anche questo , Risolto con N computazioni di un sistema lineare di N-1 
equazioni. Dato che la codifica è uno XOR il costo computazionale è 
trascurabile.

> 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.
In realtà ne ho solo N*(N-1) , che è tanto  , ma è MOLTO meno di 2^N
Altro problema , se non so quali sono i due messaggi in XOR , non posso 
decidere con quale hash confrontarli per sapere se sono sani...
> 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).
Proprietà necessaria.O esiste un isomorfismo , facilmente calcolabile , tra lo 
spazio delle firme che è conservativo rispetto allo XOR , oppure non si 
riesce a fare il controllo.

> 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).
Mi sfugge come mai non si possa identificare il mittente : c'è un qualche 
meccanismo per fare sì che chi mi consegna i dati nasconda l' identità di chi 
me li ha mandati? in quel caso si trasforma di un problema legato a garantire 
l' identità del mittente.

> 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?
Affinche una funzione sia xor distributive deve essere lineare , proprietà che 
eviterei in una hash.

> 2) Trovare alcuni rilassamenti ai requisiti che ci permettono di
> trovare una soluzione più semplice.
Controllare l' integrità dei messaggi inviati risolvendo il sistema lineare 
principale e controllando con le hash dei messaggi che posso avere perchè 
pubblicate : questo costa 
messaggi ok -> una decodifica,n confronti con le hash
messaggi faulty -> una decodifica , al peggio N decodifiche di N-1 messaggi , 
N*N-1 confronti con le hash singole.

Cheers 

Alex


-- 
"I computer sono incredibilmente veloci, accurati e stupidi. Gli  
uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme  
sono una potenza che supera l'immaginazione." 
						
						---Albert Einstein