SHA-1 est-il sécurisé pour le stockage des mots de passe?

Question

Conclusion: SHA-1 est aussi sûr que quoi que ce soit contre preimage attaques, cependant il est facile à calculer, ce qui signifie qu'il est plus facile de monter un bruteforce ou attaque par dictionnaire. (La même chose est vraie pour les successeurs comme SHA-256.) Selon les circonstances, une fonction de hachage qui a été conçu pour être gourmand en ressources (comme bcrypt) pourrait être un meilleur choix.

---

Certaines personnes jettent dans des remarques comme "SHA-1 est cassé" beaucoup, donc je suis en train d'essayer de comprendre exactement ce que cela signifie. Supposons que j'ai une base de données de l'algorithme SHA-1 des mots de passe, et un attaquant avec un état de l'art SHA-1 rupture de l'algorithme et un botnet avec 100 000 machines obtient l'accès à elle. (Avoir le contrôle de plus de 100 ordinateurs à domicile signifie qu'ils peuvent faire sur 10^15 opérations par seconde). Combien de temps auraient-ils besoin de

1. trouver le mot de passe d'un utilisateur?
2. trouver le mot de passe d'un utilisateur donné?
3. trouver le mot de passe de tous les utilisateurs?
4. trouver un moyen pour ouvrir une session en tant qu'un des utilisateurs?
5. trouver un moyen de se connecter en tant qu'utilisateur spécifique?

Comment est-ce que changer si les mots de passe sont salées? La méthode de salage (préfixe, suffixe, à la fois, ou quelque chose de plus compliqué comme xor-ing) de la matière?

Voici ma compréhension actuelle, après quelques recherches sur google. Merci de corriger dans les réponses si j'ai mal compris quelque chose.

• Si il n'y a pas de sel, un arc-en-ciel attaque immédiatement trouver tous les mots de passe (à l'exception de très longs).
• Si il y a un temps suffisamment long aléatoire sel, le moyen le plus efficace de trouver le mots de passe est une force brute ou par dictionnaire attaque. Ni collision ni preimage attaques sont d'une aide pour trouver le mot de passe réel, de sorte que les attaques cryptographiques contre SHA-1 ne sont d'aucune aide ici. Il n'a même pas d'importance quel algorithme est utilisé -, on pourrait même utiliser MD5 ou MD4 et les mots de passe serait tout aussi sûr (il y a une légère différence, car le calcul d'un hash SHA-1 est plus lent).
• Pour évaluer le degré de sécurité "tout comme le coffre-fort" est, supposons qu'un seul sha1 run prend 1000 opérations et les mots de passe contiennent des majuscules, des minuscules et des chiffres (60 caractères). Cela signifie que l'attaquant peut faire le test 10¹⁵*60*60*24 / 1000 ~= 10¹⁷ le potentiel de mot de passe un jour. Pour une attaque en force brute, ça voudrait dire que les tests de tous les mots de passe jusqu'à 9 caractères en 3 heures, jusqu'à 10 caractères dans une semaine, jusqu'à 11 caractères en un an. (Il faut 60 fois plus pour chaque caractère). Une attaque par dictionnaire est beaucoup, beaucoup plus rapide (même un attaquant avec un seul ordinateur pourrait l'arracher en heures), mais ne trouve que des mots de passe faibles.
• Pour vous connecter en tant qu'utilisateur, l'attaquant n'a pas besoin de connaître le mot de passe exact; il suffit de trouver une chaîne de résultats dans le même hash. Ceci est appelé une première preimage attaque. Aussi loin que j'ai pu trouver, il n'y a pas preimage attaques contre SHA-1. (Une attaque bruteforce faudrait 2¹⁶⁰ opérations, ce qui signifie que nos théorique attaquant aurait besoin de 10^{à 30} ans pour s'en sortir. Les limites de la possibilité théorique sont autour de 2⁶⁰ opérations, à qui l'attaque et prend quelques années.) Il y a preimage attaques contre la diminution des versions de l'algorithme SHA-1 avec effet négligeable (pour la réduction de SHA-1, qui utilise 44 étapes au lieu de 80, temps d'attaque est en baisse de 2¹⁶⁰ opérations à 2¹⁵⁷). Il y a des attaques par collision contre SHA-1 qui sont bien au sein de la possibilité théorique (le meilleur que j'ai trouvé apporte le temps vers le bas à partir de 2⁸⁰ 2⁵²), mais ceux-ci sont inutile contre les mots de passe, même sans saler.

