Cryptographic Hardware and Embedded Systems - CHES 2007

Previous first-order differential power analysis (DPA) attacks have depended on knowledge of the target algorithm’s input or output. This paper describes a first-order DPA attack against AES in counter mode, in which the initial counter and output values are all unknown.

We introduce the use of multivariate Gaussian mixture models for enhancing higher-order side channel analysis on masked cryptographic implementations. Our contribution considers an adversary with incomplete knowledge at profiling, i.e., the adversary does not know random numbers used for masking. At profiling, the adversary observes a mixture probability density of the side channel leakage. However, the EM algorithm can provide estimates on the unknown parameters of the component densities using samples drawn from the mixture density. Practical results are presented and confirm the usefulness of Gaussian mixture models and the EM algorithm. Especially, success rates obtained by automatic classification based on the estimates of the EM algorithm are very close to success rates of template attacks.

In the recent years, DPA attacks have been widely investigated. In particular, 2-nd order DPA have been improved and successfully applied to break many masked implementations. In this context a higher order masking scheme has been proposed by Schramm and Paar at CT-RSA 2006. The authors claimed that the scheme is resistant against

d

-th order DPA for any arbitrary chosen order

d

. In this paper, we prove that this assertion is false and we exhibit several 3-rd order DPA attacks that can defeat Schramm and Paar’s countermeasure for any value of

d

.

It is shown that the amount of true randomness produced by the recently introduced Galois and Fibonacci ring oscillators can be evaluated experimentally by restarting the oscillators from the same initial conditions and by examining the time evolution of the standard deviation of the oscillating signals. The restart approach is also applied to classical ring oscillators and the results obtained demonstrate that the new oscillators can achieve orders of magnitude higher entropy rates. A theoretical explanation is also provided. The restart and continuous modes of operation and a novel sampling method almost doubling the entropy rate are proposed. Accordingly, the new oscillators appear to be by far more effective than other known solutions for random number generation with logic gates only.

In recent years, IP protection of FPGA hardware designs has become a requirement for many IP vendors. In [34], Simpson and Schaumont proposed a fundamentally different approach to IP protection on FPGAs based on the use of Physical Unclonable Functions (PUFs). Their work only assumes the existence of a PUF on the FPGAs without actually proposing a PUF construction. In this paper, we propose new protocols for the IP protection problem on FPGAs and provide the first construction of a PUF intrinsic to current FPGAs based on SRAM memory randomness present on current FPGAs. We analyze SRAM-based PUF statistical properties and investigate the trade offs that can be made when implementing a fuzzy extractor.

MDPL has been proposed as a masked logic style that counteracts DPA attacks. Recently, it has been shown that the so-called “early propagation effect” might reduce the security of this logic style significantly. In the light of these findings, a 0.13

μm

prototype chip that includes the implementation of an 8051-compatible microcontroller in MDPL has been analyzed. Attacks on the measured power traces of this implementation show a severe DPA leakage. In this paper, the results of a detailed analysis of the reasons for this leakage are presented. Furthermore, a proposal is made on how to improve MDPL with respect to the identified problems.

Masked logic styles use a random mask bit to de-correlate the power consumption of the circuit from the state of the algorithm. The effect of the random mask bit is that the circuit switches between two complementary states with a different power profile. Earlier work has shown that the mask-bit value can be estimated from the power consumption profile, and that masked logic remains susceptible to classic power attacks after only a simple filtering operation. In this contribution we will show that this conclusion also holds for masked pre-charged logic styles and for all practical implementations of masked dual-rail logic styles. Up to now, it was believed that masking and dual-rail can be combined to provide a routing-insensitive logic style. We will show that this assumption is not correct. We demonstrate that the routing imbalances can be used to detect the value of the mask bit. Simulations as well as analysis of design data from an AES chip support this conclusion.

MDPL is a logic style claiming to provide resistance against Differential Side Channel Analysis on power consumption measurements. In this paper we show that the power consumption of a non-linear MDPL gate can be reliably exploited to determine signal values and hence secret data, if the random masks have a slight bias. We present an attack methodology and a case study on how to infer secret key bits of an MDPL secured AES-ASIC in practice by attacking a single MDPL AND gate in a VLSI circuit. Our attack is not based on frequently made assumptions on circuit “anomalies”, but on the per definition unbalanced routing, realistic PRNG biases, and knowledge of the circuit layout.

