Distributed password-based authentication in a public key cryptography authentication system

• US 9,515,996 B1
• Filed: 06/28/2013
• Issued: 12/06/2016
• Est. Priority Date: 06/28/2013
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Juels, Ari, Richards, Gareth
• Primary Examiner(s): Desrosiers, Evans
• Application Number:
  US13/930,884
• Time in Patent Office: 1,257 Days
• Field of Search: 713/176, 713168-174, 713182-186, 713/202, 709/206, 709/225, 709/229, 709/249, 709/389, 726 2- 8
• US Class Current: 1/1
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/0807 using tickets, e.g. Kerberos cryptographic mechanisms or cryptographic arrangements for entity authentication using tickets or tokens H04L9/3213
• CPC Class Codes: H04L 63/083 using passwords cryptographic mechanisms or cryptographic arrangements for entity authentication using a predetermined code H04L9/3226

Abstract

An authentication system comprises a plurality of servers storing respective shares of a private key, and a controller associated with the servers. The authentication system is configured to receive a message comprising a password encrypted using a public key corresponding to the private key. The controller directs performance of distributed password-based authentication in the authentication system based at least in part on the encrypted password utilizing the shares of the private key stored in the respective servers. The message is formatted in a manner consistent with an authentication protocol that normally utilizes public key signatures as a mechanism for authentication but is modified to support password-based authentication. For example, the message may be formatted in a manner consistent with a request message of a Kerberos PKINIT protocol extension.

Claims

1. A method comprising:

storing in a plurality of servers of an authentication system respective shares of a private key;

receiving in the authentication system a message comprising a password encrypted using a public key corresponding to the private key; and

performing distributed password-based authentication in the authentication system based at least in part on the encrypted password utilizing the shares of the private key stored in the respective servers;

wherein the message comprises a request message formatted in accordance with a Kerberos PKINIT protocol extension that has been modified to support password-based authentication by configuring the request message to include a message element that incorporates the encrypted password;

wherein an unmodified version of the Kerberos PKINIT protocol extension is configured to utilize public key signatures as a mechanism for authentication;

wherein the request message comprises an (a, b, c)-formatted authentication service request message of the Kerberos PKINIT protocol extension that has been modified to incorporate the encrypted password;

wherein the modified (a, b, c)-formatted authentication service request message of the Kerberos PKINIT protocol extension comprises a modified authentication service request message AS_REQ*=(a, b*, c), where message elements a and c are the same as in an unmodified authentication service request message AS_REQ and message element b* incorporates the encrypted password; and

wherein the method is implemented by at least one processing device comprising a processor coupled to memory.

2. The method of claim 1 wherein performing distributed password-based authentication in the authentication system comprises:

performing local verifications in respective ones of the servers; and

generating a global verification of the received request message based on results of the local verifications.

3. The method of claim 1 wherein the encrypted password is bound to other message elements through inclusion with those other message elements in a common ciphertext.

4. The method of claim 3 wherein the request message further comprises an additional key used to generate the common ciphertext with said additional key being encrypted using a public key of a key distribution center.

5. The method of claim 1 wherein the servers comprise distributed authentication servers of a key distribution center.

6. The method of claim 1 wherein the (a, b, c)-formatted authentication service request message of the Kerberos PKINIT protocol extension absent the modification to incorporate the encrypted password comprises the unmodified authentication service request message AS_REQ of the form:

AS_REQ=(a,b,c)=Cert_C,Σ

_SKC[t_C,n₂],{C,T,n₁},

where t_c is a timestamp, n₁ and n₂ are random nonces, C is a client identifier, Cert_C is a client certificate, Σ

_SKC is a digital signature generated using a client secret key SK_C, and T is an identifier of the key distribution center.

7. The method of claim 1 wherein the modified (a, b, c)-formatted authentication service request message of the Kerberos PKINIT protocol extension comprises the modified authentication service request message AS_REQ*=(a, b*, c), where message elements a and c are the same as in the unmodified authentication service request message AS_REQ and message element b* is given by:

b*=(r,s)=(Enc2<sub>PKK[λ

],encλ</sub>

*[Z=Enc3_PKDIST[P],Cert_C*,t_C,n₂]),

