(Septembre 2015) Une fonction de hachage moderne

Où nous allons parler de SHA-1, SHA-2 mais surtout SHA-3

Le problème exposé dans ce sujet a été résolu.

Bonjour à tous !

J’ai le plaisir d’être l’instigateur du premier Défi de Clem, qui abordera les rivages de la sécurité informatique. Mais avant toute chose, un peu de contexte.

Fonctions de hachage cryptographiques

Vous connaissez tous MD5 et SHA-1, je suppose ? On s’en sert massivement pour stocker des mots de passe dans une base de données sous une forme cryptée, ainsi que dans le domaine de la signature numérique. Toutes deux sont ce qu’on appelle des fonctions de hachage cryptographiques. Pour reprendre le lien donné à l’instant, elles ont les caractéristiques suivantes.

  1. À partir d’une entrée de n’importe quelle taille, elles produisent un résultat de taille fixe, souvent 128, 160 ou 256 bits.
  2. Il est strictement impossible de savoir quelle entrée a produit un résultat donné : contrairement à RSA, il n’y a pas de porte dérobée, la fonction est vraiment à sens unique.
  3. Deux entrées extrêmement similaires, même si elles ne diffèrent que d’un bit, donneront des résultats radicalement différents. Par corollaire, il est très difficile de produire volontairement un message qui donnera le même résultat qu’un autre message donné, ce que l’on appelle une collision.

Le résultat d’une fonction de hachage est appelé un condensat.

Bien évidemment, comme tout produit de la cryptographie, certains s’attachent à casser ces fonctions de hachage, de manière à pouvoir flouer les systèmes qui l’utilisent pour assurer leur sécurité. L’exemple typique est celui de l’authentification par un site Web : pas besoin de connaître le mot de passe de l’administrateur si l’on peut générer un mot de passe qui a le même condensat que le vrai.

Et justement, cela fait maintenant deux ans que MD5 a cédé aux assauts des cryptanalystes. Donc si par hasard certains d’entre vous l’utilisent encore, c’est mal ! SHA-1, qui a l’âge de ses artères, commence lui aussi à montrer des signes de faiblesse. Pas de souci, vous répondra-t-on : il suffit d’utiliser SHA-2, la nouvelle génération, plus robuste, plus sécurisée.

Mais au final, ce n’est qu’une fuite en avant. En effet, SHA-2 est un renforcement de SHA-1, qui est un renforcement de MD5, qui était lui-même un renforcement de MD4, qui lui-même venait renforcer MD2. Parce que tous ces algorithmes, ainsi que pas mal d’autres fonctions de hachage, utilisent la construction de Merkle-Darmgård, une sorte de patron de conception commun. Et à l’intérieur même de ce moule, les techniques utilisées pour mélanger les données sont à peu près les mêmes d’une génération à l’autre. Et forcément, depuis 30 ou 40 ans que les principales fonctions de hachage massivement utilisées sont toutes construites sur le même modèle, on sait fort bien comment les attaquer, dans les grandes lignes.

SHA-3

C’est pourquoi le NIST, l’organisme américain en charge des algorithmes SHA, a décidé de prendre les devants. Ils ont organisé un concours pour sélectionner une troisième génération de SHA bien avant que la deuxième ne soit sérieusement menacée, et le candidat retenu utilise une architecture nettement différente de la construction de Merkle-Darmgård. Je reviendrai dans un instant sur ce grand gagnant.

En effet, cela fait maintenant 3 ans que les résultats du concours ont été annoncés, mais SHA-3 reste utilisé de manière très minime. Il en existe peu d’implémentations dans l’un ou l’autre langage, et elles reposent souvent sur un appel indirect à l’implémentation de référence en C. Or, le 5 août 2015, après un trèèès long processus de validation officielle, le NIST a publié la version définitive du standard SHA-3. Et c’est là l’objectif de notre défi.

Implémenter l’algorithme SHA-3 dans le plus de langages différents possible.

Alors intéressons-nous d’un peu plus près à cet algorithme. À l’origine de SHA-3, il y a la famille de primitives cryptographiques Keccak (à prononcer ké-tchak). Famille, parce qu’il s’agit en réalité d’un modèle de construction permettant de générer des dizaines de fonctions de hachage similaires, en fonction de trois paramètres :

  • la taille de l’état interne de la fonction ;
  • la vitesse de production du condensat ;
  • la longueur du condensat voulu.

SHA-3 est en réalité composé de 4 variantes de Keccak, qui partagent une même taille d’état interne, mais de longueurs de condensat différentes, la vitesse de production de celui-ci étant calibrée pour être proportionnelle à sa longueur. Il me faut donc commencer par vous expliquer en détail le fonctionnement de Keccak. Suivez bien !

Pour les curieux, voici le site officiel de Keccak. Vous y trouverez la norme complète, ainsi que l’implémentation de référence en C. Attention, cependant : l’une et l’autre sont assez ardues à comprendre, et il est sans doute préférable que vous vous contentiez de mes explications simplifiées dans un premier temps.

Keccak

La fonction de permutation

Au cœur de Keccak se trouve la fonction de permutation, qui va complètement secouer les données qui lui sont fournies en entrée, de manière à les rendre méconnaissables. Celle-ci dépend d’un seul paramètre, appelé $l$, et qui peut prendre une valeur entière comprise entre $0$ et $6$. À partir de celle-ci, on définit la longueur $w = 2^l$, puis la taille de l’état interne dont nous avons parlé, qui vaut $b = 25w$.

La fonction de permutation prend en entrée un tableau de $5 \times 5$ cases de $w$ bits de longueur (attention, ce sont bien des bits et non des octets !) et renvoie un tableau du même format. Entre les deux, elle va faire passer ce tableau successivement par 4 fonctions chargées de le mélanger, et répéter l’opération un certain nombre de fois, nombre qui vaut $12 + 2l$. Voici comment ces 4 fonctions sont définies en pseudo code.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// Fonction 1 (appelée θ dans la publi originelle)
  C[x] = A[x,0] xor A[x,1] xor A[x,2] xor A[x,3] xor A[x,4],   forall x in 0…4
  D[x] = C[x-1] xor rotl(C[x+1],1),                            forall x in 0…4
  A[x,y] = A[x,y] xor D[x],                          forall (x,y) in (0…4,0…4)

// Fonction 2 (ρ et π combinées)
  B[y,2*x+3*y] = rotl(A[x,y], r[x,y]),               forall (x,y) in (0…4,0…4)

// Fonction 3 (χ)
  A[x,y] = B[x,y] xor ((not B[x+1,y]) and B[x+2,y]), forall (x,y) in (0…4,0…4)

// Fonction 4 (ι)
  A[0,0] = A[0,0] xor RC

Le A[x, y] de la fonction 1 est le tableau donné en entrée, B, C et D étant des variables intermédiaires. Les indices sont à comprendre modulo $5$. Par exemple, dans la fonction 2, si $x = 3$ et $y = 4$, alors $2x+3y = 18 mod 5 = 3$. La fonction rotl(mot, i) est la fonction « rotation de i bits vers la gauche ». Le RC de la fonction 4 est une constante qui dépend de la longueur des mots et d’à la combientième itération des 4 fonctions on en est. Voici le tableau de la valeur des différents RC quand $w$ vaut $64$ ($l$ vaut $6$, et il y a donc $24$ itérations).

Itération Valeur Itération Valeur
RC[ 0] 0x0000000000000001 RC[12] 0x000000008000808B
RC[ 1] 0x0000000000008082 RC[13] 0x800000000000008B
RC[ 2] 0x800000000000808A RC[14] 0x8000000000008089
RC[ 3] 0x8000000080008000 RC[15] 0x8000000000008003
RC[ 4] 0x000000000000808B RC[16] 0x8000000000008002
RC[ 5] 0x0000000080000001 RC[17] 0x8000000000000080
RC[ 6] 0x8000000080008081 RC[18] 0x000000000000800A
RC[ 7] 0x8000000000008009 RC[19] 0x800000008000000A
RC[ 8] 0x000000000000008A RC[20] 0x8000000080008081
RC[ 9] 0x0000000000000088 RC[21] 0x8000000000008080
RC[10] 0x0000000080008009 RC[22] 0x0000000080000001
RC[11] 0x000000008000000A RC[23] 0x8000000080008008

Pour un $w$ plus petit, il faut naturellement tronquer la partie gauche, et prendre uniquement les premiers RC de la liste, en fonction du nombre d’itérations. Quant au r[x,y] de la fonction 2, il s’agit là aussi d’une valeur définie en dur par la référence, et que voici (les valeurs sont bien sûr modulo $w$).

. x = 3 x = 4 x = 0 x = 1 x = 2
y = 2 25 39 3 10 43
y = 1 55 20 36 44 6
y = 0 28 27 0 1 62
y = 4 56 14 18 2 61
y = 3 21 8 41 45 15

Et voilà tout pour la fonction de permutation. Dans la version utilisée pour SHA-3, $l$ vaut toujours $6$ : les mots font alors 64 bits de longueur, ce qui peut permettre des optimisations sur les processeurs 64 bits.

La fonction d’éponge

Nous entrons là dans le vif du sujet ! C’est cette fonction qui traite les données dont on cherche à obtenir le condensat et qui les incorpore petit à petit dans la pâte. Un nouveau paramètre entre en jeu, et c’est la vitesse de production du condensat : elle est notée $r$ (pour rate), prend n’importe quelle valeur entière inférieure à $b$ la taille de l’état interne (cf. plus haut), et on définit également la « capacité » $c = b - r$ (uniquement pour des raisons pratiques, cf. plus bas). Dans l’idéal, $r$ est un multiple de $w$, mais ce n’est pas obligatoire.

La fonction d’éponge va passer elle aussi par un certain nombre d’itérations, nombre qui dépend de $r$ et de la longueur des données fournies en entrée. En effet, la première étape consiste à découper l’entrée en tronçons de $r$ bits de longueur (que l’on complétera ensuite si besoin avec des 0 à la fin, pour atteindre une longueur de $25w$ bits).

Pour cela, il faut s’assurer que la longueur de l’entrée (en bits) est bien un multiple de $r$, ce qui se fait au moyen du bourrage ou padding. Il existe deux façons différentes de bourrer l’entrée.

  • Dans la spécification de départ de Keccak, on concatène à la fin de l’entrée un bit qui vaut $1$, puis autant de $0$ que nécessaire, avant d’ajouter un dernier $1$ qui amène à une longueur multiple de $r$.
  • Dans la spécification de SHA-3, on commence par y concaténer les deux bits $01$, avant de faire comme dans la spécification de Keccak.

Chacun des tronçons de longueur $25w$ bits est ensuite lui-même découpé en mots de longueur $w$ bits. À chaque tronçon est associée une itération de la fonction d’éponge, constituée des étapes suivantes (avec A[x, y] qui constitue le résultat de l’itération précédente, sous forme d’un tableau de $5 \times 5$ mots de longueur $w$, comme vous vous en doutez).

  1. Le premier mot est xoré avec A[0, 0], le deuxième avec A[1, 0], le troisième avec A[2, 0], le sixième avec A[0, 1], etc. jusqu’à ce qu’on soit arrivé au bout du tableau.
  2. Le tableau A, auquel viennent d’être incorporés les mots du tronçon, est passé à la fonction de permutation.

L’état initial est un tableau de la taille adéquate, intégralement composé de $0$.

À ce stade, l’éponge a absorbé toute l’entrée, et il est maintenant temps pour elle de recracher un condensat. C’est là qu’intervient la longueur du condensat voulu. En effet, immédiatement après la fin des itérations d’absorption, et sans étape intermédiaire, on entame une série d’itérations légèrement différentes, définies ainsi.

  1. On concatène A[0, 0], puis A[1, 0], puis A[2, 0], etc. (dans le même ordre que plus haut), puis on en prend les $r$ premiers bits, que l’on concatène à la fin du condensat obtenu jusqu’ici (qui est vide au départ, naturellement). C’est là qu’il est intéressant que $r$ soit un multiple de $w$, car on n’a pas à jouer avec des fractions de mot.
  2. Le tableau A est passé à la fonction de permutation.

Et ainsi de suite jusqu’à ce que la longueur du condensat dépasse la longueur voulue. À ce moment-là, il suffit de tronquer les bits les plus à la fin du condensat pour le raboter à la bonne longueur.

Le standard SHA-3 définit 4 longueurs de condensat (224, 256, 384 et 512 bits), chacune associée à une valeur de $c$ (à partir de laquelle vous pouvez donc calculer $r$, qui est un multiple de $w$, donc tout est bien pour vous), qui est tout simplement le double de la longueur du condensat voulu. Les choses étant bien faites, une seule itération est suffisante pour recracher l’intégralité du condensat voulu.

Le défi

