Consider Case I from Section 7.3.5. Case I: Trudy has decided that she wants to

Question

Consider Case I from Section 7.3.5.

Case I: Trudy has decided that she wants to crack Alice's password. Trudy, who is somewhat absent-minded, has forgotten that she has a password dictionary available. Without a dictionary of common passwords, Trudy has no choice other than a brute force approach. This is precisely equivalent to an exhaustive key search and hence the expected work is 2^55. The result here is the same whether the passwords are salted or not, unless someone has precomputed, sorted, and stored the hashes of all possible passwords. If the hashes of all passwords are already known, then in the unsalted case, there is no work at all—Trudy simply looks up the hash value and finds the corresponding password. But, if the passwords are salted, there is no benefit to having the password hashes. In any case, precomputing all possible password hashes is a great deal of work, so for the remainder of this discussion, we'll assume this is infeasible.

a. If the passwords are unsalted, how much work is it for Trudy to precompute all possible hash values?

b. If each password is salted with a 16-bit value, how much work is it for Trudy to precompute all possible hash values?

c. If each password is salted with a 64-bit value, how much work is it for Trudy to precompute all possible hash values?

Explanation / Answer

a.   If the passwords are unsalted, how much work is it for Trudy to precompute all possible hash values?

Ans)

There is no work at all—Trudy simply looks up the hash value and finds the corresponding password

Without a dictionary of common passwords, Trudy has no choice other than a brute force approach. This is precisely equivalent to an exhaustive key search and hence the expected work is 2^55. The result here is the same whether the passwords are salted or not, unless someone has precomputed, sorted, and stored the hashes of all possible passwords. If the hashes of all passwords are already known, then in the unsalted case, there is no work at all—Trudy simply looks up the hash value and finds the corresponding password

b.   If each password is salted with a 16-bit value, how much work is it for Trudy to precompute all possible hash values?

Ans)

In any case, precomputing all possible password hashes is a great deal of work, so for the remainder of this discussion, we'll assume this is infeasible Hash password with salt

·        Choose random salt s and compute

y = h(password, s)

and store (s,y) in the password file

Note that the salt s is not secret

Analogous to IV

·        Still easy to verify salted password

·        But lots more work for Trudy

c.    If each password is salted with a 64-bit value, how much work is it for Trudy to precompute all possible hash values?

Ans) In any case, precomputing all possible password hashes is a great deal of work, so for the remainder of this discussion, we'll assume this is infeasible.

Salts only need to be long enough so that each user's salt will be unique. Random 64-bit salts are very unlikely to ever repeat even with a billion registered users, so this should be fine. A singly repeated salt is a relatively minor security concern, it allows an attacker to search two accounts at once but in the aggregate won't speed up the search much on the whole database

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.