Hachage rapide: combinaison de différentes techniques pour identifier les changements dans un fichier?

9

Je veux créer un moyen rapide de détecter si un fichier peut ou non être le même. Pour une sécurité de près de 100%, j'utiliserais un algorithme de hachage existant, par exemple SHA256. Cependant, les fichiers devraient être des fichiers vidéo énormes avec plusieurs Go, donc le calcul du hachage SHA256 pourrait prendre un certain temps, en particulier sur le réseau.

Je souhaite donc combiner différentes autres techniques:

  • taille du fichier: si la taille du fichier a changé, le contenu a changé (bien sûr)
  • hachage tête / queue
  • hachage aléatoire

Les 2 derniers font partie de ma question:

Je suppose que dans l'en-tête il y a des choses comme:

  • fréquences d'images (par exemple, vidéos)
  • résolution (p. ex. vidéos, images)
  • (fichier) longueur (par exemple dans les cadres, pixels, etc.)
  • dernière date de modification (par exemple, des documents Word, pas spécifiquement des vidéos)

Pourquoi je considère la vérification de la queue:

  • MP3 contient les informations d'étiquette
  • EXIF ajoute des données personnalisées à la fin si j'ai raison

Les hachages aléatoires sélectionneraient par exemple 126 régions à des positions aléatoires dans le fichier avec une longueur spécifique, par exemple 64 Ko et créeraient un hachage pour elles. Bien sûr, je me souviens des décalages pour une comparaison ultérieure. Dans l'ensemble, j'utiliserais (1 + 126 + 1) * 64 Ko de données pour mon hachage, j'ai donc besoin de lire seulement 8 Mo au lieu de plusieurs Go pour obtenir le hachage.

C'est peut-être plus une question mathématique maintenant, mais: quelle est la probabilité de détecter un changement en utilisant la combinaison de la taille du fichier, de la tête, de la queue et des données aléatoires pour générer cette somme de hachage rapide?

Je suppose que les fichiers sont toujours des fichiers légaux. Il n'y a aucun avantage à manipuler des octets uniques. L'utilisateur utiliserait un outil d'édition vidéo normal pour modifier les fichiers.

MISE À JOUR : J'ai refusé cette réponse qui venait de Crypto.StackExchange. J'accepte que ma proposition ne soit pas cryptographique et ne soit pas destinée à être sécurisée. Je suis également d'accord que CRCing un fichier est rapide, mais dans mon cas, j'ai vraiment besoin d'un hachage - je vais expliquer pourquoi:

  • On s'attend à ce que mon application enregistre des signets dans des vidéos. Ma base de données devrait enregistrer le hachage vidéo et les signets.
  • Les utilisateurs déplacent ou renomment parfois des fichiers. Mon programme remarquera qu'un fichier n'existe plus, mais ne supprimera pas les signets de la base de données. Au lieu de cela, lorsque la même vidéo est (accidentellement) rejouée, je veux reconnaître que c'est (probablement) le même fichier.
  • Les utilisateurs sont censés enregistrer des fichiers sur des lecteurs réseau (NAS) et diffuser des vidéos. Ce sont des stockages stupides. Je ne peux pas installer de composant serveur. Et ils peuvent être assez lents, donc je ne veux vraiment pas le hachage complet. Le calcul d'un hachage complet sur un fichier de 3 Go prend au moins 5 minutes à 10 Mo / s, quelle que soit la vitesse de l'algorithme de hachage.
  • Si l'utilisateur a édité le fichier, j'espère que le hachage ne correspondra plus, car sinon j'afficherais de mauvais signets.

Je serais d'accord avec ~ 80% de chances d'avoir les bons signets. Combien de morceaux de hachage dois-je assembler et où serait-il dans le fichier?

