How to figure about the total amount of password combinations possibles that have salt values?

Question

I'm reading this book about Computer Security to better prepare me for my role, however, this question is just not clicking to me. I've figured out half of it, but cannot figure out this last part. If someone can show me how, that would be great.

The question:

Assume that passwords in a system are limited to the use of 95 printable ASCII characters and that all passwords are 10 characters in length. Assume the system is not using any salt values.

a. How many different passwords are possible? 95^10 possible passwords

b. Assume a password cracker with an encryption rate of 6.4 million encryptions per second. How long will it take to test all possible passwords? 296,653 years (based on my calculations)

Suppose that there are only 4 users in the system described in part (I) of the question, and each user has a different salt value (stored as plain text in the password file).

c. If the password cracker above is used, how long will it take to test all possible passwords?

I cannot figure out question C. The added possibility of 4 users and different salt values is really throwing me off. If I could figure out the different combinations, the time needed to test all passwords would be cake to calculate. If someone can show me how to figure this out, that would be great!

Answer 1

Salt is stored in plain, alongside the hash, so there is no need to test multiple salt combinations when the correct salt is known. This will make your calculations simple.

If there is no salt, one could crack all passwords in one brute force job.

But if each of the 4 users has a different salts, then it will take 4 separate brute force jobs.

So 296,653 years for a single salt × 4 unique salts = 1,186,612 years to crack passwords for all users.

Answer 2

Being nitpicky - for b., if you're using years as your unit of time, make sure to use 365.25 days/year instead of 365, you should account for leap year.

c. is tricky. The initial question asks you to assume the system is not using any salt values. In the preface for part c, they mention that each user has a unique salt. Don't let that throw you off. Does the text prior to this question mention which hashing algorithm was used to hash the passwords initially? If there is no mention of how much time would be used when including a defined salt, and each salt is unique per password hash, then the calculation is straightforward.

In this example, it would take the software 296k years to crack one password with no salt, and there is no time penalty for salting, then assume that each unique salt would require the same amount of time per password. There is also no specification that the password cracker is multi-threaded. The calculation would be:

• (x (passwords) * rate (time / password)) / n (threads) = time
• (4 passwords * 296K years)/1 thread = 1.185 M years

Also... if the salts are the same per password, a correct answer would be "less than 1.185M years", otherwise, your answer would be just "1.185 M years".

Answer 3

What unique per-user salts do is to make the computations performed to attack one user's password be useless for attacking any other user. Alternatively put, if there are no salts, then for each password that the attacker tries, they get to test that password against all four users' hashes. If there are unique salts, the attacker has to perform a separate brute-force attack for each password entry.

That should be enough of a hint.

---

I must add that I'm concerned about the quality of the teaching materials that you're using. You just quoted a tiny snippet, and yet I see several flags:

1. It talks about "encrypting" passwords instead of hashing them.
2. 6.4 million "encryptions" per second isn't actually as fast as it might sound. GPUs are able to compute orders of magnitude more hashes per second. It doesn't affect the answer of the problem, but improving its realism would be fine.
3. The number of most interest isn't the amount of time to test all passwords, but rather the average time until the attacker succeeds.
4. The time estimate assumes that the users pick their passwords uniformly at random, which isn't how most real-life users do it.

To expand on the third point, the cracker would have to be extremely unlucky for their last brute force guess to be the right one. That'd be the worst case; on average, they only need to test half of the possible passwords to succeed.

(And if we're talking about four users with unsalted passwords, and we assume the goal is to brute force one password, that further quarters the expected time until success.)

On point #4, if the attacker can guess likelier passwords ahead of unlikely ones, that brings down the expected time until success. In real life, password cracking uses a variety of techniques to attempt this (e.g., dictionaries of common passwords), and those techniques are very successful.

Answer 4

I sincerely hope that the passwords are (one-way, preferably via a slow function) hashed, not (reversibly) encrypted. There are extremely few situations where encrypting login passwords is a good idea (mostly because, if you do that, an attacker who managed to steal your password verifiers probably also managed to steal the encryption key and it will take them milliseconds to decrypt the verifiers and get the passwords back).

Assuming they are hashed, not encrypted, adding a salt doesn't make it take any extra time per password, because the salt is just prefixed (or appended) to each guessed-at password value before you hash it and check the hash. However, it does mean each password must be brute-forced independently; even if you compete the entire search space for password 1, that won't save you any time at all with password 2 because the salt is different. I'm not going to spoon-feed you the answer here, but you know how long it'll take to brute-force one password independently...