where P denotes the password, PK_K denotes a public key of the key distribution center, PK_dist denotes the public key corresponding to the private key stored as shares on the servers, Enc_PKK[λ

] denotes encryption of a symmetric key λ

under the public key PK_K, Enc_PKdist[P] denotes encryption of the password P under the public key PK_dist, enc_λ

* denotes an authenticated symmetric-key encryption algorithm using symmetric key λ

, and Cert_C* denotes a certificate generated using a client ephemeral key pair (SK_C, PK_C).

8. The method of claim 7 wherein performing distributed password-based authentication in the authentication system comprises:

computing λ

←

Dec_SKK[r];

computing z=Enc_PKdist[P], Cert_C* , t_c, n₂←

dec_λ

*[s];

verifying AS_REQ* as correct based on results of the computing and freshness of the timestamp t_c; and

if AS_REQ* is verified as correct, providing the encrypted password Enc_PKdist[P] to the plurality of servers for joint verification.

9. The method of claim 1 wherein the modified (a, b, c)-formatted authentication service request message of the Kerberos PKINIT protocol extension comprises the modified authentication service request message AS_REQ*=(a, b*, c), where message elements a and c are the same as in the unmodified authentication service request message AS_REQ and message element b* is given by:

b*=Σ

_SKC*[t_c,n₂]

where Σ

_SKC* denotes a modified digital signature generated using a client secret key SK_C over a plurality of message elements including the encrypted password, and where t_c is a timestamp and n₂ is a random nonce.

10. The method of claim 1 wherein each of the servers stores a secret key SK_K of a key distribution center.

11. The method of claim 1 wherein the public key comprises one of a plurality of signing keys of a given client.

12. The method of claim 1 wherein the request message is received in a key distribution center of the authentication system from a client device.

13. A method comprising:

storing in a plurality of servers of an authentication system respective shares of a private key;

receiving in the authentication system a message comprising a password encrypted using a public key corresponding to the private key; and

performing distributed password-based authentication in the authentication system based at least in part on the encrypted password utilizing the shares of the private key stored in the respective servers;

wherein the message comprises a request message formatted in accordance with a Kerberos PKINIT protocol extension that has been modified to support password-based authentication by configuring the request message to include a message element that incorporates the encrypted password;

wherein an unmodified version of the Kerberos PKINIT protocol extension is configured to utilize public key signatures as a mechanism for authentication;

wherein the request message includes a ciphertext Enc_PKdist[P] on password P under a public key PK_dist for distributed verification using key shares of a corresponding private key SK_dist stored on respective ones of the plurality of servers; and

wherein the method is implemented by at least one processing device comprising a processor coupled to memory.

14. A computer program product comprising a non-transitory processor-readable storage medium having embodied therein one or more software programs, wherein the one or more software programs when executed by at least one processing device cause said at least one processing device:

to store in a plurality of servers of an authentication system respective shares of a private key;

to receive in the authentication system a message comprising a password encrypted using a public key corresponding to the private key; and

to perform distributed password-based authentication in the authentication system based at least in part on the encrypted password utilizing the shares of the private key stored in the respective servers;

wherein the message comprises a request message formatted in accordance with a Kerberos PKINIT protocol extension that has been modified to support password-based authentication by configuring the request message to include a message element that incorporates the encrypted password;

wherein an unmodified version of the Kerberos PKINIT protocol extension is configured to utilize public key signatures as a mechanism for authentication;

wherein the request message comprises an (a, b, c)-formatted authentication service request message of the Kerberos PKINIT protocol extension that has been modified to incorporate the encrypted password; and

wherein the modified (a, b, c)-formatted authentication service request message of the Kerberos PKINIT protocol extension comprises a modified authentication service request message AS_REQ*=(a, b*, c), where message elements a and c are the same as in an unmodified authentication service request message AS_REQ and message element b* incorporates the encrypted password.

15. The computer program product of claim 14 wherein performing distributed password-based authentication in the authentication system comprises:

performing local verifications in respective ones of the servers; and

generating a global verification of the received request message based on results of the local verifications.

