INFECTIVE COUNTERMEASURES

Abstract

The invention proposes a novel type of infective countermeasure against fault injection attacks. Instead of determining the injected error before amplifying it, the novel countermeasure applies the same diffusion function to two intermediate ciphers obtained by executing a cryptographic operation on an input. The error is therefore amplified within the same intermediate ciphers, referred to as infective ciphers after diffusion. It is then possible to use diffusion functions which do not map the cipher 0 as an output equal to 0. A cipher recomposed from bits of undiffused ciphers is also generated. These infective and recomposed ciphers are XOR-combined to provide an output cipher. This approach makes it possible to adapt, by simple duplication of the pairs and associated specific diffusion functions, the protection offered by the countermeasure to a desired number of injected faults.

Claims

1. A method for cryptographic processing of an input message into an output message, comprising the following steps implemented by a processor: executing several times the same cryptographic operation on the input message (E) in order to obtain one or more pairs of intermediate messages, for each pair, applying a single diffusion function to the two intermediate messages of the pair in order to obtain two infective messages, and combining the infective messages with a recomposed message obtained by selecting bits from one or more first messages resulting from the executions of the cryptographic operation, in order to obtain the output message.

2. The method according to claim 1, wherein the diffusion function differs from one pair of intermediate messages to another.

3. The method according to claim 2, wherein the diffusion function of one pair is based on a first parameter specific to said pair, for example a unique identifier of said pair.

4. The method according to claim 1, wherein the diffusion functions of the pairs are based on a second parameter which varies in order to obtain a new output message from a new input message.

5. The method according to claim 1, wherein each intermediate message is a first message resulting directly from one of the executions of the cryptographic operation.

6. The method according to claim 1, wherein each intermediate message is a message concatenating, according to a corresponding concatenation profile, several or all of the first messages resulting directly from the executions of the cryptographic operation.

7. The method according to claim 6, wherein the intermediate messages of two different pairs differ from one another by a different rotation of the first messages within a single master message concatenating all the first messages.

8. The method according to claim 6, wherein the intermediate messages (C.sub.i) are formed of distinct pairs of first messages.

9. The method according to claim 6, wherein at most $.Math.\frac{n}{2}.Math.$ disjoint pairs of concatenation profiles are symmetrical for a group of n first messages, for any n between 2 and d, with d+1 the total number of executions of the cryptographic operation and └x┘ the floor of x, a pair of concatenation profiles being said to be symmetrical for the group of n first messages when its two concatenation profiles use the same message positions in the concatenation to position the first messages originating from the group of n first messages.

10. The method according to claim 9, wherein the recomposed message is not only formed by one or more of said first n messages (c.sub.i) of the group when $.Math.\frac{n}{2}.Math.$ disjoint pairs of concatenation profiles are symmetrical.

11. The method according to claim 1, wherein the combination step comprises the application of the EXCLUSIVE OR logical operator between the different infective messages and the recomposed message.

12. The method according to claim 11, wherein the combination step comprises a first initial sub-step combining the recomposed message with one of the infective messages and one or more subsequent sub-steps combining the result of the initial sub-step with the other infective messages.

13. The method according to claim 1, wherein the recomposed message is one of the first messages resulting directly from one of the executions of the cryptographic operation.

14. The method according to claim 1, wherein the recomposed message is formed of bits originating from several or all of the first messages resulting directly from the executions of the cryptographic operation.

15. A cryptographic processing device comprising a processor configured to: execute, several times, a single cryptographic operation on an input message in order to obtain one or more pairs of intermediate messages, for each pair, apply a single diffusion function to the two intermediate messages of the pair in order to obtain two infective messages, and combine the infective messages with a recomposed message obtained by selecting bits from one or more first messages resulting from the executions of the cryptographic operation, in order to obtain an output message.

16. A non-transient computer-readable medium for storing a program which, when it is executed by a cryptographic processing device, causes the cryptographic processing device to perform the method according to claim 1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0057] Other particular features and advantages of the invention will become more apparent in the following description, illustrated by the appended figures which depict examples of non-limiting embodiments.

[0058] FIG. 1 schematically shows the principle of known infective countermeasures.

[0059] FIG. 2 schematically depicts a data-processing device forming a cryptographic system in which the present invention is implemented.

[0060] FIG. 3 depicts a smart card which constitutes an example of a cryptographic processing device for an implementation of the invention as depicted in FIG. 1.

[0061] FIG. 4 schematically illustrates the general principle of the improved infective countermeasure according to the invention.

[0062] FIG. 5 schematically illustrates first embodiments of the improved countermeasure according to the invention.

[0063] FIG. 6 illustrates a variant of the countermeasure in FIG. 5 resistant to the injection of one fault.

[0064] FIG. 7 illustrates an improved infective countermeasure variant resistant to the injection of two faults.

[0065] FIG. 8 illustrates an improved infective countermeasure resistant to the injection of d faults (d integer greater than or equal to 1).

[0066] FIG. 9 schematically illustrates second embodiments of the improved countermeasure according to the invention.

DETAILED DESCRIPTION

[0067] The invention proposes a novel type of infective countermeasures for securing cryptographic processing devices against fault injection attacks.

[0068] Instead of determining the injected error before amplifying it, the novel countermeasure applies a single diffusion function to two intermediate messages obtained by executing a cryptographic operation on an input message. The error is therefore amplified within the intermediate messages themselves, referred to as infective messages after diffusion.

[0069] It is thus possible to overcome the constraint of the diffusion functions aimed at mapping an intermediate message 0 as an “infective” message 0. The result is a greater choice of available diffusion functions.

[0070] A message recomposed from bits of messages resulting from the executions of the cryptographic operation is also generated.

[0071] The infective and recomposed messages are XOR-combined to provide an output message. This operation by pairs of intermediate messages and associated diffusion function makes it possible, by simple duplication of this assembly with a different diffusion function each time, to scale the countermeasure to the desired protection level, i.e. to the number of injection faults which the countermeasure must resist.

[0072] The cryptographic processing may receive a cleartext message as input and thus generate an encrypted message or “cipher” as output. This is the case for example for encryption or digital signature type cryptographic operations. In this case, the intermediate, infective and recomposed messages are also encrypted.

