Blowfish

Blowfish utilise une taille de bloc de 64 bits et la clé, de longueur variable, peut aller de 32 à 448 bits. Blowfish est basé sur un schéma de Feistel avec 16 tours et utilise des S-Boxes de grande taille qui dépendent de la clé. Il ressemble à CAST-128 qui a adopté, quant à lui, des S-Boxes au contenu fixé d'avance.

Schéma de Feistel dans Blowfish

F-fonction de Blowfish.

Le schéma à gauche montre la structure principale de Blowfish. Chaque ligne représente 32 bits. L'algorithme gère deux ensembles de clés : les 18 entrées du tableau P et les quatre S-Boxes de 256 éléments chacune. Les S-Boxes acceptent un mot de 8 bits en entrée et produisent une sortie de 32 bits. Une entrée du tableau P est utilisée à chaque tour. Arrivé au tour final, la moitié du bloc de donnée subit un XOR avec un des deux éléments restants dans le tableau P.

Le deuxième schéma montre la F-fonction de Blowfish. Elle sépare une entrée de 32 bits en quatre morceaux de 8 bits et les utilise comme entrées pour accéder aux S-Boxes. Les sorties sont additionnées avec une somme modulo 2³² et l'algorithme effectue un XOR entre les deux sous-totaux pour produire la sortie finale de 32 bits. En tant que schéma de Feistel, Blowfish peut être inversé simplement en appliquant un XOR des éléments 17 et 18 du tableau P sur le bloc chiffré. Il faut ensuite utiliser les entrées du tableau P dans l'ordre inverse.

La préparation de la structure à partir de la clé commence avec l'initialisation du tableau P et des S-Boxes avec des valeurs qui sont tirées du nombre Pi exprimé en hexadécimal. On opère ensuite un XOR entre la clé secrète et les entrées du tableau P pour obtenir les nouvelles entrées du tableau P (avec une extension cyclique de la clé si nécessaire). Un bloc de 64 bits, tous à zéro, est ensuite chiffré avec cette version temporaire de Blowfish. Le résultat chiffré remplace ensuite le premier et le deuxième élément du tableau P. On réitère l'opération de chiffrement avec cette nouvelle version et ceci sur le résultat précédent. On obtient alors le troisième et quatrième élément de P. L'algorithme continue ainsi en remplaçant tout le tableau P et les éléments des S-Boxes. Finalement, ce sont 72 octets de données qui doivent être générés pour le tableau P, et 1 024 octets de données par S-Box, soit un total de 4 168 octets, et Blowfish effectue 521 itérations pour y parvenir.

De par ces contraintes, Blowfish est lent quand il faut changer de clé mais très rapide pour le chiffrement pris séparément.

Le principe d'initialisation consistant à effectuer un XOR entre le tableau P long de 576 bits et les bits de la clé étendus de façon cyclique sur 576 bits, de nombreuses implémentations permettent d'utiliser des clés d'une taille atteignant 576 bits pour augmenter la sécurité. Bien que ce soit tout à fait possible, la limite de 448 bits a été fixée de façon que chaque bit de chaque valeur du tableau P et des S-Boxes dépende de tous les bits de la clé[1], les quatre dernières valeurs du tableau P n'affectant pas tous les bits du bloc chiffré.

Ce point doit être pris en considération pour déterminer la longueur de clé maximale d'une implémentation de l'algorithme d'un nombre différent de tours, car même si l'extension de la taille de la clé (indépendamment d'une extension du nombre de tours) fournit une meilleure sécurité face à une recherche exhaustive, elle affecte la sécurité garantie par l'algorithme. Car hormis les évidents bénéfices qu'offrent une clé de taille accrue, aucune étude à ce jour n'a étudié l'impact sur la sécurité qu'a le non-respect de cette règle, ce qui mène de nombreux éditeurs de logiciels à la respecter. En effet, étant donné la longue et complexe initialisation de Blowfish à chaque changement de clé, il est doté d'une protection naturelle contre les recherches exhaustives car le temps de calcul s'en trouve grandement accru. Ainsi à l'heure actuelle, le gain obtenu ne justifie pas vraiment l'utilisation d'une clé de taille supérieure à 448 bits, ce qui est déjà bien au-delà des capacités de calcul par recherche exhaustive, ainsi que de nombreux algorithmes considérés comme sécurisés.

En 1996, Serge Vaudenay a montré que les permutations dans Blowfish s'écartaient sensiblement des permutations complètement aléatoires sur 14 tours[2]. L'attaque qu'il a forgée nécessite 2^{8r + 1} textes clairs connus, avec r le nombre de tours. Il a de plus mis en évidence des clés dites faibles, qui génèrent des S-Boxes comportant des collisions. Ces clés sont détectables et cassables avec la même attaque en seulement 2^{4r + 1} textes clairs connus. L'attaque ne peut être étendue au Blowfish complet avec ses 16 tours. Vincent Rijmen a publié une attaque sur quatre tours en 1997, elle est basée sur une cryptanalyse différentielle de second degré. La recherche exhaustive reste la seule solution pour vaincre un Blowfish complet à ce jour.

Dans GNU Privacy Guard, Blowfish et Twofish sont implémentés et ils peuvent être activés. Un autre logiciel Windows (Open Source) avec Blowfish et Twofish est Blowfish Advanced CS[3] - [4].

Blowfish II a été publié en 2005[5], développé par d'autres personnes que Bruce Schneier. Il est basé sur le même principe que Blowfish mais les tables S ont une taille double et les entiers sont sur 64 bits au lieu de 32 bits. Cela se traduit par un algorithme de chiffrement par bloc de 128 bits (comme AES) au lieu de 64 bits[6].

• (en) Site officiel
• (en) Sources dans plusieurs langages de programmation
• (en) Comparatif des performances