METHOD AND APPARATUS FOR MASKING CRYPTOGRAPHIC OPERATIONS

METHODE ET APPAREILLAGE DE MASQUAGE DES OPERATIONS CRYPTOGRAPHIQUES

English Abstract

A method of masking a cryptographic operation using a secret value, comprising the steps of dividing the secret value into a plurality of parts; combining with each part a random value to derive a new part such that the new parts when combined are equivalent to the original secret value; and utilizing each of the individual parts in the operation.

French Abstract

Méthode de masquage d'une opération cryptographique utilisant une valeur secrète et comprenant la division de la valeur secrète en plusieurs parties, combinant une valeur aléatoire à chaque partie pour dériver une nouvelle partie de sorte que les nouvelles parties, lorsqu'elles sont combinées, correspondent à la valeur secrète d'origine; et utilisation de chacune des parties dans l'opération.

Claims

Claims:
1. A method of masking ai private key used in a cryptographic operation, said
method comprising the steps of:
applying a masking value, said masking value comprising a random value
modulo n where n is a n, umber of points on an elliptic curve, to said private
key
during at least a portion of said cryptographic operation to produce a result,
said
result corresponding to that obtained without application of said masking
value
whereby observation of 6t least said private key is inhibited by said masking
value during at least a portion of said cryptographic operation.
2. The method of claim 1 wherein said random value is randomly generated for
each session of said cryptographic operation.
3. The method of claim 2 wherein before applying said masking value, said
method further comprising:
dividing said private key into a plurality of parts, and wherein applying said
masking value comprises applying said masking value to each of said plurality
of
parts to generate a plurality of new parts, said plurality of new parts stored
such
that said plurality of new parts are updated with said random value each
session.
4. The method according to any one of claims 1 to 3 wherein said cryptographic
operation is according to :an elliptic curve (EC) cryptographic scheme.
5. The method according, to claim 4 wherein said cryptographic operation
comprises generation of a first signature component.
6. The method according to claim 5 wherein said private key comprises a short
term private key, said method further comprising applying said short term
private
key to a point on an elliptic curve utilized by said EC scheme to obtain a
short
term public key.
6

7. The method according to claim 6 further comprising using said short term
public key to generate a second signature component.
8. The method according to claim 5 wherein said private key comprises. a long
term private key, said method further comprising applying said long term
private
key to a point on said elliptic curve to obtain a long term public key.
9. The method according to claim 5 wherein said private key comprises a short
term private key and a long term private key and wherein said first signature
component has the form: s = ae + k (mod n), wherein s is said first signature
component, a is said long term private key, e is a value obtained using a hash
function, k is said short term private key.
10. The method according to claim 9 wherein e is computed using a value
computed using said short term private key.
11. The method according to claim 9 wherein a first masking value is applied
to
said long term private key and a second masking value different from said
first
masking value is applied to said short term private key.
12. The method according to claim 11 wherein said masking values change after
each cryptographic operation.
13. The method according to claim 9 wherein at least one of said short term
private key and said long term private key is split into component parts and a
masking value applied to each of said parts.
14. The method according to claim 13 wherein said masking value is applied in
a
complementary manner to each of said parts, such that, when said parts are
combined, the value of said at least one of said short term private key and
said
7

long term private key is obtained.
15. The method; according to claim 13 or claim 14 wherein said masking value
is
added to one of said component parts and said masking value is subtracted from
another of said component parts.
16. A computer readable medium comprising computer executable instructions
for causing a processor to perform the method according to any one of claims 1
to 15.
17. A cryptographic unit comprising said processor and said computer readable
medium according to claim 16.
18. A method for generating a public key in an elliptic curve (EC)
cryptographic
scheme, said method comprising the steps of:
obtaining a private key; splitting said private key into a plurality of
components;
combining, with each of said components, a random value modulo n, where n is
a number of points on an elliptic curve, to derive a plurality of new parts
such that
said plurality of new parts when combined are equivalent to said private key;
combining each of said new parts with a point on said elliptic curve to obtain
a
plurality of point multiples; and,
combining said plurality of point multiples to obtain said public key.
19. The method according to claim 18 further comprising generating a new
random value and storing updated values for said new parts for each session of
said cryptographic operation.
20. The method according to claim 18 or claim 19 wherein combining comprises
adding said random value to a one of said components and subtracting said
random value from another of said components.
8