Thomas Weller
la source
1
Tant que la falsification malveillante ou la corruption de fichiers ne sont pas un problème, rien de tout cela n'est nécessaire. Utilisez simplement un programme spécialisé pour interpréter les en-têtes des fichiers multimédias, qui devraient contenir les dates et tailles d'encodage / marquage des flux. Vous pouvez hacher les informations sur les médias pour une comparaison facile.
De plus, la plupart des systèmes d'exploitation gardent une «date de dernière modification» disponible pour chaque fichier. Si vous n'avez pas à vous soucier d'une falsification malveillante (cette dernière date de modification peut généralement être fixée par quelqu'un), vous pouvez simplement regarder cela et ne pas vous soucier du contenu du fichier.
poncho
EXIF ou MP3tag sont presque inutiles pour détecter les changements: de nombreux programmes de manipulation sont incapables de les toucher et conservent donc leur contenu précédent. Par exemple, EXIF ​​peut très bien conserver l' image d'origine .
1
En passant par «je suppose que les fichiers sont toujours des fichiers légaux», je suppose que vous ne recherchez aucune sécurité? Dans ce cas, vous êtes sur le mauvais site. L'informatique devrait être une meilleure aide. Les réponses que vous avez reçues ici ne sont pas pertinentes si vous ne voulez pas de sécurité, donc si c'est le cas, je suggère de republier sur l' informatique et de clarifier ce point dans votre question republiée.
Gilles 'SO- arrête d'être méchant'
2
1) Le calcul du hachage réel sera généralement bon marché par rapport à l'IO. MD5 détectera toutes les modifications non malveillantes et est assez rapide. Surtout si vous le parallélisez. Vous auriez besoin d'un RAID de SSD ou quelque chose de similaire rapide pour dépasser sa vitesse. 2) Pour les fichiers locaux, le système d'exploitation peut souvent vous dire s'il a changé. Pas seulement la date du dernier changement, il existe également des API spécialisées.
CodesInChaos

Réponses:

8

