Key sequence generation for cryptographic operations

Abstract

Methods, system and devices are provided that generate a sequence of sub-keys for cryptographic operations from a main key. The main key is operated on only once to generate the sub-keys of the sequence, with a transformation comprising one or more one-way functions. The respective bit values of the sub-keys of the sequence are set using respective bit values of the one or more one-way functions. Advantageously, deriving sub-key bits from respective output bits of one or more one-way functions removes or at least reduces correlations between the main key and the sub-keys, as well as between sub-keys, making it harder or even impossible to recover the main key or other sub-keys from a single sub-key, for example as found using a side-channel attack. At the same time, by using the main key only once (rather than using the main key each time a sub-key is generated), the vulnerability of the main key to a side-channel attack is reduced, because the opportunities for recovering physical information that could lead to the discovery of the main key are reduced. Specific embodiments use parallel or chained execution of sub-functions to generate respective sub-keys. Other specific embodiments generate all sub-keys from a single one-way function in one go.

Claims

1. A method of generating, from a main key, a sequence of sub-keys for cryptographic operations, wherein each sub-key is defined by respective bit values, the method comprising: operating on the main key with a transformation, wherein the transformation comprises one or more one-way functions and the main key is operated on only once to generate the sub-keys of the sequence; and setting the respective bit values of the sub-keys of the sequence using respective bit values of the one or more one-way functions.

2. The method of claim 1, further comprising generating an encrypted message using the respective bit values of the sub-keys of the sequence of sub-keys using the respective bit values of the one or more one-way functions.

3. The method of claim 2 further comprising decrypting the encrypted message using the respective bit values of the sub-keys of the sequence of sub-keys using respective bit values of the respective one-way functions.

4. The method of claim 1, wherein operating on the main key with a transformation comprises generating a plurality of intermediate outputs from the main key using one or more of the one-way functions.

5. The method of claim 4, further comprising generating respective one-way outputs from the plurality of intermediate outputs using one or more of the one-way functions.

6. The method of claim 5, wherein the respective bit values of the respective one-way functions are the respective one-way outputs.

7. A device for generating, from a main key, a sequence of sub-keys for cryptographic operations, wherein each sub-key is defined by respective bit values, the method comprising: a memory configured to store the main key and at least one sub-key; and a processor configured to: operate on the main key with a transformation, wherein the transformation comprises one or more one-way functions and the main key is operated on only once to generate the sub-keys of the sequence; and set the respective bit values of the sub-keys of the sequence using respective bit values of the one or more one-way functions.

8. The device of claim 7, wherein the processor is further configured to generate an encrypted message using the respective bit values of the sub-keys of the sequence of sub-keys using the respective bit values of the one or more one-way functions.

9. The device of claim 8, wherein the processor is further configured to decrypt the encrypted message using the respective bit values of the sub-keys of the sequence of sub-keys using respective bit values of the respective one-way functions.

10. The device of claim 7, wherein in operating on the main key with a transformation, the processor is further configured to generate a plurality of intermediate outputs from the main key using one or more of the one-way functions.

11. The device of claim 10, wherein the processor is further configured to generate respective one-way outputs from the plurality of intermediate outputs using one or more of the one-way functions.

12. The device of claim 11, wherein the respective bit values of the respective one-way functions are the respective one-way outputs.

13. A non-transitory computer-readable medium storing computer-readable instructions that, when executed by a processor, cause the processor to perform a method of generating, from a main key, a sequence of sub-keys for cryptographic operations, wherein each sub-key is defined by respective bit values, the method comprising: operating on the main key with a transformation, wherein the transformation comprises one or more one-way functions and the main key is operated on only once to generate the sub-keys of the sequence; and setting the respective bit values of the sub-keys of the sequence using respective bit values of the one or more one-way functions.

14. The non-transitory computer-readable medium of claim 13, further comprising generating an encrypted message using the respective bit values of the sub-keys of the sequence of sub-keys using the respective bit values of the one or more one-way functions.

15. The non-transitory computer-readable medium of claim 14 further comprising decrypting the encrypted message using the respective bit values of the sub-keys of the sequence of sub-keys using respective bit values of the respective one-way functions.

16. The non-transitory computer-readable medium of claim 13, wherein operating on the main key with a transformation comprises generating a plurality of intermediate outputs from the main key using one or more of the one-way functions.

17. The non-transitory computer-readable medium of claim 16, further comprising generating respective one-way outputs from the plurality of intermediate outputs using one or more of the one-way functions.

18. The non-transitory computer-readable medium of claim 17, wherein the respective bit values of the respective one-way functions are the respective one-way outputs.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Specific embodiments will now be described, by way of example, to illustrate aspects of the disclosure and with reference to the accompanying drawings, in which:

(2) FIGS. 1 to 4 illustrate different modes of a block cipher with a round key generator;

(3) FIG. 5 illustrates an implementation of a round key generator enabling parallel execution of sub-functions to generate round keys;

(4) FIG. 6 illustrates a recursive version of the implementation of FIG. 5;

(5) FIG. 7 illustrates an implementation of a round key generator with sequential execution of sub-functions;

(6) FIG. 8 illustrates an implementation of a round key generator with sequential execution of sub-functions to generate a reverse sequence of round keys:

(7) FIG. 9 illustrates a recursive version of the implementations of FIGS. 7 and 8; and

(8) FIG. 10 illustrates an implementation of a round key generator generating a sequence of round keys using a single one-way function.

DETAILED DESCRIPTION OF SPECIFIC EMBODIMENTS

(9) With reference to FIGS. 1 to 4, a block cipher 10 comprises a round key generator 200 taking as input a main key K stored in a register 100. The round key generator 200 generates a sequence 120 of round keys K.sub.0, K.sub.1, K.sub.2, . . . , K.sub.N-1. An encryption module 300 takes as input the sequence of round keys 120 and a plaintext from a register 400. The encryption module 300 encrypt the plaintext 400 with the first key in the sequence, then encrypts the result with the second key in the sequence, and so on for all keys in the sequence, and outputs a cipher text to a register 500 as a result. With reference to FIG. 2, in a decryption mode of the block cipher 10, the encryption module 300 is replaced with a decryption module 302 taking as an input a cipher text from the register 500 and a decryption sequence 142 that is the reverse of the encryption sequence 140 of round keys 142. The decryption module 302 decrypts the cipher text 500 by applying the first key of the sequence 140 (the last key of the sequence 120) to the cipher text 500, then the second key 142 in the sequence 140 to the result of that operation, and so forth, until the last key in the sequence 140 is used to produce the plaintext 400. It will be understood that, according to the embodiment, encryption and decryption modules of the block cipher 10 are implemented in the same device or circuit (in some embodiments sharing computational modules) or in different devices and circuits.

(10) In some embodiments, as illustrated schematically in FIGS. 1 and 2, the round keys are generated independently, that is each round key is stored separately to store the entire sequence 120, 140 of round keys, enabling the round keys of the sequence to be generated in any order or in parallel (and the decryption sequence to be generated by reading the encryption sequence in reverse order without further computation). In other embodiments, as schematically illustrated in FIGS. 3 and 4, the round keys are generated in sequence one at a time. While this is advantageous in requiring less memory to store the round keys and exposing only one round key at a time, it requires that the reverse sequence of round keys is computed again, while in embodiments as depicted in FIGS. 1 and 2, the stored round keys can simply be traversed in the reverse order.

(11) With reference to FIG. 5, a specific embodiment of the round key generator 200 is now described. The main key K is passed through a one-way function 220, also referred to as x, and the result is then passed through a set 240 of sub-functions 242, also referred to as F.sub.0, F.sub.1, F.sub.2, . . . , F.sub.N-1. The result of each sub-function 242 is then passed through a sub-function 262, also referred to as H. The result of each sub-function 242 may be fed to a common one-way function 262 common to all sub-functions, or each sub-function 242 may have a corresponding one-way function 262 to form a set of instances of one-way functions 260, which may all implement the same one-way function H, or different one-way functions, for example a different one-way function 262 for each sub-function 242. These operations result in a set of round keys 122 as the output of the one or more one-way functions 262, in a sequence 120 of sub-keys 122, also referred to as K.sub.0, K.sub.1, K.sub.2, . . . , K.sub.N-1.

(12) Taking the sequence 120 as an encryption sequence, the decryption sequence can be obtained simply by reading the sequence 120 in reverse order in embodiments where the round keys 122 are all stored. In other embodiments, the decryption sequence can be obtained by generating the reverse sequence of round keys by running the sub-functions 242 in reverse order to the sequence 240, for example where only one round key is stored and generated on the fly.

(13) In some embodiments, irrespective of whether the round keys 122 are computed in one go or on the fly, the following functions are used for x, F and H, where p, q, p*, q*, pi and qi are large prime numbers:

(14) x:=K.sup.2 mod N*, with N*=p*q*

(15) Fi(x):=x.sup.2 mod Ni, with Ni=piqi

(16) H(y):=y.sup.8 mod N, with N=pq; y:=Fi(x)

(17) The prime numbers for p* and q*, are chosen such that it is in practice not possible to compute the square root. For example, in some embodiments log.sub.2 (|N*|) is at least 2048 bits. The others primes pi and qi are chosen similarly, for example such that log.sub.2 (|Ni|) is half the number of bits of the output of x (half of log.sub.2 (|N*|)) and p and q are chosen such that log.sub.2 (|N|) is greater or equal the number of bits required in the round keys 122. To protect the main key K from side-channel analysis, a random multiple of N* can be added to K on read out, or K can be stored with such a constant added, as, in embodiments using a mod N* operation as a first stage, this will not affect the output of x.

(18) With reference to FIG. 6, some embodiments in which only a single round key Ki is stored in a register 640 and generated on the fly to generate the sequence 120 is now described. Such embodiments are particularly suitable for implementation in dedicated circuits in which execution can be done quickly in hardware and storage capacity may be limited. A register 100 holding a value for the main key K is read by a module 220 implementing x. The module 220 calculates x(K) and stores it in internal register. A sub-function module 610 configured to compute a sub-function F.sub.i for each iteration of key generation communicates with a register 620 holding a sequence of parameters, each defining a specific instance of F.sub.i for each iteration: F.sub.0, F.sub.1, . . . F.sub.N-2, F.sub.N-1. The sub-function module 610 passes its output to a one-way module 630 implementing the one-way function H to generate an output K.sub.i and store it in a register 640. The sub-function module 610 is configured such that it sends a trigger on a trigger connection 652 to module 220 to receive the value of x(K) again (alternatively this value may be stored in a register in sub-function module 610 or elsewhere). On receiving the value of x(K), the next parameter to define F.sub.i+1 is read from the register 620 and a value for K.sub.i+1 is calculated via one-way module 630.

(19) Embodiments described so far protect the main key by passing it through a first one-way function x and calculate the round keys 122 from this value as independent inputs to respective sub-functions 242. Alternative embodiments are now described with reference to FIGS. 7 to 9, in which a first sub-function 242 of the sequence of sub-functions 240 takes the main key K as an input and subsequent sub-functions F.sub.1, F.sub.2, . . . , F.sub.N-1 244 to 248 (F.sub.1, F.sub.2, . . . , F.sub.N-1) each take the output of the previous sub-function as an input, for example the sub-function 244 takes as input the output of the sub-function 242, and the sub-function 246 takes as input the output of the sub-function 244, and so on. The output of each sub-function 242 to 248 in the sequence 240 is again passed through a one-way 30 function 262, as discussed above with reference to FIG. 5 to produce in turn as an output a sequence 120 of round keys 122 to 128, again as described above with reference to FIG. 5.

(20) In some specific embodiments, F.sub.i is chosen from the classes of functions described above specifically in some embodiments F.sub.i: is a table look up function, and the one-way function H(y) is chosen from the classes of functions described above, specifically in some embodiments, H(y) is a Davis-Meyer construction based on a lightweight permutation. In some embodiments, the one-way function H may be chosen as above, that is H(y):=y.sup.8 mod N. In some embodiments, a first one-way function x, as described above, may be interposed between K and the first sub-function 242 (F.sub.0) of the sequence 240.

(21) Taking the sequence of round keys 120 as the encryption sequence, the decryption sequence can be derived simply by reading the sequence 120 in reverse, in embodiments in which the individual round keys 122 to 128 remain stored. Where the round keys 122 to 128 are not available, they can of course be computed by the sequence of sub-functions 240, as described above, with results read in reverse order once computed. However, it may be desirable to begin the computation of the decryption sequence with the first round key of the decryption sequence, which is the last round key of the encryption sequence. This means that the first key to be used is available first, and enables embodiments in which round keys are computed on the fly and not stored. Some embodiments enabling the reversal of the sequence of round keys to derive a decryption sequence 130 of round keys 122 to 128 are now described with reference to FIG. 8. These embodiments are suitable for computing the reverse or decryption sequence 134 of a forward or decryption sequence 120 derived using sub-functions 242 to 248, which are invertible and from which a composite function that directly computes the result of the sequence of sub-functions 240 can be constructed as a composite function of the sub-functions 242 to 248 as follows:
F.sub.{0.fwdarw.N-1}:=F.sub.0∘F.sub.1∘ . . . ∘F.sub.N-2∘F.sub.N-1

(22) With reference to FIG. 8, a first sub-function 252 of the reverse sequence 250 computes the composite function F.sub.{0.fwdarw.N-1} of the sub-functions of the forward sequence 240 and the output is passed through a one-way function 262 to generate a first round key 128 in the reverse round key sequence 130, corresponding to the last round key 128 of the forward sequence 120, that is K.sub.N-1. The output of the sub-function 252 is also passed to the next sub-function 254 of the reverse sequence 250, which corresponds to the inverse function of the last function 248 of the forward sequence 240, F.sub.N-1.sup.−1. The output of the sub-function 254 is again passed through a one-way function 262 to generate the next round key in the reverse sequence 130, K.sub.N-2, the penultimate round key in the forward sequence 120. The next sub-function 256 in the reverse sequence 250 corresponds to the inverse of the penultimate sub-function in the forward sequence 240, F.sub.N-2.sup.−1, and is used to generate the next round key in the inverse sequence 130, and so forth, until the last sub-function in the reverse sequence 250 which corresponds to the inverse of the second sub-function in the forward sequence 240 is used to generate the last round key 122 in the reverse sequence 130, which is the first round key in the forward sequence 120.

(23) As mentioned above, in these embodiments, the sub-functions are required to be invertible and composable into a composite function. In some embodiments, the sub-functions are invertible table lookup functions or shift or rotation bit operators. As long as the sub-functions are invertible and composable, the sub-functions of the sequence 240 may be all the same, single sub-function, used repeatedly, or may each be different, or a combination of the two.

(24) With reference to FIG. 9, some embodiments in which only a single round key K.sub.i is stored in a register 640 and round keys are generated on the fly to generate the sequence 120 using a sequence of sub-functions 240 is now described. It will be understood that these embodiments are equally suitable for producing the sequence 130 described above using the corresponding sequence 250 of sub-functions. Again, such embodiments are particularly suitable for implementation in dedicated circuits in which execution can be done quickly in hardware and storage capacity may be limited.

(25) A register 100 holding a value for the main key K is read by a sub-function module 610. As described above, the sub-function module 610 also reads one or more parameters to define the function Fi for the relevant iteration and evaluates Fi, supplying the result as an output to a one-way module 630 which calculates a one-way function of its input and stores the result as the round key K.sub.i in register 640. The module 610 also supplies its own output again to its input over a line 660 trigger the calculation of the next sub-function F.sub.i+1 and hence K.sub.i+1 via the one-way function module 630.

(26) All of the above embodiments have been described in terms of generating a single round key K.sub.i from a corresponding sub-function F.sub.i. In these embodiments, the number of bits in the output of the one-way function(s) H must be equal to or greater than the number of bits of the round K.sub.i. It will, of course, be understood that in some embodiments the output of the one-way functions may have less bits than required for the sub-keys. In such embodiments, for example where the number of output bits of the one-way function is ½ the number of bits required, or 1/m more generally, the processes above can be run twice or m times to generate the required bits. Likewise, in some embodiments, the output of two (m) one-way functions run one after the other can be combined to generate the sub-keys in sequence, in effect grouping adjacent round keys (as illustrated in the figures) together to form a round key of sufficient bits.

(27) On the other hand, in some embodiments, the number of bits in the output of H is at least m-fold that of a single round key K.sub.i and m round keys are generated from the output of the one-way function H applied to a corresponding sub-function F.sub.i. In other words, in these embodiments, m round keys K.sub.i.Math.m+j, j=1, 2, . . . , m, are generated from each sub-function F.sub.i. For example, if the output of H has 2048 bits, 16 128 bit round keys K.sub.i can be generated from the output of that function.

(28) In some embodiments, the output bits of H are mapped to the bits of the K.sub.i by a predetermined relationship. For example, if the number of bits of K.sub.i is n, the first n bits of the output of H are used to set the bits of K.sub.0, the next n bits of the output of H are used to set the bits of K.sub.1, and so forth. Other relationships are of course equally possible, for example using the first m bits of the output of H to set the first bits of all K.sub.i using the second m bits of the output of H to set the second bits of K.sub.i, and so forth, or any other predetermined mapping.

(29) In some embodiments, now described with reference to FIG. 10, a single one-way function 280 produces an output with a sufficient number of bits to generate the required number of round keys K.sub.i in the sequence 120, that is there are m round keys in the sequence in terms of the above discussion. Since all round keys are generated from the output of a single one-way function, no sub-functions F.sub.i are required or, alternatively, the one-way function 280 can be seen as the combination of a single sub-function F.sub.i and a one-way function H. As illustrated in FIG. 10 and described above, in some embodiments the bits of contiguous blocks of the output of the one-way function 280 are used to define corresponding K.sub.i round keys, although other schemes of assigning one-way function output bits to round key bits are equally possible, as described above.

(30) While the preceding specific description made reference to some specific functions to implement x, H and F.sub.i, many other suitable functions are possible subject to the constraints explained above, where applicable, in the various embodiments, and will readily occur to a person skilled in the art. Specifically, some suitable functions have been discussed above and may be used in combination with the described specific embodiments.

(31) The following embodiments are also disclosed:

(32) 1. A device for generating from a main key a sequence of sub-keys for cryptographic operations, wherein each sub-key is defined by respective bit values, the device comprising a memory for storing the main and at least one sub-key and a processor configured to:

(33) operate on the main key with a transformation, wherein the transformation comprises one or more one-way functions and the main key is operated on only once to generate the sub-keys of the sequence; and

(34) set the respective bit values of the sub-keys of the sequence using respective bit values of the one or more one-way functions.

(35) 2. A device according to item 1, wherein setting the respective bit values comprises setting the respective bit values of at least two of the sub-keys in accordance with respective bit values of one of the one or more one-way functions according to a pre-defined relationship.

(36) 3. A device according to item 1, wherein setting the respective bit values comprises setting the respective bit values of all the sub-keys of the sequence in accordance with respective bit values of the one of the one or more one-way function according to a pre-defined relationship.

(37) 4. A device according to item 1 or 2, wherein operating on the main key comprises generating a plurality of intermediate outputs and applying a one-way function to each intermediate output to generate a respective one-way output, and wherein the processor is configured to generate one or more of the sub-keys from each one-way output.

(38) 5. A device according to item 1, 2 or 4, wherein the processor is configured to

(39) apply a first sub-function to the main key to generate a first intermediate output;

(40) apply a first one-way function to the first intermediate output; and generate a first one or more of the sub-keys of the sequence from an output of the first one-way function, and

(41) repeatedly: apply a next sub-function to the previous intermediate output to generate a next intermediate output; apply a next one-way function to the next intermediate output; and generate a next one or more of the sub-keys of the sequence from an output of the next one-way function.

(42) 6. A device according to item 1, 2 or 4, wherein the processor is configured to:

(43) apply an input one-way function to the main key to generate a working key;

(44) apply a plurality of sub-functions to the working key to generate respective intermediate outputs,

(45) apply an output one-way function to each intermediate output to generate a respective transformation output; and

(46) generate the sub-keys of the sequence from the transformation outputs.

