SECURE DATA STORAGE

Abstract

The disclosure relates to secure data storage and retrieval, in particular to methods and circuits for securely storing data to reduce the possibility of leakage via side channel attacks. Embodiments disclosed include a method of storing a value comprising a series of words, the method comprising: i) combining in a series of XOR operations a word of a first portion of the value, a word of a second portion of the value and an output word of a first random number generator to provide a first combined word; ii) storing the first combined word in a shift register; and iii) repeating steps i) and ii) for each successive word of the first and second portions of the value.

Claims

1. A method of storing a value comprising a series of words, the method comprising: i) XOR combining a word of a first portion of the value, a word of a second portion of the value and an output word of a first random number generator to provide a first combined word; ii) storing the first combined word in a shift register; and iii) repeating steps i) and ii) for each successive word of the first and second portions of the value.

2. The method of claim 1 comprising: iv) outputting a first output word from the shift register; v) outputting a second output word from a second random number generator; and vi) repeating steps iv) and v) for each successive word stored in the shift register.

3. The method of claim 2 wherein the first and second random number generators are pseudo random number generators configured to generate the same sequence of words, the outputs from the first and second random number generators being shifted relative to each other in the sequence of words by a length of the shift register.

4. The method of claim 1, wherein step i) comprises: ia) XOR combining the word of the second portion of the value with the output word of the first random number generator to provide a second combined word; and ib) XOR combining the word of the first portion of the value with the second combined word to provide the first combined word.

5. The method of claim 3 wherein: step iv) comprises XOR combining the first output word with an output word of a third random number generator to provide a first combined output word; and step v) comprises XOR combining the second output word with the output word of the third random number generator to provide a second combined output word.

6. The method of claim 1 wherein step i) comprises: ia) XOR combining the output word of the first random number generator with an output word of a or the third random number generator to provide a second combined word; ib) XOR combining the word of the second portion of the value with the second combined word to provide a third combined word; ic) XOR combining the output word of the third random number generator with the word of the first portion of the value to provide a fourth combined word; and id) XOR combining the fourth combined word with the third combined word to provide the first combined word.

7. The method of claim 5 wherein the third random number generator generates a different sequence of words to the sequence of words generated by the first and second random number generators.

8. The method of claim 7 wherein the third random number generator is a true random number generator.

9. A circuit for storing a value comprising a series of words, the circuit comprising: a first input for receiving a word of a first portion of the value; a second input for receiving a word of a second portion of the value; a first random number generator; a first XOR gate having inputs connected to the second input and an output of the first random number generator; a second XOR gate having inputs connected to the first input and an output of the first XOR gate; and a shift register having an input connected to an output of the second XOR gate and having an output.

10. The circuit of claim 9 further comprising a second random number generator, wherein the first and second random number generators are pseudo random number generators configured to generate the same sequence of words, the outputs from the first and second random number generators being shifted relative to each other in the sequence of words by a length of the shift register.

11. The circuit of claim 9 comprising: a third XOR gate connected between the first input and the second XOR gate, the third XOR gate having inputs connected to the first input and an output of a third random number generator and an output connected to an input of the second XOR gate; and a fourth XOR gate connected between the first random number generator and the first XOR gate, the fourth XOR gate having inputs connected to the first random number generator and the third random number generator and an output connected to an input of the first XOR gate.

12. The circuit of claim 11 comprising: a fifth XOR gate having inputs connected to the output of the shift register and the third random number generator; and a sixth XOR gate having inputs connected to the second random number generator and the third random number generator.

13. The circuit of claim 10 wherein the third random number generator generates a different sequence of words to the sequence of words generated by the first and second random number generators.

14. The circuit of claim 13 wherein the third random number generator is a true random number generator.

15. An IC card comprising an integrated circuit having the circuit according to claim 9.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0043] Embodiments will be described, by way of example only, with reference to the drawings, in which

[0044] FIG. 1 is a schematic circuit diagram of an example embodiment for storing and retrieving a value;

[0045] FIG. 2 is a schematic circuit diagram of an alternative example embodiment for storing and retrieving a value;

[0046] FIG. 3 is a schematic circuit diagram of an alternative example embodiment for storing and retrieving a value; and

[0047] FIG. 4 is a schematic flow diagram illustrating operation of the example embodiment of FIG. 1.