[0073] As a variant, the cryptographic processing may receive as input an encrypted message and thus generate a decrypted or “cleartext” message as output. This is the case, for example, for decryption-type cryptographic operations. In this case, the intermediate, infective and recomposed messages are also cleartext messages.

[0074] To clarify the words hereunder, reference is principally made to first, intermediate, infective, recomposed and “cipher”-type output messages (in which case the input message is in “cleartext”), but the invention also applies to the case of “cleartext”-type messages resulting from the decryption of an encrypted input message. Generally, a person skilled in the art is capable of applying the following teachings to any type of message (cleartext or encrypted) instead of the “ciphers” specifically indicated.

[0075] FIG. 2 schematically depicts a data-processing device 40 forming a cryptographic system in which the present invention is implemented. This device 40 comprises a microprocessor 41, with which is associated on the one hand a random access memory 42, for example by means of a bus 43, and on the other hand a non-volatile memory 44 (for example of the EEPROM type), for example through a bus 45. The buses 43 and 45 may be one and the same bus. The microprocessor 41 may be a secure cryptoprocessor.

[0076] The data-processing device 40, and specifically the microprocessor 41 which it incorporates, may exchange data with external devices by means of a communication interface 50.

[0077] FIG. 2 schematically depicts the transmission of input data X received from an external device (not shown) and transmitted from the communication interface 50 to the microprocessor 41. In a similar manner, the transmission of output data Y from the microprocessor 41 to the communication interface 50 bound for the external device is depicted. This output data Y originates from a processing of data by the microprocessor 41, generally on the input data X using secret data 60 internal to the system, for example a private key stored in memory.

[0078] The input data X and output data Y may be the input E and output data S of a cryptographic processing algorithm according to the invention, typically a cleartext message (or alternatively a cipher) at the input and an encrypted message (or alternatively a cleartext message) at the output. As a variant, other processing operations may be foreseen on the input data X and/or on the cipher S in the device 40 such that data X, Y and E, S may be, in whole or in part, different.

[0079] Although, in the illustration, the input data and the output data appear on two different arrows, the physical means which facilitate the communication between the microprocessor 41 and the interface 50 may be provided by unique means, for example a serial communication port or a bus.

[0080] The microprocessor 41 is able to execute a software (or computer program) which enables the data-processing device 40 to execute a method compliant with the invention, examples of which are given below with respect to FIGS. 4 to 9. The software consists of a series of command instructions of the microprocessor 41 which are, for example, stored in the memory 44.

[0081] As a variant, the microprocessor 41/non-volatile memory 44/random-access memory 42 assembly may be replaced by an application-specific circuit which then comprises means for implementing the various steps of the method according to the invention.

[0082] Data-processing devices 40 include secure elements which may be embedded (embedded SE or eSE) or not, for example smart cards, UICC cards (or eUICC—for embedded Universal Integrated Circuit Card) or SIM cards (or eSIM).

[0083] FIG. 3 depicts a smart card which constitutes an example of a cryptographic processing device for an implementation of the invention as depicted in FIG. 2. In this case, the communication interface 50 is produced for example by means of the contacts of the smart card. The smart card incorporates a microprocessor 41, a random access memory 42 and a non-volatile memory 44 as is depicted in FIG. 1.

[0084] This smart card is, for example, compliant with standard ISO 7816 and equipped with a secure microcontroller which groups together the microprocessor (or CPU) 41 and the random access memory 42.

[0085] As a variant, the cryptographic processing device may be included in a USB stick, a document or a paper information medium comprising, in one of its sheets, a microcircuit associated with contactless communication means. In a preferred manner, it is a portable or pocket electronic entity. Naturally, the invention also applies to a cryptographic processing device equipping a personal computer or a server.

[0086] Such a cryptographic processing device may, for example, receive a binary message E to be processed (encryption or signature for example) and return a cipher S.

[0087] In the following examples, reference is principally made to a cryptographic operation OPE of AES (Advanced Encryption Standard) type to encrypt the message E. The size of the latter is, for example, L=128 bits (i.e. 16 bytes).

[0088] Naturally, the invention applies to any type of cryptographic operation, whether it be encryption and/or signature. Similarly, the invention applies to any size L (in bits) of input message E, preferentially an integer (1 or more) of bytes.

[0089] FIG. 4 schematically illustrates the general principle of the improved countermeasure according to the invention.

[0090] In contrast to the approach of the prior art, it is no longer sought to obtain the injected error ‘e’ in order to modify it by the diffusion function. According to the invention, the injected error is nonetheless diffused but within intermediate ciphers C.sub.0 and C.sub.1 themselves originating (via the function F) from the first ciphers c.sub.0 and c.sub.1 directly obtained from the executions of the cryptographic operation on the input message E.

[0091] The final recombination of different ciphers, for example via the XORs 10, 11, makes it possible to reinject the diffused error in one of the ciphers.

[0092] The execution of the same cryptographic operation OPE can be found several times on the input data E to obtain herein a pair of intermediate ciphers C.sub.0, C.sub.1, but more generally, as disclosed hereinafter, one or more pairs of intermediate messages.

[0093] In a simple manner and according to the embodiments, the intermediate ciphers may be simply the first ciphers resulting directly from the executions of the cryptographic operation, i.e. C.sub.0=c.sub.0 and C.sub.1=c.sub.1, or may combine, mix or concatenate (“∥” being the concatenation operator) the first ciphers resulting from these executions, for example C.sub.0=c.sub.0∥c.sub.1 and C.sub.1=c.sub.1∥c.sub.0.

[0094] Diffusion processing is then performed for each pair of intermediate ciphers.

[0095] The same diffusion function is applied to the two intermediate ciphers of the pair. This makes it possible to obtain two infective ciphers g.sub.0, g.sub.1. In particular, it is possible to use any type of diffusion function, and notably those which do not map the intermediate cipher 0 as the infective cipher 0. As disclosed below, the diffusion functions differ from one pair of intermediate ciphers to another, in cases where several pairs of intermediate ciphers could be generated.

[0096] Then the infective ciphers g.sub.0, g.sub.1 are combined with a recomposed cipher C.sub.rec(Rec function) originating from a selection of bits of one or more first ciphers resulting from the executions of the cryptographic operation (herein c.sub.0 and c.sub.1), optionally recovered via the intermediate ciphers concatenating them. The output cipher S is thus obtained.

