Cryptographic Hardware and Embedded Systems - CHES 2004

Viable cryptosystem designs must address power analysis attacks, and masking is a commonly proposed technique for defending against these side-channel attacks. It is possible to overcome simple masking by using higher-order techniques, but apparently only at some cost in terms of generality, number of required samples from the device being attacked, and computational complexity. We make progress towards ascertaining the significance of these costs by exploring a couple of attacks that attempt to efficiently employ second-order techniques to overcome masking. In particular, we consider two variants of second-order differential power analysis: Zero-Offset 2DPA and FFT 2DPA.

A classical model is used for the power consumption of cryptographic devices. It is based on the Hamming distance of the data handled with regard to an unknown but constant reference state. Once validated experimentally it allows an optimal attack to be derived called Correlation Power Analysis. It also explains the defects of former approaches such as Differential Power Analysis.

Since their publication in 1998, power analysis attacks have attracted significant attention within the cryptographic community. So far, they have been successfully applied to different kinds of (unprotected) implementations of symmetric and public-key encryption schemes. However, most published attacks apply to smart cards and only a few publications assess the vulnerability of hardware implementations. In this paper we investigate the vulnerability of Rijndael FPGA (Field Programmable Gate Array) implementations to power analysis attacks. The design used to carry out the experiments is an optimized architecture with high clock frequencies, presented at CHES 2003. First, we provide a clear discussion of the hypothesis used to mount the attack. Then, we propose theoretical predictions of the attacks that we confirmed experimentally, which are the first successful experiments against an FPGA implementation of Rijndael. In addition, we evaluate the effect of pipelining and unrolling techniques in terms of resistance against power analysis. We also emphasize how the efficiency of the attack significantly depends on the knowledge of the design.

A digit-serial, multiplier-accumulator based cryptographic co-processor architecture is proposed, similar to fix-point DSP’s with enhancements, supporting long modular arithmetic and general computations. Several new “column-sum” variants of popular quadratic time modular multiplication algorithms are presented (Montgomery and interleaved division-reduction with or without Quisquater scaling), which are faster than the traditional implementations, need no or very little memory beyond the operand storage and perform squaring about twice faster than general multiplications or modular reductions. They provide similar advantages in software for general purpose CPU’s.

In this paper we show how the usage of Residue Number Systems (RNS) can easily be turned into a natural defense against many side-channel attacks (SCA). We introduce a Leak Resistant Arithmetic (LRA), and present its capacities to defeat timing, power (SPA, DPA) and electromagnetic (EMA) attacks.

We present a new sequential normal basis multiplier over GF(2m). The gate complexity of our multiplier is significantly reduced from that of Agnew et al. and is comparable to that of Reyhani-Masoleh and Hasan, which is the lowest complexity normal basis multiplier of the same kinds. On the other hand, the critical path delay of our multiplier is same to that of Agnew et al. Therefore it is supposed to have a shorter or the same critical path delay to that of Reyhani-Masoleh and Hasan. Moreover our method of using a Gaussian normal basis makes it easy to find a basic multiplication table of normal elements. So one can easily construct a circuit array for large finite fields, GF(2m) where m=163,233,283,409,571, i.e. the five recommended fields by NIST for elliptic curve cryptography.

We introduce new modulus scaling techniques for transforming a class of primes into special forms which enables efficient arithmetic. The scaling technique may be used to improve multiplication and inversion in finite fields. We present an efficient inversion algorithm that utilizes the structure of scaled modulus. Our inversion algorithm exhibits superior performance to the Euclidean algorithm and lends itself to efficient hardware implementation due to its simplicity. Using the scaled modulus technique and our specialized inversion algorithm we develop an elliptic curve processor architecture. The resulting architecture successfully utilizes redundant representation of elements in GF(p) and provides a low-power, high speed, and small footprint specialized elliptic curve implementation.

