Cryptographic Hardware and Embedded Systems – CHES 2008

At CHES 2006, a DPA countermeasure based on the Fourier Transform was published. This generic countermeasure aims at protecting from DPA any S-box calculation used in symmetric cryptosystems implementations. In this paper, we show that this countermeasure has a flaw and that it can be broken by first order DPA. Moreover, we have successfully put into practice our attack on two different S-box implementations. Finally, we propose an improvement of the original countermeasure and we prove its security against first order DPA.

When applied to AES, MDCA using binary voting without profiling requires about 2.7 to 13.2 times less traces than the Hamming-weight based CPA for the same implementation. MDCA on AES using ternary voting with profiling and linear key recovery clearly outperforms CPA by requiring only about 6 online measurements for the range of noise amplitudes where CPA requires from 163 to 6912 measurements. These attacks do not need the S-box to be known. Moreover, neither key nor plaintexts have to be known to the attacker in the profiling stage.

In this paper ways to efficiently implement public-key schemes based on ultivariate uadratic polynomials (\(\mathcal{MQ}\)-schemes for short) are investigated. In particular, they are claimed to resist quantum computer attacks. It is shown that such schemes can have a much better time-area product than elliptic curve cryptosystems. For instance, an optimised FPGA implementation of amended TTS is estimated to be over 50 times more efficient with respect to this parameter. Moreover, a general framework for implementing small-field \(\mathcal{MQ}\)-schemes in hardware is proposed which includes a systolic architecture performing Gaussian elimination over composite binary fields.

Elliptic Curve Cryptosystems (ECC) have gained increasing acceptance in practice due to their significantly smaller bit size of the operands compared to other public-key cryptosystems. Since their computational complexity is often lower than in the case of RSA or discrete logarithm schemes, ECC are often chosen for high performance public-key applications. However, despite a wealth of research regarding high-speed software and high-speed FPGA implementation of ECC since the mid 1990s, providing truly high-performance ECC on readily available (i.e., non-ASIC) platforms remains an open challenge. This holds especially for ECC over prime fields, which are often preferred over binary fields due to standards in Europe and the US.

This work presents a new architecture for an FPGA-based ultra high performance ECC implementation over prime fields. Our architecture makes intensive use of the DSP blocks in modern FPGAs, which are embedded arithmetic units actually intended to accelerate digital signal processing algorithms. We describe a novel architecture and algorithms for performing ECC arithmetic and describe the actual implementation of standard compliant ECC based on the NIST primes P-224 and P-256. We show that ECC on Xilinx’s Virtex-4 SX55 FPGA can be performed at a rate of more than 37,000 point multiplications per second. Our architecture outperforms all single-chip hardware implementations over prime fields in the open literature by a wide margin.

Modern Graphics Processing Units (GPU) have reached a dimension with respect to performance and gate count exceeding conventional Central Processing Units (CPU) by far. Many modern computer systems include – beside a CPU – such a powerful GPU which runs idle most of the time and might be used as cheap and instantly available co-processor for general purpose applications.

In this contribution, we focus on the efficient realisation of the computationally expensive operations in asymmetric cryptosystems on such off-the-shelf GPUs. More precisely, we present improved and novel implementations employing GPUs as accelerator for RSA and DSA cryptosystems as well as for Elliptic Curve Cryptography (ECC). Using a recent Nvidia 8800GTS graphics card, we are able to compute 813 modular exponentiations per second for RSA or DSA-based systems with 1024 bit integers. Moreover, our design for ECC over the prime field P-224 even achieves the throughput of 1412 point multiplications per second.

This paper proposes an efficient concurrent error detection scheme for hardware implementation of the block cipher AES. The proposed scheme does not require an additional arithmetic unit, but simply divides the round function block into two sub-blocks and uses the sub-blocks alternately for encryption (or decryption) and error detection. The number of clock cycles is doubled, but the maximum operating frequency is increased owing to the shortened critical path of the sub-block. Therefore, the proposed scheme has a limited impact on hardware performance with respect to size and speed. AES hardware with the proposed scheme was designed and synthesized using a 90-nm CMOS standard cell library with size and speed optimization options. The compact and high-speed implementations achieved performances of 2.21 Gbps @ 16.1 Kgates and 3.21 Gbps @ 24.1 Kgates, respectively. In contrast, the performances of AES hardware without error detection were 1.66 Gbps @ 12.9 Kgates for the compact version and 4.22 Gbps @ 30.7 Kgates for the high-speed version. There is only a slight difference between the performances with and without error detection. The performance overhead caused by the error detection is evaluated at the optimal balance between size and speed and was estimated to be 14.5% at maximum. Conversely, the AES hardware with the proposed scheme had better performance in some cases. If pipeline operation is allowed, as in the CTR mode, throughputs can easily be boosted by further dividing the sub-blocks. Although the proposed error detection scheme was applied to AES in the present study, it can also be applied to other algorithms efficiently.

