An Architecture-Independent Instruction Shuffler to Protect against Side-Channel Attacks

Embedded cryptographic systems, such as smart cards, require secure implementations that are robust to a variety of low-level attacks. Side-Channel Attacks (SCA) exploit the information such as power consumption, electromagnetic radiation and acoustic leaking through the device to uncover the secret information. Attackers can mount successful attacks with very modest resources in a short time period. Therefore, many methods have been proposed to increase the security against SCA. Randomizing the execution order of the instructions that are independent, i.e., random shuffling, is one of the most popular among them. Implementing instruction shuffling in software is either implementation specific or has a significant performance or code size overhead. To overcome these problems, we propose in this work a generic custom hardware unit to implement random instruction shuffling as an extension to existing processors. The unit operates between the CPU and the instruction cache (or memory, if no cache exists), without any modification to these components. Both true and pseudo random number generators are used to dynamically and locally provide the shuffling sequence. The unit is mainly designed for in-order processors, since the embedded devices subject to these kind of attacks use simple in-order processors. More advanced processors (e.g., superscalar, VLIW or EPIC processors) are already more resistant to these attacks because of their built-in ILP and wide word size. Our experiments on two different soft in-order processor cores, i.e., OpenRISC and MicroBlaze, implemented on FPGA show that the proposed unit could increase the security drastically with very modest resource overhead. With around 2% area, 1.5% power and no performance overhead, the shuffler increases the effort to mount a successful power analysis attack on AES software implementation over 360 times.

Faster Software Cryptography

Dag Arne Osvik

This thesis presents work on the efficiency and security of cryptographic software. First it describes several efforts to construct very efficient implementations of cryptographic primitives. These include the Advanced Encryption Standard (AES) as well as several popular hash functions, spanning from the old MD5 to several candidates for the upcoming SHA-3 standard. Computer architectures considered range from low-end 8-bit microcontrollers to modern high-end graphics cards, and several key techniques for optimizing such implementations are presented. Results include compact implementations of SHA-1 and SHA-256 with reduced memory footprint and more than triple and double speed, respectively, compared with other fast implementations on the same architecture. Next it presents novel cryptanalytic attacks that can be performed on processor architectures with cache memories, like those used in modern personal computers. These belong to the category of side-channel attacks, exploiting unintended information leakage from an implementation to retrieve secret keys without having to find weaknesses in the cipher itself. The attacks even allow an unprivileged process to attack other processes running in parallel on the same processor, despite partitioning methods such as memory protection, sandboxing and virtualization. Practical results include full AES key recovery in 65ms using only write access to an encrypted partition. Finally the thesis investigates a technique for reducing the number of boolean operations required to express the AES round function, resulting in a significant improvement over previous efforts. This can be useful both for very compact AES implementations in hardware and for bitslice implementations of AES, in which software simulates many copies of the same compact hardware. Such software eliminates the table lookups exploited in cache attacks, and hence this kind of implementaton can be completely immune to them.

EPFL2012

A First Step Towards Automatic Application of Power Analysis Countermeasures

Ali Galip Bayrak, Philip Brisk, Paolo Ienne, Francesco Regazzoni

In cryptography, side channel attacks, such as power analysis, attempt to uncover secret information from the physical implementation of cryptosystems rather than exploiting weaknesses in the cryptographic algorithms themselves. The design and implementation of physically secure cryptosystems is a challenge for both hardware and software designers. Measuring and evaluating the security of a system is manual and empirical, which is costly and time consuming; this work demonstrates that it is possible to automate these processes. We introduce a systematic methodology for automatic application of software countermeasures and demonstrate its effectiveness on an AES software implementation running on an 8-bit AVR microcontroller. The framework identifies the most vulnerable instructions of the implementation to power analysis attacks, and then transforms the software using a chosen countermeasure to protect the vulnerable instructions. Lastly, it evaluates the security of the system using an information-theoretic metric and a direct attack.

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2011

Computer Aided Cryptanalysis from Ciphers to Side Channels

Martin Vuagnoux

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.