[0097] As indicated in the Figure, the infective and recomposed ciphers are typically combined using EXCLUSIVE OR (or XOR) logical operators, which simplifies the operations. As a variant, it is possible to combine these different ciphers using a operator and its opposite ‘-’: C.sub.rec+g.sub.0−g.sub.1.

[0098] It is also indicated in the Figure that this combination initially combines the recomposed cipher with one of the infective ciphers (herein g.sub.0 by means of XOR 10) and then subsequently combines the result with the other infective cipher(s) (herein g.sub.1 by means of the XOR 11).

[0099] If the countermeasure in the Figure provides protection against fault injection attacks, this order in the combination of ciphers additionally protects against a second fault attacking one of the XORs.

[0100] The diffusion function f.sub.diff preferably returns an infective cipher of length L (in number of bits) in order to be able to perform the combination operations (XOR) on ciphers of the same length. If a diffusion function returns an infective cipher with a greater length than L, the XOR (combination) with a cipher is performed on the common length (the bits present in the two combined ciphers).

[0101] In one embodiment, the diffusion function f.sub.diff is a pseudorandom number generator (PRNG) based on one or more keys or “parameters”, for example three rounds of AES (the PRNG is thus AES-based). Naturally, other types of diffusion function may be used, typically including the hash functions.

[0102] Pseudorandom generators are suited to cryptographic processing operations in that they are capable of producing an infective cipher likely to be barely discernible from a completely random value. Such PRNG generators include Yarrow, Fortuna, Blum Blum Shub, ISAAC generators or even multiple rounds of AES.

[0103] A first so-called “pair” key or parameter is specific to said pair, for example a unique identifier of said pair. This makes it possible to obtain different diffusion functions for the pairs using the same diffusion algorithm. This key pair is optional for the case of an implementation having a single pair of intermediate ciphers.

[0104] A second so-called “execution” key or parameter is modified from one execution of the countermeasure to another, i.e. it varies in order to obtain each new output message from a new input message, i.e. at each new execution of the countermeasure. This gives the invention a robustness over several executions of the countermeasure, using the same diffusion algorithm. By way of example, it may be a random value generated by the cryptographic system. Preferably, the same execution key is used for all the diffusion functions during the same execution of the countermeasure. This makes it possible to limit the generation of random values to a single random value by executing the countermeasure.

[0105] Naturally, the two keys can be manipulated together in the form of a single key (the result, for example, of the concatenation of two keys).

[0106] As mentioned hereinbefore, the invention proposes embodiments where each intermediate cipher (more generally message) is a first cipher resulting directly from one of the executions of the cryptographic operation. The function F in FIG. 4 is, in this case, the identity: C.sub.1=c.sub.1. These embodiments are illustrated by FIGS. 5 to 8.

[0107] The countermeasure illustrated by FIG. 5 is resistant to a fault injection, optionally over several executions of the countermeasure insofar as the execution key is changed each time the countermeasure is executed.

[0108] The cryptographic operation OPE, for example the AES, is executed twice on the input data E of length L, resulting in obtaining two first ciphers c.sub.0, c.sub.1 forming a single pair (C.sub.0=c.sub.0, C.sub.1=c.sub.1) of intermediate ciphers of length L. Due to the identity function F, the terms “first cipher” and “intermediate cipher” are synonymous.

[0109] A single diffusion function f.sub.diff, for example a PRNG such as three rounds of AES, is applied to the two intermediate ciphers C.sub.0=c.sub.0, C.sub.1=c.sub.1 resulting in obtaining two infective ciphers g.sub.0, g.sub.1 preferably of length L. The diffusion function f.sub.diff amplifies the potential error that one of the intermediate ciphers may contain.

[0110] The recomposed cipher is formed of one of the first two ciphers, herein Rec(c.sub.0, c.sub.1)=c.sub.0. Also, the recomposition function Rec is, in this case, the identity function of one of the inputs thereof. The processor occupancy time is thus reduced for the infective countermeasure against a single injected fault.

[0111] The infective ciphers g.sub.0, g.sub.1 and the recomposed cipher C.sub.rec=c.sub.0 are then combined to obtain the output cipher S of length L. As illustrated, this combination may be performed using the XORs 10, 11: S=g.sub.0⊕c.sub.0⊕g.sub.1. Preferably, the following steps are performed:

S←g.sub.0⊕c.sub.0

S←S⊕g.sub.1

[0112] In this configuration, the recomposed cipher c.sub.0 is first combined with one of the infective ciphers g.sub.0 and g.sub.1 rather than combining the infective ciphers together before introducing c.sub.0. This additionally provides protection against the injection of an additional error attacking one of the XORs.

[0113] FIG. 6 illustrates an improved infective countermeasure variant resistant to the injection of a fault. Again, this countermeasure is resistant to attacks (injection of a single fault) on several executions thereof, insofar as the execution key is provided and changed each time the countermeasure is executed.

[0114] As for the previous Figure, the cryptographic operation OPE, for example the AES, is executed twice on the input data E of length L, resulting in obtaining the pair of intermediate ciphers (C.sub.0=c.sub.0, C.sub.1=c.sub.1) of length L. Due to the identity function F, the terms “first cipher” and “intermediate cipher” are synonymous.

[0115] The same diffusion function f.sub.diff is applied thereto resulting in obtaining two infective ciphers g.sub.0, g.sub.1.

[0116] The two ciphers C.sub.0=c.sub.0, C.sub.1=c.sub.1 are also processed using the recomposition function Rec to form the recomposed cipher C.sub.rec of length L by selecting bits from the first ciphers c.sub.0, c.sub.1. If the first ciphers directly obtained from the executions of the operation OPE are combined herein, the result is identical with the intermediate ciphers C.sub.0, C.sub.1 since the function F is the identity.

[0117] Each bit of the recomposed cipher C.sub.rec originates from one of the first ciphers c.sub.0, c.sub.1 and occupies the same position in the recomposed cipher as its position in the first cipher from which it originates. In other words, C.sub.rec(i)=c.sub.0(i) or c.sub.1(i), with x(i) representing the bit b.sub.i of index i in the cipher x. Generally the cipher x of length L is formed of bits {b.sub.L-1, b.sub.L-2, . . . , b.sub.2, b.sub.1, b.sub.0}.

