Back-end matching method supporting front-end knowledge-based probabilistic authentication systems for enhanced credential security

• US 9,215,072 B1
• Filed: 10/23/2012
• Issued: 12/15/2015
• Est. Priority Date: 10/23/2012
• Status: Active Grant

• Current Assignee: Authernative
• Original Assignee: Authernative
• Inventors: Barton, Edward M., Mizrah, Len L.
• Primary Examiner(s): Chai, Longbit
• Application Number:
  US13/658,815
• Publication Number:
  US 20150341327A1
• Time in Patent Office: 1,148 Days
• Field of Search: 726/5
• US Class Current: 1/1
• CPC Class Codes: G06F 21/36 by graphic or iconic representation
• CPC Class Codes: H04L 63/083 using passwords cryptographic mechanisms or cryptographic arrangements for entity authentication using a predetermined code H04L9/3226
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/3226 using a predetermined code, e.g. password, passphrase or PIN network architectures or network communication protocols for supporting authentication of entities using passwords in a packet data network H04L63/083
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

A party can authenticate itself by interacting with multiple servers without revealing the shared secret to any of the involved parties. The stored shared secret is strengthened and broken into shares and saved on the servers. The shared secret is safe against offline brute force attack unless all servers where the shares are stored are compromised. The compromise of any single server, or multiple servers—but less than the maximum number—will not allow the attacker to do a brute force analysis on the shared secret. This back end security enhancement is suitable for probabilistic front end authentication algorithms.

Claims

1. A method for knowledge-based probabilistic authentication of a client by server side resources, using a client identifier and a client credential having a number of elements, where each element of the credential represents a character that is mapped to a selected grid location parameter, indicated in a challenge, from a set of N×

N grid parameters, the method comprising;

storing data in a computer memory including a first data set for a client identifier including a representation of a client credential accessible by a first server in server side resources, wherein the representation includes at least one of processed credential elements generated from a one-way function of the at least one credential element and protected data, and wherein the protected data cannot be determined by the first server, and a second data set including at least part of said protected data accessible by a second server in the server side resources;

sending from the first server, to authenticate a user, a set of N×

N grid parameters (N as a greater than zero integer) of fields filled with random digital content different in each of a plurality of sessions and a challenge of a plurality of session values, and in response from the user, receiving using the first server via data communications, a client identifier and an authentication response corresponding to the challenge that comprises said plurality of session values and each of the plurality of session values can be specified as, at least, a character that is mapped to a selected grid location parameter, indicated in the challenge, from the set of N×

N grid parameters;

transforming in the server side resources, said session values of the authentication response into corresponding sets of intermediate values, each set in said sets of intermediate values having a member for the selected grid location parameter to which the corresponding session value of the response can be mapped, and sending said sets of intermediate values to the second server;

generating a plurality of sets of processed credential element match values using the second server, wherein each set of processed credential element match values of the authentication response is derived based upon said one-way function of said protected data and a corresponding one of said sets of intermediate values, and sending said plurality of sets of processed credential element match values to the first server in an order different from an order in which the sets of intermediate values were received using the second server;

determining using the first server, whether each of the sets of processed credential element match values includes one member that matches one of the processed credential elements in the representation of the client credential; and

if all of the sets of processed credential element match values for a given authentication response include one member that matches one of the processed credential elements in the representation of the client credential, then signaling authentication success.

2. The method of claim 1, wherein the one-way function includes a hash.

3. The method of claim 1, including generating said representation of the credential in a set up operation, comprising using a client platform:

receiving input data including said client identifier and said credential;

encoding said elements of said credential into corresponding credential values, said credential having a number N elements having credential values;

generating a random value K;

using a one-way function, computing said processed credential elements for said representation of the credential using a combination of the value K and the credential values; and

sending said client identifier and said processed credential elements to the first server.

4. The method of claim 3, including encrypting said value K using the client platform using an encryption tunnel between the client platform and the second server to form said protected data, and sending said encrypted protected data to the first server;

assigning an alias for the client identifier using the first server; and

sending said encrypted protected data and said alias to the second server.