16. The computer program product of claim 14 wherein the encrypted password is bound to other message elements through inclusion with those other message elements in a common ciphertext.

17. The computer program product of claim 16 wherein the request message further comprises an additional key used to generate the common ciphertext with said additional key being encrypted using a public key of a key distribution center.

18. An apparatus comprising:

a server comprising a local verifier;

wherein the server is configured for use as one of a plurality of servers of an authentication system storing respective shares of a private key;

the server being configured to store its corresponding share of the private key;

the local verifier being configured to generate an indication based on the stored share and at least a portion of a received message comprising a password encrypted using a public key corresponding to the private key;

wherein the indication is utilizable in conjunction with corresponding indications generated by respective ones of the other servers to implement distributed password-based authentication based at least in part on the encrypted password utilizing the shares of the private key stored in the respective servers;

wherein the message comprises a request message formatted in accordance with a Kerberos PKINIT protocol extension that has been modified to support password-based authentication by configuring the request message to include a message element that incorporates the encrypted password;

wherein an unmodified version of the Kerberos PKINIT protocol extension is configured to utilize public key signatures as a mechanism for authentication;

wherein the request message comprises an (a, b, c)-formatted authentication service request message of the Kerberos PKINIT protocol extension that has been modified to incorporate the encrypted password;

wherein the modified (a, b, c)-formatted authentication service request message of the Kerberos PKINIT protocol extension comprises a modified authentication service request message AS_REQ*=(a, b*, c), where message elements a and c are the same as in an unmodified authentication service request message AS_REQ and message element b* incorporates the encrypted password; and

wherein the server is implemented by at least one processing device comprising a processor coupled to memory.

19. An apparatus comprising:

a controller comprising a global verifier;

the global verifier being configured to interface with a plurality of servers of an authentication system storing respective shares of a private key;

the global verifier being configured to authenticate a received message based on indications from respective ones of the plurality of servers generated in accordance with distributed password-based authentication, the received message comprising a password encrypted using a public key corresponding to the private key;

wherein the message comprises a request message formatted in accordance with a Kerberos PKINIT protocol extension that has been modified to support password-based authentication by configuring the request message to include a message element that incorporates the encrypted password;

wherein an unmodified version of the Kerberos PKINIT protocol extension is configured to utilize public key signatures as a mechanism for authentication;

wherein the request message comprises an (a, b, c)-formatted authentication service request message of the Kerberos PKINIT protocol extension that has been modified to incorporate the encrypted password;

wherein the modified (a, b, c)-formatted authentication service request message of the Kerberos PKINIT protocol extension comprises a modified authentication service request message AS_REQ*=(a, b*, c), where message elements a and c are the same as in an unmodified authentication service request message AS_REQ and message element b* incorporates the encrypted password; and

wherein the controller is implemented by at least one processing device comprising a processor coupled to memory.

20. An authentication system comprising:

a plurality of servers storing respective shares of a private key; and

a controller associated with the servers;

wherein the authentication system is configured to receive a message comprising a password encrypted using a public key corresponding to the private key;

wherein the controller directs performance of distributed password-based authentication in the authentication system based at least in part on the encrypted password utilizing the shares of the private key stored in the respective servers;

wherein the message comprises a request message formatted in accordance with a modified Kerberos PKINIT protocol extension that supports password-based authentication by configuring the request message to include a message element that incorporates the encrypted password;

wherein an unmodified version of the modified Kerberos PKINIT protocol extension is configured to utilize public key signatures as a mechanism for authentication;

wherein the request message comprises an (a, b, c)-formatted authentication service request message of the Kerberos PKINIT protocol extension that has been modified to incorporate the encrypted password;

wherein the modified (a, b, c)-formatted authentication service request message of the Kerberos PKINIT protocol extension comprises a modified authentication service request message AS_REQ*=(a, b*, c), where message elements a and c are the same as in an unmodified authentication service request message AS_REQ and message element b* incorporates the encrypted password; and

wherein the plurality of servers and the controller are implemented by at least one processing device comprising a processor coupled to memory.

21. A communication system comprising the authentication system of claim 20 and one or more client devices, a given one of the client devices being adapted to provide the request message to the authentication system over a network in conjunction with an authentication attempt.