[0118] In this variant of FIG. 6, the recomposed cipher C.sub.rec is formed of bits originating from the first two ciphers of the pair, i.e. there is at least one i and one j such that C.sub.rec(i) originates from c.sub.0 and C.sub.rec(j) originates from c.sub.1.

[0119] The recomposition function preferably (but not necessarily) uses equitably the same number of bits of each c.sub.i.

[0120] Several selection schemes may be envisaged. For example, half of the bits of C.sub.rec originate from each first cipher c.sub.0, c.sub.1. However, another distribution of bits may be envisaged, for example providing at least one bit of each cipher c.sub.0, c.sub.1 inside one or more or all of the bytes forming the recomposed cipher C.sub.rec.

[0121] By way of example, one in two bits may originate from one or other of the ciphers c.sub.0, c.sub.1. For example, C.sub.rec(2i)=c.sub.0(2i) and C.sub.rec(2i+1)=c.sub.1(2i+1) irrespective of L/2>i≥0 (L length of ciphers), also written as follows in Boolean notation:

(c.sub.0∧0xAAA . . . AA)⊕(c.sub.1∧0x555 . . . 55)

with ∧ the AND operator and ⊕ the EXCLUSIVE OR operator (XOR). Other distributions of bits may be envisaged, even being split in half. For example, (c.sub.0∧0x0F0F . . . 0F)⊕(c.sub.1∧0xF0F0 . . . F0) and more generally (c.sub.0∧a.sub.0)⊕(c.sub.1∧a.sub.1), where a.sub.0⊕a.sub.1=0xFFFF . . . FF.

[0122] In the absence of an injected fault, C.sub.rec=c.sub.0=c.sub.1 is found. In the presence of an injected fault, C.sub.rec is likely to be different from c.sub.0 and/or c.sub.1.

[0123] The infective ciphers g.sub.0, g.sub.1 and the recomposed cipher C.sub.rec are then combined to obtain the output cipher S. As illustrated, this combination may be produced using the XORs 10, 11: S=g.sub.0⊕Rec(c.sub.0, c.sub.1)⊕g.sub.1. Preferably, the following steps are performed:

S←Rec(c.sub.0,c.sub.1)

S←g.sub.0⊕S

S←S⊕g.sub.1

[0124] In this configuration, the recomposed cipher C.sub.rec is first combined with one of the infective ciphers g.sub.0 and g.sub.1 rather than combining the infective ciphers together before introducing C.sub.rec.

[0125] FIG. 7 illustrates an improved infective countermeasure variant resistant to the injection of two faults on an execution of the countermeasure. This countermeasure is resistant to fault injection attacks on several executions thereof where the execution key is provided and changed each time the countermeasure is executed.

[0126] The cryptographic operation OPE, for example the AES, is executed four times on the input data E, resulting in obtaining four first ciphers c.sub.0 to c.sub.3, four intermediate ciphers C.sub.0=c.sub.0 to C.sub.3=c.sub.3 forming two pairs of intermediate ciphers (c.sub.0, c.sub.1) and (c.sub.2, c.sub.3), i.e. generically (c.sub.2i, c.sub.2i+1) for the pair “p.sub.i”. Naturally, this organization of pairs by consecutive indices is only illustrative, for the purposes of simplifying the explanations. Due to the identity function F, the terms “first cipher” and “intermediate cipher” are synonymous.

[0127] For each pair “p.sub.i”, a single diffusion function f.sub.diff-i is applied to the two ciphers (c.sub.2i, c.sub.2i+1) of the pair. Four infective ciphers g.sub.0 to g.sub.3 are thus obtained.

[0128] f.sub.diff-0 is the diffusion function for the first pair p.sub.0 and f.sub.diff-1 is that of the second pair p.sub.1. As noted above, these diffusion functions may for example be PRNGs, notably AES-based PRNGs, such as three rounds of AES using different keys.

[0129] In some embodiments, the diffusion functions are based on a key pair and on an execution key. By way of example, the key pair and/or the execution key may be concatenated or XORed with the cipher at the input of the diffusion function. This makes it possible to easily obtain different diffusion functions from one pair to another and from one execution of the countermeasure to another, whilst executing the same diffusion algorithm on the concatenated or XORed input.

[0130] The use of pseudorandom number generators based on a different key from one pair of ciphers to another is only one embodiment of the invention. Generally, the diffusion function is different from one pair of ciphers to another. Additionally, it also varies from one execution of the countermeasure to another.

[0131] The four ciphers c.sub.0 to c.sub.3 are also processed using a recomposition function Rec, the purpose of which is to form a recomposed cipher C.sub.rec by selecting bits from the ciphers c.sub.0 to c.sub.3. Each bit of the recomposed cipher C.sub.rec originates from one of the ciphers c.sub.0 to c.sub.3 and occupies the same position in the recomposed cipher as its position in the cipher from which it originates. In other words, C.sub.rec(i)=c.sub.0(i) or c.sub.1(i) or c.sub.2(i) or c.sub.3(i).

[0132] For security reasons, the recomposed cipher C.sub.rec is preferentially formed of bits originating from ciphers from at least two different pairs, and not only from two different ciphers.

[0133] In the case of the Figure which only presents two pairs of ciphers, the recomposed cipher C.sub.rec is formed of bits originating from ciphers of each of the pairs.

[0134] The recomposition function may be selected based on the attacks to be countered. By way of example, DFA (Differential Fault Analysis) type attacks on an AES-128 cryptographic operation are based on modifying four bytes of the cipher and exploiting these modifications.

[0135] In a general manner, the attacks generally exploit modifications to one, several or even all the bytes of the cipher.

[0136] In this context, the recomposition function may be selected such that at least one or more or each byte of the recomposed cipher C.sub.rec is formed of bits originating from ciphers of at least two different pairs, or even more than two pairs or all of the pairs when this is possible (e.g. 8 pairs maximum). This makes it possible to secure the countermeasure against certain attacks injecting the same fault into the executions of the operation OPE corresponding to a single pair of ciphers.

[0137] As noted above, several selection/recomposition schemes may be envisaged.

[0138] The recomposition function preferably (but not necessarily) uses equitably the same number of bits of each c.sub.i or of each pair p.sub.i. For example, a quarter of the bits of C.sub.rec may originate from each cipher c.sub.0 to c.sub.3. As a variant, half of the bits of C.sub.rec may originate from the ciphers of each pair p.sub.i. However, another distribution of bits may be envisaged, for example providing at least one bit of each cipher c.sub.0 to c.sub.3 inside one or more or each byte forming the recomposed cipher C.sub.rec.