In this article we present a low-cost coprocessor for smartcards which supports all necessary mathematical operations for a fast calculation of the Elliptic Curve Digital Signature Algorithm (ECDSA) based on the finite field GF(2m). These ECDSA operations are GF(2m) addition, 4-bit digit-serial multiplication in GF(2m), inversion in GF(2m), and inversion in GF(p). An efficient implementation of the multiplicative inversion which breaks the 11:1 limit regarding multiplications makes it possible to use affine instead of projective coordinates for point operations on elliptic curves. A bitslice architecture allows an easy adaptation for different bit lengths. A small chip area is achieved by reusing the hardware registers for different operations.

Strong public-key cryptography is often considered to be too computationally expensive for small devices if not accelerated by cryptographic hardware. We revisited this statement and implemented elliptic curve point multiplication for 160-bit, 192-bit, and 224-bit NIST/SECG curves over GF(p) and RSA-1024 and RSA-2048 on two 8-bit microcontrollers. To accelerate multiple-precision multiplication, we propose a new algorithm to reduce the number of memory accesses.Implementation and analysis led to three observations: 1. Public-key cryptography is viable on small devices without hardware acceleration. On an Atmel ATmega128 at 8 MHz we measured 0.81s for 160-bit ECC point multiplication and 0.43s for a RSA-1024 operation with exponent e=216+1. 2. The relative performance advantage of ECC point multiplication over RSA modular exponentiation increases with the decrease in processor word size and the increase in key size. 3. Elliptic curves over fields using pseudo-Mersenne primes as standardized by NIST and SECG allow for high performance implementations and show no performance disadvantage over optimal extension fields or prime fields selected specifically for a particular processor architecture.

Instruction set extensions are a small number of custom instructions specifically designed to accelerate the processing of a given kind of workload such as multimedia or cryptography. Enhancing a general-purpose RISC processor with a few application-specific instructions to facilitate the inner loop operations of public-key cryptosystems can result in a significant performance gain. In this paper we introduce a set of five custom instructions to accelerate arithmetic operations in finite fields GF(p) and GF(2m). The custom instructions can be easily integrated into a standard RISC architecture like MIPS32 and require only little extra hardware. Our experimental results show that an extended MIPS32 core is able to perform an elliptic curve scalar multiplication over a 192-bit prime field in 36 msec, assuming a clock speed of 33 MHz. An elliptic curve scalar multiplication over the binary field GF(2191) takes only 21 msec, which is approximately six times faster than a software implementation on a standard MIPS32 processor.

We present an implementation of elliptic curves and of hyperelliptic curves of genus 2 and 3 over prime fields. To achieve a fair comparison between the different types of groups, we developed an ad-hoc arithmetic library, designed to remove most of the overheads that penalize implementations of curve-based cryptography over prime fields. These overheads get worse for smaller fields, and thus for larger genera for a fixed group size. We also use techniques for delaying modular reductions to reduce the amount of modular reductions in the formulae for the group operations.The result is that the performance of hyperelliptic curves of genus 2 over prime fields is much closer to the performance of elliptic curves than previously thought. For groups of 192 and 256 bits the difference is about 14% and 15% respectively.

Recently a new class of collision attacks which was originally suggested by Hans Dobbertin has been introduced. These attacks use side channel analysis to detect internal collisions and are generally not restricted to a particular cryptographic algorithm. As an example, a collision attack against DES was proposed which combines internal collisions with side channel information leakage. It had not been obvious, however, how this attack applies to non-Feistel ciphers with bijective S-boxes such as the Advanced Encryption Standard (AES). This contribution takes the same basic ideas and develops new optimized attacks against AES. Our major finding is that the new combined analytical and side channel approach reduces the attack effort compared to all other known side channel attacks. We develop several versions and refinements of the attack. First we show that key dependent collisions can be caused in the output bytes of the mix column transformation in the first round. By taking advantage of the birthday paradox, it is possible to cause a collision in an output with as little as 20 measurements. If a SPA leak is present from which collisions can be determined with certainty, then each collision will reveal at least 8 bits of the secret key. Furthermore, in an optimized attack, it is possible to cause collisions in all four output bytes of the mix column transformation with an average of only 31 measurements, which results in knowledge of all 32 key bits. Finally, if collisions are caused in all four columns of the AES in parallel, it is possible to determine the entire 128-bit key with only 40 measurements, which a is a distinct improvement compared to DPA and other side channel attacks.

