[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]

Re: Open Xlock as root



At 19:39 08/12/99 -0500, Michael K. Johnson wrote:
>"Craig R.P. Heath" writes:
>>No, you're right, that was the weakness I was thinking of.  I do think
>>that collisions are of significant concern in password algorithm
>>though.  If I'm doing an exhaustive search against an encrypted
>>password, and there are actually four possible strings which hash to
>>that value, then on average I will find a password that works four
>>times more quickly.
>
>Look, it's a digest.  If it's good, it has infinitely many collisions!
>(If it doesn't have infinitely many collisions for any particular
>digest, then it is not equally weighted, and so is a bad digest
>algorithm.)

I know its a digest.  I also know that it's a 128 bit digest (or
16 bytes, if you prefer).  16 bytes is bigger than the average
password, so if it was a good _password_ algorithm, you'd expect
there to be minimal collisions.  You have infinitely many collisions
if you have an infinitely large input.  Does your xdm program have
an infinitely large input field for the password?  And an infinitely
large virtual memory to store it in?  I expect you're exaggerating
for effect, but you don't have to treat me like an idiot.

Oh, and incidentally, a good digest algorithm should have less
collisions than a bad digest algorithm, so I don't know what point
you're trying to make there.

>But you are wrong that that if you have four possible strings, you
>will find the result four times as quickly, and, in fact, what I just
>said proves it ad absurdum.  There are infinitely many collisions, but
>it is not inifinitely "faster" (faster than what?) because "inifinitely
>faster", if it has any meaning at all, means "instantaneously", which
>is clearly not true.

There's only an infinite number of collisions if there's an infinitely
large input.  If you can manage to cast your mind back, I was talking
about exhaustive search attacks.  An exhaustive search of an infinitely
large space takes an infinite amount of time.  So, it's infinitely
faster?  So what?  It's still infinite.  Check a maths textbook if
you don't understand this.

>Essentially, worthwhile crack attempts are not random; they use human
>language information characteristics to narrow the search, and within
>those boundaries, collisions will be much less likely, and there are
>probably very few collisions between the relatively short strings that
>people use as passwords anyway.

But that's the point - "probably".  There is some chance of collisions,
we agree, but who knows whether there are more collisions with the
libcrypt algorithm or with the MD5 algorithm?  Neither of us, it would
seem.  I just referred to the relatively recent discovery that there
were more collisions with MD5 than people had previously thought, as
an interesting point to demonstrate that no one has proved the MD5
algorithm to be a better one.  I don't know if it is, you obviously
don't know if it is, why don't we both shut up until someone comes
along who does?

			- Craig.



[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index] []