The use of an appropriate fault detection scheme for hardware implementation of the Advanced Encryption Standard (AES) makes the standard robust to the internal defects and fault attacks. To minimize the overhead cost of the fault detection AES structure, we present a lightweight concurrent fault detection scheme for the composite field realization of the S-box using normal basis. The structure of the S-box is divided into blocks and the predicted parities of these blocks are obtained. Through an exhaustive search among all available composite fields and transformation matrices that map the polynomial basis representation in binary field to the normal basis representation in composite field, we have found the optimum solution for the least overhead S-box and its parity predictions. Finally, using FPGA implementations, the complexities of the proposed schemes are compared to those of the previously reported ones. It is shown that the FPGA implementations of the S-box using normal basis representation in composite fields outperform the traditional ones using polynomial basis for both with and without fault detection capability.

Fault attacks as introduced by Bellcore in 1996 are still a major threat toward cryptographic products supporting RSA signatures. Most often on embedded devices, the public exponent is unknown, turning resistance to fault attacks into an intricate problem. Over the past few years, several techniques for secure implementations have been published, all of which suffering from inadequacy with the constraints faced by embedded platforms. In this paper, we introduce a novel countermeasure mechanism against fault attacks in RSA signature generation. In the restricted context of security devices where execution time, memory consumption, personalization management and code size are strong constraints, our countermeasure is simply applicable with a low computational complexity. Our method extends to all cryptosystems based on modular exponentiation.

We briefly address general aspects that reliable security evaluations of physical RNGs should consider. Then we discuss an efficient RNG design that is based on a pair of noisy diodes. The main contribution of this paper is the formulation and the analysis of the corresponding stochastic model which interestingly also fits to other RNG designs. We prove a theorem that provides tight lower bounds for the entropy per random bit, and we apply our results to a prototype of a particular physical RNG.

In this paper, a new true random number generator (TRNG), based entirely on digital components is proposed. The design has been implemented using a fast random number generation method, which is dependent on a new type of ring oscillator with the ability to be set in metastable mode. Earlier methods of random number generation involved employment of jitter, whereas the proposed method leverages the metastability phenomenon in digital circuits and applies it to a ring oscillator. The new entropy employment method allows an increase in the TRNG throughput by significantly reducing the required entropy accumulating time. Samples obtained from simulation of TRNG design have been evaluated using AIS.31 and FIPS 140-1/2 statistical tests. The results of these tests have proven the high quality of generated data. Corners analysis of the TRNG design was also performed to estimate the robustness to technology process and environment variations. Investigated in FPGA technology, phase distribution highlighted the advantages of the proposed method over traditional architectures.

Physical Unclonable Functions (PUFs) have properties that make them very attractive for a variety of security-related applications. Due to their inherent dependency on the physical properties of the device that contains them, they can be used to uniquely bind an application to a particular device for the purpose of IP protection. This is crucial for the protection of FPGA applications against illegal copying and distribution. In order to exploit the physical nature of PUFs for reliable cryptography a so-called helper data algorithm or fuzzy extractor is used to generate cryptographic keys with appropriate entropy from noisy and non-uniform random PUF responses. In this paper we present for the first time efficient implementations of fuzzy extractors on FPGAs where the efficiency is measured in terms of required hardware resources. This fills the gap of the missing building block for a full FPGA IP protection solution. Moreover, in this context we propose new architectures for the decoders of Reed-Muller and Golay codes, and show that our solutions are very attractive from both the area and error correction capability points of view.

Here, we show that even though the binary exponentiation, or the scalar product on elliptic curves implementation, does not leak information on the secret key, the computation of the randomized secret exponent, or scalar, can leak useful information for an attacker. Such part of the algorithm can be not well-protected since its goal is to avoid attack during the exponentiation. Consequently, our attack can be mounted against any kind of exponentiation, even very resistant as soon as the exponent randomization countermeasure is used. We target an ℓ-bit adder which adds ℓ-bit words of the secret exponent and of a random value. We show that if the carry leaks during the addition, then we can almost learn the high order bits of each word of the secret exponent. Finally, such information can be then used to recover the entire secret key of RSA or ECC based cryptosystems.