This paper discusses the state-of-the-art fast software implementation of block ciphers on Intel’s new microprocessor Core2, particularly concentrating on “bitslice implementation”. The bitslice parallel encryption technique, initially proposed by Biham for speeding-up DES, has been successful on RISC processors with many long registers, but on the other side bitsliced ciphers are not widely used in real applications on PC platforms, because in many cases they were actually not very fast on previous PC processors. Moreover the bitslice mode requires a non-standard data format and hence an additional format conversion is needed for compatibility with an existing parallel mode of operation, which was considered to be expensive.

This paper demonstrates that some bitsliced ciphers have a remarkable performance gain on Intel’s Core2 processor due to its enhanced SIMD architecture. We show that KASUMI, a UMTS/GSM mobile standard block cipher, can be four times faster when implemented using a bitslice technique on this processor. Also our bitsliced AES code runs at the speed of 9.2 cycles/byte, which is the performance record of AES ever made on a PC processor. Next we for the first time focus on how to optimize a conversion algorithm between a bitslice format and a standard format on a specific processor. As a result, the bitsliced AES code can be faster than a highly optimized “standard AES” code on Core2, even taking an overhead of the conversion into consideration. This means that in the CTR mode, bitsliced AES is not only fast but also fully compatible with an existing implementation and moreover secure against cache timing attacks, since a bitsliced cipher does not use any lookup tables with key/data-dependent address.

This papers introduces several binary scalar multiplication algorithms with applications to cryptography. Remarkably, the proposed algorithms regularly repeat the same pattern when evaluating a scalar multiplication in an (additively written) abelian group. Furthermore, they are generic and feature the following properties:

no dummy operation is involved;

no precomputation nor prior recoding is needed;

a small number of temporary registers / code memory is required;

the scalar is processed right-to-left.

As a result, they are particularly well fitted for implementing cryptosystems in constrained devices, in an efficient yet secure way.

This paper describes a new compression function, MAME designed for hardware-oriented hash functions which can be used in applications with reduced hardware requirements. MAME takes a 256-bit message block and a 256-bit chaining variable as input and produces a 256-bit output. In the light of recent attacks on MD5 and SHA-1, our design strategy is very conservative, and we show that our compression function is secure against various kinds of widely known attacks with very large security margins. The simple logical operations and the hardware efficient S-boxes are used to achieve a hardware implementation of MAME requiring only 8.1 Kgates on 0.18

μm

technology.

Message Authentication Code construction Alred and its AES-based instance Alpha-MAC were introduced by Daemen and Rijmen in 2005. We show that under certain assumptions about its implementation (namely that keyed parts are perfectly protected against side-channel attacks but bulk hashing rounds are not) one can efficiently attack this function. We propose a side-channel collision attack on this MAC recovering its internal state just after 29 measurements in the known-message scenario which is to be compared to 40 measurements required by collision attacks on AES in the chosen-plaintext scenario. Having recovered the internal state, we mount a selective forgery attack using new 4 to 1 round collisions working with negligible memory and time complexity.

Contrarily to Kerckhoffs’ principle, many applications of today’s cryptography still adopt the

security by obscurity

paradigm. Furthermore, in order to rely on its proven or empirical security, some realizations are based on a given well known and widely used cryptographic algorithm. In particular, a possible design would obfuscate a standard block cipher

E

by surrounding it with two

secret

external encodings

P

1

and

P

2

(one-to-one mappings), leading to the proprietary algorithm

E′ = P

2

 ∘ 

E

 ∘ 

P

1

.

A claimed advantage of this approach is that, since inputs and outputs of the underlying function

E

are not known by a potential attacker, such a construction is usually believed to inherently prevent any kind of transient fault analysis that may apply on the core function

E

. In this paper, we show that this latter argument is not true, by exhibiting a key recovery attack which applies to the whole class of externally encoded DES or Triple-DES. Moreover, our attack remains applicable even in the presence of the classical counter-measure against fault attacks which consists in executing the algorithm twice and returning an output only if both results are identical.

We describe two new techniques of side-channel cryptanalysis which we call the

impossible collision attack

and the

multiset collision attack

. These are inspired by the state-of-the-art cryptanalytic techniques of impossible differential attacks [BBS99] and partial-function collision attacks [GM00] respectively. Using these techniques on an example of the AES we show that one has to mask all the rounds of a 128-bit key AES in order to prevent such attacks. For example these attacks can be used to break a recent proposal by Schramm et al. [SP06] of high order masking for the AES, since it protects only 3 external rounds.

Graphics Processing Units (GPUs) present large potential performance gains within stream processing applications over the standard CPU. These performance gains are best realised when high computational intensity is required across large amounts of mostly independent input elements. The GPU’s success in general purpose stream processing has been demonstrated in many diverse fields, though attempts to port cryptographic algorithms to the GPU have thus far met little success. In recent years, GPU architectures have continued to develop a more flexible and uniform programming environment. These developments have overcome a lot of previously encountered restrictions in cipher implementations. We present novel approaches for the implementation of the AES block cipher encryption algorithm on these GPUs. This work also serves as a precursor for future cipher implementations on the most advanced GPU architecture, the recently released Nvidia G80, which now includes integer support and a simplified programming interface.

This paper presents a design-space exploration of the Galois/Counter Mode (GCM) algorithm with Advanced Encryption Standard (AES) as underlying block cipher for high throughput applications to combine data encryption and message authentication on FPGAs. Four different degrees of parallelism were implemented, namely a 128-, 64-, 32- and 16-bit wide data path calculating an output block in 1, 2, 4 and 8 clock cycles, respectively. Regarding the AES algorithm different

SubBytes()

and round architectures were evaluated against each other. For the multiplier required for GCM, two bit-parallel, a digit-serial and a hybrid architecture were evaluated. The different architectures were designed, implemented and tested on a Xilinx Virtex4-FX100 FPGA. All architectures support key lengths of 128, 192 and 256 bits and are equipped with a ready-to-use interface for real-world applications. A throughput of 15.3 Gb/s was reached. It pointed out that throughput rates for state-of-the-art communication channels can be achieved using reasonable hardware resources. The results comparing slice counts, RAM usage and speed are presented.

Since their introduction in constructive cryptographic applications, pairings over (hyper)elliptic curves are at the heart of an ever increasing number of protocols. Software implementations being rather slow, the study of hardware architectures became an active research area. In this paper, we first study an accelerator for the

η

T

pairing over

$\mathbb{F}_3[x]/(x^{97}+x^{12}+2)$

. Our architecture is based on a unified arithmetic operator which performs addition, multiplication, and cubing over

$\mathbb{F}_{3^{97}}$

. This design methodology allows us to design a compact coprocessor (1888 slices on a Virtex-II Pro 4 FPGA) which compares favorably with other solutions described in the open literature. We then describe ways to extend our approach to any characteristic and any extension field.

Elliptic curve signature schemes offer shorter signatures compared to other methods and a family of curves called Koblitz curves can be used for reducing the cost of signing and verification. This paper presents an FPGA implementation designed specifically for rapid verification of self-certified identity based signatures using Koblitz curves. Verification requires computation of three elliptic curve point multiplications which are computed efficiently with 3-term multiple point multiplication and joint sparse form. Certain improvements to precomputations associated with multiple point multiplications are introduced. It is shown that, when using parallel processors, it is possible to gain considerable increases in the number of operations per second by allowing slightly longer computation times for single operations. It is demonstrated that up to 166,000 verifications per second can be computed using a single Altera Stratix II FPGA.

This paper describes a modular exponentiation processing method and circuit architecture that can exhibit the maximum performance of FPGA resources. The modular exponentiation architecture proposed by us comprises three main techniques. The first technique is to improve the Montgomery multiplication algorithm in order to maximize the performance of the multiplication unit in FPGA. The second technique is to improve and balance the circuit delay. The third technique is to ensure and make fast the scalability of the effective FPGA resource. We propose a circuit architecture that can handle multiple data lengths using the same circuits. In addition, our architecture can perform fast operations using small-scale resources; in particular, it can complete 512-bit modular exponentiation in 0.26 ms by means of XC4VF12-10SF363, which is the minimum logic resources in the Virtex-4 Series FPGAs. Also, the number of SLICEs used is approx. 4000 to make a very compact design. Moreover, 1024-, 1536- and 2048-bit modular exponentiations can be processed in the same circuit with the scalability.

Replay attacks are often the most costly attacks to thwart when dealing with off-chip memory integrity. With a trusted System-on-Chip, the existing countermeasures against replay require a large amount of on-chip memory to provide tamper-proof storage for metadata such as hash values or nonces. Tree-based strategies can be deployed to reduce this unacceptable overhead; for example, the well-known Merkle tree technique decreases this overhead to a single hash value. However, it comes at the cost of performance-killing characteristics for embedded systems – e.g. non-parallelizable hash computations on tree updates. In this paper, we propose an alternative solution: the Tamper-Evident Counter Tree (TEC-Tree). It allows for tamper-evident off-chip storage of the nonces involved in a replay countermeasure; TEC-Tree parallelizes the computations involved in both the authentication and tree update processes. Moreover, because our tree relies on block encryption, it provides data confidentiality at no extra cost. TEC-Tree is a deployable solution for memory integrity, with low performance hit and hardware cost.

In recent years, different instruction set extensions for cryptography have been proposed for integration into general-purpose RISC processors. Both public-key and secret-key algorithms can profit tremendously from a small set of custom instructions specifically designed to accelerate performance-critical code sections. While the impact of instruction set extensions on performance and silicon area has been widely investigated in the recent past, the resulting security aspects (i.e. resistivity to side-channel attacks) of this particular design approach remain an open research topic. In this paper we discuss and analyze different techniques for increasing the side-channel resistance of AES software implementations using instruction set extensions. Furthermore, we propose a combination of hardware and software-related countermeasures and investigate the resulting effects on performance, cost, and security. Our experimental results show that a moderate degree of protection can be achieved with a simple software countermeasure. Hardware countermeasures, such as the implementation of security-critical functional units using a DPA-resistant logic style, lead to much higher resistance against side-channel attacks at the cost of a moderate increase in silicon area and power consumption.

During the last years, more and more security applications have been developed that are based on passive 13.56 MHz RFID devices. Among the most prominent applications are electronic passports and contactless payment systems. This article discusses the effectiveness of power and EM attacks on this kind of devices. It provides an overview of different measurement setups and it presents concrete results of power and EM attacks on two RFID prototype devices. The first device performs AES encryptions in software, while the second one performs AES encryptions in hardware. Both devices have been successfully attacked with less than 1 000 EM traces. These results emphasize the need to include countermeasures into RFID devices.

RFID applications do not always use encryption to ensure the security as public key cryptographic algorithms that are costly in term of computing resources. We proposed to secure the communication from an ISO 14443 RFID card to the reader against passive eavesdropping at the physical layer by adding noise. During the card reply, the reader generates an appropriate noise that is modulated by the load of the card. By knowing the noise it emitted, the reader is able to subtract it and to retrieve the card message when a spying probe in the field is inefficient.

A certificate of authenticity (COA) is an inexpensive physical object that has a random and unique multidimensional structure

S

which is hard to near-exactly replicate. An inexpensive device should be able to scan object’s physical “fingerprint,” i.e., obtain a set of features in the form of a multidimensional signal x that pseudo-uniquely represents

S

. For a given “fingerprint” x and without access to

S

, it should be computationally difficult to construct an object of fixed dimensions with a “fingerprint” y which is at a bounded proximity from x according to a standardized distance metric. We introduce objects that behave as COAs in the electromagnetic field. The objective is to complement RFIDs so that they are physically, not only digitally, unique and hard to replicate. By enabling this feature, we introduce a tag whose information about the product can be read within a relative far-field, and also whose authenticity can be reliably verified within its near-field. In order to counterfeit a tag, the adversary faces two difficulties – a computational and a manufacturing one. The computational difficulty stems from the hardness of solving linear inverse problems in the electromagnetic field. In order to create an actual tag, the adversary must also manufacture a multidimensional object with a specific three-dimensional topology, dielectric properties, and conductivity.

The hardness of the integer factorization problem assures the security of some public-key cryptosystems including RSA, and the number field sieve method (NFS), the most efficient algorithm for factoring large integers currently, is a threat for such cryptosystems. Recently, dedicated factoring devices attract much attention since it might reduce the computing cost of the number field sieve method. In this paper, we report implementational and experimental results of a dedicated sieving device “CAIRN 2” with Xilinx’s FPGA which is designed to handle up to 768-bit integers. Used algorithm is based on the line sieving, however, in order to optimize the efficiency, we adapted a new implementational method (the pipelined sieving). In addition, we actually factored a 423-bit integer in about 30 days with the developed device CAIRN 2 for the sieving step and usual PCs for other steps. As far as the authors know, this is the first FPGA implementation and experiment of the sieving step in NFS.

