Method and apparatus for entity authentication and session key generation

• US 6,292,896 B1
• Filed: 01/22/1997
• Issued: 09/18/2001
• Est. Priority Date: 01/22/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wells, Bruce Robert, McGee, Harvey Tildon, Guski, Richard Henry, Dayka, John Carr
• Primary Examiner(s): Swann, Tod
• Assistant Examiner(s): Smithers, Matthew
• Application Number:
  US08/785,939
• Time in Patent Office: 1,700 Days
• Field of Search: 380/21, 380/23, 380/25, 380/44, 380/283, 380/282, 713/171, 713/162, 713/169, 713/159
• US Class Current: 713/169
• CPC Class Codes: H04L 63/0838 using one-time-passwords
• 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/0866 involving user or device identifiers, e.g. serial number, physical or biometrical information, DNA, hand-signature or measurable physical characteristics
• CPC Class Codes: H04L 9/088 Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068
• CPC Class Codes: H04L 9/3228 One-time or temporary data, i.e. information which is sent for every authentication or authorization, e.g. one-time-password, one-time-token or one-time-key
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC

Abstract

A system for authenticating a first entity to a second entity and for simultaneously generating a session key for encrypting communications between the entities. The first entity generates an authentication value by encrypting time-dependent information using a long-lived secret key shared by the entities and transmits the authentication value to the second entity. The first entity independently encrypts other time-dependent information using the long-lived key to generate a session key that cannot be derived from the authentication value without the long-lived key. Upon receiving the transmitted authentication value, the second entity checks the transmitted authentication value using the shared long-lived key to determine whether it is valid. If the authentication value is valid, the second entity authenticates the first entity and generates an identical session key from the same shared secret information and time-dependent information. The encrypted time-dependent information is passed through a key weakening function to generate a weakened key which is used as the session key. The key weakening function includes a one-way function to protect the input value from discovery by an attacker who may have ascertained the weakened session key.

Claims

1. A method for authenticatiing a first entity to a second entity and for generating a secret session key for communication between said entities, wherein said first entity performs the steps of:

generating an authentication value from secret information shared by said entities and nonsecret time-dependent information;

transmitting said authenitcation value to said second entity to authenticate said first entity to said second entity;

generating from said shared secret information and said nonsecret time-dependent information a secret session key that cannot be derived from said authentication value without said shared secret information; and

using said secret session key for encrypted communications with said second entity.

2. The method of claim 1 wherein said shared secret information comprises an encryption key, said step of generating said session key comprising the step of:

encrypting said nonsecret time-dependent information using said encryption key to generate said session key.

3. The method of claim 1 wherein said step of generating said session key comprises the step of:

transforming a strong encryption key derived from said shared secret information into a weakened encryption key from which said session key is derived using a key weakening function, said strong encryption key being selected from a first key space composed of a first number of keys, said key weakening function mapping each strong key from said first key space to a corresponding weakened key in a second key space composed of a smaller number of keys than said first key space.

4. The method of claim 3 wherein said strong encryption key is derived from said shared secret information by encrypting said nonsecret time-dependent infromation using said shared secret infromation as an encryption key.

5. The method of claim 3 wherein said session key comprises said weakened key.

6. The method of claim 3 wherein said shared secret information comprises said strong encryption key.

7. The method of claim 3 wherein said session key is derived from said weakened key by encrypting said nonsecret time-dependent information using said weakened key as an encryption key.

8. The method of claim 3 wherein said first key space is composed of 2⁵⁶ keys and said second key space is composed of 2⁴⁰ keys.

9. The method of claim 3 wherein said transforming step comprises the step of:

fixing predetermined bits of an input value derived from said strong key to generate an output value, said weakened key being derived from said output value.

10. The method of claim 9 wherein said transforming step comprises the further step of:

passing said strong key through a one-way function to generate said input value.

11. The method of claim 9 wherein said transforming step comprises the further step of:

pseudorandomly transforming said output value to generate said weakened key.

12. The method of claim 2 wherein said nonsecret time-dependent information is combined with an additional value before being encrypted.

13. The method of claim 2 wherein said nonsecret time-dependent information is concatenated with an additional value.

14. The method of claim 2 wherein said additional value is derived from said shared secret information.

15. The method of claim 1 wherein said nonsecret time-dependent information comprises time-of-day (TOD) information.

16. The method of claim 1 wherein said authentication value comprises a password.

17. The method of claim 1 wherein said step of generating said authentication value comprises the steps of:

combining said nonsecret time-dependent information with non-time-dependent information to generate composite information; and

encrypting said composite information to generate said authentication value.

18. The method of claim 17 wherein said nonsecret time-dependent information is combined with said non-time-dependent information by modulo addition.

19. The method of claim 17 wherein said non-time-dependent information is derived by encrypting nonsecret information identifying a request for authentication to generate encrypted information.

20. The method of claim 17 wherein said encrypted information is partitioned into two parts, one of which is combined with said nonsecret time-dependent information to generate said composite information and the other of which is used to generate said session key.

21. The method of claim 1 wherein said second entity performs the steps of:

receiving said authentication value from said first entity;

validating said authentication value using said shared secret information to determine whether said authentication value is valid; and

if said authentication value is determined to be valid, authenticating said first entity and generating said session key from said shared secret information and said time-dependent information.

22. The method of claim 21 wherein said step of validating said authentication value includes the steps of:

recovering said nonsecret time-dependent information from said authentication value and said shared secret information; and

comparing the recovered nonsecret time-dependent information with reference nonsecret time-dependent information.

23. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps of claim 1.

24. In a system in which a first entity generates an authentication value from secret information and nonsecret time-dependent information and transmits said authentication value to a second entity sharing said secret information with said first entity, a method for authenticating said first entity and for generating a secret session key for communication with said first entity, wherein said second entity performs the steps of:

receiving said authentication value from said first entity;

validating said authentication value using said shared secret information to determine whether said authentication value is valid;

if said authentication value is determined to be valid, authenticating said first entity and generating from said shared secret information and said nonsecret time-dependent information a secret session key that cannot be derived from said authentication value without said shared secret information; and

using said secret session key for encrypted communications with said first entity.

25. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps of claim 24.

26. Apparatus for authenticating a first entity to a second entity and for generating a secret session key for communication between said entities, said apparatus comprising:

means associated with said first entity for generating an authentication value from secret information shared by said entities and nonsecret time-dependent information;

means associated with said first entity for transmitting said authentication value to said second entity to authenticate said first entity to said second entity;

means associated with said first entity for generating from said share secret information and said nonsecret time-dependent information a secret session key that cannot be derived from said authentication value without said shared secret information; and

means associated with said first entity for using said secret session key for encrypted communications with said second entity.

27. In a system in which a first entity generates an authentication value from secret information and nonsecret time-dependent information and transmits said authentication value to a second entity sharing said secret information with said first entity, apparatus for authenticating said first entity and for generating a secret session key for communication with said first entity, comprising:

means associated with said second entity for receiving said authentication value from said first entity;

means associated with said second entity for validating said authentication value using said shared secret information to determine whether said authentication value is valid;

means associated with said second entity and responsive to a determination that said authentication value is valid for authenticating and said first entity and generating from said shared secret information and said nonsecret time-dependent information a secret session key that cannot be derived from said authentication value without said shared secret information; and

means addociated with said second entity for using said secret session key for encrypted communications with said first entity.