Statistical and Algebraic Cryptanalysis of Lightweight and Ultra-Lightweight Symmetric Primitives
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.
Keywords: symmetric cryptography ; light-weight cryptography ; statistical attacks ; RC4 crypt-analysis ; WEP and WPA ; block and stream ciphers ; algebraic cryptanalysis ; systems of sparse polynomial equations of low degree ; challenge-response protocols ; ElimLin ; SAT solving techniques ; cryptographie à clé symétrique ; cryptographie bas-coût ; attaques statistiques ; cryptanalyse de RC4 ; WEP et WPA ; systèmes de chiffrement par blocs ; systèmes de chiffrement à flot ; systèmes d'équations polynomiales creuses de faible degré ; protocoles de challenge/réponse ; ElimLin ; techniques résolvant SATThèse École polytechnique fédérale de Lausanne EPFL, n° 5415 (2012)
Programme doctoral Informatique, Communications et Information
Faculté informatique et communications
Institut de systèmes de communication
Laboratoire de sécurité et de cryptographie
Record created on 2012-08-15, modified on 2013-10-02