3
$\begingroup$

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?

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

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.

$\endgroup$
  • 1
    $\begingroup$ Length extension attacks are a "known weakness in SHA256 about hashing related messages." ​ (However, I don't see any way of using them here.) ​ ​ ​ ​ $\endgroup$ – user991 Mar 22 '16 at 0:20
  • $\begingroup$ @RickyDemer: Yes, you are correct (and I don't see a way of using them either) $\endgroup$ – poncho Mar 22 '16 at 0:46
  • $\begingroup$ Where "sufficiently large" is something of the order $n/k > 2^{80}$. Higher if you care about state level attackers. $\endgroup$ – CodesInChaos Mar 22 '16 at 9:24
  • 1
    $\begingroup$ Although I agree with this answer, I can't think of a good reason for not salting the input numbers. $\endgroup$ – squeamish ossifrage Mar 22 '16 at 11:05
  • 1
    $\begingroup$ 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]. $\endgroup$ – fgrieu Mar 23 '16 at 11:54
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user9070 Mar 24 '16 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.