Fast encryption and authentication for data processing systems

• US 20040019783A1
• Filed: 07/24/2002
• Published: 01/29/2004
• Est. Priority Date: 07/24/2002
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Rose, Gregory G., Hawkes, Philip Michael
• Granted Patent: US 7,305,084 B2
• Time in Patent Office: Days
• US Class Current: 713/161
• 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/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC

Abstract

Methods and apparatus are presented for secure, authenticated communication and data storage. The methods can be based on other methods such as IAPM, in which the encryption and authentication keys are of the same strength. In the HR-IAPM mode, a sender encrypts the data as in the IAPM mode using two encryption keys K₀ and K₁. The sender then XORs the plaintexts with corresponding ciphertexts, and combines the results to form a checksum This checksum is encrypted under the authentication key K₂, this value is appended to the encrypted message as a message authentication code (MAC). The receiver decrypts as with IAPM, XORs the plaintexts with the corresponding ciphertexts and combines these values to form a checksum. The receiver then encrypts the checksum under the authentication key K₂ and verifies that the resulting value agrees with the MAC. The HR mode allows blocks to be sent un-encrypted if desired.

Claims

1. A method for encrypting and authenticating data as a single entity, comprising:

arranging data into a plurality of plaintext blocks, determining a plurality of noise blocks using a nonce value and a first key;

determining a plurality of ciphertext blocks by combining each of the plurality of plaintext blocks with a corresponding noise block to form an intermediate plaintext block, encrypting the intermediate plaintext block to form an intermediate ciphertext block, and combining the intermediate ciphertext block with the corresponding noise block to form a plurality of ciphertext blocks;

computing an input checksum value by combining the plurality of plaintext blocks that are not specified by at least one cleartext position and a noise block;

computing an output checksum value by combining the plurality of ciphertext blocks that are specified by the at least one cleartext position and another noise block;

computing an authentication tag by encrypting the input checksum value and combining the encrypted input checksum value with the output checksum value;

replacing each of the plurality of ciphertext blocks that is specified by the at least one cleartext position with a corresponding plaintext block; and

appending the authentication tag.

2. The method of claim 1, wherein the nonce value is predetermined.

3. The method of claim 1, wherein the nonce value is negotiated between a sender and a receiver.

4. The method of claim 1, wherein the encrypting uses block cipher encryption.

5. The method of claim 1, wherein the encrypting comprises:

choosing to apply block cipher encryption or block cipher decryption;

selecting a block cipher to use, according to a set of predetermined selection rules; and

forming the plurality of intermediate ciphertext blocks by applying the chosen block cipher encryption or block cipher decryption to one of the plurality of plaintext blocks combined with the corresponding noise block.

6. The method of claim 1, wherein combining is performed using a bit-wise exclusive-or operation.

7. The method of claim 1, wherein combining is performed using a group operator.

8. The method of claim 7, wherein the group operator is a modular integer addition operator.

9. A method for decrypting and verifying a plurality of received transmission blocks accompanied by an authentication tag, comprising:

determining a plurality of noise blocks using a nonce value;

for each of the plurality of received transmission blocks not specified by a cleartext position, determining a first plurality of plaintext blocks using a decryption mode;

for each of the plurality of received transmission blocks specified by a cleartext position, determining a plurality of secondary ciphertext blocks using an encryption mode;

determining a second plurality of plaintext blocks by setting each of the second plurality of plaintext blocks equal to a corresponding one of the plurality of received transmission blocks specified by a cleartext position;

computing an input checksum value based on the first plurality of plaintext blocks and the last noise block;

computing an output checksum value based on the plurality of second ciphertext blocks and the first noise block; and

verifying the authentication tag using the input checksum value and the output checksum value.

10. The method of claim 9, wherein verifying the authentication tag comprises:

computing a test authentication tag by encrypting the input checksum value and combining the encrypted input checksum value with the output checksum value; and

comparing the test authentication tag with the authentication tag, wherein the authentication tag is verified if the test authentication tag and authentication tag are the same.

11. The method of claim 9, wherein verifying the authentication tag comprises:

combining the authentication tag with the output checksum value to form a test input checksum value;

encrypting the input checksum value; and

comparing the test input checksum value with the encrypted input checksum value, wherein the authentication tag is verified if the test input checksum value and the encrypted input checksum value are the same.

12. The method of claim 9, wherein verifying the authentication tag comprises:

combining the authentication tag with the output checksum value to form a test input checksum value;

decrypting the test input checksum value; and

comparing the decrypted test input checksum value with the input checksum value, wherein the authentication tag is verified if the decrypted test input checksum value and the input checksum value are the same.

13. Apparatus for encrypting and authenticating data as a single entity, comprising:

at least one memory element; and

at least one processing element configured to execute a set of instructions stored on the at least one memory element, the set of instructions for;

determining a plurality of noise blocks using a nonce value and a first key;

