Qu'est-ce qui rend un algorithme de hachage «sécurisé»?

19

Après avoir lu cette question intéressante, j'ai eu l'impression d'avoir une bonne idée de l'algorithme de hachage non sécurisé que j'utiliserais si j'en avais besoin, mais je ne sais pas pourquoi je pourrais utiliser un algorithme sécurisé à la place.

Alors, quelle est la distinction? La sortie n'est-elle pas juste un nombre aléatoire représentant la chose hachée? Qu'est-ce qui sécurise certains algorithmes de hachage?

CodexArcanum
la source
8
Cette question est mieux adaptée au site IT Security SE.
Bernard
@Bernard Si c'est le cas, je suis d'accord, mais ma question n'était pas vraiment de savoir comment ou quand utiliser un hachage sécurisé, mais ce qui distingue un algorithme de hachage sécurisé d'un algorithme non sécurisé. Cela ressemble plus à une question de programmation pour moi, mais je ne parcours pas IT Security SE, alors peut-être que cela fonctionne aussi.
CodexArcanum
2
Une question très similaire a déjà été posée sur la sécurité informatique
ChrisF

Réponses:

34

Il y a trois propriétés que l'on veut de chaque fonction de hachage cryptographique H:

  • résistance à la pré-image : étant donné h, il devrait être difficile de trouver une valeur xavec h = H(x).

  • deuxième résistance à la pré-image : Étant donné x1, il devrait être difficile de trouver x2 != x1avec H(x1) = H(x2).

  • résistance aux collisions : il devrait être difficile de trouver deux valeurs x1 != x2avec H(x1) = H(x2).

Avec les fonctions de hachage utilisées dans les langages de programmation courants pour les tables de hachage (de chaînes), généralement aucune de celles-ci n'est donnée, elles ne prévoient que:

  • faible résistance aux collisions : pour les valeurs sélectionnées de manière aléatoire (ou "typiquement") du domaine, le risque de collision est faible. Cela ne dit rien sur un attaquant essayant intentionnellement de créer des collisions, ou d'essayer de trouver des pré-images.

Les trois propriétés ci-dessus sont (parmi) les objectifs de conception pour chaque fonction de hachage cryptographique. Pour certaines fonctions (comme MD4, SHA-0, MD5), il est connu que cela a échoué (au moins partiellement). La génération actuelle (SHA-2) est supposée sécurisée et la suivante ("Secure Hash Algorithm 3") est en cours de standardisation , après une compétition .

Pour certaines utilisations (comme le hachage de mot de passe et la dérivation de clés à partir de mots de passe), le domaine des valeurs réellement utilisées xest si petit que le forçage brutal de cet espace devient possible avec des fonctions de hachage sécurisées normales (rapides), et c'est à ce moment-là que nous voulons également:

  • exécution lente : étant donné x, il faut un minimum (de préférence configurable) de ressources pour calculer la valeur H(x).

Mais pour la plupart des autres utilisations, ce n'est pas voulu, on veut plutôt:

  • exécution rapide : étant donné x, le calcul de la valeur de H(x)est aussi rapide que possible (tout en étant sécurisé).

Il existe certaines constructions (comme PBKDF2 et scrypt) pour créer une fonction de hachage lente à partir d'une fonction rapide en l'itérant souvent.

Pour plus de détails, jetez un œil à la balise de hachage sur notre site sœur Cryptography Stack Exchange.

Paŭlo Ebermann
la source
3

Sécurisé signifie que quelqu'un qui veut vous induire en erreur en utilisant une collision (c'est-à-dire le fait que deux sources sont hachées à la même valeur) aura des difficultés.

Quelques caractéristiques:

  • connaître le hachage, construire un fichier qui hache à cette valeur est difficile (variante, une partie du nouveau fichier est donnée ainsi que le hachage souhaité)

  • la construction de deux fichiers différents qui hachent à la même valeur est difficile (variante, une partie des fichiers est donnée)

AProgrammer
la source
3

La principale différence est assez simple: un hachage normal est destiné à minimiser le nombre de collisions accidentelles, dans la mesure où il peut sans ralentir beaucoup dans le processus.

Un hachage sécurisé destiné à empêcher les collisions, même lorsque quelqu'un fait de son mieux pour en provoquer un. Vous ne voulez pas généralement au commerce toute possibilité d'une collision pour un fonctionnement plus rapide. En fait, ralentir intentionnellement le fonctionnement présente en soi certains avantages en termes de sécurité, même si cela ne rend pas la recherche de collisions plus difficile.

