CALCUL DE HASH SHA 256

Commentaire de metheorn le 22/12/2008 11:17:35

Bonjour

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

Commentaire de metheorn le 23/12/2008 11:36:54

J'attends donc la nouvelle version avec impatience ;)
Merci pour ce code.

Commentaire de metheorn le 05/01/2009 12:10:59

Merci, ça marche nickel ;)

Meilleurs voeux à Tous

Commentaire de ciberrique le 09/01/2009 17:43:02

Salut, pour l'executer tu dois le compiler avec eclipse par exemple, sinon tu peux l'executer sans compiler directement dans eclispe.

Commentaire de ciberrique le 12/01/2009 13:00:31

Bonjour
Tu as juste à le telecharger ici.

Commentaire de ciberrique le 12/01/2009 13:18:32

Je ne pense pas avoir le temps ni l'envie de faire des recherches à ta place si tu as des questions utilise le forum et non pas ma source, merci.

Commentaire de moimeme0606 le 12/01/2009 13:22:18

Non, je vous demande pas de le faire a ma place parceque je l'ai deja fait et j'ai fait bcp de recherche mais le pblm c que c qlq chose de recent, il y a eu une seule publication par ADi Shamir c tout.
Je suis pas si fenéant que ça.
                           merci.

Commentaire de verdy_p le 01/03/2009 17:45:36

Le code manque d'optimisations évidentes:
- 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).

Commentaire de dadou1236 le 24/03/2009 16:52:53

bonjour tous le monde
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.

Commentaire de dadou1236 le 24/03/2009 17:30:36

rebonjour,
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.

Commentaire de verdy_p le 24/03/2009 21:34:53

Concernant la sécurité, la réduction de longueur d'une clé de hachage sécurisée doit se faire par une méthode préservant la distribution des bits. Si on suppose que SHA256 a une distribution plate (ce qui devrait être le cas pour tout algorithme éprouvé) et en reconnaissant que SHA256 est reconnu comme bien plus résistant que MD5 ou SHA1 par le fait qu'il utilise un nombre d'états internes (ou degréds de libertés) bien plus élevé, indépendamment de la longueur de clé finale), il suffit simplement de tronquer la clé à la longueur voulue: c'est ce qui est fait par exemple dans SHA384 qui consiste simpelment à tronquer la clé de hachage en prenant les 384 premiers bits de la clé de hachage SHA512 (cela n'augmente ni ne diminue pas le nombre d'états internes dans le calcul).

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.