Workshop on Cryptographic Hardware and Embedded Systems
Ches 2001
May 14-16, 2001
Paris, France
Jonathan Towle
InterTrust
jtowle@intertrust.com
CHES 2001 ( www.chesworkshop.org) was held in Paris France. This was the third year of CHES. For the past two years the workshop had been help at WPI in Massachusetts. There were 210 people on the list of attendees. The workshop chairs Cetin Koc, David Naccache and Christof Paar did an excellent of putting together a very interesting program. CHES 2002 will be in San Jose, CA in August either just prior to or just after Crypto 2002.
The two and a half day workshop had two one hour invited talks at the start of Monday and Tuesday. The rest of the workshop was 20-minute presentations. I will list the presentations in chronological order, with the title in italics; the authors are given in brackets at the end with the presenter in bold.
Monday May 16
Invited Speaker
Protecting Embedded Systems - The Next Ten Years
A very interesting presentation looking at the security requirements for the near to mid term future for devices attached to the Internet. A brief history of the Internet was given, the “first wave” was centered around main frames and terminals; the “second wave” (1992 until now) has been centered on PC’s running browsers; the “third wave” will see many devices, ranging from cell phones to refrigerators, connected to the Internet. The protection requirements for these devices were discussed.
[Ross Anderson, University of Cambridge]
Side
Channel attacks I
A Sound Method for Switching between Boolean and Arithmetic Masking
A beautifully rigorous paper. Algorithms were presented which are secure against first order DPA. Unfortunately the Arithmetic to Boolean algorithm is very computationally expensive (requiring 5K+5 operations where K is the number of registers).
[Louis Gobin, Schlumberger]
Fast primitives for internal data scrambling in tamper
resistant hardware.
This paper addresses the problem of an attacker probing internal buses. Three implementations of keyed permutations were proposed, one using hardware and two using group theory. These methods are well suited to data obfuscation in smart cards.
[Eric Brier, Helena Handschuh and Christophe
Tymen, Gemplus Card International]
Random Register Renaming to Foil DPA
Since most of the power consumed by an electronic processor is used to overwrite register values, if the bit to be overwritten is chosen randomly, the power consumption is randomized, making DPA difficult. An implementation of a Non-Deterministic Instruction Stream Computer (NDISC) was discussed.
[D. May, H.L. Muller and N.P. Smart, University of Bristol]
Randomized Addition-Subtraction Chains as a Countermeasure Against Power Attacks
Unskilled implementations of Elliptic Curve Cryptosystems (ECC) are vulnerable to SPA. An adversary can identify the parts of the trace that correspond to additions and duplications and therefore deduce the secret key. Previously proposed countermeasures randomize secret parameters. This paper introduces a new countermeasure where a random decision is taken as to how the calculation is to be performed. This countermeasure increases the number of operations required by 9%; this is independent of key length.
[Elisabeth Oswald and Manfred Aigner, Graz University, Austria]
Rijndael
Hardware Implementations
Architectural optimization for 1.82Gbits/sec VLSI implementation of the AES Rijndael algorithm.
An interesting presentation of hardware required for high speed encryption rates. The circuits proposed were based on 0.18mm CMOS and the timing estimates based on gate counts. The design could complete one Rijdael round in one clock cycle (100MHz in this model).
[H. Kuo & I.Verbauwhede, UCLA]
High Performance Single-Chip FPGA Rijndael Algorithm Implementations
A beautifully clear description of Rijndael was presented. When implemented using a high performance FPGA a data rate of 7 GBits/s was achieved.
[Maire McLoone and J.V. McCanny, Queen’s University, Northern Ireland]
Two Methods of Rijndael Implementation in Reconfigurable Hardware
An implementation of Rijndael using FPGA was presented. In this implementation T-boxes were used. The T-box is a combination of an S-box and the Mix Column operations. The T-box approach gave a 22% rate increase compared to the S-Box approach but required four times the memory.
[Viktor Fischer and Milos Drutarovsky, Technical University of Kosice, Slovak Republic]
Pseudo-Random Number Generation on the IBM 4758 Secure Crypto Coprocessor
It was shown that PRN generators based on SHA-1 are faster than those based on discrete logarithms.
[Nick Howgrave-Graham, Joan Dyer and Rosario Gennaro, IBM]
Efficient Online Tests for True Random Number Generators
A new online test procedure was presented, which although it required slightly more computer resources than currently used tests, it is considered to be more secure.
[Werner Schindler, BSI, Germany]
The Hessian form of an elliptic curve.
The Hessian form of an EC has the advantage that field multiplications can be performed in parallel. This has been implemented using FPGAs and can give a performance advantage of up to 40%.
[N.P. Smart, University of Bristol, UK]
Efficient ECC from a Scalar Multiplication Algorithm with
Recovery of the y-Coordinate on a Montgomery-Form EC.
A new scalar multiplication algorithm with recovery of the y-coordinate was compared to traditional ones.
[Katauyuki Okeya, Kouichi Sakurai, Hitachi, Japan]
Generating EC of Prime Order
A variant of the complex multiplication (CM) EC generation algorithm for finite fields was presented. The new method allows off-line recalculation and therefore smaller and faster on-line implementation.
[Erkay Savas, Thomas A. Schmidt, and Centin
Koc, Oregon State University]
Tuesday May 16, 2001 – Invited Talk
New Directions in Croptography [SIC]
A method for breaking stream ciphers using classical optical computers was presented. The method has not been implemented.
[Adi Shamir, The Weizman Institute, Israel]
A multiplier was presented that reduces the number of gates required it implement it compared to other fast parallel multipliers that a currently in use.
[Manuel Leone, Telecom Italia]
Efficient Rijndael Encryption Implementation with Composite Field Arithmetic
Careful consideration of polynomial multiplication on GF{2^8} let to an implementation using 265 kgates with a rate of 7.5Gbits/sec@32MHz.
[A. Rudra et al., IBM India]
High-Radix Design of Scalable Modular Multiplier
The Montgomery Multiplication (MM) provides certain advantages in the implementation of modular multiplication. Experimental results show that the radix-8 scalable multiplier is able to perform better that radix-2 for large areas.
[Alexandre F. Tenca, Georgi Todorov, and Cetin K.
Koc, Oregon state University]
A bit-serial unified multiplier architecture for finite fields GF(p) and GF(2^m)
A very efficient unified multiplier was presented which could be implemented in smart card processors.
[Johnann Grosschadl, Graz University of Technology Austria]
Attacks on Cryptographic Transaction Sets
An interesting description of attacks on the IBM 4758 CCA and the Visa security Module.
[Mike Bond, University of Cambridge]
Bandwidth-Optimal Kleptographic Attacks
Kleptographic attacks are carried out by the designer/manufacture of a black box cryptosystem using information such as keys initiated in the system at time of setup.
[Adam Young and Moti Yung, Columbia University]
Electromagnetic Analysis: Concrete results
A fascinating paper: a small copper coil was used to pick up Electromagnetic emissions from a smart card processor. The leaked information is similar to that given by power analysis, although in the case of a smart card processor performing RSA, if was found that the key could be recovered using SEMA but not with SPA.
[K. Gandolfi, C. Mourtel and F. Olivier, Gemplus
Card International, France]
Embedded
Implementations and New Ciphers.
NTRU in Constrained Devices
A description of Ntru was given along with performance data from an FPGA implementation.
[Dan Bailey et al., Ntru Inc]
Transparent Hard Disk Encryption
New block cipher, FBC, was introduced that is optimized for high bandwidth applications.
[T. Pornin, Ecole Normale Superieure, Paris, France]
Sliding Windows Succumbs to Big Mac Attack
A very clever variation of DPA was presented. Sliding windows is a technique for obtaining an efficient exponentiation scheme. In a Big Mac attack is one in which bits of the secret key are deduced independently. Interesting longer keys are more vulnerable to this form of attack.
[Colin Walter, UMIST]
Universal Exponentiation Algorithm - First step towards provable SPA resistance
An algorithm was presented that avoids the use of secrets directly in exponentiation and is therefore SPA proof.
[C. Clavier and M. Joye, Gemplus Card International]
An Implementation of DES and AES Secure Against Some Attacks
A software masking method was presented
[M-L Akkar and C. Giraud, Schmberger, France]