Method and apparatus for two-way authentication without nonces

• US 20080077795A1
• Filed: 09/25/2007
• Published: 03/27/2008
• Est. Priority Date: 09/25/2006
• Status: Abandoned Application

• Current Assignee: David MacMillan
• Original Assignee: David MacMillan
• Inventors: MacMillan, David
• Application Number:
  US11/903,812
• Publication Number:
  US 20080077795A1
• Time in Patent Office: Days
• US Class Current: 713/169
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• 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/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

A method and logical apparatus for accomplishing the two-way authentication of two parties without the use of nonce values. In the prior art, authentication may be accomplished both through the use of stored and of generated password lists. Also from the prior art these methods may be extended by the use of “nonce” values, a subset of a larger category of “anti-replay values” (ARVs). ARVs are values which satisfy the constraints that they must be used only once, that they must be unguessable by an attacker, and that they must reveal nothing about either the entity generating them or the entity receiving them. These methods are extended here by using not nonces but “Mutual Anti-Replay Values” (MARVs), which are values which satisfy the requirements for ARVs and which, further, are known to both the authenticator and authenticatee. These MARVs may be stored or generated lists independent of the password lists maintained by the authenticator and authenticatee, or they may be derived in special ways from these password lists. The use of MARVs in this invention, rather than the nonces of the prior art, provides tamper-evidence at the authenticatee while a replay attack is underway and provides security against serial impersonation attacks, in addition to protection against eavesdropping, protection against replay attacks, and tamper-evidence at the authenticator.

Claims

1. A method and apparatus whereby two entities may authenticate each to the other comprising

(a) a list of arbitrary length of key data serving as the keys for one of the entities, maintained in the storage of that entity and also maintained in the storage of the other entity,

(b) optionally, a list of arbitrary length of data serving as values to be known as mutual anti-replay values, maintained in the storage of that entity and also maintained in the storage of the other entity,

(c) a list of arbitrary length of key data serving as the keys for the other of the entities, maintained in the storage of that entity and also maintained in the storage of the first entity,

(d) optionally, a list of arbitrary length of data serving as values to be known as mutual anti-replay values, maintained in the storage of the other of the entities and also maintained in the storage of the first entity,

(e) indexes into these key lists maintained by each entity,

(f) optionally, if independent lists of mutual anti-replay values are maintained, indexes into these lists of mutual anti-replay values,

(g) optionally, if independent lists of mutual anti-replay values are not maintained, a pair of one-way computational functions which may be applied to the contents of the key lists each of which functions is computationally feasible but the inverse of which is computationally infeasible for an attacker, such that each function of the pair may be identical to or different from the other, to be used to generate values to be known as mutual anti-replay values in lieu of separate lists of such values,

(h) another pair of one-way computational functions which may be applied to the contents of these lists each of which is computationally feasible but the inverse of which is computationally infeasible for an attacker, such that each function of the pair may be identical to or different from the other, to be used to generate values to be known as return values,

(i) a compositing computational function which may be used to combine key and other values in such a way that the inverse of this combination may easily be computed,

such that for one entity, in the role of authenticatee, to be authenticated to the other entity, in the role of authenticator,

(a) if a separate list of mutual anti-replay values is maintained, the authenticator selects the current value from the list of mutual anti-replay values for the authenticatee, or

(b) if a separate list of mutual anti-replay values is not maintained, the authenticator applies one of the mutual anti-replay value generating one-way functions to the current key in the authenticatee'"'"'s list of keys, generating a value known as the mutual anti-replay value,

(c) the authenticator, at this or any point up to the receipt of authentication data back from the authenticatee, computes the application of the composition function to the mutual anti-replay value so generated and the current key in the authenticatee'"'"'s list, and then computes the application of one of the return-value generating functions to this composition, using the return-value generating function to be used by the authenticatee in generating a return value in (i) below,

(d) the authenticator transmits the mutual anti-replay value to the authenticatee,

(e) if separate lists of mutual anti-replay values is maintained, the authenticatee selects the current value from its list, or

(f) if a separate list of mutual anti-replay values is not maintained, the authenticatee applies the mutual anti-replay value one-way function to the current key in its list of keys, generating a value which would in the absence of attacks or operational difficulties be identical to the anti-replay value it has received from the authenticator,

