On Sun, 27 Sep 2009, Dave Searles wrote:
alexandre_paterson@yahoo.fr wrote:
On Sep 25, 5:11 pm, grz01 <gr...@spray.se> wrote:
...
The pw-hashes must be stored in a protected place (unless you're fine
with "toy security").
Wait... (my post is apparently unrelated to the OP's problem btw)
I agree that storing {hash} is stupid, but long before
shadow passwords Un*x systems where already storing:
{hash(password+salt),salt}.
(a long time ago it was a lame 12-bit salt, but nothing stops me
nor anyone from using a much bigger salt, which I sure did ;)
Are you saying that storing {hash(password+64-bit salt), 64-bit salt}
without the equivalent of shadow passwords would be "toy security"?
It seems to me that if you have the hash and the salt, and know the
algorithm for convolving the password with the salt, then you can
still carry out a dictionary attack.
On the other hand, if the password is something like zs1df3rh, good
luck with that.
The point is that without a salt, you can make one pass through the
dictionary and recover *all* the passwords in the file:
for word in dictionary:
hashedWord = hash(word)
for username, hashedPassword in passwordFile:
if (hashedPassword == hashedWord):
print username, hashedWord # pwned!
Whereas with a salt, you need to do a different computation for each user:
for word in dictionary:
for username, salt, hashedPassword in passwordFile:
hashedWord = hash(word, salt)
if (hashedPassword == hashedWord):
print username, hashedWord # pwned!
Note that in the former case, the hashing operation is inside the word
loop; in the latter, it is inside the loop over the passwords. If you
have w words and u users, then the former is O(w) to crack all users,
whereas the latter is O(w*u) to crack them all. Correspondingly, the
time taken to crack any one user is something very vaguely like O(w/u)
in the former case, and O(w) in the latter.
You use of big-O is rather unconventional.
But we understand the point.
Very important: you logic assumes different salts per user. That
is good practice. But I think it should be emphasized.
Which means that Alexandre's challenge is actually rather silly. Adding
salt doesn't make any single password more secure, it makes the
population of passwords more secure. If he's giving us a single password
to work on, then the salt will make no difference.
it invalidates pre-calculated dictionaries.
one among many passwords.