Secret key recovery from weak side channel leakage is always a challenge in the presence of standard counter-measures. The use of randomised exponent recodings in RSA or ECC means that, over multiple re-uses of a key, operations which correspond to a given key bit are not aligned in the traces. This enhances the difficulties because traces cannot be averaged to improve the signal-to-noise ratio.

In order to protect software implementations of secret-key cryptographic primitives against side channel attacks, a software developer has only a limited choice of countermeasures. A combination of masking and randomization of operations in time promises good protection and can be realized without too much overhead. Recently, new advanced DPA methods have been proposed to attack software implementations with such kind of protection. In this work, we have applied these methods successfully to break a protected AES software implementation on a programmable smart card. Thus, we were able to verify the practicality of the new attacks and to estimate their effectiveness in comparison to traditional DPA attacks on unprotected implementations. In the course of our work, we have also refined and improved the original attacks, so that they can be mounted more efficiently. Our practical results indicate that the effort required for attacking the protected implementation with the examined methods is more than two orders of magnitude higher compared to an attack on an unprotected implementation.

This paper presents a new shape for ordinary elliptic curves over fields of characteristic 2. Using the new shape, this paper presents the first complete addition formulas for binary elliptic curves, i.e., addition formulas that work for all pairs of input points, with no exceptional cases. If n ≥ 3 then the complete curves cover all isomorphism classes of ordinary elliptic curves over .

This paper also presents dedicated doubling formulas for these curves using 2M + 6S + 3D, where M is the cost of a field multiplication, S is the cost of a field squaring, and D is the cost of multiplying by a curve parameter. These doubling formulas are also the first complete doubling formulas in the literature, with no exceptions for the neutral element, points of order 2, etc.

Finally, this paper presents complete formulas for differential addition, i.e., addition of points with known difference. A differential addition and doubling, the basic step in a Montgomery ladder, uses 5M + 4S + 2D when the known difference is given in affine form.

In this paper we present a real-world hardware-assisted attack on the well-known A5/1 stream cipher which is (still) used to secure GSM communication in most countries all over the world. During the last ten years A5/1 has been intensively analyzed [1,2,3,4,5,6,7]. However, most of the proposed attacks are just of theoretical interest since they lack from practicability — due to strong preconditions, high computational demands and/or huge storage requirements — or have never been fully implemented.

In contrast to these attacks, our attack which is based on the work by Keller and Seitz [8] is running on an existing special-purpose hardware device, called COPACOBANA [9]. With the knowledge of only 64 bits of keystream the machine is able to reveal the corresponding internal 64-bit state of the cipher in about 6 hours on average. We provide a detailed description of our attack architecture as well as implementation results.

The security challenges posed by RFID-tag deployments are well-known. In response there is a rich literature on new cryptographic protocols and an on-tag hash function is often assumed by protocol designers. Yet cheap tags pose severe implementation challenges and it is far from clear that a suitable hash function even exists. In this paper we consider the options available, including constructions based around compact block ciphers. While we describe the most compact hash functions available today, our work serves to highlight the difficulties in designing lightweight hash functions and (echoing [17]) we urge caution when routinely appealing to a hash function in an RFID-tag protocol.

Multiplication is the main finite field arithmetic operation in elliptic curve cryptography and its bit-serial hardware implementation is attractive in resource constrained environments such as smart cards, where the chip area is limited. In this paper, a new serial-output bit-serial multiplier using polynomial bases over binary extension fields is proposed. It generates a bit of the multiplication in each clock cycle with the latency of one cycle. To the best of our knowledge, this is the first time that such a serial-output bit-serial multiplier architecture using polynomial bases for general irreducible polynomials is proposed.

Bit-slicing is a non-conventional implementation technique for cryptographic software where an n-bit processor is considered as a collection of n 1-bit execution units operating in SIMD mode. Particularly when implementing symmetric ciphers, the bit-slicing approach has several advantages over more conventional alternatives: it often allows one to reduce memory footprint by eliminating large look-up tables, and it permits more predictable performance characteristics that can foil time based side-channel attacks. Both features are attractive for mobile and embedded processors, but the performance overhead that results from bit-sliced implementation often represents a significant disadvantage. In this paper we describe a set of light-weight Instruction Set Extensions (ISEs) that can improve said performance while retaining all advantages of bit-sliced implementation. Contrary to other crypto-ISE, our design is generic and allows for a high degree of algorithm agility: we demonstrate applicability to several well-known cryptographic primitives including four block ciphers (DES, Serpent, AES, and PRESENT), a hash function (SHA-1), as well as multiplication of ternary polynomials.