Side Channel Attacks (SCA) have received a huge interest in the last 5 years. These new methods consider non-cryptographic sources of information (like timing or power consumption) in addition to traditional techniques. Consequently block ciphers must now resist a variety of SCAs, among which figures the class of “collision attacks”. This recent technique combines side channel information with tools originally developed for block cipher or hash function cryptanalysis, like differential cryptanalysis for instance.In this paper, we propose techniques to enhance collision attacks. First we describe a general framework for collision attacks against Feistel ciphers that extends and improves on previous results specifically obtained against DES. Then, we describe an improved method to attack DES using “almost collisions”. Indeed we observed that taking into account internal states which are abnormally similar results in more efficient attacks. Some experimental results obtained against a DES implementation are finally presented.

Classical formulae for point additions and point doublings on elliptic curves differ. This can make a side channel attack possible on a single ECC point multiplication by using simple power analysis (SPA) to observe the different times for the component point operations. Under the usual binary exponentiation algorithm, the deduced presence or absence of a point addition indicates a 1 or 0 respectively in the secret key, thus revealing the key in its entirety. Several authors have produced unified code for these operations in order to avoid this weakness. Although timing differences are thereby eliminated from this code level, it is shown that SPA attacks may still be possible on selected single point multiplications if there is sufficient side channel leakage at lower levels. Here a conditional subtraction in Montgomery modular multiplication (MMM) is assumed to give such leakage, but other modular multipliers may be equally susceptible to attack. The techniques are applicable to a single decryption or signature even under prior blinding of both the input text and the secret key. This means that one should use a constant time implementation of MMM even if the secret key is blinded or replaced every time, and all side channel leakage should be minimised, whatever multiplier is used.

Differential Power Analysis (DPA) has turned out to be an efficient method to attack the implementations of cryptographic algorithms and has been well studied for ciphers that incorporate a nonlinear substitution box as e.g. in DES. Other product ciphers and message authentication codes are based on the mixing of different algebraic groups and do not use look-up tables. Among these are IDEA, the AES finalist RC6 and HMAC-constructions such as HMAC-SHA-1 and HMAC-RIPEMD-160. These algorithms restrict the use of the selection function to the Hamming weight and Hamming distance of intermediate data as the addresses used do not depend on cryptographic keys. Because of the linearity of the primitive operations secondary DPA signals arise. This article gives a deeper analysis of the characteristics of DPA results obtained on the basic group operations XOR, addition modulo 2n and modular multiplication using multi-bit selection functions. The results shown are based both on simulation and experimental data. Experimental results are included for an AVR ATM163 microcontroller which demonstrate the application of DPA to an IDEA implementation.

Side-channel attacks in elliptic curve cryptography occur with the unintentional leakage of information during processing. A critical operation is that of computing nP where n is a positive integer and P is a point on the elliptic curve E. Implementations of the binary algorithm may reveal whether P+Q is computed for $P\ne Q$ or P=Q as the case may be. Several methods of dealing with this problem have been suggested. Here we describe a general technique for producing a large number of different representations of the points on E in characteristic p≥ 5, all having a uniform implementation of P+Q. The parametrization may be changed for each computation of nP at essentially no cost. It is applicable to all elliptic curves in characteristic p≥ 5, and thus may be used with all curves included in present and future standards for p≥ 5.

Cryptographic algorithms implemented on smart-cards must be protected against side-channel attacks. Some encryption schemes and hash functions like IDEA, RC6, MD5, SHA-1 alternate various arithmetic and boolean operations, each of them requiring a different kind of blinding. Hence the maskings have to be changed frequently. How to switch reasonably between standard arithmetic masking and boolean masking was shown in [2], [3], [5] and [9].In this paper we propose more space-efficient table-based conversion methods. Furthermore, we deal with some non-standard arithmetic operations, namely arithmetic modulo 2k+1 for some k ∈ IN and a special multiplication used by IDEA.

