Secure Cryptographic Algorithm Implementation on Embedded Platforms

Author: Michael Tunstall

Reference: RHUL-MA-2007-5

Abstract:

Sensitive systems that are based on smart cards use well-studied and well-developed
cryptosystems. Generally these cryptosystems have been subject to rigorous mathematical
analysis in an effort to uncover cryptographic weaknesses in the system. 
The cryptosystems used in smart cards are, therefore, not usually vulnerable to
these types of attacks. Since smart cards are small objects that can be easily placed
in an environment where physical vulnerabilities can be exploited, adversaries have
turned to different avenues of attack.

This thesis describes the current state-of-the-art in side channel and fault analysis
against smart cards, and the countermeasures necessary to provide a secure
implementation. Both attack techniques need to be taken into consideration when
implementing cryptographic algorithms in smart cards.

In the domain of side-channel analysis a new application of using cache accesses
to attack an implementation of AES by observing the power consumption is described,
including an unpublished extension.

Several new fault attacks are proposed based on finding collisions between a
correct and a fault-induced execution of a secure secret algorithm. Other new fault
attacks include reducing the number of rounds of an algorithm to make a differential
cryptanalysis trivial, and fixing portions of the random value used in DSA to allow
key recovery.

Countermeasures are proposed for all the attacks described. The use of random
delays, a simple countermeasure, is improved to render it more secure and less
costly to implement. Several new countermeasures are proposed to counteract the
particular fault attacks proposed in this thesis. A new method of calculating a
modular exponentiation that is secure against side channel analysis is described,
based on ideas which have been proposed previously or are known within the smart
card industry. A novel method for protecting RSA against fault attacks is also
proposed based on securing the underlying Montgomery multiplication.

The majority of the fault attacks detailed have been implemented against actual
chips to demonstrate the feasibility of these attacks. Details of these experiments
are given in appendices. The experiments conducted to optimise the performance
of random delays are also described in an appendix.