Dynamically reconfigurable systems are known to have many advantages such as area and power reduction. The drawbacks of these systems are the reconfiguration delay and the overhead needed to provide reconfigurability. We show that dynamic reconfiguration can also improve the resistance of cryptographic systems against physical attacks. First, we demonstrate how dynamic reconfiguration can realize a range of countermeasures which are standard for software implementations and that were practically not portable to hardware so far. Second, we introduce a new class of countermeasure that, to the best of our knowledge, has not been considered so far. This type of countermeasure provides increased resistance, in particular against fault attacks, by randomly changing the physical location of functional blocks on the chip area at run-time. Third, we show how fault detection can be provided on certain devices with negligible area-overhead. The partial bitstreams can be read back from the reconfigurable areas and compared to a reference version at run-time and inside the device. For each countermeasure, we propose a prototype architecture and evaluate the cost and security level it provides. All proposed countermeasures do not change the device’s input-output behavior, thus they are transparent to upper-level protocols. Moreover, they can be implemented jointly and complemented by other countermeasures on algorithm-, circuit-, and gate-level.

Radio Frequency Identification (RFID) is a rapidly upcoming technology that has become more and more important also in security-related applications. In this article, we discuss the impact of faults on this kind of devices. We have analyzed conventional passive RFID tags from different vendors operating in the High Frequency (HF) and Ultra-High Frequency (UHF) band. First, we consider faults that have been enforced globally affecting the entire RFID chip. We have induced faults caused by temporarily antenna tearing, electromagnetic interferences, and optical inductions. Second, we consider faults that have been caused locally using a focused laser beam. Our experiments have led us to the result that RFID tags are exceedingly vulnerable to faults during the writing of data that is stored into the internal memory. We show that it is possible to prevent the writing of this data as well as to allow the writing of faulty values. In both cases, tags confirm the operation to be successful. We conclude that fault analysis poses a serious threat in this context and has to be considered if cryptographic primitives are embedded into low-cost RFID tags.

We describe here a new fault attack on RSA public elements. Under a very natural fault model, we show that our attack is more efficient than previously published ones. Moreover, the general strategy described here can be applied using multiple transient fault models, increasing the practicability of the attack.

Both the theoretical analysis of the success probability, and the experimental results – obtained with the GMP Library on a PC –, provide evidence that this is a real threat for all RSA implementations, and confirm the need for protection of the public key.

Dual Rail Precharge circuits offer an effective way to address Differential Power Analysis Attacks, provided routing of differential signals is fully balanced. Fat Wire [1] and Backend Duplication [2] methods address this problem. However they do not consider the effect of coupling capacitance on adjacent differential signals. In this paper we propose a new method, Divided Backend Duplication, which is based on Divided Wave Dynamic Differential Logic [3] and Backend Duplication [2], that effectively addresses balanced routing problem of Dual Rail Precharge circuits. Experimental results on an AES test circuit in 130nm technology show improvements in achieving a balanced dual rail design. Further our method can also be successfully applied to FPGAs. Results from an sbox test circuit implementation on a Xilinx FPGA are presented.

The power consumption and electromagnetic radiation are among the most extensively used side-channels for analyzing physically observable cryptographic devices. This paper tackles three important questions in this respect. First, we compare the effectiveness of these two side-channels. We investigate the common belief that electromagnetic leakages lead to more powerful attacks than their power consumption counterpart. Second we study the best combination of the power and electromagnetic leakages. A quantified analysis based on sound information theoretic and security metrics is provided for these purposes. Third, we evaluate the effectiveness of two data dimensionality reduction techniques for constructing subspace-based template attacks. Selecting automatically the meaningful time samples in side-channel leakage traces is an important problem in the application of template attacks and it usually relies on heuristics. We show how classical statistical tools such as Principal Component Analysis and Fisher Linear Discriminant Analysis can be used for efficiently preprocessing the leakage traces.

In 2008 we are celebrating the 10-th anniversary of CHES and the 30-th anniversary of the publication of the RSA paper at CACM. In this talk I will survey some of the major RSA-related papers published at CHES during the last 10 years, describe my own research on security and implementation issues, introduce some new attacks, and make predictions about the future of RSA.

Intel has recently produced several new capabilities to enhance security on the platform that have been released or will be released in the near future. In this presentation I will give a review of these capabilities and discuss their benefit to the security of the platform.