Comment identifier efficacement un fichier binaire

Question

Quel est le moyen le plus efficace d'identifier un fichier binaire? Je voudrais extraire une sorte de signature d'un fichier binaire et l'utiliser pour le comparer avec d'autres. L'approche par force brute consisterait à utiliser le fichier entier en tant que signature, ce qui prendrait trop de temps et trop de mémoire. Je suis à la recherche d'une approche plus intelligente à ce problème, et je suis prêt à sacrifier un peu de précision (mais pas trop, ey) pour la performance.

(alors que le code-exemples Java sont préférés, les réponses de langue agnostique sont encouragés)

Modifier: Numérisation le fichier entier pour créer un hachage présente l'inconvénient que plus le fichier, plus il faut. Puisque le hachage ne serait pas unique de toute façon, je me demandais s'il y avait une approche plus efficace (c.-à-d. Un hachage à partir d'un échantillonnage uniformément réparti des octets).

Answer 1

Une approche que j'ai trouvé efficace pour ce genre de chose était de calculer deux hachages SHA-1. Un pour le premier bloc dans un fichier (j'ai arbitrairement choisi 512 octets comme taille de bloc) et un pour le fichier entier. J'ai ensuite stocké les deux hachages avec une taille de fichier. Lorsque je devais identifier un fichier, je comparais d'abord la longueur du fichier. Si les longueurs correspondent alors je comparerais le hachage du premier bloc et si cela correspondait j'ai comparé le hachage du fichier entier. Les deux premiers tests ont rapidement éliminé beaucoup de fichiers non correspondants.

Answer 2

C'est pour cela que hashing est pour. Voir MessageDigest.

Notez que si votre fichier est trop volumineux pour être lu en mémoire, c'est OK car vous pouvez charger des morceaux du fichier dans la fonction de hachage. MD5 et SHA1 par exemple peuvent prendre des blocs de 512 bits.

De plus, deux fichiers avec le même hachage ne sont pas nécessairement identiques (c'est très rare qu'ils ne le soient pas), mais deux fichiers identiques ont nécessairement le même hachage.

Answer 3

La réponse habituelle est d'utiliser MD5, mais je voudrais suggérer qu'il ya trop de collisions à utiliser MD5 dans les applications modernes: http://www.mscs.dal.ca/~selinger/md5collision/

SHA-1 remplacé MD5 il y a plus d'une décennie. Le NIST a recommandé en 2005 que SHA-2 soit utilisé à la place de SHA-1 d'ici 2010, en raison du travail qui avait été fait pour démontrer les collisions dans des variants réduits de SHA-1. (Ce qui est une bonne idée, puisque c'est now known qu'il faut 2^51 travail pour trouver des collisions dans ce qui devrait idéalement nécessiter 2^80 travail pour trouver des collisions.)

Donc, s'il vous plaît, en fonction de ce que vous essayez de faites, et quels autres programmes vous devrez peut-être interopérer avec, sélectionnez parmi 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 d'en-tête. Si vous pouvez concevoir vos fichiers de cette façon, ce serait rapide et fiable. En utilisant un octet, vous pouvez distinguer 255 types de fichiers;)