Mouaif, chez moi ça fait surtout "illegal hardware instruction". Et si je lui dis "n'essaye pas de trop finasser avec ton compilateur JIT" (flag -Xem:jet), j'ai une segfault. C'est le build 5.0M1 pour x86 32-bits. M'est avis qu'ils ont compilé et testé sur des processeurs plus récents que mon Athlon XP, qui n'est tout de même pas un vieux clou innommable.
Ce projet avance ; c'est bien. Ils entrent dans la phase où les fonctionnalités sont là et où il faut faire que l'assurance-qualité : ils vont morfler, parce qu'une JVM, c'est pas ce qu'il y a de plus simple à débugguer. À vue de nez, Harmony sera exploitable en production d'ici environ deux ans.
- "fil d'exécution" : c'est la suite d'instructions que le processeur parcourt et exécute en séquence.
- "espace d'adressage" : c'est la vision de la mémoire d'un processus.
Les espaces d'adressage des processus sont distincts, et chaque processus ne peut taper que dans le sien (sinon c'est segfault). On appelle "MMU" le morceau du processeur qui gère l'espace d'adressage (localisation en mémoire -- ou pas, en cas de swap ; droits d'accès ; etc). Il peut y avoir des morceaux de RAM communs entre plusieurs espaces d'adressage (mémoire partagée, comme on dit) mais la règle commune reste la séparation des espaces.
Un processus, c'est un espace d'adressage, et un certain nombre de fils d'exécution qui travaillent dans cet espace. Ces fils d'exécution, quand ils sont au moins deux, on les appelle des threads.
Dans un processeur multi-coeurs, chaque coeur peut gérer un espace d'adressage à la fois. Donc deux processus distincts peuvent tourner en parallèle, un sur chaque coeur. Chaque coeur peut en outre gérer plusieurs fils d'exécution plus ou moins en même temps (ce qu'Intel appelle "hyper-threading"), mais là c'est forcément dans le même espace d'adressage (la MMU de chaque coeur ne peut prendre en compte qu'un seul espace d'adressage à la fois), donc ces fils d'exécution ne peuvent être que des threads du même processus.
En bref, le multi-coeurs, on peut en profiter pour des processus distincts, mais pour l'hyper-threading, il faut des threads au sein d'un même processus. Les deux mécanismes sont proposés par les processeurs récents. Pour profiter à fond de ces processeurs, il faut avoir plusieurs threads, mais le multi-coeur aide déjà quand on a plusieurs processus indépendants.
Les instructions SSE* peuvent aider pour certains algorithmes de crypto ; surtout ceux qui manipulent des mots de 64 bits et font des opérations arithmétiques et logiques avec ces mots. L'effet est surtout sensible en mode 32 bits.
L'exemple typique est SHA-512. L'implémentation de SHA-512 dans OpenSSL est en C, mais, quand elle tourne sur un processeur disposant du jeu d'instruction SSE2, alors elle commute automatiquement vers une implémentation en assembleur utilisant à fond le SSE2. SHA-512 fait des additions, des rotations, et des opérations booléennes bit à bit sur des mots de 64 bits, ce qui est pile-poil dans ce que SSE2 permet de faire. Le gain est impressionnant : ça fait passer SHA-512 de 20 à plus de 80 Mo/s sur la même machine. On ne retrouve pas ce gain en AMD64, car alors les registres "standard" sont en 64 bits et sont en nombre suffisant pour faire le boulot.
Pour Whirlpool, c'est moins clair. Une phase de Whirlpool est exprimée, mathématiquement, comme un ensemble de transformations (dont certaines linéaires) dans un espace vectoriel de dimension 8 sur un corps GF(256). C'est très en dehors de ce que les processeurs savent faire "nativement". Ça s'implémente efficacement en faisant des accès à des tables précalculées : grosso-modo, il faut, pour chaque mot de 64 bits, le découper en huit octets, faire un accès indexé par chacun de ces octets dans huit tables, et faire un XOR des résultats (chaque table -- il y en a 8 -- contient 256 entrées de 64 bits). Il y a 16 mots d'état de 64 bits dans un Whirlpool, et il faut faire ça 10 fois, donc 1280 accès à une table pour un bloc de données (un bloc = 64 octets). À peu près tout le coût d'un Whirlpool est concentré dans ces accès, soit 20 accès par octet en entrée.
Tout ça pour dire que les capacités de calcul de SSE ne seront pas exploitées par Whirlpool ; et il n'y a pas, à ma connaissance, d'opcode SSE (même dans SSE4) pour accéder à une table en mémoire selon un index stocké dans un registre SSE. Il faudra faire une partie du traitement dans les registres entiers usuels. On peut imaginer que les registres SSE serviraient pour le XOR des sorties des tables ; il faudrait que je me penche sur la question sérieusement. À froid, je peux imaginer un gain, mais relativement faible, pour l'usage de SSE2 par rapport à une implémentation 32 bits "simple". Mais SSE4 n'apportera rien en lui-même (par rapport à SSE2), et tous ces gains disparaissent si on passe en mode AMD64 (et les processeurs sachant faire du SSE4 sauront probablement faire aussi de l'AMD64, donc on aurait tort de se priver).
Je ne sais pas si l'usage du SSE est posible dans le noyau Linux. Dans le temps, on ne pouvait pas utiliser la FPU dans le noyau. Ça pourrait simplifier la question.
Usuellement, les cryptographes travaillent dans l'autre sens : ils observent l'existence de nouveaux opcodes, et ils se demandent comment s'en servir pour inventer de nouvelles fonctions qui en profiteront.
Pour les performances, j'ai fait quelques essais sur un Athlon Sempron 3000+, en mode AMD64, sous Linux (Ubuntu 3.10). Le compilateur C est annoncé comme :
gcc version 4.1.2 20060928 (prerelease) (Ubuntu 4.1.1-13ubuntu5)
Ça donne ça :
- En mode AMD64, ça tourne à 61 cycles par octet traité.
- En mode i386, sur la même machine, ça fait du 116 cycles par octet.
Donc oui, c'est optimisé 64 bits : le passage de 32 à 64 bits double quasiment les performances. Par comparaison, pour MD4, le passage de 32 à 64 bits ne gagne même pas 1% en vitesse, parce que le 32 bits lui suffit, et il n'a que faire de registres plus grands ou plus nombreux. Mais Whirlpool reste lent : mon Sempron utilisé à plein régime fait du 26 Mo/s, ce qui n'est même pas suffisant pour suivre le disque dur (et c'est en supposant que 100% du cpu est dédié à la tâche). MD4 tape au-delà des 450 Mo/s, ce qui est tout de même mieux. Il y a probablement un "juste milieu" entre un MD4 hyper-rapide et cassé, et un Whirlpool pas cassé mais lent.
Ces mesures marchent aussi bien avec mon code à moi qu'avec le code de référence de Whirlpool, code de référence qui est celui repris tel quel dans le noyau Linux. Il n'y a pas 36 manières d'optimiser un Whirlpool sur PC... Et vues les primitives utilisées, il n'y a pas de raison particulière pour qu'un passage en assembleur optimisé à la main permette de gagner plus que les 5 à 30% qu'on constate usuellement.
Pour ce qui est des implémentations matérielles de Whirlpool, je suis un peu sceptique. L'AES lui-même a été publié en 2001 et il n'y a pas beaucoup de plateformes qui offrent une implémentation matérielle de l'AES. Il y a visiblement des délais assez longs dans l'industrie des microprocesseurs.
Quant à l'aspect dérivé de l'AES, disons qu'il fait débat. Whirlpool est fondé sur un algorithme de chiffrement par blocs, nommé "W" (rien à voir avec un président américain), dont la structure est une version étendue de Rijndael, c'est-à-dire l'AES. Mais W est utilisé dans le mode usuel pour faire une fonction de hachage, c'est-à-dire en faisant rentrer le message en tant que clé. L'AES n'a pas été évalué pour ce mode d'utilisation ; dans le jargon des cryptographes, une collision sur Whirlpool serait une paire de "clés liées" pour W, et on ne sait pas grand chose sur les clés liées de l'AES. Ce n'est pas une propriété intéressante à étudier pour un algorithme de chiffrement utilisé simplement en mode chiffrement.
En bref, Whirlpool est un concept intéressant, et une fonction à surveiller, mais ce n'est pas la panacée et il y a encore beaucoup à inventer dans le domaine des fonctions de hachage.
Notons quand même que Whirlpool est sortie "gagnante" du processus NESSIE essentiellement parce que c'était la seule fonction de hachage soumise. À vaincre sans péril, on triomphe sans gloire...
Il y a beaucoup d'effervescence sur les fonctions de hachage actuellement, et pas mal de chercheurs qui bossent sur le sujet. On ne sait pas actuellement caractériser une fonction de hachage "solide" autrement que comme "on a tapé dessus mais on n'a pas réussi à la casser". Outre Whirlpool, il reste des choses comme SHA-256 et SHA-512 (aucune attaque, même théorique et embryonnaire), Tiger ou Panama. Whirlpool a l'insigne désavantage d'être plutôt lente, de l'ordre de la centaine de cycles d'horloge par octet traité, alors qu'un banal MD5 peut tourner à moins de 10 cycles par octet (et MD4 descend en dessous de 4, ce qui est outrageusement rapide).
# C'est bien sauf quand ça plante
Posté par Thomas Pornin . En réponse au journal Harmony est enfin out. Évalué à 2.
Ce projet avance ; c'est bien. Ils entrent dans la phase où les fonctionnalités sont là et où il faut faire que l'assurance-qualité : ils vont morfler, parce qu'une JVM, c'est pas ce qu'il y a de plus simple à débugguer. À vue de nez, Harmony sera exploitable en production d'ici environ deux ans.
[^] # Re: Merci pour l'article et petite question ...
Posté par Thomas Pornin . En réponse à la dépêche Les nouveaux processeurs arrivent. Évalué à 4.
- "fil d'exécution" : c'est la suite d'instructions que le processeur parcourt et exécute en séquence.
- "espace d'adressage" : c'est la vision de la mémoire d'un processus.
Les espaces d'adressage des processus sont distincts, et chaque processus ne peut taper que dans le sien (sinon c'est segfault). On appelle "MMU" le morceau du processeur qui gère l'espace d'adressage (localisation en mémoire -- ou pas, en cas de swap ; droits d'accès ; etc). Il peut y avoir des morceaux de RAM communs entre plusieurs espaces d'adressage (mémoire partagée, comme on dit) mais la règle commune reste la séparation des espaces.
Un processus, c'est un espace d'adressage, et un certain nombre de fils d'exécution qui travaillent dans cet espace. Ces fils d'exécution, quand ils sont au moins deux, on les appelle des threads.
Dans un processeur multi-coeurs, chaque coeur peut gérer un espace d'adressage à la fois. Donc deux processus distincts peuvent tourner en parallèle, un sur chaque coeur. Chaque coeur peut en outre gérer plusieurs fils d'exécution plus ou moins en même temps (ce qu'Intel appelle "hyper-threading"), mais là c'est forcément dans le même espace d'adressage (la MMU de chaque coeur ne peut prendre en compte qu'un seul espace d'adressage à la fois), donc ces fils d'exécution ne peuvent être que des threads du même processus.
En bref, le multi-coeurs, on peut en profiter pour des processus distincts, mais pour l'hyper-threading, il faut des threads au sein d'un même processus. Les deux mécanismes sont proposés par les processeurs récents. Pour profiter à fond de ces processeurs, il faut avoir plusieurs threads, mais le multi-coeur aide déjà quand on a plusieurs processus indépendants.
[^] # Re: NESSIE
Posté par Thomas Pornin . En réponse à la dépêche Nouvelles fonctions de hachage. Évalué à 3.
L'exemple typique est SHA-512. L'implémentation de SHA-512 dans OpenSSL est en C, mais, quand elle tourne sur un processeur disposant du jeu d'instruction SSE2, alors elle commute automatiquement vers une implémentation en assembleur utilisant à fond le SSE2. SHA-512 fait des additions, des rotations, et des opérations booléennes bit à bit sur des mots de 64 bits, ce qui est pile-poil dans ce que SSE2 permet de faire. Le gain est impressionnant : ça fait passer SHA-512 de 20 à plus de 80 Mo/s sur la même machine. On ne retrouve pas ce gain en AMD64, car alors les registres "standard" sont en 64 bits et sont en nombre suffisant pour faire le boulot.
Pour Whirlpool, c'est moins clair. Une phase de Whirlpool est exprimée, mathématiquement, comme un ensemble de transformations (dont certaines linéaires) dans un espace vectoriel de dimension 8 sur un corps GF(256). C'est très en dehors de ce que les processeurs savent faire "nativement". Ça s'implémente efficacement en faisant des accès à des tables précalculées : grosso-modo, il faut, pour chaque mot de 64 bits, le découper en huit octets, faire un accès indexé par chacun de ces octets dans huit tables, et faire un XOR des résultats (chaque table -- il y en a 8 -- contient 256 entrées de 64 bits). Il y a 16 mots d'état de 64 bits dans un Whirlpool, et il faut faire ça 10 fois, donc 1280 accès à une table pour un bloc de données (un bloc = 64 octets). À peu près tout le coût d'un Whirlpool est concentré dans ces accès, soit 20 accès par octet en entrée.
Tout ça pour dire que les capacités de calcul de SSE ne seront pas exploitées par Whirlpool ; et il n'y a pas, à ma connaissance, d'opcode SSE (même dans SSE4) pour accéder à une table en mémoire selon un index stocké dans un registre SSE. Il faudra faire une partie du traitement dans les registres entiers usuels. On peut imaginer que les registres SSE serviraient pour le XOR des sorties des tables ; il faudrait que je me penche sur la question sérieusement. À froid, je peux imaginer un gain, mais relativement faible, pour l'usage de SSE2 par rapport à une implémentation 32 bits "simple". Mais SSE4 n'apportera rien en lui-même (par rapport à SSE2), et tous ces gains disparaissent si on passe en mode AMD64 (et les processeurs sachant faire du SSE4 sauront probablement faire aussi de l'AMD64, donc on aurait tort de se priver).
Je ne sais pas si l'usage du SSE est posible dans le noyau Linux. Dans le temps, on ne pouvait pas utiliser la FPU dans le noyau. Ça pourrait simplifier la question.
Usuellement, les cryptographes travaillent dans l'autre sens : ils observent l'existence de nouveaux opcodes, et ils se demandent comment s'en servir pour inventer de nouvelles fonctions qui en profiteront.
[^] # Re: NESSIE
Posté par Thomas Pornin . En réponse à la dépêche Nouvelles fonctions de hachage. Évalué à 10.
gcc version 4.1.2 20060928 (prerelease) (Ubuntu 4.1.1-13ubuntu5)
Ça donne ça :
- En mode AMD64, ça tourne à 61 cycles par octet traité.
- En mode i386, sur la même machine, ça fait du 116 cycles par octet.
Donc oui, c'est optimisé 64 bits : le passage de 32 à 64 bits double quasiment les performances. Par comparaison, pour MD4, le passage de 32 à 64 bits ne gagne même pas 1% en vitesse, parce que le 32 bits lui suffit, et il n'a que faire de registres plus grands ou plus nombreux. Mais Whirlpool reste lent : mon Sempron utilisé à plein régime fait du 26 Mo/s, ce qui n'est même pas suffisant pour suivre le disque dur (et c'est en supposant que 100% du cpu est dédié à la tâche). MD4 tape au-delà des 450 Mo/s, ce qui est tout de même mieux. Il y a probablement un "juste milieu" entre un MD4 hyper-rapide et cassé, et un Whirlpool pas cassé mais lent.
Ces mesures marchent aussi bien avec mon code à moi qu'avec le code de référence de Whirlpool, code de référence qui est celui repris tel quel dans le noyau Linux. Il n'y a pas 36 manières d'optimiser un Whirlpool sur PC... Et vues les primitives utilisées, il n'y a pas de raison particulière pour qu'un passage en assembleur optimisé à la main permette de gagner plus que les 5 à 30% qu'on constate usuellement.
Pour ce qui est des implémentations matérielles de Whirlpool, je suis un peu sceptique. L'AES lui-même a été publié en 2001 et il n'y a pas beaucoup de plateformes qui offrent une implémentation matérielle de l'AES. Il y a visiblement des délais assez longs dans l'industrie des microprocesseurs.
Quant à l'aspect dérivé de l'AES, disons qu'il fait débat. Whirlpool est fondé sur un algorithme de chiffrement par blocs, nommé "W" (rien à voir avec un président américain), dont la structure est une version étendue de Rijndael, c'est-à-dire l'AES. Mais W est utilisé dans le mode usuel pour faire une fonction de hachage, c'est-à-dire en faisant rentrer le message en tant que clé. L'AES n'a pas été évalué pour ce mode d'utilisation ; dans le jargon des cryptographes, une collision sur Whirlpool serait une paire de "clés liées" pour W, et on ne sait pas grand chose sur les clés liées de l'AES. Ce n'est pas une propriété intéressante à étudier pour un algorithme de chiffrement utilisé simplement en mode chiffrement.
En bref, Whirlpool est un concept intéressant, et une fonction à surveiller, mais ce n'est pas la panacée et il y a encore beaucoup à inventer dans le domaine des fonctions de hachage.
# NESSIE
Posté par Thomas Pornin . En réponse à la dépêche Nouvelles fonctions de hachage. Évalué à 9.
Il y a beaucoup d'effervescence sur les fonctions de hachage actuellement, et pas mal de chercheurs qui bossent sur le sujet. On ne sait pas actuellement caractériser une fonction de hachage "solide" autrement que comme "on a tapé dessus mais on n'a pas réussi à la casser". Outre Whirlpool, il reste des choses comme SHA-256 et SHA-512 (aucune attaque, même théorique et embryonnaire), Tiger ou Panama. Whirlpool a l'insigne désavantage d'être plutôt lente, de l'ordre de la centaine de cycles d'horloge par octet traité, alors qu'un banal MD5 peut tourner à moins de 10 cycles par octet (et MD4 descend en dessous de 4, ce qui est outrageusement rapide).