Fault and Power Analysis Attack Protection Techniques for Standardized Public Key Cryptosystems

Apostolos P. Fournaris

Introduction

The basic building block of any security protocol is its cryptographic algorithms and their primitive operations. While there exist many cryptographic algorithms only few of them are standardized. In several of them, their cryptographic primitives have considerable similarities. This is especially true in public key cryptography where the real, day-to-day, security scene is dominated by security products relying on public key cryptography schemes that are based on RSA, El Gamal or ECC approaches. So, considerable research is focused on enhancing the security of such standardized schemes implementations without reducing those implementation performance.

The mathematical backbone of RSA, El-Gamal and ECCs is the integer factorization problem (IFP), the discrete logarithm (DLP) and elliptic curve discrete logarithm problem (ECDLP) respectively. Those problems rely on the arithmetic operations of modular exponentiation (ME) and scalar multiplication (SM) that from number theoretic perspective are very closely related. RSA and El-Gamal is structured around Z* multiplicative and additive cyclic group, i.e., where addition and multiplication operations are defined. Modular exponentiation in Z* for RSA is defined as c^{e} mod n where c is an RSA message, e is the exponent (public or private RSA key) and n is the public modulus. To reduce high bit length of involved numbers needed to keep the IFP or DLP hard, we can replace Z* with a different abelian group where these problems are harder. Such group is the Elliptic Curve group E (F) where F is a finite field. However, since this group is additive, all Zn multiplication operations are replaced by their additive equivalent. Thus, in ECC schemes, all Elliptic Curve points P : (x, y) are defined over the additive group E (F) where F is a finite field in which each EC point’s coordinates (x, y) belong to F and instead of Z* multiplication, addition between EC points is performed while instead of Z* squaring EC

A.P. Fournaris (B)

Computer Informatics Engineering Department, Technological Educational Institute of Western, Antirion, Greece e-mail:
This email address is being protected from spam bots, you need Javascript enabled to view it
;
This email address is being protected from spam bots, you need Javascript enabled to view it

N. Sklavos et al. (eds.), Hardware Security and Trust,

DOI 10.1007/978-3-319-44318-8_5

doubling (as a special case of addition) is performed. Z*_{n} ME can be realized as series of modular multiplications and squaring operations. Similarly, due to the equivalence of Zn multiplication to E (F) EC point addition, E (F) scalar multiplication (SM), defined as e ? P where P e E (F) (P is denoted also as base point) and e e F, from engineering perspective, is equivalent to Zn ME and can be realized as a series of E( F) EC point addition and E( F) point doubling operations.

Regardless of the fact that Z* operations and F operations (i.e., operation between EC point coordinates) can have significant differences (e.g., when F is a binary extension field), the Zn multiplication to EC(F) addition equivalence hints that the two public key cryptographic primitives design (ME and SM) follow similar principles for achieving efficiency in hardware terms (chip covered area, resources, computation time, power consumption). Traditional ME and SM algorithms like multiply and square or double-and-add algorithms respectively are very close in concept.

Similar ME and SM design principles, however, lead to common implementation attack techniques and approaches. Implementation attacks target an actual implementation of a cryptographic algorithm and exploit information leakage (side channel attack) or faulty behavior (fault injection) of the implementation’s physical characteristics (power dissipation, timing, electromagnetic emission, etc.). As expected, side channel (SCA) and fault analysis (FA) attacks in ME or SM designs require similar SCA-FA countermeasures. In this book chapter, apart from FAs, our research interest is focused on SCAs relying on power dissipation, known as power analysis attacks (PA) but the proposed countermeasures can be also applicable to other SCAs (e.g., relying on electromagnetic emission or timing).

In this book chapter, expanding the work of [1], the concept of a unified SCA-FA protection mechanism both for ME and SM is explored. This mechanism is capable of thwarting a wide range of existing PA and FA attack approaches. The proposed approach is a variation of the Montgomery Power Ladder algorithm for ME/SM that is sufficiently modified in order to counter “vertical” and “horizontal” simple and advanced SCAs (focusing on PAs). To achieve that goal, the randomization technique is adopted in the proposed algorithm by introducing a random element eZn or E (F) along with the message/base point in every algorithmic round. This randomization is propagated and extended in each round and is only removed after the last round of the proposed algorithm. The high regularity of the Montgomery Power Ladder algorithm and its intrinsic parallelism provide high performance as well as additional resistance against SCAs-PAs. The proposed algorithm takes advantage of the intrinsic mathematical coherence between intermediate algorithmic values, offered by Montgomery Power Ladder, to detect possible faults (following the infective computation principle) thus providing FA resistance. Attempts to bypass successfully the fault detection mechanism by injecting a second fault lead to non-usable information by an attacker since the ME/SM result is released (unblinded) only after passing the fault detection check. The above countermeasures are combined in an harmonic way so that they do not introduce new vulnerabilities.

The rest of the paper is organized as follows. In Sect. 5.2 existing SCA-PA and FA approaches and countermeasures on ECC and RSA systems are presented. In Sect. 5.3 the proposed approach is described and a security analysis of the algorithm is made in Sect. 5.4, while Sect. 5.5 concludes the paper.