Shift register protected against physical attacks

Abstract

The present invention relates to a shift register protected against physical attacks, comprising a coding module, a decoding module, a plurality of basic shift registers of which the respective inputs receive the bits of a codeword supplied by the coding module using an input bit at each clock cycle, and of which the respective outputs are connected to the decoding module in order to supply an output bit, with the codewords being chosen in such a way as to have the same non-zero Hamming weight and two successive codewords having a constant non-zero Hamming distance. The codewords are generated using an internal state machine and/or an external state machine to the coding module.

Claims

1. A shift register protected against physical attacks, characterized in that it comprises a coding module receiving input bits and encoding, at each clock cycle, an input bit (b.sub.in) into a codeword of size K>1, a pluraliy K of basic shift registers (330.sub.1, . . . , 330.sub.K) each comprising the same number N>2 of memory cells, with each basic shift register receiving as input one bit (S.sub.n.sup.k) of the codeword and supplying one bit of a word to be decoded of size K in order to generate one output bit (b.sub.out), with the codewords being chosen in such a way as to all have the same non-zero Hamming weight and each pair of consecutive codewords having the same non-zero Hamming distance.

2. The shift register according to claim 1, wherein the coding implemented by the coding module is a systematic coding, with the output bit being the systematic bit of the word to be decoded and being supplied by one of the basic registers.

3. The shift register according to claim 1, further comprising a decoding module of which the inputs are connected to the respective outputs of the K basic shift registers, and decoding the word to be decoded in order to supply the output bit.

4. The shift register according to claim 1, wherein the coding module comprises an internal state machine, with each state being associated with a codeword, the state machine passing at each clock cycle from a current state to a following state according to the current state and the input bit, with the codeword generated by the coding module being the one associated with the following state.

5. The shift register according to claim 1, further comprising an external state machine, clocked by said clock and cyclically running through a sequence of states, with the codeword generated by the coding module being a function of the input bit and of the current bit of the state machine.

6. The shift register according to claim 5, wherein the external state machine is a synchronous binary counter.

7. The shift register according to claim 6, wherein the counter supplies a parity in the number of clock cycles using an initialization instant, with the codeword generated by the coding module being a function of the input bit and of said parity.

8. The shift register according to claim 3, wherein when the decoding module determines that the word to be decoded is not a codeword, it generates an error signal.

9. A stream cipher circuit, comprising at least one shift register according to claim 2, the basic shift register corresponding to the systematic bit comprising a linear feedback by means of coefficients of a primitive polynomial, with the bit resulting from the linear feedback being used as an input bit for the coding module, with the bits stored in the basic shift register corresponding to the systematic bit, or only some of them, being combined in a non-linear combination module in order to supply a key stream cipher, with a sequence of bits (a.sub.1, . . . , a.sub.N) to be encrypted being added to the key stream cipher (d.sub.1, . . . , d.sub.N) in order to supply a stream cipher sequence (a.sub.1.sup.*, . . . , a.sub.N.sup.*).

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Other characteristics and advantages of the invention shall appear when reading a preferred embodiment of the invention, described in reference to the accompanying figures among which:

(2) FIG. 1 diagrammatically shows a shift register that is not protected against physical attacks;

(3) FIG. 2 shows a shift register protected against physical attacks via side channels, known from the prior art;

(4) FIG. 3 shows a shift register protected against physical attacks according to a first embodiment of the invention;

(5) FIG. 4 shows a first example of a shift register according to FIG. 3;

(6) FIG. 5 shows an example of a state diagram for the coding module of FIG. 3;

(7) FIG. 6 shows a second example of a shift register according to FIG. 3, using the state diagram of FIG. 5;

(8) FIG. 7 shows a shift register against physical attacks according to a second embodiment of the invention;

(9) FIG. 8 diagrammatically shows a stream cipher circuit that uses a shift register protected against physical attacks according to the second embodiment of the invention.

DETAILED DISCLOSURE OF PARTICULAR EMBODIMENTS

(10) We shall consider in what follows a shift register comprising a plurality N≥2 of memory cells, to be protected against the physical attacks described hereinabove. Such a register can for example be an integral part of a stream cipher circuit to be protected as we shall see further on.

(11) The idea at the base of the invention is to provide a plurality K>1 of basic shift registers in parallel and to code each input bit into one word of K bits, with the bits of this word being respectively supplied to the inputs of these basic shift registers. The shift register to be protected can be seen as any one of the basic shift registers.

(12) FIG. 3 shows a shift register protected against physical attacks according to a first embodiment of the invention.

(13) The shift register protected against physical attacks is implemented in the form of a plurality K of basic registers 330.sub.1, . . . , 330.sub.K, controlled by the same clock, Clk. At each clock cycle, a new input bit is supplied to the coding module, 310, in order to generate a codeword of K bits, with each one of the K outputs of the coding module being connected to the input of a basic register. Thus, at each clock cycle, one bit of the codeword is supplied to a basic shift register. The bits at the output of the basic shift registers, 330.sub.1, . . . , 330.sub.K, are supplied in parallel in the form of a word of K bits which is decoded by the decoding module 320 in order to supply an output bit.

(14) According to a first alternative, the coding of the input bit by the coding module can depend on the state of an external state machine, clocked by the clock Clk and cyclically running through a sequence of states. According to a second alternative, wherein the encoder (coding module) is itself a state machine, the coding of the input bit will depend on the state of the encoder, such as resulting from the preceding coding operation. According to a third alternative, the coding of the input bit by the coding module will depend on both a first state of an external state machine and on a second state of an internal state machine.

(15) Regardless of the alternative considered, the set of all the codewords, in other words the dictionary of the code, is only comprised of words that have the same non-zero Hamming weight. Furthermore, the Hamming distance between any two successive codewords is chosen as constant, non-zero, in other words the number of binary switchings at each clock cycle is identical and non-zero. Thus, the same input bit value will be coded differently in two successive instants.

(16) In the first alternative, the external state machine can be carried out by means of a synchronous binary counter, and even in its simplest implementation by a flip-flop DQ looped onto itself (Q on D) so as to perform a division of the frequency by 2. In this latter case, the coding of the input bit will simply depend on the parity P of the number of clock cycles from an initialization instant.

(17) A first example of such a coding of an input bit b for K=4 is given by the coding table hereinafter:

(18) TABLE-US-00001 TABLE I P = 0 P = 1 b = 0 0001 0010 b = 1 0100 1000

(19) It is indeed checked that all of the codewords have the same Hamming weight (here 1) and that two successive codewords have the same Hamming distance (equal to 2).

(20) FIG. 4 shows an example of a protected shift register wherein the coding module uses the coding table hereinabove. The top of the figure shows, as a dotted line, the equivalent unprotected shift register. In this figure, the first clock cycle, corresponding to S.sub.1.sup.1, . . . , S.sub.1.sup.K is assumed to have an odd parity (P=1).

(21) The decoding module decodes at each clock cycle the word formed by the K bits at the output of the basic shift registers, by using the dictionary of the code. If the word in question is not part of the dictionary of the code, an error is detected and reported. Thus, in the case of the example of the protected register shown in FIG. 4, if the word to be decoded has two bits or more equal to “1”, or no bit equal to 1, an error will be detected and reported.

(22) An attacker who wants to inject a fault into the circuit without the latter being detected will have to simultaneously inject a fault at the same position and in two different basic registers. He will furthermore have to inject this fault over exactly one bit per basic register, otherwise an unknown state will be generated. Finally, the attacker will have to have access to the parity P in order to carry out this insertion. The combination of these three conditions is very difficult to produce. In particular, it is much more difficult to conduct an attack conducted against a countermeasure known from prior art, based on simple spatial redundancy.

(23) As indicated hereinabove, according to a second alternative, the coding module can operate itself as a state machine, in other words each clock cycle switches the machine to a new state, according to the preceding state and the binary value of the input bit (such a state machine will be referred to as “internal”). The description of the transitions between states, according to the input bits is given by a state diagram. Each state corresponds to a codeword of K bits, with these K bits being supplied to the K respective inputs of the basic shift registers.

(24) The codewords associated with the various states are chosen in such a way as to all have the same non-zero Hamming weight and such that each pair of successive codewords has the same non-zero Hamming distance.

(25) The decoding module is based on the same state diagram as the coding module: using two successive states, this module determines the binary value that corresponds to the transition from one to the other, and supplies this value as an output bit.

(26) FIG. 5 shows an example of a state diagram for the coding module of FIG. 3. The binary values associated with the edges of the graph correspond to the possible values of the input bit of the coding module.

(27) FIG. 6 shows a second example of a shift register according to FIG. 3, using the state diagram of FIG. 5.

