CIRCUIT PROTECTION SYSTEM AND METHOD

• US 20170228562A1
• Filed: 07/30/2015
• Published: 08/10/2017
• Est. Priority Date: 08/06/2014
• Status: Active Grant

• Current Assignee: Secure-IC S.A.S
• Original Assignee: Secure-IC S.A.S
• Inventors: GUILLEY, Sylvain, PORTEBOEUF, Thibaut, DANGER, Jean-Luc
• Granted Patent: US 10,331,912 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/22 Detection or location of defective computer hardware by testing during standby operation or during idle time, e.g. start-up testing
• CPC Class Codes: G06F 11/263 Generation of test inputs, e.g. test vectors, patterns or sequences ; with adaptation of the tested hardware for testability with external testers
• CPC Class Codes: G06F 21/55 Detecting local intrusion or implementing counter-measures
• CPC Class Codes: G06F 21/56 Computer malware detection or handling, e.g. anti-virus arrangements
• CPC Class Codes: G06F 21/71 to assure secure computing or processing of information
• CPC Class Codes: G06F 21/75 by inhibiting the analysis of circuitry or operation
• CPC Class Codes: G06F 2221/034 Test or assess a computer or a system
• CPC Class Codes: G09C 1/00 Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system cryptographic typewriters G09C3/00
• CPC Class Codes: H04L 2209/046 of operations, operands or results of the operations
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441

Abstract

The invention proposes a method of protection of a Boolean circuit associated with a structural description of the circuit comprising elementary Boolean variables, each represented by one bit, the method comprising the steps consisting in:

• • selecting a set of k elementary Boolean variables of the circuit as a function of predefined selection criteria,
  • constructing a variable x represented by k bits by concatenation of the k selected variables in accordance with a chosen order,
  • determining a binary code C comprising a set of code words and belonging to a given vector space and the supplementary code D of said binary code C as a function of a condition bearing on the dual distance of said supplementary code D, said binary code C having a length n and a size 2^k, where k designates the number of bits representing said variable x;
  • substituting the variable x in the structural description of the Boolean circuit with a protected variable z represented by n bits so that:
    • any operation of writing on the variable x in the circuit is substituted with an operation of writing on the variable z, the variable z being generated by adding the variable x encoded by said code C to a random bit vector y encoded by the supplementary code D, and
    • any operation of reading the variable x in the circuit is substituted with an operation of reading the value of the protected variable z and an operation of decoding said read value of the protected variable z using a decoding matrix J of size (n×k) determined from the binary code C and the supplementary code D of the binary code C.

Claims

1. Method of protection of a Boolean circuit associated with a structural description of the circuit comprising elementary Boolean variables, each represented by one bit, the method comprising:

selecting a set of k elementary Boolean variables of the circuit as a function of predefined selection criteria,

constructing a variable x represented by k bits by concatenation of the k selected variables in accordance with a chosen order,

determining a binary code C comprising a set of code words and belonging to a given vector space and the supplementary code D of said binary code C as a function of a condition bearing on the dual distance of said supplementary code D, said binary code C having a length n and a size 2^k, where k designates the number of bits representing said variable x;

substituting the variable x in the structural description of the Boolean circuit with a protected variable z represented by n bits so that;

any operation of writing on the variable x in the circuit is substituted with an operation of writing on the protected variable z, the protected variable z being generated by adding the variable x encoded by said code C to a random bit vector y encoded by the supplementary code D, and

any operation of reading the variable x in the circuit is substituted with an operation of reading the value of the protected variable z and an operation of decoding said read value of the protected variable z using a decoding matrix J of size (n×

k) determined from the binary code C and the supplementary code D of the binary code C.

2. Circuit protection method according to claim 1, wherein the selecting said elementary Boolean variables comprises selecting the elementary Boolean variables with different uses.

3. Circuit protection method according to claim 1, wherein said binary code C is a linear code comprising a generator matrix G of size k×

n used to code the state of said variable x in accordance with the relation xG and in that said supplementary code D comprises a generator matrix H of size (n−

k)×