En bref, le stockage des mots de passe avec l'algorithme SHA-1 semble parfaitement en sécurité. Ai-je raté quelque chose?

Mise à jour: Marcelo a souligné un article qui mentionne une seconde preimage attaque en 2¹⁰⁶ opérations. (Edit: Comme Thomas explique, cette attaque est une hypothétique construction qui ne s'applique pas à des scénarios réels.) Je ne vois pas comment ce sorts danger pour l'utilisation de SHA-1 comme une fonction de dérivation de clé, cependant. Là généralement de bonnes raisons de penser qu'une collision ou une attaque de la deuxième preimage attaque peut être finalement transformé en un premier preimage attaque?

Answer 1

La réponse courte à votre question est: SHA-1 est aussi sécurisé que vous pouvez obtenir. MD5 serait bien aussi, même MD4; mais elle pourrait rendre certains investisseurs nerveux. Pour les relations publiques, il est préférable d'utiliser un "mieux" fonction de hachage, par exemple, SHA-256, même si vous tronquez sa sortie à 160 ou 128 bits (pour économiser sur les coûts de stockage). Certains SHA-3-ronde 2 les candidats semblent être plus rapide que l'algorithme SHA-1, tout en étant sans doute "plus sécurisé"; mais ils sont encore un peu nouveau, afin de coller à SHA-256 ou SHA-512 serait une route plus sûre maintenant. Ce serait vous faire un look professionnel et de prudence, ce qui est bon.

Notez que "aussi sûr que vous pouvez obtenir" n'est pas la même que la "sécurité parfaite". Voir ci-dessous pour plutôt de longues explications.

Sur les attaques connues:

Les attaques connues sur MD4, MD5 et SHA-1 sont sur les collisions, qui n'ont pas d'impact preimage résistance. Il a été démontré que MD4 a quelques faiblesses qui peuvent être (seulement en théorie) exploitées lors de la tentative de briser HMAC/MD4, mais cela ne s'applique pas à votre problème. Le 2¹⁰⁶ deuxième preimage attaque dans le papier par Kesley et Schneier est un générique de compromis qui ne s'applique qu'à très long entrées (2⁶⁰ octets; c'est un million de téraoctets -- remarquez comment 106+60 dépasse 160; c'est là qu'on voit que le compromis a rien de magique).

Le reste de ce message suppose que la fonction de hachage que vous utilisez (par exemple SHA-1) est une "boîte noire" n'ayant pas de propriété particulière que l'attaquant peut utiliser. C'est ce que vous avez en ce moment même avec le "cassé" les fonctions de hachage MD5 et SHA-1.

Sur les tables arc-en-ciel:

