Fuzzy Hashing na prática

A ferramenta SSDEEP é uma implementação do conceito de computing context triggered piecewise hashes (CTPH) ou simplesmente fuzzy hashing.

Basicamente, arquivos idênticos possuem determinadas sequências de bits na mesma ordem, sendo que, os intervalos existentes entre tais sequências podem variar. Dessa forma, a aplicação deste conceito possibilita o cálculo de um índice (%) de semelhança entre arquivos.

Mais detalhes sobre o conteito podem ser lidos no artigo “Identifying almost identical files using context triggered
piecewise hashing”
de Jesse Kornblum. É interessante lembrar que, mais um software livre contribuiu para a evolução do conceito e implementação da ferramenta SSDEEP. A matemática (algoritmo) por trás do conceito de fuzzy hashing foi implementada, inicialmente, no software anti-spam spamsum, de Andrew Tridgell, membro do time de desenvolvimento do projeto Samba.

O funcionamento da ferramenta é bastante simples. Primeiro, obtém-se uma base de hashes dos arquivos cuja semelhança precisa ser comparada (calculada em relação a outros arquivos); em seguida, essa base gerada é confrontada com hashes de arquivos alvo, passados como parâmetro do comando ssdeep.

A imagem abaixo representa um dos pinguins, senão “o” pinguim, mais famoso da Internet. (Não sabia disso? Leia aqui). Esta imagem possui milhares ou milhões de variações espalhadas na Internet, com tamanhos e cores diferentes.

Imagem orginal

O comando mostrado a seguir faz com que a base de hash relativa ao arquivo da imagem acima seja armazenada no arquivo hash.db, o parâmetro “-b” faz uso do caminho base do arquivo na saída, em vez do caminho absoluto. Em seguida, o comando cat faz com que o conteúdo do arquivo o qual contém a base seja mostrado:

ssdeep -b tux.png > hash.db

cat  hash.db

ssdeep,1.0--blocksize:hash:hash,filename
768:iglxhcCLWzmTcMgpZ8I6ViE0hbM4jGBpQ4WC8qg4qRkm/JBXUW2yKbfcLHKf9W81:iglxhcCKz8BgUE314iqkkmHX/iLf,"tux.png"

É interessante aqui obtermos o hash da imagem original para que possamos compará-lo posteriormente. Isso é feito por meio do comando abaixo:

md5sum tux.png

526bdc75fa845fff5e9d8356d9c81e0a  tux.png

Em seguida, utilizamos a ferramenta exiftool para visualizar e manipular metadados da imagem. A ideia é adicionarmos um valor qualquer à TAG “Author” da imagem (que está em branco). Para visualizar os metadados da imagem original, utiliza-se a sintaxe abaixo:

exiftool tux.png

ExifTool Version Number         : 8.00
File Name                       : tux.png
Directory                       : .
File Size                       : 42 kB
File Modification Date/Time     : 2009:10:23 00:53:43-04:00
File Type                       : PNG
MIME Type                       : image/png
Image Width                     : 334
Image Height                    : 393
Bit Depth                       : 8
Color Type                      : RGB with Alpha
Compression                     : Deflate/Inflate
Filter                          : Adaptive
Interlace                       : Noninterlaced
Background Color                : 255 255 255
Modify Date                     : 2007:03:23 03:03:21
Image Size                      : 334x393

Para inserirmos a TAG “Author”, basta execuarmos o seguinte comando:

exiftool -Author=Zm9yZW42LndvcmRwcmVzcy5jb20K tux.png

1 image files updated

Perceba que agora o valor da TAG é listada na saída:

exiftool tux.png  | grep Author

Author                          : Zm9yZW42LndvcmRwcmVzcy5jb20K

E o valor hash é alterado (“completamente”, lógico):

md5sum tux.png

963fcf85297dfb6859865d9cc638c620  tux.png

Neste momento, podemos realizar a análise com o SSDEEP. Iremos comparar a base de hash na qual está contido o hash da imagem original (sem a TAG “Author”) com o arquivo da imagem modificada. Perceba o resultado:

ssdeep -bm hash.db tux.png

tux.png matches tux.png (99)

O valor entre parênteses (99) representa um “índice de semelhança” entre os arquivos. O texto “tux.png matches tux.png” pode parecer confuso, mas se alterarmos o nome do arquivo, a mudança irá refletir na saída do comando. A imagem final pode ser obtida aqui.

Algumas ferramentas de mercado (comerciais) já se utilizam do mesmo conceito, dentre elas podemos destacar o LTU Finder, ferramenta que produz e manipula o que é chamado pelo fabricante de “DNA Digital”.

Conhece mais alguma ferramenta ou sistema que se utiliza da mesma técnica? Manda aí nos comentários!

3 thoughts on “Fuzzy Hashing na prática

Comments are closed.