CALCUL DE HASH SHA 256
metheorn
Messages postés
4
Date d'inscription
jeudi 18 décembre 2008
Statut
Membre
Dernière intervention
5 janvier 2009
-
22 déc. 2008 à 11:17
ferdybihaw Messages postés 1 Date d'inscription lundi 22 octobre 2012 Statut Membre Dernière intervention 22 octobre 2012 - 22 oct. 2012 à 03:45
ferdybihaw Messages postés 1 Date d'inscription lundi 22 octobre 2012 Statut Membre Dernière intervention 22 octobre 2012 - 22 oct. 2012 à 03:45
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/48697-calcul-de-hash-sha-256
https://codes-sources.commentcamarche.net/source/48697-calcul-de-hash-sha-256
22 oct. 2012 à 03:45
24 mars 2009 à 22:32
Voir la liste des fichiers sur (aucune pub, juste les fichiers):
http://org.rodage.com/pub/java/security/
(il y a d'autres algos que SHA256, il y a eu de très lègères modifications de performance depuis leur création, mais plus aucun changement depuis 2005). Ce sont toutes des implémentations en 100% pur Java (pas d'utilisation de DLLs natives via JNI), et donc totalement portable sur toutes plateforme compatible Java (des serveurs d'applications aux PCs ou Macs, aux plus simples téléphones mobiles, set-top boxes, consoles de jeux, ou appareils hifi intégrés comme des lecteurs DVD, webradios, lecteurs MP3 mobiles, etc, qui ont un firmware intégrant une VM Java).
Tout est disponible sous licence LGPL (dont une traduction française est disponible dans le même dossier).
Chaque algorithme est implémenté dans une classe implémentant l'interface standard MessageDigestSPI (donc compatible avec toute implémentation d'un JCE et pouvant remplacer les algos fournis par Sun). Le code est compatible avec toutes les versions de Java (il n'y a pas de spécificité demandant Java 5 ou 6).
Chaque algo est fourni avec sa classe de test, contenant les valeurs attendues de la quasi totalité des vecteurs standardisés de test dans les normes américaines FIPS ou européennes. Le code effectue enfin un test de performance et fait la comparaison de performances avec l'algo du JCE de Sun, quand il est présent: cette comparaison n'est pas toujours possible si votre JCE par défaut n'a pas l'algorithme correspondant: la classe de Test est à adapter aux versions de JCE avec lesquelles vous voulez comparer les performances et en vérifier les résultats.
Tous les algos de hachage sécurisés standards des normes FIPS sont présents (MD5, SHA1, SHA224, SHA256, SHA384, SHA512), ainsi que quelques autres (Tiger et Whirlpool).
Il n'y a pas MD2 ni MD4 car ils ne sont pas sécurisés du tout (ils n'ont été recommandés dans aucune norme) et pourtant plus lents que MD5. Mais j'en a des versions de même qualité si vous les voulez.
(Note: les commentaires sont en anglais, mais ils sont mis en forme pour JavaDoc.)
24 mars 2009 à 21:34
Il n'y a aucune préférence de choix dans les bits de la clé obtenue à préserver: si une telle préférence existait et avait été démontrée, les algorithmes n'auraient pas été aprouvés avec la longueur de clé indiquée.
En terme de résistance aux collisions, évidemment, si on tronque trop, on augmente statistiquement le risque de collision (le passage de 256 bits à 64 bits mulitpliera ce risque par 2^(256-64) ce qui est évidemment énorme, et permet d'envisager à un coût faible la recherche de collision (qui surviendra sur ces 64 seuls bits, même si la clé originale sur 256 bits ne provoquait pas de collision).
Peut importe la méthode de réduction des clés utilisée, il n'y a aucun moyen de préserver la sécurité contre les collisions si on réduit le nombre de bits. Donc il est parfaitement inutile de chercher des méthodes compliquées (comme prendre un bit sur 4, ou compresser les 256 bits en les coupant en 4 paquaets combinés ensemble par un XOR): la sécurité obtenue sera la même.
Le seule problème avec une méthode avec troncature de clé plus longue, c'est que le calcul intermédiaire de clés plus longues nécessite plus de calcul, alors que cet excès n'apporte aucune sécurité supplémentaire significative par rapport à un autre algorithme "sécurisé" calculant directement une clé plus courte. Donc c'est vrai qu'on peut finalement se contenter d'utiliser SHA1 et non SHA256 comme algorithme de base.
D'une açon générale, pour une longueur de clé voulue donnée, on doit prendre un algorithme sécurisé ne calculant pas plus du double de cette longueur. Au delà c'est du travail inutile pour rien puisque le supplément d'effort est perdu.
Si le but n'est pas la sécurité mais simpement avoir des clés courtes suffisantes pour faire une table d'index par hachage résident en mémoire, SHA256 est certainement peu adapté et réduira les performances de votre application. Autant se contenter dans ce genre d'application de clé de hachage non sécurisées mais donnant une distribution suffisamment "plate" des bits afin que les "slots" dans la table de hachage soient équitablement utilisés. En général les tables de hachage en mémoire ont un nombre de slots relativement faible (guère plus de 65000) car on y stocke en fait un nombre limité d'objets (aussi car si on ugmente trop la tailel de la table de hachage, on va se retruver avec plein de slots vides qui occupent inutilement de la mémoire).
Pour cette raison, les table de hachage se contentent d'algorithmes plus simples basés sur une réduction par multiplication et addition dans un espace de Galois de longueur égale à la taille de la table de hachage. On choisit normalement une tailel qui sit un nombre premier pour les tailles faibles inférieures à 12 bits, et au delà on utilise une taille qui est une puissance de 2 dans le corps de Galois binaire, et cela suffit: le multiplicateur utilisé est en général dans ce cas un nombre proche du tiers de la taille totale N et qui soit premier avec cette taille, en fait le nombre premier le plus proche de N/e.
Par exemple pour une taille de table de hachage voisine de 1024, on choisit la taille première proche 1031, et le multiplicateur est alors le nombre premier le plus proche de 1031/e=379,28... qui est donc ici 379; la constante additive devrait être proche de la moitié de cette valeur, et également première, ici 379/2=189,5, on peut choisir 187; le calcul de hachage pour chaque octet à hacher est alors: nouvelleclé=(ancienneclé*379+187+octet) modulo 1031.
Pour indexer en revanche un nombre très élevé de fichiers par la valeur exacte de leur contenu (avec une clé si possible distincte pour la moindre modification de ce contenu) c'est là qu'on a besoin d'un algo sécurisé. Mais il ne faut pas se leurrer: il n'y a pratiquement aucun moyen d'assurer l'unicité et le risque de collision avec une clé de 64 bits seulement (quel que soit l'algo employé!). En revacnhe on peut estimer le nombre total de fichiers existants à tout instant ou le temps qui serait nécessaire pour atteindre un nombre donné, puis ensuite le nombre de fichiers auxquels il est possible d'accéder en un temps donné: s'il faut plus d'une vie à attendre même en employant tous les ordinateurs du monde pour en générer assez, il est pratiquement impossible d'obtenir une collision. On estimait il y a encore 5 ans qu'une longueur raisonnable actuelle est celle de la clé SHA1 (et pas moins), mais aujourd'hui la longueur minimale suggérée est de 128 bits (et par sécurité on choisit plutôt 192 bits).
En revanche contre le risque de production de collisions volontaires (dans le but de modifier des fichiers existants sans que cette modification soit détectable par la clé de hachage, il est hautement recommandé de ne plus descendre sous les 256 bits: c'est pour ça qu'on a l'algo SHA256, et déjà l'algo SHA512 pour le futur ou les plus paranoïaques (ainsi que SHA384 qui en est une version mineure obtenue par simple troncature de SHA512).
L'ennui des clés obtenues avec 256 bits ou moins est que le calcul se fait avec des entiers 32 bits: en augmentant le nombre de bits dans la clé, on a augmenté énormément le nombre d'opérations pour l'utilisation normale (ce qui pourrait rendre l'utilisation de ces algorithmes prohibitive pour la sécurisation tout en conservant les performances). De plus, en accroissant le nombre de variables internes, cela fait déborder les tailles de cache des processeurs, et les performances s'effondrent.
C'est pour ça que SHA512 (ou SHA384, mais aussi l'algo Tiger qui calcule des clé sur 192 bits d'une façon complètement différente des algos linéaires utilisés dans les algos MD ou SHA) utilise pour son calcul interne des entiers sur 64 bits et non 32 bits, des tailles maintenant supportées nativement par les processeurs, et qui diminuent le nombre d'opérations nécessaires sans réduire le nombre d'états internes et de degrés de libertés "cachés" dans la clé obtenue: cela a permi de continuer à augmenter la sécurité sans réduire significativement les performances (c'est vrai que le calcul sera plus long, mais ce n'est rien en fonction de la "loi de Moore" concernant l'évolution des performances des processeurs, ordinateurs, et systèmes en réseau, c'est à dire la capacité totale de calcul disponible en moyenne par poste utilisateur).
Bref, pour conclure: pas besoin de se compliquer avec les algos sécurisés connus si vos voulez des clés plus courtes: il suffit de les tronquer.
En revanche l'utilisation de deux clés obtenus par des algos distincts ne donne pour obtenir une clé composite ne donne PAS une sécurité équivalente à l'utilisation d'un algo sécurisé unique de longueur supérieure (la sécurité sera bien moindre).
Par exemple: SHA512 tronqué à 256 bits a une sécurité très légèrement supérieure à SHA256 (mais ce supplément est négligeable). Mais si on combine la clé SHA512 tronquée à 256 bits, avec la clé SHA256, on obtient une clé composite de 512 bits, mais qui sera de sécurité TRES NETTEMENT INFERIEURE à l'utilisation d'une clé unique SHA512 non tronquée !!!)
Ceci est une règle générale: les clés ne se combinent pas de façon additive mais sont seulement légèrement supérieures à la sécurité de la plus forte d'entre elles. La combinaison de deux clés d'algorithmes distincts ne peut servir qu'au cas où un algorithme réputé sécurisé voit sa sécurité brutalement diminuée: la seconde clé permet de conserver une sécurité minimale quand la securité de l'autre est compromise.
C'est pour ça que les certificats de sécurité des PKI comportent généralement une double signature (avec des clés de longueurs similaires, mais avec deux algorithmes), car il faudrait alors réussir simultanément à casser les deux algorithmes pour casser les deux certificats (le reste de l'effort de calcul pour réussir à produire une collision simultanée dans les deux algorithmes est alors négligeable par rapport à l'effort qui était initialement nécessaire pour casser chaque algorithme): la sécurité du certificat est alors effectivement celle de celui des deux algorithmes qui est le plus sécurisé.
En revanche une double clé ne sert à rien s'il s'agit de vérifier l'intégrité d'un fichier unique. La bonne méthode est plutôt d'utiliser un découpage du fichier en morceaux de taille inférieur à une limite maximale et de hacher chaque fragment: la sécurité de l'algorithme augmente mathématiquement quand la taille des fichiers est bornée (par exemple des fragments de 4Ko comportent 32768 bits, et il suffit d'avoir pour chacun d'eux une clé sur 128 bits, ce qui apporte une compression limitée à 1 bit sur 256 entre la oangueur de clé et celle du fichier:
ce taux de compression est correct et pas excessif par rapport à la longueur de clé (car on estime que que sur une clé sécurisée de taille N, au moins N/2 bits sont significatifs, mais souvent beaucoup plus et pratiquement jusqu'à N-k avec k très petit: ici une clé 128 bits d'un algo sécurisé approuvé donne au minimum 64 bits significatifs et peut-être jusqu'à 120 avec les méthodes connues de cryptanalyse actuelle.
Le risque de collision ne peut commencer à devenir un peu signiticatif sur 1 seul bit qu'à partir de longueur de fichiers dépassant le carré de cette longueur de résistance (120²=14400 bits, soit 1,8 Kio). Avec des fragments de 4Ko, on n'aura une résistance jusqu'à 2,2 bits, mais c'est insuffisant par rapport à la longueur significative de clé pour obtenir une collision véritable (ici 120 pour l'algo de clé sur 128 bits).
En fait on peut aller à des tailles de fragments en bits allant jusqu'au cube du nombre strictement minimum de bits significatifs dans la clé sécurisée: avec une clé de 128 bits, on a au strict minimum 64 bits significatifs et les fragments peuvent aller jusqu'à un strict maximum de 64^3=262144 bits (soit 32 Kio) (la clé 128 bits elle-même apportant une compression d'un tel bloc de 32 Kio d'un ratio de 1:256, ce qui est insigifiant par rapport à la taille de bloc à sécuriser ou authentifier)
Mais en revanche, pour des tailles de fichiers supérieures, il faut davantage de clés, une par bloc, et/ou des clés plus longues (mais c'est au prix des performances car des clés longues sur des fichiers longs représentent une masse de calcul non négligeable).
A vous de voir selon vos besoins s'il vous faut (et quand?) utiliser SHA256 (ou passer directement à SHA512 sur une plateforme 64-bits comme Intel IA64 ou AMD64/x64, puisque SHA512 est en fait maintenant légèrement plus rapide que SHA256 sur les plateformes 64-bits actuelles, avec du code spécialement optimisé pour chaque plateforme en prenant en compte les tailles de caches, et surtout les états d'attente ou de parallélisme possible des pipelines, le nombre de registres rapides et d'ALU indépendantes). Tout dépend largement de la taille des fichiers à hacher, de leur fréquence et de l'estimation de leur nombre total rencontré dans vos applications (ou parmi tous les utilisateurs de votre application si celle-ci est en réseau et notamment sur Internet), et du compromis fait entre performance et dégré (ou durée) de résistance aux attaques (éventuellement massives et coordonnées).
Et n'oubliez pas non plus de définir la valeur des données à protéger (et la durée de validité de cette valeur, puisqu'en général la valeur de toute information diminue avec le temps au contraire du coût nécessaire pour une tentative de violation de l'intégrité de cette information sur cette même période): il peut être plus rentable de ne pas utiliser inutilement les algos les plus sécurisés si au bout du temps nécessaire pour les casser cela a coûté plus cher que la valeur des données elle-mêmes.
24 mars 2009 à 17:53
24 mars 2009 à 17:30
pour le problème du binaire c'est bien résolu.
mais je ne voix pas comment je vais compresser et passer de 250 a 64 bit
si tu peux m'aider stp.
merci beaucoup.
24 mars 2009 à 17:10
24 mars 2009 à 16:52
merci énormément ciberrique de proposer ce code.
je l'ai testé et il marche très bien.
mais est ce que vous pouvez me montrer comment je peux le modifier de façon a ce que je puisse l'introduire dans mon code?
en fait j'ai besoin de hacher une chaine de caractère - comme c'est déjà fait - mais le résultat doit être en binaire et pas forcement en hexadécimal en plus je vais travailler au début avec 64 bit donc je veux diminuer la longueur du résultat.
merci d'avance pour la réponse.
1 mars 2009 à 19:26
Enfin comme tu l'as dis c'est une implementation qui suit les spécifications du fips donc comme dis précedemment sans optimisation.
Je dirais que tu as raison sur le fait qu'il faudrait optimiser cette source pour une utilisation quelconque mais pourquoi utiliser une source d'explication alors que sun fournis une implémentation fonctionnelle.
Ton commentaire est le bienvenu mais evite les monologues sans rapport avec les sources.
1 mars 2009 à 17:45
- Tout d'abord il y a trop de méthodes d'instance, alors qu'elles ne sont pas liées à l'instance de la classe, et devraient pour la plupart être déclarées comme fonctions statiques; ce sont les méthodes (appelées intensivement dans la classe SHA26): rotr() et shr() (non spécifiques à SHA256), ch(), maj(), sum0(), sum1(), sigma0() et sigma1()
- ensuite ces mêmes fonctions devraient être déclarées finales (l'algorithme ne peut pas changer et même dans ses variantes, ces méthodes sont figées) afin de permettre au compilateur de supprimer le coûteux appel de méthode virtuelle, et (au runtime) leur expansion par inlining (sur un JVM de type HotSpot); toutefois en déclarant ces méthodes privées, le compilateur de classe pourrait faire cette expansion inline lui-même (à condition de ne pas activer le débogage qui nécessite le support de la réflexion). Mais généralement on se passe de cette compatibilité pour Réflexion, en réalisant l'expansion inline directement dans le code source.
- la boucle de traitement est très inefficace: il y a trop de recopies de variables, alors que cette permutation n'est pas nécessaire. on obtient de bien meilleurs performances en réalisant que ces permutations se symbolisent dans un graphe, dont les varaibles peuvent aussi être réutilisées directement sans dépendre d'un autre calcul (il faut rappeler qu'en Java, une lecture de variable nécessite d'attendre que le stockage d'une valeur dans celle-ci soit terminé, ce qui expose une sécurité et une fiabilité pour les calculs en multithread, mais représente aussi une frontière limitant les performances: on a intérêt en limiter le nombre, afin de maximiser les possibilités de parallélisation au sein des processeurs (c'est encore plus vrai quand Java est porté sur des architectures massivement parallèles, par exemple si java est porté pour supporter des kernels de calcul (tel que SHA256 lui-même) sur GPU. SHA256 est très difficile à paralléliser complètement mais peut bénéficier d'une parallélisation partielle avec une série de kernels différents et non interdépendants (j'ai pu en compter jusqu'à 32 en optimisant le graphe de dépendance, et réduit aussi le nombre de "load" et de "store" de façon dramatique pour permettre des accélérations jusqu'à ×32 sur GPU, et de toute façon ×N sur tout CPU monocoeur utilisant un pipeline interne de N étages, rien qu'avec une distribution des instructions, ce qui est aussi possible en Java en préparant le Bytecode). D'une façon générale, cela divise largement le coût en temps et en énergie (particulièrement sur les téléphones mobiles et PC portables ou ultraportables "netbooks", où la consommation en milliwatt-heure par kilooctet traité est directement proportionnelle à une combinaison linéaire des "store" et "load" dans le code Java, cette consommation étant dominée par les "store", mais est également augmentée légèrement par le nombre d'états d'attente dans le CPU en cas de dépendance de résultats dans le pipeline; pour le temps total d'exécution c'est ce nombre d'états d'attente qui commence à dominer dans le temps total consommé).
Ce code est tel qu'il est écrit (reproduction directe de la description mathématique de l'algorithme publié par RSA sans aucune recherche supplémentaire), le plus lent de ceux qui existent déjà par ailleurs (même l'implémentation Sun dans le JRE est plus rapide, c'est peu dire, sachant qu'elle n'est pas non plus très optimisée, et que j'ai ma propre version qui est plus de 2 fois plus rapide en terme de débit par seconde par rapport à celle du JCE Sun sur n'importe quel PC 32 bit ou 64 bit, monocoeur ou multicoeur, les performances étant encore plus évidentes sur des architectures légères comme celle des mobiles, où ce type de classe ci-dessus serait excessivement lent, gourmand en CPU et en énergie).
Je ne critique pas trop le code pour ce qu'il est: une implémentation simple montrant en Java ce que veut dire la description officielle de l'alhgorithme (qui est faite, elle, sous une forme mathématique indépendante de tout langage, cette représentation étant toutefois plus adaptée à la simplification des formules dans les démonstrations de théorèmes et la recherche des propriétés). Mais pour une implémentation réelle, il faut savoir aller plus loin que la simple transcription (qui souvent peut manquer de performances voire même de précision dans les algos portant sur des valeurs ni discrètes ni même rationelles et qui peuvent même dépasser certaines bornes de capacité).
Allez un peu d'effort! Tu peux diviser facilement par 5 le nombre de stores(couteux) , et supprimer tous les if (couteux) de la fonction principale, et diviser par plus de 80 le nombre d'appels (couteux) de méthodes ! Pense que la permutation de variables est équivelente à un renommage de variables, puis recherche les expressions communes. Pour passer ensuite à la phase de "scheduling" d'instructions, il faut bien connaitre le bytecode java, et savoir comment la JVM l'analyse et les contraintes qu'elle lui impose avant de générer le code machine; quand on sait comment le bytecode et généré, on sait alors comment écrire le code source Java afin que le compilateur génère le code voulu.
J'avais posté sur ce site mon implémentation simple (en Java pur, car j'en ai aussi une version non postée ici: pour GPU via JNI que je compte peut-être porter avec Java3D ou JOGL s'ils savent correctement générer les kernels) mais l'administrateur l'a supprimé pour je ne sais quelle raison, alors que mon code démontrait clairement le même algorithme, mais aussi comment l'utiliser, et le comparait avec celui du JCE (dans une classe de test montrant aussi comment utiliser le JCE classique) pour démontrer les différences de performance.
Il y a d'autres implémentations des fonctions classiques de hachage sécurisé (MD5, SHA1, SHA256, SHA364, SHA512 sont recommandés mais il y en a d'autres qui ne font pas l'objet de recommandation uniquemlent car ils n'ont pas été évalués aussi profondément; et d'autres qui ne sont plus recommandés comme MD2 et MD4; ou qui son inadaptés à la signature de code contre les attaques volontaires comme les sommes de contrôles et les codes cycliques de contrôles ou CRC) avec leur code source disponible:
celle du JCE de Sun est disponible à tous gratuitement c'est la plus simple; celle pour GNU ClassPath, celle de GNU Crypto, ...
Il y a de nombreuses références sur le Web, mais aucune d'elle n'est aussi rapide que celle que j'ai écrite en Java; elle bat même pas mal d'implémentations en C++ ou assembleur qui ne sont optimales que sur un nombre limité de processeurs déjà obsolètes, avec à chaque fois le même problème:
Toute optimisation pour une machine donnée dans un langage à compilation staitue comme C ou C++ n'est souvent valide qu'en fonction d'un nombre précis de registres disponibles, et une taille de pipeline donnée (ce qui évolue sans arrêt même pour la même famille de processeurs avec un même code binaire compatible): l'avenir n'est plus aux logiciels totalement précompilés, mais à des machines virtuelles (Java, .Net, GL, etc...) recompilant le code directement sur la machine cible en fonction de ses capacités spécifiques et de son architecture (plus ou moins parallèle, plus ou moins hétérogène) et du profilage d'utilisation.
Raison de plus pour bien maîtriser le codage vers une machine virtuelle comme ici Java. L’autre solution serait que C ou C++ compileront du code vers la machine virtuelle uniquement (mais la JVM est actuellement incapable de traiter correctement du code issu d'un compilateur C/C++, contrairement à la machine virtuelle .Net, ce qui en fait un véritable problème pour l'avenir du langage Java lui-même). Il existerait bien la solution J#, mais elle est encore incompatible avec la JVM (dont la compatibilité nécessaire avec Reflection ne permet pas non plus un support correct sur .Net). Il nous manque encore une plateforme VM commune pouvant supporter presque nativement les deux environnements ainsi que les nouveaux environnements GL pour le parallélisme massif sur différents types de processeurs au sein d'un même OS contrôleur).
13 janv. 2009 à 20:15
12 janv. 2009 à 13:22
Je suis pas si fenéant que ça.
merci.
12 janv. 2009 à 13:18
12 janv. 2009 à 13:18
12 janv. 2009 à 13:14
12 janv. 2009 à 13:00
Tu as juste à le telecharger ici.
12 janv. 2009 à 12:58
9 janv. 2009 à 17:43
9 janv. 2009 à 15:44
comment est ce qu'on l'exécute svp?
merci
a+
5 janv. 2009 à 12:10
Meilleurs voeux à Tous
23 déc. 2008 à 21:59
23 déc. 2008 à 11:36
Merci pour ce code.
22 déc. 2008 à 16:31
22 déc. 2008 à 11:17
l'algo ne semble pas fonctionner entièrement.
Plusieurs hash sont inférieurs à 64 caractères.
exemple :
le hash256 de ABC12348 donne :
47b804a251770c65f5f68f93216f24bef2433be3c8eba51d5fa782b525fb9
alors que le vrai hash est :
47b804a2051770c605f5f68f093216f24bef2433be3c8eba51d5fa782b525fb9