[0139] By way of example, one in four bits may originate from each of the ciphers c.sub.0 to c.sub.3. For example,

(c.sub.0∧0x888 . . . 88)⊕(c.sub.1∧0x222 . . . 22)⊕(c.sub.2∧0x444 . . . 44)⊕(c.sub.3∧0x111 . . . 11).

This example illustrates the case of a recomposition function which does not use two consecutive bits originating from two ciphers of the same pair.

[0140] Other distributions of bits may be envisaged, even being split into four. For example,

(c.sub.0∧0xF000F000 . . . F000)⊕(c.sub.1∧0x0F000F00 . . . 0F00)⊕(c.sub.2∧0x00F000F0 . . . 00F0)⊕(c.sub.3∧0x000F000F . . . 000F)

but also

(c.sub.0∧0xFF000000 . . . FF000000)⊕(c.sub.1∧0x00FF0000 . . . 00FF0000)⊕(c.sub.2∧0x0000FF00 . . . 0000FF00)⊕(c.sub.3∧0x000000FF . . . 000000FF),

and more generally

(c.sub.0∧a.sub.0)⊕(c.sub.1∧a.sub.1)⊕(c.sub.2∧a.sub.2)⊕(c.sub.3∧a.sub.3)

with ⊕.sub.i=0.sup.3 a.sub.i=0xFFFF . . . FF.

[0141] In one embodiment improving the robustness, a.sub.t∧a.sub.j≠i=0 (for any values of i and j) ensuring that a bit is only recovered from a single cipher.

[0142] In another embodiment, optionally capable of being combined, a.sub.0∨a.sub.1≠0 and a.sub.2∨a.sub.3≠0 (V being the Boolean operator OR), ensuring that at least one bit is taken from each pair.

[0143] In the absence of an injected fault, C.sub.rec=c.sub.0=c.sub.1=c.sub.2=c.sub.3 is found. In the presence of an injected fault, C.sub.rec is likely to be different from c.sub.0 to c.sub.3.

[0144] The infective ciphers g.sub.0 to g.sub.3 and the recomposed cipher C.sub.rec are then combined to obtain the output cipher S. As illustrated, this combination may be produced using the XORs 10, 11: S=g.sub.0⊕Rec(c.sub.0, c.sub.1, c.sub.2, c.sub.3)⊕g.sub.1⊕g.sub.2⊕g.sub.3.

[0145] Naturally, the infective ciphers may be used in a different order. Additionally, if it is preferable to alternate the infective ciphers originating from different pairs, it is equally possible to produce the first XORs with the two ciphers of a single pair, then the last XORs with the two ciphers of the other pair.

[0146] Preferably, the following steps are performed:

S←Rec(c.sub.0,c.sub.1,c.sub.2,c.sub.3)

S←g.sub.0⊕S

S←S⊕g.sub.1

S←S⊕g.sub.2

S←S⊕g.sub.3

[0147] In this configuration, the recomposed cipher C.sub.rec is first combined with one of the infective ciphers g.sub.0 to g.sub.3 rather than combining two or more infective ciphers together before introducing C.sub.rec. The recomposed cipher C.sub.rec is combined with one of the infective ciphers during an initial sub-step, then, during several successive subsequent sub-steps, each of the other infective ciphers is combined with the result of the previous sub-step.

[0148] This embodiment in FIG. 7 shows that the improved countermeasure according to the invention can be scaled to the desired security level (in terms of the number of injected faults against which the countermeasure is effective). This scaling is performed by duplicating executions of the operation OPE to add a new pair p.sub.i of intermediate ciphers and by using a novel dedicated diffusion function f.sub.diff-i.

[0149] Also, it is possible to obtain an improved infective countermeasure which is resistant to any number of injected faults.

[0150] As such, FIG. 8 illustrates the improved infective countermeasure resistant to the injection of d faults (d integer greater than or equal to 1) on a single execution of the countermeasure. It is therefore particularly well suited to mechanisms such as the generation of session keys.

[0151] Additionally, this countermeasure is resistant to fault injection attacks on several executions thereof where the execution key is provided and changed each time the countermeasure is executed.

[0152] The maximum value of d may depend on the OPE algorithm to be protected and/or on the type of attack being targeted. For example, since AES is sensitive to an attack which targets 32 bits of the incorrect cipher, the maximum value for d is 31. In other words, this maximum value is the minimum number of bits of the cipher on which the attack can be based, minus 1.

[0153] The cryptographic operation OPE, for example AES, is executed 2d times on the input data E, resulting in obtaining 2d intermediate ciphers C.sub.0 to C.sub.2d-1 equal to the 2d first ciphers c.sub.0 to c.sub.2d-1 directly originating from the executions of the operation OPE. They form d pairs of ciphers (c.sub.0, c.sub.1), (c.sub.2, c.sub.3) . . . (c.sub.2a-2, c.sub.2d-1), i.e. generically (c.sub.2i, c.sub.2i+1) for the pair p.sub.i. Naturally, this organization of pairs by consecutive indices is only illustrative, for the purposes of simplifying the explanations. Again, due to the identity function F, the terms “first cipher” and “intermediate cipher” are synonymous.

[0154] The multiple executions of the operation OPE may be in whole or in part simultaneous and/or in sequence.

[0155] For each pair p.sub.i (0≤i<d), a single diffusion function f.sub.diff-i, for example a PRNG such as three rounds of AES using a key pair K.sub.i (K.sub.i≠K.sub.j for any i, j with i≠j) and optionally an execution key (a random value), is applied to the two ciphers (c.sub.2i, c.sub.2i+1) of the pair. Two infective ciphers g.sub.2i to g.sub.2i+1 per pair are thus obtained, i.e. a total of 2d infective ciphers g.sub.0 to g.sub.2d-1.

[0156] The explanations provided above on the diffusion functions also apply to this embodiment. For example, the use of pseudorandom number generators based on a different key K.sub.i from one pair of ciphers to another is only one embodiment of the invention. Generally, the diffusion function is different from one pair of ciphers to another. One or more diffusion functions used may be PRNGs while one or more others may be one or more other types, for example hash functions. Also, the key pair and/or the execution key may be concatenated or XORed with the intermediate cipher at the input of the diffusion function.