(28) The top of the figure shows, as a dotted line, the equivalent unprotected shift register. The coding module is shown in 610 and the one for decoding in 620. The basic shift registers are shown in 630.sub.1, . . . , 630.sub.4.

(29) It was assumed here that the initial state of the state machine was 1010. This state is supplied as a first codeword S.sub.1.sup.1, . . . , S.sub.1.sup.K to the K basic shift registers. The arrival of the first bit of value “1” switches the encoder from the state 1010 to the state 1100. This codeword, S.sub.2.sup.1, . . . , S.sub.2.sup.K, is supplied to the basic shift registers. The second bit of value “1” switches the encoder from the state 1100 to the state 1010. This codeword S.sub.3.sup.1, . . . , S.sub.3.sup.K is supplied to the basic shift registers and so on.

(30) In this example, the Hamming weight of the various codewords is equal to 2 and the Hamming distance between two successive words of the code is equal to 2.

(31) In the same way as hereinabove, if an output word S.sub.n.sup.1, . . . , S.sub.n.sup.K does not belong to the dictionary of the code, the decoding module 620 will detect an error and will be able to report it.

(32) More generally, in a third alternative, the coding of the input bit can be carried out according to the state of a first external state machine, such as a counter, and of the state of a second internal state machine. The transitions between the internal states can then depend on both the external state (for example on the portion P of the clock cycle counter) and on the bit as input of the coding module. This results in a double indexing of the state diagram of the second state machine.

(33) FIG. 7 shows a shift register protected against physical attacks according to a second embodiment of the invention.

(34) As in the first embodiment, the coding module 710 can be implemented according to the first, the second or the third alternative disclosed hereinabove.

(35) It differs however from the preceding one in that the coding module 710 uses a systematic code. In other words, the codeword S.sub.n.sup.1, . . . , S.sub.n.sup.K encoding the bit b.sub.n contains this bit: ∃k such that S.sub.n.sup.k=b.sub.n, ∀n. It also differs in that the decoding module is here absent, the systematic output, i.e. that of the basic shift register 730.sub.k being used directly. Thus, for example, it can be noted that the shift register shown in FIG. 6 is able to be implemented according to the second embodiment of the invention, with the sequence of bits at the output of the register 630.sub.1 being identical to the sequence of the input bits.

(36) FIG. 8 diagrammatically shows a stream cipher circuit that uses a shift register protected against physical attacks, according to the second embodiment of the invention.

(37) It should be noted that a shift register according to the first embodiment of the invention could alternatively be used, at the price of greater complexity (provision of the decoding module) but with the advantage of the associated error detection.

(38) In FIG. 8, the coding module 810 uses a systematic code such as the module 710 of FIG. 7. Only the basic shift register, here 830.sub.1, corresponding to the systematic output is used to generate the key stream cipher. The contents of the memory cells of the basic shift register in question are respectively multiplied in 840 by the binary coefficients c.sub.1, c.sub.2, . . . , c.sub.N of a primitive polynomial and added in the binary added (XOR) 850 in order to provide the bit at the input of the coding module:

(39) $b_n=\underset{i=1}{\overset{N}{.Math.}}{c}_{N-i+1}{S}_i^1=\underset{i=1}{\overset{N}{.Math.}}{c}_{N-i+1}{b}_i$

(40) Moreover, the bits of the basic register 830.sub.1, or even only some of them, can be combined by means of a combination module 860 (for example logic gate) that implements a non-linear function NL in order to provide a key stream cipher d.sub.1, . . . , d.sub.M.

(41) The sequence of bits to be encrypted a.sub.1, . . . , a.sub.M forming the unencrypted message and the key stream cipher are added by the logic adder 870 in order to supply the encrypted message a.sub.1.sup.*, . . . , a.sub.M.sup.*, with a.sub.1.sup.*=a.sub.i+d.sub.i.

(42) In practice, it is possible to use a plurality of shift registers protected against physical attacks such as the one shown in FIG. 8 and certain bits of each one of the basic registers corresponding to their respective systematic outputs will be combined in order to obtain the key stream cipher. For example, each one of these basic registers will be associated with a non-linear combination module and the sequences at the output of these non-linear combination modules will be added together. Alternatively, the non-linear combination module could be mutualized between these basic registers and receive certain bits of each one of them in order to form the key stream cipher.