Faculté informatique et communications IC, Section des systèmes de communication, Institut de systèmes de communication ISC (Laboratoire de sécurité et de cryptographie LASEC)

Applied stream ciphers in mobile communications

Lu, Yi ; Vaudenay, Serge (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2006 ; no 3491.

Add to personal list
    Summary
    This dissertation is concerned with cryptanalysis of E0, the stream cipher used in the short-range wireless radio standard Bluetooth, and of its generalization by means of correlation attacks. It consists of three parts. In the first part, we propose an E0-like combiner with memory as the core stream cipher. First, we formulate a systematic and simple method to compute the correlations. An upper bound of the correlations is given. Second, we show how to build either a uni-bias-based or multi-bias-based distinguisher to distinguish the keystream produced by the combiner from a truly random sequence, once correlations are found. The data complexity of either distinguisher is analyzed for performance comparison. The keystream distinguisher is then upgraded for use in the key-recovery attack. The latter reduces to the well-known maximum likelihood decoding problem given the keystream long enough. In the second part, the core stream cipher is transformed into the dedicated stream cipher by attaching the one-level or two-level initialization scheme. We show that the correlation attack on the core stream cipher leads to the correlation attack on the dedicated stream cipher with the one-level initialization scheme (with equal bias), but not necessarily so with the two-level initialization scheme. In the last part, we generalize the existing concept of conditional correlations and study conditional correlation attacks against stream ciphers and other cryptosystems. A general framework is developed for smart distinguishers, which exploit those generalized conditional correlations. Based on the theory of the traditional distinguisher, we derive the number of samples necessary for a smart distinguisher to succeed. It allows to prove that the smart distinguisher improves on the traditional basic distinguisher. As an application of all our analysis, it leads to the fastest (and only) practical known-plaintext attack on Bluetooth encryption so far. Our attack recovers the encryption key using the first 24 bits of 223.8 frames and with 238 computations.
    Résumé
    Cette thèse traite des cryptanalyses, utilisant des attaques par corrélation, de E0 (le chiffrement à flots utilisé dans le standard Bluetooth de communication sans-fil) et d'une généralisation de E0. Elle est composée de trois parties. Dans la première partie, nous proposons une construction centrée sur un chiffrement à flots utilisant une fonction de combinaison à mémoire similaire à celle de E0. D'abord nous présentons une méthode simple et systématique pour calculer les corrélations. Nous donnons ainsi une borne supérieure aux corrélations. Ensuite, nous montrons comment, une fois des corrélations trouvées, construire deux distingueurs utilisant soit un seul, soit plusieurs de ces biais afin de distinguer une suite chiffrante d'une suite purement aléatoire. Afin de comparer les performances de ces deux distingueurs, nous analysons leurs quantités de données nécessaires. Ce distingueur de suite chiffrante est ensuite modifié pour être utilisé dans une attaque permettant de retrouver la clef. Cette attaque se ramène au problème bien connu de décodage à maximum de vraisemblance, étant donné une suite chiffrante assez longue. Dans la deuxième partie, nous considérons le chiffrement à flot complet en ajoutant au chiffrement central précédent l'un des schémas d'initialisation à un ou à deux niveaux. Nous montrons que l'attaque par corrélation sur le chiffrement à flot central mène à une attaque sur le chiffrement complet utilisant un schéma d'initialisation à un niveau (avec un biais identique) mais pas nécessairement avec le schéma d'initialisation à deux niveaux. Dans la dernière partie, nous généralisons le concept connu de corrélations conditionnelles et étudions des attaques par corrélation conditionnelles sur des chiffrements à flots et d'autres cryptosystèmes. Un cadre général est développé pour des distingueurs améliorés, tirant profit de ces corrélations conditionnelles généralisées. En se reposant sur la théorie des distingueurs traditionnels, nous déduisons le nombre d'échantillons nécessaires au succès d'un distingueur intelligent. Cela permet de prouver que les distingueurs améliorés font mieux que les distingueurs basics traditionnels. En appliquant toutes nos analyses, nous obtenons la plus rapide (mais aussi la seule réalisable à ce jour) attaque à clair connu applicable en pratique au chiffrement Bluetooth. Notre attaque permet de retrouver la clef de chiffrement en utilisant les 24 premiers bits de 223.8 paquets et en 238 calculs.