[0157] The 2d ciphers c.sub.0 to c.sub.2d-1 are also processed using a recomposition function Rec, the purpose of which is to form a recomposed cipher C.sub.rec by selecting bits from the ciphers c.sub.0 to c.sub.2d-1. Each bit of the recomposed cipher C.sub.rec originates from one of the ciphers c.sub.0 to c.sub.2d-1 and occupies the same position in the recomposed cipher as its position in the cipher from which it originates. In other words, C.sub.rec(i)=c.sub.j(i) where j=0 to 2d−1.

[0158] For security reasons, the recomposed cipher C.sub.rec is preferentially formed of bits originating from ciphers from at least two different pairs, and not only from two different ciphers.

[0159] In one particular embodiment, the recomposed cipher C.sub.rec is formed of bits originating from ciphers of each of the pairs. This makes it possible to statistically mix, in the recomposed cipher, some of the errors injected into the different executions of the operation OPE.

[0160] The recomposition function may be selected based on the attacks to be countered. By way of example, DFA (Differential Fault Analysis) type attacks on an AES-128 cryptographic operation are based on modifying four bytes of the cipher (due to the size of the MixColumns operation in the AES) and exploiting these modifications.

[0161] In a general manner, the attacks generally exploit modifications to one, several or even all the bytes of the cipher.

[0162] In this context, the recomposition function may be selected such that at least one or more or each byte of the recomposed cipher C.sub.rec is formed of bits originating from ciphers of at least two different pairs, or even more than two pairs or all of the pairs when this is possible (e.g. 8 pairs maximum per byte). This actually makes it possible to secure the countermeasure against certain attacks injecting the same fault into the executions of the operation OPE corresponding to one pair of ciphers.

[0163] As noted above, several selection/recomposition schemes may be envisaged.

[0164] The recomposition function preferably (but not necessarily) uses equitably the same number of bits of each c.sub.i or of each pair p.sub.i. For example, ½d of the bits of C.sub.rec may originate from each cipher c.sub.0 to c.sub.2d-1. As a variant, 1/d of the bits of C.sub.rec may originate from the ciphers of each pair p.sub.i. However, another distribution of bits may be envisaged, for example providing at least one bit of each cipher c.sub.0 to c.sub.2d-1 inside one or more or each byte forming the recomposed cipher C.sub.rec.

[0165] By way of example, one bit every 2d bits may originate from each of the ciphers c.sub.0 to c.sub.2d-1. If d is not a power of 2, an extra bit may be selected for certain ciphers with respect to others.

[0166] Typically if d is a power of 2, the following recomposition function may be used:

[00005]${\oplus }_{i=0}^{2d-1}{c}_i\wedge \left({.Math.}_{j=0}^{\left(\frac{128}{2d}-1\right)}{2}^{\frac{128}{2d}*j}\ll \left(i\right)\right)$

where x<<y shifts (rotation) the bits of x by y positions (bits) to the left.

[0167] A person skilled in the art is able to identify recomposition functions ensuring the selection of bits originating from ciphers of at least two distinct pairs, optionally inside the same byte, of each of several bytes, or even of each byte of the recomposed cipher.

[0168] For example, Rec(c.sub.0, c.sub.1, . . . , c.sub.2d-1)=⊕.sub.i=1.sup.2d-1c.sub.i∧a.sub.i

with ⊕.sub.i=0.sup.2d-1 a.sub.i=0xFFFF . . . FF.

[0169] In one embodiment improving the robustness, a.sub.i∧.sub.j≠i=0 (for all i and j).

[0170] Additionally, to ensure that at least one bit is selected from n (e.g. n=2) distinct pairs of ciphers, a.sub.i∨a.sub.d+i≠0 for at least n different values of i. This condition is applied to all the bits of a.sub.i, but, as a variant, it may be applied to a particular byte, to several bytes, to each of several bytes or to each byte of a.sub.i depending on the desired constraints.

[0171] In the absence of an injected fault, C.sub.rec=c.sub.i, i=0 . . . 2d-1 is found. In the presence of an injected fault, C.sub.rec is likely to be different from c.sub.0 to c.sub.2d-1.

[0172] The infective ciphers g.sub.0 to g.sub.2d-1 and the recomposed cipher C.sub.rec are then combined to obtain the output cipher S. As illustrated, this combination may be produced using the XORs 10, 11: S=g.sub.0⊕Rec(c.sub.0, c.sub.1, . . . , c.sub.2d-1)⊕g.sub.1⊕g.sub.2 . . . ⊕g.sub.2d-1.

[0173] Naturally, the infective ciphers may be used in a different order. Additionally, if it is preferable to alternate the infective ciphers originating from different pairs, it is equally possible to perform two consecutive XORs with the two ciphers of a single pair.

[0174] Preferably, the following steps are performed by first combining the recomposed cipher C.sub.rec with one of the infective ciphers g.sub.0 to g.sub.2d-1 rather than combining two or more infective ciphers together before introducing C.sub.rec, then combining the result of each successive combination with each of the other infective ciphers.

[0175] While the infective countermeasures illustrated by FIGS. 5 to 8 are resistant to the injection of d faults on one execution, they do not guarantee the same degree of security over several executions (only protection against one fault).

[0176] The embodiments presented hereinafter, in connection with FIG. 9, offer enhanced security, notably against the injection of d faults on one execution and against the repeated injection of d faults on several executions of the countermeasure. The maximum value of d (d integer greater than or equal to 1) is as mentioned above in reference to FIG. 8.

[0177] Additionally, these embodiments have the advantage of being less complex since, as explained below, the number of executions of the operation OPE and diffusion functions is substantially reduced (to d or d+1 compared with 2d).

[0178] In these embodiments, each intermediate cipher C.sub.i is a cipher combining or concatenating several or all of the first ciphers c.sub.i resulting directly from the executions of the cryptographic operation. In other words, the function F (FIG. 4) is not the identity function but it combines all or part of the first ciphers c.sub.i.

[0179] The cryptographic operation OPE, for example the AES, is executed d+1 times on the input data E of length L, resulting in obtaining d+1 first ciphers c.sub.0 to c.sub.d directly originating from the executions of the operation OPE. The mixing function F of the first ciphers makes it possible to generate k pairs of intermediate ciphers (C.sub.0, C.sub.1), (C.sub.2, C.sub.3) . . . , or generically (C.sub.2i, C.sub.2i+1) for the pair p.sub.i. Naturally, this organization of pairs by consecutive indices is only illustrative, for the purposes of simplifying the explanations.

