Forward secure pseudorandom number generation resilient to forward clock attacks

1. A method for generating a forward secure pseudorandom number, comprising:

obtaining a first state s i corresponding to a current leaf node ν i in a hierarchical tree, wherein said first state s i comprises a sequence of one or more seeds in said hierarchical tree, wherein said first state s i is stored in a memory of a hardware device as at least one data structure, wherein said at least one data structure comprises each of said one or more seeds of said first state s i and corresponding position information identifying a position of said corresponding seed in said hierarchical tree, wherein said current leaf ν i produces a first pseudorandom number r i−1 ;

updating said first state s i to a second state s i+t corresponding to a second leaf node ν i+t by processing said one or more seeds in said at least one data structure in a predefined order based on said corresponding position information to traverse a portion of the hierarchical tree to the second state s i+t ; and

computing a second pseudorandom number r i+t−1 corresponding to said second leaf node ν i+t wherein said second pseudorandom number r i+t−1 is based on a forward clock reset index that identifies an instance of said hierarchical tree, wherein said instance of said hierarchical tree is incremented when one or more criteria indicating a forward clock attack are detected.

2. The method of claim 1 , wherein said forward clock reset index is encoded in a forward secure manner in said hierarchical tree.

3. The method of claim 2 , wherein said forward clock reset index is encoded as a layer in said hierarchical tree.

4. The method of claim 1 , wherein said first state s i comprises said forward clock reset index and one or more of a current device time and a last used device time during a generation of said second pseudorandom number.

5. The method of claim 4 , further comprising the step of updating a last used device time to said current device time during a generation of said second pseudorandom number.

6. The method of claim 1 , wherein said criteria indicating a forward clock attack are detected comprise a current device time being less than a difference between a last used device time during a generation of said second pseudorandom number and a predefined threshold.

7. The method of claim 1 , further comprising the step of updating said forward clock reset index if said forward clock attack is detected.

8. The method of claim 1 , wherein a server identifies a matching passcode in a hierarchical tree identified by said forward clock reset index stored by said server in a range between a current server time less a threshold and said current server time plus said threshold.

9. The method of claim 8 , further comprising the step of updating a server time corresponding to a correct passcode to be equal to a time of said identified match.

10. The method of claim 8 , wherein said server conditionally accepts an access attempt and detects a small forward clock reset (FCR) if a time of said access attempt is less than or equal to a last server time corresponding to a correct passcode.

11. The method of claim 8 , wherein said server conditionally accepts an access attempt if a time of said access attempt is greater than a last server time corresponding to a correct passcode.

12. The method of claim 1 , wherein a server does not identify a matching passcode in a hierarchical tree identified by said forward clock reset index stored by said server in a range between a current server time less a threshold and said current server time plus said threshold.

13. The method of claim 1 , further comprising the step of said server searching a hierarchical tree identified by one or more increments to said forward clock reset index.

14. The method of claim 13 , wherein said server rejects an access attempt if said server does not identify a matching passcode in one of said hierarchical trees identified by said one or more increments to said forward clock reset index.

15. The method of claim 13 , wherein said server conditionally accepts an access attempt and detects a large forward clock reset (FCR) if said server identifies a matching passcode in one of said hierarchical trees identified by said one or more increments to said forward clock reset index.

16. The method of claim 15 , further comprising the step of updating a server time corresponding to a correct passcode to be equal to a time of said identified match.

17. The method of claim 15 , further comprising the step of incrementing said forward clock reset index by one or more increments.

18. The method of claim 1 , wherein one or more of said forward secure pseudorandom numbers are generated using a given one of a plurality of hierarchical trees and are processed by a corresponding one of a plurality of authentication servers.

19. The method of claim 1 , wherein said hierarchical tree comprises at least one chain comprised of a plurality of nodes on a given level of said hierarchical tree.

