David Naccache, Nigel P. Smart, and Jacques Stern
David Naccache, Nigel P. Smart, and Jacques Stern
David Naccache, Nigel P. Smart, and Jacques Stern
david.naccache@gemplus.com
nigel@cs.bris.ac.uk
jacques.stern@ens.fr
multiplication of a public base point G by a secret k, we show that allowing an adversary access to the projective representation of P , obtained
using a particular double and add method, may result in information
being revealed about k.
Such access might be granted to an adversary by a poor software implementation that does not erase the Z coordinate of P from the computer's memory or by a computationally-constrained secure token that
sub-contracts the ane conversion of P to the external world.
From a wider perspective, our result proves that the choice of representation of elliptic curve points can reveal information about their underlying
discrete logarithms, hence casting potential doubt on the appropriateness
of blindly modelling elliptic-curves as generic groups.
As a conclusion, our result underlines the necessity to sanitize Z after
the ane conversion or, alternatively, randomize P before releasing it
out.
1 Introduction
There are various systems of projective coordinates that are used in conjunction
with elliptic curves: the usual (classical) system replaces the ane coordinates
(x; y) by any triple (X; Y; Z ) = (x; y; ), where 6= 0 is an element of the
base eld.
From such a (X; Y; Z ), the ane coordinates are computed back as
Y = Ane(X; Y; Z )
x= X
;
y
=
Z
Z
Y
X
x = Z 2 ; y = Z 3 = Ane(X; Y; Z )
These coordinates are widely used in practice, see for example [1] and [4].
This paper explores the following question:
Denoting by P = [k]G the elliptic-curve multiplication of a public base point
G by a secret k, does the projective representation of P result in information
being revealed about k?
From a practical perspective access to P 's Z coordinate might stem from a
poor software implementation that does not erase the Z coordinate of P from
the computer's memory or caused by a computationally-constrained secure token
that sub-contracts the ane conversion of P to the external world.
We show that information may leaks-out and analyse the leakage in two
dierent settings: Die-Hellman key exchange and Schnorr signatures.
Moreover, our paper seems to indicate that point representation matters: The
generic group model is often used to model elliptic curve protocols, see [2], [10],
[11]. In this model one assumes that the representation of the group elements
gives no benet to an adversary. This approach allows cryptographic schemes
built from elliptic curves to be supported by some form of provable security.
However, it has some pitfalls. In [11], it was shown that using encodings which do
not adequately distinguish an elliptic curve from its opposite, as done in ECDSA,
open the way to potential
aws in the security proofs. In this paper we show that
using projective coordinates to represent elliptic curve points rather than ane
coordinates may leak some information to an attacker. Thus, we can conclude
that modelling elliptic curves as generic groups is not appropriate in this case,
so that the generic model methodology only applies under the assumption that
ane points are made available to an external viewer/adversary of the protocol.
We note that our results imply that projective coordinates should be used
with care when they could be made available to an adversary. Our results do
not however imply that using projective coordinates for internal calculations has
any security implications.
y , y 2
x2 = x1 , x0 , x0 , x1
1
0
X1 , X0 = W
Z12 Z02 (Z0 Z1 )2
y0 (x , x )
y2 = ,y0 + xy1 ,
0
2
1 , x0
U0
W
Z2
X0 Z12 ; S0 Y0 Z13 ;
U1 X1 Z02;
S1 Y1 Z03 ;
U0 , U1 ; R S0 , S1 ;
T U0 + U1 ;
M S0 + S1 ;
WZ0 Z1 ; X2 R2 , TW 2; V TW 2 , 2X2 ; 2Y2 V R , MW 3 :
There is a similar analysis for doubling; again, we simply provide the corresponding formulae:
M 3X12 + aZ14 ; Z2 2Y1 Z1 ; S 4X1 Y12 ;
X2 M 2 , 2S;
T 8Y14 ;
Y2 M (S , X2 ) , T:
3 The Attack
Throughout this section we let G be an element of prime order r on an elliptic
curve C over a prime eld, given by its regular coordinates (xG ; yG ). Let k be
a secret scalar and dene P = [k]G. Let (X; Y; Z ) be Jacobian projective coordinates for P , computed by the formulae introduced in Section 2, when the
standard double-and-add algorithm is used.
Let t be a small integer and guess the last t bits of k. Once this is done, it is
possible to compute a set of candidates for the coordinates of the sequence of
intermediate values handled by the double-and-add algorithm while processing
k's t trailing bits (appearing at the end of the algorithm). This is achieved
by `reversing' computations: reversing doubling is halving, i.e. by reversing the
formulae for doubling ; reversing an addition amounts to subtracting G. Thus,
we obtain a set of sequences,
fs ; s ; : : : ; sm g where sj = fM j
1
( )
0
99 K M j 99 K 99 K M` j g
( )
1
( )
a fourth root is possible for one half of the inputs and, when possible, yields
two values. When p 1 mod 4 then this is possible in around one quarter
of all cases and yields four values.
We can now take advantage of the above observation to learn a few bits of k.
More precisely, we observe that, with probability at least 1=2, one can spot
values of k for which the least signicant trailing bit is one. Suppose we consider
such a k and make the wrong guess that the last bit is zero. This means that
the nal operation M`,1 99 K M` is a doubling. The error can be spotted when
the value
Z`
2y`,1
is not a fourth power, which happens with probability at most 1=2. We can then
iterate this to (potentially) obtain a few further bits of k. In the case of the least
signicant bit being zero a similar analysis can be performed.
SP = f(2 x; 3 y; ) : 2 Fq g:
The standard addition formulae for computing P + Q, for a xed value of Q
(by xed we mean a xed projective representation of Q, including an ane
representation of Q) gives a map
P;P +Q : SP ,! SP +Q :
The doubling formulae for Jacobian projective coordinates also gives us a map
P;[2]P : SP ,! S[2]P :
The crucial observations from the previous subsection are summarized in the
following Lemma
Lemma 1. The following holds, for Jacobian projective coordinates in large
prime characteristics:
If q 1 mod 3 then P;P +Q is a 3 1 map.
If q 2 mod 3 then P;P +Q is a 1 1 map.
If q 1 mod 4 then P;[2]P is a 4 1 map.
If q 3 mod 4 then P;[2]P is a 2 1 map.
Note: It is easy given an element in the image of either P;P +Q or P;[2]P to
determine whether it has pre-images, and if so to compute all of them.
The attack is then simply to consider when a point could have arisen from
an application of P;P +Q or P;[2]P and if so to compute all the pre-images and
then recurse. The precise tests one applies at dierent points will depend on the
precise exponentiation algorithm implemented by the attacked device, a subject
we shall return to in a moment.
d + xH (m; PX ; PY ; PZ ) = k mod r
Using the information he has, the attacker rewrites the above as:
An elliptic-curve C
G 2R C of order r
A collision-resistant hash-function H : f0; 1g ,! Z?r
Private x 2R Z?r
Public Q [x]G
signature generation
Pick k 2R Z?r
Compute (PX ; PY ; PZ ) [k]G = DoubleAdd(k; G)
d k , x H (m; PX ; PY ; PZ ) mod r
If d = 0 or H (m; PX ; PY ; PZ ) = 0 resume signature generation
Output fPX ; PY ; PZ ; dg as the signature of m
signature verification
parameters
Input k 2 Z?r; G 2 C
Output P [k]G
algorithm DoubleAdd(k; G)
P O
for j = ` , 1 downto 0:
P [2]P
if kj = 1 then P
P +G
return(P )
5 Practical Experiments
The double-and-add exponentiation's case is the simplest to analyse: given the
projective representation of the result P , we can try and `unwind' the algorithm
with respect to the xed point G.
In other words, we can check whether there is a value P 0 such that
P ;P +G (P 0 ) = P
and if so compute all the pre-images P 0 . Then for all pre-images P 0 we can check
0
whether this was the result of a point doubling. We also need to check whether
P itself was the output of a point doubling. This results in a backtracking style
algorithm which investigates all possible execution paths through the algorithm.
There are two factors at work here. For each testing of whether P;P +G (resp.
P;[2]P ) was applied we have a representation-dependent probability of p (from
the above lemmata), this acts in the attacker's favour. However, each success
for this test yields 1=p pre-images, which increases the attacker's workload. The
result is that, while practical, the attack against the double-and-add algorithm
is not as ecient as one might initially hope.
We ran one thousand experiments in each prime characteristic modulo 12.
Table 1 presents the success of determining the parity of the secret exponent.
One should interpret the entries in the table as follows: For example with q 5
(mod 12), we found that in 71 percent of all cases in which k was even we where
able to determine this using the above backtracking algorithm. This means that
Input
Output P
k 2 Z?r; G 2 C
parameters
[k]G
precomputation
G1 G
G2 [2]G
for j = 1 to 2r,2 , 1:
G2j+1 G2j,1 + G2
P Gk` ,1
encoding
Pexponent
`,1
set k = i=0 ki 2ei
with ei+1 , ei r and ki 2 f1; 3; : : :; 2r,1 , 1g
algorithm SlidingWindow(k; G)
for j = ` , 2 downto 0:
P [2ej+1 ,ej ]P
if `j > 0 then P
P + Gkj else P P + G,kj
P [2e0 ]P
return(P )
q mod 12
1
0.98
0.95
0.96
5
0.71
0.74
0.72
7
0.80
0.50
0.65
11
0.50
0.47
0.48
Only in the cases q 1 mod 12 and q 7 mod 12 did we have any success
in determining the value of the secret exponent modulo 8 precisely (around
50 percent of the time when q 1 mod 12 and 8 percent of the time when
q 7 mod 12).
We did a similar experiment using the signed sliding window method, with
a window width of 5 (see also Algorithm IV.7 of [1]) assuming that the precomputed table of multiples of the base point is known to the attacker. In this
case we had a much lower probability of determining the parity, but could still
determine the value of the exponent modulo 32 in a signicant number of cases
(Table 2).
Table 2. Probability of Determining the Secret's Parity Using Signed Sliding Window
Exponentiation
q mod 12
1
0.86
0.81
0.81
0.42
5
0.00
0.75
0.37
0.01
7
0.05
0.49
0.27
0.01
11
0.00
0.53
0.26
0.00
Note that this means that if q 1 mod 12 then we will be successful in determining the full private key for the division free signature algorithm of Section
4 using lattice reduction.
be the signature. With signicant probability, fm; X; Y; Z g is queried from the
random oracle. Replaying the attack with a dierent answer modulo r to this
question, one gets, with signicant probability, another forgery fm; X; Y; Z; d0g,
with h replaced by h0 . From the relation
[d]G + [h]Q = [d0 ]G + [h0 ]Q
one nally derives the discrete logarithm of Q.
References
1. I.F. Blake, G. Seroussi and N.P. Smart, Elliptic Curves in Cryptography, Cambridge University Press, 1999.
2. D. Brown, Generic Groups, Collision Resistance, and ECDSA, ePrint Report
2002/026, http://eprint.iacr.org/.
3. N.A. Howgrave-Graham and N.P. Smart, Lattice attacks on digital signature
schemes, Designs, Codes and Cryptography, 23, pp. 283{290, 2001.
4. IEEE 1363, IEEE standard specications for public key cryptography, 2000.
5. A. Joux and J. Stern, Lattice Reduction: a Toolbox for the Cryptanalyst, In
Journal of Cryptology, vol. 11, pp. 161{186, 1998.
6. J. Lopez and R. Dahab, Improved algorithms for elliptic curve arithmetic in
GF (2n ), In Selected Areas in Cryptography - sac'98, Springer-Verlag LNCS
1556, pp. 201{212, 1999.
7. P. Nguyen and I. Shparlinski, The Insecurity of the Digital Signature Algorithm
with Partially Known Nonces, In Journal of Cryptology, vol. 15, pp. 151{176,
2002.
8. P. Nguyen and J. Stern, The hardness of the subset sum problem and its cryptographic implications, In Advances in Cryptology crypto'99, Santa Barbara,
Lectures Notes in Computer Science 1666, pp. 31{46, Springer-Verlag, 1999.
9. D. Pointcheval and J. Stern, Security Arguments for Digital Signatures and
Blind Signatures, In Journal of Cryptology, vol. 13, pp. 361{396, 2000.
10. N. P. Smart, The Exact Security of ECIES in the Generic Group Model In
B. Honary (Ed.), Cryptography and Coding 8-th IMA International Conference
Cirencester, LNCS 2260, Springer Verlag, pp. 73{84, 2001.
11. J. Stern, D. Pointcheval, J. Malone-Lee and N. P. Smart, Flaws in Applying Proof Methodologies to Signature Schemes, In Advances in Cryptology
crypto'02, Santa Barbara, Lectures Notes in Computer Science 2442, pp. 93{
110, Springer-Verlag, 2002.
12. C. P. Schnorr, Ecient Signature Generation by Smart Cards, In Journal of
Cryptology, vol. 4, pp. 161{174, 1991.
13. U.S. Department of Commerce, National Institute of Standards and Technology.
Digital Signature Standard. Federal Information Processing Standard Publication 186, 1994.