Recherche de fichiers connus

Introduction

En cas de concurrence déloyale, de fuite d'informations, il peut être intéressant de déterminer si des supports, par exemple une clé USB saisie, ont contenu certains documents précis. Dans un dossier pénal, il peut être demandé, non pas « qu'y a-t-il sur les supports qui intéresserait le dossier ? », mais « un ou plusieurs fichiers faisant partie de tel ensemble d'images et vidéos connus ont-ils été présents sur les supports saisis ? ». Ces questions ou demandes reviennent à caractériser le transit d'un fichier ou ensemble de fichiers identifiés sur un support informatique (disques durs, clés USB, mémoires SSD, etc.).

La méthode décrite s'applique aussi à un stockage volatil comme de la mémoire vive ou un échange sur un réseau (la difficulté commencera alors par l'appréhension du contenu de la mémoire ou des échanges réseau).

Nous parlerons de recherche de fichiers connus. Elle se fait usuellement a posteriori, pour la détection de copies ou de transferts non autorisés, des recherches de traces d'activités délictueuses (contenu protégé, confidentiel ou illégal), etc.

Il existe deux situations :

- le ou les fichiers recherchés sont toujours sur le support de stockage, ils peuvent être cachés ou modifiés ;

- le ou les fichiers ont été présents sur le support, mais ont été effacés.

Les méthodes de recherches peuvent être réparties en deux groupes : dans et hors du système de fichiers.

1. Recherches dans le système de fichiers

Ce sont les recherches les plus classiques. Elles reposent sur l'hypothèse que les fichiers sont toujours sur le support de stockage (pas effacés) et qu'ils présentent une ou plusieurs caractéristiques permettant leur identification. Ces caractéristiques peuvent être externes (nom, type...) ou internes (contenu). Il existe des bases de fichiers connus, identifiés par leurs condensats [1].

Le principal inconvénient est évidemment qu'une telle recherche ne permet pas de détecter des fichiers qui ont été présents et sont effacés. Un second écueil est que le nom, la date de création ou de modification peuvent facilement être changés ; la moindre modification du contenu du fichier altère son condensat.

Malgré ces défauts, ces recherches ne sont pas à négliger : dans les cas simples, elles permettent d'obtenir rapidement des résultats. Comme elles peuvent être facilement mises en échec, elles ne constituent pas un outil approprié à toutes les situations.

2. Recherches hors du système de fichiers

La recherche en dehors du système de fichiers est proche de la restauration de fichiers effacés. On parle aussi de data carving, que l'on peut traduire par extraction de données[2].

PhotoRec [3] 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 « signatures » 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'améliorations peuvent être apportées à l'algorithme ci-dessus, l'idée restant la même.

Lorsque l'on examine l'ensemble d'un support (et pas uniquement les blocs libres qu'il contient), une extraction renverra la totalité des fichiers présents ainsi que ceux qui ont été effacés, mais peuvent être reconstruits. Sur un disque récent, le nombre de fichiers obtenus peut facilement dépasser la centaine de milliers. Une phase de nettoyage, par exemple à base de condensats de fichiers connus et innocents, est souvent nécessaire.

Même si elle permet de trouver des fichiers 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 donne de bons résultats.

3. Recherche par blocs

La recherche par blocs est récente [4]. Elle repose sur la notion de blocs discriminants et l'identification de ces blocs sur un support de stockage.

3.1 Principe général

Un fichier est composé d'un ensemble de blocs de stockage sur un support. Plutôt que chercher un fichier dont le contenu correspond à un certain condensat, on recherche les blocs qui le composent. Cette recherche s'affranchit complètement de la notion de système de fichiers.

Au-delà d'un certain pourcentage de blocs trouvés, la probabilité de présence/transit du fichier sur le support devient une certitude.

3.2 Blocs discriminants

Il existe environ 10¹²³³ blocs de 512 octets différents (2^8*512). Nous définissons un bloc discriminant comme étant un bloc à forte entropie, et donc statistiquement unique.

Ainsi,

1- si 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.

2- si le contenu d'un fichier est produit par un processus à forte entropie, et si l'on prouve que les blocs qui composent ce fichier sont discriminants par rapport à un corpus connu et étoffé, alors les blocs du fichier sont discriminants.

La photo de la figure 1 est composée de 183075 octets, soit 45 blocs de 4096 octets. Tous les blocs ont un condensat MD5 différent.

À l'inverse, la photo de la figure 2 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.

La photo de la figure 3 est identique à celle de la figure 1 (même taille, même sujet), le contraste ayant été légèrement modifié. Il n'y a aucune collision de condensats entre les deux fichiers.

De nombreux processus produisent des fichiers contenant des blocs discriminants, même si le fichier n'est pas toujours constitué uniquement de blocs discriminants :

- fichiers vidéos, musicaux, photographiques ;

- fichiers chiffrés ;

- fichiers contenant quelques caractères aléatoires (il existe 10³³ blocs différents contenant 500 zéros et 12 espaces).

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

- contenu constant ;

- répétition de motifs.

En conclusion, trouver sur un support un bloc discriminant associé à un fichier connu est un signe très fort que le fichier a été (ou est toujours) présent sur le support. Trouver plusieurs blocs discriminants amène à une quasi-certitude.

4. En pratique

4.1 Frag_find

L'outil frag_find [5] recherche les blocs composant un ou plusieurs fichiers. Si ces fichiers ont transité sur le support examiné, et ont été effacés, il reste 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 recherche sera toujours un succès.

