E0 (algorithme)

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 264 opérations (au lieu de 2128) si l'on dispose d'une sortie, théorique, de 264 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 280 opérations et une complexité de recherche de clé de l'ordre de 265 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 270 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 235 frames Bluetooth (une frame a une longueur de 2745 bits). La complexité finale pour récupérer la clé est de l'ordre de 240 opérations. Ils améliorent par la suite leur attaque pour atteindre la meilleure méthode publiée à ce jour, soit 237 pour les calculs au préalable et 239 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 235 opérations.

Voir aussi

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article E0 (algorithme) de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Algorithme De Knuth-Morris-Pratt — L algorithme de Knuth Morris Pratt (souvent abrégé par algorithme KMP) est un algorithme de recherche de sous chaîne, permettant de trouver les occurrences d une chaîne P dans un texte S. Sa particularité réside en un pré traitement de la chaîne …   Wikipédia en Français

  • Algorithme KMP — Algorithme de Knuth Morris Pratt L algorithme de Knuth Morris Pratt (souvent abrégé par algorithme KMP) est un algorithme de recherche de sous chaîne, permettant de trouver les occurrences d une chaîne P dans un texte S. Sa particularité réside… …   Wikipédia en Français

  • Algorithme de Knuth-Pratt-Morris — Algorithme de Knuth Morris Pratt L algorithme de Knuth Morris Pratt (souvent abrégé par algorithme KMP) est un algorithme de recherche de sous chaîne, permettant de trouver les occurrences d une chaîne P dans un texte S. Sa particularité réside… …   Wikipédia en Français

  • Algorithme de knuth-morris-pratt — L algorithme de Knuth Morris Pratt (souvent abrégé par algorithme KMP) est un algorithme de recherche de sous chaîne, permettant de trouver les occurrences d une chaîne P dans un texte S. Sa particularité réside en un pré traitement de la chaîne …   Wikipédia en Français

  • Algorithme De Boyer-Moore — L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme 2.1 Pré traitement …   Wikipédia en Français

  • Algorithme De De Casteljau — L algorithme de De Casteljau est un algorithme récursif trouvé par Paul de Casteljau pour approximer efficacement les polynômes écrit dans la base de Bernstein. Cet algorithme peut être utilisé pour dessiner des courbes et des surfaces de Bézier …   Wikipédia en Français

  • Algorithme de boyer-moore — L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme 2.1 Pré traitement …   Wikipédia en Français

  • Algorithme de de Casteljau — L algorithme de De Casteljau est un algorithme récursif trouvé par Paul de Casteljau pour approximer efficacement les polynômes écrit dans la base de Bernstein. Cet algorithme peut être utilisé pour dessiner des courbes et des surfaces de Bézier …   Wikipédia en Français

  • Algorithme de de casteljau — L algorithme de De Casteljau est un algorithme récursif trouvé par Paul de Casteljau pour approximer efficacement les polynômes écrit dans la base de Bernstein. Cet algorithme peut être utilisé pour dessiner des courbes et des surfaces de Bézier …   Wikipédia en Français

  • Algorithme de recherche de chaîne de caractères de Boyer-Moore — Algorithme de Boyer Moore L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme …   Wikipédia en Français

  • Algorithme de recherche de sous-chaîne de Boyer-Moore — Algorithme de Boyer Moore L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”