[0180] The multiple executions of the operation OPE may be in whole or in part simultaneous and/or in sequence.

[0181] k depends on d: if d is even, k=d/2; if d is uneven, k=(d+1)/2. Also, if d is even, the function F generates intermediate ciphers organized into pairs; if d is uneven, the function F generates d+1 intermediate ciphers organized into pairs. If d=2, one pair of intermediate ciphers is found, in a similar way to FIG. 5 or 6 for the embodiment hereinbefore. If d=3 or 4, two pairs of intermediate ciphers are found, in a similar way to FIG. 7 for the embodiment hereinbefore.

[0182] The function F produces intermediate ciphers C.sub.i from a concatenation of all or part of the first ciphers c.sub.0 to c.sub.d, which differs from one intermediate cipher to another.

[0183] The function F may be selected such that the injection of the same fault on n (2 or more) executions of the operation OPE (therefore in two or more c.sub.i) does not result in obtaining too many pairs of identical intermediate ciphers, which would lead to their cancellation via the final XORs 10, 11. This protection is possible by selecting appropriate concatenations and offers the advantage of enabling the same diffusion function f.sub.diff to be used for several if not all of the pairs of intermediate ciphers.

[0184] For example for d=3 (therefore k=2 pairs), four executions of the operation OPE take place resulting in obtaining c.sub.0 to c.sub.3. The four (2k) intermediate ciphers, of length (d+1) L, can be formed as follows:

C.sub.0=c.sub.0c.sub.1∥c.sub.2∥c.sub.3,

C.sub.1=c.sub.1∥c.sub.2∥c.sub.3∥c.sub.0,

C.sub.2=c.sub.2∥c.sub.0∥c.sub.1∥c.sub.3,

C.sub.3=c.sub.3∥c.sub.2∥c.sub.0∥c.sub.1.

[0185] As a variant, it is possible to simply form the intermediate ciphers in distinct pairs of first ciphers (sliding pairs). Typically, it is possible to browse a circular queue composed of d+1 first ciphers:

C.sub.0=c.sub.0∥c.sub.1,

C.sub.1=c.sub.1∥c.sub.2,

C.sub.2=c.sub.2∥c.sub.3,

C.sub.3=c.sub.3∥c.sub.0.

[0186] Each row of the tables defines a concatenation profile, where each cipher c.sub.i has a cipher position in the concatenation.

[0187] Such a concatenation table, for each pair (d, k) may be provided in the memory of the device.

[0188] These table examples illustrate a more general approach according to which at most

[00006]$.Math.\frac{n}{2}.Math.$

disjoint pairs of concatenation profiles are symmetrical for a group of n first messages. A pair of concatenation profiles is said to be symmetrical for the group of n first messages when its two concatenation profiles use the same message positions in the concatenation to position the first messages originating from the group of n first messages (the profile may only contain some of the n first messages of the group, but not all of them). This condition is verified for every value of n between 2 and d. It should be noted that └x┘ is the floor of x.

[0189] Thus, this avoids having

[00007]$.Math.\frac{n}{2}.Math.+1\mathrm{pairs}$

in which the two intermediate ciphers are identical and consequently, in which the corresponding infective ciphers cancel each other out in pairs during the final combination. It is thus guaranteed that

[00008]$2\left(k-.Math.\frac{n}{2}.Math.\right)$

infective ciphers do not cancel each other during this combination, ensuring robustness against 2k injected faults.

[0190] For example, for d=16, 17 first ciphers c.sub.i and 16 intermediate ciphers C.sub.j are obtained. It is therefore possible to verify that the concatenation profiles for obtaining the intermediate ciphers are not sensitive to two injected faults (n=2) by verifying that there is no more than one pair of concatenation profiles which is symmetrical for two (n) first ciphers. In the opposite case, two faults on the two corresponding executions would make it possible to obtain four (or more) identical intermediate ciphers for the two symmetrical pairs and therefore to cancel (in the case of an identical diffusion function) the corresponding infective ciphers during the XOR combination. At most 12 faults would make it possible to short circuit the other 12 XORs and an additional fault would make it possible to obtain, via C.sub.rec, an uninfected cipher fault. Thus 15 faults would be sufficient to circumvent the countermeasure.

[0191] It is also verified that the concatenation profiles are not sensitive to three injected faults (n=3) by verifying that there is not more than one pair of concatenation profiles that is symmetrical for three (n) first ciphers. Similarly for four injected faults (n=4) by verifying that there are not more than two pairs of concatenation profiles that are symmetrical for four (n) first ciphers. And so on, up to d injected faults (n=d).

[0192] If, by chance,

[00009]$.Math.\frac{n}{2}.Math.+1$

(or more) pairs of concatenation profiles were symmetrical for a group of n first ciphers, it is possible to provide the desired robustness by adding one or more pairs of intermediate ciphers to the existing pairs, where the intermediate ciphers of one pair combine at least one of the ciphers of the group with at least one of the one of the first ciphers not in the group, according to two distinct profiles.

[0193] For example, if c.sub.0 belongs to said group and c.sub.3 does not, a pair formed of the intermediate ciphers c.sub.0∥c.sub.3 and c.sub.3∥c.sub.0 may be added.

[0194] In one variant simplifying the concatenation operations, and as shown in the Figure, the cipher mixing function F comprises a concatenation module CONCAT producing a master cipher CM (of length (d+1) L bits) concatenating all the first ciphers c.sub.0 to c.sub.d resulting directly from the executions of the cryptographic operation.

[0195] 2k operations R.sub.j can then be applied to the same master cipher in order to obtain the intermediate ciphers.

[0196] For example, the operation R.sub.j may be a sliding window for selecting two ciphers in CM (which operates as a circular queue). Thus, R.sub.0 selects c.sub.0 and c.sub.1 to form C.sub.0 (C.sub.0=c.sub.0∥c.sub.1), R.sub.1 selects c.sub.1 and c.sub.2 to form C.sub.1 (C.sub.1=c.sub.1∥c.sub.2), and so on.

[0197] As a variant, the operations R.sub.j may be rotation operations, on a multiple of L bits (length of each cipher c.sub.i), of the master cipher CM.

