METHOD AND DEVICES FOR PROTECTING A MICROCIRCUIT FROM ATTACKS FOR OBTAINING SECRET DATA

• US 20100262840A1
• Filed: 04/28/2010
• Published: 10/14/2010
• Est. Priority Date: 11/02/2007
• Status: Abandoned Application

• Current Assignee: CONTACTLESS, Cryptography Research, Inc. (Rambus Inc.)
• Original Assignee: INSIDE Contactless
• Inventors: FEIX, Benoit, BENTEO, Bruno, NEROT, Sébastien
• Application Number:
  US12/768,837
• Publication Number:
  US 20100262840A1
• Time in Patent Office: Days
• US Class Current: 713/190
• CPC Class Codes: G06F 7/582 Pseudo-random number generators
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/004 for fault attacks
• CPC Class Codes: Y04S 40/20 Information technology specific aspects, e.g. CAD, simulation, modelling, system security

Abstract

A method of protecting a microcircuit against attacks aimed at discovering secret data used on the execution, by the microcircuit, of an encryption algorithm includes generating at least one protection parameter for the secret data and modifying the execution of the encryption algorithm through that protection parameter. Generation of the at least one protection parameter includes defining a function generating, by successively applying to at least one secret parameter which is stored in memory, a sequence of values which can only be determined from that secret parameter and that function, and to generate the protection parameter in a reproducible way from at least one value in that sequence.

Claims

1. A method of protecting a microcircuit against attacks aimed at discovering secret data used on execution, by the microcircuit, of an encryption algorithm, the method comprising:

generating at least one protection parameter P for the secret data; and

modifying the execution of the encryption algorithm using the at least one protection parameter P, the generation of the at least one protection parameter P including;

providing at least one secret parameter stored in a secure memory of the microcircuit;

defining at least one generating function allowing for the generation of a sequence of values p_n, by successive applications of the generating function to the secret parameter, the sequence of values being determinable only from the generating function and the secret parameter;

generating at least one sequence of values p_n, using the generating function and the secret parameter, and

generating the at least one protection parameter P in a reproducible way from at least one value of the sequence of values p_n.

2. The method according to claim 1, wherein the secret data is a message, a symmetric cryptography secret key, an asymmetric cryptography private key, or a combination thereof.

3. The method according to claim 1, further comprising performing an initialization, which includes defining of the secret parameter, and in which each execution of the encryption algorithm is modified by a plurality of protection parameters P₁, . . . P_N, that are generated respectively from elements p_N(i−

1)+1 to p_Ni in the sequence of values p_n on an i-th execution of the encryption algorithm following the initialization.

4. The method according to claim 1, wherein the sequence of values p_n is generated using a recurrence relation p_n+1=q.p_n+r, applied to secret parameters q, r, and p₀.

5. The method according to claim 1, wherein the sequence of values p_n, is generated using a recurrence relation p_n+1=(q.p_n+r) mod m, applied to secret parameters q, r, m, and p₀.

6. The method according to claim 5, wherein the secret parameter m is an integer power of 2.

7. The method according to claim 1, wherein the sequence of values p_n includes values in a cyclic group GC with m elements, with a value p as element generator for the group and multiplication as internal composition law, and generation of the sequence of values p_n includes:

choosing an initial element p₀ of the sequence as being the generator element p to which the group GC internal composition law is applied k times, and

changing from an element p_i of rank i to an element p_i+1 of rank i+1 by applying k′

times the group GC internal composition law, m, p, k and k′

being secret parameters.

8. The method according to claim 1, wherein the sequence of values p_n includes values in a Frobenius group, the Frobenius group including reversible affine transformations on a finished field GF(q), wherein an order q is a prime number of k bits, q and k being secret parameters.

9. The method according to claim 1, wherein the sequence of values p_n includes values output from a shift register with linear feedback of size m such that the elements in the sequence comply with a relation of the type p_t+m=α

_m.p_t+α

<sub>m−

1</sub>.p_t+1+. . . +α

₁.p<sub>t+m−

1</sub>, where α

_i takes the value 0 or 1, the parameters α

_i, the size m, and the m first elements in the sequence of values p_n being secret parameters.

10. The method according to claim 1, wherein the sequence of values p_n is obtained by a recurrence relation p_n+1=F(p_n), where function F carries out a Cyclic Redundancy Check calculation based on a Cyclic Redundancy Check polynomial, the first element in the sequence of values p_n and the chosen polynomial being secret parameters.

11. The method according to claim 1, further comprising:

generating a plurality of sequences of values p′

_n, p″

