(Septembre 2015) Une fonction de hachage moderne

Tu te poses trop de questions, contente-toi de lire ce qui est écrit sans chercher des difficultés là où il n'y en a pas. Ce que je vous ai fourni, c'est la version la plus simplifiée possible de la norme (pour tenter de contenter ceux qui ne savent pas lire), qui reste complète.

Qu'est-ce que tu vas chercher d'autres sources ? À part t'embrouiller, qu'est-ce que tu espères obtenir ? A, c'est l'état interne de la fonction, ce sur quoi on travaille à tout moment, et il s'agit d'une suite ordonnée de 25w bits.

Ensuite, il peut être plus pratique selon les circonstances de traiter cette suite de bits comme un objet ayant une autre forme. Pour la fonction de permutation, c'est beaucoup plus simple de la traiter comme une matrice de 5 × 5 trucs de w bits de longueur. Pour la fonction d'éponge, dans mon implémentation, il était plus simple de la traiter comme une liste de 25 trucs de w bits de longueur, mais dans l'implémentation de référence en C, ils ont préféré la traiter comme un unique buffer de 25w bits de long.

Et pour la démonstration mathématique de la solidité cryptographique de la fonction, et uniquement dans ce cadre, il est plus pratique de la traiter comme une matrice en 3D de 5 × 5 × w trucs de 1 bit de long. D'où le schéma que tu exhibes, qui est directement tiré de la norme, et qui n'a strictement aucun intérêt dans le cadre d'une simple implémentation de la fonction. Raison pour laquelle je n'en ai pas parlé.

De même que je n'ai pas parlé de la manière dont sont générées les constantes, parce que dans le cadre présent, on n'en a rien à foutre, et ça n'aurait fait que rendre les explications plus compliquées.

Voilà donc d'où sort le tableau de 5 × 5 : c'est simplement une manière différente (et plus pratique sur le moment) d'interpréter A.

Et c'est tout. Y'a rien de compliqué.

Quant à l'ordre dans lequel il faut mettre les fonctions, relis donc attentivement mon explication, et tu verras qu'il n'y a pas d'ambiguïté sur l'ordre d'utilisation, sauf sur la question du bourrage, parce que ça peut dépendre de ton choix d'implémentation.

Tu as la fonction d'éponge, qui absorbe petit à petit le message donné en entrée, puis recrache un condensat. C'est la « boucle principale » de la fonction. À la fin de chaque itération de cette boucle, l'état interne est envoyé à la fonction de permutation. Une fois que cette boucle principale est terminée, on met le condensat sous une forme lisible (ce que tu appelles l'étape « condensat »).

Quant au bourrage, ça dépend de ce qui est le plus pratique pour toi. Personnellement, je trouve plus simple de le placer avant la fonction d'éponge, mais l'implémentation de référence en C le place entre la partie absorption et la partie extraction de la fonction d'éponge.

l qui vaut 6 (c'est par défaut - why ?)

Quand j'te dis que tu te poses trop de questions… Ça vaut 6, parce que la norme SHA-3 a dit « nous, on va utiliser un l qui vaut 6, alors c'est comme ça », y'a aucune raison spécifique.

Le pourquoi du l=6 c'est quand même pour avoir w=64 et donc offrir des optimisations aux systèmes en 64 bits (probablement parce qu'ils sont ou seront à terme majoritaires sur le marché ?) si j'ai bien compris, non ? Ou alors c'est une optimisation qui aurait été possible même sans cette contrainte en interprétant A différemment, mais dans ce cas je suppose que ça nécessite de changer Keccac plus en profondeur ?

Tu te poses trop de questions […]

Je suis un geek, c'est tout. La question "Pourquoi ?" est très importante à mes yeux (surtout quand je ne comprends pas).

A propos, merci pour ton travail. Ce que je trouve dommage dans ton sujet, c'est qu'il y a peu d'effort de vulgarisation.

Bon voici un pseudo code, est-ce que ça correspond à l'implémentation que tu as pu en faire ?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

