E0 (algorithme)

E0 est un algorithme de chiffrement par flot utilisé par le protocole Bluetooth pour protéger les transmissions. Il génère une suite pseudo-aléatoire avec laquelle on effectue un XOR avec les données. La clé peut avoir une taille variable mais sa longueur est généralement de 128 bits.

À chaque itération, E0 génère un bit grâce à quatre registres à décalage de longueurs différentes (25, 31, 33, 39 bits) et deux états internes de 2 bits chacun. À chaque coup d'horloge, les registres sont décalés et les deux états sont mis à jour en utilisant l'état courant, l'état précédent et les valeurs présentes dans les registres à décalage. Quatre bits sont extraits des quatre registres à décalage et sont additionnés. L'algorithme effectue ensuite un XOR entre cette somme et la valeur du registre de 2 bits, le premier bit ainsi obtenu est la sortie pour le chiffrement.

E0 se divise en trois parties :

• préparation de la clé (payload key generator)
• génération du flux (keystream generator)
• chiffrement

La préparation de l'état initial dans Bluetooth utilise la même structure que la génération du flux de bits aléatoires. On est donc en présence de deux E0 couplés. Un état initial de 132 bits est produit par le premier stage à partir de quatre entrées (clé de 128 bits, adresse Bluetooth sur 48 bits et compteur du maître de 26 bits). Le résultat passe ensuite dans une opération polynomiale et on obtient une clé que l'on transmet au stage suivant, celui qui va générer le flux utilisé pour le chiffrement. La clé a une taille variable mais toujours un multiple de 2 (entre 8 et 128 bits). On utilise en général 128 bits. Ces bits sont introduits dans les registres à décalage du deuxième stage. On produit ensuite 200 bits pseudo-aléatoires grâce à 200 coups d'horloge du générateur, les derniers 128 bits sont insérés dans les registres à décalage. C'est l'état initial du générateur par flot.

Cryptanalyse

Plusieurs attaques et tentatives de cryptanalyse ont été menées sur E0 et le protocole Bluetooth.

En 1999, Miia Hermelin et Kaisa Nyberg ont montré que E0 était susceptible d'être cassé avec 2⁶⁴ opérations (au lieu de 2¹²⁸) si l'on dispose d'une sortie, théorique, de 2⁶⁴ bits. Ce type d'attaque a été peaufinée par la suite par Kishan Chand Gupta et Palash Sarkar. Scott Fluhrer de Cisco Systems a démontré une attaque théorique avec un calcul préalable de 2⁸⁰ opérations et une complexité de recherche de clé de l'ordre de 2⁶⁵ opérations. Il en conclut que la sécurité maximale de E0 est équivalente à une clé de 65 bits et que des clés plus longues n'amélioraient pas la sécurité. Il optimise de ce fait une attaque précédente due à Golic, Bagini et Morgani qui nécessitait 2⁷⁰ opérations.

En 2000, le Finlandais Juhia Vainio a mis en évidence les problèmes liés à une mauvaise utilisation de E0 et plus généralement les failles possibles dans Bluetooth.

En 2004, Serge Vaudenay et Yi Lu ont publié une attaque statistique utilisant les 24 premiers bits de 2³⁵ frames Bluetooth (une frame a une longueur de 2745 bits). La complexité finale pour récupérer la clé est de l'ordre de 2⁴⁰ opérations. Ils améliorent par la suite leur attaque pour atteindre la meilleure méthode publiée à ce jour, soit 2³⁷ pour les calculs au préalable et 2³⁹ pour la recherche effective de la clé.

Éric Filiol a mis en évidence en 2006 des faiblesses dans Bluetooth en apportant une preuve à divulgation nulle de connaissance, les détails de l'attaque n'ont pas encore été publiés (août 2006) mais l'estimation de la complexité de l'attaque est de l'ordre de 2³⁵ opérations.

Voir aussi

• A5/1
• RC4

Liens externes

• (en) Spécifications de Bluetooth 1.2 (E0 dans partie H, volume 2)
• (en) Bluetooth Security, Juhia Vainio
• (en) Correlation properties of the Bluetooth Combiner, Miia Hermelin, Kaisa Nyberg
• (en) Improved key recovery of level 1 of the Bluetooth Encryption, Scott Fluhrer
• (en) Faster correlation attack on Bluetooth Keystream Generator E0, Serge Vaudenay, Yi Lu
• (en) Cryptanalysis of E0, présentation de Serge Vaudenay et Yi Lu
• (en) Zero-knowledge-like Proof of Cryptanalysis of Bluetooth Encryption, Eric Filiol