5. The method of claim 1, wherein said protected data comprises a random value K, and said one-way function uses a combination of the value K and corresponding elements of the credential to produce the processed credential elements.

6. The method of claim 1, wherein said protected data comprises a product KM of a random matrix K and a matrix M having elements that are functions (hashes) of combinations of a first key (mKEY) and said elements of the credential, one-way function uses a combination of a second key (hKEY) and elements of a matrix equal to a product SKM of a random matrix S and said product KM to produce the processed credential elements;

members of said sets of intermediate values being products KM_P(j) of the matrix K and possible value matrices M_P(j), the possible value matrices M_P(j) having elements that are functions of combinations of said first key and the possible parameters (grid locations) in the parameter set to which the corresponding session value of the response can be mapped; and

for each of said sets of intermediate values, computing said sets of possible processed credential element match values using the second server, members of said sets of possible processed credential element match values being results of said one-way function using a combination of said second key and elements of the matrices equal to the product S(KM_P(j)) of the matrix S and said products KM_P(j).

7. The method of claim 6, wherein the product KM and the second key are produced using a client platform, and protected from determination by the first server by encryption, and including decrypting the product KM and the second key (hKEY) using the second server.

8. The method of claim 1, wherein said protected data comprises a set of values KM generated using an exponentiation function M^K of a generator M and an exponent K, where the generator M is a function of a parameter from the parameter set and a first key, and K is a random value, and said processed credential elements are a function of results SKM of an exponentiation function KM^S, where S is a random value, and said second key.

9. The method of claim 8, wherein the values KM and the second key are produced using a client platform, and protected from determination by the first server by encryption, and including decrypting the values KM and the second key using the second server.

10. The method of claim 1, including generating said representation of the credential in a set up operation, comprising:

using a client platform;

receiving input data including said client identifier and said credential;

encoding said elements of said credential into corresponding credential values, said credential having a number N elements having credential values;

generating a random value K;

using a one-way function, computing intermediate values using a combination of the value K and the credential values;

encrypting said intermediate values using the client platform using an encryption tunnel between the client platforms and the second server to form encrypted protected data;

sending the protected data the value K and the client identifier to the first server;

using the first server;

storing the value K and the client identifier in memory accessible by the first server, assigning an alias to the client identifier, and sending the encrypted protected data and the alias to the second server;

using the second server;

decrypting the encrypted protected data to recover said intermediate values, and generating a random value S;

using a one-way function, computing said processed credential elements using a combination of the value S and the intermediate values; and

sending said processed credential elements to the first server.

11. The method of claim 1, including generating said representation of the credential in a set up operation, comprising

using a client platform:

receiving input data including said client identifier and said credential;

encoding said elements of said credential into corresponding credential values, said credential having a number N elements having credential values;

forming a matrix P having elements that consist of said credential values of said N elements;

forming a matrix K having random elements;

generating a first key (mKEY) and a second key (hKEY);

generating a matrix M having elements determined by a function of the first key and the matrix P;

generating an intermediate value matrix using a matrix product KM;

encrypting said intermediate value matrix KM and the second key using the client platform using an encryption tunnel between the client platform and the second server to form encrypted protected data;

sending the encrypted protected data, the matrix K, the first key and the client identifier to the first server;

using the first server;

storing the matrix K, the first key and the client identifier in memory accessible by the first server, assigning an alias to the client identifier, and sending the protected data and the alias to the second server;

using the second server;

decrypting the encrypted protected data to recover said intermediate value matrix KM and the second key, storing the second key and the alias in memory accessible to the second server, and generating matrix S having random elements;

generating a matrix using a matrix product S(KM);

using a one-way function, computing said processed credential elements using a combination of the elements of the matrix product S(KM) and the second key; and

sending said processed credential elements to the first server.

12. The method of claim 1, including generating said representation of the credential in a set up operation, comprising

using a client platform:

receiving input data including said client identifier and said credential;

encoding said elements of said credential into corresponding credential values, said credential having a number N elements having credential values;

generating a random value K;

randomly generating a first key (mKEY) and a second key (hKEY);

generating generators M corresponding to each part of said credential, the generators being a determined by a function of the first key and the credential values of the elements of said credential;

