# Brute-force attack given multiple hash prefixes

(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? ## 2 Answers 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. • 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. – D.W. Jun 17 '15 at 21:37 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.