FAST COMPUTATION OF ONE-WAY HASH SEQUENCES

• US 20090279692A1
• Filed: 05/12/2008
• Published: 11/12/2009
• Est. Priority Date: 05/12/2008
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Perlman, Radia J.
• Granted Patent: US 8,538,014 B2
• Time in Patent Office: Days
• US Class Current: 380/28
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

Some embodiments of the present invention provide a system that computes a target secret S_t in a sequence of secrets S₀ . . . S_n. During operation, the system obtains k hash functions h₁, . . . , h_k, where h₁ is known as the “lowest order hash function”, and h_k is known as the “highest order hash function.” Associated with each hash function h_i is a seed value seed comprising a pair (seedindex_i, seedvalue_i). Hash function h_i operates on a pair (index_i, value_i) to produce a pair (newindex_i, newvalue_i), where newindex_i>index_i. To compute target secret S_t, the hash functions are applied successively, starting with the highest order hash function whose associated seed'"'"'s index value is largest without being greater than t, applying that hash function as many times as possible without having that hash function'"'"'s output'"'"'s index value become greater than t, and then applying each successive hash function in turn as many times as possible, until S_t has been computed. To delete the earliest computable secret in the chain, S₁, the new seed for each of the hash functions is computed as follows. Let x=1+index₁, (the index of the seed associated with the lowest order hash function). For each hash function h_i, if x>index_i, then h_i is applied to seed_i. If the resulting index_i is greater than index_i+1, then (index_i+1, value_i+1) associated with hash_i+1 is copied into the (index, value) associated with hash_i. Otherwise, seed is replaced by h_i(seed_i).

Claims

1. A method for computing a target secret S_t in a sequence of secrets S₀ . . . S_n, the method comprising:

obtaining k hash functions h₁, . . . , h_k;

obtaining one or more seeds (index₁, S_h1), . . . , (index_k, S_hk) for hash functions h₁(index, x), . . . , h_k(index, x), respectively, wherein the first component in the seed, index_i, is the index of, and the second component in the seed S_hi is the value of that secret in the sequence of secrets S₀ . . . S_n; and

computing S_t by starting with a seed which precedes S_t and successively applying each hash function h_k, . . . , h₁ zero or more times to produce S_t.

2. The method of claim 1,

wherein the hash functions h₁, . . . , h_k are ordered, with h₁ being the lowest order hash function and h_k being the highest order hash function, and applied in order from highest order to lowest, wherein the index of the seed for a higher order hash function is greater than or equal to the indices of the seeds for lower order hash functions;

and

wherein computing S_t involves starting with the highest-order hash function'"'"'s corresponding seed for which the index is not greater than t, and successively applying each hash function, starting with that hash function and proceeding sequentially through the lower-order hash functions zero or more times to produce S_t.

3. The method of claim 2,

wherein hash functions h₁, . . . , h_k are associated with an increasing sequence of skip values sv₁, . . . , sv_k, respectively, wherein a given skip value sv_i specifies how many secrets in the sequence the associated hash function h_i(x) skips;

and

wherein for a given seed S_hi in the one or more seeds S_h1, . . . , S_hk, the associated index_i is the smallest multiple of sv_i which is greater than the index of the lowest-numbered existing secret S_lowest.

4. The method of claim 1, further comprising:

using S_t as an encryption key to encrypt sensitive data D; and

storing the encrypted data on a computer-readable storage medium.

5. The method of claim 3, wherein successively applying each hash function h_k, h_k−

1, . . . , h₁ involves applying each hash function zero or more times in decreasing order of associated skip values sv_k, . . . , sv₁, so that the highest skip value is applied first and the lowest skip value is applied last.

6. The method of claim 5,

wherein the skip values sv₁, . . . , sv_k are powers of n^1/k, namely n^0/k, n^1/k, n^2/k, . . . , n^k−

1; and

wherein each skip value is applied between zero and (n^1/k−

1) times when computing S_t.

7. The method of claim 3, further comprising deleting a lowest-numbered existing secret S_lowest so that S_lowest cannot be recovered by:

computing x=1+index₁, wherein index₁ is the index associated with the lowest order hash function h₁;

for each hash function h_i,

if x>

index_i,

applying h_i to seed_i;

if the resulting index_i is greater than index_i+1, copying the (index_i+1, value_i+1) associated with h_i+1 into the (index_i, value_i) associated with h_i; and

otherwise, replacing seed_i with h_i(seed_i).

8. The method of claim 3, wherein obtaining the one or more seeds S_h1, . . . , S_hk, involves initializing the one or more seeds by:

obtaining an initial secret S₀; and

for each hash function h_i, computing a corresponding initial value for the seed S_hi=h_i(S₀) and setting an initial for the index for the seed, index_i, to be the index of the initial value of Shi in the sequence of secrets S₀ . . . S_n.

9. The method of claim 1, wherein obtaining the k hash functions h₁(x), . . . , h_k(x) involves deriving the k hash functions from a single hash function h(x), wherein a given derived hash function h_i(x) is computed by:

concatenating x and “

i”

to form x|“

i”

; and

computing h_i(x)=h(x|“

i”

).

10. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for computing a target secret S_t in a sequence of secrets S₀ . . . S_n, the method comprising:

