Blowfish

Blowfish
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.
modifier

Blowfish est un algorithme de chiffrement symétrique (i.e. « à clef secrète ») par blocs conçu par Bruce Schneier en 1993. Il tire son nom du poisson globe japonais (ou fugu), qui en est également l'emblème.

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 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 (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. Au final, ce sont 72 octets de données qui doivent être générées 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 à ce 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é 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 implementés et ils peuvent être activés. Un autre Logiciel Windows (Open Source) avec Blowfish et Twofish est Blowfish Advanced CS, Anglais (Un Manual en Allemand; PDF).

Anecdote

Blowfish a été cité dans la 4^e et la 7^e saison de la série 24 heures chrono.

Mais malgré ce qui est dit dans l'épisode le mentionnant, il n'a toujours pas été cassé et nous laissons le lecteur juger du terme « algorithme propriétaire ». À l'heure actuelle, il s'agit forcément d'une recherche exhaustive qui n'a rien de spécial.

- They used Blowfish algorithm.
- How can you tell?
- By the tab on the file headers.
- Can you decrypt it?
- CTU has a proprietary algorithm. It shouldn't take that long. We'll start by trying to hack the password.
Let's start with the basics. Write down nicknames, birthdays, pets—anything you think he might have used.

- Ils ont utilisé l'algorithme Blowfish.
- Comment pouvez-vous l'affirmer ?
- D'après les tabulations dans les entêtes du fichier.
- Pouvez-vous le déchiffrer ?
- La cellule anti-terrorisme a un algorithme propriétaire. Ça ne devrait pas prendre beaucoup de temps. On va d'abord essayer de hacker le mot de passe.
Commençons avec les plus courants en écrivant les pseudonymes, anniversaires, noms d'animaux, tout ce que vous pensez qu'il aurait pu utiliser.

Il en va de même dans la saison 7 où il est fait mention de Blowfish 148, taille de clé n'existant pas.

Notes et références

1. ↑ (en)http://www.schneier.com/paper-blowfish-fse.html
2. ↑ (en)http://lasecwww.epfl.ch/php_code/publications/search.php?ref=Vau96a

Liens externes

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