Re: [FWP] crypt() fun

[Bennett Todd <bet@rahul.net>]

2000-06-12-17:46:34 Jeff Pinyan:
> I'm searching for a 13-character string that, when crypt()ed upon itself,
> returns itself.

Sounds like fun!

To the comments others have made, I'd add a couple. First off, it
might be worth looking at the modified-DES implementations used by
brute-force password crackers; they'll be the fastest available.

As others have suggested, it's probably worth doing this whole thing
in C, for the performance edge, as well as making arrangements to be
able to distribute it over a lot of boxes.

And one more thought: while the nature of a cryptographically strong
hashing algorithm may make this approach fruitless, at least with
some mathematical functions a feedback loop, like:

	my $last = '';
	my $cur = "any random start";
	while ($cur ne $last) {
		$last = $cur;
		$cur = crypt($cur, $cur);
	}

finds fixed-points surprisingly fast. Of course if it finds one it
might be a cycle, so a robust searcher would want to run the lag/2
loop detector, and reseed with a new random start each time it
snags. Something like maybe

	my $last = '';
	my $cur = random_string_gen();
	my @lag = ($cur);
	while (1) {
		$last = $cur;
		$cur = crypt($cur, $cur);
		last if $last eq $cur;
		$cur = random_string_gen() and @lag=($cur) if $lag[0] eq $cur;
		push @lag, $cur;
		$last = $cur;
		$cur = crypt($cur, $cur);
		last if $last eq $cur;
		$cur = random_string_gen() and @lag=($cur) if shift(@lag) eq $cur;
		if ($#lag > 10000) {
			$cur = random_string_gen();
			@lag = ($cur);
		} else {
			push @lag, $cur;
		}
	}

or thereabouts. Naturally it'd be rather more painful to try and say
this sort o' thing in C :-).

-Bennett

PGP signature