Les 32 premiers bits d'un hachage SHA1 de 160 bits sont-ils un substitut acceptable pour un hachage CRC32?

Question

Je travaille sur un projet .NET 3.5 et j'ai besoin d'une valeur de hachage de 32 bits. Il ne semble pas y avoir de méthodes dans les classes .NET Cryptography qui retournent un hachage 32 bits (MD5 est 128 bits, SHA1 est 160 bits, etc.). J'ai implémenté une classe CRC32, mais je trouve que les fonctions de hachage SHA1 et MD5 qui existent déjà sont beaucoup plus rapides. Y aura-t-il un problème (c'est-à-dire un risque accru de collisions) avec moi en utilisant la fonction de hachage SHA1 et en rompant simplement les 32 premiers bits à stocker comme valeur de hachage?

Answer 1

Sauf si vous voulez les fonctionnalités supplémentaires du CRC32 (étant un code linéaire), vous devriez être en mesure de couper la sortie à 32 bit. Le fait de couper la sortie de certaines fonctions de hachage cryptographiques nuit à sa sécurité vis-à-vis de la résistance aux collisions est un problème de recherche ouvert (des exemples construits «non naturels» existent si je me souviens bien). Mais NIST (probablement avec l'approbation de la NSA) a utilisé la technique de coupe pour obtenir le SHA-224 de SHA-256 de toute façon (voir article about SHA in wikipedia). EDIT: le CRC32 permet de détecter (et peut-être de corriger) les erreurs sur un seul bit, tandis qu'une fonction de hachage cryptographique devrait avoir la propriété de ne pas trouver deux entrées ayant la même valeur de hachage.

Connaissez-vous le "paradoxe de l'anniversaire" (voir à nouveau wikipedia)? Avec une somme de contrôle de 32 bits, vous vous attendez à une collision (c'est-à-dire, deux entrées avec la même valeur de hachage) lorsque vous avez environ 2^16 entrées, et vous voulez hacher beaucoup plus d'entrées. (Relecture de votre commentaire, cela pourrait ne pas poser de problème pour vous.)

Answer 2

Si vous n'avez pas l'intention d'utiliser les 32 bits à des fins de chiffrement, alors vous devriez être OK. Sinon, je ne compterais pas sur les premiers 32 bits ayant la même distribution que l'ensemble du hachage. Pourquoi ne pouvez-vous pas simplement utiliser le hachage plus large qui est disponible?

Answer 3

CRC32 est probablement raisonnable pour vos besoins. Cela a été discuté dans this question.

En termes de tronçonnage d'une primitive de hachage, la seule application fortement utilisée est SSL/TLS Pseudo Random Function (PRF) qui est utilisée pour générer des clés. Il utilise les HMAC, les seed et les labels pour générer autant d'octets que nécessaire en hachant plusieurs fois et en tronquant la quantité d'octets dont vous avez besoin.

Quant à votre question cependant, vous pouvez lire la sortie du hachage dans de Int32, puis les XOR ensemble si vous êtes paranoïaque:

static void Main() 
{ 
    int xorCrc = GetHashedCrc(new SHA1Cng(), new byte[] {0xDE, 0xAD, 0xBE, 0xEF}); 
} 

private static int GetHashedCrc(HashAlgorithm algorithm, byte[] bytesToHash) 
{ 
    byte[] hash = algorithm.ComputeHash(bytesToHash); 
    int totalInt32s = hash.Length/sizeof(int); 
    int result = 0; 
    for(int i = 0; i < totalInt32s; i++) 
    { 
     int currentInt = BitConverter.ToInt32(hash, sizeof(int)*i); 
     result = result^currentInt; 
    } 

    return result; 
} 

Answer 4

Compte tenu de l'hypothèse selon laquelle une fonction de hachage distribue ses entrées aussi au-dessus de son codomaine, il semble logique de supposer qu'il se répartira également sur tout sous-ensemble de celui-ci. Cependant, l'utilisation d'une fonction de hachage 32 bits "native" sera probablement le meilleur choix. Peut-être quelqu'un de plus dans la question peut nous fournir une meilleure raison que mon instinct :)

Answer 5

Pourquoi n'utilisez-vous pas simplement string.GetHashCode(). Il est conçu pour calculer une valeur de hachage 32 bits et produire peu de collisions données données du monde réel. Bien sûr, ce n'est pas sécurisé, mais votre question ne comprend pas cela comme une exigence.