[0198] For example, the rotation R.sub.j to obtain the intermediate cipher C.sub.j may involve shifting the bits of the master cipher CM to the left by jL bits (i.e. shift by j ciphers c.sub.i). The rotation R.sub.0 is thus the identity: C.sub.0=CM.

[0199] In another example, R.sub.2j=Id and R.sub.2j+1 is any rotation of the bits of the master cipher CM by a multiple of L bits (therefore rotation of one or more ciphers c.sub.i) which differs from the identity. Thus for each pair p.sub.i of intermediate ciphers, there is the master cipher C.sub.2i=CM and an intermediate cipher C.sub.2i+1 resulting from another concatenation of ciphers c.sub.0 to c.sub.d.

[0200] As these different mixtures of ciphers by rotation do not guarantee the absence of identical intermediate ciphers in the case of identical faults on several executions of the operation OPE, the diffusion functions to be applied may differ from one to another.

[0201] Examples of diffusion functions, notably based on a key pair and optionally on an execution key, are given above.

[0202] For each pair p.sub.i (0≤i<k), a single diffusion function f.sub.diff-i is applied to two intermediate ciphers (C.sub.2i, C.sub.2i+1) of the pair. Two infective ciphers g.sub.2i to g.sub.2i+1 per pair are thus obtained, i.e. a total of 2k (d if d is even, d+1 if d is uneven) infective ciphers g.sub.0 to g.sub.2k-1. The infective ciphers therefore cancel each other out two by two.

[0203] The explanations provided above on the diffusion functions also apply to this embodiment. For example, the use of pseudorandom number generators based on a different key K.sub.i from one pair of ciphers to another is only one embodiment of the invention. Generally, the diffusion function is different from one pair of ciphers to another. One or more diffusion functions used may be PRNGs while one or more others may be one or more other types, for example hash functions. Also, the key pair and/or the execution key may be concatenated or XORed with the intermediate cipher at the input of the diffusion function.

[0204] In some embodiments, it is possible to use a single diffusion function for a subset of pairs, and this for two or more subsets (the diffusion functions differ from one subset to another). In this case, it is possible to ensure that the concatenation profiles used in each subset of pairs are not sensitive to n injected faults as disclosed hereinbefore (n being limited by the number of intermediate ciphers comprising the subset in question).

[0205] It should be noted that in the embodiments where the diffusion functions receive an input of ciphers of multiple length of L (for example 2 L or (d+1) L bits in the examples hereinbefore), they preferably generate infective ciphers of length L bits. The diffusion functions used must therefore be able to absorb the multiple (2 or d+1 in the examples) input ciphers (forming the intermediate cipher). Hash functions may therefore be typically used.

[0206] Naturally, the output of the diffusion functions may be longer than L bits, in which case, the combinations (XOR 10 and 11) work on the least significant bits L.

[0207] In the example of FIG. 9, the first cipher c.sub.0 is used as a recomposed cipher C.sub.rec for the purposes of the final combination by XOR 10. Any other first cipher c.sub.i may be used instead, irrespective of the number of executions of the operation OPE.

[0208] The use of a single first cipher for C.sub.rec simplifies the diagram in the Figure.

[0209] As a variant, the recomposed cipher C.sub.rec may be formed by selecting bits of all or part of the first ciphers c.sub.0 to c.sub.d. The explanations given above about the recomposition function Rec also applies to this embodiment.

[0210] For example, in the variant with sliding pairs mentioned hereinbefore, the recomposed cipher C.sub.rec is formed from bits or bytes or ciphers originating from intermediate ciphers of each pair (or more generally all intermediate ciphers) sharing the same diffusion function.

[0211] If it is detected that

[00010]$.Math.\frac{n}{2}.Math.$

disjoint pairs of concatenation profiles are symmetrical, then it is possible to select the recomposed message so that it is not only formed of one or more of said n first messages of the group. It is possible for example to select a first cipher which is not involved in the symmetries between concatenation profiles. This constraint may be applied for any value of n, or only when n is even. Similarly, it may be applied for any value of d, or only when d is even. Otherwise, it is possible to use a single first cipher as C.sub.rec.

[0212] In the absence of an injected fault, C.sub.rec=c.sub.i, i=0 . . . d is found. In the presence of an injected fault, C.sub.rec is likely to be different from c.sub.0 to c.sub.d.

[0213] It is noted that if the recomposition can be performed by selecting bits in the first ciphers c.sub.0 to c.sub.d, it is also possible to make this selection from one (or a plurality of) intermediate cipher C.sub.i insofar as this latter concatenates, in some embodiments, all or part of the first ciphers c.sub.0 to c.sub.d.

[0214] The infective ciphers g.sub.0 to g.sub.2k-1 and the recomposed cipher C.sub.rec are then combined to obtain the output cipher S. As illustrated, this combination may be produced using the XORs 10, 11: S=g.sub.0⊕Rec(c.sub.0, c.sub.1, c.sub.2, . . . , c.sub.d)⊕g.sub.1⊕g.sub.2⊕ . . . ⊕g.sub.2k-1.

[0215] Naturally, the infective ciphers may be used in a different order. Additionally, if it is preferable to alternate the infective ciphers originating from different pairs, it is equally possible to realize two consecutive XORs with the two infective ciphers of a single pair.

[0216] Preferably, the following steps are performed by first combining the recomposed cipher C.sub.rec with one of the infective ciphers g.sub.0 to g.sub.2k-1 rather than combining two or more infective ciphers together before introducing C.sub.rec, then combining the result of each successive combination with each of the other infective ciphers.

[0217] Although the present invention has been disclosed hereinbefore with reference to specific embodiments, the present invention is not limited to these specific embodiments, and modifications, which are found within the scope of the present invention, will be obvious to a person skilled in the art.

[0218] Numerous other modifications and variations will be imposed on those persons skilled in the art by referring to the illustrative embodiments hereinbefore, which are only given by way of example and which do not limit the scope of the invention, this only being determined by the appended claims. In particular, the different features of the different embodiments may be exchanged, where applicable.

[0219] In the claims, the word “comprising” does not exclude other elements or steps, and the indefinite article “a” or “an” does not exclude a plurality. The mere fact that different features are cited in different mutually dependent claims does not indicate that a combination of these features cannot be used advantageously.