Method to protect a cryptographic assembly by homographic masking

• US 8,074,076 B2
• Filed: 05/11/2005
• Issued: 12/06/2011
• Est. Priority Date: 05/11/2004
• Status: Expired due to Fees

• Current Assignee: Gemalto SA (Thales SA)
• Original Assignee: Gemalto SA (Thales SA)
• Inventors: Courtois, Nicolas
• Primary Examiner(s): Srivastava, Vivek
• Assistant Examiner(s): SONG, HEE K
• Application Number:
  US11/568,958
• Publication Number:
  US 20080022126A1
• Time in Patent Office: 2,400 Days
• Field of Search: 713/189, 380/28, 380/277, 380/252, 380/263, 380/286
• US Class Current: 713/189
• CPC Class Codes: G06F 2207/7233 Masking, e.g. (A**e)+r mod n
• CPC Class Codes: G06F 7/726 Inversion; Reciprocal calculation; Division of elements of a finite field
• CPC Class Codes: H04L 2209/046 of operations, operands or results of the operations
• CPC Class Codes: H04L 9/003 for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]
• CPC Class Codes: H04L 9/0631 Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms

Abstract

This invention relates to a method to protect an assembly implementing a cryptographic calculation process which uses a homographic function f of type:
f(z)=(az+b)/(cz+d) when (cz+d) is not equal to 0 and
f(−d/c)=a/c
the function f operating on masked variables, wherein, for any k, if x is an input and y=f(x+k) is an output of the function f, to pass directly from a masked value x+m_i (additive masking of type XOR) to a masked value y+m_j, the method consists in comprises of performing this operation using a composition of several transformations operating on GF(2^k) with addition of the infinite, defined as (ax+b)/(cx+d), and of transformations which exchange two points.

Claims

1. A method to protect an assembly having a processor and a memory, the method comprising:

operating the processor of the assembly according to instructions stored in the memory to cause the processor to perform the steps;

performing a cryptographic calculation process that uses a homographic function f of the type;

f(z)=(az+b)/(cz+d) when (cz+d) is not equal to 0 and

f(−

d/c)=a/c

by operating on masked variables, wherein, for any k, if x is an input and y=f(x+k) is an output of the function f, to pass directly from a masked value x+m_i (additive masking of type XOR) to a masked value y+m_j using a composition of;

several transformations F_i and G_j wherein i≧

1 and j>

1, each transformation F_i and G_j operating on the set K′

wherein K′

=K U oo, and wherein K=GF(2^k), each transformation F_i(z) and G_j(z) are defined as (az+b)/(cz+d) when (cz+d) is not equal to 0, F_i(−

d/c) and G_j(−

d/c)=oo, and F_j(oo) and G_j(oo)=a/c; and

the exchange of two points.

2. The method according to claim 1, wherein the operation f is the function Inv (Inverse in GF(2^k) with 0 mapped to 0 as in AES).

3. The method according to claim 1 or 2, wherein the calculation process protected is Rijndael or AES.

4. The method according to claim 3, wherein instead of additive masking of x by x+m, the masking is carried out for any homographic operation:

instead of x, the value of (ax+b)/(cx+d) is handled.

5. The method according to claim 1 or 2, wherein the operations are implemented using tables.

6. The method according to claim 1 or 2, used to protect an implementation in a smart card, USB token, cryptographic module or other specialised hardware.

7. The method according to claim 1 or 2, used to protect a software implementation with “

code obfuscation”

(a virtual smart card).

8. The method according to claim 1 or 2, used to protect an implementation executed in an obscure manner on a remote server (another type of virtual smart card).

9. The method of claim 1 wherein the transformation to exchange two points is an operation that exchanges u and v using an operation defined as E[u,v](x)=x when x is not equal to either u or v, and otherwise, E[u,v](u)=v and E[u,v](v)=u and wherein the transformation to exchange two points is introduced in the composition of several transformations F_i and G_j according to the composition:

F_—

1 o . . . o F_—

n o E[u,v]o G_—

1 o . . . G_—

n

wherein

u=G_—

1( . . . G_n(o)) and

v=G_—

1( . . . G_n(oo)).

10. Electronic system including storage means comprising:

a calculation process means to process a cryptographic calculation process which uses a homographic function f of type;

f(z)=(az+b)/(cz+d) when (cz+d) is not equal to 0 and

f(−

d/c)=a/c