21, The method according to any one of claims 18 to 20 further comprising
using
said public key in a further cryptographic operation.
22. The method according to claim 21 wherein said further cryptographic
operation is computing a signature.
23. A computer readable medium comprising computer executable instructions
for causing a processor to perform the method according to any one of claims
18
to 22.
24. A cryptographic unit comprising said processor and said computer readable
medium according to claim 23.
26. A method of masking a private key used in a cryptographic operation
comprising the
steps of:
(a) dividing said private key into a plurality of parts;
(b) combining with each part a random value modulo n, where n is a number
of points on an elliptic curve, to derive a new part such that the new parts
when combined are equivalent to the original private key; and
(c) utilizing each of the individual parts in said cryptographic operation.
26. A method according to claim 25, comprising generating said random value
for each
session of said cryptographic operation.
27.A method according to claim 25, said operation being an elliptic curve
cryptographic
operation.
28.A method according to claim 26 wherein said new parts are stored such that
said
new parts are updated with said random value for each session.
29.A method according to Claim 25 wherein said private key is used to compute
a public
9

key by combining said plurality of parts with a point P of said elliptic
curve.
30.A method according to claim 25 wherein said cryptographic operation
comprises
generating a signature component using said private key.
31. A method according to claim 30 wherein said private key is a short term
private key
and a long term private key, each generated according to steps (a) and (b) and
said
signature component is generated using said short term private key and said
long
term private key.
32.A method according to claim 25 wherein said plurality of parts is a pair of
values b1
and b2 and said random value is a value .pi., said plurality of parts and said
random
value combined as follows: b1 = h1 + .pi. mod n and b2 = b2 - .pi. mod n.
33.A method according to claim 32 wherein computation is then performed on a
point P
using said values b1 and b2 as follows: dP = b1 P+ b2P; wherein dP is a public
key.
34. A method according to claim 25 wherein said cryptographic operation is
generating
a signature component s = ae + k (mod n) to be used in verifying a signature
on a
message m, e being a secure hash of said message m, a being a long term
private
key and is said private key and k being a short term private key, and said
long term
private key being divided into a pair of values b1 and b2 which are combined
with
said random, value modulo n by adding said random value modulo n to b1 and
subtracting said random value modulo n from b2.
35.A computer readable medium comprising computer readable program code
embodied thereon for causing a cryptographic processor to perform the method
of
any one of claims 25 to 34.
36. A cryptographic unit comprising said processor and said computer readable
medium according to claim 35.

37. A method of masking a cryptographic operation performed in a discrete
logarithm
public key cryptographic system, a processor of said system having a long term
private
key and a short term private key, the processor performing said cryptographic
operation
using a generator G, said method comprising:
a) dividing one of said long term private key and said short term private key
into a
plurality of parts;
b) generating a separate random value for association with said plurality of
parts;
c) combining each of said plurality of parts with said random value to derive
a
plurality of new values such that said new values when combined are equivalent
to said
one of said long term private key and said short term private key; and
d) using each of said new values in said cryptographic operation to obtain
components and subsequently combining said components to obtain a value
corresponding to a combination of said one of said long term private key and
said short
term private key and said generator.
38. The method of claim 37, wherein said one of said long term private key and
said
short term private key is updated by a new random value after said
cryptographic
operation is performed, for use in a subsequent operation.
39. The method of claim 37, wherein said one of said long term private key and
said
short term private key, when divided into first and second parts, has said
random value
added to said first part and subtracted from said second part such that the
sum of said
first and second parts and said associated random value is equivalent to said
one of
said long term private key and said short term private key.
40. The method of claim 37, wherein said cryptographic operation is an
elliptic curve
digital signature algorithm.
41. The method of claim 40 wherein a signature component s has the form s =
ae+k
where a is said long term private key, e is a bit string derived from a
message m and k
11

