Accueil🇫🇷Chercher

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
Description de l'image Blowfish Feistel function (en).svg.
Résumé
Concepteur(s) Bruce Schneier
Première publication 1993
Dérivé de Aucun
Chiffrement(s) basé(s) sur cet algorithme Twofish
Caractéristiques
Taille(s) du bloc 64 bits
Longueur(s) de la clé 32 à 448 bits (par tranche de 8 bits)
Structure schéma de Feistel
Nombre de tours 16 tours

Meilleure cryptanalyse

Attaque sur quatre tours (Rijmen, 1997). Vulnérabilité statistique avec des clés faibles démontrée par Serge Vaudenay sur 14 tours en 1996.

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.

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 232 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.

Cryptanalyse

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 28r + 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 24r + 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[3] - [4].

Blowfish II

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].

Notes et références

  1. (en) B. Schneier, « Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish) », (consulté le ).
  2. (en) S. Vaudenay, « On the Weak Keys of Blowfish », (consulté le ).
  3. (en) « Blowfish Advanced CS (Personal Edition) » (version du 19 février 2013 sur Internet Archive).
  4. (de) « Blowfish Advanced CS » (version du 24 avril 2013 sur Internet Archive) [PDF].
  5. http://pccipher.free.fr/blowfish2/blowfish2.txt
  6. http://pccipher.free.fr/blowfish2/blowfish2.zip

Liens externes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.