Cryptographic method protected against covert channel type attacks
The invention relates to a cryptographic method secured against a covert channel attack. According to the invention, in order to carry out a selected block of instructions as a function of an input variable amongst N predefined instruction blocks, a common block is carried out on the predefined N instruction blocks, a predefined number of times, the predefined number being associated with the selected instruction block.
1. A method for implementing a cryptographic calculation in an electronic device, comprising the following steps:
selecting a block of instructions from amongst a plurality of predefined blocks of instructions, as a function of an input variable; and
executing, in the electronic device, a set of instructions that is common to the plurality of predefined blocks of instructions a predefined number of times, wherein said predefined number is associated with the selected block of instructions.
2. A method according to claim 1 , wherein the predefined number is variable from one predefined block of instructions to another.
3. A method according to claim 1 , wherein the common set of instructions comprises at least one calculation instruction that is equivalent to a calculation instruction of each predefined block in the context of a covert channel attack.
4. A method according to claim 3 , in which the common set of instructions also comprises an instruction to update a loop pointer indicating a number of executions already performed with the common set of instructions.
5. A method according to claim 4 wherein the value of the loop pointer is a function of the value of the input variable and/or of the number of instructions in the selected block of instructions.
6. A method according to claim 3 wherein the common set of instructions also comprises an instruction to update a state pointer indicating whether the predefined number has been reached.
7. A method according to claim 6 , wherein the value of the state pointer is a function of the value of the input variable and/or of the number of instructions in the selected block of instructions.
8. A method according to claim 1 , wherein, in order to successively effect several blocks of instructions chosen from amongst the plural predefined blocks of instructions, each selected block of instructions is selected as a function of an input variable associated with an input index, and
the common set of instructions is executed a total number of times equal to a sum of the predefined numbers associated with each selected block of instructions.
9. A method according to claim 8 wherein one and the same block of instructions is selected several times according to the input variable associated with the input index.
10. A method according to claim 8 , wherein at least two of the following data items, (a) the value of a loop pointer, (b) the value of a state pointer, (c) the value of the input variable, and (d) the number of instructions of the selected block of instructions, are linked by one or more mathematical functions.
11. A method according to claim 10 , used in the implementation of an exponentiation calculation of the type B=A D , with D being an integer number of M bits, and each bit (D i ) of D corresponding to an input variable of input index i, comprising the following steps:
Initialisation:
R 0 ←1; R 1 ←A; i←M−1
As long as i≧0, repeat the common set of instructions:
k←(/s)×(k+1)+s×2×(/D i )
s←(k mod 2)+(k div 2)
γ(k,s): R 0 ←R 0 ×R k mod 2
i←i−s
Return R 0 ,
where R 0 and R 1 are values stored in two registers, respectively,
k is a loop pointer indicating a number of executions performed with the common set of instructions, and
s is a state pointer indicating whether the predefined number has been reached.
12. A method according to claim 10 , used in the implementation of an exponentiation calculation of the type B=A D , with D being an integer number of M bits, and each bit (D i ) of D corresponding to an input variable of input index i, comprising the following steps:
Initialisation:
R 0 ←1; R 1 ←A; i←M−1; k←1
As long as i≧0 repeat the common set of instructions:
k←(Di) AND (/k)
γ′(s,k): R 0 ←R 0 ×R k
i←i−(/k)
Return R 0 ,
where R 0 and R 1 are values stored in two registers, respectively,
k is a loop pointer indicating a number of executions performed with the common set of instructions, and
s is a state pointer indicating whether the predefined number has been reached.
13. A method according to claim 10 , used in the implementation of an exponentiation calculation of the type B=A D , with D being an integer number of M bits, and each bit (D i ) of D corresponding to an input variable of input index i, comprising the following steps:
Initialisation:
R 0 ←1; R 1 ←A; i ←0; k ←1
As long as i≦M−1, repeat the common set of instructions:
k←k⊕D i
γ(k): R k ←R k ×R 1
i←i+k
Return R0,
where R0 and R1 are values stored in two registers, respectively, and
k is a loop pointer indicating a number of executions performed with the common set of instructions.
14. A method according to claim 10 , used in the implementation of an exponentiation calculation of the type B=A D , with D being an integer number of M bits, and each bit (D i ) of D corresponding to an input variable of input index i, comprising the following steps:
Initialisation:
R 0 ←1; R 1 ←A; R 2 ←A 3 ;
D −1 ←0; i←M−1; s←1
As long as i≧0, repeat the common set of instructions:
k←(/s)×(k+1)+s×(D i +2×(D i AND D i-1 ))
s←/((k mod 2)⊕(k div 4))
γ(k,s): R 0 ←R 0 ×R s×(k div 2)
i←i−s×(k mod 2+1)
Return R 0 ,
where R 0 and R 1 are values stored in two registers, respectively,
k is a loop pointer indicating a number of executions performed with the common set of instructions, and
s is a state pointer indicating whether the predefined number has been reached.
15. A method according to claim 10 , used in the implementation of an exponentiation calculation of the type B=A D , with D being an integer number of M bits, and each bit (D i ) of D corresponding to an input variable of input index i, comprising the following steps:
Initialisation:
R 0 ←1; R 1 ←A; R 2 ←A 3 ;
D −1 ←0; i←M−1; s←1
As long as i≧0, repeat:
k←(/s)×(k+1)
s←s⊕D i ⊕((D i−1 AND (k mod 2))
R 0 ←R 0 ×R k×s
i←i−k×s−(/D i )
Return R0,
where R 0 and R 1 are values stored in two registers, respectively,
k is a loop pointer indicating a number of executions performed with the common set of instructions, and
s is a state pointer indicating whether the predefined number has been reached.
16. A method according to claim 8 , wherein at least two of the following data items, (a) the value of a loop pointer, (b) the value of a state pointer, (c) the value of the input variable, and (d) the number of instructions of the selected block of instructions, are linked and such linking is defined by a table with several inputs.
17. A method according to claim 16 , used in the implementation of an exponentiation calculation of the type B=A D , with D being an integer number of M bits, and each bit (D i ) of D corresponding to an input variable of input index i, comprising the following step:
As long as i≧0, repeat the common set of instructions:
k←(/s)×(k+1)+s×2×(/D i )
s←U(k,1)
γ(k,s): R 0 ←R 0 ×R U(k,0)
i←i−s
where (U(k,1)) is the following matrix:
(
U
(
k
,
1
)
)
0
≤
k
≤
2
0
≤
1
≤
1
=
(
0
0
1
1
0
1
)
,
R 0 and R 1 are values stored in two registers, respectively,
k is a loop pointer indicating a number of executions performed with the common set of instructions, and
s is a state pointer indicating whether the predefined number has been reached.
18. A method according to claim 16 , used in the implementation of an exponentiation calculation of the type B=A D according to the algorithm (M, M 3 ), with D being an integer number of M bits, and each bit (D i ) of D corresponding to an input variable of input index i, comprising the following step:
As long as i≧0, repeat the common set of instructions:
k←(/s)×(k+1)+s×(D i +2×(/D i AND D i−1 ))
s←U(k,2)
γ(k,s): R 0 ←R 0 ×R U(k,0) ;
i←i−U(k,1)
where (U(k,1)) is the following matrix:
(
U
(
k
,
1
)
)
0
≤
k
≤
5
0
≤
1
≤
2
=
(
0
1
1
0
0
0
1
1
1
0
0
0
0
0
0
2
2
1
)
,
R 0 and R 1 are values stored in two registers, respectively,
k is a loop pointer indicating a number of executions performed with the common set of instructions, and
s is a state pointer indicating whether the predefined number has been reached.
19. A method according to claim 16 , used in the implementation of a calculation on an elliptic curve in affine coordinates, a calculation using operations of the addition or doubling of points type, and in which the following step is performed:
As long as i≧0, repeat:
γ(k): R U(k,0) ←R 1 +R 3 ;
R U(k,1) ←R U(k,1) +R U(k,2) ;
R 5 ←R 2 /R 1 ; R U(k,3) ←R 1 +R 5 ;
R U(k,4) ←R 5 2 ;
R U(k,4) ←R U(k,4) +a;
R 1 ←R 1 +R U(k,5) ;
R 2 ←R 1 +R U(k,6) ; R 6 ←R 1 +R U(k,7) ;
R 5 ←R 5 ·R 6 ; R 2 ←R 2 +R 5
s←k−D i +1
k←(k+1)×(/s);
i←i−s;
where (U(k,1)) is the following matrix:
(U(k, 1)) (U(k, 1))
(
U
(
k
,
1
)
)
0
≤
k
≤
1
0
≤
1
≤
10
=
(
1
2
4
1
6
6
4
3
6
6
3
5
1
5
2
6
)
,
R 0 and R 1 are values stored in two registers, respectively,
k is a loop pointer indicating a number of executions performed with the common set of instructions, and
s is a state pointer indicating whether the predefined number has been reached.
20. A method according to claim 16 , wherein said several inputs comprise a matrix.
21. A method for obtaining an elementary set of instructions common to a plurality of predefined blocks of instructions, for implementing a cryptographic calculation method according to claim 1 , comprising the following steps:
E1: breaking down each predefined block of instructions into a series of elementary blocks that are equivalent in the context of a covert channel attack, and classifying all the elementary blocks,
E2: identifying a common elementary block that is equivalent to all the elementary blocks of all the predefined blocks of instructions,
E3: identifying a common block comprising at least the common elementary block previously identified and an instruction to update a loop pointer such that an execution of the common elementary block associated with the value of the loop pointer and an execution of the elementary block with a rank equal to the value of the loop pointer are identical.
22. A method according to claim 21 , wherein, during step E1, at least one fictional instruction is added to at least one predefined block of instructions.
23. A method according to claim 1 , wherein said electronic device is a chip card.