RC4 | EPFL Graph Search

RC4 (Rivest Cipher 4) est un algorithme de chiffrement en continu conçu en 1987 par Ronald Rivest, l'un des inventeurs du RSA, pour les Laboratoires RSA. Il est supporté par différentes normes, par exemple dans TLS (anciennement SSL) ou encore WEP. Histoire RC4 a été conçu par Ronald Rivest de RSA Security en 1987. Officiellement nommé Rivest Cipher 4, l'acronyme RC est aussi surnommé Ron's Code comme dans le cas de RC2, RC5 et RC6. Les détails de RC4 furent initialement tenus secrets mais en 1994, une description du chiffrement fut postée de manière anonyme sur la liste de diffusion Cypherpunks . Le message apparut ensuite sur le forum sci.crypt puis sur divers sites. L'algorithme avait vraisemblablement fait l'objet d'une rétro-ingénierie. Sur le plan légal, RC4 est une marque déposée dont les implémentations non officielles sont autorisées sous un autre nom que RC4, car l'algorithme n'a pas été breveté. La version non officielle de RC4 est aussi connue sous le nom de

Statistical and Algebraic Cryptanalysis of Lightweight and Ultra-Lightweight Symmetric Primitives

Pouyan Sepehrdad

Symmetric cryptographic primitives such as block and stream ciphers are the building blocks in many cryptographic protocols. Having such blocks which provide provable security against various types of attacks is often hard. On the other hand, if possible, such designs are often too costly to be implemented and are usually ignored by practitioners. Moreover, in RFID protocols or sensor networks, we need lightweight and ultra-lightweight algorithms. Hence, cryptographers often search for a fair trade-off between security and usability depending on the application. Contrary to public key primitives, which are often based on some hard problems, security in symmetric key is often based on some heuristic assumptions. Often, the researchers in this area argue that the security is based on the confidence level the community has in their design. Consequently, everyday symmetric protocols appear in the literature and stay secure until someone breaks them. In this thesis, we evaluate the security of multiple symmetric primitives against statistical and algebraic attacks. This thesis is composed of two distinct parts: In the first part, we investigate the security of RC4 stream cipher against statistical attacks. We focus on its applications in WEP and WPA protocols. We revisit the previous attacks on RC4 and optimize them. In fact, we propose a framework on how to deal with a pool of biases for RC4 in an optimized manner. During this work, we found multiple new weaknesses in the corresponding applications. We show that the current best attack on WEP can still be improved. We compare our results with the state of the art implementation of the WEP attack on Aircrack-ng program and improve its success rate. Next, we propose a theoretical key recovery and distinguishing attacks on WPA, which cryptographically break the protocol. We perform an extreme amount of experiments to make sure that the proposed theory matches the experiments. Finally, we propose a concrete theoretical and empirical proof of all our claims. These are currently the best known attacks on WEP and WPA. In the second part, we shed some lights on the theory behind ElimLin, which is an algorithm for solving multivariate polynomial systems of equations. We attack PRESENT and LBlock block ciphers with ElimLin algorithm and compare their security using this algebraic technique. Then, we investigate the security of KATAN family of block ciphers and multi-purpose cryptographic primitive ARMADILLO against algebraic attacks. We break reduced-round versions of several members of KATAN family by proposing a novel pre-processing technique on the original algebraic representation of the cipher before feeding it to a SAT solver. Finally, we propose a devastating practical key recovery attack against the ARMADILLO1 protocol, which breaks it in polynomial time using a few challenge-response pairs.

EPFL2012

Smashing WEP in A Passive Attack

Pouyan Sepehrdad, Petr Susil, Serge Vaudenay, Martin Vuagnoux

In this paper, we report extremely fast and optimised active and passive attacks against the old IEEE 802.11 wireless communication protocol WEP. This was achieved through a huge amount of theoretical and experimental analysis (capturing WiFi packets), refinement and optimisation of all the former known attacks and methodologies against RC4 stream cipher in WEP mode. We support all our claims by providing an implementation of this attack as a publicly available patch on Aircrack-ng. Our new attacks improve its success probability drastically. We adapt our theoretical analysis in Eurocrypt 2011 to real-world scenarios and we perform a slight adjustment to match the empirical observations. Our active attack, based on ARP injection, requires 22 500 packets to gain success probability of 50% against a 104-bit WEP key, using Aircrack-ng in non-interactive mode. It runs in less than 5 seconds on an off-the-shelf PC. Using the same number of packets, Aicrack-ng yields around 3% success rate. Furthermore, we describe very fast passive only attacks by just eavesdropping TCP/IPv4 packets in a WiFi communication. Our passive attack requires 27 500 packets. This is much less than the number of packets Aircrack-ng requires in active mode (around 37 500), which is a huge improvement.We believe that our analysis brings on further insight to the security of RC4.

2013

Tornado Attack on RC4 with Applications to WEP & WPA

Pouyan Sepehrdad, Petr Susil, Serge Vaudenay, Martin Vuagnoux

In this paper, we construct several tools for building and manipulating pools of biases in the analysis of RC4. We report extremely fast and optimized active and passive attacks against IEEE 802.11 wireless communication protocol WEP and a key recovery and a distinguishing attack against WPA. This was achieved through a huge amount of theoretical and experimental analysis (capturing WiFi packets), refinement and optimization of all the former known attacks and methodologies against RC4 stream cipher in WEP and WPA modes. We support all our claims on WEP by providing an implementation of this attack as a publicly available patch on Aircrack-ng. Our new attack improves its success probability drastically. Our active attack, based on ARP injection, requires 22500 packets to gain success probability of 50% against a 104-bit WEP key, using Aircrack-ng in non-interactive mode. It runs in less than 5 seconds on an off-the-shelf PC. Using the same number of packets, Aicrack-ng yields around 3% success rate. Furthermore, we describe very fast passive only attacks by just eavesdropping TCP/IPv4 packets in a WiFi communication. Our passive attack requires 27500 packets. This is much less than the number of packets Aircrack-ng requires in active mode (around 37500), which is a huge improvement. Deploying a similar theory, we also describe several attacks on WPA. Firstly, we describe a distinguisher for WPA with complexity 2^{42} and advantage 0.5 which uses 2^{42} packets. Then, based on several partial temporary key recovery attacks, we recover the full 128-bit temporary key of WPA by using 2^{42} packets. It works with complexity 2^{96}. So far, this is the best key recovery attack against WPA. We believe that our analysis brings on further insight to the security of RC4.

2015

Statistical and Algebraic Cryptanalysis of Lightweight and Ultra-Lightweight Symmetric Primitives

Pouyan Sepehrdad

EPFL2012