calculating intermediate values KM using a exponentiation function M^K for each generator M;

encrypting said intermediate values KM and the second key using the client platform and an encryption tunnel between the client platform and the second server to form said protected data;

sending the encrypted protected data, the random value K, the first key and the client identifier to the first server;

using the first server;

storing the random value K, the first key and the client identifier in memory accessible by the first server, assigning an alias to the client identifier, and sending the encrypted protected data and the alias to the second server;

using the second server;

decrypting the encrypted protected data to recover said intermediate values KM and the second key, storing the second key and the alias in memory accessible to the second server, and generating a random value S;

calculating values SKM using an exponentiation function KM^S for each said intermediate values KM;

computing said processed credential elements using a function (e.g. a hash) of a combination the values SKM and the second key; and

sending said processed credential elements to the first server.

13. The method of claim 1, including presenting a session specific instance of an interface usable to produce said authentication response using a client platform, said session specific instance comprising an interface mapping construct in which any given session value of the authentication response maps to a plurality of features on the interface that correspond to possible parameters in the parameter set.

14. The method of claim 1, wherein said using the second server includes using one or more subordinated server.

15. The method of claim 1, wherein said using the first server includes using one or more subordinated server.

16. The method of claim 1, wherein said protected data includes a source of randomness.

17. A client-server authentication system for knowledge-based probabilistic authentication of a client by server side resources, using a client identifier and a client credential having a number of elements, where each element of the credential represents a character that is mapped to a selected grid location parameter, indicated in a challenge, from a set of N×

N grid parameters, comprising;

server-side data processing resources, including one or more processors, memory and a communication interface, the server-side data processing resources including at least first and second servers;

data stored in said memory including a first data set for a client identifier including a representation of the client credential accessible by a first server in server side resources, wherein the representation includes at least one of processed credential elements generated from a one-way function of the at least one credential element and protected data, and wherein the protected data cannot be determined by the first server, and a second data set including at least part of said protected data accessible by a second server in the server side resources;

the data processing resources including executable instructions stored in said memory adapted for execution by the processor, including logic to

receive using the first server via data communications, a client identifier and an authentication response corresponding to the challenge that comprises said plurality of session values and each of the plurality of session values can be specified as, at least, a character that is mapped to a selected grid location parameter, indicated in the challenge, from the set of N×

N grid parameters (N as a greater than zero integer) of fields filled with random digital content different in each of a plurality of sessions sent by the server;

transform in the server side resources, said session values of the authentication response into corresponding sets of intermediate values, each set in said sets of intermediate values having a member for the selected grid location parameter to which the corresponding session value of the response can be mapped, and sending said sets of intermediate values to the second server;

generate a plurality of sets of processed credential element match values using the second server, wherein each set of processed credential element match values of the authentication response is derived based upon said one-way function of said protected data and a corresponding one of said sets of intermediate values, and send said plurality of sets of processed credential element match values to the first server in an order different from an order in which the sets of intermediate values were received using the second server;

determine using the first server, whether each of the sets of processed credential element match values includes one member that matches one of the processed credential elements in the representation of the client credential; and

if all of the sets of processed credential element match values for a given authentication response include one member that matches one of the processed credential elements in the representation of the client credential, then signaling authentication success.

18. The authentication system of claim 17, wherein the one-way function includes a hash.

19. The authentication system of claim 17, said executable instructions including logic to receive from a client platform input data including said client identifier and said processed credential elements using the first server.

20. The authentication system of claim 19, said executable instructions including logic to receive encrypted protected data from a client platform using the first server;

assign an alias for the client identifier using the first server; and

send said encrypted protected data and said alias to the second server.

21. The authentication system of claim 17, wherein said protected data comprises a random value K, and said one-way function uses a combination of the value K and corresponding elements of the credential to produce the processed credential elements.

22. The authentication system of claim 17, wherein said protected data comprises a product KM of a random matrix K and a matrix M having elements that are functions (hashes) of combinations of a first key (mKEY) and said elements of the credential, one-way function uses a combination of a second key (hKEY) and elements of a matrix equal to a product SKM of a random matrix S and said product KM to produce the processed credential elements;