A fault attack is a powerful cryptanalytic tool which can be applied to many types of cryptosystems which are not vulnerable to direct attacks. The research literature contains many examples of fault attacks on public key cryptosystems and block ciphers, but surprisingly we could not find any systematic study of the applicability of fault attacks to stream ciphers. Our goal in this paper is to develop general techniques which can be used to attack the standard constructions of stream ciphers based on LFSR’s, as well as more specialized techniques which can be used against specific stream ciphers such as RC4, LILI-128 and SOBER-t32. While most of the schemes can be successfully attacked, we point out several interesting open problems such as an attack on FSM filtered constructions and the analysis of high Hamming weight faults in LFSR’s.

Previously proposed differential fault analysis (DFA) techniques against iterated block ciphers mostly exploit computational errors in the last few rounds of the cipher to extract the secret key. In this paper we describe a DFA attack that exploits computational errors in early rounds of a Feistel cipher. The principle of the attack is to force collisions by inducing faults in intermediate results of the cipher. We put this attack into practice against DES implemented on a smart card and extracted the full round key of the first round within a few hours by inducing one bit errors in the second and third round, respectively.

In this paper, a new, patent pending, architecture for a jitter-based random bit source which is cost-effective and suitable for applications in cryptography, is presented. The source is designed to be robust against parameter variations and attacks aimed to force its output. It also features an auto-test which allows to detect faults and to estimate the source entropy. The proposed design is an enhancement of the oscillator-based architecture where a compensation loop is added to maximize the statistical quality of the output sequence, especially in presence of low-jittered oscillators. As a consequence, a fully-digital implementation, without any amplified noise source, can be adopted for the proposed generator. From an analysis of the known techniques for random number generation, the proposed architecture is derived and implementation details are also reported.

Dual-rail encoding, return-to-spacer protocol and hazard-free logic can be used to resist differential power analysis attacks by making the power consumption independent of processed data. Standard dual-rail logic uses a protocol with a single spacer, e.g. all-zeroes, which gives rise to power balancing problems. We address these problems by incorporating two spacers; the spacers alternate between adjacent clock cycles. This guarantees that all gates switch in each clock cycle regardless of the transmitted data values. To generate these dual-rail circuits an automated tool has been developed. It is capable of converting synchronous netlists into dual-rail circuits and it is interfaced to industry CAD tools. Dual-rail and single-rail benchmarks based upon the Advanced Encryption Standard (AES) have been simulated and compared in order to evaluate the method.

In this paper we propose a new side channel attack, where exponent recodings for public key cryptosystems such as RSA and ECDSA are considered. The known side channel attacks and countermeasures for public key cryptosystems were against the main stage (square and multiply stage) of the modular exponentiation (or the point multiplication on an elliptic curve). We have many algorithms which achieve fast computation of exponentiations. When we compute an exponentiation, the exponent recoding has to be carried out before the main stage. There are some exponent recoding algorithms including conditional branches, in which instructions depend on the given exponent value. Consequently exponent recoding can constitute an information channel, providing the attacker with valuable information on the secret exponent. In this paper we show new algorithms of attack on exponent recoding. The proposed algorithms can recover the secret exponent, when the width-w NAF [9] and the unsigned/signed fractional window representation [5] are used.

The recent development of side channel attacks has lead implementers to use increasingly sophisticated countermeasures in critical operations such as modular exponentiation, or scalar multiplication on elliptic curves. A new class of countermeasures is based on inserting random decisions when choosing one representation of the secret scalar out of a large set of representations of the same value. For instance, this is the case of countermeasures proposed by Oswald and Aigner, or Ha and Moon, both based on randomized Binary Signed Digit (BSD) representations. Their advantage is to offer excellent speed performances. However, the first countermeasure and a simplified version of the second one were already broken using Markov chain analysis.In this paper, we take a different approach to break the full version of Ha-Moon’s countermeasure using a novel technique based on detecting local collisions in the intermediate states of computation. We also show that randomized BSD representations present some fundamental problems and thus recommend not to use them as a protection against side-channel attacks.