20. A non-transitory machine-readable recordable storage medium encoded with computer program instructions for generating a forward secure pseudorandom number, when executed by one or more processors, cause a computer to perform the following steps:

obtaining a first state s i corresponding to a current leaf node ν i in a hierarchical tree wherein said first state s i comprises a sequence of one or more seeds in said hierarchical tree, wherein said first state s i is stored in a memory of a hardware device as at least one data structure, wherein said at least one data structure comprises each of said one or more seeds of said first state s i and corresponding position information identifying a position of said corresponding seed in said hierarchical tree, wherein said current leaf ν i produces a first pseudorandom number r i−1 ;

updating said first state s i to a second state s i+t corresponding to a second leaf node ν i+t by processing said one or more seeds in said at least one data structure in a predefined order based on said corresponding position information to traverse a portion of the hierarchical tree to the second state s i+t ; and

computing a second pseudorandom number r i+t−1 corresponding to said second leaf node ν i+t , wherein said second pseudorandom number r i+t−1 is based on a forward clock reset index that identifies an instance of said hierarchical tree, wherein said instance of said hierarchical tree is incremented when one or more criteria indicating a forward clock attack are detected.

21. An apparatus for generating a forward secure pseudorandom number, the apparatus comprising:

a memory; and

at least one hardware device, coupled to the memory, operative to implement the following steps:

obtain a first state s i corresponding to a current leaf node ν i in a hierarchical tree, wherein said first state s i comprises a sequence of one or more seeds in said hierarchical tree, wherein said first state s i is stored in a memory of a hardware device as at least one data structure, wherein said at least one data structure comprises each of said one or more seeds of said first state s i and corresponding position information identifying a position of said corresponding seed in said hierarchical tree, wherein said current leaf ν i produces a first pseudorandom number r i−1 ;

update said first state s i to a second state s i+1 corresponding to a second leaf node ν i+t by processing said one or more seeds in said at least one data structure in a predefined order based on said corresponding position information to traverse a portion of the hierarchical tree to the second state s i+t ; and

compute a second pseudorandom number r i+t−1 corresponding to said second leaf node ν i+t , wherein said second pseudorandom number r i+t−1 is based on a forward clock reset index that identifies an instance of said hierarchical tree, wherein said instance of said hierarchical tree is incremented when one or more criteria indicating a forward clock attack are detected.

22. The apparatus of claim 21 , wherein said forward clock reset index is encoded in a forward secure manner in said hierarchical tree.

23. The apparatus of claim 22 , wherein said forward clock reset index is encoded as a layer in said hierarchical tree.

24. The apparatus of claim 21 , wherein said first state s i comprises said forward clock reset index and one or more of a current device time and a last used device time during a generation of said second pseudorandom number.

25. The apparatus of claim 24 , wherein said at least one hardware device is further configured to synchronize said current device time and a last used device time during a generation of said second pseudorandom number.

26. The apparatus of claim 21 , wherein said criteria indicating a forward clock attack are detected comprise a current device time being less than a difference between a last used device time during a generation of said second pseudorandom number and a predefined threshold.

27. The apparatus of claim 21 , wherein a server identifies a matching passcode in a hierarchical tree identified by said forward clock reset index stored by said server in a range between a current server time less a threshold and said current server time plus said threshold.

28. The apparatus of claim 21 , wherein a server does not identify a matching passcode in a hierarchical tree identified by said forward clock reset index stored by said server in a range between a current server time less a threshold and said current server time plus said threshold.

29. The apparatus of claim 28 , further comprising the step of said server searching a hierarchical tree identified by one or more increments to said forward clock reset index.

30. The apparatus of claim 29 , wherein said server rejects an access attempt if said server does not identify a matching passcode in one of said hierarchical trees identified by said one or more increments to said forward clock reset index.

31. The apparatus of claim 21 , wherein said hierarchical tree comprises at least one chain comprised of a plurality of nodes on a given level of said hierarchical tree.