is said short term private key, and said private key a is represented as a
pair of
components, b0, b1, such that b0 +b1=a and wherein said component b0 has said
random value added and said component b1 has said random value subtracted.
42. The method of claim 37 wherein said operation is performed in an additive
group.
43. The method of claim 37 wherein said operation is performed in a
multiplicative
group.
44. The method of claim 38 wherein said new values are stored after said
cryptographic
operation and said new random value is combined with said stored values, for
use in a
subsequent operation.
46. The method of claim 1 wherein said one of said long term private key and
said
short term private key is used to generate a corresponding public key, said
method
comprising performing said group operation on each of said plurality of parts
to
generate a plurality of public keys and utilizing each of said public keys in
said
operation.
46. The method of claim 37 wherein said cryptographic operation includes the
generation of a signature component utilizing said long term and short term
private keys
combined with additional information, said method comprising combining each of
said
plurality of parts with said additional information and subsequently combining
results
thereof to form said signature component.
47. A computer readable storage medium having stored thereon computer
executable
instructions configured to cause a processor to perform the method of any one
of claims
37 to 46.
48. A processor configured to perform the method of any one of claims 37 to
46.
12

49. A cryptographic unit comprising said processor of claim 48 configured by
said
computer readable medium of claim 47.
13

Description

CA 02259089 1999-01-15
METHOD AND APPARATUS FOR MASKING CRYPTOGRAPHIC OPERATIONS
This invention relates to cryptographic systems and in particular to a method
and
apparatus for minimizing successful power analysis attacks on processors.
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. This
secret information must generally be stored within a secure boundary, making
it difficult for
an attacker to get at it directly however, various schemes or attacks have
been attempted in
order to obtain the secret information. Of particular risk are portable
cryptographic tokens,
including smart cards and the like. Of the more recent attacks performed on
these particularly
vulnerable devices are simple power analysis, differential power analysis,
higher order
differential power analysis and other related techniques. These technically
sophisticated and
extremely powerful analysis tools can be used by an attacker to extract secret
keys from
cryptographic devices. It has been shown that these attacks can be mounted
quickly and can
be implemented using readily available hardware. The amount of time required
for these
attacks depends on the type of attack and varies somewhat by device. For
example it has been
shown that a simple power attack (SPA) typically take a few seconds per card,
while the
differential power attacks (DPA) can take several hours.
Cryptographic operations are performed in a processor operating in a
sequential
manner by performing a sequence of fundamental operations, each of which
generates a
distinct timing pattern. Laborious but careful analysis of end-to-end power
waveforms can
decompose the order of these fundamental operations performed on each bit of a
secret key
and thus be, analyzed to find the entire secret key, compromising the system.
In the simple power analysis (SPA) attacks on smart cards and other secure
tokens, an
attacker directly measures the token's power consumption changes over time.
The amount of
power consumed varies depending on the executed microprocessor instructions. A
large
calculation such as elliptic curve (EC) additions in a loop and DES rounds,
etc, may be
identified, since the operations performed with a microprocessor vary
significantly during
1

CA 02259089 1999-01-15
different parts of these operations. By sampling the current and voltage at a
higher rate, i.e.,
higher resolution, individual instructions can be differentiated.
The differential power analysis attack (DPA) is a more powerful attack than
the SPA
and is much more difficult to prevent. Primarily, the DPA uses statistical
analysis and error
correction techniques to extract information which may be correlated to secret
keys, while the
SPA attacks use primarily visual inspection to identify relevant power
fluctuations. The DPA
attack is performed in two steps. The first step is recording data that
reflects the change in
power consumed by the card during execution of cryptographic routines. In the
second step,
the collected data is statistically analyzed to extract information correlated
to secret keys. A
detailed analysis of these attacks is described in the paper entitled
"Introduction to
Differential Power Analysis and Related Attacks" by Paul Kocher et al.
Various techniques for addressing these power attacks have been attempted to
date.
These include hardware solutions such as providing well-filtered power
supplies and physical
shielding of processor elements. However, in the case of smart cards and other
secure tokens,
this is unfeasible. The DPA vulnerabilities result from transistor and circuit
electrical
behaviors that propagate to expose logic gates, microprocessor operation and
ultimately the
software implementations.
Accordingly, there is a need for a system for reducing the risk of a
successful power
analysis attacks and which is particularly applicable to current hardware
environments.
SUMMARY OF THE INVENTION
It is an object of this invention to provide a method for minimizing power
analysis
attacks on processors.
In accordance with this invention there is provided a method of masking a
cryptographic operation using a secret value, comprising the steps of:
(a) dividing said secret value into a plurality of parts;
(b) combining with each part a random value to derive a new part such that the
new
parts when combined are equivalent to the original secret value; and
(c) utilizing each of the individual parts in said operation.
2