determining a plurality of ciphertext blocks by combining each of the plurality of plaintext blocks with a corresponding noise block to form an intermediate plaintext block, encrypting the intermediate plaintext block to form an intermediate ciphertext block, and combining the intermediate ciphertext block with the corresponding noise block to form a plurality of ciphertext blocks;

computing an input checksum value by combining the plurality of plaintext blocks that are not specified by at least one cleartext position and a noise block;

computing an output checksum value by combining the plurality of ciphertext blocks that are specified by the at least one cleartext position and another noise block;

computing an authentication tag by encrypting the input checksum value and combining the encrypted input checksum value with the output checksum value;

replacing each of the plurality of ciphertext blocks that is specified by the at least one cleartext position with a corresponding plaintext block; and

appending the authentication tag.

14. Apparatus for decrypting and verifying a plurality of received transmission blocks accompanied by an authentication tag, comprising:

at least one memory element; and

at least one processing element, the at least one processing element configured to execute a set of instructions store on the at least one memory element, the set of instructions for;

determining a plurality of noise blocks using a nonce value;

for each of the plurality of received transmission blocks not specified by a cleartext position, determining a first plurality of plaintext blocks using a decryption mode;

for each of the plurality of received transmission blocks specified by a cleartext position, determining a plurality of secondary ciphertext blocks using an encryption mode;

determining a second plurality of plaintext blocks by setting each of the second plurality of plaintext blocks equal to a corresponding one of the plurality of received transmission blocks specified by a cleartext position;

computing an input checksum value based on the first plurality of plaintext blocks and a noise block;

computing an output checksum value based on the plurality of second ciphertext blocks and another noise block; and

verifying the authentication tag using the input checksum value and the output checksum value.

15. Apparatus for encrypting and authenticating data as a single entity, comprising:

means for determining a plurality of noise blocks using a nonce value and a first key;

means for determining a plurality of ciphertext blocks by combining each of the plurality of plaintext blocks with a corresponding noise block to form an intermediate plaintext block, encrypting the intermediate plaintext block to form an intermediate ciphertext block, and combining the intermediate ciphertext block with the corresponding noise block to form a plurality of ciphertext blocks;

means for computing an input checksum value by combining the plurality of plaintext blocks that are not specified by at least one cleartext position and a noise block;

means for computing an output checksum value by combining the plurality of ciphertext blocks that are specified by the at least one cleartext position and another noise block;

means for computing an authentication tag by encrypting the input checksum value and combining the encrypted input checksum value with the output checksum value;

means for replacing each of the plurality of ciphertext blocks that is specified by the at least one cleartext position with a corresponding plaintext block; and

means for appending the authentication tag.

16. Apparatus for decrypting and verifying a plurality of received transmission blocks accompanied by an authentication tag, comprising:

means for determining a plurality of noise blocks using a nonce value;

means for for each of the plurality of received transmission blocks not specified by a cleartext position, determining a first plurality of plaintext blocks using a decryption mode;

means for for each of the plurality of received transmission blocks specified by a cleartext position, determining a plurality of secondary ciphertext blocks using an encryption mode;

means for determining a second plurality of plaintext blocks by setting each of the second plurality of plaintext blocks equal to a corresponding one of the plurality of received transmission blocks specified by a cleartext position;

means for computing an input checksum value based on the first plurality of plaintext blocks and a noise block;

means for computing an output checksum value based on the plurality of second ciphertext blocks and another noise block; and

means for verifying the authentication tag using the input checksum value and the output checksum value.

17. A method for secure data transmissions, wherein a first portion of the data transmission is sent as plaintext, a second portion of the data transmission is sent as ciphertext, and all of the data transmission is authenticated, the method comprising:

encrypting the first portion of the data transmission a first ciphertext portion and the second portion of the data transmission into a second ciphertext portion, wherein the first portion of the data transmission is specified by a set of cleartext positions and the second portion of the data transmission is not associated with any one of the set of cleartext positions;

generating an input checksum value using the second portion of the data transmission and a noise block;

generating an output checksum value using the second ciphertext portion and another noise block;

forming an authentication tag from the input checksum value and the output checksum value; and

transmitting the first portion of the data transmission, the second ciphertext portion, and the authentication tag.

18. Apparatus for secure data transmissions, wherein a first portion of the data transmission is sent as plaintext, a second portion of the data transmission is sent as ciphertext, and all of the data transmission is authenticated, the apparatus comprising:

means for encrypting the first portion of the data transmission a first ciphertext portion and the second portion of the data transmission into a second ciphertext portion, wherein the first portion of the data transmission is specified by a set of cleartext positions and the second portion of the data transmission is not associated with any one of the set of cleartext positions;

means for generating an input checksum value using the second portion of the data transmission and a noise block;

means for generating an output checksum value using the second ciphertext portion and another noise block;

means for forming an authentication tag from the input checksum value and the output checksum value; and

means for selecting the first portion of the data transmission, the second ciphertext portion, and authentication tag for transmission.