members of said sets of intermediate values being products of the matrix K and possible value matrices, the possible value matrices having elements that are functions of combinations of said first key and the possible parameters (grid locations) in the parameter set to which the corresponding session value of the response can be mapped; and

said, executable instructions including logic to compute for each of said sets of intermediate values, said sets of possible processed credential element match values using the second server, members of said sets of possible processed credential element match values being results of said one-way function using a combination of said second key.

23. The authentication system of claim 22, wherein the product KM and the second key are receive from a client platform, and protected from determination by the first server by encryption, and said executable instructions including logic to decrypt the product KM and the second key (hKEY) using the second server.

24. The authentication system of claim 17, wherein said protected data comprises a set of values KM generated using an exponentiation function M^K of a generator M and an exponent K, where the generator M is a function of a parameter from the parameter set and a first key, and K is a random value, and said processed credential elements are a function of results SKM of an exponentiation function KM^S, where S is a random value, and said second key.

25. The authentication system of claim 24, wherein the values KM and the second key are produced using a client platform, and protected from determination by the first server by encryption, and said executable instructions including logic to decrypt the values KM and the second key using the second server.

26. The authentication system of claim 17, said executable instructions including logic to

receive data from a client platform using the first server including encrypted protected data, a random value K and the client identifier, the encrypted protected data including intermediate data which are results of a one-way function using a combination of the value K and the credential values;

store the value K and the client identifier in memory accessible by the first server, assigning an alias to the client identifier, and send the encrypted protected data and the alias to the second server;

using the second server, decrypt the encrypted protected data to recover said intermediate values, and generate a random value S;

use a one-way function, computing using the second server, said processed credential elements using a combination of the value S and the intermediate values; and

send said processed credential elements from the second server to the first server.

27. The authentication system of claim 17, said executable instructions including logic to

receive data from a client platform using the first server including the encrypted protected data, a random matrix K, a first key and a client identifier, the encrypted protected data including a second key and an intermediate value matrix KM which are results of a product of the random matrix K and a matrix M having elements determined by a function of the first key and a matrix P, the matrix P having elements that consist of said credential values;

store the matrix K, the first key and the client identifier in memory accessible by the first server, assigning an alias to the client identifier, and send the encrypted protected data and the alias to the second server;

decrypt the encrypted protected data using the second server to recover said intermediate value matrix and the second key, store the second key and the alias in memory accessible to the second server, and generate matrix S having random elements;

generate using the second server a matrix using a matrix product S(KM);

use a one-way function using the second server to compute said processed credential elements using a combination of the elements of the matrix product S(KM) and the second key; and

send said processed credential elements to the first server.

28. The authentication system of claim 17, said executable instructions including logic to

receive data from a client platform using the first server including the encrypted protected data, a random value K, a first key and the client identifier to the first server;

the encrypted protected data including a second key and intermediate values which are results of an exponentiation function M^K for each generator M, including a generator M for each part of said credential, the generators being a determined by a function of the first key and the credential values of the elements of said credential;

store the random value K, the first key and the client identifier in memory accessible by the first server, assign an alias to the client identifier, and send the encrypted protected data and the alias to the second server;

decrypt the encrypted protected data to recover said intermediate values KM and the second key, store the second key and the alias in memory accessible to the second server, and generate a random value S;

calculate values SKM using an exponentiation function KM^S for each said intermediate values KM;

compute said processed credential elements using a function (e.g. a hash) of a combination the values SKM and the second key; and

send said processed credential elements to the first server.

29. The authentication system of claim 17, said executable instructions including logic to present a session specific instance of an interface usable to produce said authentication response to a client platform, said session specific instance comprising an interface mapping construct in which any given session value of the authentication response maps to a plurality of features on the interface that correspond to possible parameters in the parameter set.

30. The authentication system of claim 17, wherein the second server includes one or more subordinated server.

31. The authentication system of claim 17, wherein the first server includes one or more subordinated server.

32. The authentication system of claim 17, wherein said protected data includes a source of randomness.

33. A computer program stored on a non-transitory computer readable medium to authenticate a client, comprising instructions when executable by a computer processor to:

