Lucifer (cryptographie)

Pour les articles homonymes, voir Lucifer (homonymie).

Lucifer
Résumé
Concepteur(s)	Horst Feistel, IBM
Première publication	1971
Dérivé de	Aucun
Chiffrement(s) basé(s) sur cet algorithme	DES
Caractéristiques
Taille(s) du bloc	32, 48, 128 bits
Longueur(s) de la clé	48, 64, 128 bits
Structure	utilisation de S-Box et d'un réseau de Feistel
Nombre de tours	16 (pour la version à 128 bits)
Meilleure cryptanalyse
cryptanalyse linéaire et différentielle
modifier

Lucifer est une famille d'algorithmes de chiffrement par bloc développés par Horst Feistel et ses collègues d'IBM. Il s'agit d'une des premières méthodes de chiffrement moderne destinée à un usage civil. Lucifer fut le précurseur direct de DES. Une des versions, DTD-1, fut utilisée pour la banque en ligne (e-banking) durant les années 1970.

Une autre variante, décrite dans le brevet (US Patent 3,798,359; Juin 1971), utilise un bloc de 48 bits. Le chiffrement se fait via un réseau de permutations et de substitutions. Deux tables de substitutions, des S-Boxes de 4 bits, sont employées. La clé détermine la table utilisée pour la substitution et le brevet décrit l'exécution du chiffrement sur 24 bits à la fois, ainsi qu'une version séquentielle qui travaille par tranches de 8 bits.

Dans un autre brevet (US Patent 3,796,830; Novembre 1971), Lucifer se présente sous la forme d'un bloc de 32 bits chiffré par une clé de 64 bits. L'architecture du chiffrement repose sur une addition modulo 4 et une seule table de substitution de 4 bits. L'algorithme est conçu pour opérer sur 4 bits par coup d'horloge. Il s'agit probablement du chiffrement par bloc le plus simple et le plus réduit jamais conçu.

Une variante plus robuste, décrite par Feistel en 1973, utilise une clé de 128 bits et travaille sur un bloc de la même taille. Il s'agit ici encore d'une série de permutations et de substitutions avec deux S-Boxes de 4 bits dont l'utilisation dépend de la clé. Une modification fut apportée plus tard et publiée par Sorkin en 1984. Ce Lucifer était construit autour d'un réseau de Feistel de 16 tours avec un bloc de 128 bits. La clé était toujours de 128 bits mais malgré cette taille d'un conservatisme remarquable pour l'époque, cette version fut cassée dès l'apparition de la cryptanalyse différentielle. Pour environ la moitié des clés, il est possible de forger une telle attaque avec environ 2³⁶ textes clairs choisis par le cryptanalyste. La complexité en temps se monte à 2³⁶ (résultats de Ben-Aroya et Eli Biham en 1996).

A l'époque, cette version fut candidate pour DES selon un processus semblable à la sélection pour AES). Après plusieurs modifications dont une réduction de la taille de la clé à 56 bits et un bloc plus court (64 bits), ce Lucifer remanié devint le nouveau standard de chiffrement en 1977. Il sera prouvé par la suite que l'algorithme avait été amélioré du point de vue cryptographique en limitant les possibilités d'attaques différentielles. L'équipe d'IBM avait en effet découvert le précurseur de l'attaque différentielle (l'attaque-T) et avait renforcé DES.

Description de la variante de Sorkin

En 1984, Arthur Sorkin décrit une version reposant sur un réseau de Feistel avec 16 tours, comme DES, mais sans les permutations initiales et finales. La clé et le bloc possèdent 128 bits. La fonction de Feistel travaille sur des morceaux de 64 bits (le bloc est scindé en deux parties) avec une clé de tour de 64 bits et 8 bits nommés ICB (interchange control bits). Ces bits contrôlent en fait des opérations de permutation.

Le bloc de 64 bits est considéré comme une série de 8 octets et si les ICB correspondant à un octet particulier sont nuls, alors l'octet est coupé en deux et les 4 bits sont échangés. Autrement, l'octet reste intact. Chaque octet est ensuite introduit dans deux S-Boxes qui travaillent chacune sur une moitié de l'octet. Les sorties des tables sont concaténées et combinées avec une clé intermédiaire en utilisant un XOR (key interruption). Il s'ensuit une permutation en deux étapes, la première fait une permutation constante de l'octet alors que la deuxième mélange les bits entre plusieurs octets.

La création des clés intermédiaires est relativement simple. La clé de 128 bits est chargée dans un registre à décalage. A chaque tour, les 64 premiers bits du registre forment la clé intermédiaire et les 8 derniers bits forment les ICB. Après chaque tour, le registre subit une rotation de 56 bits vers la gauche.

Anecdote

Le nom de « Lucifer » proviendrait de « Demon » qui était obtenu en tronquant « Demonstration », le nom du système sur lequel travaillait Feistel. Le système d'exploitation ne pouvait pas supporter des noms aussi longs, d'où « Demon » qui fut transformé en « Lucifer ».

Voir aussi l'article sur Lucifer

Références

• Horst Feistel. Block Cipher Cryptographic System, US Patent 3,798,359. Filed June 30, 1971. (IBM)
• John Lynn Smith. Recirculating Block Cipher Cryptographic System, US Patent 3,796,830. Filed Nov 2, 1971. (IBM)
• Horst Feistel, (1973). Cryptography and Computer Privacy". Scientific American, 228(5), May 1973, pp 15–23.
• A. Sorkin, (1984). LUCIFER: a cryptographic algorithm. Cryptologia, 8(1), 22—35, 1984.
• Eli Biham, Adi Shamir (1991). Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer. CRYPTO 1991: pp156–171
• Ishai Ben-Aroya, Eli Biham (1996). Differential Cryptanalysis of Lucifer. Journal of Cryptology 9(1), pp. 21–34, 1996.
• Whitfield Diffie, Susan Landau (1998). Privacy on the Line: The Politics of Wiretapping and Encryption.
• Stephen Levy. (2001). Crypto: Secrecy and Privacy in the New Code War (Penguin Press Science).

• Portail de la cryptologie