(g) the authenticatee compares the mutual anti-replay value as received at (d) with either the value so selected at (e) or the value so computed in (f) and, if they are identical, continues, but, if they differ, aborts the authentication protocol and optionally signals an error condition or warning alarm,

(h) if the authentication protocol is to continue, then the authenticatee computes the combination of this anti-replay value so received with the current key in its list of keys, using the same composition function used in (c) above by the authenticator,

(i) the authenticatee computes the application of one the same return-value generating one-way function used by the authenticator in (c) above by the authenticator to this composite value,

(j) the authenticatee transmits this result, called the return value, to the authenticator,

(k) the authenticator compares this value with the presumably identical value that it has previously computed,

(l) and if these two values match, then the authenticator concludes that the authentication of the authenticatee has occurred,

(m) this protocol is executed again, either simultaneously, interleaved, or serially, with the roles of authenticator and authenticatee reversed between the entities, to accomplish this second direction of authentication,

(n) the authenticator and authenticatee increment their indexes into the key lists at such points in the protocol after which these indexes are no longer required for the current exchange in either direction of authentication.

2. The method and apparatus of claim 1 where the authenticatee does not use an ordinary one-way function to generate the return value but instead uses public key cryptographic methods to generate the return value, such that

(a) the authenticator initially generates and maintains a public and a private key pair using public key cryptographic technology

(b) the authenticator makes known its public key to the authenticatee,

(c) the authenticatee encrypts its return value to the authenticator using this public key encryption technology and the authenticator'"'"'s public key,

(d) the authenticator, on receipt of this return value, decrypts it using this public key encryption technology and its private key, and

(e) the authenticator decomposes the value so decrypted into its mutual anti-replay value and key components, and

(f) the authenticator, in addition to checking for the validity of the key either explicitly here or as described above, further checks the mutual anti-replay value as returned, and

(g) if the mutual anti-replay value is not identical to the value sent to B, the authenticator refuses to continue the authentication process and may signal an error or warning.

3. The method and apparatus of claim 1 wherein the authentication process is terminated at or ignored beyond the first authentication of one entity to the other, provided that

(a) the authenticator and authenticatee increment their indexes into the key lists at such points in the protocol after which these indexes are no longer required for the current exchange.

4. The method and apparatus of claim 2 wherein the authentication process is terminated at or ignored beyond the first authentication of one entity to the other, provide that

(a) the authenticator and authenticatee increment their indexes into the key lists at such points in the protocol after which these indexes are no longer required for the current exchange.

7. The method and apparatus of claims 1, 2, and 5 wherein the authentication process proceeds in one direction between two entities as described in claims 1 or 2 and in the opposite direction between the same two entities as described in claim 5.

5. A method and apparatus whereby two entities may authenticate each to the other, comprising

(a) an initial key value for one of the entities, stored in that entity only,

(b) optionally, an initial mutual anti-replay list seed value, stored in that entity only,

(c) the current-plus-one key value for one of the entities, stored in the other entity only,

(d) optionally, the current-plus-one mutual anti-replay list value, stored in the other entity only,

(e) an initial key value for the other of the entities, stored in that entity only,

(f) optionally, an initial mutual anti-reply list seed value for the other of the entities, stored in that entity only,

(g) the current-plus-one key value for the other of the entities, stored in the first entity only,

(h) optionally, the current-plus-one mutual anti-replay list value for the other of the entities, stored in that entity only,

(i) a count or index for each entity representing the serial number of the current authentication exchange, stored respectively in each entity,

(j) in each entity, a one-way computational function which may be applied the initial key value from (a) and (e) above, and to subsequent recursive applications of this function, which is computationally feasible but the inverse of which is computationally infeasible, which function may be identical in both entities or different in each, used for the generation of key lists,

(k) optionally, in each entity, a one-way computational function which may be applied to the seed mutual anti-replay list value from (b) and (f) above, and to subsequent recursive applications of this function, which is computationally feasible but the inverse of which is computationally infeasible, which function may be identical in both entities or different in each, used for the generation of lists, if maintained separately, for the production of mutual anti-replay values,

(l) in each entity, a one-way computational function, different from the function identified in (j), if separate anti-replay value lists are not maintained, or (k), if separate anti-replay value lists are maintained, which may be applied to the values in (j) or (k) which is computationally feasible but the inverse of which is computationally infeasible, used for the generation of mutual anti-replay values either from generated key lists or, as appropriate, generated mutual anti-replay value lists,