_n from a plurality of generating functions and from a plurality of corresponding secret parameters,

combining the plurality of sequences of values p′

_n, p″

_n through an ore-defined relation to generate a new sequence of values p_n, and

generating the protection parameter P in a reproducible way from at least one value of the new sequence of values p_n.

12. The method according to claim 1, further comprising:

combining a sequence of values p′

n with public parameters of the encryption algorithm to generate a new sequence of values p_n, and

generating the protection parameter P in a reproducible way from at least one value of the new sequence of values p_n.

13. A microcircuit device protected against attacks aimed at discovering secret data used on execution, by the microcircuit, of an encryption algorithm, the microcircuit device comprising:

a secure memory configured to store the secret data;

a data generator configured to generate at least one protection parameter P for the secret data; and

a microprocessor configured to execute the encryption algorithm, modified using the protection parameter P, the data generator including;

a generating section configured to generate the sequence of values p_n by successive application of at least one predefined generating function to at least one predetermined secret parameter, the sequence of values p_n being determinable only from the secret parameter and the generating function, and

a section configured to supply the protection parameter P in a reproducible way from at least one value of the sequence of values p_n supplied by the generating section, the secret parameter being a predetermined parameter stored in the secure memory of the microcircuit.

14. The microcircuit device according to claim 13, wherein the secret data is a message, a symmetric cryptography secret key, an asymmetric cryptography private key, or a combination thereof.

15. The microcircuit device according to claim 13, wherein:

the generating section is configured to perform an initialization that includes defining of the secret parameter, and

the microprocessor is configured to modify each execution of the encryption algorithm using a plurality of protection parameters P₁, P_N that are generated respectively from elements p<sub>N(i−

1)+1</sub> to p_Ni of the sequence of values p_n on an i-th execution of the encryption algorithm following the initialization.

16. The microcircuit device according to claim 13, wherein the generating section is configured to supply the sequence of values p_n, which are obtained through a recurrence relation p_n+1=q.p_n+r, applied to secret parameters q, r, and p₀.

17. The microcircuit device according to claim 13, wherein the generating section is configured to supply the sequence of values p_n, which are obtained through a recurrence relation p_n+1=(q.p_n+r) mod m, applied to secret parameters q, r, m, and p₀.

18. The microcircuit device according to claim 17, wherein m is an integer power of 2.

19. The microcircuit device according to claim 13, wherein the generating section is configured to supply the sequence of values p_n, which includes values in a cyclic group GC with m elements, with a value p as generator element for the group and multiplication as internal composition law, and is further configured to:

choose an initial element p₀ of the sequence as being the generator element p to which the group GC internal composition law is applied k times, and

change the element p_i of rank i to an element p_i+1 of rank i+1 by applying k′

times the group GC internal composition law, m, p, k and k′

being secret parameters (S).

20. The microcircuit device according to claim 13, wherein the generating section is configured to supply the sequence of values p_n, which includes values in a Frobenius group, the Frobenius group including reversible affine transformations on a finished field GF(q), where an order q is a prime number of k bits, q and k being secret parameters.

21. The microcircuit device according to claim 13, wherein the generating section is configured to supply the sequence of values p_n, which includes values output from a shift register with a linear feedback of size m such that the sequence elements comply with a relation of the type p_t+m=α

_m.p_t+α

<sub>m−

1</sub>.p_t+1+ . . . +α

₁.p<sub>t+m−

1</sub>, where the α

_i takes the value 0 or 1, the parameters α

_i, the size m, and the m first elements of the sequence of values p_n being secret parameters.

22. The microcircuit device according to claim 13, in which the generating section is configured to supply the sequence of values p_n, which are obtained through a recurrence relation p_n+1=F(p_n), where a function F performs a Cyclic Redundancy Check calculation based on a Cyclic Redundancy Check polynomial, the first element of the sequence of values and the chosen polynomial being secret parameters.

23. The microcircuit device according to claim 13, wherein the data generator is configured to:

generate a plurality of sequences of values p′

_n, p″

_n from a plurality of generating functions and from a plurality of corresponding secret parameters,

combine the plurality of sequences of values p′

_n, p″

_n using a predefined relation to generate a new sequence of values p_n, and

generate the protection parameter P in a reproducible way from at least one value of the new sequence of values p_n.

24. The microcircuit device according to claim 13, wherein the data generator is configured to:

combine a sequence of values p′

_n with public parameters of the encryption algorithm to generate a new sequence of values p_n, and

generate the protection parameter P in a reproducible way from at least one value of the new sequence of values p_n.

25. A portable device comprising a microcircuit device according to claim 13.