Le principe de fonctionnement est :

- pour chacun des fichiers recherchés, calcul des condensats des blocs de 512 octets qui le compose ;

- examen du support, et calcul du condensat de chacun des blocs de 512 octets qui le compose ;

- détection des collisions de condensats.

4.2 Utilisation de la détection de blocs

La détection de blocs permet d'identifier le transit de fichiers connus sur un support de stockage, par l'identification des blocs qui les composent. Ses principaux avantages sont :

- 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 fichiers originaux est garantie.

- Peu voire pas de faux positifs, pour peu que l'on ait nettoyé la liste des condensats à chercher afin d'en retirer ceux des blocs non discriminants.

- Abaissement de l'espace de stockage nécessaire : une clé USB de 32Go peut contenir plusieurs centaines de millions de condensats pré-calculés.

5. Analyse probabiliste

5.1 Principe

La recherche par blocs présente un inconvénient significatif : il faut examiner l'ensemble du support. Autant une clé USB de 16Go sera traitée rapidement, autant un disque de 4To demandera beaucoup plus de temps.

Si l'on garde à l'esprit que l'identification d'un seul bloc discriminant prouve le transit ou la présence du fichier contenant ce bloc, une recherche par échantillonnage prend du sens. Cependant, comme l'on n'examine plus l'intégralité du support de stockage, il faut dimensionner l'échantillon, au risque sinon d'un faux négatif. 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é.

Supposons :

- un support de stockage de 1,5 Tio, soit 3 x 10⁹ blocs de stockage (512 octets chacun) ;

- 100 fichiers recherchés de 1 Mio chacun, soit 2 x 10⁵ blocs de stockage ;

- un échantillon d'un seul bloc lu au hasard sur le support.

Dans ce cas, la probabilité de succès (le bloc choisi au hasard est l'un des 2 x 10⁵ associés aux fichiers) est de (2 x 10⁵/3 x 10⁹), soit 6.66 x 10^-5. La probabilité d'échec est de (3 x 10⁹ - 2 x 10⁵)/(3 x 10⁹⁾, soit environ 99.993%.

D'une manière générale, avec un support composé de D blocs de stockage, R blocs de stockage pour les fichiers cherchés et un échantillon de n blocs, la probabilité d'échec est égale à

5.2 Calculs de probabilités

Nous supposons, pour nos calculs que les fichiers recherchés sont composés exclusivement de blocs discriminants.

La table 1 donne la probabilité d'échec en fonction de la taille de l'échantillon, pour un support de 1 To et un fichier recherché de 10 Mo (ou de 10 fichiers de 1 Mo chacun). Une telle recherche peut donc se faire par la lecture de 500 000 blocs, avec une probabilité d'échec de 0,6%.

La table 2 indique la probabilité d'échec en fonction de la taille du fichier recherché, sur un support de 1 To avec un échantillon de 10 000 blocs. Il y a environ 8% de risque de passer à côté d'un fichier de 250 Mo, et moins de 0,6% de risque de rater un fichier de 500 Mo.

5.3 Performances

5.3.1 Mesures théoriques

Sur un disque de 2 To connecté en USB2, avec un débit de 40 Mio/s et un fichier recherché de 100 Mio, on devrait obtenir les performances suivantes :

- lecture de l'intégralité du support : 794 minutes. Probabilité de faux négatif nulle.

- échantillon de 10 000 blocs : moins d'une seconde. Probabilité de faux négatif : 60,65%.

- échantillon de 50 000 blocs : moins d'une seconde. Probabilité de faux négatif : 8,20%.

- échantillon de 100 000 blocs : une seconde et demie. Probabilité de faux négatif : 0,67%.

5.3.2 Mesures réelles

Nous avons procédé à des mesures réelles, avec un disque de 2 To connecté en USB2 :

- la lecture de l'intégralité du disque a pris 963 minutes.

- lecture d'un échantillon de 10 000 blocs en 79 secondes.

- lecture d'un échantillon de 50 000 blocs en 317 secondes.

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. L'optimisation de l'accès aux blocs, en fonction de la géométrie du disque, de sa vitesse de rotation, etc. pourrait diminuer les temps de recherche.

Nous avons procédé à 200 recherches, avec un échantillon de 50 000 blocs. 183 ont renvoyé un résultat positif (fichier présent) et 17 un résultat négatif (fichier absent), soit un taux d'échec de 8,5%, proche du taux théorique (8,20%).

Conclusions

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

Dès lors que l'on identifie des blocs discriminants correspondant à un fichier connu, il est possible d'en conclure avec une très grande fiabilité que le fichier en question est présent ou a transité 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. Il est donc intéressant de ne pas lire l'intégralité du support, mais seulement un échantillon de blocs choisis au hasard.

La taille de l'échantillon doit être calculée 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. En cas de détection, le gain de temps est particulièrement intéressant (quelques minutes au lieu de nombreuses heures). En cas 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 envisagées.

Références et liens

[1] National Software Reference Library : http://www.nsrl.nist.gov/

[2] Extraction de données : http://www.sans.org/reading_room/whitepapers/forensics/data-carving-concepts_32969

[3] PhotoRec : http://www.cgsecurity.org/wiki/PhotoRec_FR

[4] DRFWS 2010, Simson Garfinkel : http://www.dfrws.org/2010/proceedings/garfinkel1.pdf

[5] frag_find : http://www.forensicswiki.org/wiki/Frag_find