Method for improved hash chaining authentication

1 . A method for authenticating messages implemented by a sending device, the method comprising:

generating, using a hash function, an N generation token of a first seed and an N−1 generation token of the first seed, wherein N is a firt integer value greater than one;

sending a first message that includes the N generation token of a first seed, wherein N is a first integer value greater than one; and

sending a second message that includes the N−1 generation token of the first seed and an M generation token of a second seed, wherein M is a second integer value greater than one, and wherein the N−1 generation token is a different generation than the M generation token.

2 . The method of claim 1 , further comprising:

prior to sending the first message, generating the N−1 generation token and the N generation token of the first seed by performing hash chaining using the first seed; and

storing the N−1 generation token.

3 . The method of claim 1 , further comprising:

prior to sending the second message, generating an M−1 generation token and the M generation token of the second seed by performing hash chaining using the second seed; and

storing the M−1 generation token.

4 . The method of claim 3 , wherein the first integer value of N is equal to the second integer value of M.

5 . The method of claim 4 , further comprising sending, when N is greater than two and M is greater than two, a third message that includes an N−2 generation token of the first seed and the M−1 generation token of a second seed.

6 . The method of claim 5 , further comprising:

prior to sending the third message, generating an N−3 generation token and the N−2 generation token of the first seed by performing hash chaining using the first seed; and

storing the N−3 generation token.

7 . The method of claim 1 , further comprising:

generating, when N is two and Mis two, an N−1 generation token and an N generation token of a third seed by performing hash chaining using the third seed;

sending a third message that includes an M−1 generation token of the second seed and the N generation token of the third seed; and

storing the N−1 generation token of the third seed.

8 . The method of claim 1 , further comprising overwriting or deleting any previously stored generation token that has been included in a sent message.

9 . A method for authenticating messages implemented by a receiving device, the method comprising:

receiving, from a sending device, a first message that includes an N generation token of a first seed, wherein N is a first integer value greater than one;

storing the N generation token of the first seed;

receiving, from the sending device, a second message that includes an N−1 generation token of the first seed and an M generation token of a second seed, wherein M is a second integer value greater than one, and wherein the N−1 generation token is a different generation than the M generation token;

determining whether a hash value of a hash of the N−1 generation token is equal to the N generation token of the first seed received in the first message; and

authenticating that the second message came from the sending device when the hash value of the hash of the N−1 generation token is equal to the N generation token received in the first message.

10 . The method of claim 9 , further comprising discarding the second message when the hash value of the hash of the N−1 generation token is not equal to the N generation token received in the first message.

11 . The method of claim 9 , further comprising storing the M generation token of the second seed when the hash value of the hash of the N−1 generation token is equal to the N generation token received in the first message.

12 . The method of claim 9 , further comprising deleting or overwriting the N generation token of the first seed from memory when the hash value of the hash of the N−1 generation token is equal to the N generation token received in the first message.

13 . The method of claim 9 , wherein the first integer value of N is equal to the second integer value of M.

14 . The method of claim 9 , further comprising:

receiving, when N is greater than two and M is greater than two, a third message that includes an N−2 generation token of the first seed and an M−1 generation token of the second seed;

determining whether the hash value of the hash of the M−1 generation token is equal to the M generation token; and

authenticating that the third message came from the sending device when the hash value of the hash of the M−1 generation token is equal to the M generation token.

15 . The method of claim 14 , further comprising storing the N−2 generation token of the first seed for authenticating a fourth message from the sending device.

16 . An apparatus comprising:

a memory configured to store instructions; and

a processor coupled to the memory and configured to execute the instructions, which when executed cause the apparatus to:

generate, using a hash function, an N generation token of a first seed and an N−1 generation token of the first seen, wherein N is a first integer value greater than one;

send a first message that includes the N generation token of a first seed, wherein N is a first integer value greater than one; and

send a second message that includes the N−1 generation token of the first seed and an M generation token of a second seed, wherein M is a second integer value greater than one, and wherein the N−1 generation token is a different generation than the M generation token.

17 . The apparatus of claim 16 , wherein the instructions when executed by the processor, further causes the apparatus to:

generate, prior to sending the first message, the N−1 generation token and the N generation token of the first seed by performing hash chaining using the first seed; and

store the N−1 generation token.

18 . The apparatus of claim 16 , wherein the instructions when executed by the processor, further causes the apparatus to:

generate, prior to sending the second message, an M−1 generation token and the M generation token of the second seed by performing hash chaining using the second seed; and

store the M−1 generation token.

19 . The apparatus of claim 18 , wherein the first integer value of N is equal to the second integer value of M.

20 . The apparatus of claim 19 , wherein the instructions when executed by the processor, further causes the apparatus to send, when N is greater than two and M is greater than two, a third message that includes an N−2 generation token of the first seed and the M−1 generation token of a second seed.

21 . The apparatus of claim 20 , wherein the instructions when executed by the processor, further causes the apparatus to generate, prior to sending the third message, an N−3 generation token and the N−2 generation token of the first seed by performing hash chaining using the first seed; and store the N−3 generation token.

22 . The apparatus of claim 16 , wherein the instructions when executed by the processor, further causes the apparatus to:

generate, when N is two and M is two, an N−1 generation token and the N generation token of a third seed by performing hash chaining using the third seed;

send a third message that includes an M−2 generation token of the second seed and the N generation token of the third seed; and

store the N−1 generation token of the third seed.

23 . The apparatus of claim 16 , wherein the instructions when executed by the processor, further causes the apparatus to overwrite or delete any previously stored generation token that has been included in a sent message.

24 . A computer program product comprising computer-executable instructions stored on a non-transitory computer-readable storage medium, the computer-executable instructions when executed by one or more processors of an apparatus, cause the apparatus to:

receive, from a sending device, a first message that includes an N generation token of a first seed, wherein N is a first integer value greater than one;

store the N generation token of the first seed;

receive a second message that includes an N−1 generation token of the first seed and an M generation token of a second seed, wherein M is a second integer value greater than one, and wherein the N−1 generation token is a different generation than the M generation token;

determine whether a hash value of a hash of the N−1 generation token is equal to the N generation token of the first seed received in the first message; and

authenticate that the second message came from the sending device when the hash value of the hash of the N−1 generation token is equal to the N generation token received in the first message.

25 . The computer program product of claim 24 , wherein the instructions when executed by the one or more processors, further causes the apparatus to discard the second message when the hash value of the hash of the N−1 generation token is not equal to the N generation token received in the first message.

26 . The computer program product of claim 24 , wherein the instructions when executed by the one or more processors, further causes the apparatus to store the M generation token of the second seed when the hash value of the hash of the N−1 generation token is equal to the N generation token received in the first message.

27 . The computer program product of claim 24 , wherein the instructions when executed by the one or more processors, further causes the apparatus to delete or overwrite the N generation token of the first seed from memory when the hash value of the hash of the N−1 generation token is equal to the N generation token received in the first message.

28 . The computer program product of claim 24 , wherein the first integer value of N is equal to the second integer value of M.

29 . The computer program product of claim 24 , wherein the instructions when executed by the one or more processors, further causes the apparatus to:

receive, when N is greater than two and M is greater than two, a third message that includes an N−2 generation token of the first seed and an M−1 generation token of the second seed;

determine whether the hash value of the hash of the M−1 generation token is equal to the M generation token; and

authenticate that the third message came from the sending device when the hash value of the hash of the M−1 generation token is equal to the M generation token.

30 . The computer program product of claim 29 , wherein the instructions when executed by the one or more processors, further causes the apparatus to store the N−2 generation token of the first seed for authenticating a fourth message from the sending device.