In the current work we propose a pipelining scheme for implementing Elliptic Curve Cryptosystems (ECC). The scalar multiplication is the dominant operation in ECC. It is computed by a series of point additions and doublings. The pipelining scheme is based on a key observation: to start the subsequent operation one need not wait until the current one exits. The next operation can begin while a part of the current operation is still being processed. To our knowledge, this is the first attempt to compute the scalar multiplication in such a pipelined method. Also, the proposed scheme can be made resistant to side-channel attacks (SCA). Our scheme compares favourably to all SCA resistant sequential and parallel methods.

In the execution on a smart card, side channel attacks such as simple power analysis (SPA) and the differential power analysis (DPA) have become serious threat [15]. Side channel attacks monitor power consumption and even exploit the leakage information related to power consumption to reveal bits of a secret key d although d is hidden inside a smart card. Almost public key cryptosystems including RSA, DLP-based cryptosystems, and elliptic curve cryptosystems execute an exponentiation algorithm with a secret-key exponent, and they thus suffer from both SPA and DPA. Recently, in the case of elliptic curve cryptosystems, DPA is improved to the Refined Power Analysis (RPA), which exploits a special point with a zero value and reveals a secret key [10]. RPA is further generalized to Zero-value Point Attack (ZPA) [2]. Both RPA and ZPA utilizes a special feature of elliptic curves that happens to have a special point or a register used in addition and doubling formulae with a zero value and that the power consumption of 0 is distinguishable from that of an non-zero element. To make the matters worse, some previous efficient countermeasures are neither resistant against RPA nor ZPA. Although a countermeasure to RPA is proposed, this is not universal countermeasure, gives each different method to each type of elliptic curves, and is still vulnerable against ZPA [30]. The possible countermeasures are ES [3] and the improved version [4]. This paper focuses on countermeasures against RPA, ZPA, DPA and SPA. We show a novel countermeasure resistant against RPA, ZPA, SPA and DPA without any pre-computed table. We also generalize the countermeasure to present more efficient algorithm with a pre-computed table.

Radio frequency identification (RFID) is an emerging technology which brings enormous productivity benefits in applications where objects have to be identified automatically. This paper presents issues concerning security and privacy of RFID systems which are heavily discussed in public. In contrast to the RFID community, which claims that cryptographic components are too costly for RFID tags, we describe a solution using strong symmetric authentication which is suitable for today’s requirements regarding low power consumption and low die-size. We introduce an authentication protocol which serves as a proof of concept for authenticating an RFID tag to a reader device using the Advanced Encryption Standard (AES) as cryptographic primitive. The main part of this work is a novel approach of an AES hardware implementation which encrypts a 128-bit block of data within 1000 clock cycles and has a power consumption below 9 μA on a 0.35 μm CMOS process.

TTS is a genre of multivariate digital signature schemes first proposed in 2002. Its public map is composed of two affine maps sandwiching a Tame Map, which is a map invertible through serial substitution and solving linear equations. We implement the signing and key generation operations for a TTS instance with 20-byte hashes and 28-byte signatures, on popular extant microcontroller cores compatible to the Intel 8051. Our tests demonstrates that TTS can be even faster than SFLASHv2, which is known for its celerity. The sample scheme TTS(20,28) is fast enough for practical deployment on a low-end 8051-based embedded device. A really low-end part like a stock Intel 8051AH running at 3.57 MHz can sign in just 170ms. A better 8051-compatible chip will take a lot less time.Security requirements today demand on-card key generation, and the big public keys of a multivariate PKC create a storage problem. TTS is unusual in that public keys can be synthesized on-card at a decent pace for block-by-block output, using some minimal information kept on-card. Since this does not take much more time than the I/O needed to transmit the public key to a reader, we can avoid holding the entire public key in the limited memory of a smart card. We show that this to be a gain for multivariate PKC’s with relatively few terms per central equation. The literature is not rich in this kind of detailed description of an implementation of a signature scheme — capable of fast on-card public key generation, on a low-cost smart card without a co-processor, and at NESSIE-approved security levels.We look into other theory issues like safeguarding against side-channel attacks, and using unusual techniques for linear algebra under serious space restrictions, which may help implementations of other multivariate PKC’s such as SFLASH.

