Blowfish
Un article de Wikipédia, l'encyclopédie libre.
| 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. | |||
.svg/240px-Blowfish_Feistel_function_(en).svg.png)
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-lune 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 est utilisé dans de nombreux logiciels propriétaires et libres (dont GnuPG et OpenSSH).
Sommaire |
[modifier] 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 grandes tailles qui dépendent de la clé. Il ressemble à CAST-128 qui a adopté, quant à lui, des S-Boxes au contenu fixé d'avance.
.svg/180px-Blowfish_structure_(fr).svg.png)
.svg/180px-Blowfish_Feistel_function_(en).svg.png)
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 (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 remplacant tout le tableau P et les éléments des S-Boxes. Au final, environ 4 Ko de données doivent être générées et Blowfish effectue 512 itérations pour y parvenir.
De part ces contraintes, Blowfish est lent quand il faut changer de clé mais très rapide pour le chiffrement pris séparément.
[modifier] 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é 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, 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.
[modifier] 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).
[modifier] Anecdote
Blowfish a été cité dans la 4e 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.
