Power signature attack resistant cryptography

Details Power signature attack resistant cryptography Power signature attack resistant cryptography

2000-09-05

2004-05-18

Rones, Charles (Department: 2175)

Cryptography

Particular algorithmic function encoding

C380S030000, C380S282000, C709S226000

Reexamination Certificate

active

06738478

ABSTRACT:

This invention relates to a method and apparatus for minimizing power signature attacks in cryptographic systems.
BACKGROUND OF THE INVENTION
Cryptographic systems generally owe their security to the fact that a particular piece of information is kept secret without which it is almost impossible to break the scheme. The secret information must generally be stored within a secure boundary in the cryptographic processor, making it difficult for an attacker to get at it directly. However, various schemes or attacks have been attempted in order to obtain this secret information. One of these is the timing or power signature attack.
The timing attack (or “side channel attack”) is an obvious result of sequential computational operations performed during cryptographic operations. The attack usually exploits some implementation aspect of a cryptographic algorithm.
For example current public key cryptographic schemes such as RSA and elliptic curve (EC) operate over mathematical groups; Z*
n
(n=pq) in RSA, discrete log systems in a finite field F*
q
(q is a power of a prime), F*
2
M
or an EC group over these finite fields. The group operations, called multiplication modulo n, in RSA, and addition of points in EC are sequentially repeated in a particular way to perform a scalar operation. In RSA the operand is called an exponent, the operation is called exponentiation and the method of multiplying is commonly known as repeated square-and-multiply. Thus given a number a&egr;Z*
n
and an integer 0≦k<p, the exponent, whose binary representation is k=&Sgr;
1=0
i
k
i
2
i
a value a
k
mod n may be calculated by repeated use of the “square-and-multiply” algorithm (described in Handbook of Applied Cryptography P.615). Similarly given g(x)&egr;F
p
m and an integer 0≦k≦p
m
−1 then g(x)
k
mod f(x) may be calculated by this method.
On the other hand, in EC the operand is a scalar multiplier, the operation is called scalar multiplication of a point, and the method is known as “double-and-add”. Thus if k is a positive integer and P is an elliptic curve point then kP may be obtained by the “double-and-add” method. Both these methods are well known in the art and will not be discussed further.
As mentioned earlier, an attacker once in possession of the private key (either long term or session) is able to forge signatures and decrypt secret messages for the attacked entity. Thus it is paramount to maintain the secrecy or integrity of the private key in the system.
Many techniques have been suggested to obtain the private key. The encryption operations are performed either in a special purpose or general-purpose processor operating in a sequential manner. Recent attack methods have been proposed in open literature as for example described in Paul Kochers's article “Timing attacks on implementations of Diffie-Hellman, RSA, DSS and other systems”. These attacks have been based on timing analysis of these processors or in other words timing analysis of ‘black box’ operations. In one instance an attacker by capturing the instantaneous power usage of a processor throughout a private key operation obtains a power signature. The power signature relates to the number of gates operating at each clock cycle. Each fundamental operation as described in the preceding paragraph generates a distinct timing pattern. Other methods exist for obtaining a power signature than instantaneous power usage.
Laborious but careful analysis of an end-to-end waveform can decompose the order of add-and-double or square-and-multiply operations. Using the standard algorithm, either a double or square must occur for each bit of either the exponent or scalar multiplier respectively. Therefore, the places where double waveforms are adjacent each other represent bit positions with zeros and places where there are add waveforms indicate bits with ones. Thus, these timing measurements can be analyzed to find the entire secret key and thus compromise the system.
In addition to the “square and multiply” or “double and add” techniques mentioned earlier, other methods to compute kP are for example the “binary ladder” or Montgomery method described in “Speeding the Pollard and Elliptic Curve Methods of Factorization” by Peter L. Montgomery. In this method the x-coordinates of the pair of points (iP, (i+1)P) are computed. The Montgomery method is an efficient algorithm for performing modula multiplication, more clearly illustrated by an example. Given a group E (F
p
) and given a point P on the elliptic curve, the Montgomery method may be used to compute another point kP. Given an ordered pair of points (iP, (i+1)P), then for each of the bits of the binary representation of k, if bit i is a 0 then the next set of points computed is (2iP, (2i+1)P) and if bit i is 1, then the next set of points is ((2i+1)P, (2i+2)P), that is, the first of the pair is derived from a doubling or an adding depending on whether the bit is a 0 or 1.
In a processor, each of the doubles and adds involve multiple operations which generate unique power signatures. By observing these power signatures as shown schematically in FIG.
1
(
a
), the attacker may derive a sequence of 0s and 1s and thus, the scalar or exponent being used.
The Montgomery method is preferable in EC cryptographic systems because of its extreme efficiency over the straight “double and add” described earlier.
The attack on the Montgomery method as described above is particularly important if performing RSA private key operations. In a recent paper published by Dan Boneh et al entitled “An Attack On RSA Given A Small Fraction Of The Private Key Bits”, it has been shown that for RSA with a low public exponent, given a quarter of the bits of the private key, an adversary can determine the entire private key. With this attack combined with the power signature attack described above, the RSA scheme is extremely vulnerable.
Thus, it is an object of this invention to provide a system which minimizes the risk of a successful timing attack particularly when utilizing the Montgomery method on private key operations.
SUMMARY OF THE INVENTION
In accordance with this invention, there is provided a method of computing a multiple k of a point P on an elliptic curve defined over a field, said method comprising the steps of:
a) representing the number k as binary vector of bits k
i
;
b) forming an ordered pair of points P
1
and P
2
, wherein the points P
1
and P
2
differ at most by P; and
c) selecting each said bits k
i
in sequence; and for each of said k
i
;
i) upon k
i
being a 0
ii) computing a new set of points P
1
′, P
2
′ by doubling the first point P
1
to generate said point P
1
′; and
iii) adding the points P
1
and P
2
to generate the point P
2
′; or upon k
i
being a 1
iv) computing a new set of points P
1
′, P
2
′ by doubling the second point P
2
to generate the point P
2
′; and
v) adding the points P
1
and P
2
to produce the point P
1
′,
whereby said doubles or adds are always performed in the same order for each of said bits b
i
, thereby minimizing a timing attack on said method.
In accordance with a further aspect of this invention, the field is either F
2
m
or F
p
.
In accordance with a further aspect of this invention, there is provided a processor hardware for implementing the method.


REFERENCES:
patent: 6252959 (2001-06-01), Paar et al.
patent: 6263081 (2001-07-01), Miyaji et al.
patent: 2001/0033655 (2001-10-01), Vadekar et al.
patent: 2002/0041681 (2002-04-01), Hoffstein et al.
patent: 2002/0057796 (2002-05-01), Lambert et al.
patent: 2003/0123655 (2003-07-01), Lambert et al.
Agnew GB et al: “An Implementation of Elliptic Curve Cryptosystems Over F2155” IEEE Journal on Selected Areas in Communications, vol. 11, No. 5, p. 804-813 XP399849 IEEE Inc. New York ISSN:0733-8716 p. 808, right-hand column, line 23-line 26, relevant to claim No. 1-3.
Kocher PC: “Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems” Advances in Cryptology—Crypto '

Affiliated with

Also associated with

Rating

Power signature attack resistant cryptography does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Power signature attack resistant cryptography, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Power signature attack resistant cryptography will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3247019