Nous présentons dans cette article une méthode de recherche de fichiers connus permettant à l'enquêteur de rapidement obtenir des réponses en maîtrisant le taux de faux négatif, sans avoir à explorer l'ensemble d'un support de stockage.

Dans de nombreuses investigations, les éléments recherchés se rapprochent de questions du type "tel fichier a-t-il été copié sur tel support". Plus généralement, il s'agit d'identifier le transit (éventuel : rien n'est certain tant que cela n'est pas prouvé)  d'un fichier ou ensemble d'informations sur un équipement informatique particulier (ou un ensemble d'équipements, que l'on peut analyser composant par composant). Si, dans cet article, nous évoquons souvent les supports de stockage classiques (disques durs, clés USB, mémoires SSD, etc.), la méthode décrite peut  s'appliquer à un stockage temporaire comme de la mémoire vive ou un transit sur un réseau.

Nous parlerons de façon générale de recherche de fichiers connus afin de décrire cet ensemble d'activités.

 La recherche de fichiers connus est souvent faite a posteriori :

• détection de copies ou (dans le cas d'un traitement en temps réel sur des paquets réseaux) de transferts non autorisés
• recherche de traces d'activités délictueuses (contenu protégé, confidentiel ou illégal).

D'une façon générale, on est confronté à deux types de situations :

• le ou les fichiers recherchés sont toujours sur les supports de stockage, mais ils peuvent être cachés ou avoir été modifiés,
• le ou les fichiers ont été présents sur les supports (nous dirons qu'ils ont transité sur les supports), mais ont été effacés.

Les méthodes de recherches peuvent elles-aussi être réparties en deux grands groupes :

• recherches dans le système de fichiers,
• recherches hors du système de fichiers.

Recherches dans le système de fichiers

Il s'agit des recherches les plus classiques, que tout utilisateur peut lancer.  Il ne pourra cependant faire ses recherches que dans des répertoires auxquels il a accès, ce qui justifie l'utilisation d'un compte privilégié si l'on souhaite examiner tout un support de stockage. Ces recherches reposent sur l'hypothèse que les fichiers

1. sont toujours présents sur le support de stockage, et
2. présentent une ou plusieurs caractéristiques qui permet leur identification.

Ces caractéristiques peuvent être externe (nom, type) ou internes (contenu). Ce sont typiquement les critères de recherche qui seront utilisés.

Recherches sur des caractéristiques externes

Une commande find bien rédigée permettra de trouver le ou les fichiers (sous réserve que l'opérateur dispose des droits d'accès appropriés pour examiner l'ensemble des fichiers et répertoires du support) :

find / -name -type f -name 'Fichier clients.ods'
find /mnt/disque_externe -size +100M -size -110M

Cependant, une telle recherche se heurte à deux écueils majeurs :

1. si le fichier a été effacé, il ne pourra pas être retrouvé : il n'est plus présent dans le système de fichiers.
2. si les caractéristiques sur lesquelles la recherche repose ont été modifiées, le fichier ne sera pas trouvé.

Or, les caractéristiques sur lesquelles la recherche est faite (via find ou tout autre outil) sont très faciles à modifier.

Recherches sur des caractéristiques internes

Si le fichier recherché est connu, son contenu est lui-aussi connu. Il est donc facile d'en calculer un condensat (MD5, SHA1 ou autre) et d'examiner l'ensemble du système de fichiers à la recherche d'un fichier présentant le même condensat. Des outils comme tripwire ou Aide reposent sur le même principe (dans une optique différente de détection de modifications apportées aux fichiers ou répertoires scellés par l'outil).

La détection de plusieurs fichiers peut se faire en une seule passe, pour peu que l'on a calculé au préalable les condensats des cibles cherchées.

Cette méthode peut être utilisée à l'envers, afin d'éliminer de l'arbre des recherches tous les fichiers connus et innocents. Il existe des bases de données de condensats, comme la NSRL (www.nsrl.nist.gov). Après une passe sur le système de fichiers et élimination des fichiers ayant un condensat présent dans la base de données des innocents, les fichiers restants sont ceux de l'utilisateur (à analyser), des fichiers système spécifiques (fichiers de configuration, base de registres) ou des fichiers suspicieux.

Cette méthode de recherche se heurte de nouveau à deux écueils :

1. si le fichier a transité sur le support, mais a été effacé, il ne sera pas détecté
2. la moindre modification du contenu du fichier altère son condensat, empêchant alors sa détection.

Conclusions sur les recherches simples

Ces recherches ne sont pas à négliger, car dans les cas simples elles permettent d'obtenir rapidement des résultats. Toutefois, elles peuvent être très facilement mises en échec, et ne constituent donc pas un outil approprié dans la majorité des situations. Le principal inconvénient est évidemment qu'une telle recherche ne permet pas de trouver des fichiers qui auraient été effacés.

Recherches en-dehors du système de fichiers

La recherche en-dehors du système de fichiers est très proche de la restauration de fichiers effacés. L'expression usuellement consacrée est celle de data carving, que l'on peut traduire par extraction de données. La recherche peut être faite sur l'intégralité du support (système de fichiers et espace libre) ou, pour la restauration d'un fichier récemment effacé, uniquement dans l'espace libre du système de fichiers (blocs non affectés).

L'extraction de données repose sur plusieurs hypothèses, qui doivent être respectées à divers degrés :

1. les fichiers disposent d'un en-tête discriminant, qui n'a pas été détruit (ce qui est le cas si le fichier est toujours présent dans le système de fichiers, mais peut ne plus être vrai si le fichier a été effacé et les blocs de stockage ayant contenu le début du fichier ont été réattribués à d'autres fichiers)
2. le fichier n'est pas ou très peu fragmenté sur le disque dur
3. le fichier n'est ni compressé, ni chiffré.

Le programme photorec, de Christophe Grenier, est un bon exemple d'outil d'extraction de données.

Le fonctionnement général d'un tel outil est le suivant :

1. parcours du support et identification des "en-têtes" des fichiers (JPG, GIF, MP3, bureautique, etc.)
2. calcul, si possible, de la taille du fichier à partir des informations trouvées dans l'en-tête de celui-ci
3. extraction des N blocs de données qui suivent l'en-tête.

Un certain nombre d'optimisations et d'améliorations peuvent être apportées à l'algorithme général ci-dessus, l'idée restant toujours la même.

Une extraction sur un support de stockage, lorsque l'on examine l'ensemble du support (et pas uniquement les blocs libres qu'il contient) renverra la totalité des fichiers présents sur le support, plus ceux qui ont été effacés mais peuvent être identifiés à partir de leur en-tête. Autant dire que, sur un disque moderne contenant un système d'exploitation, le nombre de fichiers extraits par l'outil peut facilement dépasser la centaine de milliers. Une phase de nettoyage, par exemple à base de condensats de fichiers connus et innocents, est absolument nécessaire.

Même si elle permet de trouver des fichiers qui ont été effacés, la méthode d'extraction de données présente plusieurs inconvénients :

• elle n'est vraiment efficace que si les fichiers cherchés contiennent des marqueurs particuliers (en-têtes ou autres structures facilement identifiables) et, pour les fichiers effacés, que ces marqueurs ont été préservés (les blocs les contenant n'ont pas encore été recyclés)
• elle produit de très nombreux faux positifs, qu'il faut vérifier un par un
• plus le délai depuis l'effacement des fichiers cherchés est long, plus la probabilité de retrouver les fichiers diminue.

Dans une situation où les fichiers cherchés sont toujours présents sur le support ou ont été récemment effacés, l'extraction de données permet d'obtenir de bons résultats, sous réserve de procéder à la validation des fichiers renvoyés.

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.

En pratique

Frag_find

L'outil frag_find (code source dans la bibliothèque bloom) réalise une recherche basée sur les condensats des blocs composant un ou plusieurs fichiers. Si les fichiers recherchés ont transité sur le support que l'on examine, puis ont été effacé, il est particulièrement probable que l'on en retrouvera des bribes sous la forme de blocs non encore réalloués à d'autres fichiers. Si les fichiers sont  toujours présents, la réussite de la recherche n'en sera que meilleure.

Le principe de fonctionnement de frag_find est le suivant :

1. pour chacun des fichiers recherchés, calcul des condensats des blocs de 512 octets qui le compose. Cette liste de condensats est stockée en mémoire.
2. examen de l'image disque (du support), et calcul du condensat de chacun des blocs de 512 octets qui le compose.
3. détection des collisions de condensats.

Si un même bloc (du support) produit un condensat que l'on retrouve dans plusieurs des fichiers recherchés, le bloc sera affecté au fichiers ayant accumulé le plus grand nombre de condensats identifiés. Nous soulignons que cela signifie probablement que le bloc de données en question n'est pas discriminant (ou que les fichiers recherchés sont très semblables entre eux, par exemple des version successives d'une même image ou document).

Utilisation de la détection de blocs

La détection de blocs, sur le principe de celle réalisée par frag_find, permet d'identifier le transit de fichiers précis sur un support de stockage. Elle peut être étendue à une détection en temps réel :

• avec des pilotes de disque modifiés, qui peuvent calculer le condensat de chacun des blocs lus sur le disque et donc détecter la présence d'un condensat connu. Les performances obtenues (temps d'accès aux informations) seraient probablement désastreuses, mais la possibilité existe. L'intérêt d'une telle utilisation nous paraît donc limité - ce qui ne disqualifie pas pour autant l'idée.
• sur des échanges au travers d'un réseau. S'il existe un système de stockage de documents sensibles (un serveur de fichiers par exemple), il est possible de détecter que l'un des fichiers est en cours de transfert vers un poste qui ne devrait pas en réaliser lecture ou copie.

Les grands avantages de la détection de blocs, par identification de leurs condensats, sont les suivants :

• il n'est pas nécessaire de fournir les fichiers originaux au système de détection. Il suffit de calculer les condensats des blocs de stockage, et de fournir cette liste. La confidentialité des documents peut être protégée, y compris dans le cadre d'une procédure officielle (recherche du transit de documents très sensibles sur un ordinateur personnel par exemple).
• très peu de faux positifs, pour peu que l'on a nettoyé la liste des condensats afin d'en retirer ceux correspondants à des blocs non discriminants. L'expérience nous fait dire (c'est à confirmer dans la durée) que les blocs non discriminants seront souvent détectés sur des supports quelconques. Il suffit donc de quelques passes de pseudo-détection sur des supports dont on est certain qu'ils n'ont jamais contenu les fichiers recherchés pour identifier les blocs non discriminants et les éliminer.
• abaissement de l'espace de stockage nécessaire : une clé USB de 4Go peut contenir plusieurs centaines de millions de condensats pré-calculés.

Analyse probabiliste

Principe

Malgré les avantages et qualités évoqués précédemment, la recherche par blocs telles qu'elle a été décrite présente un inconvénient significatif : on examine l'ensemble du support de stockage. Autant une clé USB de 16Go sera traitée relativement rapidement, autant un disque de 2To demandera beaucoup plus de temps.

Si l'on garde présent à l'esprit que l'identification d'un seul bloc discriminant sur le support prouve le transit du fichier associé à ce bloc, la notion d'une recherche par échantillonnage prend tout son sens. Cependant, dès lors que l'on n'examine pas l'intégralité du support de stockage, il faut bien calibrer l'échantillonnage du disque, au risque sinon d'un faux négatif (non détection alors que le fichier recherché a bel et bien été présent sur le support). Nous appellerons probabilité d'échec la probabilité de conclure, de façon erronée, que le fichier n'a pas transité sur le support examiné. La probabilité d'échec ne peut être annulée que par une analyse exhaustive du support.

Supposons que

• on prend un support de stockage de 1,5 Tio, soit 3 x 10⁹ blocs de stockage (512 octets chacun),
• le fichier recherché fait 100 Mio, soit 2 x 10⁵ blocs de stockage,
• l'échantillon contient un seul bloc.

Dans ce cas, la probabilité de succès (le bloc choisi au hasard est l'un des 2 x 10⁵ associés au fichier) est de (2 x 10⁵/3 x 10⁹), soit 6.66 x 10^-5. Autant dire que ce n'est pas très élevé. La probabilité d'échec est de (3 x 10⁹ - 2 x 10⁵)/3 x 10⁹, soit environ 99.993%.

D'une manière plus générale, si l'on prend un support composé de D blocs de stockage, un fichier recherché utilisant R blocs de stockage et un échantillonnage de n blocs sur le support, la probabilité d'échec (aucun des blocs du fichier n'est identifié) est égale à

Calculs de probabilités

Si l'on prend un support de 1To et un fichier recherché de 10 Mo, les probabilités de passer à côté du fichier alors qu'il est présent, en fonction de la taille de l'échantillon, sont les suivantes :

Taille échantillon	Proba échec
1	0.999990	99,999%
100	0.999000	99,900%
1000	0.990050	90,004%
10000	0.904837	90,484%
100000	0.367868	36,787%
200000	0.135320	13,532%
300000	0.049775	4,977%
400000	0.018308	1,831%
500000	0.006733	0,673%

La recherche d'un fichier de 10Mo sur un support de 1To peut être réalisée par la lecture de 500000 blocs seulement, avec une probabilité d'échec de 0,6%.

Toujours sur un support de 1To, avec un échantillonnage sur 10000 blocs, les probabilités d'échec en fonction de la taille du fichier recherché sont :

Taille fichier	Proba échec
10 Mo	0.904837	90,484%
50 Mo	0.606522	60,652%
100 Mo	0.367860	36,786%
150 Mo	0.223104	22,310%
200 Mo	0.135308	13,531%
250 Mo	0.082059	8,206%
300 Mo	0.049764	4,976%
400 Mo	0.018301	1,830%
500 Mo	0.006729	0,673%

Sur un support de 1To et avec un échantillon de 10000 blocs, il y a environ 8% de risque de passer à côté d'un fichier de 250 Mo, et moins de 0,7% de risque de rater un fichier de 500 Mo.

Mesures de performances

Mesures théoriques

Sur un disque de 2 To connecté en USB2, avec un débit soutenu de 40 Mio/s (soit la lecture 82000 blocs de stockage par seconde) et un fichier recherché de 100 Mo, on devrait obtenir les performances suivantes :

• la lecture de l'intégralité du disque dur prendra 794 minutes (13 heures 14 minutes et 43 secondes). La probabilité d'échec est nulle.
• la lecture d'un échantillon de 10000 blocs prendra moins d'une seconde. Probabilité d'échec : 60,65%.
• la lecture d'un échantillon de 50000 blocs prendra moins d'une seconde. Probabilité d'échec : 8,20%.
• la lecture d'un échantillon de 100000 blocs prendra une seconde et demie. Probabilité d'échec : 0,67%.

Mesures réelles

Nous avons procédé à des mesures réelles, avec un disque de 2 To connecté en USB2 et un fichier recherché de 100 Mio ayant été effacé :

• intégralité du disque lue en 963 minutes (probabilité d'échec nulle).
• échantillon de 1000 blocs lu en 13 secondes (probabilité d'échec de 95,12%).
• échantillon de 10000 blocs lu en 79 secondes (probabilité d'échec de 60,65%).
• échantillon de 100000 bolcs lu en 712 secondes (11 minutes 52 secondes), probabilité d'échec de 0,67%.

Les mesures montrent que les performances du support sont déterminantes pour la durée de la recherche. L'essentiel du temps d'attente est lié au temps de recherche d'un bloc sur le disque. La vitesse de transfert (USB2, USB3, Sata) n'a que peu d'impact.

Nous avons procédé à 100 recherches par échantillonnage, avec un échantillon de 100000 blocs. Sur ces 100 recherches, 72 ont renvoyé un résultat positif (fichier présent) et 28 un résultat négatif (fichier absent), soit un taux d'échec de 38,8%, proche du taux théorique.

Conclusions

La recherche par blocs permet de s'affranchir des limitations des recherches classiques de fichiers connus.

Dès lors que l'on identifie un ou plusieurs blocs discriminants correspondant à un fichier connu, il est possible d'en conclure avec une très grande fiabilité que le fichier en question est ou a été sur le support examiné. Plus le nombre de blocs identifiés est important, plus la conclusion est fiable.

La durée d'une recherche par blocs se faisant sur l'intégralité d'un support de stockage est une fonction linéaire de la taille du support. Ainsi, une recherche sur un support de 1,5 Tio durera environ 10 heures. Il devient alors intéressant de ne pas lire l'intégralité du support, mais seulement un échantillon choisi au hasard parmi tous les blocs de stockage.

La taille de l'échantillon doit être choisie en fonction de la taille du support, de la taille du fichier recherché et du niveau considéré acceptable de risque de faux négatif. Cette probabilité d'échec pouvant être calculée, en fonction des trois paramètres que sont la taille du support, la taille du fichier recherché et le nombre d'échantillon, l'enquêteur peut facilement décider de la taille de l'échantillon qu'il va exploiter. En cas de détection, le gain de temps est particulièrement intéressant (quelques minutes au lieu de plusieurs heures). Dans le cas inverse de non détection, si l'enquêteur craint qu'il ne s'agisse d'un faux négatif, il peut toujours lancer une recherche sur l'intégralité du support. Il n'aura perdu que quelques minutes pour la recherche par échantillonnage.

Le principal problème de la recherche par échantillonnage se situe au niveau du temps d'accès aux blocs du support à analyser. Dans nos tests, un simple ordonnancement des blocs à lire (après un choix aléatoire) a permis de diviser par trois le temps d'exécution du programme. D'autres optimisations, en fonction des caractéristiques physiques du support, peuvent probablement être réalisées.

Références

• Extraction de données
• PhotoRec
• DRFWS 2010, présentation de Simson Garfinkel