Re: [FWP] crypt() fun

[Bennett Todd <bet@rahul.net>]

2000-06-14-04:03:42 Ariel Scolnicov:
> To detect a cycle, you can use a constant-memory algorithm.

Thanks! That was what I tried, and failed, to remember when I
offered my lag/2 detector. It hadn't occurred to me to make the
algorithm constant-memory by doing a third again more crypts. That
tradeoff appeals to me, frankly. I.e. I like your version better.

> However, I'm fairly confident that DES has no known fixpoints.

That's an interesting theoretical result. I wasn't aware of it.

> Perhaps some modification would...

Well, crypt(3) is definitely some modification; it uses the salt to
modify one of the DES internal tables, then shoves a block of nulls
through the resulting modified DES, then takes the output of that
and shoves it through again, and 'round and 'round --- 16 times?

But whether this modification produces a hash with one or more fixed
points would be another pretty obscure result. At least I'd find it
obscure:-).

-Bennett

PGP signature