Joye M.Cryptographic hardware and embedded systems.2005

306 Y. Sakai and K. Sakurai

We can evaluate that how many bits can be recovered from observed in the case of the NAF recoding.

4.3An Attack on Unsigned Fractional Window Recoding

We show an attack on the unsigned fractional window recoding. Similar strategies as in the recoding case can be applied. Data dependent subtraction

TEAM LinG

instructions have to be carried out at Step 6 and 8 of Algorithm 4. Therefore, the attacker can observe during the recoding. The difference on the strategies from the case of NAF is that even when the subtraction instruction at Step 8 is carried out, no carry occur.

The attack is shown in Algorithm 7.

Remark 1. Even if the case of “unknown”, the probability of “0” or “1” may not be equal in some cases depending on the parameter In such a case we can modify the attack with weighted probability of guessed value. In appendix A relations between successive unknown bits are described.

4.4An Attack on Signed Fractional Window Recoding

An attack on the signed fractional window recoding is shown in Algorithm 8. The similar strategies as recoding can be applied, but handling of the transmission of a carry should be more complicated. Only when continuous are observed after a carry may be transmitted to or The variable in Algorithm 8 is used to store the number of continuous

TEAM LinG

308 Y. Sakai and K. Sakurai

4.5Experimental Results

We carried out experiments by a simulation on the attacks described in the previous sections as follows.

TEAM LinG

1.randomly generate 10,000 exponents which have 160-bit, 512-bit or 1024bit.

2.implement algorithms for exponent recodings described in Algorithms 3, 4 and 5 in S/W written in C-language.

3.generate using this S/W.

4.using the we guess the secret exponent by Algorithm 6, 7 and 8.

