4
$\begingroup$

(Context: I'm auditing some code which I suspect to be insecure, but I'd like to be able to quantify this.)

Suppose you have a 56-bit secret key ($secret), and suppose you have revealed the following information to untrusted parties:

  • $salt – An easily discovered string
  • $prefix – The first 32-bits from sha1($secret + $salt)

Based on a previous question, an attacker could perform an offline attack using ($salt,$prefix) as a sieve to narrow the list of possible $candidates. This sieve would reduce the number of candidates from $2^{56}$ to $2^{(56-32)}=2^{24}$.

Now suppose you reveal multiple variations of ($salt,$prefix) (all based on the same $secret). The attacker now has multiple sieves; if applied iteratively, each sieve would further narrow the list of possible $candidates.

I'd like to understand how quickly $candidates will filter down to the true $secret. For example, if you have two prefixes, how many $candidates should be left? If you have three prefixes, how many should be left?

$\endgroup$
2
$\begingroup$

If you have two prefixes, say $p_1$ and $p_2$ assuming a well designed hash function, this will give you two lists of possible candidates $L_1,L_2$ each of size roughly $2^{24}.$ The correct value is in both of these lists. It is unlikely to also have spurious candidates since assuming uniformity o relevant variables and fixing, say the list $L_1$, the probability that a random quantity from $\{0,1\}^{56}$ is not in $L_1$ is $$ \left(1-\frac{2^{24}}{2^{56}}\right)=\left(1-\frac{1}{2^{32}}\right), $$ since $\lim_{n\rightarrow \infty}\left(1+\frac{x}{n}\right)^n=\exp(x).$ Thus the probability that the $2^{24}$ elements in $L_2$ all fall outside $L_1$ is $$ \left(1-\frac{1}{2^{32}}\right)^{2^{24}}=\left[\left(1-\frac{1}{2^{32}}\right)^{2^{32}}\right]^{2^{-8}}\approx \exp(-2^{-8}) \approx 0.9961 $$ so only in one of about 250 trials would there be a spurious candidate in addition to the correct candidate.

Edit: It is widely believed and supported by experimentation that SHA-1 is such a function. Ignore my earlier reference to universal hash functions.

$\endgroup$
1
  • $\begingroup$ There's no "big question" here. SHA-1 is almost certainly such a function -- if it wasn't, it would be horribly broken, and we probably would have noticed this deviation from random from now. So from the perspective of an attacker, yes, an attack can absolutely treat SHA-1 in this way. As a result, the bottom line is: 2 candidates are enough to filter down to the true secret. Universal hash functions are a distraction, and the last paragraph introduces uncertainty that doesn't really exist in practice. $\endgroup$ – D.W. Jun 17 '15 at 21:37
1
$\begingroup$

2 candidates are enough that you can (with high probability) uniquely identify the correct secret. An attacker would still have to enumerate all $2^{56}$ possible values for the secret -- or, on average, about $2^{55}$ values -- to find the right one. But if the attacker has 2 candidates, then this is enough information that the attacker can recognize when he has the correct value for the secret.

So, yes, your code is insecure. 56-bit security is not enough for most purposes.

$\endgroup$

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.