Pour un exemple de ce dernier: si le calcul d'un hachage prend 50 ms, cela n'aura pas d'effet matériel sur la connexion d'un utilisateur normal (c'est-à-dire que la plupart des utilisateurs ne remarqueront pas une différence de 50 ms lors de leur connexion). Dans le même temps, si un attaquant veut effectuer une attaque par dictionnaire, être capable de produire seulement 20 hachages par seconde est un sérieux handicap. En d'autres termes, pour une raison quelconque, pour un hachage sécurisé, plus lent est mieux.

Jerry Coffin
la source
3
Dans le domaine des fonctions de hachage cryptographique, il existe deux sous-groupes importants: les sous-groupes rapides (utilisés pour l'authentification des messages, la signature, etc.) et les lents - utilisés pour la dérivation des clés et le hachage des mots de passe. Ne les mélangez pas, il y a des applications pour les deux.
Paŭlo Ebermann
En fait, il existe également des fonctions de hachage conçues pour maximiser les collisions: Soundex en est un exemple. Évidemment, cela en fait une fonction de hachage sécurisée très merdique.
Jörg W Mittag
@ JörgWMittag: Non seulement merdique comme hachage sécurisé, mais serait également assez pauvre pour une utilisation avec une table de hachage. Là encore, bien que quelque peu semblable à du hachage, j'hésiterais à appeler Soundex une fonction de hachage, simplement parce que son intention et son utilisation sont très différentes des fonctions de hachage normales.
Jerry Coffin
@JerryCoffin: Je suppose que cela dépend de la définition. Par exemple, la page Wikipédia en anglais dit simplement qu'une fonction de hachage est un algorithme ou un sous-programme qui mappe un ensemble plus grand (potentiellement infini) de valeurs arbitraires en un ensemble plus petit et fini de valeurs (généralement scalaires). Alors que la page Wikipédia allemande dit que le "hachage" (allemand: "zerhacken") fait partie intégrante, c'est-à-dire que l'évitement des collisions et la distribution des valeurs mappées est la clé. Soundex remplit très bien la première définition mais pas la seconde.
Jörg W Mittag
3

Lisez ce http://www.codinghorror.com/blog/2012/04/speed-hashing.html cela expliquera tout bien mieux que je ne pourrais jamais l'expliquer. Voici les deux en-têtes les plus importants de l'article qui répondent directement à votre question:

  • Les hachages sécurisés sont conçus pour être inviolables
    • change radicalement sa sortie avec de minuscules modifications d'un seul bit dans les données d'entrée
  • Les hachages sécurisés sont conçus pour être lents

Sa section TL; DR à la fin:

Si vous êtes un utilisateur:

Assurez-vous que tous vos mots de passe contiennent 12 caractères ou plus, idéalement beaucoup plus. Je recommande d'adopter des phrases de passe, qui sont non seulement beaucoup plus faciles à mémoriser que les mots de passe (sinon taper) mais aussi ridiculement protégées contre le forçage brutal uniquement en raison de leur longueur.

Si vous êtes développeur:

Utilisez bcrypt ou PBKDF2 exclusivement pour hacher tout ce dont vous avez besoin pour être sécurisé. Ces nouveaux hachages ont été spécifiquement conçus pour être difficiles à implémenter sur les GPU. N'utilisez aucune autre forme de hachage. Presque tous les autres schémas de hachage populaires sont vulnérables au forçage brutal par des tableaux de GPU de base, qui ne deviennent plus rapides et plus parallèles et plus faciles à programmer pour chaque année.

Nate
la source
4
Jeff se trompe ici sur le deuxième point ... alors que pour certaines utilisations (comme hachage de mot de passe et dérivation de clé à partir d'un mot de passe), vous voulez être lent, pour d'autres utilisations (comme l'authentification de message, les signatures, etc.) rapide (sécurisé) les fonctions de hachage sont bonnes.
Paŭlo Ebermann
Tu as raison Paŭlo. Les performances du hachage dépendent de l'application du hachage. Cependant, les hachages lents sont toujours plus sûrs que les hachages rapides. La raison pour laquelle vous utiliseriez un hachage rapide est que vous sacrifiez la sécurité pour la performance.
Nate
2
@Nate «Plus sécurisé» est toujours ambigu, mais même dans l'application la plus charitable, «les hachages lents sont toujours plus sûrs que les rapides» est définitivement faux. Il existe de nombreuses applications où la vitesse d'un hachage n'est pas pertinente.
Gilles 'SO- arrête d'être méchant'
@Gilles pouvez-vous donner un exemple? Cela me semble vrai, mais des précisions seraient utiles.
Nate
2
@Nate L'application la plus évidente des hachages est de vérifier l'intégrité d'une donnée: transmettre le hachage sur un canal sécurisé mais éventuellement à faible bande passante, transmettre la charge utile éventuellement importante sur un canal non sécurisé, puis vérifier que la charge utile reçue a la capacité attendue hacher. Les hachages figurent également en bonne place dans les méthodes de signature (où vous vérifiez non seulement l'intégrité, mais aussi qui vous a envoyé les données). Le hachage des mots de passe est plutôt l'exception.
Gilles 'SO- arrête d'être méchant'
2

Un hachage «sécurisé» est un hachage qui est considéré comme difficile à «usurper» d'une manière formelle et reproductible sans connaissance préalable du message utilisé pour créer le hachage. Comme ces informations sont généralement secrètes, d'où la nécessité d'un hachage, il s'agit d'une bonne propriété d'une fonction de hachage destinée à être utilisée dans l'authentification.

Un hachage est généralement considéré comme "sécurisé" si, étant donné un message M, une fonction de hachage hash () et une valeur de hachage H produite par le hachage (M) avec une longueur en bits L, aucune des opérations suivantes ne peut être effectuée en moins de O (2 L ) temps:

  • Étant donné le hachage () et H, produire M. (résistance de pré-image)
  • Étant donné hash () et M, produire un M 2 différent tel que hash (M 2 ) == H. (faible résistance à la collision)
  • Étant donné hash (), produisez tout M 1 et M 2 tels que hash (M 1 ) == hash (M 2 ). (forte résistance aux collisions)

De plus, un hachage "sécurisé" doit avoir une longueur de hachage L telle que 2 Ln'est pas un nombre d'étapes réalisables pour qu'un ordinateur exécute le matériel actuel donné. Un hachage entier 32 bits ne peut avoir que 2,1 milliards de valeurs; alors qu'une attaque de pré-image (trouver un message qui produit un hachage spécifique H) prendrait un certain temps, ce n'est pas irréalisable pour de nombreux ordinateurs, en particulier ceux entre les mains d'agences gouvernementales chargées de briser le code. En outre, un algorithme qui crée et stocke des messages aléatoires et leurs hachages aurait, selon la probabilité, 50% de chances de trouver un hachage en double avec chaque nouveau message après avoir essayé seulement 77 000 messages, et aurait 75% de chances de frapper un dupliquer après seulement 110 000. Même les hachages 64 bits ont encore 50% de chances de se heurter après avoir essayé seulement environ 5 milliards de valeurs. Telle est la puissance de l'attaque d'anniversaire sur les petits hachages. Par contre,nombres de décillions (1,5 * 10 34 ).

La plupart des attaques démontrées sur les hachages cryptographiques ont été des attaques par collision et ont démontré la capacité de générer des messages entrant en collision en moins de 2 L (la plupart ont toujours été à temps exponentiel, mais réduire l'exposant de moitié est une réduction significative de la complexité car cela rend un hachage 256 bits aussi facile à résoudre qu'un 128 bits, un 128 bits aussi facile à résoudre qu'un 64 bits, etc.).

En plus de la petite taille du hachage, d'autres facteurs qui peuvent rendre un hachage peu sûr sont:

Faible travail - un hachage conçu pour être utilisé par une table de hachage ou à d'autres fins de type "somme de contrôle" est généralement conçu pour être peu coûteux en termes de calcul. Cela rend une attaque par force brute beaucoup plus facile.

"Sticky State" - La fonction de hachage est sujette à des modèles d'entrée où la valeur de hachage actuelle de toutes les entrées ne change pas jusqu'à présent lorsqu'elle reçoit un octet supplémentaire particulier d'entrée. Le fait d'avoir un "état collant" rend les collisions faciles à trouver, car une fois que vous identifiez un message qui produit un hachage "d'état collant", il est trivial de générer d'autres messages qui ont le même hachage en ajoutant des octets d'entrée qui gardent le hachage dans son "état collant". ".

Diffusion - Chaque octet d'entrée du message doit être réparti entre les octets de la valeur de hachage d'une manière également complexe. Certaines fonctions de hachage créent des modifications prévisibles de certains bits du hachage. Cela rend encore une fois la création de collisions triviale; étant donné un message qui produit un hachage, des collisions peuvent être facilement créées en introduisant de nouvelles valeurs dans le message qui n'affectent que les bits qui changent de façon prévisible.

KeithS
la source
0

Utilisez le bon algorithme pour la tâche à accomplir.

Les CRC sont utilisés pour la détection / correction des erreurs.

Les résumés de messages cryptographiques tels que SHA2 sont utilisés comme blocs de construction pour les constructions cryptographiques (signatures numériques, MAC, fonctions de dérivation de clé / hachage de mot de passe) et les protocoles de sécurité.

Dans les tables de hachage / dictionnaires / cartes, utilisez SipHash .

Ce que vous appelez les algorithmes de hachage non sécurisés ne doit pas être utilisé dans les tables de hachage , comme le prouvent les entrées CVE suivantes: CVE-2003-0364, CVE-2011-4461, CVE-2011-4838, CVE-2011-4885, CVE-2011- 4462, CVE-2011-4815, CVE-2012-0840, CVE-2012-5371 , CVE-2012-5374, CVE-2012-5375

Erwan Legrand
la source