Electrical computers and digital processing systems: support – Data processing protection using cryptography – Tamper resistant
Reexamination Certificate
1999-06-17
2003-12-02
Peeso, Thomas R. (Department: 2132)
Electrical computers and digital processing systems: support
Data processing protection using cryptography
Tamper resistant
C713S155000, C713S168000, C713S189000, C713S193000, C713S152000, C713S152000
Reexamination Certificate
active
06658569
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a process for protecting a computer system implementing a cryptographic algorithm that uses a secret key. More precisely, the purpose of the process is to produce a version of the algorithm that is not vulnerable to a certain type of physical attack—known as Differential Power Analysis or High-Order Differential Power Analysis—aimed at obtaining information on the secret key through a study of the computer system's electric power consumption during the execution of the calculation.
The cryptographic algorithms considered herein use a secret key to calculate output information as a function of input information; this can involve an operation for encryption, decryption, signature, signature verification, authentication or non-repudiation. They are constructed in such a way that in practice, an attacker who knows the inputs and the outputs cannot deduce any information on the secret key itself.
The invention described herein relates to a class larger than that traditionally designated by the expression “secret key algorithms” or “symmetric algorithms.” In particular, everything that is described in the present patent application also applies to so-called “public key” algorithms or “asymmetric algorithms,” which actually include two keys: one public, the other private and undisclosed, the latter being the one targeted by the attacks described below.
2. Description of Related Art
Attacks of the type known as Power Analysis, developed by Paul Kocher and Cryptographic Research (see the document
Introduction to Differential Power Analysis and Related Attacks
by Paul Kocher, Joshua Jaffe, and Benjamin Jun, Cryptography Research, 870 Market Street, Suite 1008, San Francisco, Calif. 94102; published as an HTML document at the URL address: http://www.cryptography.com/dpa/technical/index.html, introduced into the present application as a reference) is based on the observation that, in reality, an attacker can acquire information other than just the input and output data during the execution of the calculation such as, for example, the electric power consumption of the microcontroller or the electromagnetic radiation emitted by the circuit.
Differential Power Analysis, abbreviated DPA, is an attack that makes it possible to obtain information on the secret key contained in the computer system by performing a statistical analysis on power consumption measurements performed on a large number of calculations with this same key.
As a non-limiting example, the case of the DES (Data Encryption Standard) algorithm, a description of which can be found in any of the following named documents will be considered:
FIPS PUB 46-2,
Data Encryption Standard,
1994;
FIPS PUB 74,
Guidelines for Implementing and Using the NBS Data Encryption Standard,
1981;
ANSI X3.92
American National Standard, Data Encryption Algorithm,
1981;
ISO/IEC 8731:1987,
Banking—Approved Algorithms for Message Authentication—Part
1:
Data Encryption Algorithm
(
DEA
);
or in the following book:
Bruce Schneier,
Applied Cryptography,
2
nd Edition
, John Wiley & Sons, 1996, page 270.
The above-mentioned documents are introduced into the present application as references.
The DES algorithm is executed in 16 steps known as rounds (see
FIG. 1
a
). In each of the 16 rounds, a transformation F into 32 bits is performed. This transformation F uses eight nonlinear transformations of 6 bits to four bits, each of which is coded into a table called an S box (see
FIG. 1
b
, in which the S boxes are marked S
1
, S
2
, . . . , S
8
.
A DPA attack on the DES can be implemented in the following way:
1st step: Power consumption measurements are made on the first round, for 1,000 DES calculations. The input values of these 1,000 calculations are marked E[1], . . . , E[1,000]. The corresponding 1,000 power consumption curves measured during these calculations are marked C[1], . . . , C[1,000]. The average curve CM of the 1,000 consumption curves is also calculated.
2nd step: The first bit output from the first S box during the first round is selected. Let b be the value of this bit. It is easy to see that b is only dependent on 6 bits of the secret key. The attacker forms a hypothesis on the 6 bits in question. He calculates—from these 6 bits and from the E[i]s—the corresponding theoretical values for b. This makes it possible to separate the 1,000 inputs E[1], . . . , E[1,000] into two categories: those that result in b=0, and those that result in b=1.
3rd step: Next, the average CM′ of the curves corresponding to inputs of the first category, i.e., those for which b=0, is calculated. If CM and CM′ show a notable difference, the values retained for the 6 key bits are considered to be the correct ones. If CM and CM′ do not show any substantial difference in the statistical sense, i.e., no difference that is clearly greater than the typical difference from the noise measured, the 2nd step is repeated with another choice for the 6 bits.
4th step: Steps 2 and 3 are repeated with a target bit b output from the second S box, then from the third S box, and so on, through the eighth S box. Thus, 48 bits of the secret key are eventually obtained.
5th step: The remaining 8 bits can be found by a thorough search.
This attack does not require any knowledge of the individual power consumption of each instruction, or of the chronological position of each of these instructions. It applies in the same way whenever it may be assumed that the attacker knows some of the outputs of the algorithm and the corresponding consumption curves. It is based only on the fundamental hypothesis according to which:
Fundamental Hypothesis
There is an intermediate variable, appearing during the calculation of the algorithm, such that the knowledge of some key bits, in practice less than 32 bits, makes it possible to determine whether two inputs, and respectively two outputs, do or do not result in the same value for this variable.
All of the algorithms, like the DES, that use S boxes are potentially vulnerable to DPA, since the normal modes of implementation generally fall within the scope of the above-mentioned hypothesis.
The attacks known as High-Order Differential Power Analysis, abbreviated HO-DPA, are a generalization of the DPA attack described above. They can use several different sources of information; in addition to power consumption, they can involve measurements of electromagnetic radiation, temperature, etc., and can use statistical operations that are more sophisticated than the simple concept of an average, and intermediate variables (generalizing the bit b defined above) that are less elementary. Nonetheless, they are based on exactly the same fundamental hypothesis as DPA.
SUMMARY OF THE INVENTION
The object of the process that is the subject of the present invention is to eliminate the risks of DPA or HO-DPA attacks on computer systems using secret or private key cryptography.
Consequently, another subject of the present invention is a modification of the cryptographic calculation process implemented by protected computer systems using cryptography such that the above-mentioned fundamental hypothesis is no longer verified, in other words, no intermediate variable is dependent on the power consumption of an easily accessible subsystem of the private or secret key, attacks of the DPA or HO-DPA type thus being rendered inoperative.
The process for protecting a computer system implementing a standard cryptographic calculation process that uses a secret key, which is the subject of the present invention, is remarkable in that the cryptographic calculation process is separated into several distinct calculation parts, executed in parallel and producing partial intermediate results distinct from those of the standard cryptographic calculation, and in that the final value obtained by the standard calculation without a separation is reconstructed from the distinct part
Goubin Louis
Patarin Jacques
Bull CP8
Coulson Lesley L.
Kondracki Edward J.
Miles & Stockbridge P.C.
Peeso Thomas R.
LandOfFree
Secret key cryptographic process for protecting a computer... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Secret key cryptographic process for protecting a computer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Secret key cryptographic process for protecting a computer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3181122