5
$\begingroup$

How do I calculate the number of computations needed to break SHA256 in case we are using it for safely storing passwords (together with a salt)? Are there any formulas that can be employed?

For example:

Passwords are chosen to be 5-character strings composed of lowercase Latin letters and numbers, and are stored as SHA256(password XOR s)||s, with s chosen as a 5 byte array filled with random content.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ ... "stored as SHA256(password XOR s)||s".... this hurts so much. Please don't use such schemes. Please use at least PBKDF2 or even better bcrypt or scrypt. $\endgroup$
    – SEJPM
    Jul 6, 2015 at 21:51
  • $\begingroup$ I know that scheme is highly unsecure, also given the fact that the pswd alphabet is quite limited. But anyway, I was interested in finding a way to determine the "exact" number of SHA algorithm computations an attacker would have to do in order to employ a bruteforce attack. Also, it would be nice to compare that number with the number of computations (s)he would need in order to find the password, by employing, for example, a rainbow table lookup. $\endgroup$
    – user3333434
    Jul 6, 2015 at 22:02
  • 1
    $\begingroup$ rainbow table isnt even necessary with such a small password and poor salt scheme, only 32GB are required to store the entirety of all salted hashes, with around 1000s of precomputation on a modern desktop, or just over 1 minute on a crack machine. $\endgroup$
    – Richie Frame
    Jul 6, 2015 at 23:44

2 Answers 2

Reset to default
6
$\begingroup$

Possible password search space = $36^5$ = 6.05 million possible combinations or ~$2^{26}$. If the passwords were randomly generated it would be 26 bits of entropy which isn't just weak it is pointless.

To put that into perspective the throughput on modern GPUs is on the order 1 billion SHA-256 hashes per second. So the exhaustive search time to break an account would be 60ms. An attacker could break about 60,000 accounts per hour.

Rainbow tables are a non issue as you are using per record random salt. It is too short to be fully effective but given how weak it is generating the rainbow tables would take far longer than just breaking all the accounts.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Importantly, the hashing algorithm is irrelevant, outside of having a constant (negligible) work factor. The only important part is the entropy in the passwords, which is catastrophically weak and results in only a few million "operations" needing to be performed. $\endgroup$
    – Stephen Touset
    Jul 6, 2015 at 23:02
  • $\begingroup$ 1 billion per second is using an off the shelf video card from a few years ago, a modern system designed for cracking or bitcoin mining based on Haswell-E with multiple cards can do over 15 times that rate, or about 1 million accounts per hour $\endgroup$
    – Richie Frame
    Jul 6, 2015 at 23:25
  • $\begingroup$ Nitpick: your times to break are off by a factor of two, because on average you need to check only half the search space. $\endgroup$
    – otus
    Jul 7, 2015 at 11:44
5
$\begingroup$

As Gerald Davis explained in the other answer, there are about 6 million possible passwords, which is way too few.

However, there's an additional weakness: since the password and salt are combined with XOR rather than concatenation, it is sufficient to generate a table for all hash values. If you know the $x$ for which $H(x) = h$, you know that the password was $p = x \oplus s$.

So a simple list with $2^{40} \approx 10^{12}$ entries (some gigabytes) would cover every password-hash combination, without even needing to use hash chains or a rainbow table. In contrast, if the password and salt were concatenated, such a list would need on the order of $10^{20}$ entries (hundreds of petabytes at least).

In this case it doesn't matter, since the password search space is so small as to be breakable regardless, but with more complex passwords that would be a significant weakness. E.g. if you had random n-byte passwords with random n-byte salt, the salt would be completely useless.

Just goes to show that you shouldn't make up your own password hashing scheme, but use established algorithms.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Additionally always using a salt of the same length as the password, you are effectively leaking the length of the password. While not disastrous, it does tell an attacker which accounts are the easiest targets. $\endgroup$
    – kasperd
    Jul 7, 2015 at 6:39
  • $\begingroup$ @kasperd, even if you used XOR to combine, you wouldn't have to make them the same length. You could e.g. zero-pad one or the other. $\endgroup$
    – otus
    Jul 7, 2015 at 6:55
  • $\begingroup$ That could work. And if the salt was then made long enough, you would solve the weakness introduced by using XOR rather than concatenation. I would still feel better about concatenation though. $\endgroup$
    – kasperd
    Jul 7, 2015 at 7:01

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.