Voilà, vous avez toutes les cartes en main pour réaliser une implémentation complète dans votre langage préféré ! Vous pouvez choisir d’implémenter tout Keccak et d’y ajouter une surcouche pour SHA-3, ou alors d’implémenter uniquement les cas qui concernent SHA-3 (ce qui peut simplifier les choses, puisque vous n’avez pas à vous occuper des cas où $l < 3$, qui ne sont pas évidents à gérer sur nos ordinateurs qui fonctionnent par octets).

En outre, l’implémentation complète peut se découper en plus petites étapes, permettant à ceux qui n’ont pas beaucoup de temps ou qui ne sont pas très à l’aise de ne réaliser qu’une partie du défi. En voici la liste.

  • Le bourrage ou padding.
  • La fonction de permutation, qui elle-même incorpore
    • la fonction 1 (θ),
    • la fonction 2 (ρ et π),
    • la fonction 3 (χ),
    • la fonction 4 (ι).
  • La fonction d’éponge, qu’il est éventuellement possible de diviser en
    • absorption de l’entrée,
    • extraction du condensat.
  • Le condensat obtenu est une suite de bits, ce qui est assez illisible, et il est d’usage de la convertir en sa représentation hexadécimale.
  • Une étape bonus peut être d’essayer d’optimiser votre implémentation, dans les limites de ce que permet votre langage.

Sachez qu’il y a un réel cap de difficulté si vous essayez d’implémenter aussi les cas où $l < 3$, donc n’hésitez pas à vous simplifier la vie en ne les gérant pas. Sachez également que dans la fonction d’éponge, l’état interne est un tableau de 5 sur 5 où les y sont les lignes et les x les colonnes, mais que dans la fonction de permutation, il peut être plus pratique de travailler avec un tableau où les x sont les lignes et les y les colonnes.

La norme présuppose une machine petit-boutiste !

