INFORMATICA - HASH & SIMILARITY-HASH

Le funzioni di hash trovano largo impiego nel digital forensics ma anche quelle di Similarity Hash si stanno facendo strada nei diversi tool forensi come ausilio di notevole utilità e dai diversi sbocchi.

Agosto 2013

Le cryptographic hash function trovano una miriade di applicazioni nel settore elettronico, informatico, telematico e matematico. Una semplice definizione è su wikipedia.org: "...an algorithm that takes an arbitrary block of data (message) and returns a fixed-size bit string, the (cryptographic) hash value or digest, such that any (accidental or intentional) change to the data will (with very high probability) change the hash value."

Le caratteristiche desiderate per queste funzioni/algoritmi dal punto di vista operativo sono: (a) una notevole efficienza dal punto di vista del calcolo mediante elaboratore; (b) l'impossibilità pratica di determinare messaggi con digest predefiniti; (c) l'impossibilità pratica di determinare modifiche ad un messaggio per averne un digest predefinito; (d) l'impossibilità pratica di trovare due messaggi differenti che determinino lo stesso digest.
Prego far attenzione alla parola "pratica" che è stata usata per ben 3 volte nei punti precedenti. Tale parola è riferita al fatto di contestualizzare le richieste funzionali allo stato degli elaboratori attuali ed alla loro potenza di elaborazione. Ne consegue che una funzione di hash accettabile in tal senso 20 anni or sono può non esserlo più ora. A questo va aggiunto che le caratteristiche evidenziate non sono indipendenti tra loro ma questo porterebbe ad una trattazione molto complessa e ricca di formalismi matematici per cui dal punto di vista del Digital Forensics è più chiaro evidenziare tali punti separatamente.

Date le caratteristiche precedenti il digest (comunemente indicato come valore di hash) è peculiare di un messaggio per cui lo identifica univocamente. Tale identificazione è di natura binaria nel senso che dati due messaggi M1 ed M2 possono sussistere solo due eventualità:

  • Hash(M1) = Hash(M2) da cui M1 = M2;
  • Hash(M1) <> Hash(M2) da cui M1 <> M2.

Se quindi si realizza la funzione:

  • Compara(M1,M2) = 0 se Hash(M1) <> Hash(M2);
  • Compara(M1,M2) = 1 altrimenti.

si ha che Compara(M1,M2) è binaria e restituisce 0 se i messaggi sono diversi, 1 se i messaggi sono identici. Nessun'altro valore di output è consentito per questo approccio.

Va sottolineato che il concetto di "messaggio" è molto ampio: un messaggio può essere un file, un'intera cartella, un settore di un disco come un frame ethernet... Questo apre un interessante punto: la funzione Compara(.,.) che cosa effettivamente va a paragonare?

A prescindere dal livello di interpretazione più o meno semantico del messaggio la funzione paragona tra loro solo le rispettive stringhe di byte. Un esempio potrà chiarificare meglio e permetterà di introdurre un ulteriore livello di impiego degli hash.

ESEMPIO. Se M1="Marco Mattiucci" ed M2="Mattiucci Marco", Compara(M1,M2) darà il valore 0 perchè la sequenza di byte dal primo all'ultimo che individua i due messaggi, pur avendo delle parti in comune (chunk), è sostanzialmente diversa.

Supponendo di avere una funzione di interpretazione del messaggio che ne stabilisca un aspetto semantico, ad esempio Nome(M), che restituisce i nomi individuati nel messaggio M, la funzione di hash può essere usata in maniera più sofisticata determinando quello che viene chiamato clustering dei messaggi.

ESEMPIO. Se M1="Marco Mattiucci", M2="Mattiucci Marco", M3="Paolo Mattiucci" ed M4="Rossi Marco" si ha:
Compara(Nome(M1),Nome(M2))=1;
Compara(Nome(M1),Nome(M3))=0;
Compara(Nome(M1),Nome(M4))=1;
Compara(Nome(M2),Nome(M3))=0;
Compara(Nome(M2),Nome(M4))=1;
Compara(Nome(M3),Nome(M4))=0;
ossia M1, M2 ed M4 formano un cluster di elementi in qualche modo simili tra loro secondo la data interpretazione.

La situazione studiata vede un primo approccio a quelli che vengono chiamati hash di silmilarità ossia algoritmi di hashing che non determinano esclusioni (identico/diverso) ma valutano somiglianze tra i contenuti (simile a). Nel caso del clustering di cui sopra (molto elementare e con i dovuti suoi limiti) si può ad esempio dire che M1 è più simile ad M2 ed a M4 che a M3 (sempre in base all'interpretazione scelta).

I Similarity Hash restituiscono generalmente valori di somiglianza espressi in percentuale piuttosto che stringhe a lunghezza fissa come gli hash crittografici classici.

Si può realizzare un similarity hash banale con una tecnica quale la seguente: si considerano i messaggi M1 ed M2 iniziali suddividendoli parimenti in N chunk indicati con Chunk(M1,1), Chunck(M1,2), ...,Chunk(M1,N) e Chunk(M2,1), Chunck(M2,2), ...,Chunk(M2,N) e per ogni coppia di chunk si applica Compara(Chunk(M1,i),Chunk(M2,i)) che restituirà 1 solo se i chunk i-esimi sono uguali. Sommando i risultati della funzione Compara(.,.) si avrà il numero totale di chunk che corrispondono, dividendo tale risultato per N si avrà la percentuale di corrispondenze per cui una misura di similarità:
Similarity_Hash(M1,M2) = Somma(Compara(Chunk(M1,i),Chunk(M2,i)) per i=1,...,N) / N.

La teoria dei Similarity Hash è vasta e datata ma purtroppo deve essere fortemente contestualizzata alle aree di lavoro altrimenti diviene poco attendibile ed impiegabile. Classica applicazione la trova nel clustering di file immagine e di documenti di testo (parlando di digital forensics), in alcune applicazioni del data mining, nella teoria dei segnali, ecc.

Anche l'esempio elementare fatto soffre di enormi carenze, dipende moltissimo da come viene generata la partizione in chunk dei messaggi, per cui può immediatamente essere reso più flessibile andando a considerare tutte le divisioni in chunk possibili dei due messaggi, calcolando il Similarity_Hash così come definito ogni volta e prendendo il MAX tra tutti i risultati.

In tal caso, infatti, il Similarity_Hash("Marco Mattiucci","Mattiucci Marco") finale risulterebbe sicuramente uguale a 1, praticamente un'identità e questo introduce altri problemi: è lecito dire che "Marco Mattiucci" e "Mattiucci Marco" sono due messaggi identici? Ovviamente dipende dal contesto interpretativo. Nello stesso modo, infatti, Similarity_Hash("ABCD","ADCB") darebbe sempre 1 e questo come stringa pura (e non nome-cognome) ha poco senso. A ciò va aggiunto che l'algoritmo di calcolo del Similarity_Hash(.,.) proposto vede nell'esplorazione di TUTTI i chunk possibili delle stringhe M1 ed M2 un punto molto critico che lo rende particolarmente pesante e poco efficiente dal punto di vista computazionale.

marcomattiucci.it

Informatica:

Digital Forensics - articoli:

Digital forensics: