Cryptographic Hardware and Embedded Systems - CHES 2003

Ubiquitous computing, over a decade in the making, has finally graduated from whacky buzzword through fashionable research topic to something that is definitely and inevitably happening. This will mean revolutionary changes in the way computing a.ects our society-changes of the same magnitude and scope as those brought about by the World Wide Web.

We introduce multi-channel attacks, i.e., side-channel attacks which utilize multiple side-channels such as power and EM simultaneously. We propose an adversarial model which combines a CMOS leakage model and the maximum-likelihood principle for performing and analyzing such attacks. This model is essential for deriving the optimal and very often counter-intuitive techniques for channel selection and data analysis. We show that using multiple channels is better for template attacks by experimentally showing a three-fold reduction in the error probability. Developing sound countermeasures against multi-channel attacks requires a rigorous leakage assessment methodology. Under suitable assumptions and approximations, our model also yields a practical assessment methodology for net information leakage from the power and all available EM channels in constrained devices such as chip-cards. Classical DPA/DEMA style attacks assume an adversary weaker than that of our model. For this adversary, we apply the maximum-likelihood principle to such design new and more efficient single and multiple-channel DPA/DEMA attacks.

We present HMM attacks, a new type of cryptanalysis based on modeling randomized side channel countermeasures as Hidden Markov Models (HMM’s). We also introduce Input Driven Hidden Markov Models (IDHMM’s), a generalization of HMM’s that provides a powerful and unified cryptanalytic framework for analyzing countermeasures whose operational behavior can be modeled by a probabilistic finite state machine. IDHMM’s generalize previous cryptanalyses of randomized side channel countermeasures, and they also often yield better results. We present efficient algorithms for key recovery using IDHMM’s. Our methods can take advantage of multiple traces of the side channel and are inherently robust to noisy measurements. Lastly, we apply IDHMM’s to analyze two randomized exponentiation algorithms proposed by Oswald and Aigner. We completely recover the secret key using as few as ten traces of the side channel.

Field Programmable Gate Arrays (FPGAs) are becoming increasingly popular, especially for rapid prototyping. For implementations of cryptographic algorithms, not only the speed and the size of the circuit are important, but also their security against implementation attacks such as side-channel attacks. Power-analysis attacks are typical examples of side-channel attacks, that have been demonstrated to be effective against implementations without special countermeasures. The flexibility of FPGAs is an important advantage in real applications but also in lab environments. It is therefore natural to use FPGAs to assess the vulnerability of hardware implementations to power-analysis attacks. To our knowledge, this paper is the first to describe a setup to conduct power-analysis attacks on FPGAs. We discuss the design of our hand-made FPGA-board and we provide a first characterization of the power consumption of a Virtex 800 FPGA. Finally we provide strong evidence that implementations of elliptic curve cryptosystems without specific countermeasures are indeed vulnerable to simple power-analysis attacks.

Bernstein [1] and Lenstra et al. [5] have proposed specialized hardware devices for speeding up the linear algebra step of the number field sieve. A key issue in the design of these devices is the question whether the required hardware fits onto a single wafer when dealing with cryprographically relevant parameters.We describe a modification of these devices which distributes the technologically challenging single wafer design onto separate parts (chips) where the inter-chip wiring is comparatively simple. A preliminary analysis of a ‘distributed variant of the proposal in [5]’ suggests that the linear algebra step for 1024-bit numbers could be doable on a 23 x 23-network with special purpose processors in less than 19 hours at a clocking rate of 200 MHz, where each processor has about the size of a Pentium Northwood. Allowing for a 16 x 16 mesh of processing units with 36mm x 36mm, the linear algebra step might take less than 3 hours.

This paper presents the results of applying an attack against the Data Encryption Standard (DES) implemented in some applications, using side-channel information based on CPU delay as proposed in [11]. This cryptanalysis technique uses side-channel information on encryption processing to select and collect effective plaintexts for cryptanalysis, and infers the information on the expanded key from the collected plaintexts. On applying this attack, we found that the cipher can be broken with 223 known plaintexts and 224 calculations at a success rate > 90%, using a personal computer with 600-MHz Pentium III.We discuss the feasibility of cache attack on ciphers that need many S-box look-ups, through reviewing the results of our experimental attacks on the block ciphers excluding DES, such as AES.

In this paper we describe a differential fault attack technique working against Substitution-Permutation Networks, and requiring very few faulty ciphertexts. The fault model used is realistic, as we consider random faults affecting bytes (faults affecting one only bit are much harder to induce). We implemented our attack on a PC for both the AES and Khazad. We are able to break the AES-128 with only 2 faulty ciphertexts, assuming the fault occurs between the antepenultimate and the penultimate MixColumn; this is better than the previous fault attacks against AES [6][10][11]. Under similar hypothesis, Khazad is breakable with 3 faulty ciphertexts.

To protect a cryptographic algorithm against Differential Power Analysis, a general method consists in masking all intermediate data with a random value. When a cryptographic algorithm combines boolean operations with arithmetic operations, it is then necessary to perform conversions between boolean masking and arithmetic masking. A very efficient method was proposed by Louis Goubin in [6] to convert from boolean masking to arithmetic masking. However, the method in [6] for converting from arithmetic to boolean masking is less efficient. In some implementations, this conversion can be a bottleneck. In this paper, we propose an improved algorithm to convert from arithmetic masking to boolean masking. Our method can be applied to encryption schemes such as IDEA and RC6, and hashing algorithms such as SHA-1.

A new general method for designing key-dependent reversible circuits is proposed and concrete examples are included. The method is suitable for data scrambling of internal links and memories on smart card chips in order to foil the probing attacks. It also presents a new paradigm for designing block ciphers suitable for small-size and/or high-speed hardware implementations. In particular, a concrete building block for such block ciphers with a masking countermeasure against power analysis incorporated on the logical gate level is provided.

Deliberate injection of faults into cryptographic devices is an effective cryptanalysis technique against symmetric and asymmetric encryption algorithms. In this paper we will describe parity code based concurrent error detection (CED) approach against such attacks in substitution-permutation network (SPN) symmetric block ciphers [22]. The basic idea compares a carefully modified parity of the input plain text with that of the output cipher text resulting in a simple CED circuitry. An analysis of the SPN symmetric block ciphers reveals that on one hand, permutation of the round outputs does not alter the parity from its input to its output. On the other hand, exclusive-or with the round key and the non-linear substitution function (s-box) modify the parity from their inputs to their outputs. In order to change the parity of the inputs into the parity of outputs of an SPN encryption, we exclusive-or the parity of the SPN round function output with the parity of the round key. We also add to all s-boxes an additional 1-bit binary function that implements the combined parity of the inputs and outputs to the s-box for all its (input, output) pairs. These two modifications are used only by the CED circuitry and do not impact the SPN encryption or decryption. The proposed CED approach is demonstrated on a 16-input, 16-output SPN symmetric block cipher from [1].

This paper describes a design method to secure encryption algorithms against Differential Power Analysis at the logic level. The method employs logic gates with a power consumption, which is independent of the data signals, and therefore the technique removes the foundation for DPA. In a design experiment, a fundamental component of the DES algorithm has been implemented. Detailed transistor level simulations show a perfect security whenever the layout parasitics are not taken into account.

Balanced asynchronous circuits have been touted as a superior replacement for conventional synchronous circuits. To assess these claims, we have designed, manufactured and tested an experimental asynchronous smart-card style device. In this paper we describe the tests performed and show that asynchronous circuits can provide better tamper-resistance. However, we have also discovered weaknesses with our test chip, some of which have resulted in new designs, and others which are more fundamental to the asynchronous design approach. This has led us to investigate the novel approach of design-time security analysis rather than rely on post manufacture analysis.

There are many applications for true, unpredictable random numbers. For example the strength of numerous cryptographic operations is often dependent on a source of truly random numbers. Sources of random information are available in nature but are often hard to access in integrated circuits. In some specialized applications, analog noise sources are used in digital circuits at great cost in silicon area and power consumption. These analog circuits are often influenced by periodic signal sources that are in close proximity to the random number generator. We present a random number generator comprised entirely of digital circuits, which utilizes electronic noise. Unlike earlier work [11], only standard digital gates without regard to precise layout were used.

A true random number generator (TRNG) usually consists of two components: an “unpredictable” source with high entropy, and a randomness extractor — a function which, when applied to the source, produces a result that is statistically close to the uniform distribution. When the output of a TRNG is used for cryptographic needs, it is prudent to assume that an adversary may have some (limited) influence on the distribution of the high-entropy source. In this work:1We define a mathematical model for the adversary’s influence on the source.2We show a simple and efficient randomness extractor and prove that it works for all sources of sufficiently high-entropy, even if individual bits in the source are correlated.3Security is guaranteed even if an adversary has (bounded) influence on the source.Our approach is based on a related notion of “randomness extraction” which emerged in complexity theory. We stress that the statistical randomness of our extractor’s output is proven, and is not based on any unproven assumptions, such as the security of cryptographic hash functions.A sample implementation of our extractor and additional details can be found at a dedicated web page [Web].

A hardware random number generator was described at CHES 2002 in [Tka03]. In this paper, we analyze its method of generating randomness and, as a consequence of the analysis, we describe how, in principle, an attack on the generator can be executed.

Representing finite field elements with respect to the polynomial (or standard) basis, we consider a bit parallel multiplier architecture for the finite field GF(2m) . Time and space complexities of such a multiplier heavily depend on the field defining irreducible polynomials. Based on a number of important classes of irreducible polynomials, we give exact complexity analyses of the multiplier gate count and time delay. In general, our results match or outperform the previously known best results in similar classes. We also present exact formulations for the coordinates of the multiplier output. Such formulations are expected to be useful to efficiently implement the multiplier using hardware description languages, such as VHDL and Verilog, without having much knowledge of finite field arithmetic.

This paper describes a new efficient method of modular reduction in % MathType!MTEF!2!1!+- % feaagaart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepyuP0xe9Fve9 % Fve9qapdbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgznf % gDOjdaryqr1ngBPrginfgDObcv39gaiuaacqWFfcVrdaWgaaWcbaGa % amyCaaqabaaaaa!454D! $$ \mathbb{F}_q $$[x] suited for both software and hardware implementations. This method is particularly well adapted to smart card implementations of elliptic curve cryptography over GF(2p) using a polynomial representation. Many publications use the equivalent in % MathType!MTEF!2!1!+- % feaagaart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepyuP0xe9Fve9 % Fve9qapdbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgznf % gDOjdaryqr1ngBPrginfgDObcv39gaiuaacqWFfcVrdaWgaaWcbaGa % aGOmaaqabaaaaa!4513! $$ \mathbb{F}_2 $$[x] of Montgomery’s modular multiplication over integers. We show here an equivalent in % MathType!MTEF!2!1!+- % feaagaart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepyuP0xe9Fve9 % Fve9qapdbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgznf % gDOjdaryqr1ngBPrginfgDObcv39gaiuaacqWFfcVrdaWgaaWcbaGa % amyCaaqabaaaaa!454D! $$ \mathbb{F}_q $$[x] to the generalized Barrett’s modular reduction over integers. The attractive properties of the last method in % MathType!MTEF!2!1!+- % feaagaart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepyuP0xe9Fve9 % Fve9qapdbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgznf % gDOjdaryqr1ngBPrginfgDObcv39gaiuaacqWFfcVrdaWgaaWcbaGa % aGOmaaqabaaaaa!4513! $$ \mathbb{F}_2 $$[x] allow nearly ideal implementations in hardware as well as in software with minimum additional resources as compared to what is available on usual processor architecture.An implementation minimizing the memory accesses is described for both Montgomery’s implementation and ours. This shows identical computing and memory access resources for both methods. The new method also avoids the need for the bulky normalization (denormalization) which is required by Montgomery’s method to obtain a correct result.

A novel technique for computing a 2n-bit modular multiplication using n-bit arithmetic was introduced at CHES 2002 by Fischer and Seifert. Their technique makes use of an Euclidean division based instruction returning not only the remainder but also the integer quotient resulting from a modular multiplication, i.e. on input x, y and z, both ⌊xy/ z⌋ and xy mod z are returned. A second algorithm making use of a special modular ‘multiply-and-accumulate’ instruction was also proposed.In this paper, we improve on these algorithms and propose more advanced computational strategies with fewer calls to these basic operations, bringing in a speed-up factor up to 57%. Besides, when Euclidean multiplications themselves have to be emulated in software, we propose a specific modular multiplication based algorithm which surpasses original algorithms in performance by 71%.

We present a fast and compact hardware architecture of exponentiation in a finite field GF(2n) determined by a Gauss period of type (n,k) with k ≥ 2. Our construction is based on the ideas of Gao et al. and on the computational evidence that a Gauss period of type (n,k) over GF(2) is very often primitive when k ≥ 2. Also in the case of a Gauss period of type (n,1), i.e. a type I optimal normal element, we find a primitive element in GF(2n) which is a sparse polynomial of a type I optimal normal element and we propose a fast exponentiation algorithm which is applicable for both software and hardware purposes. We give an explicit hardware design using the algorithm.

This paper describes new algorithms for computing a modular inverse e− 1 given coprime integers e and f. Contrary to previously reported methods, we neither rely on the extended Euclidean algorithm, nor impose conditions on e or f. The main application of our gcd-free technique is the computation of an RSA private key in both standard and CRT modes based on simple modular arithmetic operations, thus boosting real-life implementations on crypto-accelerated devices.