Recently, Lenstra and Verheul proposed an efficient cryptosystem called XTR. This system represents elements of $F_{p^6}^*$ with order dividing p2–p+1 by their trace over $F_{p^2}$. Compared with the usual representation, this one achieves a ratio of three between security size and manipulated data. Consequently very promising performance compared with RSA and ECC are expected.In this paper, we are dealing with hardware implementation of XTR, and more precisely with Field Programmable Gate Array (FPGA). The intrinsic parallelism of such a device is combined with efficient modular multiplication algorithms to obtain effective implementation(s) of XTR with respect to time and area.We also compare our implementations with hardware implementations of RSA and ECC. This shows that XTR achieves a very high level of speed with small area requirements: an XTR exponentiation is carried out in less than 0.21 ms at a frequency beyond 150 MHz.

Because of the rapidly shrinking dimensions in VLSI, transient and permanent faults arise and will continue to occur in the near future in increasing numbers. Since cryptographic chips are a consumer product produced in large quantities, cheap solutions for concurrent checking are needed. Concurrent Error Detection (CED) for cryptographic chips also has a great potential for detecting (deliberate) fault injection attacks where faults are injected into a cryptographic chip to break the key. In this paper we propose a low cost, low latency, time redundancy based CED technique for a class of symmetric block ciphers whose round functions are involutions. This CED technique can detect both permanent and transient faults with almost no time overhead. A function F is an involution if F(F(x))=x. The proposed CED architecture (i) exploits the involution property of the ciphers and checks if x=F(F(x)) for each of the involutional round functions to detect transient and permanent faults and (ii) uses the idle cycles in the design to achieve close to a 0% time overhead. Our preliminary ASIC synthesis experiment with the involutional cipher KHAZAD resulted in an area overhead of 23.8% and a throughput degradation of 8%. A fault injection based simulation shows that the proposed architecture detects all single-bit faults.

We focus on the GPS identification scheme implementation in low cost chips, i.e not equipped with a microprocessor (such as those embedded in some prepaid telephone cards or RFID tags). We present three solutions to decrease the overall number of manipulated bits during the computation of the answer by a factor two or three. All the solutions stand in the use of low Hamming weight parameters. The first one consists in building the private key as the product of low Hamming weight sub-keys. The second one suggests the choice of full size low Hamming weight private keys. Finally, the third solution corresponds to a variant of the basic GPS scheme in which large challenges with low Hamming weight are used. Whereas the first solution does not withdraw the need for a multiplier in the chip, the two other ones are ideally suited to low cost chips as they can be implemented with only one serial addition. Therefore, as a surprising result, one entity can be public key authenticated by doing one on-line addition only at the time of authentication!

We discuss how to recover the private key for DSA style signature schemes if partial information about the ephemeral keys is revealed. The partial information we examine is of a second order nature that allows the attacker to know whether certain bits of the ephemeral key are equal, without actually knowing their values. Therefore, we extend the work of Howgrave-Graham, Smart, Nguyen and Shparlinski who, in contrast, examine the case where the attacker knows the actual value of such bits. We also discuss how such partial information leakage could occur in a real life scenario. Indeed, the type of leakage envisaged by our attack would appear to be feasible than that considered in the prior work.

This paper presents the theoretical blueprint of a new secure token called the Externalized Microprocessor (XμP). Unlike a smart-card, the XμP contains no ROM at all.While exporting all the device’s executable code to potentially untrustworthy terminals poses formidable security problems, the advantages of ROM-less secure tokens are numerous: chip masking time disappears, bug patching becomes a mere terminal update and hence does not imply any roll-out of cards in the field. Most importantly, code size ceases to be a limiting factor. This is particularly significant given the steady increase in on-board software complexity.After describing the machine’s instruction-set we introduce a public-key oriented architecture design which relies on a new RSA screening scheme and features a relatively low communication overhead. We propose two protocols that execute and dynamically authenticate arbitrary programs, provide a strong security model for these protocols and prove their security under appropriate complexity assumptions.