(m) a public and private key pair for one of the entities, using any appropriate public-key cryptographic technology, the private key of which is stored in the entity and the public key of which is known at least to the other entity,

(n) a public and private key pair for the other of the entities, using any appropriate public-key cryptographic technology, the private key of which is stored in the entity and the public key of which is known at least to the other entity,

(o) in each entity, implementations of said appropriate public-key cryptographic technology,

(p) in each entity, a compositing computational function which may be used to combine key and other values in such a way that the inverse of this combination may easily be computed,

such that for one entity, in the role of authenticatee, to be authenticated to the other entity, in the role of authenticator,

(a) if a separate generated list for mutual anti-replay values is maintained, the authenticator calculates a mutual anti-replay value by applying the second one-way function of (l), above, to the current list value for the authenticatee, or

(b) if a separate generated list of mutual anti-replay values is not maintained, the authenticator calculates an anti-replay value by applying the second one-way function of (l), above, to the current key value for the authenticatee,

(c) the authenticator transmits this mutual anti-replay value to the authenticatee,

(d) the authenticatee generates its current key value by repeated application of the one-way function of (j), above, to the initial key value, to the results of the application of that function to the initial key value, to the result of this in turn, and so on until the current index value of the authentication exchange has been reached,

(e) if a separate generated list for mutual anti-replay values is maintained, the authenticatee generates the current value in that list by repeated application of the one-way function of (k), above, to the initial seed value for this list, to the result of this in turn, and so on until the current index value of the mutual anti-replay value list has been reached,

(f) if a separate generated list for mutual anti-replay values is maintained, the authenticatee calculates the anti-replay value that it expects to receive by applying the one-way function of (l) to the current value in its mutual anti-replay value list as computed in (e), or

(g) if a separate generated list for mutual anti-replay value sis not maintained, the authenticatee calculates the anti-replay value that it expects to see by applying the one-way function of (l) to its current key value as computed in (d),

(h) if the anti-replay value as received does not match the expected anti-replay value as computed, then the authenticatee aborts the authentication process and optionally signals an error condition or warning alarm,

(i) if the anti-replay value as received does match the expected anti-replay value, then the authenticatee continues the authentication protocol,

(j) if the authentication protocol is to continue, then the authenticatee applies the composing computational function to compute the combination of this anti-replay value so received or expected with the current key as computed,

(k) the authenticatee then encrypts this combined value using a public key cryptographic technology and the public key of the authenticator,

(l) the authenticatee transmits this encrypted value to the authenticator,

(m) the authenticator decrypts this received encrypted value using a public key cryptographic technology and its own private key, extracting from this process the mutual anti-replay value and the current key for the authenticatee,

(n) the authenticator examines the mutual anti-replay value so extracted and compares it with the mutual anti-replay value sent, and if this value does not match the mutual anti-replay value as sent, then the authenticator aborts the authentication process and optionally signals an error condition or warning alarm,

(o) the authenticator applies the key generation one-way function of (j) to this current key value to obtain the current-plus-one key value in the authenticatee'"'"'s list of keys,

(p) the authenticator compares this current-plus-one key value so computed from information received from the authenticatee against its stored version of the current-plus-one key value,

(q) if the key values so compared match, then the authentication succeeds

(r) if the key values so compared do not match, then the authentication fails,

(s) the authenticator may then discard the current-plus-one key value,

(t) if a separate generated mutual anti-replay value list is maintained, the authenticator may then discard the current-plus-one value of this list,

(u) the authenticator takes the current key value as received from the authenticatee to be the current-plus-one key value for the next authentication of the authenticatee,

(v) if a separate generated mutual anti-replay value list is maintained, the authenticator takes the current mutual anti-replay value as received from the authenticatee to be the current-plus-one mutual anti-replay value for the next authentication of the authenticatee,

(w) this protocol is executed again, either simultaneously, interleaved, or serially, with the roles of authenticator and authenticatee reversed between the entities, to accomplish the second direction of authentication.

6. The method and apparatus of claim 5 wherein the authentication process is terminated at or ignored beyond the first authentication of one entity to the other, provided that

(a) the authenticator and authenticatee increment their indexes into the key lists at such points in the protocol after which these indexes are no longer required for the current exchange.