store data in a computer memory including a first data set for a client identifier including a representation of client credential accessible by a first server in server side resources, wherein the representation including at least one of processed credential elements generated from a one-way function of the at least one credential element and protected data, and wherein the protected data cannot be determined by the first server, and a second data set including at least part of said protected data accessible by a second server in the server side resources;

send from the first server, to authenticate a user, a set of N×

N grid parameters (N as a greater than zero integer) of fields filled with random digital content different in each of a plurality of sessions and a challenge of a plurality of session values, and in response from the user, receive using the first server via data communications, a client identifier and an authentication response corresponding to the challenge that comprises said plurality of session values and each of the plurality of session values can be specified as, at least, a character that is mapped to a selected grid location parameter, indicated in the challenge, from the set of N×

N grid parameters

transform in the server side resources, said session values of the authentication response into corresponding sets of intermediate values, each set in said sets of intermediate values having a member for the selected grid location parameter to which the corresponding session value of the response can be mapped, and sending said sets of intermediate values to the second server;

generate a plurality of sets of processed credential element match values using the second server, wherein each set of processed credential element match values of the authentication response is derived based upon said one-way function of said protected data and a corresponding one of said sets of intermediate values, and send said plurality of sets of processed credential element match values to the first server in an order different from an order in which the sets of intermediate values were received using the second server;

determine using the first server, whether each of the sets of processed credential element match values includes one member that matches one of the processed credential elements in the representation of the client credential; and

if all of the sets of processed credential element match values for a given authentication response include one member that matches one of the processed credential elements in the representation of the client credential, then signaling authentication success.

34. The computer program of claim 33, wherein the one-way function includes a hash.

35. The computer program of claim 33, said instructions including logic to receive from a client platform input data including said client identifier and said processed credential elements using the first server.

36. The computer program of claim 35, said instructions including logic to receive encrypted protected data from a client platform using the first server;

assign an alias for the client identifier using the first server; and

send said encrypted protected data and said alias to the second server.

37. The computer program of claim 33, wherein said protected data comprises a random value K, and said one-way function uses a combination of the value K and corresponding elements of the credential to produce the processed credential elements.

38. The computer program of claim 33, wherein said protected data comprises a product KM of a random matrix K and a matrix M having elements that are functions (hashes) of combinations of a first key (mKEY) and said elements of the credential, one-way function uses a combination of a second key (hKEY) and elements of a matrix equal to a product SKM of a random matrix S and said product KM to produce the processed credential elements;

members of said sets of intermediate values being products of the matrix K and possible value matrices, the possible value matrices having elements that are functions of combinations of said first key and the possible parameters (grid locations) in the parameter set to which the corresponding session value of the response can be mapped; and

said instructions including logic to compute for each of said sets of intermediate values, said sets of possible processed credential element match values using the second server, members of said sets of possible processed credential element match values being results of said one-way function using a combination of said second key.

39. The computer program of claim 38, wherein the product KM and the second key are receive from a client platform, and protected from determination by the first server by encryption, and said instructions including logic to decrypt the product KM and the second key (hKEY) using the second server.

40. The computer program of claim 33, wherein said protected data comprises a set of values KM generated using an exponentiation function M^K of a generator M and an exponent K, where the generator M is a function of a parameter from the parameter set and a first key, and K is a random value, and said processed credential elements are a function of results SKM of an exponentiation function KM^S, where S is a random value, and said second key.

41. The computer program of claim 40, wherein the values KM and the second key are produced using a client platform, and protected from determination by the first server by encryption, and said instructions including logic to decrypt the values KM and the second key using the second server.

42. The computer program of claim 33, said instructions including logic to

receive data from a client platform using the first server including encrypted protected data, a random value K and the client identifier, the encrypted protected data including intermediate data which are results of a one-way function using a combination of the value K and the credential values;

store the value K and the client identifier in memory accessible by the first server, assigning an alias to the client identifier, and send the encrypted protected data and the alias to the second server;

using the second server, decrypt the encrypted protected data to recover said intermediate values, and generate a random value S;

use a one-way function, computing using the second server, said processed credential elements using a combination of the value S and the intermediate values; and

send said processed credential elements from the second server to the first server.

