Method of executing a cryptographic protocol between two electronic entities

• US 8,612,761 B2
• Filed: 01/30/2001
• Issued: 12/17/2013
• Est. Priority Date: 01/31/2000
• Status: Active Grant

• Current Assignee: Oberthur Card Systems, S.A. (Advent International Corporation)
• Original Assignee: Oberthur Card Systems, S.A. (Advent International Corporation)
• Inventors: Akkar, Mehdi-Laurent, Dischamp, Paul
• Primary Examiner(s): Davis, Zachary A
• Application Number:
  US09/771,967
• Publication Number:
  US 20010012360A1
• Time in Patent Office: 4,704 Days
• Field of Search: 726/34, 380/29, 380/28, 380/30, 380/1, 713/189, 713/194, 713/168, 713/170
• US Class Current: 713/170
• CPC Class Codes: G06F 2207/7223 Randomisation as countermeasure against side channel attacks
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00
• CPC Class Codes: G06K 19/07363 by preventing analysis of the circuit, e.g. dynamic or static power analysis or current analysis
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• 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/0625 with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI

Abstract

Perfected cryptographic protocol making it possible to counter attacks based on the analysis of the current consumption during the execution of a DES or similar.

According to the invention, a message (M) is processed by two entities (A and B) and the entity (B) subject to attack executes a chain of operations known as DES in which it is chosen to carry out a given operation (O₁, O₂, O₃ . . . O_n) or the same operation complemented (Ō₁, Ō₂, Ō₃ . . . Ō_n), the choice being random.

Claims

1. A method of executing and validating a cryptographic protocol between a server entity and a microcircuit card in order to resist a Differential Power Analysis attack against the microcircuit card during execution of said cryptographic protocol, said method comprising the steps of:

storing a first set of instructions for a first chain of operations and a key in both the server entity and the microcircuit card, said first chain of operations implementing a Data Encryption Standard algorithm,

storing, at the microcircuit card, a second set of instructions for a second chain of operations based on the first chain of operations stored in said microcircuit card, said second chain of operations comprising a succession of operations each corresponding to a complement of a respective one of the operations in the first chain of operations,

sending a request from said server entity to said microcircuit card for generating a message and sending said message to the server entity,

executing, at the server entity, when said message from the microcircuit card is received by said server entity, said first set of instructions for the first chain of operations stored therein using said key and said message to obtain a server result,

identifying, in the microcircuit card, after reception of the request from the server entity, a selected chain of operations, said step of identifying comprising randomly choosing one of the following groups as said selected chain;

     1) all of the operations in said first chain of operations stored in the microcircuit card;

or

     2) all of the operations in said second chain of operations stored in the microcircuit card as well as an additional complementation instruction;

executing, in the microcircuit card, with said key and said message which has been sent by said microcircuit card to said server entity, instructions for the identified and selected chain of operations,

outputting a result of a last operation of the identified and selected chain of operations as a resultant message,

comparing the resultant message to the server result, and

validating the cryptographic protocol between the server entity and the microcircuit card when the server result and the resultant message are identical.

2. The method of claim 1, wherein at least one of said operations in the first chain of operations comprises an exclusive OR.

3. The method of claim 1, wherein at least one of said operations in the first chain of operations comprises an operation of bit permutation of an intermediate result obtained from execution of an operation of said first chain of operations preceding said operation of bit permutation within said first chain of operations.

4. The method of claim 1, wherein at least one of said operations in the first chain of operations comprises an operation of indexed access to a table.

5. The method of claim 1, wherein at least one of said operations in the first chain of operations comprises an operation which is stable with respect to the application of an exclusive OR function.

6. The method of claim 1, wherein at least one of said operations in the first chain of operations comprises an operation of transfer of an intermediate result obtained from execution of an operation of said first chain of operations preceding said operation of transfer within said first chain of operations, from one location to another one in a storage space.

7. The method of claim 1, wherein the step of randomly choosing comprises generating a random parameter that is used to identify which of said groups of operations to choose.

8. The method of claim 1, further comprising the step of computing a parameter which is equal to a difference between a number of times when one of said groups has been executed during preceding cycles and a number of times when the other of said groups has been executed during said preceding cycles, and when the difference exceeds a given threshold, decreasing the difference during a current cycle.

9. The method of claim 1, wherein the step of storing, at the microcircuit card, the second set of instructions comprises storing instructions for a succession of operations each corresponding to a complement byte by byte of one of the operations in the first chain of operations.

10. The method of claim 1, wherein the step of storing, at the microcircuit card, the second set of instructions comprises storing instructions for a succession of operations each corresponding to a complement bit by bit of one of the operations in the first chain of operations.

11. The method of claim 1, wherein the step of storing the second set of instructions for the second chain of operations further comprises a step of applying a permutation of the order of successive commutative operations in the first chain of operations before storing said second set of instructions.

12. The method of claim 11, wherein the step of determining a permutation of the order of successive commutative operations is carried out randomly.

13. A method of executing and validating a cryptographic protocol between a server entity and a microcircuit card in order to resist a Differential Power Analysis attack against the microcircuit card during execution of said cryptographic protocol, said method comprising the steps of:

storing a first set of instructions for a first chain of operations and a key in both the server entity and the microcircuit card, said first chain of operations implementing a Data Encryption Standard algorithm,

storing, at the microcircuit card, a second set of instructions for a second chain of operations based on the first chain of operations stored in said microcircuit card, said second chain of operations comprising a succession of operations each corresponding to a complement of a respective one of the operations in the first chain of operations,

sending a message from said server entity to said microcircuit card,

executing, at the server entity, when said message from the microcircuit card is received by said server entity, said first set of instructions for the first chain of operations stored therein using said key and said message to obtain a server result,

identifying, in the microcircuit card upon reception by said microcircuit card of said message received from the server entity, a selected chain of operations, said step of identifying comprising randomly selecting, for each operation of the first chain of operations in said microcircuit card, either said each operation or the corresponding operation in the second chain of operations in said microcircuit card;

executing, in the microcircuit card, instructions for the identified and selected chain of operations using said key and said message,

outputting a result of a last operation executed in said identified and selected chain of operations either in an uncomplemented state or a complemented state as a resultant message, depending on a number representative of successive random selections,

comparing the resultant message to the server result, and

validating the cryptographic protocol between the server entity and the microcircuit card when the server result and the resultant message are identical.

14. The method of claim 13, wherein the step of randomly selecting comprises generating a random parameter before randomly selecting said operations from either the first chain of operations or from the second chain of operations and updating a complementation counter, and the step of outputting the resultant message includes deciding to output the result of the last operation in the uncomplemented state or in the complemented state depending on a state of the complementation counter.

15. The method of claim 13, wherein the step of randomly selecting comprises generating a random parameter before randomly selecting said operations from either the first chain of operations or the second chain of operations and wherein said method further comprises updating, in parallel with each operation, information to be used during the step of outputting the resultant message to determine whether to output the result of the last operation in the uncomplemented state or the complemented state as the resultant message.

16. The method of claim 13, wherein the step of identifying further comprises a step of computing a parameter which is equal to a difference between a number of times when an operation of the first chain of operations is executed and a number of times when an operation of the second chain of operations is executed, and when the difference exceeds a given threshold, a next operation to be included in the selected chain of operations is selected from either the first chain of operations or the second chain of operations so as to decrease this difference.

17. The method of claim 13, wherein the step of executing in the microcircuit card further comprises a selection between using the message as the message is or using the message in complemented form.