Efficient implementations of RSA on computationally limited devices, such as smartcards, often use the CRT technique in combination with Garner’s algorithm in order to make the computation of modular exponentiation as fast as possible. At PKC 2001, Novak has proposed to use some information that may be obtained by simple power analysis on the execution of Garner’s algorithm to recover the factorization of the RSA modulus. The drawback of this approach is that it requires chosen messages; in the context of RSA decryption it can be realistic but if we consider RSA signature, standardized padding schemes make impossible adaptive choice of message representative.In this paper, we use the same basic idea than Novak but we focus on the use of known messages. Consequently, our attack applies to RSA signature scheme, whatever the padding may be. However, our new technique based on SPA and lattice reduction, requires a small difference, say 10 bits, between the bit lengths of modulus prime factors.

The recent developments of side channel attacks have lead implementers to use more and more sophisticated countermeasures in critical operations such as modular exponentiation, or scalar multiplication in the elliptic curve setting. In this paper, we propose a new attack against a classical implementation of these operations that only requires two queries to the device. The complexity of this so-called “doubling attack” is much smaller than previously known ones. Furthermore, this approach defeats two of the three countermeasures proposed by Coron at CHES ’99.

Power analysis attacks on elliptic curve based systems work by analysing the point multiplication algorithm. Recently Goubin observed that if an attacker can choose the point P to enter into the point multiplication algorithm then none of the standard three randomizations can fully defend against a DPA attack. In this paper we examine Goubin’s attack in more detail and completely discount its effectiveness when the attacker chooses a point of finite order, for the remaining cases we propose a defence based on using isogenies of small degree.

We investigate side-channel attacks where the attacker only needs the Hamming weights of several secret exponents to guess a long-term secret. Such weights can often be recovered by SPA, EMA, or simply timing attack. We apply this principle to propose a timing attack on the GPS identification scheme. We consider implementations of GPS where the running time of the exponentiation (commitment phase) leaks the exponent’s Hamming weight, which is typical of a square and multiply algorithm for example. We show that only 800 time measures allow the attacker to find the private key in a few seconds on a PC with a success probability of 80%. Besides its efficiency, two other interesting points in our attack are its resistance to some classical countermeasures against timing attacks, and the fact that it works whether the Chinese Remainder Technique is used or not.

We proposed unified hardware architecture for the two 128-bit block ciphers AES and Camellia, and evaluated its performance using a 0.13-μm CMOS standard cell library. S-Boxes are the biggest hardware components in block ciphers, and some times they consume more than half of the design area. The S-Boxes in AES and Camellia are the combination of affine transformations and multiplicative inversions on a Galois fields. The size of the fields is same, but their structures are different. Therefore we converted the basis between the fields by using isomorphism transformations, and shared the inverter between AES and Camellia. The affine transformations were also merged by factoring common terms. In addition to the S-Box sharing, many other components such as permutation layers and key whiting are also merged. As a result, a compact hardware of 14.9K gates with throughputs of 469 Mbps for AES and of 661 Mbps for Camellia was achieved. The hardware synthesized with speed optimization obtained throughputs of 794 Mbps and 1.12 Gbps for each algorithm with 24.4K gates.

In this paper a compact FPGA architecture for the AES algorithm with 128-bitkey targeted for low-costembedded applications is presented. Encryption, decryption and key schedule are all implemented using small resources of only 222 Slices and 3 Block RAMs. This implementation easily fits in a low-costXilinx Spartan II XC2S30 FPGA. This implementation can encrypt and decrypt data streams of 150 Mbps, which satisfies the needs of most embedded applications, including wireless communication. Specific features of Spartan II FPGAs enabling compact logic implementation are explored, and a new way of implementing MixColumnsand InvMixColumnstransformations using shared logic resources is presented.

Performance evaluation of the Advanced Encryption Standard candidates has led to intensive study of both hardware and software implementations. However, although plentiful papers present various implementation results, it seems that efficiency could still be greatly improved by applying good design rules adapted to devices and algorithms. This paper addresses various approaches for efficient FPGA implementations of the Advanced Encryption Standard algorithm. As different applications of the AES algorithm may require different speed/area tradeoffs, we propose a rigorous study of the possible implementation schemes, but also discuss design methodology and algorithmic optimization in order to improve previously reported results. We propose heuristics to evaluate hardware efficiency at different steps of the design process. We also define an optimal pipeline that takes the place and route constraints into account. Resulting circuits significantly improve previously reported results: throughput is up to 18.5 Gbits/sec and area requirements can be limited to 542 slices and 10 RAM blocks with a ratio throughput/area improved by at least 25% of the best-known designs in the Xilinx Virtex-E technology.

