Comment identifier efficacement un fichier binaire

Question

Quel est le moyen le plus efficace d'identifier un fichier binaire ? J'aimerais extraire une sorte de signature d'un fichier binaire et l'utiliser pour le comparer à d'autres.

L'approche par force brute consisterait à utiliser l'ensemble du fichier comme signature, ce qui prendrait trop de temps et de mémoire. Je cherche une approche plus intelligente de ce problème, et je suis prêt à sacrifier un peu de précision (mais pas trop, ey) pour la performance.

(les exemples de code Java sont préférables, mais les réponses indépendantes du langage sont encouragées)

Éditer : L'analyse de l'ensemble du fichier pour créer un hachage présente l'inconvénient que plus le fichier est volumineux, plus cela prend de temps. Comme le hash ne serait de toute façon pas unique, je me demandais s'il existait une approche plus efficace (c'est-à-dire un hash à partir d'un échantillonnage d'octets uniformément distribués).

Answer 1

Une approche que j'ai trouvée efficace pour ce genre de choses consiste à calculer deux hachages SHA-1. L'un pour le premier bloc d'un fichier (j'ai choisi arbitrairement 512 octets comme taille de bloc) et l'autre pour l'ensemble du fichier. Je stockais ensuite les deux hachages avec la taille du fichier. Lorsque je devais identifier un fichier, je comparais d'abord la longueur du fichier. Si les longueurs correspondent, je compare le hachage du premier bloc et si c'est le cas, je compare le hachage du fichier entier. Les deux premiers tests ont permis d'éliminer rapidement un grand nombre de fichiers ne correspondant pas.

Answer 2

C'est ce que hachage est destiné à. Voir aussi MessageDigest .

Notez que si votre fichier est trop volumineux pour être lu en mémoire, ce n'est pas grave car vous pouvez envoyer des morceaux du fichier à la fonction de hachage. MD5 et SHA1, par exemple, peuvent prendre des blocs de 512 bits.

Par ailleurs, deux fichiers ayant le même hash ne sont pas nécessairement identiques (il est très rare qu'ils ne le soient pas), mais deux fichiers identiques ont nécessairement le même hash.

Answer 3

La réponse habituelle est d'utiliser MD5, mais j'aimerais suggérer qu'il y a trop de collisions pour utiliser MD5 dans les applications modernes : http://www.mscs.dal.ca/~selinger/md5collision/

SHA-1 a remplacé MD5 il y a plus de dix ans.

Le NIST a recommandé en 2005 que SHA-2 soit utilisé à la place de SHA-1 d'ici 2010, en raison des travaux réalisés pour démontrer les collisions dans les variantes réduites de SHA-1. (Il s'agit là d'une très bonne anticipation, puisqu'il s'agit de maintenant connu qu'il faut 2^51 travaux pour trouver des collisions dans ce qui devrait idéalement nécessiter 2^80 travaux pour trouver des collisions).

Alors s'il vous plaît, en fonction de ce que vous essayez de faire et des autres programmes avec lesquels vous pourriez avoir besoin d'interopérer, choisissez entre MD5 (s'il vous plaît, non), SHA-1 (je comprendrais, mais nous pouvons faire mieux), et SHA-2 (choisissez-moi ! choisissez-moi !).

Answer 4

Tenez-vous compte de l'utilisation de l'identification de l'en-tête. Si vous pouvez concevoir vos fichiers de cette manière, ils seront rapides et fiables. Avec un octet, vous pouvez distinguer 255 types de fichiers ;)