La norme part du principe que l’on est sur une machine petit-boutiste, ce qui a des conséquences assez sévères sur toutes les opérations bit-à-bit (donc à peu près toute la génératrice Keccak, en fait…).
Pour que vous compreniez bien, cela signifie que les bits sont lus à l’envers dans chaque octet (par exemple, s’il y a 0010 0001 sur la machine, le programme devra l’interpréter comme 1000 0100. Mais également que les octets au sein d’un mot de plus grande taille sont lus dans l’ordre inverse (par exemple, s’il y a 0x801255aa sur la machine, le programme devra l’interpréter comme les deux mots de 16 bits 0x1280 et 0xaa55 ou comme le mot de 32 bits 0xaa551280.
Si vous travaillez avec un langage comme le C qui touche directement à la mémoire, vous n’aurez pas de problème, car ces conversions sont faites automatiquement, mais si vous êtes dans un langage de plus haut niveau, il vous faudra sans doute prêter attention à ce que ce soit correctement géré.

Vous pouvez également faire le choix (si votre langage le permet) d’adopter une représentation gros-boutiste des données, mais il vous faudra alors impérativement prendre garde aux points suivants.

  • Le message fourni en entrée doit être interprété comme un espace mémoire contenant des octets petit-boutistes. Il faudra donc « retourner » chaque groupe de 8 bits (ainsi que le dernier groupe de bits si la longueur totale n’est pas un multiple de 8) de l’entrée avant d’appliquer le bourrage.
  • Le bourrage décrit (on ajoute un 1, puis des 0, puis à nouveau un 1) doit bien être compris comme tel. C’est si vous adoptez une représentation petit-boutiste que cela s’avère plus compliqué : par exemple, rajouter le 1 tout à la fin revient en fait à rajouter l’octet 0x80 (1000 0000 soit 0000 0001 en vrai sur la machine).
  • Les rotations vers la gauche deviennent des rotations vers la droite.
  • Les constantes RC doivent elles aussi être interprétées comme étant petit-boutistes. Cela signifie qu’une fois supprimés les bits de gauche dont vous n’avez pas besoin, il vous faudra « retourner » d’un bloc chaque constante. Par exemple, la constante 0x000000008000808B est rabotée en 0x808B pour des mots de 16 bits et en 0x8B pour des mots de 8 bits, mais sa représentation est toujours petit-boutiste : en gros-boutiste, elle devient respectivement 0xD101 et 0xD1.
  • Une fois que vous serez arrivé à un condensat sous la forme d’une suite gros-boutiste de bits, il vous faudra « retourner » chaque groupe de 8 bits (ainsi que le dernier groupe de bits si la longueur totale du condensat n’est pas un multiple de 8) avant de transformer le tout en sa représentation hexadécimale.

Enfin, afin de vérifier si votre implémentation fonctionne, voici les résultats attendus si vous fournissez une chaîne d’octets (bytestring) vide aux différentes variantes.

1
2
3
4
5
6
7
8
Keccak-224("")
0xf71837502ba8e10837bdd8d365adb85591895602fc552b48b7390abd
Keccak-256("")
0xc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
Keccak-384("")
0x2c23146a63a29acf99e73b88f8c24eaa7dc60aa771780ccc006afbfa8fe2479b2dd2b21362337441ac12b515911957ff
Keccak-512("")
0x0eab42de4c3ceb9235fc91acffe746b29c29a8c366b7c60e4e67c466f36a4304c00fa9caf9d87976ba469bcbe06713b435f091ef2769fb160cdab33d3670680e

1
2
3
4
5
6
7
8
SHA3-224("")
0x6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7
SHA3-256("")
0xa7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a
SHA3-384("")
0x0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004
SHA3-512("")
0xa69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26

Pour ceux qui voudraient pousser un peu plus loin, voici le résultat attendu si vous fournissez la suite de 29 bits 0110 0001 0110 0010 0110 0011 0011 0 aux variantes suivantes de Keccak.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
Keccak (l = 6, r = 1152, longueur du condensat = 224)
0x09edb5114e84f5d9c2e227dbd852666ed615449895384ac671b042c7
Keccak (l = 6, r = 1152, longueur du condensat = 223)
0x09edb5114e84f5d9c2e227dbd852666ed615449895384ac671b042 0b1000111
Keccak (l = 6, r = 1100, longueur du condensat = 224)
0xf4332c585e53a89021577d531cdaa862818752196ff6adb9a3d01873
Keccak (l = 3, r = 200, longueur du condensat = 128)
0x38428c4f002a6e20d576ad6b27942f2c
Keccak (l = 3, r = 200, longueur du condensat = 224)
0x38428c4f002a6e20d576ad6b27942f2c4c4b122a4b3c3585a8d7d22c
Keccak (l = 2, r = 50, longueur du condensat = 24)
0xa2c154

Je rajouterai quelques tests pour les fonctions intermédiaires, afin que vous puissiez en vérifier le bon fonctionnement.

Bon courage, et amusez-vous bien ! Je tiendrai à jour la liste des participations, langage par langage.

Implémentations proposées

C

fromvega (uniquement SHA-3) (version complète)

C++

Berdes

Haskell

Dominus Carnufex

+26 -0

Salut, vraiment sympa, j'ai pas eu le temps de tout lire mais je tenterais une implémentation en C++.

EDIT: En fait, je pense ne pas avoir pleins de notions de cryptographie qui sont nécessaires, pareil pour les maths, donc je crois que pour l'instant je vais rester sur des exercices légèrement plus simples.

+0 -0

Histoire de préparer le terrain, et d'évaluer la difficulté réelle du défi, j'ai réalisé par avance une implémentation complète (toutes les valeurs de $l$, $r$ et longueur de condensat sont acceptées) en Haskell, ce qui m'a permis de découvrir certaines difficultés (entre autres, cette histoire de boutisme). Commentaire et documentation compris, cela m'a pris une petite semaine tout mis bout à bout. En outre, l'algorithme étant comme bien souvent présenté de manière très impérative, ce code pourra éventuellement donner des idées à ceux qui veulent utiliser un langage fonctionnel.

J'ai fait les choses proprement, le code est organisé en trois modules : Data.Digest.Keccak qui contient la fonction proprement dite, Data.Verbum qui contient le type servant à représenter l'état interne de Keccak et toutes les fonctions servant à le manipuler, et Varia, qui contient quelques fonctions utilitaires. J'ai également séparé la documentation (sous forme de commentaires dans le format de Haddock) placée avant les fonctions, des commentaires explicatifs proprement dits placés après les fonctions qui en ont besoin.

Mais sans plus attendre, mon code !

Data/Digest/Keccak.hs

  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
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
{-|
Module      : Data.Digest.Keccak
Description : Keccak et SHA-3
License     : CeCIll-C
Stability   : experimental

Ce module fournit les quatre fonctions de hachage définies par la norme SHA-3, en deux
variantes chacune : l’une prend une liste de 'Data.Verbum' de largeur 1 en entrée,
l’autre un 'Data.ByteString'. Il fournit également la génératrice Keccak qui constitue
le cœur de ces fonctions.
-}

module Data.Digest.Keccak (
-- * Les quatre fonctions SHA-3 définies dans la norme
  sha3_224
, sha3_256
, sha3_384
, sha3_512
-- * Les variantes qui prennent des ByteString en entrée
-- |Noter que cela limite la longueur de l’entrée à un multiple de 8 bits.
, sha3_224_bs
, sha3_256_bs
, sha3_384_bs
, sha3_512_bs
-- * La génératrice Keccak
, keccak
) where

import qualified Data.ByteString as BS
import Data.List
import Data.Bits
import Data.Word

-- Pour des raisons de lisibilité, le type 'Verbum'
-- n’est pas importé qualifié.
import qualified Data.Verbum as V hiding (Verbum(..))
import Data.Verbum (Verbum(..))
import Varia


{---------------------------------------------------@
   Les quatre fonctions SHA-3 définies dans la norme
   -------------------------------------------------}


sha3_224 :: [Verbum] -> String
sha3_224 = keccak True 6 1152 224

sha3_256 :: [Verbum] -> String
sha3_256 = keccak True 6 1088 256

sha3_384 :: [Verbum] -> String
sha3_384 = keccak True 6  832 384

sha3_512 :: [Verbum] -> String
sha3_512 = keccak True 6  576 512
{-@
   La liste en fin de ligne ajoute les deux bits @01@ de bourrage
   spécifiques à SHA-3, avant de passer la main à Keccak
-}


{-----------------------------------------------------@
   Les variantes qui prennent des ByteString en entrée
   ---------------------------------------------------}


sha3_224_bs :: BS.ByteString -> String
sha3_224_bs = sha3_224 . V.bs_ad_vb0

sha3_256_bs :: BS.ByteString -> String
sha3_256_bs = sha3_256 . V.bs_ad_vb0

sha3_384_bs :: BS.ByteString -> String
sha3_384_bs = sha3_384 . V.bs_ad_vb0

sha3_512_bs :: BS.ByteString -> String
sha3_512_bs = sha3_512 . V.bs_ad_vb0


{--------------------------------------------------@
   La génératrice Keccak et ses fonctions associées
   ------------------------------------------------}


keccak :: Bool     -- ^Décide si l’on doit ou non utiliser le bourrage de SHA-3
       -> Int      -- ^La largeur des mots de l’état interne (@2^l@), telle que 0 <= @l@ <= 6.
       -> Int      -- ^La vitesse de production du condensat (@r@) en bits.
       -> Int      -- ^La longueur du condensat voulu en bits.
       -> [Verbum] -- ^Le message à hacher, sous forme de 'Data.Verbum' de largeur 1.
       -> String   -- ^Le condensat, en représentation hexadécimale.
keccak sha3 l r l_condens xs =
    if l < 0 || l > 6 then error e_falsum_l
    else if r < 1 then error e_falsum_r_1
    else if r > 2^l * 25 then error e_falsum_r_2
    else if False == foldl (\x y -> x && (0 == V.longitudo y)) True xs then error e_falsa_verba
    else scribere $ spongia l r l_condens $ farcire sha3 r $ xs
{-@
   La fonction en elle-même ne présente aucune difficulté : le message fourni en entrée est
   bourré, passé à la fonction d’éponge, puis le condensat est transformé en sa représentation
   hexadécimale, le tout au moyen de fonctions qui ne sont pas exposées.

   En revanche, c’est à ce moment-là qu’on fait toutes les vérifications nécessaires sur
   les paramètres fournis. En particulier, il faut s’assurer que le message est composé
   intégralement de 'Data.Verbum' de largeur 1. 
-}

-- |Cette fonction complète un message donné jusqu’à atteindre un multiple de @r@.
farcire :: Bool -> Int -> [Verbum] -> [Verbum]
farcire sha3 r verba =
    verba_voluta ++ farsura_sha3 ++ V.bit1 : (replicate n $ V.bit0) ++ [V.bit1]
        where verba_voluta = concat $ map (reverse) $ scindere 8 verba
              farsura_sha3 = if sha3 then [V.bit0, V.bit1] else []
              n = r - (length verba + 1) `mod` r - if sha3 then 3 else 1
{-@
   La norme considère qu’on est sur une machine petit-boutiste, et que l’entrée
   fournie doit /aussi/ être interprétée comme telle.
-}

-- |La fonction d’éponge de Keccak.
spongia :: Int -> Int -> Int -> [Verbum] -> [Verbum]
spongia l r l_condens = exitus . introitus where
    w = 2^l
    t_perm_t = transpose . permutare l . transpose
{-@
   Pour ce qui est de la structure générale, aucune difficulté particulière :
   on passe par la boucle d’absorption, puis par la boucle d’extraction.

   Pourquoi ne pas avoir défini des fonctions annexes non-exportées et plutôt
   utilisé des fonctions locales ? Pour éviter de devoir leur passer à chacune
   les trois arguments @l@, @r@ et @l_condens@ (ce qu’on a déjà dû faire pour
   passer de 'keccak' à 'spongia'), et de redéfinir dans chacune @w@ et 
   @t_perm_t@.

   Le premier est décrit dans la norme, je n’y reviens pas. Pour le troisième,
   il s’agit de se simplifier la vie. En effet, la fonction d’éponge travaille
   sur un état interne où les @y@ sont les lignes et les @x@ les colonnes,
   alors que dans la fonction de permutation, il est plus facile de travailler
   sur un état interne où les @x@ sont les lignes et les @y@ sont les colonnes.
-}

-- Boucle d’absorption
    introitus = foldl (absorbere) initium_spongiae . secare where
        secare = map (ad_formam_stati) . scindere r
        ad_formam_stati = map (V.vb0_ad_vbx l) . scindere w . farcire
        farcire xs = xs ++ replicate (25 * w - r) (V.bit0)
        initium_spongiae = scindere 5 $ replicate 25 $ V.verba_nulla !! l
        absorbere statum = t_perm_t . scindere 5 . zipWith (xor) (concat statum)
{-@
   La fonction 'secare' sert à découper le message (fourni en entrée) en
   morceaux de @r@ bits de long, puis de découper chacun en une liste de 25
   'Data.Verbum' de la bonne largeur, étant donné la taille d’état interne de
   l’éponge. Cela peut nécessiter de les compléter avec des bits valant 0
   pour atteindre une longueur totale de @25 * w@.

   L’état initial de l’éponge, entièrement composé de 0, est évidemment donné
   par 'initium_spongiae'.

   Pour chaque morceau à absorber, il est plus économique d’aplatir puis
   redécouper en 5 l’état interne, que de découper le morceau en 5 lignes de 5
   colonnes et de devoir utiliser deux 'zipWith' imbriqués. 
-}

-- Boucle d’extraction
    exitus = take l_condens . exitus' [] n where
        n = l_condens `div` r + if l_condens `mod` r == 0 then 0 else 1
        exitus' acc 0 _ = acc
        exitus' acc n statum = exitus' (acc ++ extractus statum) (n-1) (t_perm_t statum)
        extractus = take r . concat . map (V.vbx_ad_vb0) . concat
{-@
   Ici, seul 'extractus' réalise vraiment l’extraction à partir de l’état
   interne : il transforme tout le tableau en une liste de 'Data.Verbum' de
   largeur 1 et n’en garde que les @r@ premiers.

   Le reste de la fonction accumule ces extraits les uns à la suite des autres,
   en faisant passer l’état interne par la fonction de permutation entre deux
   extractions, jusqu’à avoir plus d’extraits que la longueur du condensat
   voulu. Il suffit alors de prendre le nombre de bits dont on a besoin.
-}

-- |La fonction de permutation de Keccak.
permutare :: Int -> [[Verbum]] -> [[Verbum]]
permutare l statum = foldl (iota . chi . rhopi . theta) statum $ constantia l
{-@
   Sans difficulté particulière, l’état interne passe par chacune des quatre
   fonctions intermédiaires, et ce pour chacune des constantes @RC@.
-}

-- |Cette fonction renvoie la liste des constantes @RC@ pour un @l@ donné.
constantia :: Int -> [Verbum]
constantia l = take (12 + 2*l) $ map (head . V.w8_ad_vbx l . brevius) rc where
    brevius = take n . V.long_idonea 8 . V.scindere_w8 . volvere . V.abscondere l
    n = V.quammulti !! l
{-@
   La norme partant du principe qu’on est sur un système petit-boutiste, les
   constantes @RC@ qu’elle donne doivent être retournées bit à bit, et pour les
   tailles de mot inférieures à 64 bits, c’est le début et non la fin des
   constantes qu’il faut conserver. Par exemple, pour un état en 8 bits, la
   première constante vaudra @0x80@ et non @0x01@.

   On commence donc par supprimer par un masque la partie des constantes qui ne
   nous intéresse pas, avant de retourner le tout, de découper le résultat en
   tronçons de 8 bits de long, et de ne conserver que les @n@ premiers tronçons
   en fonction de la longueur de mots voulue.

   À partir desquels on produit un 'Data.Verbum'. Pour rappel, 'V.w8_ad_vbx'
   renvoie une /liste/ de 'Data.Verbum', il faut donc prendre le premier pour
   avoir un 'Data.Verbum' seul.

   La liste ainsi obtenue contient toujours 24 constantes, il faut donc prendre
   uniquement les @12 + 2*l@ premières pour tomber en accord avec la norme.
-}

-- |Le tableau des constantes @RC@, dans leur largeur maximale, fourni dans la norme.
rc :: [Word64]
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]

-- |La fonction θ telle que définie dans la norme.
theta :: [[Verbum]] -> [[Verbum]]
theta statum = fundere statum (map (replicate 5) $ miscere $ paritas statum)
    where fundere = zipWith (zipWith (xor))
          miscere xs = zipWith (xor) (cxm1 xs) (cxp1 xs) where
              cxm1 xs = (last xs) : (init xs)
              cxp1 (x:xs) = map (\x -> rotate x (-1)) (xs ++ [x])
          paritas = map (foldl1 (xor))
{-@
   Pour chaque @x@ (donc ligne) de l’état courant, on calcule sa parité (@C[x]@
   dans la norme), puis on décale le premier ou le dernier élément d’un cran
   pour obtenir @C[x-1]@ et @C[x+1]@, et on fusionne le tout pour avoir @D[x]@
   (étape 'miscere'). Chacun des éléments de cette liste est dupliqué 5 fois et
   le tout est fondu dans l’état courant.
-}

-- |Les fonctions ρ et π combinées telles que définies dans la norme.
rhopi :: [[Verbum]] -> [[Verbum]]
rhopi statum = map (b_lineae statum) [0..4] where
    b_lineae xss n = zipWith (rotate) (extrahere_lineam xss n) (extrahere_lineam rotationes n)
    extrahere_lineam xss n = map (transpose xss !! n !!) (ordines !! (2*n))
    ordines = iterate (\(x:xs) -> xs ++ [x]) [0, 3, 1, 4, 2] :: [[Int]]
    rotationes = map (map (negate)) rot_normae
    rot_normae = [[ 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]] :: [[Int]]
{-@
   La mise en œuvre de cette fonction est assez complexe. Pour bien comprendre,
   il faut prêter attention à plusieurs points.

   Tout d’abord, la norme part du principe qu’on est sur un système petit-
   boutiste. Par conséquent, quand elle dit de décaler tous les bits d’un mot
   vers la /gauche/, il faut en réalité les décaler vers la /droite/ dans notre
   représentation gros-boutiste. C’est pourquoi, on utilise ici l’opposé des
   décalages fournis dans la norme.

   Ensuite, la norme suit l’ordre logique des indices de @A[x,y]@ pour
   construire petit à petit le contenu de @B[x,y]@. Or, il serait beaucoup plus
   pratique pour nous de savoir quel @A[x,y]@ (et donc quel @r[x,y]@) piocher
   pour construire chaque élément successif de @B[x,y]@.

   On se rend compte que chaque ligne du tableau d’arrivée utilise la colonne
   correspondante du tableau de départ, mais en mélangeant ses éléments.
   L’ordre voulu est 0-3-1-4-2 pour la première ligne, 1-4-2-0-3 pour la
   deuxième, et ainsi de suite en faisant à chaque fois tourner de deux rangs
   vers la gauche.

   On commence donc avec 'ordines', qui est une liste infinie de l’ordre de
   départ décalé d’un rang supplémentaire à chaque itération.

   Ensuite, 'extrahere_lineam' extrait une colonne donnée d’un tableau et la
   met dans l’ordre attendu grâce à la bonne itération de 'ordines'.

   Puis on applique cette dernière fonction à l’état courant et au tableau des
   décalages, et on 'rotate' chaque élément de la première du nombre de rang
   contenu dans l’élément correspondant de la seconde.

   Enfin, on répète cette opération pour chaque colonne de l’état de départ,
   afin de constituer chaque ligne de l’état d’arrivée.
-}

-- |La fonction χ telle que définie dans la norme.
chi :: [[Verbum]] -> [[Verbum]]
chi statum = zipWith (zipWith (xor)) statum (zipWith (zipWith (.&.)) statum1 statum2)
    where statum1 = map (map (complement)) (bxp1 statum)
          statum2 = bxp1 $ bxp1 statum
          bxp1 (x:xs) = xs ++ [x]
{-@
   Comme plus haut, on transforme un tableau de @B[x, y]@ en un tableau de @B[x+1, y]@
   simplement en déplaçant la première ligne à la fin du tableau. Répété deux fois
   pour @B[x+2, y]@.

   Et on est obligé de doubler les 'map' et 'zipWith', afin d’atteindre le deuxième
   rang de liste et de travailler vraiment sur les éléments eux-mêmes.
-}

-- |La fonction ι telle que définie dans la norme.
iota :: [[Verbum]] -> Verbum -> [[Verbum]]
iota ((x:xs):xss) rc = ((x `xor` rc):xs):xss
{-@
   Triviale.
-}

-- |Cette fonction transforme une liste de 'Data.Verbum' de largeur 1 en sa représentation
-- hexadécimale, suivie si besoin d’un complément en représentation binaire.
scribere xs = prima_pars ++ spatium ++ secunda_pars where
    prima_pars = 
        if fst verba == [] then ""
        else "0x" ++ (hexadecimare $ concat $ map (V.vbx_ad_w8) $ fst verba)
    secunda_pars = if snd verba == [] then ""
                   else "0b" ++ V.binarizare (snd verba)
    spatium = if fst verba == [] || snd verba == [] then "" else " "
    verba = if length xs `mod` 8 == 0 && length xs >= 8 then (octona, [])
            else if length xs < 8 then ([], head octona)
            else (init octona, last octona)
    octona = map (reverse) $ scindere 8 xs
{-@
   On commence par diviser la liste de 'Data.Verbum' en paquets de 8 et un
   éventuel dernier paquet plus petit, puis on inverse l’ordre des éléments de
   chaque paquet, afin de revenir à une représentation petit-boutiste.

   Ensuite, on convertit les paquets de 8 bits en leur représentation
   hexadécimale, et le paquet plus petit en sa représentation binaire, à chaque
   fois uniquement s’ils existent, bien sûr.

   Enfin, on fait un peu de mise en forme pour avoir quelque chose de joli en
   toutes circonstances.
-}


{-------------------------------------------------@
   Les messages d’erreur des différentes fonctions
   -----------------------------------------------}


e_falsum_l = "(`keccak`) Le paramètre l doit être compris entre 0 et 6 inclus."
e_falsum_r_1 = "(`keccak`) La vitesse de production du condensat doit être strictement positive."
e_falsum_r_2 = "(`keccak`) La vitesse de production du condensat doit être inférieure à la taille de l'état interne"
e_falsa_verba = "(`keccak`) Tous les 'Verbum' donnés en entrée doivent être de largeur 0."

Data/Verbum.hs

  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
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
{-|
Module      : Data.Verbum
Description : Un type pour manipuler des mots de taille variable en bits
License     : CeCIll-C
Stability   : experimental

Ce module définit le type 'Verbum' qui permet de manipuler des mots
de 1, 2, 4, 8, 16, 32 ou 64 bits de manière transparente, afin de factoriser
les fonctions qui peuvent travailler sur des 'Data.Word' de différentes
tailles. Il fournit également une série de fonctions pour les manipuler.
-}

module Data.Verbum (
  -- * Le type 'Verbum' et son instance de 'Data.Bits'
  Verbum()
  -- * Quelques constantes utiles
, clam
, quammulti
, verba_nulla
, bit0
, bit1
  -- * Les fonctions qui manipulent des 'Verbum'
, abscondere
, long_idonea
, longitudo
, scindere_w8
, summa_wx
  -- * Les fonctions de conversion entre formats
, w8_ad_vbx
, vbx_ad_w8
, vb0_ad_vbx
, vbx_ad_vb0
, bs_ad_vb0
, binarizare
) where

import qualified Data.ByteString as BS
import Data.Bits
import Data.Word
import Varia


{-------------------------------------------------@
   Le type 'Verbum' et son instance de 'Data.Bits'
   -----------------------------------------------}


{-|
   Le type 'Verbum' contient un entier qui détermine sa largeur en bits,
   calculée comme une certaine puissance de 2 (actuellement, 6 est le maximum 
   supporté), et une liste de 'Data.Word.Word8' représentant son contenu,
   en représentation gros-boutiste. Pour ceux qui ont moins de 8 bits de largeur,
   ce sont cependant les bits de poids le plus faible qui sont pris en compte.
   Il est impossible sans types dépendants de s’assurer que la longueur de la
   liste est cohérente avec la largeur du mot, c’est pourquoi le constructeur
   n’est pas exporté et seules les fonctions de conversion permettent de créer
   des 'Verbum' (ainsi que les constantes).
-}
data Verbum = V Int [Word8] deriving (Eq, Show)

-- |Le type 'Verbum' est une instance de 'Data.Bits', afin de pouvoir faire
-- usage des fonctions de manipulation bit à bit, indispensables à la cryptographie.
instance Bits Verbum where
    xor (V l xs) (V l2 xs2) = if l /= l2 then error $ "(`xor`) " ++ e_long_dissimiles
                              else V l $ zipWith (xor) xs xs2
    (.&.) (V l xs) (V l2 xs2) = if l /= l2 then error $ "(`.&.`) " ++ e_long_dissimiles
                                else V l $ zipWith (.&.) xs xs2
    (.|.) (V l xs) (V l2 xs2) = if l /= l2 then error $ "(`.|.`) " ++ e_long_dissimiles
                                else V l $ zipWith (.|.) xs xs2
    complement (V l xs) = V l $ map (complement) xs
{-@
   La gestion des erreurs n’est pas très propre, mais c’est le seul moyen, en
   l’absence de types dépendants de s'assurer qu’on ne xor/and/or entre eux
   que des 'Verbum' de même largeur.
-}

    -- |Comme il peut y avoir plusieurs longueurs de Verbum, cette fonction
    -- renvoie la plus courte possible, pour conserver de la place.
    --
    -- Notez que les fonctions setBit, clearBit et complementBit risquent d'avoir un
    -- comportement étrange !
    bit i
      | i <  1 = V 0 [bit i]
      | i <  2 = V 1 [bit i]
      | i <  4 = V 2 [bit i]
      | i <  8 = V 3 [bit i]
      | i < 16 = V 4 [bit (i-8), 0]
      | i < 32 = if i < 24 then V 5 [0, bit (i-16), 0, 0] else V 5 [bit (i-24), 0, 0, 0]
      | i < 64 = V 6 $ long_idonea 8 $ scindere_w8 bit64
      where bit64 = bit i :: Word64
    testBit (V _ xs) i = testBit (summa_wx $ map_ad_word64 xs) i
    bitSize (V l _) = 2^l
    isSigned _ = False
    popCount (V _ xs) = sum $ map (popCount) xs
{-@
   Ces fonctions ont été intégrées pour ne pas générer de /warning/ à la compilation, mais
   elles n’ont pas vocation à être réellement utilisées.
-}

    shift (V m xs) i = V m $ brevius $ shift' i $ summa_wx $ map_ad_word64 xs
        where shift' i x = shift x i
              brevius = long_idonea (length xs) . scindere_w8 . abscondere m
{-@
   Afin de gérer toutes les largeurs possibles, la procédure est un peu complexe. On commence
   par transformer la suite de 'Data.Word.Word8' en un unique 'Data.Word.Word64' correspondant
   à la même suite de bits, puis on applique le décalage, avant de ne conserver que les bits
   qui rentrent dans la largeur d’origine. Le tout est à nouveau découpé en une liste de
   'Data.Word.Word8' qui est intégrée au nouveau 'Verbum'.
-}

    rotate (V 0 [x]) _ = V 0 [x]
    rotate (V 1 [x]) i = V 1 $ (motum .&. 0x03) `xor` (shift (motum .&. 0x0c) (-2)) : []
        where motum = shift x (i `mod` 2)
    rotate (V 2 [x]) i = V 2 $ (motum .&. 0x0f) `xor` (shift (motum .&. 0xf0) (-4)) : []
        where motum = shift x (i `mod` 4)
    rotate (V 3 [x]) i = V 3 $ rotate x i : []
    rotate (V 4 xs) i = V 4 $ rotate' 2 i $ map_ad_word16 xs
    rotate (V 5 xs) i = V 5 $ rotate' 4 i $ map_ad_word32 xs
    rotate (V 6 xs) i = V 6 $ rotate' 8 i $ map_ad_word64 xs
{-@
   Là encore, la gestion des différentes tailles rend les choses assez complexes.

       * Pour une largeur de 1, toute rotation équivaut à une identité.
       * Pour une largeur de 2 ou 4, on décale les bits du bon nombre de rangs,
       avant de prendre ceux qui dépassent de la largeur, et de les remettre
       aux bits de poids les plus faibles. L’usage de 'mod' plutôt que de 'rem'
       garantit d’avoir toujours un décalage positif (donc vers la gauche) et
       de n’avoir donc qu’une seule situation à gérer.
       * Pour une largeur de 8, il suffit d’appliquer la rotation à l’unique
       'Data.Word.Word8' que compte le 'Verbum'.
       * Pour une largeur supérieure à 8, la procédure est similaire à celle
       utilisée pour le décalage, à ceci près que les suites de 'Data.Word.Word8'
       sont transformées en un 'Data.Word' de la taille correspondante et non
       systématiquement en un 'Data.Word.Word64'. Cela simplifie la procédure,
       au prix d’une répétition du code.
-}


{----------------------------@
   Quelques constantes utiles
   --------------------------}


-- |Les masques correspondant à chaque largeur de 'Verbum', pour ne conserver d’un
-- 'Data.Word.Word64' que les bits que le 'Verbum' pourra effectivement représenter.
clam :: [Word64]
clam = [0x01, 0x03, 0x0f, 0xff, 0xffff, 0xffffffff, 0xffffffffffffffff]

-- |Le nombre de 'Data.Word.Word8' que doit contenir chaque largeur de 'Verbum'.
quammulti :: [Int]
quammulti = [1, 1, 1, 1, 2, 4, 8]

-- |La représentation de 0 dans chaque largeur de 'Verbum'.
verba_nulla :: [Verbum]
verba_nulla = [V 0 [0], V 1 [0], V 2 [0], V 3 [0], V 4 [0, 0],
               V 5 [0, 0, 0, 0], V 6 [0, 0, 0, 0, 0, 0, 0, 0]]

-- |La représentation du bit 0, soit un 'Verbum' de largeur 1 contenant 0.
-- Parfaitement équivalent à @verba_nulla !! 0@.
bit0 :: Verbum
bit0 = V 0 [0]

-- |La représentation du bit 1, soit un 'Verbum' de largeur 1 contenant 1.
bit1 :: Verbum
bit1 = V 0 [1]


{-------------------------------------------@
   Les fonctions qui manipulent des 'Verbum'
   -----------------------------------------}


-- |Cette fonction ne conserve d’un 'Data.Word.Word64' que les bits qu’un 'Verbum' de
-- largeur @l@ pourra représenter.
abscondere :: Int -> Word64 -> Word64
abscondere l = ((clam !! l) .&.)

-- |Cette fonction sert à corriger le fait que 'scindere_w8' ne renvoie pas une liste de
-- la bonne longueur si au moins les 8 premiers bits du mot sont à 0. Elle en a été séparée
-- car il est parfois utile de glisser un traitement entre les deux étapes.
long_idonea :: (Bits a, Integral a) => Int -> [a] -> [a]
long_idonea n xs = replicate (n-(length xs)) 0 ++ xs

-- |Cette fonction renvoie la largeur d’un 'Verbum'.
longitudo :: Verbum -> Int
longitudo (V l _) = l

-- |Cette fonction sert uniquement à généraliser la transformation d’une liste de 'Verbum'
-- de largeur inférieure à 8 en un 'Data.Word.Word8' qui en représente la succession. C’est
-- pourquoi elle n’est pas exportée.
plicare :: Word8 -> Word8 -> [Verbum] -> Word8
plicare n = foldl (\x (V _ [y]) -> n*x+y)
{-@
   Elle n’est pas intégrée à la définition de 'vbx_ad_w8' pour une histoire de /scope/.
-}

-- |Cette fonction sert uniquement à raccourcir l'écriture de la fonction 'rotate' pour les
-- 'Verbum' de largeur supérieure à 8. C’est pourquoi elle n’est pas exportée.
rotate' :: (Integral a, Bits a) => Int -> Int -> [a] -> [Word8]
rotate' n i = long_idonea n . scindere_w8 . rotate'' i . summa_wx
    where rotate'' i x = rotate x i
{-@
   Elle n’est pas intégrée à la définition de 'rotate' pour une histoire de /scope/.
-}

-- |Cette fonction prend un 'Data.Word' de longueur quelconque et renvoie une liste des
-- groupes de 8 bits successifs qui le composent, sous forme de 'Data.Word.Word8'.
scindere_w8 :: (Bits a, Integral a) => a -> [Word8]
scindere_w8 n = map_ad_word8 $ scindere_w8' [] n
    where scindere_w8' acc 0 = acc
          scindere_w8' acc n = scindere_w8' ((n `mod` 256):acc) $ n `div` 256

-- |Cette fonction prend une liste de 'Data.Word' de longueur quelconque représentant des
-- groupes de 8 bits et renvoie un 'Data.Word' de même longueur représentant la succession
-- de ces groupes.
summa_wx :: (Bits a, Integral a) => [a] -> a
summa_wx =  foldl1 (\x y -> x*256+y) . map (satis_parvum)
    where satis_parvum n = if n < 0 || n > 255 then error e_summa_wx else n


{-------------------------------------------@
   Les fonctions de conversion entre formats
   -----------------------------------------}


{-|
   Cette fonction convertit un ou des 'Data.Word.Word8' en un ou des 'Verbum', le nombre
   de chaque dépendant de la largeur du ou des 'Verbum' voulu :

       * un 'Data.Word.Word8' converti en plusieurs 'Verbum' de largeur 1, 2 ou 4 ;
       * un 'Data.Word.Word8' converti en un 'Verbum' de largeur 8 ;
       * plusieurs 'Data.Word.Word8' convertis en un 'Verbum' de largeur supérieure à 8.
-}
w8_ad_vbx :: Int -> [Word8] -> [Verbum]
w8_ad_vbx _ [] = []
w8_ad_vbx 0 [x] = [V 0 [shift (x .&. 0x80) (-7)],
                  V 0 [shift (x .&. 0x40) (-6)],
                  V 0 [shift (x .&. 0x20) (-5)],
                  V 0 [shift (x .&. 0x10) (-4)],
                  V 0 [shift (x .&. 0x08) (-3)],
                  V 0 [shift (x .&. 0x04) (-2)],
                  V 0 [shift (x .&. 0x02) (-1)],
                  V 0 [x .&. 0x01]]
w8_ad_vbx 1 [x] = [V 1 [shift (x .&. 0xc0) (-6)],
                  V 1 [shift (x .&. 0x30) (-4)],
                  V 1 [shift (x .&. 0x0c) (-2)],
                  V 1 [x .&. 0x03]]
w8_ad_vbx 2 [x] = [V 2 [shift (x .&. 0xf0) (-4)],
                  V 2 [x .&. 0x0f]]
w8_ad_vbx 3 [x] = V 3 [x] : []
w8_ad_vbx l xs = if l < 0 || l > 6 then error $ "(`w8_ad_vbx`) " ++ e_falsum_l
                 else if length xs /= 2^(l-3) then error $ "(`w8_ad_vbx`) " ++ e_numerosius
                 else V l xs : []
{-@
   Comme il peut y avoir plusieurs de chaque en entrée comme en sortie, on travaille avec
   des listes, même si elles ne contiendront souvent qu’un seul élément. À la sortie, il
   faut évidemment en tenir compte dans le traitement.

   Les erreurs sont toutes regroupées dans le dernier motif, car c’est plus économique en
   nombre de messages d’erreur différents.
-}

-- |Cette fonction est l’exact inverse de la précédente et convertit un ou des 'Verbum' en
-- un ou des 'Data.Word.Word8'. 
--
-- prop> vbx_ad_w8 . w8_ad_vbx n = w8_ad_vbx n . vbx_ad_w8 = id
vbx_ad_w8 :: [Verbum] -> [Word8]
vbx_ad_w8 [] = []
vbx_ad_w8 ((V 0 [x]):xs) = if length xs + 1 /= 8 then error $ "(`vbx_ad_w8`) " ++ e_numerosius
                           else plicare 0x02 x xs : []
vbx_ad_w8 ((V 1 [x]):xs) = if length xs + 1 /= 4 then error $ "(`vbx_ad_w8`) " ++ e_numerosius
                           else plicare 0x04 x xs : []
vbx_ad_w8 ((V 2 [x]):xs) = if length xs + 1 /= 2 then error $ "(`vbx_ad_w8`) " ++ e_numerosius
                           else plicare 0x10 x xs : []
vbx_ad_w8 [(V l xs)] = if l < 3 then error $ "(`vbx_ad_w8`) " ++ e_numerosius else xs

-- |Cette fonction convertit une liste de 'Verbum' de largeur 0 en un 'Verbum' de largeur @l@.
vb0_ad_vbx :: Int -> [Verbum] -> Verbum
vb0_ad_vbx 0 [x] = x
vb0_ad_vbx l xs = if length xs /= 2^l then error $ "(`vb0_ad_vbx`) " ++ e_numerosius
                  else head $ concat $ brevius $ scindere 8 xs
    where brevius = map (w8_ad_vbx') . scindere (quammulti !! l) . map (vbx_ad_w8 . plus_0)
          plus_0 xs = replicate (if l == 1 then 6 else if l == 2 then 4 else 0) bit0 ++ xs
          w8_ad_vbx' = ultimum . w8_ad_vbx l . concat
          ultimum xs = if l < 3 then drop (length xs - 1) xs else xs
{-@
   Encore une fois, pour gérer toutes les largeurs de 'Verbum' en une seule fonction, on est
   obligé d’adopter une démarche non triviale. La liste de 'Verbum' de taille 1 est découpée
   en paquets de 8 qui sont convertis en 'Data.Word.Word8'. Cette liste de 'Data.Word.Word8'
   est elle-même convertie en un ou plusieurs 'Verbum' de la largeur voulue. Si cette largeur
   est inférieure à 8, on ne conserve que le dernier de la liste, le seul qui contienne
   effectivement les bits de départ.

   Afin de s’épargner ce traitement fastidieux pour une conversion de 'Verbum' de largeur 0
   en 'Verbum' de taille 0, on a mis un motif pour ce cas particulier.

   La fonction 'plus_0' s’assure qu'il y ait le bon nombre de 'Verbum' dans la liste passée
   à 'vbx_ad_w8', sinon, cette dernière gueule.
-}

-- |Cette fonction est l’exact inverse de la précédente et convertit un 'Verbum' de n’importe
-- quelle largeur en une liste de 'Verbum' de largeur 1.
--
-- prop> vbx_ad_vb0 . vb0_ad_vbx n = vb0_ad_vbx n . vbx_ad_vb0 = id
vbx_ad_vb0 :: Verbum -> [Verbum]
vbx_ad_vb0 (V 0 [x]) = V 0 [x] : []
vbx_ad_vb0 (V n xs) = drop n' $ concat $ map (w8_ad_vbx 0) $ scindere 1 xs
    where n' = case n of {1 -> 6; 2 -> 4; _ -> 0}

-- |Cette fonction convertit un 'Data.ByteString' en une liste de 'Verbum' de largeur 1.
bs_ad_vb0 :: BS.ByteString -> [Verbum]
bs_ad_vb0 = concat . map (w8_ad_vbx 0) . scindere 1 . BS.unpack

-- |Cette fonction convertit une liste de 'Verbum' de largeur 1 en sa représentation en
-- binaire sous forme de chaîne de caractères.
binarizare :: [Verbum] -> String
binarizare = binarizare' ""
    where binarizare' acc [] = acc
          binarizare' acc ((V 0 [x]):xs) = binarizare' (acc ++ if x == 0 then "0" else "1") xs


{-------------------------------------------------@
   Les messages d’erreur des différentes fonctions
   -----------------------------------------------}


e_long_dissimiles = "Les deux 'Verbum' doivent être de même largeur."
e_summa_wx = "(`summa_wx`) Tous les nombres fournis doivent être compris entre 0 et 255 inclus."
e_falsum_l = "La largeur des 'Verbum' doit être une puissance de 2, puissance comprise en 0 et 6 inclus."
e_numerosius = "Le nombre d’éléments de la liste donnée en entrée doit être cohérent avec la largeur de 'Verbum' utilisée."

Varia.hs

 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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
{-|
Module      : Varia
Description : Petites fonctions utilitaires
License     : CeCIll-C
Stability   : experimental

Ce module contient quelques fonctions utilitaires ne se rattachant à aucun domaine
d’utilisation particulier. Faire un module de vrac n’est évidemment pas idéal, mais
ça évite d'avoir à les répéter dans chaque fichier.
-}

module Varia (
  hexadecimare
, map_ad_word8
, map_ad_word16
, map_ad_word32
, map_ad_word64
, scindere
, volvere
, zeroBits
) where

import Data.Bits
import Data.Word

-- |La fonction 'hexadecimare' donne la représentation hexadécimale d’une suite d'octets,
-- fournie sous la forme d’une liste de 'Data.Word.Word8'.
hexadecimare :: [Word8] -> String
hexadecimare xs = concat $ map (ad_litteras . fromIntegral) xs
    where ad_litteras x = [litterae !! (x `div` 16), litterae !! (x `mod` 16)]
          litterae = "0123456789abcdef"
{-@
   Le passage par 'fromIntegral' est nécessaire, car '!!' n’accepte que les 'Int'.
-}

-- |Prend une liste de 'Data.Word' et les convertit en 'Data.Word.Word8'.
map_ad_word8 :: (Bits a, Integral a) => [a] => [Word8]
map_ad_word8 xs = map (fromIntegral) xs

-- |Prend une liste de 'Data.Word' et les convertit en 'Data.Word.Word16'.
map_ad_word16 :: (Bits a, Integral a) => [a] => [Word16]
map_ad_word16 xs = map (fromIntegral) xs

-- |Prend une liste de 'Data.Word' et les convertit en 'Data.Word.Word32'.
map_ad_word32 :: (Bits a, Integral a) => [a] => [Word32]
map_ad_word32 xs = map (fromIntegral) xs

-- |Prend une liste de 'Data.Word' et les convertit en 'Data.Word.Word64'.
map_ad_word64 :: (Bits a, Integral a) => [a] => [Word64]
map_ad_word64 xs = map (fromIntegral) xs

-- |Divise une liste en sous-listes de @n@ éléments de long.
scindere :: Int -> [a] -> [[a]]
scindere _ [] = [[]]
scindere 0 _ = [[]]
scindere n xs = if n < 1 then error e_scindere
                else scindere' [] xs
    where scindere' acc [] = acc
          scindere' acc xs = scindere' (acc ++ [take n xs]) $ drop n xs

e_scindere = "(`scindere`) La taille des sous-listes doit être un nombre strictement positif."

-- |Inverse l’ordre des bits dans un 'Data.Word'.
volvere :: Bits a => a -> a
volvere n = foldl1 (.|.) $ map (volvere') [0..ultimum]
    where volvere' i = if testBit n i then bit (ultimum - i) else zeroBits
          ultimum = ((bitSize n) - 1)
{-@
   On pourrait utiliser 0 au lieu de 'zeroBits', mais cela entraînerait une contrainte 
   supplémentaire 'Num a', qui met la pagaille quand on utilise 'volvere' conjointement
   à des fonctions qui n’ont pas cette contrainte.
-}

-- |Un 0 de type 'Bits a' mais pas 'Num a'.
zeroBits :: Bits a => a
zeroBits = clearBit (bit 0) 0
{-@
   D’après la documentation, il est défini par le module 'Data.Bits', mais mon GHC ne
   le trouve pas, alors je le réimplémente d’après la définition donnée dans la doc.
-}

J'ai réalisé un tout petit test de performances, avec le programme suivant (composé d'un script bash qui appelle 1000 fois le programme en Haskell, chaque fois avec une valeur différente).

1
2
3
for i in `seq 1 1000`
    do ./test $i > /dev/null
done

1
2
3
4
5
6
7
import Data.Digest.Keccak
import qualified Data.ByteString.Char8 as BS
import System.Environment

main = do
    args <- getArgs
    putStrLn $ sha3_224_bs $ BS.pack $ head args

Je l'ai fait tourner trois fois, sur mon ordi personnel dans des conditions non optimales (ordi allumé depuis des jours, Firefox et IRC en tâche de fond, etc.) et j'arrive à une moyenne de 18,6 secondes, soit à la louche 18ms par condensat.

EDIT : j'ai refait des tests avec le code suivant qui me permet de ne pas passer par un script bash, et les résultats sont nettement meilleurs, avec 13ms par condensat, soit presque 30 % de gain juste en améliorant le test. Bon, ça reste faiblard par rapport à une implémentation en C/C++, mais il apparaît assez clairement que le mode de représentation de l'état interne n'est pas optimal : il faudrait sans doute quelque chose qui se rapproche du byteset du C++.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
import Data.Digest.Keccak
import qualified Data.ByteString as BS
import Control.Monad
import Data.Word

main = do
     mapM (putStrLn) $ map (sha3_224_bs . BS.pack) $ tutu

toto = [0..255] :: [Word8]
tata = map (replicate 256) toto
tutu = concat $ zipWith (zipWith (\x y -> [x, y])) tata $ replicate 256 toto
+5 -1

Dans la deuxième fonction de permutation B[y,2*x+3*y], il ne s'agirait pas plutôt de A[y,2*x+3*y] ?

EDIT : ah non, faut que je relise.

EDIT 2 : Pour la fonction d'éponge, l'histoire de vitesse de production du condensat n'est pas claire pour moi. Quel est l'intéret de $r$ ? Les tronçons doivent-ils avoir une longueur de $r$ bits ou de $25w$ bits ?

+0 -0

Le sujet m'intéresse, mais le pavé initial m'a complètement découragé – je pensais le lire pendant ma pause mais il est trop long (9 pages).

Je suggère 2 améliorations :

  1. Soit déplacer le contexte (certes, très intéressant, mais 1.5 pages) après l'énoncé, ou au moins fournir un moyen d'aller directement à l'énoncé tout en haut du premier message.
  2. Rendre beaucoup moins visible la problématique du boutisme, puisque l'immense majorité des ordinateurs sur lesquels on programme dans un langage proche du matériel (x86 ou x86_64 donc) n'a pas ce problème, ce qui économiserait un « avertissement » d'une page entière.

J'espère trouver le courage de me pencher sur ce défi un jour.

+10 -1

J'ai eu exactement la même réaction que SpaceFox à la lecture de ce sujet. Je n'ai pas eu le courage de dépasser le premier scroll. C'est dommage parce qu'il a l'air intéressant, détaillé et documenté, mais l'aspect pavé du PO m'a découragé d'en entreprendre la lecture.

Peut-être que quelques balises [[secret]] bien placées permettraient de le rendre plus digeste en venant plus directement au fait ?

+6 -1

Pareil, étant totalement débutant dans le domaine de la programmation (mon niveau est pour le moment aux GUIs) je comptais faire ces petits défis en Python ou Ruby. Puis j'ai vu le défi… et le pavé d'instruction… Je suis retourné dans ma caverne de suite (ce n'est pas faute d'avoir essayé de le lire !)

+3 -1

Complexe mais intéressant à lire pour peu qu'on s'intéresse au sujet. Cependant je suis pas fan du tout du choix de présentation adopté : gros pâté de texte complexe et impossible à retenir en première lecture suivi tout à la fin du "vous n'êtes pas obligés de tout faire". Je pense que le défi serait plus abordable s'il était découpé comme indiqué à la fin :

En outre, l’implémentation complète peut se découper en plus petites étapes, permettant à ceux qui n’ont pas beaucoup de temps ou qui ne sont pas très à l’aise de ne réaliser qu’une partie du défi. En voici la liste.

  • Le bourrage ou padding.
  • La fonction de permutation, qui elle-même incorpore
    • la fonction 1 (θ),
    • la fonction 2 (ρ et π),
    • la fonction 3 (χ),
    • la fonction 4 (ι).
  • La fonction d’éponge, qu’il est éventuellement possible de diviser en
    • absorption de l’entrée,
    • extraction du condensat.
  • Le condensat obtenu est une suite de bits, ce qui est assez illisible, et il est d’usage de la convertir en sa représentation hexadécimale.
  • Une étape bonus peut être d’essayer d’optimiser votre implémentation, dans les limites de ce que permet votre langage.

Dans l'idéal je trouve qu'il faudrait que chacun de ces points soit un "sous-défi" déclaré explicitement comme tel au cours de la lecture, avec des indications de code, etc. J'imaginais un truc qui se rapproche plus de l'exercice "Javaquarium" en gros.

Je pense que je vais tenter le défi sous sa forme actuelle mais c'est bien parce que j'ai eu des cours de sécu l'année dernière et que je sais d'avance de quoi ça parle, sinon je pense pas que j'aurais le coeur à tenter.

Bref, sinon deux trois petites remarques plus sur le fond :

contrairement à RSA, il n’y a pas de porte dérobée

?

Et justement, cela fait maintenant deux ans que MD5 a cédé aux assauts des cryptanalystes

Je crois que depuis 10 ans j'ai toujours entendu ça, que ça a été démenti, que c'est redevenu vrai… Est-ce qu'il y a de vraies sources qui annoncent incontestablement MD5 comme cassé au sens cryptographique ?

Donc si par hasard certains d’entre vous l’utilisent encore, c’est mal

J'aurais tendance à dire que ça dépend pourquoi, à ma connaissance il n'y a pas tellement de risques à utiliser MD5 comme bête checksum, je me trompe peut-être ?

la fonction de permutation […] dépend d’un seul paramètre, appelé l, et qui peut prendre une valeur entière comprise entre 0 et 6. La fonction de permutation prend en entrée un tableau de 5×5 cases de w bits de longueur

?

petit-boutiste

Je suis pas contre le protectionnisme de la langue mais c'est possible de préciser (entre parenthèses à la limite) que ça parle de "little-endian", terme bien plus répandu et reconnu ? :-°

Dernier point sur le code Haskell proposé, le latin dans du code c'est rigolo mais personnellement je peux vraiment pas lire ça, c'est dommage de perdre autant d'intérêt sur un exemple d'implémentation aussi utile à cause d'un pareil détail :/

+7 -0

Note : pour les plus pressés, j'ai un code fonctionnel (sha3 et keccak) disponible à la fin du message.

Bon, je me suis lancé dans le code en C++ (le Haskell ne me semble pas particulièrement adapté pour ce genre de tâche, ou du moins, pas au premier abord).

Je me suis beaucoup basé sur la lib standard et notamment sur bitset, array et vector<bool>. Cela m'a permis d'éviter tout problème lié à l < 3. De même, les paramètres l, r et la taille du condensat sont en template, ce qui permet qu'il soit connu à la compilation et donc que le compilateur optimise un maximum pour chaque ensemble de paramètres utilisé.

J'ai découpé au maximum en petites fonctions simple, ce qui donne finalement quelque chose de facilement lisible. Le code complet fait environ 200 lignes (compilable avec clang ou gcc en c++14) :

  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
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <array>
#include <bitset>
#include <vector>

namespace keccak {
  /* Définition des alias de types */
  template<size_t w>
  using Vec = std::array<std::bitset<w>, 5>;

  template<size_t w>
  using Mat = std::array<Vec<w>, 5>;


  /* Définitions des constants et constexpr */
  constexpr size_t pow(size_t x, size_t n) {
    return n>0 ? x*pow(x, n-1) : 1;
  }

  template<size_t w>
  const std::array<std::array<size_t, 5>, 5> r{{
    {{ 0%w, 36%w,  3%w, 41%w, 18%w}},
    {{ 1%w, 44%w, 10%w, 45%w,  2%w}},
    {{62%w,  6%w, 43%w, 15%w, 61%w}},
    {{28%w, 55%w, 25%w, 21%w, 56%w}},
    {{27%w, 20%w, 39%w,  8%w, 14%w}}
  }};

  template<size_t w>
  const std::array<std::bitset<w>, 24> RC{{
    0x0000000000000001ULL,
    0x0000000000008082ULL,
    0x800000000000808AULL,
    0x8000000080008000ULL,
    0x000000000000808BULL,
    0x0000000080000001ULL,
    0x8000000080008081ULL,
    0x8000000000008009ULL,
    0x000000000000008AULL,
    0x0000000000000088ULL,
    0x0000000080008009ULL,
    0x000000008000000AULL,
    0x000000008000808BULL,
    0x800000000000008BULL,
    0x8000000000008089ULL,
    0x8000000000008003ULL,
    0x8000000000008002ULL,
    0x8000000000000080ULL,
    0x000000000000800AULL,
    0x800000008000000AULL,
    0x8000000080008081ULL,
    0x8000000000008080ULL,
    0x0000000080000001ULL,
    0x8000000080008008ULL
  }};


  /* Définitions des sous-fonctions de permutation */
  template<size_t w>
  void theta(Mat<w> &A) {
    Vec<w> C;
    for(size_t x{0}; x<5; ++x) {
      for(size_t y{0}; y<5; ++y) {
        C[x] ^= A[x][y];
      }
    }

    Vec<w> D;
    for(size_t x{0}; x<5; ++x) {
      D[x] = C[(x-1)%5] ^ (C[(x+1)%5] << 1);
    }

    for(size_t x{0}; x<5; ++x) {
      for(size_t y{0}; y<5; ++y) {
        A[x][y] ^= D[x];
      }
    }
  }

  template<size_t w>
  void rhoPi(const Mat<w> &A, Mat<w> &B) {
    for(size_t x{0}; x<5; ++x) {
      for(size_t y{0}; y<5; ++y) {
        B[y][(2*x+3*y)%5] = A[x][y] << r<w>[x][y];
      }
    }
  }

  template<size_t w>
  void chi(Mat<w> &A, const Mat<w> &B) {
    for(size_t x{0}; x<5; ++x) {
      for(size_t y{0}; y<5; ++y) {
        A[x][y] = B[x][y] ^ ((~B[(x+1)%5][y]) & B[(x+2)%5][y]);
      }
    }
  }

  template<size_t w>
  void iota(Mat<w> &A, size_t num_op) {
    A[0][0] ^= RC<w>[num_op];
  }


  /* Définitions des sous-fonctions de Keccak */
  template<size_t r>
  std::vector<bool> padding(const std::vector<bool> &input) {
    std::vector<bool> padded{input};
    padded.push_back(false);
    padded.push_back(true);
    padded.push_back(true);
    size_t num_zero{r - (padded.size()+1)%r};
    padded.insert(padded.end(), num_zero, false);
    padded.push_back(true);
    return padded;
  }

  template<size_t r, size_t l>
  void sponge(Mat<pow(2, l)> &A,
      const std::vector<bool> &input,
      size_t pos) {
    std::bitset<pow(2, l)> current_word;
    size_t end_pos{pos+r};
    for(size_t y{0}; y<5; ++y) {
      for(size_t x{0}; x<5; ++x) {
        for(size_t b{0}; b<pow(2, l); ++b) {
          if(pos < end_pos) {
            current_word[b] = input[pos];
            ++pos;
          } else {
            current_word[b] = 0;
          }
        }
        A[x][y] ^= current_word;
      }
    }
  }

  template<size_t l>
  void permutation(Mat<pow(2, l)> &A) {
    Mat<pow(2, l)> B;
    for(size_t num_op{0}; num_op<12+2*l; ++num_op) {
      theta(A);
      rhoPi(A, B);
      chi(A, B);
      iota(A, num_op);
    }
  }

  template<size_t r, size_t l, size_t output_size>
  std::bitset<output_size> keccak(const std::vector<bool> &input) {
    static const size_t w{pow(2, l)};
    static const size_t internal_size{25*w};
    static_assert(l <= 6, "Valeur de 'l' invalide : les mots ne peuvent faire plus de 64 bits.");
    static_assert(r <= internal_size, "Valeur de 'r' invalide : "
        "la vitesse de production ne peut excéder la taille de l'état interne (25*2^l).");

    // padding
    std::vector<bool> padded_input{padding<r>(input)};

    // absorbtion de l'entrée
    // A est initialisé à 0 par défaut
    Mat<w> A;
    for(size_t chunk_start{0}, size{padded_input.size()};
        chunk_start < size;
        chunk_start += r) {
      sponge<r, l>(A, padded_input, chunk_start);
      permutation<l>(A);
    }

    // sortie du condensat
    std::bitset<output_size> output;
    size_t inserted{0};
    while(inserted < output_size) {
      size_t x{0}, y{0}, b{0};
      for(size_t i{0}; i < r && inserted < output_size; ++i) {
        output[inserted] = A[x][y][b];
        ++inserted;

        b = (b+1)%w;
        if(b == 0) {
          x = (x+1)%5;
          if(x == 0) {
            y = (y+1)%5;
          }
        }
      }
      permutation<l>(A);
    }

    return output;
  }

  std::bitset<224> sha3_224(const std::vector<bool> &input) {
    return keccak<pow(2, 6)*25-2*224, 6, 224>(input);
  }

  std::bitset<256> sha3_256(const std::vector<bool> &input) {
    return keccak<pow(2, 6)*25-2*256, 6, 256>(input);
  }

  std::bitset<384> sha3_384(const std::vector<bool> &input) {
    return keccak<pow(2, 6)*25-2*384, 6, 384>(input);
  }

  std::bitset<512> sha3_512(const std::vector<bool> &input) {
    return keccak<pow(2, 6)*25-2*512, 6, 512>(input);
  }
}

Par contre, j'ai du rater un point important puisque les résultats que j'ai ne correspondent pas à ceux donnés à titre d'exemple. Et pire encore, je n'ai pas des fonctions de hashage intéressantes (la sortie ne varie que peu avec une modification de l'entrée et une partie de la sortie semble fixe).

Voici le code de test :

 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
#include <iostream>
#include <vector>
#include <bitset>
#include <string>

#include "Keccak.cpp"

const std::array<char, 16> hex_table{{
  '0', '1', '2', '3',
  '4', '5', '6', '7',
  '8', '9', 'a', 'b',
  'c', 'd', 'e', 'f'
}};

template<size_t size>
std::string to_hex(const std::bitset<size> &input) {
  static_assert(size%4 == 0,
      "Flemme d'implémenter la conversion sur des entrées qui sont pas multiple de 4 bits");
  std::string output;
  for(size_t i{0}; i<size; i+=4) {
    output += hex_table[input[i]*8+input[i+1]*4+input[i+2]*2+input[i+3]];
  }
  return output;
}

int main() {
  std::cout << to_hex(keccak::sha3_224(std::vector<bool>{})) << std::endl;
  std::cout << to_hex(keccak::sha3_256(std::vector<bool>{})) << std::endl;
  std::cout << to_hex(keccak::sha3_384(std::vector<bool>{})) << std::endl;
  std::cout << to_hex(keccak::sha3_512(std::vector<bool>{})) << std::endl;

  // 0110 0001 0110 0010 0110 0011 0011 0
  std::vector<bool> test_input{
    false, true, true, false,
    false, false, false, true,
    false, true, true, false,
    false, false, true, false,
    false, true, true, false,
    false, false, true, true,
    false, false, true, true,
    false
  };
  std::cout << to_hex(keccak::keccak<1152, 6, 224>(test_input)) << std::endl;
  std::cout << to_hex(keccak::keccak<1100, 6, 224>(test_input)) << std::endl;
  std::cout << to_hex(keccak::keccak<200, 3, 128>(test_input)) << std::endl;
  std::cout << to_hex(keccak::keccak<200, 3, 224>(test_input)) << std::endl;
  std::cout << to_hex(keccak::keccak<50, 2, 24>(test_input)) << std::endl;
  return 0;
}

et les résultats :

1
2
3
4
5
6
7
8
9
200af96cd9e80d4b00000082f4b6d5d50000274d0a051582300bd8a2
200af96cd9e80d4b00000082f4b6d5d50000274d0a051582300bd8a235f04768
200af96cd9e80d4b00000082f4b6d5d50000274d0a051582300bd8a235f04768000027cf3eb5cf3d1a2382545bef897c
200af96cd9e80d4b00000082f4b6d5d50000274d0a051582300bd8a235f04768000027cf3eb5cf3d1a2382545bef897c0000012897cfa3541a238378b325bbf6
200aecbd6c81939700000082f4ef77750000274d011e1866300bc8b2
200aec16054cbca600000082f4eff7150000274d000e9b13300bc892
54060354020602030501362619061e0d
54060354020602030501362619061e0d067a05720024032403560603
ab06a5

Par contre, en terme de perf, c'est juste largement plus rapide que l'implémentation de Dominus Carnufex en Haskell (encore heureux :p ) puisque clang donne un million de condensat en 13,13s et gcc met 9,77s (conversion en hexa et affichage dans /dev/null compris).

Edit : ok, j'avais confondu shift et rotate. En corrigeant ça, les résultats sont bien plus probants (mais toujours faux). Nouvelle version du code :

  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
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#include <array>
#include <bitset>
#include <vector>

namespace keccak {
  /* Définition des alias de types */
  template<size_t w>
  using Vec = std::array<std::bitset<w>, 5>;

  template<size_t w>
  using Mat = std::array<Vec<w>, 5>;


  /* Définitions des constants et constexpr */
  constexpr size_t pow(size_t x, size_t n) {
    return n>0 ? x*pow(x, n-1) : 1;
  }

  template<size_t w>
  const std::array<std::array<size_t, 5>, 5> r{{
    {{ 0%w, 36%w,  3%w, 41%w, 18%w}},
    {{ 1%w, 44%w, 10%w, 45%w,  2%w}},
    {{62%w,  6%w, 43%w, 15%w, 61%w}},
    {{28%w, 55%w, 25%w, 21%w, 56%w}},
    {{27%w, 20%w, 39%w,  8%w, 14%w}}
  }};

  template<size_t w>
  const std::array<std::bitset<w>, 24> RC{{
    0x0000000000000001ULL,
    0x0000000000008082ULL,
    0x800000000000808AULL,
    0x8000000080008000ULL,
    0x000000000000808BULL,
    0x0000000080000001ULL,
    0x8000000080008081ULL,
    0x8000000000008009ULL,
    0x000000000000008AULL,
    0x0000000000000088ULL,
    0x0000000080008009ULL,
    0x000000008000000AULL,
    0x000000008000808BULL,
    0x800000000000008BULL,
    0x8000000000008089ULL,
    0x8000000000008003ULL,
    0x8000000000008002ULL,
    0x8000000000000080ULL,
    0x000000000000800AULL,
    0x800000008000000AULL,
    0x8000000080008081ULL,
    0x8000000000008080ULL,
    0x0000000080000001ULL,
    0x8000000080008008ULL
  }};


  /* Définitions des sous-fonctions de permutation */
  template<size_t w>
  std::bitset<w> rotate(const std::bitset<w> &input, size_t step) {
    return (input << step) | (input >> (w-step));
  }

  template<size_t w>
  void theta(Mat<w> &A) {
    Vec<w> C;
    for(size_t x{0}; x<5; ++x) {
      for(size_t y{0}; y<5; ++y) {
        C[x] ^= A[x][y];
      }
    }

    Vec<w> D;
    for(size_t x{0}; x<5; ++x) {
      D[x] = C[(x-1)%5] ^ rotate(C[(x+1)%5], 1);
    }

    for(size_t x{0}; x<5; ++x) {
      for(size_t y{0}; y<5; ++y) {
        A[x][y] ^= D[x];
      }
    }
  }

  template<size_t w>
  void rhoPi(const Mat<w> &A, Mat<w> &B) {
    for(size_t x{0}; x<5; ++x) {
      for(size_t y{0}; y<5; ++y) {
        B[y][(2*x+3*y)%5] = rotate(A[x][y], r<w>[x][y]);
      }
    }
  }

  template<size_t w>
  void chi(Mat<w> &A, const Mat<w> &B) {
    for(size_t x{0}; x<5; ++x) {
      for(size_t y{0}; y<5; ++y) {
        A[x][y] = B[x][y] ^ ((~B[(x+1)%5][y]) & B[(x+2)%5][y]);
      }
    }
  }

  template<size_t w>
  void iota(Mat<w> &A, size_t num_op) {
    A[0][0] ^= RC<w>[num_op];
  }


  /* Définitions des sous-fonctions de Keccak */
  template<size_t r>
  std::vector<bool> padding(const std::vector<bool> &input) {
    std::vector<bool> padded{input};
    padded.push_back(false);
    padded.push_back(true);
    padded.push_back(true);
    size_t num_zero{r - (padded.size()+1)%r};
    padded.insert(padded.end(), num_zero, false);
    padded.push_back(true);
    return padded;
  }

  template<size_t r, size_t l>
  void sponge(Mat<pow(2, l)> &A,
      const std::vector<bool> &input,
      size_t pos) {
    std::bitset<pow(2, l)> current_word;
    size_t end_pos{pos+r};
    for(size_t y{0}; y<5; ++y) {
      for(size_t x{0}; x<5; ++x) {
        for(size_t b{0}; b<pow(2, l); ++b) {
          if(pos < end_pos) {
            current_word[b] = input[pos];
            ++pos;
          } else {
            current_word[b] = 0;
          }
        }
        A[x][y] ^= current_word;
      }
    }
  }

  template<size_t l>
  void permutation(Mat<pow(2, l)> &A) {
    Mat<pow(2, l)> B;
    for(size_t num_op{0}; num_op<12+2*l; ++num_op) {
      theta(A);
      rhoPi(A, B);
      chi(A, B);
      iota(A, num_op);
    }
  }

  template<size_t r, size_t l, size_t output_size>
  std::bitset<output_size> keccak(const std::vector<bool> &input) {
    static const size_t w{pow(2, l)};
    static const size_t internal_size{25*w};
    static_assert(l <= 6, "Valeur de 'l' invalide : les mots ne peuvent faire plus de 64 bits.");
    static_assert(r <= internal_size, "Valeur de 'r' invalide : "
        "la vitesse de production ne peut excéder la taille de l'état interne (25*2^l).");

    // padding
    std::vector<bool> padded_input{padding<r>(input)};

    // absorbtion de l'entrée
    // A est initialisé à 0 par défaut
    Mat<w> A;
    for(size_t chunk_start{0}, size{padded_input.size()};
        chunk_start < size;
        chunk_start += r) {
      sponge<r, l>(A, padded_input, chunk_start);
      permutation<l>(A);
    }

    // sortie du condensat
    std::bitset<output_size> output;
    size_t inserted{0};
    while(inserted < output_size) {
      size_t x{0}, y{0}, b{0};
      for(size_t i{0}; i < r && inserted < output_size; ++i) {
        output[inserted] = A[x][y][b];
        ++inserted;

        b = (b+1)%w;
        if(b == 0) {
          x = (x+1)%5;
          if(x == 0) {
            y = (y+1)%5;
          }
        }
      }
      permutation<l>(A);
    }

    return output;
  }

  std::bitset<224> sha3_224(const std::vector<bool> &input) {
    return keccak<pow(2, 6)*25-2*224, 6, 224>(input);
  }

  std::bitset<256> sha3_256(const std::vector<bool> &input) {
    return keccak<pow(2, 6)*25-2*256, 6, 256>(input);
  }

  std::bitset<384> sha3_384(const std::vector<bool> &input) {
    return keccak<pow(2, 6)*25-2*384, 6, 384>(input);
  }

  std::bitset<512> sha3_512(const std::vector<bool> &input) {
    return keccak<pow(2, 6)*25-2*512, 6, 512>(input);
  }
}

Edit 2 : c'est bon, mes fonction sha3 fonctionnent. L'erreur restante était l'utilisation de (x-1)%5 avec x un entier non signé. Ça donne 0 quand x=0 au lieu de 4 (je suppose à cause du fait que ça overflow). L'idée est d'écrire (x+4)%5 pour résoudre le problème. La conversion en hexadécimal ne donnait pas non plus les éléments dans l'ordre habituel. J'ai aussi augmenté (légèrement) les performances en ne recalculant les permutations dans la génération du condensat que si l'on ne sort pas de la boucle.

Au passage, pour trouver mon erreur, je me suis servi de ce document : http://csrc.nist.gov/groups/ST/toolkit/examples.html#aHashing . Il donne un certain nombre de résultats intermédiaires pour plusieurs entrées. Je laisse dans mon code la fonction qui permet d'afficher l'état interne sous la même forme que celle qui est utilisé dans le document pour ceux que ça intéresse.

Edit 3 : le dernier problème qu'il me restait avec Keccak par rapport à l'entrée de test fourni par Dominus Carnufex n'en est probablement pas un. J'ai vérifié avec les valeurs officiels (cf. Edit 2) pour des messages de différentes tailles pour sha3 et ça colle parfaitement. De même, le résultat obtenu pour Keccak et une chaîne vide correspond au résultat présenté au début du sujet. La dernière différence provient des résultats obtenus avec le message de Dominus Carnufex sur Keccak. Vu que tout le reste est valide, ça me semble difficile que j'ai un bug sur mon implémentation. C'est donc soit l'implémentation de Dominus Carnufex qui n'est pas valide, soit un problème dans l'ordre des bits/octets ou carrément une erreur dans le message.

Edit final : C'est bon, le problème venait bien de l'ordre des bits au sein des octets. Les bitsets C++ sont en big-endian (ce qui est le plus logique en terme d'utilisation), il fallait inverser l'ordre des bits dans les octets (y compris l'octet incomplet de la fin, en le traitant comme si c'était un octet de 5 bits, donc un quintet ^^ ).

Code fonctionnel

Code de Keccak :

  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
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
#ifndef KECCAK_CPP
#define KECCAK_CPP

#include <array>
#include <bitset>
#include <vector>

#include "hex_utils.cpp"

namespace keccak {
  /* Définition des alias de types */
  template<size_t w>
  using Vec = std::array<std::bitset<w>, 5>;

  template<size_t w>
  using Mat = std::array<Vec<w>, 5>;


  /* Définitions des constants et constexpr */
  constexpr size_t pow(size_t x, size_t n) {
    return n>0 ? x*pow(x, n-1) : 1;
  }

  template<size_t w>
  constexpr std::array<std::array<size_t, 5>, 5> r{{
    {{ 0%w, 36%w,  3%w, 41%w, 18%w}},
    {{ 1%w, 44%w, 10%w, 45%w,  2%w}},
    {{62%w,  6%w, 43%w, 15%w, 61%w}},
    {{28%w, 55%w, 25%w, 21%w, 56%w}},
    {{27%w, 20%w, 39%w,  8%w, 14%w}}
  }};

  template<size_t w>
  constexpr std::array<std::bitset<w>, 24> RC{{
    0x0000000000000001ULL,
    0x0000000000008082ULL,
    0x800000000000808AULL,
    0x8000000080008000ULL,
    0x000000000000808BULL,
    0x0000000080000001ULL,
    0x8000000080008081ULL,
    0x8000000000008009ULL,
    0x000000000000008AULL,
    0x0000000000000088ULL,
    0x0000000080008009ULL,
    0x000000008000000AULL,
    0x000000008000808BULL,
    0x800000000000008BULL,
    0x8000000000008089ULL,
    0x8000000000008003ULL,
    0x8000000000008002ULL,
    0x8000000000000080ULL,
    0x000000000000800AULL,
    0x800000008000000AULL,
    0x8000000080008081ULL,
    0x8000000000008080ULL,
    0x0000000080000001ULL,
    0x8000000080008008ULL
  }};


  /* Définitions des sous-fonctions de permutation */
  template<size_t w>
  std::bitset<w> rotate(const std::bitset<w> &input, size_t step) {
    return (input << step) | (input >> (w-step));
  }

  template<size_t w>
  void theta(Mat<w> &A) {
    Vec<w> C;
    for(size_t x{0}; x<5; ++x) {
      for(size_t y{0}; y<5; ++y) {
        C[x] ^= A[x][y];
      }
    }

    Vec<w> D;
    for(size_t x{0}; x<5; ++x) {
      D[x] = C[(x+4)%5] ^ rotate(C[(x+1)%5], 1);
    }

    for(size_t x{0}; x<5; ++x) {
      for(size_t y{0}; y<5; ++y) {
        A[x][y] ^= D[x];
      }
    }
  }

  template<size_t w>
  void rhoPi(const Mat<w> &A, Mat<w> &B) {
    for(size_t x{0}; x<5; ++x) {
      for(size_t y{0}; y<5; ++y) {
        B[y][(2*x+3*y)%5] = rotate(A[x][y], r<w>[x][y]);
      }
    }
  }

  template<size_t w>
  void chi(Mat<w> &A, const Mat<w> &B) {
    for(size_t x{0}; x<5; ++x) {
      for(size_t y{0}; y<5; ++y) {
        A[x][y] = B[x][y] ^ ((~B[(x+1)%5][y]) & B[(x+2)%5][y]);
      }
    }
  }

  template<size_t w>
  void iota(Mat<w> &A, size_t num_op) {
    A[0][0] ^= RC<w>[num_op];
  }


  /* Définitions des sous-fonctions de Keccak */
  template<size_t r, bool sha3_padding>
  std::vector<bool> padding(const std::vector<bool> &input) {
    std::vector<bool> padded{input};
    if(sha3_padding) {
      padded.push_back(false);
      padded.push_back(true);
    }
    padded.push_back(true);
    size_t num_zero{r - (padded.size()+1)%r};
    padded.insert(padded.end(), num_zero, false);
    padded.push_back(true);
    return padded;
  }

  template<size_t r, size_t l>
  void sponge(Mat<pow(2, l)> &A,
      const std::vector<bool> &input,
      size_t pos) {
    std::bitset<pow(2, l)> current_word;
    size_t end_pos{pos+r};
    for(size_t y{0}; y<5; ++y) {
      for(size_t x{0}; x<5; ++x) {
        for(size_t b{0}; b<pow(2, l); ++b) {
          if(pos < end_pos) {
            current_word[b] = input[pos];
            ++pos;
          } else {
            current_word[b] = 0;
          }
        }
        A[x][y] ^= current_word;
      }
    }
  }

  template<size_t l>
  void permutation(Mat<pow(2, l)> &A) {
    Mat<pow(2, l)> B;
    for(size_t num_op{0}; num_op<12+2*l; ++num_op) {
      theta(A);
      rhoPi(A, B);
      chi(A, B);
      iota(A, num_op);
    }
  }

  template<size_t r, size_t l, size_t output_size, bool sha3_padding = true>
  std::bitset<output_size> keccak(const std::vector<bool> &input) {
    static const size_t w{pow(2, l)};
    static const size_t internal_size{25*w};
    static_assert(l <= 6, "Valeur de 'l' invalide : les mots ne peuvent faire plus de 64 bits.");
    static_assert(r <= internal_size, "Valeur de 'r' invalide : "
        "la vitesse de production ne peut excéder la taille de l'état interne (25*2^l).");

    // padding
    std::vector<bool> padded_input{padding<r, sha3_padding>(input)};

    // absorbtion de l'entrée
    // A est initialisé à 0 par défaut
    Mat<w> A;
    for(size_t chunk_start{0}, size{padded_input.size()};
        chunk_start < size;
        chunk_start += r) {
      sponge<r, l>(A, padded_input, chunk_start);
      permutation<l>(A);
    }

    // sortie du condensat
    std::bitset<output_size> output;
    size_t inserted{0};
    while(inserted < output_size) {
      size_t x{0}, y{0}, b{0};
      for(size_t i{0}; i < r && inserted < output_size; ++i) {
        output[inserted] = A[x][y][b];
        ++inserted;

        b = (b+1)%w;
        if(b == 0) {
          x = (x+1)%5;
          if(x == 0) {
            y = (y+1)%5;
          }
        }
      }
      if(inserted < output_size) {
        permutation<l>(A);
      }
    }

    return output;
  }

  std::bitset<224> sha3_224(const std::vector<bool> &input) {
    return keccak<pow(2, 6)*25-2*224, 6, 224>(input);
  }

  std::bitset<256> sha3_256(const std::vector<bool> &input) {
    return keccak<pow(2, 6)*25-2*256, 6, 256>(input);
  }

  std::bitset<384> sha3_384(const std::vector<bool> &input) {
    return keccak<pow(2, 6)*25-2*384, 6, 384>(input);
  }

  std::bitset<512> sha3_512(const std::vector<bool> &input) {
    return keccak<pow(2, 6)*25-2*512, 6, 512>(input);
  }
}

#endif

Utilitaires hexadécimal :

 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
#ifndef HEX_UTILS_CPP
#define HEX_UTILS_CPP

#include <iostream>
#include <array>
#include <bitset>
#include <string>

const std::array<char, 16> hex_table{{
  '0', '1', '2', '3',
  '4', '5', '6', '7',
  '8', '9', 'a', 'b',
  'c', 'd', 'e', 'f'
}};

template<size_t size>
std::string to_hex(const std::bitset<size> &input) {
  static_assert(size%8 == 0,
      "Flemme d'implémenter la conversion sur des entrées qui sont pas multiple de 8 bits");
  std::string output;
  for(size_t i{0}; i<size; i+=8) {
    output.push_back(hex_table[input[i+4]+input[i+5]*2+input[i+6]*4+input[i+7]*8]);
    output.push_back(hex_table[input[i]+input[i+1]*2+input[i+2]*4+input[i+3]*8]);
  }
  return output;
}

template<size_t w>
void debug(const std::array<std::array<std::bitset<w>, 5>, 5> &A) {
  size_t n{0};
  for(size_t y{0}; y<5; ++y) {
    for(size_t x{0}; x<5; ++x) {
      for(size_t i{0}; i<w; i+=8) {
        std::cout << hex_table[A[x][y][i+4]+A[x][y][i+5]*2+A[x][y][i+6]*4+A[x][y][i+7]*8]
                  << hex_table[A[x][y][i]+A[x][y][i+1]*2+A[x][y][i+2]*4+A[x][y][i+3]*8];
        ++n;
        if(n%16 == 0) {
          std::cout << std::endl;
        } else {
          std::cout << ' ';
        }
      }
    }
  }
  std::cout << std::endl;
}

#endif

Programme de test (certaines entrées n'y sont pas parce que je n'ai pas géré l'affichage en hexa sur des bouts d'octets) :

  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
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
#include <algorithm>
#include <iostream>
#include <vector>
#include <bitset>
#include <string>

#include "Keccak.cpp"
#include "hex_utils.cpp"

int main() {
  /*
  // pour les tests de performance
  for(auto i=0ULL; i<1000000; ++i) {
    std::bitset<20> input{i};
    std::vector<bool> v_input{};
    for(size_t a=0; a<10; ++a) {
      v_input.emplace_back(input[a]);
    }
    std::cout << to_hex(keccak::sha3_224(v_input)) << std::endl;
  }
  */
  const size_t is = keccak::pow(2, 6)*25;
  std::cout << to_hex(keccak::keccak<is-2*224, 6, 224, false>(std::vector<bool>{})) << std::endl;
  std::cout << to_hex(keccak::keccak<is-2*256, 6, 256, false>(std::vector<bool>{})) << std::endl;
  std::cout << to_hex(keccak::keccak<is-2*384, 6, 384, false>(std::vector<bool>{})) << std::endl;
  std::cout << to_hex(keccak::keccak<is-2*512, 6, 512, false>(std::vector<bool>{})) << std::endl;
  std::cout << std::endl;

  std::cout << to_hex(keccak::sha3_224(std::vector<bool>{})) << std::endl;
  std::cout << to_hex(keccak::sha3_256(std::vector<bool>{})) << std::endl;
  std::cout << to_hex(keccak::sha3_384(std::vector<bool>{})) << std::endl;
  std::cout << to_hex(keccak::sha3_512(std::vector<bool>{})) << std::endl;
  std::cout << std::endl;

  // 0110 0001 0110 0010 0110 0011 0011 0 en changeant l'ordre des bits
  std::vector<bool> test_input{
    true, false, false, false, false, true, true, false,
    false, true, false, false, false, true, true, false,
    true, true, false, false, false, true, true, false,
    false, true, true, false, false
  };
  std::cout << to_hex(keccak::keccak<1152, 6, 224, false>(test_input)) << std::endl;
  std::cout << to_hex(keccak::keccak<1100, 6, 224, false>(test_input)) << std::endl;
  std::cout << to_hex(keccak::keccak<200, 3, 128, false>(test_input)) << std::endl;
  std::cout << to_hex(keccak::keccak<200, 3, 224, false>(test_input)) << std::endl;
  std::cout << to_hex(keccak::keccak<50, 2, 24, false>(test_input)) << std::endl;
  std::cout << std::endl;

  // résultats disponibles sur : http://csrc.nist.gov/groups/ST/toolkit/examples.html#aHashing
  std::cout << to_hex(keccak::sha3_224(std::vector<bool>{})) << std::endl;
  std::cout << to_hex(keccak::sha3_224(std::vector<bool>{true, true, false, false, true})) << std::endl;
  std::cout << to_hex(keccak::sha3_224(std::vector<bool>{
      true, true, false, false, true, false, true, false,
      false, false, false, true, true, false, true, false,
      true, true, false, true, true, true, true, false,
      true, false, false, true, true, false})) << std::endl;
  std::cout << to_hex(keccak::sha3_224(std::vector<bool>{
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true,
      true, true, false, false, false, true, false, true})) << std::endl;
  return 0;
}

Autrement, ça m'intéresserait d'avoir des retours sur mon code C++. Je ne l'utilise pas très souvent et ça doit être le code le plus compliqué que j'ai fait jusqu'à présent dans ce langage. Au passage, j'ai quand même trouvé un bug dans clang (confirmé par plusieurs personnes bien plus compétentes que moi). D'ailleurs, pour ceux qui veulent compiler avec clang, il faut remplacer le constexpr de la déclaration de keccak::r par const.

+7 -0

Le sujet semble très rigolo ! :)

Pour ce qui est de la présentation, je propose de convertir quasiment tout le sujet en tutoriel. Le post proposera alors un découpage en fonction du niveau souhaité. De plus, le dur labeur de Dominus Carnufex sera beaucoup plus pérenne dans le temps.

+5 -0

Pour ce qui est de la présentation, je propose de convertir quasiment tout le sujet en tutoriel. […] De plus, le dur labeur de Dominus Carnufex sera beaucoup plus pérenne dans le temps.

abrl

J'aime bien l'idée. Je pense aussi que transformer ce sujet de défi en tuto + exercices/TPs aux différentes étapes le rendrait plus abordable. En plus ça pourrait permettre de profiter du découpage en parties/sous-parties du module de tutoriels et ça débarrasserait de l'effet "pavé".

+3 -0

J'ai pris le temps de lire le sujet en entier, et il y a 2-3 trucs qui me coincent.

Le premier problème se fait avec ce r. Peut-il être plus grand que 25w, et quel intérêt y a-t-il a en prendre un petit. En somme, à quoi sert-il ?

Ensuite (~ la moitié du paragraphe sur l'éponge), on va découper notre machin en truc de longueur w, et utiliser des bouts de A pour faire ce qu'on veut. Deuxième problème : avec quel données a-t-on créé A ? À priori, on a découpé en bouts de taille w, mais on n'a rien qui fasse 5x5 à ce niveau là.

Puis ensuite, je sais que je n'ai pas compris, mais je n'ai plus de questions formulable correctement.

Personnellement, mes connaissances en bas-niveau (j'ai lu "bit", donc c'est du bas niveau pour moi ^^ ) est au ras des pâquerettes. Je n'ai pas de problème pour le lire (je sais lire, y'a qu'à prendre le temps), mais pour comprendre.

Mais ça à l'air super intéressant.

+0 -0

Le premier problème se fait avec ce r. Peut-il être plus grand que 25w, et quel intérêt y a-t-il a en prendre un petit. En somme, à quoi sert-il ?

Gabbro

r correspond à la quantité d'entrée que tu vas intégrer à A à chaque itération. r ne peut dépasses 25w puisque c'est la taille de A. Par exemple, si tu as une entrée de 5r (après padding), à la première itération, tu intègres le premier cinquième de l'entrée dans A, à la deuxième itération, tu intègres le deuxième cinquième de l'entrée, etc. Le fait qu'il puisse être plus petit permet d'augmenter le temps de calcul et donc les possibilités d'attaques en brute-force (même si je ne sais pas si c'est utile dans ce contexte). Après, ça a peut-être aussi un intérêt en terme de qualité de hash produit.

Ensuite (~ la moitié du paragraphe sur l'éponge), on va découper notre machin en truc de longueur w, et utiliser des bouts de A pour faire ce qu'on veut. Deuxième problème : avec quel données a-t-on créé A ? À priori, on a découpé en bouts de taille w, mais on n'a rien qui fasse 5x5 à ce niveau là.

Gabbro

A est initialement une matrice 5x5 vide (qui contient uniquement des 0), à chaque itération, tu intègres un bout de l'entrée (de taille r) avec un xor (dans l'ordre expliqué dans le sujet). Chaque élément de A étant de taille w, il peut être utile de découper le bout d'entrée en éléments de taille w. Si r est inférieur à 25w, il faudra compléter le bout d'entrée avec des 0 pour qu'il atteigne cette taille.

Personnellement, mes connaissances en bas-niveau (j'ai lu "bit", donc c'est du bas niveau pour moi ^^ ) est au ras des pâquerettes. Je n'ai pas de problème pour le lire (je sais lire, y'a qu'à prendre le temps), mais pour comprendre.

Gabbro

Ce qui risque le plus de poser problème dans la partie "bas-niveau", c'est l'endianness (l'ordre des bits et des octets). Pour le reste, entre manipuler des bits ou des octets ou des entiers, ça ne change pas grand chose au final.

+1 -0

Merci pour le sujet. Mais j'ai quand même un gros souci pour lire le contenu. Tous les deux mots apparaît un nouveau concept avec une nouvelle définition et je ne parle même pas du pseudo code - des raccourcis par-ci par-là. La boucle comment est-ce qu'on la définit ?

J'avoue que par rapport à ce qu'on trouve sur internet, c'est plus complet. Pour autant, un néophyte des méthodes de hashage ne comprend rien du tout. A quoi ressemble notre objet A ? Sur d'autre source, on ne voit plus le A comme un simple tableau de 5x5 mais un objet en 3 dimensions.

En faite dès le début je suis largué. D'accord, j'ai une variable l qui vaut 6 (c'est par défaut - why ?), puis w qui vaut 2l = 26 = 64, puis un b qui vaut 25*w = 25*64 = 1600. A partir de là, on introduit un tableau de 5x5 - on ne sait pas d'où il apparaît dans le comportement du programme.

Tu dis qu'il faut tout ça :

  • bourrage
  • permutation
  • fonction éponge
  • condensat

Mais dans quel ordre ? Est-ce qu'il y a une boucle qui englobe l'ensemble ?

+2 -2
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte