Precomputing internal AES states in counter mode to protect keys used in AES computations

• US 9,716,586 B2
• Filed: 01/19/2016
• Issued: 07/25/2017
• Est. Priority Date: 02/28/2013
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Chevallier-Mames, Benoit, Ciet, Mathieu, Icart, Thomas, Kindarji, Bruno, Farrugia, Augustin J.
• Primary Examiner(s): Tolentino, Roderick
• Assistant Examiner(s): MALINOWSKI, WALTER J
• Application Number:
  US15/000,223
• Publication Number:
  US 20160211972A1
• Time in Patent Office: 553 Days
• Field of Search: 380 28, 380 29, 380 30, 380 37, 380 44
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 9/0631 Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms
• CPC Class Codes: H04L 9/0637 Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM]
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy

Abstract

Methods, media, and systems for, in one embodiment, protecting one or more keys in an encryption and/or decryption process can use precomputed values in the process such that at least a portion of the one or more keys is not used or exposed in the process. In one example of a method, internal states of an AES encryption process are saved for use in a counter mode stream cipher operation in which the key used in the AES encryption process is not exposed or used.

Claims

1. A machine readable non-transitory storage medium containing executable program instructions which when executed by a data processing system cause the data processing system to perform a method comprising:

generating a set of precomputed block cipher encryption values from a key and a set of nonces, the number of nonces in the set of nonces being limited to less than or equal to a number determined from a predetermined maximum plaintext length having a plurality of blocks, wherein the set of precomputed block cipher encryption values comprise a set of internal states of a block encryption algorithm;

storing the set of precomputed block cipher encryption values for use in an encryption operation, in a stream cipher mode, on plaintext; and

transmitting the set of precomputed block cipher encryption values to another data processing system wherein the transmission of the set of precomputed cipher block encryption values does not transmit an external state for at least one nonce in the set of one or more nonces;

wherein the another data processing system can decrypt the cipher text using the set of precomputed block cipher encryption values,wherein the decrypting is performed without exposing or using at least a portion of the key.

2. The medium as in claim 1, the method further comprising:

receiving plaintext having a first length which is less than the predetermined maximum plaintext length.

encrypting the plaintext using the stored set of precomputed block cipher encryption values, wherein the encrypting is performed without exposing the key; and

wherein the predetermined maximum plaintext length is an assumed maximum length.

3. The medium as in claim 2 wherein the encrypting comprises XORing a block of the plaintext and a block value derived from the set of precomputed block cipher encryption values.

4. The medium as in claim 3 wherein the set of nonces comprise an initial nonce and a plurality of updated nonces derived from the initial nonce and from a plurality of counter values having, as one of the counter values, a maximum counter value that is based on a maximum number of blocks contained in the predetermined maximum plaintext length.

5. The medium as in claim 4 wherein each of the plurality of counter values modify a part of a corresponding one of the updated nonces, and wherein the part is restricted to a predetermined number of Least Significant Bytes (LSB) of the updated nonces.

6. The medium as in claim 5 wherein the set of precomputed block cipher encryption values comprise a set of internal states for each nonce of the set of nonces, and wherein each internal state, in the set of internal states, is precomputed using the key.

7. The medium as in claim 6 wherein the encrypting is performed without exposing or using the key and wherein the key is obtained from a key schedule.

8. A machine readable non-transitory storage medium containing executable program instructions which when executed by a data processing system cause the data processing system to perform a method comprising:

precomputing a set of internal states, within a symmetric key block cipher algorithm in counter mode, using a key and a set of one or more nonces, the set of internal states that are precomputed being those internal states that use the key as an input to an operation, in the symmetric key block cipher algorithm, that produces those internal states;

storing the precomputed set of internal states for use in a later encryption or decryption operation, the later encryption or decryption operation being performed without using or exposing at least a portion of the key, wherein the number of nonces in the later encryption or decryption operation is limited to a predetermined value related to a maximum plaintext length having a plurality of blocks; and

transmitting the precomputed set of internal states to a client data processing system for use in a decryption operation, wherein the transmission of the set of precomputed internal states does not transmit an external state for at least one nonce in the set of one or more nonces;

wherein the client data processing system can decrypt the cipher text using the set of precomputed internal states, wherein the decrypting is performed without exposing or using at least a portion of the key.

9. The medium as in claim 8 wherein the symmetric key block cipher algorithm is the Advanced Encryption Standard (AES) and wherein the storing of the precomputed set does not store an external output state for at least one nonce in the set of one or more nonces and wherein the later encryption or decryption operation computes the external state for a particular nonce and then encrypts a plaintext block by bitwise XORing the plaintext block with the external state for the particular nonce or decrypts a ciphertext block by bitwise XORing the ciphertext block with the external state for the particular nonce.

10. The medium as in claim 9 wherein the later encryption or decryption operation computes the external state for a particular nonce without using the key and wherein the key is obtained from a key schedule during the precomputing of the set of internal states.

11. The medium as in claim 10, the method further comprising:

transmitting ciphertext, created by the later encryption operation, to the client data processing system.

12. The medium as in claim 10 wherein the external state for a particular nonce is an output, for the particular nonce, of the AES algorithm.

13. The medium as in claim 12 wherein the set of one or more nonces comprise an initial nonce, and wherein a plurality of updated nonces are derived from the initial nonce and from a plurality of counter values, and wherein the plurality of counter values are restricted to a predetermined number of least significant bytes (LSB) of the plurality of updated nonces.

14. The medium as in claim 13 wherein the later encryption or decryption operation computes the plurality of updated nonces from the precomputed set of internal states.

15. A machine readable non-transitory storage medium containing executable program instructions which when executed by a data processing system cause the data processing system to perform a method comprising:

transmitting, to a client device, a transmission of a cipher text, the cipher text having been encrypted with a key and a set of nonces using the Advanced Encryption Standard (AES) block encryption algorithm;

transmitting, to the client device, a transmission of a set of precomputed block cipher encryption values that were precomputed using the key and the set of nonces, wherein the transmission of the set of precomputed block cipher encryption values does not transmit an external state for at least one nonce in the set of one or more nonces, wherein the set of precomputed block cipher encryption values comprise a set of internal states of the block encryption algorithm;

wherein the client device can decrypt the cipher text using the set of precomputed block cipher encryption values, wherein the decrypting is performed without exposing or using at least a portion of the key.

16. The medium of claim 15, wherein the cipher text was encrypted from a plaintext having a length that is less than a predetermined maximum length.

17. The medium as in claim 16, wherein the number of nonces in the decryption operation is limited to a predetermined value related to the maximum plaintext length having a plurality of blocks.

18. The medium of claim 15, wherein the cipher text was encrypted using the set of precomputed block cipher values without exposing at least a portion of the key.

19. The medium as in claim 15 wherein the set of nonces comprise an initial nonce and a plurality of updated nonces derived from the initial nonce and from a plurality of counter values having, as one of the counter values, a maximum counter value that is based on a maximum number of blocks contained in the predetermined maximum plaintext length.

20. The medium as in claim 19 wherein each of the plurality of counter values modify a part of a corresponding one of the updated nonces, and wherein the part is restricted to a predetermined number of Least Significant Bytes (LSB) of the updated nonces.

21. The medium as in claim 20 wherein the decryption operation computes the external state for a particular nonce and then decrypts a block of cipher text by bitwise XORing the block of cipher text block with the external state for the particular nonce and wherein the plaintext has an arbitrary, unknown length of any number of blocks in the range of 2 to N blocks where N is set by the predetermined value related to the maximum plaintext length.

22. The medium as in claim 21, wherein the decryption operation computes the external state for a particular nonce without using the key.

23. The medium as in claim 22, wherein the external state for a particular nonce is an output, for the particular nonce, of the AES algorithm.

24. The medium as in claim 19, wherein the decryption operation computes the plurality of updated nonces from the precomputed set of internal states.

25. A computer-implemented method comprising:

transmitting, to at a client device, a transmission of a cipher text, the cipher text having been encrypted with a key and a set of nonces using the Advanced Encryption Standard (AES) block encryption algorithm;

transmitting, to the client device, a transmission of a set of precomputed block cipher encryption values that were precomputed using the key and the set of nonces, wherein the transmission of the set of precomputed block cipher encryption values does not transmit an external state for at least one nonce in the set of one or more nonces, wherein the set of precomputed block cipher encryption values comprise a set of internal states of the block encryption algorithm;

wherein the client device can decrypt the cipher text using the set of precomputed block cipher encryption values, wherein the decrypting is performed without exposing or using at least a portion of the key.