Authentication protocol using a multi-factor asymmetric key pair

• US 20060184787A1
• Filed: 02/14/2005
• Published: 08/17/2006
• Est. Priority Date: 02/14/2005
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: TriCipher, Inc. (Broadcom, Inc.)
• Inventors: Ganesan, Ravi, Schoppert, Brett Jason, Sandhu, Ravinderpal Singh, deSa, Colin Joseph, Bellare, Mihir
• Granted Patent: US 7,386,720 B2
• Time in Patent Office: Days
• US Class Current: 713/155
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

Techniques for user authentication based upon an asymmetric key pair having a public key and a split private key are provided. A first portion of the split private key is generated based upon multiple factors under control of the user. The factors include a password. A challenge is cryptographically combined with a first one of the multiple factors, but not the user password, to form a first message. The first message is transformed with the generated first portion to form a second message, which is then sent to an authentication entity. The sent second message is transformed to authenticate the user by proving direct verification of user control of the first factor.

Claims

1. A method for user authentication based upon an asymmetric key pair having a public key and a split private key, comprising:

generating a first portion of the split private key based upon multiple factors under control of the user, the multiple factors including a user password;

cryptographically combining a challenge with a first one of the multiple factors other than the user password to form a first message;

transforming the first message with the generated first portion to form a second message;

transmitting the second message to an authentication entity; and

transforming the transmitted second message to authenticate the user, the transformation of the transmitted second message providing direct verification of user control of the first factor.

2. The method of claim 1, wherein the transformation of the transmitted second message provides direct verification of user control of the first factor and indirect verification of user control of the password.

3. The method of claim 2, wherein:

transforming the transmitted second message includes applying a second portion of the split private key and the public key of the asymmetric key pair to the transmitted second message to recover the first message; and

recovery of the first message provides the indirect verification of user control of the password.

4. The method of claim 1, wherein:

forming the first message includes cryptographically combining the challenge with each of the multiple factors other than the user password; and

the transformation of the transmitted second message provides direct verification of user control of each of the multiple factors combined with the challenge.

5. The method of claim 4, wherein the asymmetric key pair having a public key and a split private key is a first asymmetric key pair, the multiple factors are the password, a first entire private key associated with a second asymmetric key pair, and a second entire private key associated with a third asymmetric key pair, and further comprising:

cryptographically signing a first hash of the challenge with the first entire private key, cryptographically singing a second hash of the challenge with the second entire private key, and combining the cryptographically signed first and second hashes with the challenge to cryptographically combine the challenge with each of the multiple factors other than the user password to form a first message.

6. The method of claim 5, further comprising:

applying a first public key associated with the second asymmetric key pair to the signed first hash to recover the challenge to provide direct verification of user control of the first entire private key; and

applying a second public key associated with the third asymmetric key pair to the signed second hash to recover the challenge to provide direct verification of user control of the second entire private key.

7. The method of claim 1, further comprising:

receiving the challenge from the authentication entity prior to cryptographically combining the challenge with the first factor.

8. The method of claim 1, further comprising:

destroying the generated first portion after transforming the first message.

9. The method of claim 1, further comprising:

performing multiple cryptographic operations to produce a result, at least one of the multiple cryptographic operations based upon less than all the multiple factors, and a final performed one of the multiple cryptographic operations based upon all the multiple factors, and performing a cryptographic operation based upon the produced result to generate the first portion of the split private key.

10. The method of claim 1, wherein the password is not stored in a persistent state.

11. A system for user authentication based upon an asymmetric key pair having a public key and a split private key, comprising:

a first network station configured to i) generate a first portion of the split private key based upon multiple factors under control of the user, the multiple factors including a user password, ii) cryptographically combine a challenge with a first one of the multiple factors other than the user password to form a first message, iii) transform the first message with the generated first portion to form a second message, and iv) transmitting the second message; and

a second network station configured to i) receive the transmitted second message, and ii) transform the transmitted second message to authenticate the user;

wherein the transformation of the transmitted second message provides direct verification of user control of the first factor.

12. The system of claim 11, wherein the transformation of the transmitted second message provides direct verification of user control of the first factor and indirect verification of user control of the password.

13. The system of claim 12, wherein:

transforming the transmitted second message includes applying a second portion of the split private key and the public key of the asymmetric key pair to the transmitted second message to recover the first message; and

recovery of the first message provides the indirect verification of user control of the password.

14. The system of claim 11, wherein:

the first network station is further configured to cryptographically combine the challenge with each of the multiple factors other than the user password to form the first message; and

the transformation of the transmitted second message provides direct verification of user control of each of the multiple factors combined with the challenge.

15. The system of claim 14, wherein:

the asymmetric key pair having a public key and a split private key is a first asymmetric key pair;

the multiple factors are the password, a first entire private key associated with a second asymmetric key pair, and a second entire private key associated with a third asymmetric key pair;

the first network station is further configured to form the first message by i) cryptographically signing a first hash of the challenge with the first entire private key, cryptographically singing a second hash of the challenge with the second entire private key, and combining the cryptographically singed first and second hashes with the challenge.

16. The system of claim 15, wherein the second network station is further configured to i) apply a first public key associated with the second asymmetric key pair to the signed first hash to recover the challenge to provide direct verification of user control of the first entire private key, and ii) apply a second public key associated with the third asymmetric key pair to the signed second hash to recover the challenge to provide direct verification of user control of the second entire private key.

17. The system of claim 11, wherein:

the second network station is further configured to transmit the challenge to the first network station; and

the first network station is further configured to receive the transmitted challenge prior to cryptographically combining the challenge with the first factor.

18. The system of claim 11, wherein the first network station is further configured to destroy the generated first portion after transforming the first message.

19. The system of claim 11, wherein the first network station is further configure to i) perform multiple cryptographic operations to produce a result, at least one of the multiple cryptographic operations based upon less than all the multiple factors, and a final performed one of the multiple cryptographic operations based upon all the multiple factors, and ii) perform a cryptographic operation based upon the produced result to generate the first portion of the split private key.

20. The system of claim 11, wherein the password is not stored in a persistent state.