43. The computer program of claim 33, said instructions including logic to

receive data from a client platform using the first server including the encrypted protected data, a random matrix K, a first key and a client identifier, the encrypted protected data including a second key and an intermediate value matrix KM which are results of a product of the random matrix K and a matrix M having elements determined by a function of the first key and a matrix P, the matrix P having elements that consist of said credential values;

store the matrix K, the first key and the client identifier in memory accessible by the first server;

assigning an alias to the client identifier, and send the encrypted protected data and the alias to the second server;

decrypt the encrypted protected data using the second server to recover said intermediate value matrix and the second key, store the second key and the alias in memory accessible to the second server, and generate matrix S having random elements;

generate using the second server a matrix using a matrix product S(KM);

use a one-way function using the second server to compute said processed credential elements using a combination of the elements of the matrix product S(KM) and the second key; and

send said processed credential elements to the first server.

44. The computer program of claim 33, said instructions including logic to

receive data from a client platform using the first server including the encrypted protected data, a random value K, a first key and the client identifier to the first server;

the encrypted protected data including a second key and intermediate values which are results of an exponentiation function M^K for each generator M, including a generator M for each part of said credential, the generators being a determined by a function of the first key and the credential values of the elements of said credential;

store the random value K, the first key and the client identifier in memory accessible by the first server, assign au alias to the client identifier, and send the encrypted protected data and the alias to the second server;

decrypt the encrypted protected data to recover said intermediate values KIM and the second key, store the second key and the alias in memory accessible to the second server, and generate a random value S;

calculate values SKM using an exponentiation function KM^S for each said intermediate values KM;

compute said processed credential elements using a function (e.g. a hash) of a combination the values SKM and the second key; and

send said processed credential elements to the first server.

45. The computer program of claim 33, said instructions including logic to present a session specific instance of an interface usable to produce said authentication response to a client platform, said session specific instance comprising an interface mapping construct in which any given session value of the authentication response maps to a plurality of features on the interface that correspond to possible parameters in the parameter set.

46. The computer program of claim 33, wherein the second server includes one or more subordinated server.

47. The computer program of claim 33, wherein the first server includes one or more subordinated server.

48. The computer program of claim 33, wherein said protected data includes a source of randomness.

49. A server in client-server authentication system for knowledge-based probabilistic authentication of a client by server side resources, using a client identifier and a credential having a number of elements, where each element of the client credential represents a character that is mapped to a selected grid location parameter, indicated in a challenge, from a set of N×

N grid, comprising;

data processing resources, including one or more processors, memory and a communication interface;

data stored in said memory including a first data set for a client identifier including a representation of the client credential accessible by a first server in server side resources, wherein the representation includes at least one of processed credential elements generated from a one-way function of the at least one credential element and protected data, and wherein the protected data cannot be determined by the first server, and a second data set including at least part of said protected data accessible by a second server in the server side resources;

the data processing resources including executable instructions stored in said memory adapted for execution by the processor, including logic to

receive using the first server via data communications, a client identifier and an authentication response corresponding to the challenge that comprises said plurality of session values and each of the plurality of session values can be specified as, at least, a character that is mapped to a selected grid location parameter, indicated in the challenge, from the set of N×

N grid parameters (N as a greater than zero integer) of fields filled with random digital content different in each of a plurality of sessions sent by the server;

transform in the server side resources, said session values of the authentication response into corresponding sets of intermediate values, each set in said sets of intermediate values having a member for the selected grid location parameter to which the corresponding session value of the response can be mapped, and sending said sets of intermediate values to a second server;

receive a plurality of sets of processed credential element match values from the second server, wherein each set of processed credential element match values of the authentication response is derived based upon said one-way function of said protected data and a corresponding one of said sets of intermediate values, said plurality of sets of processed credential element match values to the first server in an order different from an order in which the sets of intermediate values were sent to the second server;

determine using the first server, whether each of the sets of processed credential element match values includes one member that matches one of the processed credential elements in the representation of the client credential; and

if all of the sets of processed credential element match values for a given authentication response include one member that matches one of the processed credential elements in the representation of the client credential, then signaling authentication success.