# Can the SHA256 hashes of consecutive integers be attacked?

Suppose that the attacker knows the SHA256 values of integers $n, n+1, n+2 ... n+k$.

$n$ is sufficiently big, so we do not expect to be able to brute force $n$ just by $\operatorname{SHA256}(n)$ itself. $k$ is very small compared to $n$.

Is there risk that he can calculate $n$ in reasonable time?

• @MaartenBodewes They are just .. numbers (like unsigned int). The attacker knows only the hash values, and he has to guess the value of n. – sqd Mar 21 '16 at 14:19
• How big are $n$ and $k$? – CodesInChaos Mar 21 '16 at 14:21
• @CodesInChaos details updated – sqd Mar 21 '16 at 14:29

If we assume that the range of possible values of $n/k$ is sufficiently large that it is infeasible for the attacker to scan through $\operatorname{SHA256}(ik)$ values (and look for a match in one of the hashes), then it would appear to be secure. There is no known weakness in SHA256 about hashing related messages.

• Length extension attacks are a "known weakness in SHA256 about hashing related messages." ​ (However, I don't see any way of using them here.) ​ ​ ​ ​ – user991 Mar 22 '16 at 0:20
• @RickyDemer: Yes, you are correct (and I don't see a way of using them either) – poncho Mar 22 '16 at 0:46
• Where "sufficiently large" is something of the order $n/k > 2^{80}$. Higher if you care about state level attackers. – CodesInChaos Mar 22 '16 at 9:24
• Although I agree with this answer, I can't think of a good reason for not salting the input numbers. – r3mainer Mar 22 '16 at 11:05
• Perhaps it should be noted more strongly that what's stated in the question is not enough to insure that the range of possible values of $n/k$ is sufficiently large. For example, we could have $n=2^{88}$ [so that we do not expect anyone but a massively funded adversary to be able to brute force $n$ just by SHA256(n) ], and $m=2^{32}$ [making the attack outlined in the answer feasible with an expected $2^{55}$ hashes and as many memory fetches and like 25 GB memory, which is clearly feasible]. – fgrieu Mar 23 '16 at 11:54

In your case, the hash function should be correlated-input secure. Hash functions that meet this notion were considered in literature, e.g., https://eprint.iacr.org/2011/233. One caveat is that correlation under these constructions is defined relative to a specific class of inputs. The paper describes a simple example of a one-way function that is not correlated-input secure. But in practice, $\operatorname{SHA256}$ is used to model a random oracle, which, by definition, is correlated-input secure.

This could be susceptible to a rainbow table attack, especially if you can collect lots sequential ones.

For example, if I have a rainbow table of hash(0), hash(1000000), hash(2000000).... which would be 1/1,000,000th of the size of the full rainbow table, then I could look up each value coming out of your sequence in my rainbow table. Once I know one, I know all previous and all future numbers. It would take, on average, 500,000 numbers from your sequence that matches.

Similarly, if any number you hashed coincedentally occurred in a rainbow table, then all would be lost (future and past). For example, 555555555 is in crackstation, so if you went past that, you'd be sunk.

I tried running some hashes of random numbers through crackstation - 7 digit random numbers seem to be precalculated, 9 digits not.

If you started at a random 64-bit number (about 19 digits), then you might get away with it, almost all of the time.

• This would be like choosing a random IV in CTR mode. Then each block is enciphered by incrementing the counter of the previous block, but the first block has a random start value. – user9070 Mar 24 '16 at 12:56