(47) 7. A device according to any one of items 1 to 6, wherein the processor is configured to implement a block cipher with a key schedule defined by the sequence and to use the sub-keys of the sequence as round keys in the block cipher.

(48) 8. A device for generating from a main key related forward and reverse sequences of sub-keys for use in cryptographic operations, the device comprising a memory for storing the main key and at least one sub-key and a processor configured according to item 5 to generate sub-keys of the forward sequence,

(49) wherein the next sub-functions are applied in a forward next sub-function sequence and

(50) wherein the first sub-function followed by the sub-functions of the forward next sub-function sequence define a forward sub-function sequence;

(51) and wherein the processor is configured according to item 5 to generate from the main key a reverse sequence of sub-keys,

(52) wherein the first sub-function is the composite function of the sub-functions of the forward sub-function sequence and

(53) wherein the next sub-functions are applied in a reverse next sub-function sequence and the sub-functions of the reverse next sub-function sequence correspond to the respective inverse functions of the sub-functions of the forward next sub-functions sequence in reverse order.

(54) 9. A device for decrypting a message encrypted with a block cipher, the block cipher having a key schedule comprising round keys applied in an encryption sequence, the encryption sequence of round keys being obtainable from a main key by a processor configured in accordance with item 5, wherein the next sub-functions are applied in an encryption next sub-function sequence and the first sub-function followed by the sub-functions of the encryption next sub-function sequence define an encryption sub-function sequence, the device comprising a memory for storing a main key and at least one sub-key and a processor configured in accordance with item 5 to generate from the main key a decryption sequence of sub-keys,

(55) wherein the first sub-function is the composite function of the sub-functions of the encryption sub-function sequence and

(56) wherein the next sub-functions are applied in a decryption next sub-function sequence and the sub-functions of the decryption next sub-function sequence correspond to the respective inverse functions of the sub-functions of the encryption next sub-functions sequence in reverse order; and

(57) configured to apply the sub-keys in the order of the decryption sequence to decrypt the message.

(58) 10. A device for processing a message with a block cipher having a key schedule, the device comprising a memory for storing a main key and at least one sub-key and a processor configured to:

(59) encrypt a plaintext of the message with the block cipher to generate a cipher text, wherein the processor is configured in accordance with item 5 to generate round keys of the key schedule in an encryption sequence from a main key, wherein the next sub-functions are applied in an encryption next sub-function sequence and the first sub-function followed by the sub-functions of the encryption next sub-function sequence define an encryption sub-function sequence and wherein the processor is configured to encrypt the plaintext with a first one of the round keys in the encryption sequence to generate a first round text; and for the remaining round keys in the encryption sequence, encrypt a previous round text with a next round key in the encryption sequence to generate a next round text, wherein the last round text is the cipher text; and wherein the processor is further configured to

(60) decrypt the cipher text to generate the plaintext, wherein the processor is configured in accordance with item 5 to generate from the main key a decryption sequence of sub-keys, wherein the first sub-function is the composite function of the sub-functions of the encryption sub-function sequence, and wherein the next sub-functions are applied in a decryption next sub-function sequence and the sub-functions of the decryption next sub-function sequence correspond to the respective inverse functions of the sub-functions of the encryption next sub-functions sequence in reverse order; and wherein the processor is configured to decrypt the cipher text with a first one of the round keys in the decryption sequence to generate a first round text; and for the remaining round keys in the decryption sequence, decrypt a previous round text with a next round key in the decryption sequence to generate a next round text, wherein the last round text is the plaintext.

(61) While the above specific description of some embodiments has been made in terms of a block cipher with a key schedule and defined by certain round key generators, it will be appreciated that the described embodiments of generating sequences of cryptographic keys may find wider application then in the context of a block cipher and round keys. The present disclosure is therefore not limited to the context of a block cipher but encompasses other uses of sub-key sequences generated from a main key in accordance with the disclosed embodiments of round key generators which can thus more generally be described as sub-key generators.

(62) More generally, the above description of specific embodiments has been made by way of example to illustrate aspects of the disclosure in is not to be read as limiting on the subject matter claimed in the claims that follow.