// Programme SHA-3
// Définition des constantes
RC = [
    0x0000000000000001, 0x0000000000008082, 0x800000000000808A,
    0x8000000080008000, 0x000000000000808B, 0x0000000080000001,
    0x8000000080008081, 0x8000000000008009, 0x000000000000008A,
    0x0000000000000088, 0x0000000080008009, 0x000000008000000A,
    0x000000008000808B, 0x800000000000008B, 0x8000000000008089,
    0x8000000000008003, 0x8000000000008002, 0x8000000000000080,
    0x000000000000800A, 0x800000008000000A, 0x8000000080008081,
    0x8000000000008080, 0x0000000080000001, 0x8000000080008008]

r = [
    [0, 36, 3, 41, 18],
    [1, 44, 10, 45, 2],
    [62, 6, 43, 15, 61],
    [28, 55, 25, 21, 56],
    [27, 20, 39, 8, 14]
]

// Définition des variables
l = 6
w = 2^l
b = 25w
m = "Mon message lambda"
A = [
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

// Préparation
tant que la taille du message n'est pas un multiple de r
    fonction de bourrage
fin

// Boucle principale
tant que la sortie est inférieur à N bit (= 256)

    // On entre les données dans A avec XOR
    fonction éponge

    // On permute les bits pour générer de l'entropie
    fonction de permutation
        tant que i est inférieur à 12+2l
            fonction 1,2,3 et 4
        fin
fin

// Etape condensat
conversion hexadécimal de la sortie

Salut !

Le sujet est vraiment très intéressant, mais je ne pense pas que j'aurais le temps de m'y consacrer, bien que j'ai envie de faire une implémentation en C++… Ca aurait fait de la concurrence à Berdes

D'ailleurs, @Dominus Carnufex, est-ce que l'on peut te piquer l'idée pour la proposer en exercice dans un cours ? (je pense au cours de C++ que je rédige avec informaticienzero, Akulen et paolo10) C'est vraiment un très bon exercice.

Merci d'avance

Oui, c'est pour cette raison qu'ils l'ont choisi.

Je suis un geek, c'est tout. La question "Pourquoi ?" est très importante à mes yeux (surtout quand je ne comprends pas).

A propos, merci pour ton travail. Ce que je trouve dommage dans ton sujet, c'est qu'il y a peu d'effort de vulgarisation.

Parce que ce n'est pas son rôle. Même si ça en chagrine certains, ce défi n'est pas un cours sur SHA-3, de la même manière que le Javaquarium n'est pas un tuto sur la reproduction des poissons en captivité. Je me contente de vous donner le minimum indispensable pour que vous puissiez effectivement réaliser le défi.

Lequel, on est bien d'accord, est dur si on essaye de le faire en entier, l'idée étant quand même qu'implémenter tout Keccak représente un défi. D'où les nombreuses pistes pour n'en faire que des morceaux…

Le bourrage devrait être à l'extérieur de la boucle, puisqu'on ne l'applique qu'une seule fois au message.

Bien sûr, je n'ai aucun droit d'auteur sur l'idée de SHA-3. Si vous voulez reprendre des morceaux du texte in extenso, ils sont sous licence BiPu L, comme toutes mes productions sur ce site.

C'est possible qu'on ait effectivement un peu perdu l'idée de "défi" en route en le considérant comme un bête TP/exercice

Même si ça en chagrine certains, ce défi n'est pas un cours sur SHA-3, de la même manière que le Javaquarium n'est pas un tuto sur la reproduction des poissons en captivité.

Sauf que Javaquarium ne demandait pas un algorithme spécifique. On pouvait le développer à sa manière. Ici, l'ordre des opérations ne change pas (ou très peu) - ce n'est pas comparable.

Je ne pense pas que tous les membres de Zds manipulent parfaitement les bits & octets, c'est déjà un défi ! Donc indiquer clairement l'architecture de l'algorithme, me semble un minimum (= le pseudo code que j'ai posté). C'est mon avis !

Merci pour la correction.

Ok, merci !

