Fast computation of one-way hash sequences

• US 8,538,014 B2
• Filed: 05/12/2008
• Issued: 09/17/2013
• Est. Priority Date: 05/12/2008
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Perlman, Radia J.
• Primary Examiner(s): Kim, Jung
• Assistant Examiner(s): Ho, Thomas
• Application Number:
  US12/118,893
• Publication Number:
  US 20090279692A1
• Time in Patent Office: 1,954 Days
• Field of Search: 380/28, 380/262, 380/44
• 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:

using a computer to perform operations for;

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

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

computing S_t by starting with a seed which precedes S_t, wherein the seed that precedes S_t corresponds to a highest-order hash h_i for which a corresponding index is not greater than t, and successively applying each hash function h_k, . . . , h₁ a corresponding number of times to produce S_t; and

storing S_t in a computer memory;

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 order, 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;

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 to produce S_t;

wherein, for each hash function, the number of times the hash function is applied to compute S_t is determined using t and the index for the hash function;

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.

2. 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.

3. The method of claim 1, 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.

4. The method of claim 3,

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.

5. The method of claim 1, 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).

6. The method of claim 1, 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 S_hi in the sequence of secrets S₀ . . . S_n.

7. 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”

).

17. The method of claim 1, wherein each of the hash functions corresponds to a different order of magnitude for S_t, and wherein, for each hash function, the number of times the hash function is applied to compute S_t is determined using a difference between a value for the order of magnitude for S_t corresponding to the hash value and a value for the order of magnitude of the index for the hash function.

18. The method of claim 1, wherein each of the hash functions corresponds to a position for a digit of S_t, wherein each of the hash functions corresponds to a different position, and wherein, for each hash function, the number of times the hash function is applied to compute S_t is determined using a difference between a value for a digit of t at a position corresponding to the hash function and a value for a digit of the index for the hash function at a position corresponding to the hash function.

8. A non-transitory 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₁, . . . , h_k, respectively, wherein the first component in the seed, index_i, is the index of a secret S_i, 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, wherein the seed that precedes S_t corresponds to a highest-order hash h_i for which a corresponding index is not greater than t, and successively applying each hash function h_k, . . . , h₁ a corresponding number of times to produce S_t;

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 order, 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;

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 to produce S_t;

wherein, for each hash function, the number of times the hash function is applied to compute S_t is determined using t and the index for the hash function;

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.

9. The computer-readable storage medium of claim 8, 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.

10. The computer-readable storage medium of claim 8, 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.

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

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.

12. The computer-readable storage medium of claim 8, 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_i with h_i(seed_i).

13. The computer-readable storage medium of claim 8, 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.

14. The computer-readable storage medium of claim 8, 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”

).

15. 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₁, . . . , h_k, respectively, wherein the first component in the seed, index_i, is the index of a secret S_i, 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, wherein the seed that precedes S_t corresponds to a highest-order hash h_i for which a corresponding index is not greater than t, and successively applying each hash function h_k, . . . , h₁ a corresponding number of times to produce S_t;

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 order, 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;

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 to produce S_t;

wherein, for each hash function, the number of times the hash function is applied to compute S_t is determined using t and the index for the hash function;

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.

16. The system of claim 15,

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.