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$
3
  • $\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, 2016 at 14:19
  • $\begingroup$ How big are $n$ and $k$? $\endgroup$ Mar 21, 2016 at 14:21
  • $\begingroup$ @CodesInChaos details updated $\endgroup$
    – sqd
    Mar 21, 2016 at 14:29

3 Answers 3

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$
5
  • 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, 2016 at 0:20
  • $\begingroup$ @RickyDemer: Yes, you are correct (and I don't see a way of using them either) $\endgroup$
    – poncho
    Mar 22, 2016 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$ Mar 22, 2016 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$
    – r3mainer
    Mar 22, 2016 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, 2016 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$
1
  • $\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, 2016 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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