> Date: Fri, 11 Jun 1999 13:05:01 -0400
> From: Justin Hahn <jehahn@raven.bu.edu>
>
>> Explain this. Any decent hash function has the following properties:
>>
>> - non invertible (or not trivially so)
>>
>> (note that a good hash function need not be bijective, and I'd
>> conjecture that it shouldn't be)
>
> The problem is that user's passwords are in a much smaller space, so you
> can simply try to invert the has by trying all possible "typable"
> passwords, which is small enough that that a brute-force attack is
> tractable.
Hmm, let's consider this.
given 26 alphabetic characters, in 2 cases (52 characters), 10
numerals, 32 marks of punctuation, we have symbol space of 94
characters. 94^8 < 2^56, so for common password lengths you are 100%
correct. (assuming you can run your hash algorithm, usu. MD5 or DES
quickly.)
However, if we up the password length to, say 15 characters (a
kerberos pass-phrase, for example), then 2^96 < 94^15, which is then
computationally difficult. Even 10 character passwords have a large
search space than 2^64. These sorts of passwords are currently
possible with MD5 and Kerberos passwords. Further MD5 passwords can be
ANY length, yielding an essentially infinite search space.
Further the MD5 algo, IIRC, makes it impossible to guarantee that the
image of any finite subset of the domain contains any given
encoding.
Of course, I'm pretty much violently agreeing with you. Standard UNIX
passwd space is TINY, and insufficient for real security. But, if you
were to increase the length of the typable password, you reach a
sufficiently large space to make brute-force presently
infeasible. (unfortunately, these spaces are small enough to become
tractable in a few years I would guess.) This has gotten pretty
offtopic. We should probably kill the thread.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/