In this last decade, Elliptic Curve Cryptography (ECC) has gained increasing acceptance in the industry and the academic community and has been the subject of several standards. This interest is mainly due to the high level of security with relatively small keys provided by ECC. Indeed, no sub-exponential algorithms are known to solve the underlying hard problem: the Elliptic Curve Discrete Logarithm.

The aim of this work is to explore the possibilities of dedicated hardware implementing the best known algorithm for generic curves: the parallelized Pollard’s

ρ

method. This problem has specific constraints and requires therefore new architectures. Four different strategies were investigated with different FPGA families in order to provide the best area-time product, according to the capabilities of the chosen platforms. The approach yielding the best throughput over hardware cost ratio is then fully described and was implemented in order to estimate the cost of an attack. Such results should help to improve the accuracy of the security level offered by a given key size, especially for the shorter parameters proposed for resource constrained devices.

A5/2 is a synchronous stream cipher that is used for protecting GSM communication. Recently, some powerful attacks [2,5] on A5/2 have been proposed. In this contribution we enhance the ciphertext-only attack [2] by Barkan, Biham, and Keller by designing special-purpose hardware for

generating and solving

the required systems of linear equations. For realizing the LSE solver component, we use an approach recently introduced in [5,6] describing a parallelized hardware implementation of the Gauss-Jordan algorithm. Our hardware-only attacker immediately recovers the initial secret state of A5/2 - which is sufficient for decrypting all frames of a session - using a few ciphertext frames

without any precomputations and memory

. More precisely, in contrast to [2] our hardware architecture directly attacks the GSM speech channel (TCH/FS and TCH/EFS). It requires 16 ciphertext frames and completes the attack in about 1 second. With minor changes also input from other GSM channels (e.g., SDCCH/8) can be used to mount the attack.

This paper describes an attack on cryptographic devices called Differential Behavioral Analysis (or DBA). This is an hybrid attack between two already powerful attacks: differential power analysis (DPA) for the statistical treatment and safe-error attack for the fault type. DBA, simulated on an algorithmic model of AES appears to be very efficient. The attacker is able to recover the entire secret key with byte-wise “stuck-at” faults injected repetitively. A theorical as well as a more realistic approach are presented.

We propose to apply an information theoretic metric to the evaluation of side-channel resistant logic styles. Due to the long design and development time required for the physical evaluation of such hardware countermeasures, our analysis is based on simulations. Although they do not aim to replace the need of actual measurements, we show that simulations can be used as a meaningful first step in the validation chain of a cryptographic product. For illustration purposes, we apply our methodology to gate-level simulations of different logic styles and stress that it allows a significant improvement of the previously considered evaluation methods. In particular, our results allow putting forward the respective strengths and weaknesses of actual countermeasures and determining to which extent they can practically lead to secure implementations (with respect to a noise parameter), if adversaries were provided with simulation-based side-channel traces. Most importantly, the proposed methodology can be straightforwardly adapted to adversaries provided with any other kind of leakage traces (including physical ones).

A side-channel analysis of a cryptographic algorithm generally concentrates on the encryption or decryption phases, rarely on the key generation phase. In this paper, we show that, when not properly implemented, the fast prime generation algorithm proposed by Joye and Paillier at CHES 2006 is susceptible to side-channel analysis; its main application is the generation of RSA key-pairs for embedded platforms like smart-cards. Our attack assumes that some parity bit can be recovered through SPA when it appears in a branch condition. Our attack can be combined with Coppersmith’s theorem to improve its efficiency; we show that for 1024-bit RSA moduli, one can recover the factorization of roughly 1/1000 of the RSA moduli.

With the establishment of the AES the need for new block ciphers has been greatly diminished; for almost all block cipher applications the AES is an excellent and preferred choice. However, despite recent implementation advances, the AES is not suitable for extremely constrained environments such as RFID tags and sensor networks. In this paper we describe an ultra-lightweight block cipher,

present

. Both security and hardware efficiency have been equally important during the design of the cipher and at 1570 GE, the hardware requirements for

present

are competitive with today’s leading compact stream ciphers.