"L'arc-en-ciel d'attaque" est en fait le partage des coûts d'un dictionnaire ou d'une attaque par force brute. C'est un dérivé de la temps-mémoire de compromis, d'abord décrit par Hellman en 1980. En supposant que vous avez N mots de passe possibles (c'est la taille de votre dictionnaire, ou 2ⁿ si vous envisagez de brute-forcer une fonction de hachage avec une puissance de n bits), il y a un temps de partage de l'attaque au cours de laquelle vous précalculer la N des mots de passe hachés et de les stocker dans un tableau. Si vous triez le hachage sorties, vous pouvez obtenir votre mot de passe en une seule recherche. Un arc-en-ciel de la table est une façon intelligente pour stocker un tableau avec beaucoup d'espace réduit. Vous stockez uniquement N/t mots de passe hachés, et vous craquer des mots de passe avec O(t²) les recherches. Rainbow tables vous permettent de pratiquement poignée de tables précalculées beaucoup plus grande que ce que vous pouvez raisonnablement magasin.

Cependant, arc-en-ciel ou pas, l'attaquant a toujours pour exécuter l'attaque au moins une fois. Ceci peut être considéré comme plusieurs successives d'optimisation de couches:

1. Le brute-force / dictionnaire d'attaque a coûté la N de la fissuration chaque mot de passe.
2. Avec un pré-calculé de la table, l'attaquant paie que le coût N une fois et peut, par la suite, l'attaque de nombreux mots de passe avec un très petit coût supplémentaire par mot de passe.
3. Si le pré-calculé de la table est une table arc-en-ciel, alors N peut être un peu plus grand, parce que le stockage coût est réduit. Le goulot d'étranglement sur N devient la puissance du PROCESSEUR qui permet à l'attaquant de rassemblement, pas de la taille de ses disques durs.

Si N est assez grand pour que la CPU coût de hachage N de mots de passe est ridicule que, une telle attaque n'est pas possible, indépendamment du fait que rainbow tables sont utilisées ou non. Cela signifie qu'un (preimage-résistant) fonction de hachage avec une puissance de 80 bits ou plus est assez pour faire attaque par force brute infaisable.

À propos de sels:

Les sels sont un moyen de vaincre les pré-calculs. Dans la description ci-dessus, le sel apporte en retour de l'attaquant de l'étape 1: le salage empêche l'attaquant de l'échange de O(N) coût entre plusieurs attaqué les mots de passe. Pré-calculé des tables, a fortiori rainbow tables, ne sont plus praticables.

Vous souhaitez saler car lorsque le haché de données consiste en des mots de passe, c'est à dire quelque chose qui s'inscrit dans le cerveau d'un homme aléatoire, N peut être assez faible: les humains sont vraiment mauvais à choisir et retenir des mots de passe. C'est ce que "les attaques par dictionnaire": c'est à l'aide d'un espace réduit de mots de passe potentiels (le "dictionnaire") sous l'hypothèse que de nombreux mots de passe utilisateur sera spécialement sélectionné de l'espace.

D'où le salage au moins empêcher l'attaquant de l'aide de pré-calculé des tables, en particulier pré-calculé rainbow tables. Cela suppose que l'attaquant sera en mesure de casser un mot de passe ou les deux; nous ne voulons pas de lui casser 1000 autres mots de passe avec peu de frais généraux supplémentaires.

Aussi, le salage est bon pour les relations publiques.

Sur SHA-1 prix:

L'élémentaire coût de l'algorithme SHA-1 est sur le hachage d'un 64 octets du bloc. C'est la façon dont l'algorithme SHA-1 fonctionne: les données sont complétées, alors divisée en 64 octets, blocs. Le coût de traitement d'un seul bloc est d'environ 500 cycles d'horloge sur un processeur Intel Core2 système, et c'est pour un seul cœur. MD5, MD4 et sont plus rapides, comptez environ 400 et 250 cycles, respectivement. N'oubliez pas que la plupart des modernes CPU avoir plusieurs cœurs, de sorte se multiplient en conséquence.

Certains salage des régimes de prescrire énorme sels; par exemple, ce qui entre dans la fonction de hachage est en fait 40000 copies successives d'un seul de 128 bits sel, suivi par le mot de passe lui-même. Cela fait de hachage de mot de passe plus cher (par un facteur de 10000 avec mon exemple), à la fois pour l'utilisateur légitime et pour l'attaquant. Si c'est une bonne idée dépend de la configuration. Pour la connexion sur un système de bureau, c'est bon: l'utilisateur ne remarquerez même pas qu'il a fallu 10 ms à hachage de mot de passe, au lieu de 1µs; mais le coût pour l'attaquant a augmenté par une très sensible facteur 10000. Sur un des serveurs partagés avec des milliers de clients par seconde, le coût global peut devenir prohibitif. Sur le plan conceptuel, monter la barre par le même facteur pour l'utilisateur légitime et l'attaquant est finalement pas une bonne sécurité; mais il peut être la peine d'idée dans certaines situations spécifiques.

Sur les attaques en ligne:

Tous les ci-dessus est sur vaincre en mode hors connexion attaques. Hors ligne d'attaque est une attaque où l'attaquant dispose de toutes les données dont il a besoin afin de "tester" les mots de passe; par exemple, l'attaquant peut obtenir une copie de la base de données contenant les mots de passe hachés. Dans et hors ligne d'attaque, l'attaquant est limité que par son des ressources de calcul. A l'inverse, une ligne d'attaque est une attaque où chaque deviner par l'attaquant doit passer par un honnête verifier (par exemple, l'attaquant essaie simplement de vous connecter sur le système attaqué). Les attaques en ligne sont repoussés par l'application de limites sur le nombre de mots de passe peut être tenté par seconde. Exemples extrêmes sont des cartes à puce qui a fermé après trois mauvais PINs.

Généralement, pour la sécurité de mot de passe, il paie beaucoup plus d'organiser le système pour ne pas laisser un attaquant de construire une attaque hors connexion. C'est ce que les systèmes Unix n': les mots de passe hachés, qui l'habitude d'être dans le monde lisible /etc/password le fichier, sont maintenant dans l' /etc/shadow fichier est protégé contre les accès en lecture, à l'exception de quelques privilégiés applications. L'hypothèse ici est que si l'attaquant peut lire /etc/shadow, puis il a probablement suffisamment de contrôle sur le système qu'il n'a pas vraiment besoin de mots de passe plus...

Answer 2

Les réponses précédentes de ne pas faire mention de Gpu, ce qui peut parallellise de hachage SHA-1 dans la mesure où un ensemble de base de données peuvent maintenant être brute forcé en minutes ou en heures plutôt qu'en jours ou des semaines, même si les mots de passe ont été salé.

Moderne hachage de mot de passe algorithmes tels que bcrypt ou scrypt sont conçus spécifiquement pour être difficile à exécuter sur les Gpu en raison du fait qu'ils sont des algorithmes de chiffrement par bloc avec beaucoup plus élevé que les exigences de mémoire (et l'accès à la mémoire dans un GPU ne peut pas être parallellised dans la même mesure). Ils ont aussi un "travail" qui leur permet d'être faite plus lente à la volée que la technologie s'améliore.

En bref, vous ne devez utiliser les meilleurs outils de travail. Et SHA-1 est très loin de l'état de l'art.

Pour davantage de lecture:

• http://crypto.stackexchange.com/questions/400/why-cant-one-implement-bcrypt-in-cuda
• http://codahale.com/how-to-safely-store-a-password/
• http://www.codinghorror.com/blog/2012/04/speed-hashing.html
• http://security.stackexchange.com/questions/4781/do-any-security-experts-recommend-bcrypt-for-password-storage/6415#6415

Answer 3

Votre description des sons précis de l'état actuel de la technique.

Vous ne devriez pas être à l'aide d'une seule itération de toute fonction de hachage, cependant: À tout le moins, vous devriez itérer plusieurs fois (1000 itérations de la table de hachage augmente l'attaquant du travail de 1000 fois. Il augmente votre travail par le même montant, mais vous êtes en train de faire beaucoup moins de hachage de mot de passe qu'ils sont).

Idéalement, cependant, vous devez utiliser un mot de passe existant de stockage primitifs, tels que ceux décrits ici.

Answer 4

De graves vulnérabilités ont été découvertes dans SHA-1 qui font de la recherche beaucoup plus rapide que la force brutale. Il est encore largement insoluble, mais qui ne devrait pas être le cas pendant trop longtemps; paranoïaque programmeurs faveur de quelque chose de la SHA-2 de la famille.

À partir de cet article concernant l'origine résultat de 2005:

"Il est temps de marcher, mais pas l'exécuter, pour les sorties de secours. Vous ne voyez pas de fumée, mais les alarmes incendie sont passés."

Ce n'est pas que le courant de la cryptanalyse rend SHA-1 dangereux, mais plutôt que la crypto communauté est inquiet que la pire des nouvelles, peut-être juste autour du coin. Cette peur s'applique également à SHA-2, qui présente les mêmes défauts que SHA-1, mais sur beaucoup plus de l'espace de recherche, d'où la recherche permanente de SHA-3.

En bref, SHA-1 est sûr maintenant, et probablement pour un certain temps, mais la crypto communauté est mal à l'aise avec le pronostic.

Answer 5

Si vous stockez le salé mot de passe, SHA-1 est très bien pour des raisons pratiques. SHA-2 est considéré comme plus sûr, mais SHA-1 n'est pas un problème, sauf si vous avez une raison de plus pour être vraiment paranoïaque.

Voici ce que le NIST dit:

Les résultats présentés jusqu'à présent sur SHA-1 ne pas appeler sa de la sécurité dans question. Toutefois, en raison des progrès dans technology, NIST plans à la phase de SHA-1 en faveur de la plus grande et plus de fonctions de hachage (SHA-224, SHA-256, SHA-384 et SHA-512) par 2010.