Votre pièce a deux faces:

  1. si vous voulez le faire en toute sécurité, vous devrez utiliser un hachage cryptographiquement sécurisé comme SHA256 (les hachages cryptographiques sont censés être rapides, mais ont tendance à être un peu lents en raison de contraintes de sécurité),
  2. des choses comme les CRC sont certainement plus rapides, mais ne pourront jamais offrir le même type de sécurité (surtout quand nous parlons de.

Option 1: CRC - Faire vite au prix de la sécurité:

Si vous êtes juste après la détection des changements, optez pour une somme de contrôle au lieu d'un hachage. C'est pour cela que les sommes de contrôle ont été faites: détecter rapidement les changements dans un fichier ou un flux de données. Mais gardez à l'esprit que CRC a été conçu pour éviter les erreurs de transmission, pas les actions malveillantes!

Pratiquement, le CRC32 est le candidat le plus évident (mais même un CRC8 additif ferait l'affaire si vous voulez seulement détecter si quelque chose a changé et n'attendez rien d'autre que celui du CRC.)

Option 2: Au-delà des CRC - le faire assez rapidement tout en améliorant la détection des changements:

D'autres options valides (en regardant le commentaire de @ poncho ) sont en effet de simplement vérifier l' horodatage du dernier mod .

Ou, vous combinez les deux (pour éviter les goulots d'étranglement), en utilisant quelque chose comme ce pseudo-code montre:

if(LastMod != knownLastMod) { CreateNewCRCandCompare(FileName, knownCRC) };

Mais cela offre-t-il une réelle sécurité? Il en va de même pour votre ...

Pourquoi je considère la vérification de la queue:
- MP3 contient les informations de balise
- EXIF ​​ajoute des données personnalisées à la fin si j'ai raison

Encore une fois, cela dépend du niveau de sécurité que vous attendez. Vous devez réaliser qu'un adversaire manipulera sûrement le fichier pour conserver (ou copier-coller) toutes les anciennes données ID3 et EXIF… car n'importe qui (avec les droits d'accès aux fichiers RW appropriés) peut le modifier. Il en va de même pour l'horodatage de la dernière modification, les fréquences d'images, la résolution, la date du dernier changement et même la longueur (du fichier). Dépendre de ces données «supplémentaires» et «modifiables» - qui peuvent être modifiées et supprimées par toute personne disposant de droits d'accès aux fichiers suffisants - introduirait une faille de sécurité.

Mais vous vous attendez à la sécurité, n'est-ce pas? Après tout, c'est la raison pour laquelle vous pensez à tout cela en premier lieu. Eh bien, il n'y a pas moyen de contourner l'utilisation de hachages cryptés…

Option 3: hachages sécurisés cryptographiquement - le faire en toute sécurité au prix de la vitesse:

Si vous attendez une réelle sécurité, vous devrez vous fier au hachage; pour être plus précis: hachage cryptographiquement sécurisé (en utilisant un hachage qui n'est pas connu pour produire des collisions). Cela prend du temps (quelques microsecs par Mo) mais ça vaut le coup.

Mes 2 cents (personnels):

Essayez de vivre avec le fait que le hachage coûte du temps et hachez tous les fichiers avec un hachage cryptographiquement sécurisé . Parce que, quand des trucs commencent à frapper le ventilateur… il vaut mieux être lent, au lieu d'être désolé.

EDIT basé sur votre EDIT…

Si la sécurité cryptographique n'est pas votre objectif principal, vous pouvez regarder MD5 ou SHA1. MD5 et SHA1 sont tous les deux «cryptographiquement rompus» car des collisions ont été détectées… mais aux fins de détection des changements que vous décrivez (en particulier après votre EDIT), la probabilité de heurter une telle collision devrait être suffisamment minime.

En regardant à nouveau tout (y compris votre EDIT), j'utiliserais très probablement MD5, car il offre une résistance aux collisions utilisable (à des fins de détection de changement) tout en étant suffisamment rapide pour hacher complètement les fichiers de plusieurs gigaoctets.

Si cela ne vous satisfait toujours pas dans un sens de «vitesse» ou si vos ressources matérielles sont vraiment aussi limitées, vous devez essayer d'équilibrer la résistance aux collisions / détection de changement avec la vitesse. Sens…

Prenez l'horodatage individuel, le nom de fichier individuel et hachez l'en-tête (la longueur dépend du type de support et du format de fichier utilisé) ainsi qu'un bon morceau du milieu et un bon morceau de la queue (= fin du fichier). Combinez ces 5 et vous devriez pouvoir filtrer grossièrement la plupart

Je serais d'accord avec ~ 80% de chances d'avoir les bons signets. Combien de morceaux de hachage dois-je assembler et où serait-il dans le fichier?

C'est plus une opinion personnelle, car cela dépend de tout un tas de détails (type de média, format de fichier, ressources disponibles, taux de détection des changements attendu, similitude de fichier, etc.), vous devrez donc équilibrer cela vous-même en fonction de votre personnalité vos attentes, vos implémentations et vos résultats locaux en raison de goulots d'étranglement matériels et / ou logiciels.

Permettez-moi néanmoins de vous donner quelques conseils:

Si le hachage du fichier complet n'est pas une option pour quelque raison que ce soit, je prendrais - au moins - prendre: l'en-tête (et peut-être quelques Ko de plus), un bon morceau du milieu (au moins la taille du «header & co . ”), Et une bonne partie de la fin du fichier (encore une fois, au moins la taille de la partie“ header & co. ”).

Plus vous pouvez investir de ressources (ou êtes prêt à investir), plus vous pouvez prendre de morceaux et / ou plus ces morceaux peuvent être gros. Si vous pensez que vos ressources / sensation / quoi que ce soit offre encore de la place pour plus, augmentez la taille des morceaux que vous hachez et / ou augmentez le nombre de morceaux que vous hachez.

L'augmentation du nombre de morceaux est facile: comme tout ce que vous devez faire est de veiller à une distribution égale (en divisant la taille du fichier en conséquence, résultant en des morceaux de même taille que vous extrayez de parties également espacées sur toute la longueur du fichier).

Et si vous vous demandez «Pourquoi des positions de blocs également réparties et non aléatoires?», Permettez-moi simplement de noter que le choix de positions de morceaux aléatoires pourrait pratiquement annuler vos efforts de détection de changement car il comporte le risque de sauter certaines parties importantes des médias où vous détecteriez normalement les chances que vous visez à détecter. Le choix d'une distribution égale est - simplement dit - plus neutre.

e-sushi
la source
1
Je n'utiliserais pas CRC32, trop grande chance d'échec même sans attaques malveillantes. La crypto est assez rapide. Vous devriez obtenir 1 Go / s sur un seul cœur avec un hachage standard. Si vous l'affaiblissez un peu, 3 Go / s devraient être possibles. Il est presque certain que les entrées-sorties sont plus chères que le hachage.
CodesInChaos
@CodesInChaos Je suis d'accord. C'est pourquoi mes derniers mots conseillent d'opter pour un hachage cryptographiquement sécurisé.
e-sushi
1
Les hachages Carter-Wegman et d'autres hachages universels pourraient vous aider. Ceux-ci ont la vitesse d'un CRC large et la sécurité des hachages, en supposant qu'une clé reste inconnue de l'attaquant et qu'elle n'est pas réutilisée. Voir cette réponse pour les références.
fgrieu
@fgrieu Mais cela ne signifierait-il pas - dans la situation des PO - que les PO auraient besoin d'une clé individuelle par fichier? Cela me semble un peu impraticable. Surtout, car cela introduirait la nécessité d'une gestion des clés, etc. juste pour vérifier les modifications de fichiers potentielles.
e-sushi
1
@ e-suschi: s'il existe un identifiant de fichier unique (comme un chemin d'accès), une clé principale et HMAC suffisent pour obtenir une clé unique par fichier. Cela dit, si l'adversaire obtient un accès en lecture à la clé, elle peut faire une contrefaçon, quand elle ne peut pas avec un hachage régulier du fichier et un accès en lecture seule.
fgrieu
5

Raccourcis

Si vous avez plusieurs fichiers et que vous souhaitez détecter les modifications apportées aux fichiers, utilisez la taille du fichier et l'horodatage de la dernière modification.

Il est possible que le système d'exploitation que vous utilisez fournisse des fonctionnalités pour détecter les modifications de fichiers, par exemple Linux permet d'obtenir une notification des modifications apportées aux répertoires.

Traitement complet des fichiers

Si vous devez lire le contenu réel des fichiers pour vérifier si les fichiers ont changé, optez pour le hachage cryptographique réel. Le CRC a un potentiel important de donner un faux négatif. SHA-256 peut être assez bon, mais en fait, SHA-512 est plus rapide sur de nombreuses plates-formes modernes.

Si vous avez plusieurs cœurs de processeur, il peut être utile de calculer différents hachages pour différentes parties du fichier ou d'utiliser l'arbre de hachage pour paralléliser le traitement.

La raison de suggérer un hachage approprié est qu'une fois que vous accédez aux données de fichier réelles, le traitement cryptographique ne sera pas trop, mais il y aura beaucoup d'autres choses plus lentes, généralement par exemple des E / S de disque ou l'envoi et la réception de paquets réseau.

Remarque: Pour (au moins) les petits fichiers, il est également possible de stocker tout le contenu du fichier et de comparer le contenu au lieu de hacher.

Remarque 2: Si vous êtes très restreint sur le stockage, le CRC ou le hachage cryptographique tronqué pourrait être un bon choix. CRC32 prend 4 octets par fichier et SHA-256 est de 32 octets. Les petites balises de 4 octets ne peuvent pas protéger contre les tentatives malveillantes de masquer les modifications.

Traitement partiel des fichiers

Dans la plupart des cas, je recommanderais d'utiliser uniquement le traitement de fichier complet.

C'est peut-être plus une question mathématique maintenant, mais: quelle est la probabilité de détecter un changement en utilisant la combinaison de la taille du fichier, de la tête, de la queue et des données aléatoires pour générer cette somme de hachage rapide?

Pour les fichiers image, il est courant de faire de petites modifications, comme supprimer les yeux rouges, ajouter de la moustache ou des cornes, etc. ou l'un des autres attributs que vous mentionnez.

Le temps de modification du fichier sera généralement affecté cependant.

En ce qui concerne les fichiers vidéo: de nombreux formats vidéo génèrent un débit binaire constant. Pour un fichier à débit binaire constant, si certaines images au milieu sont modifiées, il n'apparaîtra pas non plus en taille de fichier, en tête ou en queue. La suppression ou l'ajout de cadres entraînera presque toujours une différence de taille.

Je vois donc tout à fait possible que le champ obtienne des modifications sans qu'il ne soit détecté.

Il est très difficile d'estimer les modifications de probabilité détectées avec ce schéma, mais il existe des scénarios d'utilisation courants pour les vidéos et les images qui ne sont pas correctement détectées.


la source
Oui, les petites modifications sur les fichiers PNG ou WAV ont de grandes chances d'être manquées si seulement quelques morceaux sont traités.
galinette