n used to code the vector y of random bits in accordance with the relation yH, the matrix J used being determined from the generator matrix G of the binary code C and the generator matrix H of the supplementary code D.

4. Circuit protection method according to claim 1, comprising detecting a fault injected into the protected variable z by determining if a condition relating to the random bit vector is verified, said condition being verified if the random bit vector y is different from the read value of the protected variable z and decoded by a decoding matrix K of size n×

(n−

k), said matrix K being determined from the binary code C and the supplementary code D.

5. Circuit protection method according to claim 3, wherein the decoding matrix K is determined from the generator matrix G of the binary code C and the generator matrix H of the supplementary code D.

6. Circuit protection method according to claim 3, wherein the decoding matrix J and/or the decoding matrix K are determined from the relation:

7. Method according to claim 4, wherein the random bit vector y encoded by said supplementary code D is further encoded by a code E of dimension greater than or equal to n−

k and producing words of size m, said code being associated with a decoding matrix M and an encoding matrix L, said code E being further associated with a supplementary code F having a decoding matrix N, corresponding to the control matrix of the code E, and an encoding matrix P, the random bit vector y being stored in a form y′

corresponding to the encoding of the random bit vector by the code E.

8. Method according to claim 7, wherein the detecting a fault injected into the protected variable z comprises the verification of a condition relating to a fault test on the random bit vector y, said condition relating to the fault test being verified if the quantity zK, depending on the value of the protected variable z and the decoding matrix K, is different from the quantity y′

M, where y′

designates the random bit vector y encoded by the code E and M designates the decoding matrix associated with the code E.

9. Method according to claim 7, wherein the detecting a fault injected into the variable y′

comprises the verification of a condition relating to the random bit vector y′

, said condition relating to the random bit vector y′

being satisfied if the quantity y′

N is different from zero.

10. Method according to claim 7, wherein said code E is equal to the supplementary code D of the binary code C and in that the supplementary code F of the code E is equal to the binary code C, the encoded variable y′

then being of size n−

k and equal to y.H.

11. Method according to claim 7, wherein the code E is equal to the binary code C and in that the supplementary code F of the code E is equal to the supplementary code D of the code C, the variable y of (n−

k) bits being transformed into a variable y_k of k bits and the encoded variable y′

being of size n and equal to y_kG.

12. Circuit protection method according to claim 1, wherein the chosen code and said supplementary are generated beforehand in such a manner as to satisfy a principal security condition relating to the value of the dual distance of the supplementary code relative to a target value.

13. Circuit protection method according to claim 12, wherein the chosen code and said supplementary code are generated beforehand in such a manner as to satisfy a secondary security condition relating to the length n of the code C and/or to the minimum distance d_C of the chosen code C.

14. Circuit protection method according to claim 12, wherein the chosen code and said supplementary code are generated beforehand in such a manner as to satisfy a secondary security condition relating to the quantity

15. Circuit protection system comprising a Boolean circuit associated with a structural description comprising elementary Boolean variables, each represented by one bit, said elementary variables comprising a set of k elementary Boolean vectorial variables preselected as a function of predefined selection criteria, the system comprising protection elements in the circuit configured to substitute a variable x represented by k bits and constructed by concatenation of the k preselected elementary variables in accordance with a chosen order with a protected variable z represented by n bits, said protection elements comprising:

circuit elements configured to replace any operation of writing on the variable x by an operation of writing on the protected variable z by addition of the variable x encoded by a predetermined binary code C, comprising a set of code words and belonging to a given vector space, to a random bit vector encoded by the supplementary code D of said binary code C, said code C having a length n and a size 2^k, where k represents the number of bits representing said variable x, and

circuit elements configured to replace any operation of reading on the variable x with an operation of reading the value of the protected variable z and an operation of decoding said read value of the protected variable z using a matrix J of size (n×

k) determined from the binary code C and the supplementary code, the binary code C being predetermined as a function of a condition bearing on the dual distance of said supplementary code D.