Method and apparatus for data authentication in a data communication environment

• US 5,673,318 A
• Filed: 05/14/1996
• Issued: 09/30/1997
• Est. Priority Date: 04/23/1993
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bellare, Mihir, Guerin, Roch Andre, Rogaway, Phillip Walder
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/647,503
• Time in Patent Office: 504 Days
• Field of Search: 380/4, 380/9, 380/23, 380/25, 380/29, 380/46, 380/49, 380/50
• US Class Current: 713/170
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 2209/20 Manipulating the length of blocks of bits, e.g. padding or block truncation
• CPC Class Codes: H04L 9/0625 with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI
• 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
• CPC Class Codes: H04L 9/3297 involving time stamps, e.g. generation of time stamps

Abstract

A method and system for providing data authentication, within a data communication environment, in a manner which is simple, fast, and provably secure. A data message to be sent is partitioned into data blocks. Each data block is combined with a block index to create a word. A pseudo-random function is applied to each word to create a plurality of enciphered data strings. An identifying header, comprising the identity of the sender and a counter value, is also enciphered using a pseudo-random function. These enciphered data strings and header are logically combined to create a tag. As the enciphering of a particular word occurs independent of the other words, each block can be enciphered independently of the others. The method and system can thus be performed and structured in either a parallel or pipelined fashion. A receiving component or system generates a second tag which can then be compared with the transmitted tag to determine message authentication.

Claims

1. An article of manufacture for allowing a data processing system to determine an authentication tag to be used in conjunction with transfer of data using a communication channel comprising:

a computer readable medium having computer program code embodied therein, the program code comprising;

means for partitioning said data into a plurality of blocks in a system memory;

means for encoding each of said blocks to create a word that represents both a value of each of said blocks and an identifier of each of said blocks;

means for applying a pseudo-random function to each said word to create a plurality of enciphered words;

means for combining said plurality of enciphered words to create a tag;

means for combining the tag and at least some data to create a data packet; and

means for transmitting the data packet over the communication channel.

2. The product of claim 1 wherein said pseudo-random function is a data encryption standard algorithm.

3. The product of claim 1 wherein said blocks are of fixed length.

4. The product of claim 1 wherein said step of combining comprises a logical exclusive-or operation.

5. The product of claim 1 wherein said tag is truncated or otherwise reduced to a given length.

6. The product of claim 1 wherein said pseudo-random function is multi-staged.

16. The product of claim 5 wherein said received time variant parameter comprises a received counter.

7. An article of manufacture for allowing a data processing system to determine an authentication tag to be used in conjunction with transfer of data using a communication channel comprising:

a computer readable medium having computer program code embodied therein, the program code comprising;

means for partitioning said data into a plurality of blocks;

means for combining with each of said blocks a block identifier to create a word;

means for applying pseudo-random function to (i) each said word and (ii) an identifier for said data to create a plurality of enciphered words;

means for combining said plurality of enciphered words to create a tag;

means for combining the tag and at least some data to create a data packet; and

means for transmitting the data packet over the communication channel.

8. The product of claim 7 wherein said pseudo-random function is multi-staged.

9. The product of claim 8 wherein a plurality of said words are pipelined to said multi-staged pseudo-random function.

10. The product of claim 7 wherein a plurality of said words are concurrently presented to a plurality of said pseudo-random functions.

11. The product of claim 7 further comprising combining at least said tag with said identifier to create a message authentication code.

12. The product of claim 7 further comprising;

means for receiving the data packet;

means for extracting the tag and the data from the data packet;

means for generating a second tag from at least the extracted data and a local key; and

means for comparing the extracted tag and the second tag to determine data authenticity of the data packet.

13. The product of claim 7 wherein said block identifier is based upon a block index.

14. An article of manufacture for allowing a data processing system to determine authenticity of a received data packet from a communication channel comprising:

a computer readable medium having computer program code embodied therein, the program code comprising;

means for receiving a received data packet;

means for extracting received data, a received tag and a received time variant parameter from the received data packet;

means for generating a local tag from at least the received data, the received time variant parameter and a local key; and

means for comparing the received tag and the local tag to determine data authenticity of the received data packet.

15. The product of claim 14 wherein said means for comparing further comprises means for comparing said received time variant parameter to a local time variant parameter to further determine said data authenticity.

17. THe product of claim 15 wherein said received time variant parameter comprises a time stamp.

18. The product of claim 15 wherein said received time variant parameter comprises a sequence number.

19. The method of claim 14 wherein said received data packet further comprises a sender identity.

20. The method of claim 19 further comprising obtaining said local key from a local table using said sender identity.