obtaining k hash functions h₁, . . . , h_k;

obtaining one or more seeds (index₁, S_h1), . . . , (index_k, S_hk) for hash functions h₁(index, x), . . . , h_k(index, x), respectively, wherein the first component in the seed, index_i, is the index of, and the second component in the seed S_hi is the value of that secret in the sequence of secrets S₀ . . . S_n; and

computing S_t by starting with a seed which precedes S_t and successively applying each hash function h_k, . . . , h₁ zero or more times to produce S_t.

11. The computer-readable storage medium of claim 10,

wherein the hash functions h₁, . . . , h_k are ordered, with h₁ being the lowest order hash function and h_k being the highest order hash function, and applied in order from highest order to lowest, wherein the index of the seed for a higher order hash function is greater than or equal to the indices of the seeds for lower order hash functions;

and

wherein computing S_t involves starting with the highest-order hash function'"'"'s corresponding seed for which the index is not greater than t, and successively applying each hash function, starting with that hash function and proceeding sequentially through the lower-order hash functions zero or more times to produce S_t.

12. The computer-readable storage medium of claim 11,

wherein hash functions h₁, . . . , h_k are associated with an increasing sequence of skip values sv₁, . . . , sv_k, respectively, wherein a given skip value sv_i specifies how many secrets in the sequence the associated hash function h_i(x) skips;

and

wherein for a given seed S_hi in the one or more seeds S_h1, . . . , S_hk, the associated index_i is the smallest multiple of sv_i which is greater than the index of the lowest-numbered existing secret S_lowest.

13. The computer-readable storage medium of claim 10, wherein the method further comprises:

using S_t as an encryption key to encrypt sensitive data D; and

storing the encrypted data on a computer-readable storage medium.

14. The computer-readable storage medium of claim 12, wherein successively applying each hash function h_k, h_k−

1, . . . , h₁ involves applying each hash function zero or more times in decreasing order of associated skip values sv_k, . . . sv₁, so that the highest skip value is applied first and the lowest skip value is applied last.

15. The computer-readable storage medium of claim 14,

wherein the skip values sv₁, . . . , sv_k are powers of n^1/k, namely n^0/k, n^1/k, n^2/k, . . . , n^k−

1; and

wherein each skip value is applied between zero and (n^1/k−

1) times when computing S_t.

16. The computer-readable storage medium of claim 12, wherein the method further comprises deleting a lowest-numbered existing secret S_lowest so that S_lowest cannot be recovered by:

computing x=1+index₁, wherein index₁ is the index associated with the lowest order hash function h₁;

for each hash function h_i,

if x>

index_i,

applying h_i to seed_i;

if the resulting index_i is greater than index_i+1, copying the (index_i+1, value_i+1) associated with h_i+1 into the (index_i, value_i) associated with h_i; and

otherwise, replacing seed with h_i(seed_i).

17. The computer-readable storage medium of claim 12, wherein obtaining the one or more seeds S_h1, . . . , S_hk, involves initializing the one or more seeds by:

obtaining an initial secret S₀; and

for each hash function h_i(x), computing a corresponding initial value for the seed S_hi=h_i(S₀) and setting an initial for the index for the seed, index_S_hi, to be the index of the initial value of S_hi in the sequence of secrets S₀ . . . S_n.

18. The computer-readable storage medium of claim 10, wherein obtaining the k hash functions h_i(x), . . . , h_k(x) involves deriving the k hash functions from a single hash function h(x), wherein a given derived hash function h_i(x) is computed by:

concatenating x and “

i”

to form x|“

i”

; and

computing h_i(x)=h(x|“

i”

).

19. A system that computes a target secret S_t in a sequence of secrets S₀ . . . S_n, the method comprising:

a computing mechanism configured to compute k hash functions h₁, . . . , h_k; and

a memory storing one or more seeds (index₁, S_h1), . . . , (index_k, S_hk) for hash functions h_i(index, x), . . . , h_k(index, x), respectively, wherein the first component in the seed, index_i, is the index of, and the second component in the seed S_hi is the value of that secret in the sequence of secrets S₀ . . . S_n;

wherein the computing mechanism is configured to compute S_t by starting with a seed which precedes S_t and successively applying each hash function h_k, . . . , h₁ zero or more times to produce S_t.

20. The system of claim 19,

wherein the hash functions h₁, . . . , h_k are ordered, with h₁ being the lowest order hash function and h_k being the highest order hash function, and applied in order from highest order to lowest, wherein the index of the seed for a higher order hash function is greater than or equal to the indices of the seeds for lower order hash functions;

and

wherein computing S_t involves starting with the highest-order hash function'"'"'s corresponding seed for which the index is not greater than t, and successively applying each hash function, starting with that hash function and proceeding sequentially through the lower-order hash functions zero or more times to produce S_t.

21. The system of claim 19,

wherein hash functions h₁, . . . , h_k are associated with an increasing sequence of skip values sv₁, . . . , sv_k, respectively, wherein a given skip value sv_i specifies how many secrets in the sequence the associated hash function h_i(x) skips;

and

wherein for a given seed S_hi in the one or more seeds S_h1, . . . , S_hk, the associated index_i is the smallest multiple of sv_i which is greater than the index of the lowest-numbered existing secret S_lowest.