CA 02259089 1999-01-15
BRIEF DESCRIPTION OF THE DRAWINGS
These and other features of the preferred embodiments of the invention will
become
more apparent in the following detailed description in which reference is made
to the
appended drawings wherein:
Figure 1 is a schematic diagram of a communication system; and
Figure 2 is a flow diagram illustrating an embodiment of the invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
Referring to figure 1, a communication system having at least a pair of
corespondents
is shown generally by numeral 10. It is assumed that the correspondents 12 and
14
incorporate cryptographic units 16 and 18 respectively. For convenience, the
first
correspondent will be referred to as the sender and the second correspondent
will be referred
to as the receiver. Generally, a plain text message is processed by the
encryption unit of the
sender and transmitted as cyphertext along a communication channel to the
receiver where the
encryption message is decrypted by the cryptographic unit 18 to recover the
original message.
The above system provides a typical environment for application of the
invention as will be
described below.
Referring to figure 2 a method for masking a private key or secret value used
in a
cryptographic operation is shown generally by numeral 200. The method
comprises the steps
of dividing a secret value into a plurality of parts and combining with each
part a random
value modulo n (where n is the number of points on the elliptic curve) to
derive a new part
such that the new parts are combined to be equivalent to the original secret
value and utilizing
each of the individual parts in the operation. Typically, the secret value is
a private key, which
is used to compute a public key, and more frequently used in signatures,
decryption and
possibly key exchange protocols, such as Diffie-Hellman key exchange.
For illustrative purposes, we will in the following discussion assume an EC
scheme,
where P is a point on the elliptic curve. The secret key d is normally
combined with the point
P to derive dP, the public key. However, the private key may also be used more
frequently in
various other cryptographic operations as described above. The cryptographic
processor is
3

CA 02259089 2011-03-28
generally initialized at manufacture time with the public key or secret value
d. Initially, the
valued may be divided into a number of parts, e.g. d - bia + bxo.
In,a first step :the bi's are initialized to bi - btaand bz such that d = b10
+ b20.
These initial, i+itlues: cif hi and b2 are stored instead of d. Alternatively
the d value may also be
stored if so, desired; however in the case of a smart card' where memory is
limited this may not
be desir~bTc_
Typically when, a computation using the value disrequired. At a next step, a
random
number n is generated and the values b I and b2 are: Updated as follows:
b1: b, + .7r mod n
b2 b2 n mod n
The updated values of b, and b2 are stored. Computation is then performed on.
the
point P usingthe:coaiponents b, and b2 as follows.
dP wo b3P + b2P
where, P is apoint on the curve which is a predefined parameter of the system.
'T'hus assuming the value n is randomly :generated for each session, then an
attacker is
unlikely tq':ohstrue a predictable power signatuic;
In a. typical application of the present invention a signature component s has
the form:-
s n ae + yk (mod n)
where:
k Is a random ;integer selected as a short terra private or session key;
R kP J. the corresponding short team public key;
r~l?, x .component o.fR
a is, the. long to nl private key of the sender;
Q:,al is the senders corresponding public key;
e is a secure hash, such as the SI3A-I hash function, of a message m and the
short terra
public ;key R( or possibly a short message itself); and,
n is, the order of the curve.
The sender sends to the recipient a message including m, s, and r and the
signature is
vcri Pied by coznpudng'the value R'- (sP-eQ) which should correspond to R. If
the:computed
4

CA 02259089 1999-01-15
Y
values correspond then the signature is verified. Both the secret keys in the
above example
may be masked using the method of the present invention.
Specifically referring back to the above example, calculation of the product
ae may
reveal some information on some platforms in some environments. To minimise
this, the
present invention is applied. The product ae is computed as ae = (bo + b1)e
for (bo + b1) =a;
where bo, b1 sum to a. The components bo , b1 are updated periodically as
described above.
This updating of the components can be made on every new signature operation.
In the above embodiments the secret value was divided into two components bo ,
b1,
however this may be generalized to a plurality of components b0....bri_1.
Furthermore the
above signature scheme is used for illustrative purposes and other schemes and
operations
may equally well be applied using the present invention.
Although the invention has been described with reference to certain specific
embodiments, various modifications thereof will be apparent to those skilled
in the art without
departing from the spirit and scope of the invention as outlined in the claims
appended hereto.
5

Representative Drawing