Authentication using random challenges

• US 5,872,917 A
• Filed: 10/08/1997
• Issued: 02/16/1999
• Est. Priority Date: 06/07/1995
• Status: Expired due to Term

• Current Assignee: Martin Hellman
• Original Assignee: America Online Inc. (Warner Bros. Discovery, Inc.)
• Inventors: Hellman, Martin E.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Elisca, Pierre E.
• Application Number:
  US08/947,053
• Time in Patent Office: 496 Days
• Field of Search: 395/186, 395/187.01, 395/188.01, 395/200.59, 705/18, 705/44, 707/9, 711/163, 711/164, 380/1-59
• US Class Current: 726/6
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 2211/007 Encryption, En-/decode, En-/decipher, En-/decypher, Scramble, (De-)compress
• CPC Class Codes: G06F 2221/2103 Challenge-response

Abstract

A method is disclosed for authenticating one or both of two parties, for example, a user and a host computer. The first party and second party each know the same password. The first party sends a challenge to the second party. The second party generates and sends to the first party a response based on a first function of the password, the first party'"'"'s challenge, and an extra value unknown to the first party. The first party, which knows only the length of the extra value, then attempts to match the response by using the same function, password, and challenge by cycling through the possible values for the extra value of known format. A method of bi-directional authentication may be achieved by having the first party return to the second party a response using a different function of the password, a preferably different challenge, and the extra value. The second party already knows the input values, including the extra value, and therefore, does not incur the costs associated with learning the extra value. The identity of the first party is confirmed by matching the transmitted response with a value generated locally.

Claims

1. A method of authentication, said method comprising the steps of:

(i) generating a password, said password known to a first party and a second party;

(ii) generating at least one challenge, said at least one challenge being generated by said first party, said second party, or a third party;

(iii) generating a first value, said first value within a range of values determined prior to generating said first value and said first value being generated by said second party;

(iv) generating a first response using said password, at least one of said challenges, and said first value, said first response being generated by said second party;

(v) transmitting said first response from said second party to said first party;

(vi) generating a second value, said second value within said range of values determined prior to generating said first value and said second value being generated by said first party;

(vii) generating a second response using said password, at least one of said challenges, and said second value, said second response being generated by said first party; and

(viii) comparing said first response and said second response, said comparison performed by said first party.

2. The method according to claim 1, further comprising the step of repeating steps vi, vii, and viii until said first response and said second response match or until all of said second values within said range of values determined prior to generating said first value have been generated.

3. The method of claim 1, further comprising the steps of:

said first party generating a third response using said password, at least one of said challenges, and said second value;

transmitting said third response from said first party to said second party;

generating a fourth response using said password, at least one of said challenges, and said first value, said fourth response being generated by said second party;

comparing said third response and said fourth response, said comparison being done by said second party.

4. The method of claim 1, further comprising the step of generating said first response using said password, at least one of said challenges, said first value, and at least one additional challenge from said second party and generating said second response using said password, at least one of said challenges, said second value, and at least one additional challenge from said second party.

5. The method of claim 1, wherein the step of generating said first value comprises the step of randomly generating said first value.

6. The method of claim 1 wherein said step of comparing said first response and said second response guarantees authentication of said second party by said first party.

7. The method of claim 1 wherein the step of generating second values within said range of values comprises generating said second values in ascending order beginning with the minimum value in said range of values.

8. The method of claim 1 wherein the step of generating second values within said range of values determined prior to generating said first value comprises generating said second values in descending order beginning with the maximum value in said range of values.

9. A system for authenticating comprising:

a first party;

a second party;

means for generating a password, said password known by said first party and by said second party;

means for generating at least one challenge, said at least one challenge being generated by said first party, said second party, or a third party;

means for said second party to generate a first value within a predetermined range of values;

means for said second party to generate a first response using said password, at least one of said challenges, and said first value;

means for transmitting said first response to said first party; and

means for said first party to generate a plurality of second values within said predetermined range of values and a plurality of second responses using said password, at least one of said challenges, and one of said plurality of second values until said first response matches one of said plurality of second responses or until all of said second values within said predetermined range of values have been generated.

10. The system of claim 9, further comprising a means for generating said first response using said password, at least one of said challenges, said first value, and at least one additional challenge from said second party and a means for generating said plurality of second responses using said password, at least one of said challenges, said second values within said predetermined range of values, and at least one additional challenge from said second party.

11. The system of claim 9, further comprising:

means for said first party to generate a third response using said password, at least one of said challenges, and said second value;

means for said first party to transmit said third response to said second party;

means for said second party to generate a fourth response using said password, at least one of said challenges, and said first value;

means for said second party to compare said third response and said fourth response.

12. The system of claim 9, wherein said second value is randomly generated.

13. The system of claim 9 wherein said second party is authenticated if said first response and said second response match.

14. The system of claim 9 wherein said plurality of second values is generated in ascending order beginning with the minimum value in said predetermined range of values.

15. The system of claim 9 wherein said plurality of second values is generated in descending order beginning with the maximum value in said predetermined range of values.

16. A method of authentication, said method comprising the steps of:

providing a first party with a password;

providing a second party with said password;

establishing by communication between said first party and said second party, that said second party knows said password, said communication involving a value, said value known to said first party, said value within a determinate range of values known to said second party, and said value tested by said second party; and

maintaining said communication free of revealing said password.

17. A system for authentication comprising:

a first party

a second party;

a first response, said first response being generated by said second party from a first random value within a specified range of values known to said first party and said first response being transmitted to said first party;

a second response, said second response being generated by said first party at a cost substantially higher than the cost of generating said first response.

18. The system of claim 17 wherein said first party generates said second response in accordance with a plurality of second values within said specified range of values known to said first party.

19. The system of claim 17 wherein said second party is authenticated if said first response and said second response match.