PICSI

Blowfish

1  Présentation générale

Pourquoi parler de cet algorithme ici ? car Blowfish a été conçu par Bruce Schneier en 1993 [1] qui souhaitait proposer une alternative libre aux algorithmes existants. Il est inclus dans le noyau linux (plus d'information sur http://www.schneier.com/blowfish.html). De plus, il est légèrement plus rapide que le DES. Il est également considéré comme un algorithme de chiffrement robuste même si des clés faibles ont été découvertes [2]. Il chiffre des blocs de 64 bits à l'aide de clés allant de 32 bits à 448 bits. C'est un chiffrement de Feistel (voir figure 1) qui itère 16 fois une même fonction d'étage.
Figure 1: Vue générale de Blowfish La fonction de déchiffrement est semblable à la fonction de chiffrement à ceci près qu'il faut prendre les sous-clés P_i dans l'ordre inverse.

2  Fonction d'étage

La fonction d'étage de Blowfish (voir figure 2) divise un bloc de 32 bits en 4 sous blocs de 8 bits puis elle applique à ces blocs 4 boîtes S différentes qui étendent chacun des mots de 8 bits en des mots de 32 bits. Ensuite, elle combine les additions modulo 2³² et lex x-ors classiques sur 32 bits.
Figure 2: La fonction d'étage de Blowfish Les boîtes S de Blowfish sont construites durant la génération de sous-clés en même temps que ces dernières à partir de valeurs tirées du nombre π exprimé en hexadécimal.

3  Génération des sous-clés

Dans un premier temps, on découpe la clé originale pouvant aller jusqu'à 448 bits en un ensemble de sous-clés de 4168 octets. On initialise, dans le même temps une table P qui contiendra les 18 sous-clés de 32 bits et chacune des boîtes S à 256 entrées à partir de valeurs tirées du nombre π exprimé en hexadécimal. Puis, on réalise les opérations suivantes permettant le calcul des sous-clés et des boîtes S

• On opère 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, tout à 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 chiffre de nouveau P₁ et P₂ concaténés avec les sous-clés modifiées. Le chiffré ainsi obtenu permet de remplir les éléments P₃ et P₄. On réitère ce processus 512 fois afin de remplacer toutes les sous-clés et les quatre boites S.

On obtient ainsi environ 4Ko de données. De part ces contraintes, Blowfish est lent quand il faut changer de clé mais très rapide pour le chiffrement.

 

 

Références

[1]

Bruce Schneier. Description of a new variable-length key, 64-bit block cipher (blowfish). In Advances in Cryptography - FSE'93, LNCS 809, pages 191-204, Springer-Verlag, 1993.

[2]

Serge Vaudenay. On the weak keys of blowfish. In Advances in Cryptography - FSE'96, LNCS 1039, pages 27-32, Springer-Verlag, 1996.