Computer Aided Cryptanalysis from Ciphers to Side Channels

In this dissertation, we study the security of cryptographic protocols and cryptosystems from the mathematical definition of the primitives, up to their physical implementations in the real world. We propose a representation of the chronological design using six layers (cryptographic primitives, cryptographic protocols, implementation, computer insecurity, side channel cryptanalysis and computer human interactions). We do the assumption that these layers should not be studied independently. Indeed, many negligible security weaknesses coming from different layers can be correlated to provide devastating practical attacks on cryptosystems. However, the complexity of a complete security analysis becomes huge and interdisciplinary knowledge is needed. These limitations are probably the reasons of the lack of complete security analysis in practice. We define a novel approach, to combine and study the six layers simultaneously. We propose to follow the data flow of a system and to perform security analysis across the six layers. This technique is applied in practice to the security analysis of computer keyboards, RC4, IEEE 802.11, and e-passports. Thanks to this method, we found 34 additional exploitable correlations in RC4 and we defined the best key recovery attacks on WEP and WPA. We also identified weaknesses in the design and the implementation of e-passports. Therefore, we show that the security risk of every layer seems to be related to its level of complexity. Thus, the implementation layer, the computer insecurity layer, the side channel layer and the computer human interfaces layer are subject to cost-effective attacks in practice. Interestingly, these layers are not intensively studied in cryptography, where research stays usually focused on the two first layers (and some side channel attacks). In this dissertation, we also propose frameworks for computer aided cryptanalysis. Indeed, when the complexity of a system is too important to perform manual analysis, some tools may automatically find weaknesses. Increasing complexity in systems adds new vulnerabilities. Straightforward but automated analysis becomes relevant. Two frameworks have been developed. The first one automatically highlights linear correlation in RC4. The second framework, called Autodafé automatically detects buffer overflows in modern software, using a technique called Fuzzing by Weighting Attacks with Markers.

Keywords: cryptanalysis ; compromising electromagnetic emanations ; tempest ; keyboards ; keystroke recovery ; side channel attacks ; buffer overflow ; autodafe ; fuzzing ; RC4 ; WEP ; WPA ; key recovery attacks ; secret key byte dependency ; linear correlations ; computer aided cryptanalysis ; biases ; visual data representation ; automated cryptanalysis ; e-passports ; privacy ; computer human interfaces ; cryptanalyse ; émanation électromagnétique compromettante ; tempête ; claviers ; recouvrement de frappes de clavier ; attaque par canaux auxiliaires ; débordement de tampon mémoire ; autodafé ; fuzzer ; RC4 ; WEP ; WPA ; attaques par recouvrement de clef ; dépendance des octets de clef secrète ; corrélations linéaires ; cryptanalyse assistée par ordinateur ; biais ; représentation visuelle de données ; cryptanalyse automatisée ; e-passeports ; sphère privée ; interfaces homme machine

Thèse École polytechnique fédérale de Lausanne EPFL, n° 4769 (2010)
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 2010-05-27, modified on 2013-10-02


Related material