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 5*K*+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]