# Blowfish

Blowfish est un algorithme de chiffrement symétrique (c'est-à-dire « à clef secrète ») par blocs conçu par Bruce Schneier en 1993.
Blowfish utilise une taille de bloc de 64 bits et la clé de longueur variable peut aller de 32 à 448 bits. Elle est basée sur l'idée qu'une bonne sécurité contre les attaques de cryptanalyse peut être obtenue en utilisant de très grandes clés pseudo-aléatoires.
Blowfish présente une bonne rapidité d'exécution excepté lors d'un changement de clé, il est environ 5 fois plus rapide que Triple DES et deux fois plus rapide que IDEA. Malgré son âge, il demeure encore solide du point de vue cryptographique avec relativement peu d'attaques efficaces sur les versions avec moins de tours. La version complète avec 16 tours est à ce jour entièrement fiable et la recherche exhaustive reste le seul moyen pour l'attaquer.
Il a été placé dans le domaine public par son créateur ; il n'est protégé par aucun brevet, et son utilisation n'est pas soumise à licence. Cela explique en partie son succès, car ce fut un des premiers algorithmes de chiffrement dont l'utilisation était libre. Il est utilisé dans de nombreux logiciels propriétaires et libres (dont GnuPG et OpenSSH).

## Algorithme

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.
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$^{32}$ 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é, 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.

## Utilisation réelle

Blowfish est un chiffrement par blocs rapide, sauf lors du changement de clé. Chaque nouvelle clé nécessite l'équivalent d'un pré-traitement de chiffrement d'environ 4 kilo-octets de texte, ce qui est très lent par rapport aux autres chiffrements par blocs. Ce n'est pas un problème pour les ordinateurs de bureau et les ordinateurs portables plus anciens, bien qu'elle empêche l'utilisation dans les plus petits systèmes embarqués tels que les premières cartes à puce.
Comme Blowfish doit être initialisé à l'aide d'une clé, c'est une bonne pratique d'avoir cette clé hachée. Pour éviter que cette clé ne soit hachée avec une fonction de hachage trop courte (SHA-160, SHA-256), est apparue en 2005 une fonction de hachage basée sur MD2 de Ron Rivest, uniquement pour les mots de passe Blowfish$^,$. Cette fonction hache une clé ou un mot de passe en une clé de 56 ou 72 octets pour Blowfish ou de 528 octets pour Blowfish II.
Blowfish a été l'un des premiers chiffrements par blocs sécurisés non soumis à des brevets et donc librement disponible pour tout le monde. Cet avantage a contribué à sa popularité dans les logiciels cryptographiques.

## Cryptanalyse

En 1996, Serge Vaudenay a montré que les permutations dans Blowfish s'écartaient sensiblement des permutations complètement aléatoires sur 14 tours. 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.

## Exemples

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$^,$.

## Blowfish II

Blowfish II a été publié en 2005, 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$^,$.