Calculation of time to crack 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? –  Henrick Hellström Dec 17 '13 at 8:42
It is related to a project, so yes, an exact answer or at least the method to calculate it, would do.. –  user2994590 Dec 17 '13 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. –  CodesInChaos Dec 17 '13 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. –  Henrick Hellström Dec 17 '13 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... –  Richie Frame Dec 17 '13 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.

-