# Calculation of time to crack a SHA-256 hash

A problem is given: 1 million users are authenticated with 9-digit PIN codes (e.g. 343534643). The PIN values are stored as hash values in a database. The hash is SHA-256, and is computed as:

hash=SHA-256(password|username)


An attacker has a graphics card which can compute 500 million hashes in a second. How long does it take to crack at least 1 password from the 1 million in the database?

• Is this homework and you want an exact answer, or would "no more than two seconds" do? Dec 17, 2013 at 8:42
• It is related to a project, so yes, an exact answer or at least the method to calculate it, would do.. Dec 17, 2013 at 8:44
• Since you're using a salt (the username), multi-target attacks don't work and thus it doesn't matter if there are one or one million hashes in the db. Dec 17, 2013 at 8:47
• Regardless, if you are only interested in a single password (for a specific user), brute force would be fast enough, to make actually programming the attack the most time consuming step, even if you attack by brute force. Dec 17, 2013 at 8:49
• looks to me like each password would take at most 2 seconds to crack, since there are 1 less than 1 billion possible passwords per username, and half a billion hashes per second... Dec 17, 2013 at 9:44

The "million usernames" is a red herring, because the user name is used as "salt": the hash value is computed over the password and the user name. When the attacker tries a potential password, he must choose which user name he puts in the hash function; and if a match is found, then this will be for the hash value for this user name only.

In other words, the attacker cannot do any better than choosing one hashed password to crack, for a specific user name, and crack that. That there are one million of hash values does not give any advantage to the attacker.

Now, consider that the attacker tries to crack one password; he has the hash value and the user name. There are $10^9$ possible passwords. If we assume that the passwords have been chosen randomly and uniformly, then the best that the attacker can do is to try them all (in any order) and hope for a match. On average, the attacker will need to try about half the key space, i.e. 500 millions, of possible passwords until a match is found. Since the attacker's hardware can compute 500 millions of hash values per second, the average time to crack one password is one second.

Similarly, if the attacker wants to crack, say, 10 passwords for 10 distinct users, then it will take him 10 seconds on average.

User names, as salt values, are suboptimal. In the context of this question, user names work well: their role is to prevent parallel attacks, and since no two users have the same name, then parallel attacks are indeed prevented. To break $n$ passwords the attacker must pay $n$ times the cost of breaking one password.

However, in practice, user names are reused, in two ways (at least):

• When a user changes his passwords, his name remains the same, so the old and the new passwords will be hashed with the same "salt". Attacking both simultaneously will be possible.

• User names are unique on a given system. But software is reused. To put things bluntly, all systems will have an "admin" user with that name; this opens the road to parallel attacks, e.g. precomputation: the attacker could precompute hash values for a given user name (such as "admin") and the billion of possible passwords; thus, when the attacker actually gains access to the database, breaking the "admin" password will be a matter of a single lookup, which will take a microsecond or so (assuming the table is in RAM), not one second. Attackers could even collude and exchange tables, so that one attacker computes the table and his dozens of friends benefit from that one-time effort.

Thus, random strings are considered to be better salts, because they will ensure worldwide uniqueness with high probability, much better than user names (assuming that the random salts are large enough; UUID are good practical salts).

On the concept of password hashing, see this answer for a lengthy introduction.

If we assume that each PIN code has exact 9 digits (10^9). We can eliminate all possibilities for shorter PIN codes (10^8). Hence the time to crack a single user PIN code is less then a second on average .

Max. PIN codes to hash 10^9 - 10^8 = 900 Mio Max. 1,8 seconds

Avg. PIN codes to hash 900 Mio / 2 = 450 Mio Avg. 0,9 seconds

Final thoughts: In a real world project the PIN code MUST be encrypted with at least 128bit security to protect them against offline cracking attacks. SHA256 MUST be replaced with BCRYPT, SCRYPT, ARGON2 ... whenever possible, because this password hash functions are designed to be slow and memory consuming.

• The problem statement does not suggest 012345678 would be an invalid PIN.
– fgrieu
Jul 26, 2023 at 7:58
• $10^9$ /is/ the number of 9-digit PIN codes, there's no need to subtract $10^8$ from there. The mention of 'encrypting' passwords seems also a bit out of place - applications such as credit cards notwithstanding. Jul 26, 2023 at 8:31
• FYI: actually, real-world PIN should be protected by HSM. Think FIDO. Jul 26, 2023 at 9:12