5.count the successfully recovered bits (= number of recovered bits / bitlength of exponent

The results are given in Table 2. The experiments were carried out with 160bit, 512-bit and 1024-bit exponents. Almost the same percentages were obtained

as we have already mentioned, the bits of the middle in the window can not be guessed uniquely. In the fractional window expansion the successfully recovered bits increase in larger Examples of the three proposed attacks with small exponents are illustrated in Appendix B.

Remark 2. No guessing errors occur in the attacks. Only “unknown” bits can be un-recovered bits.

TEAM LinG

310 Y. Sakai and K. Sakurai

5Concluding Remarks

We have shown that unless the exponent recoding is carefully implemented, RSA and elliptic curve based cryptosystems are vulnerable to power analysis. We have introduced new side channel attacks on exponent recoding.

While the effects of a single transistor switching would be normally be impossible to identify from direct observations of a device’s power consumption [4], the statistical operations are able to reliably identify extraordinarily small differences in power consumption.

Okeya and Takagi proposed efficient counter measures for side channel attacks [6,7]. The exponent recodings given in [6,7] are based on NAF or fractional window. Therefore, it may be possible to construct attacks on the recodings.

References

l.J.-S. Coron, “Resistance against differential power analysis for elliptic curve cryptosystems,” CHES’99, LNCS 1717, pp.292–302, Springer-Verlag, 1999.

2.P.C. Kocher, “Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems,” Advances in Cryptology – CRYPTO’96, LNCS 1109, pp.104–113, Springer-Verlag, 1996.

3.P.C. Kocher, J. Jaffe, and B. Jun, “Differential power analysis,” Advances in Cryptology – CRYPTO’99, LNCS 1666, pp.388–397, Springer-Verlag, 1999.

4.P.C. Kocher, J. Jaffe, and B. Jun, “Introduction to differential power analysis and related attacks,” Cryptography Research, http://www.cryptography.com

5.B. Möller, “Improved techniques for fast exponentiation,” ICISC 2002, LNCS 2587, pp.298–312, Springer-Verlag, 2002.

6.K. Okeya, T. Takagi, “The NAF method provides small memory and fast elliptic scalar multiplications secure against side channel attacks,” CT-RSA 2003, LNCS 2612, pp.328–342, Springer-Verlag, 2003.

7.K. Okeya, T. Takagi, “A more flexible countermeasure against side channel attacks using window method,” CHES 2003, LNCS 2779, pp.397–410, Springer-Verlag, 2003.

8.G.W. Reitwiesner, “Binary arithmetic,” Advances in Computers, vol.1, pp.231–308, 1960.

9.J.A. Solinas, “Efficient arithmetic on Koblitz curve,” Designs, Codes and Cryptography, vol.87, pp. 195–249. Kluwer Academic Publishers, 2000.

ARelation Between Unknown Bits

In this appendix we show relations between unknown bits. If several unknown bits occur in succession, some unknown bits can be “0” or “1” with high probability. Table 3 shows the probability that unknown bits can be “0” or “1” in the case of the unsigned fractional window recoding with the parameter and

TEAM LinG

BExamples of the Attacks

In this appendix we illustrate small examples of the three attacks. In examples below, given randomly generated 32-bit exponents, recoded representations and expected are described. The attacker can recover the exponents from the observed as shown below. The symbol “x” in the recovered bits denotes the “unknown” bit.

width-3 NAF

exponent: 1 1 1 0 0 0 0 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 10 1 0 1 10 0 1 1 recoded: 1 0 0 -1 0 0 0 10 0 0 0 0 -3 0 0 3 0 0 0 0 -1 0 0 0 -3 0 0 3 0 0 0 3 1 0 0 0 1 0 0 2 0 0 0 2 0 0 0 0 10 0 2 0 0 0 0 0 1 0 0 0 2 0 0 1 recovered: 1x 1 0 0 x 0 1x 1 10 x 0 1 0 1 x 1 1 x 1 1 0 1 0 x 10 0 x 1

unsigned fractional window with w = 3, m = 1

exponent: 1 0 1 1 1 0 0 0 1 1 1 1 0 0 0 0 1 0 1 1 1 0 1 0 1 0 0 0 0 1 1 1 recoded: 1 0 0 0 7 0 0 0 1 0 0 7 0 0 0 0 1 0 0 0 7 0 0 0 5 0 0 0 0 0 0 7 1 0 0 0 1 0 0 0 1 0 0 2 0 0 0 0 10 0 0 1 0 0 0 1 0 0 0 0 0 0 1 recovered: 1 x x x 1 x x x 1 x x 10 x x x 1 x x x 1x x x 1 0 0 0 x x x 1

signed fractional window with w = 3, m = 1

exponent: 10 0 1 1 0 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0 recoded: 1 0 0 0 0 7 0 0 0 -3 0 0 0 0 -1 0 0 0 5 0 0 0 -3 0 0 0 0 0 0 9 0 0 1 0 0 0 0 1 0 0 0 2 0 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 0 0 0 1 0 0 recovered: 1 0 x x x x x x x 0 1 x x x x x x x x x x x 1 0 0 0 x x x 1 0 0

TEAM LinG

Defeating Countermeasures Based on Randomized BSD Representations

Pierre-Alain Fouque1, Frédéric Muller2, Guillaume Poupard2, and

Frédéric Valette2

1 École normale supérieure, Département d’informatique

45 rue d’Ulm 75230 Paris Cedex 05 France

Pierre-Alain.Fouque@ens.fr

2 DCSSI Crypto Lab 51, Boulevard de Latour-Maubourg 75700 Paris 07 SP France

{Frederic.Muller,Guillaume.Poupard,Frederic.Valette}@sgdn.pm.gouv.fr

Abstract. The recent development of side channel attacks has lead implementers to use increasingly sophisticated countermeasures in critical operations such as modular exponentiation, or scalar multiplication on elliptic curves. A new class of countermeasures is based on inserting random decisions when choosing one representation of the secret scalar out of a large set of representations of the same value. For instance, this is the case of countermeasures proposed by Oswald and Aigner, or Ha and Moon, both based on randomized Binary Signed Digit (BSD) representations. Their advantage is to offer excellent speed performances. However, the first countermeasure and a simplified version of the second one were already broken using Markov chain analysis.

In this paper, we take a different approach to break the full version of HaMoon’s countermeasure using a novel technique based on detecting local collisions in the intermediate states of computation. We also show that randomized BSD representations present some fundamental problems and thus recommend not to use them as a protection against side-channel attacks.

1 Introduction

Modular exponentiation or scalar multiplication are used by most popular public key cryptosystems like RSA [22] or DSA [4]. However, data manipulated during these computations should generally be kept secret, since any leakage of information (even only a few bits of secret information) might be useful to an attacker. For example, during the generation of an RSA signature by a cryptographic device, the secret exponent is used to transform an input related to the message into a digital signature via modular exponentiation.

Timings and power attacks, first introduced by Kocher [11,12] are now well studied and various countermeasures have been proposed. These attacks represent a real threat when considering operations that involve secret data and require a long computation time. In general, naive implementations leak information about the secret key.

In [2], Coron has shown that several countermeasures are possible to prevent this type of leakage. In the context of Elliptic Curve Cryptosystems (ECC), he proposed different techniques based on blinding the critical data manipulated. An alternative approach is to randomize the number and the sequence of steps in the multiplication algorithm itself. In this type of countermeasure the usual scalar multiplication algorithm on ECC is replaced by a randomized addition-subtraction chain. From a general perspective, the idea is to allow additional symbols in the secret scalar representation. When using the set of digits {0,1, –1}, we generally speak of Binary Signed Digit (BSD) representation. Then the multiplication algorithm picks at random a valid representation of the secret scalar. Actually several algorithms of this class have been proposed in the recent years [7,13,20], many of which have been broken quickly [16,26,27]. In this paper, we present a new side channel attack against randomized exponentiation countermeasures. We believe this result enlightens fundamental defects in these constructions.

Basically our attack scenario is that an attacker has physical access to a cryptographic device and tries to find the private key used by the device. He first obtains different encryptions of a fixed message. Since the scalar representation is randomized, the cryptographic device performs a different computation each time. However, we will show that collisions occur frequently at each step of computation. They can be detected using power consumption curves and reveal critical information concerning the private key. Our attack does not depend much on which public key encryption scheme is actually used, so we focus on the case of ECCs. Furthermore, the Ha-Moon’s countermeasure [7], proposed at CHES’02, was designed originally for ECCs. It is straightforward to apply our ideas to RSA-based encryption schemes and even to signature schemes based on RSA with a deterministic padding (i.e. without randomization) such as PKCS#1 v1.5 [23]. Indeed all we need is the ability to send the same input several times to the cryptographic device.

In this paper, we first recall the classical binary scalar multiplication on elliptic curves. Then, we briefly describe different types of side channel attacks such as Simple Power Analysis (SPA) and Differential Power Analysis (DPA) but also the attack of Messerges, Dabbish and Sloan [14] in order to motivate common countermeasures. Next, we describe the principles of countermeasures using a randomized BSD representation through the example of [7]. In the last two sections, we expose some major weaknesses in this family of algorithms and describe a new collision-based attack against the full Ha-Moon’s countermeasure.

2Binary Scalar Multiplication Algorithms

In classical cryptosystems based on the RSA or on the discrete logarithm problem, the main operation is modular exponentiation. In the elliptic curve setting, the corresponding operation is the scalar multiplication. From an algorithmic point of view, those two operations are very similar; the only difference is the underlying group structure. In this paper, we consider operations over a generic

TEAM LinG

314 P.-A. Fouque et al.

group with additive notations. We do not use additional properties of this group. The consequence is an immediate application to the elliptic curve setting but it should be clear that all what we state can be easily transposed to modular exponentiation.

Scalar multiplication is usually performed using the “double-and-add”

This method is obviously analog to the “square-and-multiply” method for modular exponentiation. The resulting algorithm is described in Figure 1, where is the point at infinity.

Fig. 1. Naive “double-and-add” scalar multiplication algorithm

3Power Analysis Attacks

It is well known that the naive double-and-add algorithm is subject to the power attacks introduced by Kocher et al [12]. More precisely, they introduced two types of power attacks : Simple Power Analysis (SPA) and Differential Power Analysis (DPA).

3.1Simple Power Analysis

The first type of attack consists in observing the power consumption in order to guess which instruction is executed. For example, in the previous algorithm, one can easily recover the exponent provided the doubling instruction can be distinguished from the point addition. To avoid this attack, the basic “double-and-add always” algorithm is usually modified using so-called “dummy” instructions (see Figure 2).

Although this new algorithm is immune to SPA, a more sophisticated treatment of power consumption measures still enables the recovery of the secret scalar

TEAM LinG

Fig. 2. Double-and-add always algorithm resistant against SPA

3.2Differential Power Analysis

DPA uses power consumption to retrieve information on the operand of the instruction. More precisely, it no longer focuses on which instruction is executed but on the Hamming weight of the operands used by the instruction. Such attacks have been described, in the elliptic curve setting, in [2,17].

This technique can also be used in a different way. Messerges, Dabbish and Sloan introduced “Multiple Exponent Single Data” attack [14]. Note that, for our purpose, a better name would be “Multiple Scalar Single Data”. We first assume that we have two identical devices available with the same implementation of the algorithm of Figure 2, one with an unknown scalar and another one for which the scalar can be chosen and modified. In order to discover the value of using correlation between power consumption and operand value, we can apply the

the power consumption of the two devices doing the scalar multiplication of the same message. If the consumption is similar during the first two steps of the inner loop, it means that we have guessed the correct bit Otherwise, if the consumption differs in the second step, it means that the values are different and that we have guessed the wrong bit. So, after this measure, we know the most

This kind of attack is well known and some classical countermeasures are often implemented (see [2,9]).

4Countermeasures Using a Randomized Scalar Representation

In the case of scalar multiplication on ECC, the most popular countermeasures against DPA are those proposed by Coron [2]. They include randomizing the secret scalar, blinding the point and using randomized projective coordinates. New directions for attacking these countermeasures have recently been proposed [5, 6] but none of them works when all protections proposed by Coron are applied

TEAM LinG