Recherche par blocs

La recherche par blocs est une méthode récente (Garfinkel, DFRWS 2010), les outils existant depuis quelques années seulement. Elle repose sur la notion de blocs discriminants et l'identification de la présence de ces blocs sur un support de stockage.

Recherche générale

Un fichier est une succession de blocs de stockage sur le support. Il est donc possible de descendre d'un niveau dans la recherche par condensat : plutôt que chercher un fichier dont le contenu (suite de blocs de stockage) correspond à un certain condensat, on recherche les blocs de stockage. Il suffit de calculer, pour chaque bloc constituant le fichier cherché, le condensat SHA1 et de rechercher des blocs ayant le même condensat. Cette recherche s'affranchit de la notion de système de fichiers, qui peut même avoir été effacé.

Au-delà d'un certain pourcentage de correspondance, la probabilité de présence (ou de transit) du fichier sur le support devient une certitude.

Blocs discriminants

Il est à noter qu'il existe environ 10¹²³³ blocs de 512 octets différents (2^8*512). Nous pouvons donc définir la notion de bloc discriminant comme étant un bloc de données à forte entropie, et donc statistiquement "unique".

Ainsi,

1. si sur un support de stockage on identifie ne serait-ce qu'un seul bloc discriminant issu d'un fichier connu, cela constitue la preuve que le fichier est ou a été présent sur le support en question.
2. si le contenu d'un fichier est produit par un processus à forte entropie, et si l'on peut prouver que les blocs qui composent ce fichier sont discriminants par rapport à un corpus connu et étoffé, alors les blocs du fichiers sont discriminants.

L'image de gauche est composée de 183075 octets, soit 45 blocs de 4096 octets. Tous les blocs ont un condensat MD5 différent.

$ perl md5blocs.pl Exemple-1.jpg
45 blocs et 183075 octets lus
0 collisions de condensats

A l'inverse, l'image de droite est composée de 7695 octets, soit 16 blocs de 512 octets. Il y a 13 collisions de condensats, ce qui ne devrait guère étonner le lecteur.

$ perl md5blocs.pl Exemple-3.jpg
Bloc 2, MD5 identique à 1
Bloc 3, MD5 identique à 1, 2
Bloc 4, MD5 identique à 1, 2, 3
[...]
Bloc 14, MD5 identique à 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
Exemple-3.jpg
16 blocs et 7695 octets lus
13 collisions de condensats

Les deux fichiers ci-dessous sont visuellement identiques (mêmes hauteurs et largeur, même sujet), le contraste ayant été légèrement modifié sur la seconde photo. Il n'y a aucune collision de condensats entre les deux fichiers.

$ perl md5blocs.pl Exemple-1.jpg Exemple-1bis.jpg
Exemple-1.jpg : 45 blocs et 183075 octets lus
0 collisions de condensats
Exemple-1bis.jpg : 45 blocs et 182891 octets lus
0 collisions de condensats
0 collisions inter-fichiers

Il existe de très nombreux processus produisant des fichiers contenant des blocs discriminants. Nous pouvons citer

• des fichiers vidéos, musicaux, photographiques
• des fichiers chiffrés
• des fichiers contenant quelques caractères aléatoires (il existe 10³³ blocs différents contenant 500 zéros et 12 espaces).

A l'inverse, il existe de nombreux fichiers sans blocs discriminants :

• contenu constant
• répétition de motifs

Sur un support de stockage, les fichiers sont alignés sur des frontières de blocs (généralement de 512 octets). Si un fichier contient des blocs discriminants, les blocs de stockage associés seront aussi discriminants.

En conclusion, trouver un bloc de stockage discriminant associé à un fichier recherché est la preuve que le fichier a été (ou est toujours) présent sur le support de stockage.