by operating on masked variables, wherein the function f includes means, for any k, if x is an input and y=f(x+k) is an output of the function f, to pass directly from a masked value x+m_i (additive masking of type XOR) to a masked value y+m_j, to perform this operation using a composition of;

several transformations F_i and G_j wherein i≧

1 and j≧

1, each transformation F_i and G_j operating on the set K′

wherein K′

=K ∪

oo, and wherein K=GF(2^k), each transformation F_i(z) and G_j(z) are defined as (az+b)/(cz+d) when (cz+d) is not equal to 0, F_i(−

d/c) and G_j(−

d/c)=oo, and F_j(oo) and G_j(oo)=a/c and

the exchange of two points.

11. The electronic system of claim 10 wherein the transformation to exchange two points is an operation that exchanges a and b using an operation defined as E[u,v](x)=x when x is not equal to either a or b, and otherwise, E[u,v](u)=v and E[u,v](v)=u and wherein the transformation to exchange two points is introduced in the composition of several transformations F_i and G_j according to the composition:

F_—

1 o . . . o F_—

n o E[u,v]o G_—

1 o . . . G_—

n

wherein

u=G_—

1( . . . G_n(o)) and

v=G_—

1( . . . G_n(oo)).

12. A program storage medium readable by a computer, comprising a program of instructions executable by the computer to perform method steps to process a cryptographic calculation process which uses a homographic function f of type:

f(z)=(az+b)/(cz+d) when (cz+d) is not equal to 0 and

f(−

d/c)=a/c

by operating on masked variables, wherein the function f includes means, for any k, if x is an input and y=f(x+k) is an output of the function f, to pass directly from a masked value x+m_i (additive masking of type XOR) to a masked value y+m_j, to perform this operation using a composition of;

several transformations F_i and G_j wherein i≧

1 and j≧

1, each transformation F_i and G_j operating on the set K′

wherein K′

=K ∪

oo, and wherein K=GF(2^k), each transformation F_i(z) and G_j(z) are defined as (az+b)/(cz+d) when (cz+d) is not equal to 0, F_i(−

d/c) and G_j(−

d/c)=oo, and F_j(oo) and G_j(oo)=a/c and

the exchange of two points.

13. The program storage medium according to claim 12, wherein the operation f is the function Inv (Inverse in GF(2^k) with 0 mapped to 0 as in AES).

14. The program storage medium according to claim 12, wherein the calculation process protected is Rijndael or AES.

15. The program storage medium according to claim 14, wherein instead of additive masking of x by x+m, the masking is carried out for any homographic operation:

instead of x, the value of (ax+b)/(cx+d) is handled.

16. The program storage medium according to claim 12, wherein the operations are implemented using tables.

17. The program storage medium of claim 12 wherein the transformation to exchange two points is an operation that exchanges a and b using an operation defined as E[u,v](x)=x when x is not equal to either u or v, and otherwise, E[u,v](u)=v and E[u,v](v)=u and wherein the transformation to exchange two points is introduced in the composition of several transformations F_i and G_j according to the composition:

F_—

1 o . . . o F_—

n o E[u,v]o G_—

1 o . . . G_—

n

wherein

u=G_—

1( . . . G_n(o)) and

v=G_—

1( . . . G_n(oo)).

18. A method to protect an assembly having a processor and a memory, the method performing a cryptographic calculation process, comprising:

define a set of transformations F_i(z) and G_j(z) operating on the set K′

wherein K′

=K Li oo, and wherein K=GF(2^k) and wherein each transformation F_i(z) and G_j(z) has the form

F_i(z) and G_j(z)=(az+b)/(cz+d) when (cz+d) is not equal to 0,

F_i(−

d/c) and G_j(−

d/c)=oo, and

F_j(oo) and G_j(oo)=a/c;

wherein the cryptographic calculation process includes operating the processor of the assembly according to instructions stored in the memory to cause the processor to perform the steps;

computing a function Inv defined as a composition of a plurality of transformations F_i(z) and G_j(z), i=1 to n by performing the composition

F_—

1 o . . . o F_—

n o E[u,v] o G_—

1 o . . . G_—

n

wherein

E[u,v](x)=x if x not equal to either u or v,

E[u,v](u)=v,

E[u,v](v)=u;

and wherein

u=G_—

1( . . . G_n(o)) and

v=G_—

1( . . . G_n(oo)).