Registers – Records
Reexamination Certificate
2002-01-14
2004-11-23
Frech, Karl D. (Department: 2876)
Registers
Records
C235S492000, C235S494000
Reexamination Certificate
active
06820814
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a countermeasure method in an electronic component implementing a secret key cryptographic algorithm. They are used in applications where the access to services or data is strictly controlled. They have an architecture formed around a microprocessor and memories, one of which is a program memory which contains the secret key.
These components are notably used in smart cards, for certain applications thereof. These are for example applications for accessing certain data banks, banking applications, or remote payment applications, for example for television, petrol dispensing or passing through motorway tolls.
These components or these cards therefore implement a secret key cryptographic algorithm, the best known of which is the DES (Data Encryption Standard) algorithm. Other secret key algorithms exist, such as the RC5 algorithm or the COMP128 algorithm. This list is of course not exhaustive.
Briefly and in general terms, the function of these algorithms is to calculate an encrypted message from a message applied at the input (to the card) by a host system (server, cash dispenser, etc.) and the secret key contained in the card, and to supply in return to the host system this encrypted message, which allows for example the host system to authenticate the component or the card, to exchange data, etc.
However, it has turned out that these components or these cards are vulnerable to attacks consisting of a differential current consumption analysis and which allow ill-intentioned third parties to find the secret key. These attacks are referred to as DPA (Differential Power Analysis) attacks.
The principle of these DPA attacks is based on the fact that the current consumption of a microprocessor executing instructions varies according to the data manipulated.
Notably, an instruction of a microprocessor manipulating a data bit generates two different current profiles depending on whether this bit has the value “1” or “0”. Typically, if the instruction is manipulating a “0”, there is at that execution instant a first consumed current amplitude, and if the instruction is manipulating a “1”, there is a second consumed current amplitude, different from the first.
The characteristics of cryptographic algorithms are known: the calculations performed and parameters used. The sole unknown is the secret key contained in program memory. This cannot be deduced from the sole knowledge of the message applied at the input and the encrypted message supplied in return.
However, in a cryptographic algorithm, certain calculated data depend solely on the message applied in clear at the input of the card and the secret key contained in the card. Other data calculated in the algorithm can also be recalculated solely from the encrypted message (generally supplied in clear at the output of the card to the host system) and the secret key contained in the card. More precisely, each bit of these particular data items can be determined from the input or output message, and from a limited number of particular bits of the key.
Thus, each bit of a particular data item has corresponding thereto a sub-key formed by a particular group of bits of the key.
The bits of these particular data items which can be predicted are referred to in the remainder of the document as target bits.
The basic idea of the DPA attack is thus to use the difference in the current consumption profile of an instruction depending on whether it is manipulating a “1” or a “0” and the possibility of calculating a target bit by the instructions of the algorithm from a known input or output message and a hypothesis on the corresponding sub-key.
The principle of the DPA attack is therefore to test a given sub-key hypothesis by applying, to a large number of current measurement curves, each relating to an input message known to the attacker, a Boolean selection function, a function of the sub-key hypothesis, and defined for each curve by the value predicted for a target bit.
Making a hypothesis on the sub-key concerned in fact gives the capability of predicting the value “0” or “1” which this target bit will take for a given input or output message.
There can then be applied, as a Boolean selection function, the value “0” or “1” predicted for the target bit for the considered sub-key hypothesis, in order to sort these curves into two bundles: a first bundle groups together the curves where the target bit was manipulated at “0” and a second bundle groups together the curves where the target bit was manipulated at “1” according to the sub-key hypothesis. By calculating the current consumption mean in each bundle, a mean consumption curve M
0
(t) for the first bundle and a mean consumption curve M
1
(t) for the second bundle are obtained.
If the sub-key hypothesis is correct, the first bundle actually groups together all the curves among the N curves where the target bit was manipulated at “0” and the second bundle actually groups together all the curves among the N curves where the target bit was manipulated at “1”. The mean consumption curve M
0
(t) of the first bundle will then have a mean consumption everywhere except at the moments at which the critical instructions are executed, with a current consumption profile characteristic of manipulation of the target bit at “0” (profile
0
). In other words, for all these curves, all the manipulated bits had as many chances of having the value “0” as having the value “1”, except the target bit which always had the value “0”. This can be written:
M
0
(
t
)=[(profile
0
+profile
1
)/2]
t≠tci
+[profile
0
]
tci
that is
M
0
(
t
)=[
Vm
t
]
t≠tci
+[profile
0
]
tci
where tci represents the critical instants, at which a critical instruction was executed.
Similarly, the mean consumption curve M
1
(t) of the second bundle corresponds to a mean consumption everywhere except at the moments at which the critical instructions are executed, with a current consumption profile characteristic of manipulation of the target bit at “1” (profile
1
). The following can be written:
M
1
(
t
)=[(profile
0
+profile
1
)/2]
t≠tci
+[profile
1
]
tci
that is
M
1
(
t
)=[
Vm
t
]
t≠tci
+[profile
1
]
tci
It has been seen that the two profiles profile
0
and profile
1
are not equal. The difference in the curves M
0
(t) and M
1
(t) then gives a signal DPA(t), the amplitude of which is equal to profile
0
−profile
1
at the critical instants tci at which the critical instructions manipulating this bit are executed, that is to say, in the example depicted in
FIG. 1
, at the locations tc
0
to tc
6
, and the amplitude of which is approximately equal to zero apart from the critical instants.
If the sub-key hypothesis is false, the sort does not correspond to reality. Statistically, there are then, in each bundle, as many curves where the target bit was actually manipulated at “0” as curves where the target bit was manipulated at “1”. The resultant mean curve M
0
(t) is then situated around a mean value given by (profile
0
+profile
1
)/2=Vm, since, for each of the curves, all the bits manipulated, including the target bit, have as many chances of having the value “0” as having the value “1”.
The same reasoning on the second bundle leads to a mean current consumption curve M
1
(t), the amplitude of which is situated around a mean value given by (profile
0
+profile
1
)/2=Vm.
The signal DPA(t) supplied by the difference M
0
(t)−M
1
(t) is in this case substantially equal to zero. The signal DPA(t) in the case of a false sub-key hypothesis is depicted in FIG.
2
.
Thus, the DPA attack exploits the difference in the current consumption profile during execution of an instruction according to the value of the manipulated bit, in order to carry out a current consumption curve sort according to a Boolean selection function for a given sub-key hypothesis. By carrying out a differential analysis of the mean current con
Burns Doane Swecker & Mathis L.L.P.
Frech Karl D.
Gegemplus
LandOfFree
Countermeasure method in an electric component using a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Countermeasure method in an electric component using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Countermeasure method in an electric component using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3303931