[0048] It should be noted that the Figures are diagrammatic and not drawn to scale. Relative dimensions and proportions of parts of these Figures have been shown exaggerated or reduced in size, for the sake of clarity and convenience in the drawings. The same reference signs are generally used to refer to corresponding or similar feature in modified and different embodiments.

DETAILED DESCRIPTION OF EMBODIMENTS

[0049] FIG. 1 illustrates a schematic diagram of an example embodiment of a circuit 100 for storing and retrieving a data value provided as two portions (or shares). The value is provided as first and second portions at first and second inputs 101, 102, and is stored in a shift register 103 after being XOR combined with the output of a first random number generator 104a. A first XOR gate 105 has inputs connected to the second input 102 and an output of the first random number generator 104a. A second XOR gate 106 has inputs connected to the output of the first XOR gate 105 and the first input 101. An output of the second XOR gate 106 provides a combined word to the shift register 103.

[0050] The shift register 103 is configured to store N words of M bits together with the state of the two random number generators 104a, 104b. Each time a value is written or “shifted-in”, another value is read or “shifted-out” at the other end of the shift register 103.

[0051] As used herein, the term “word” refers to a unit of digital information consisting of M bits (where a bit is a single binary digit, i.e. 1 or 0), where M is an integer greater than one. A word may be a byte, commonly defined as a group of eight bits, or any other number appropriate for the particular application, such as 16, 32 etc.

[0052] On the output side, a first portion is provided at a first output 107 and a second portion at a second output 108. The first output 107 is provided by the shift register 103, and the second output 108 is provided by a second random number generator 104b. The second random number generator 104b is identical to the first random number generator 104a, i.e. is a pseudo random number generator initiated by the same seed. The second random number generator 104b is, however, configured to provide a word in a set sequence of words that is shifted by a number of words equal to the length of the shift register 103. The result is that a word being stored in the shift register 103 is combined with the same value produced by the first random number generator 104a as the value that is output by the second random number generator 104b when the stored word is output from the shift register. The shift register 103 may be able to store N words, each word consisting of M bits. Each of the connections between the various components in the circuit 100 are M bits wide, i.e. the inputs 101, 102 and the random number generators 104a, 104b all provide words having equal number of bits. The length of the shift register 103 is therefore defined by the number of words stored between the input and output, i.e. the number N. The shift register 103 may have multiple parallel registers, each N words long, resulting in the shift register 103 being capable of storing a multiple of N words.

[0053] The embodiment in FIG. 1 shows the first XOR gate 105 connected before the second XOR gate 106. Since XOR operations are commutative and associative, the same output could be achieved with the XOR gates arranged with the second XOR gate connected before the first XOR gate, with the input to the shift register 103 being provided by the first XOR gate. This would, however, result in the portions from the first and second inputs 101, 102 being XOR combined, which results in the plain input value, thereby compromising the security of the circuit 100. The arrangement as shown in FIG. 1 avoids this by first combining the second input value with the output from the first random number generator 104a.

[0054] The first and second random number generators 104a, 104b must be identical and seeded with the same seed for the data values to be extracted correctly from the shift register 103. The design of the random number generators 104a, 104b may be fixed in the design of the circuit 100 and can be assumed to be public knowledge. Since the quality of the outputs from the random number generators 104a, 104b has a direct impact on security, it is important that their outputs are uniformly distributed. The output of each random number generator is a sequence of words, each having M bits, i.e. the same as the number of bits in each of the input words. If M is smaller than 32 bits, the internal state of the random number generators must be carefully dimensioned. If the random number generators have a small state of say 8 bits, the number of possible mask sequence is limited to 256 (=2.sup.8), since there are 256 starting states (or even 255 if implemented as a simple linear feedback shift register). For all practical applications 256 starting states is definitely too small since it is common for attackers to gather several millions of power traces. A state of 16 bits gives 65,536 possible sequences (2.sup.16), while a state of 32 bits gives over 4 billion (2.sup.32) possible sequences, which is a much safer choice. In general therefore, the number of bits in each word should be 16 or more.

[0055] FIG. 2 illustrates an alternative example embodiment of a circuit 200 for storing and retrieving data values, in which further remasking of data values is implemented at the input stage to further minimise or prevent first order leakage. As with the circuit 100 of FIG. 1, the circuit 200 comprises first and second inputs 101, 102 and first and second random number generators 104a, 104b, each of which is fed by a common seed at an input 201. The common seed may be a true random seed, and is provided to the second random number generator via connection 202.

[0056] The circuit 200 further comprises a third random number generator 203, which may be a pseudo random number generator or a true random number generator, but in either case provides a sequence of words that is different to the first and second random number generators 104a, 104b, through being fed by a different seed. The output from the third random number generator 203 is XOR combined with the output from the first random number generator 104a and with the first and second inputs 101, 102. The effect of the third random number generator 203 is to provide further masking of data values as they are being stored. If one considers the effect of the third random number generator generating only zero values, the overall effect of the circuit 200 is the same as the circuit 100 in FIG. 1.

[0057] In the circuit 200 in FIG. 2, a third XOR gate 205 is connected between the first input 101 and the second XOR gate 106, the third XOR gate 205 having inputs connected to the first input 101 and an output of the third random number generator 203. A fourth XOR gate 206 is connected between the first random number generator 104a and the first XOR gate 105, the fourth XOR gate 206 having inputs connected to the first random number generator 104a and the third random number generator 203 and an output connected to an input of the first XOR gate 105.

[0058] Also shown in the circuit 200 in FIG. 2 are first and second D-type flip-flops (or latches) 207, 208, with the first flip-flop 207 connected between the second and third XOR gates 106, 205 and the second flip-flop 208 connected between the output of the first XOR gate 105 and an input of the second XOR gate 106. The D input of the first flip-flop 207 is connected to the output of the third XOR gate 205 and the Q output is connected to an input of the second XOR gate (the Q output not being connected). The second flip-flop 208 is similarly connected between the output of the first XOR gate 105 and an input of the second XOR gate 106. The flip-flops 207, 208 serve to further mask stored data values through ensuring that the XOR gate 106 is fed with words only according to a clock cycle. The flip-flops 207, 208 thereby serve to prevent glitches because, if the inputs are not glitch-free, a power trace may otherwise leak information.

[0059] FIG. 3 illustrates a further alternative example embodiment of a circuit 300 for storing and retrieving data values. The circuit 300 has the same components as in the circuit in FIG. 2, but with the addition of fifth and sixth XOR gates 305, 306 at the output stage. The fifth XOR gate 305 has inputs connected to the output of the shift register 103 and the third random number generator 203 (via connection 302), while the sixth XOR gate 306 has inputs connected to the third random number generator 203 (also via connection 302) and the second random number generator 104b, which is fed (via connection 303) with the same random number seed at input 201. The outputs of the XOR gates 305, 306 form the outputs of the circuit 300. This arrangement serves to further mask the data values being output from the shift register 103.

[0060] FIG. 4 is a schematic flow diagram illustrating an example embodiment of a method of storing a value comprising a series of words, as for example carried out by the circuit 100 of FIG. 1. Steps 401, 402 and 403 represent words being provided at the first input 101, the first random number generator 104a and the second input 102 respectively. The words from the first input 101 and the first random number generator 104a are combined in an XOR operation at step 404, and the output from this operation is combined at step 405 in a further XOR operation with the word from the second input 102.

[0061] From reading the present disclosure, other variations and modifications will be apparent to the skilled person. Such variations and modifications may involve equivalent and other features which are already known in the art of secure data storage, and which may be used instead of, or in addition to, features already described herein.

[0062] Although the appended claims are directed to particular combinations of features, it should be understood that the scope of the disclosure of the present invention also includes any novel feature or any novel combination of features disclosed herein either explicitly or implicitly or any generalisation thereof, whether or not it relates to the same invention as presently claimed in any claim and whether or not it mitigates any or all of the same technical problems as does the present invention.

[0063] Features which are described in the context of separate embodiments may also be provided in combination in a single embodiment. Conversely, various features which are, for brevity, described in the context of a single embodiment, may also be provided separately or in any suitable sub-combination. The applicant hereby gives notice that new claims may be formulated to such features and/or combinations of such features during the prosecution of the present application or of any further application derived therefrom.

[0064] For the sake of completeness it is also stated that the term “comprising” does not exclude other elements or steps, the term “a” or “an” does not exclude a plurality, a single processor or other unit may fulfill the functions of several means recited in the claims and reference signs in the claims shall not be construed as limiting the scope of the claims.