Comme promis je poste ma solution développée en C99 pour ce défi, elle se limite au standard SHA-3 (w = 64), tout en gérant toutes les longueurs de hash autorisées (de 32 bits à 768 bits si j'ai bien compté).

Le code se trouve sur github. EDIT nouveau lien, comprend également l'algo Keccak complet maintenant. Le module qui implémente l'algo spécifique SHA-3 est sha3.c

La partie ou j'ai eu le plus de difficulté est le padding, je trouve il n'est pas évident en C de prévoir tous les cas.

Concernant l'optimisation, j'ai rangé dans des tableaux tous les résultats de calculs pouvant l'être particulièrement dans la fonction de permutation (indices de tableaux modulo 5, calcul du 2x+3y).

Le type uint64_t est utilisé afin d'être certain de travailler toujours avec le bon w quelque soit la plateforme.

La solution comprend un programme de test où j'ai laissé tous les cas que j'ai vérifié, notamment ceux du lien fourni par Berdes, que je remercie et félicite pour sa solution complète au passage

Concernant les performances, j'ai pu tester sur mon PC windows 32 bits et sur un serveur Linux 64 bits. Sans surprise le programme est plus rapide sur la machine 64 bits : 100,000 itérations de mon programme de test (ce qui correspond à 5,000,000 de condensats générés) prennent 100 secondes en 32 bits, 40 secondes en 64 bits (sans affichage). La machine 32 bits étant plus puissante on peut considérer que le programme s'exécute environ 3 fois plus rapidement en 64 bits.

Voilà si vous avez besoin d'éclaircissement n'hésitez pas, je ne sais pas si j'irai plus loin en implémentant le keccak complet, je trouve que commencer par le SHA-3 uniquement est un bon moyen de comprendre le fonctionnement de l'algorithme dans un 1er temps, sans trop s'embêter avec la "cuisine de bits" sans doute nécessaire pour gérer toutes les longueurs, au moins en C.

EDIT: le résultat de l'exécution du programme de test ci-dessous, le programme demande 2 paramètres sur l'entrée standard:

• Le nombre d'itérations à exécuter

• Affichage des résultats ou pas (1/0)

@Yarflam : Je me permets de mettre mon grain de sel. Si tu ne veux pas que ce soit compliqué, ne fais pas de défis. Un défi n'a aucun intérêt si on te dit tout dès le début. De plus, la programmation, c'est dur. Surtout lorsqu'on travaille sur un projet qui doit respecter une norme, les normes étant des textes assez indigestes ; alors, étant donné que dans un vrai projet, tu dois te taper la norme en entier, c'est déjà un défi plus facile que ce qui se fait en réalité.

Alors tu ne peux pas critiquer un défi pour sa difficulté… D'autant plus que de ce que j'ai lu, les explications de @Dominus Carnufex sont assez complètes et claires pour qu'il n'y ait pas de problèmes de compréhension.

@mehdidou99 : L'idée c'est aussi que le lecteur apprenne des choses durant le défi, et chacun peut comprendre plus ou moins facilement les explications données. Il n'y a pas de lots à gagner ou de classement à la fin, les participants font ça pour enrichir leurs connaissances, et les défis ne s'adressent pas forcément à des professionnels ou des étudiants.

J'ai commencé à travailler sur cette fonction de hachage au moment où elle a été postée, mais j'ai été assez découragé par les phrases ambigues à partir de la fonction d'éponge. Du coup j'ai mis mon code de côté en attendant de voir comment les autres comprennent les indications, et pour le moment je n'ai que la fonction de permutation. D'autant qu'apparemment, je suis pas le seul à penser que certaines parties ne sont pas très claires et mériteraient plus d'explications.

Donc dire "ça devrait être dur, là c'est déjà trop facile", je suis pas d'accord.

@Dominus Carnufex : J'ai pas bien compris ta réponse à Yarflam. Peut être que tu étais fatigué ou pas trop d'humeur, mais je la trouve vachement agressive. Il a pas bien compris l'énoncé mais est intéressé et va chercher d'autres sources pour essayer de comprendre, et tu lui explique qu'il a tort et que tes explications devraient être suffisantes. Je veux bien croire que la norme est incroyablement compliquée comparée à ce que tu nous offres, mais visiblement, il y a certaines choses qui ne sont pas forcément claires pour tout le monde. C'est dommage, le sujet est réellement intéressant.

EDIT : Des résultats attendus pour les fonctions intermédiaires serait un réel ajout à l'énoncé et permettrait de tester son code au fur et à mesure et d'être certain de ne pas être à côté de la plaque.

EDIT : Des résultats attendus pour les fonctions intermédiaires serait un réel ajout à l'énoncé et permettrait de tester son code au fur et à mesure et d'être certain de ne pas être à côté de la plaque.

Ayant fait un bout, mais pas tout, je ne peux qu'approuver ceci.

J’approuve également pour la même partie du message …

Il y a un jeu de test ici - Tableau FIPS 202 - avec le résultat attendu à chaque étape, lien donné par Berdes qui pour ma part m'a bien servi dans les tests.

• "state" correspond à la matrice A
• "data to be absorbed" correspond à l'entrée déjà "rembourrée".

@Bibibye : Je n'ai pas dit que c'était "déjà trop facile", mais que c'est plus facile que la réalité. Et j'ai surtout dit que l'on ne peut pas critiquer un défi pour sa difficulté, car c'est un défi. S'il n'est pas adapté au niveau de certains, ils ne peuvent pas le critiquer "parce qu'il est trop dur". Ils peuvent juste essayer de le réaliser avec leurs capacités, et s'arrêter lorsque ça devient vraiment trop dur (à la limite demander de l'aide, mais sans critiquer parce que "c'est trop dur".

Je n'ai jamais dit que c'était trop dur. Le défi est tout à fait à mon échelle de compétence. C'est la structure de l'algorithme (avec son explication) qui est beaucoup plus difficile à assimiler.

Par ailleurs, je suis en train de développer l'algorithme en Python. Les explications de Dominus Carnufex m'ont aidé et mon code devrait paraître d'ici quelques temps.

Sans vouloir être trop critique et dénigrer le travail fait, ce défi me laisse une impression étrange.

En arrivant sur Sdz je pensais que le site se voulait une sorte de site du zéro2, c'est à dire un site pour le partage des connaissances, adapté aux débutants et basé sur une structure associative pour le protéger de dérives commerciales. Un super projet quoi.

En pratique j'ai l'impression que le site ressemble plus à l'association des potes de la fac de science qui partagent leurs connaissances entre eux (je caricature).

Je veux dire par là que très peu de choses sont faites pour le débutant et que la plupart des ressources sont difficilement accessibles car trop pointues/spécialisés ou demandant un niveau de prérequis important.

Je pensais que les défis de Clem étaient des défis qui se voulaient accessibles à tous sans nécessairement plus de prérequis qu'un niveau bac ou quelque chose du genre. Je me disais "cool je vais participer". Je me rends compte que même là, bien que Clem soit la mascotte du site, le contenu est réservé à ceux qui ont un bon niveau en algorithmique et qui doivent être plus ou moins professionnels de l'informatique. Moi en temps qu'étudiant en économie et web développeur amateur, je me sens complétement incapable de réussir ce défi même si j'en comprends le sens (j'imagine qu'une personne qui n'a pas une certaine culture informatique s’enfuie en courant dés la première ligne…^^).

Je comprends que ce genre de défi soit cool pour certains membres, mais n'ont pas plutôt leurs places dans le forum où dans une section particulière (quitte à ce que Clem indique l’existence du défi) ? Les défis de Clem ne devraient pas être l’occasion de rassembler l'ensemble de la communauté sans distinction, au lieu d'être un concours d'entre soi (ici entre programmeurs?).

J'ai parfois plus l'impression d'être sur un site réservé à des bac+3 en info que sur un site qui veut promouvoir le partage de la connaissance pour tous… et je trouve ça un peu dommage (le sdz n'existe plus, OC est commercial et zds est un site élitiste en pratique). Je suis le seul à pensez ainsi ?

Alors on va éviter de polluer ce sujet avec un débat qui peut certainement s'avérer intéressant mais n'a pas sa place ici. Si tu comptes t'en tenir à une critique des Défis de Clem, je t'invite à reposter ton message dans le sujet adéquat. Si, comme ton message le laisse penser, tu veux lancer un débat plus global sur le contenu de ZdS, je t'invite à créer un nouveau sujet dans le Bar à Smoothies et à y déplacer ton message.

Merci !

Dac, tu as raison ça sera plus pertinent je vais ouvrir un sujet ailleurs:)

Une fois que tu l'auras fait, peux-tu nous prévenir sur ce topic ? C'est un sujet intéressant.

Voilà c'est fait ici pour ceux qui veulent s'écharper discuter dans la joie et la bonne humeur !

Promis je ne pollue plus ce topic, je m'en vais