For most of the time since they were proposed, it was widely believed that hyperelliptic curve cryptosystems (HECC) carry a substantial performance penalty compared to elliptic curve cryptosystems (ECC) and are, thus, not too attractive for practical applications. Only quite recently improvements have been made, mainly restricted to curves of genus 2. The work at hand advances the state-of-the-art considerably in several aspects. First, we generalize and improve the closed formulae for the group operation of genus 3 for HEC defined over fields of characteristic two. For certain curves we achieve over 50% complexity improvement compared to the best previously published results. Second, we introduce a new complexity metric for ECC and HECC defined over characteristic two fields which allow performance comparisons of practical relevance. It can be shown that the HECC performance is in the range of the performance of an ECC; for specific parameters HECC can even possess a lower complexity than an ECC at the same security level. Third, we describe the first implementation of a HEC cryptosystem on an embedded (ARM7) processor. Since HEC are particularly attractive for constrained environments, such a case study should be of relevance.

In this paper we describe some countermeasures against differential side-channel attacks on hyperelliptic curve cryptosystems. The techniques are modelled on the corresponding ones for elliptic curves. The first method consists in picking a random group isomorphic to the one where we are supposed to compute, transferring the computation to the random group and then pulling the result back. The second method consists in altering the internal representation of the divisors on the curve in a random way. The impact of the recent attack of L. Goubin is assessed and ways to avoid it are proposed.

The differential power analysis (DPA) enables an adversary to reveal the secret key hidden in a smart card by observing power consumption. The address-bit DPA is a typical example of DPA which analyzes a correlation between addresses of registers and power consumption. In this paper, we propose a practical countermeasure, the randomized addressing countermeasure, against the address-bit DPA which can be applied to the exponentiation part in RSA or ECC with and without pre-computed table. Our countermeasure has almost no overhead for the protection, namely the processing speed is no slower than that without the countermeasure. We also report experimental results of the countermeasure in order to show its effect. Finally, a complete comparison of countermeasures from various view points including the processing speed and the security level is given.

Elliptic curve cryptosystem (ECC) is well-suited for the implementation on memory constraint environments due to its small key size. However, side channel attacks (SCA) can break the secret key of ECC on such devices, if the implementation method is not carefully considered. The scalar multiplication of ECC is particularly vulnerable to the SCA. In this paper we propose an SCA-resistant scalar multiplication method that is allowed to take any number of pre-computed points. The proposed scheme essentially intends to resist the simple power analysis (SPA), not the differential power analysis (DPA). Therefore it is different from the other schemes designed for resisting the DPA. The previous SPA-countermeasures based on window methods utilize the fixed pattern windows, so that they only take discrete table size. The optimal size is 2w − 1 for w=2,3,..., which was proposed by Okeya and Takagi. We play a different approach from them. The key idea is randomly (but with fixed probability) to generate two different patterns based on pre-computed points. The two distributions are indistinguishable from the view point of the SPA. The proposed probabilistic scheme provides us more flexibility for generating the pre-computed points — the designer of smart cards can freely choose the table size without restraint.

Public Key Cryptography Standards (PKCS) #11 has gained wide acceptance within the cryptographic security device community and has become the interface of choice for many applications. The high esteem in which PKCS #11 is held is evidenced by the fact that it has been selected by a large number of companies as the API for their own devices. In this paper we analyse the security of the PKCS #11 standard as an interface (e.g. an application-programming interface (API)) for a security device. We show that PKCS #11 is vulnerable to a number of known and new API attacks and exhibits a number of design weaknesses that raise questions as to its suitability for this role. Finally we present some design solutions.

In this paper we present a practically feasible attack on RSA-based sessions in SSL/TLS protocols. We show that incorporating a version number check over PKCS#1 plaintext used in the SSL/TLS creates a side channel that allows an attacker to invert the RSA encryption. The attacker can then either recover the premaster-secret or sign a message on behalf of the server. Practical tests showed that two thirds of randomly chosen Internet SSL/TLS servers were vulnerable. The attack is an extension of Bleichenbacher’s attack on PKCS#1 (v. 1.5). We introduce the concept of a bad-version oracle (BVO) that covers the side channel leakage, and present several methods that speed up the original algorithm. Our attack was successfully tested in practice and the results of complexity measurements are presented in the paper.