Re: Notes... The case for an open client

I appear to be bad at writing replies.

>> Do you have a magic ability to out guess a random number generator?
>
> Nope. Nor was the key generation source publically released, or the
> system identified that it was run on. For all I know it was an older
> unix box with a flawed rand function. Or that the default seed function
> was used, with some predicable range or number of iterations that would
> give a clue about distributions in the pseudo random sequence.

Nobody needs the source. It was probably /dev/srandom or so, anyway. 
The microsecond timer can have enough entropy. Hell, on a PowerPC 
there's an easy way to gather entropy. Count jumps in the timebase. 
Gather enough bits, through a hash function (RC5 is decent), get n-bits 
of key. Repeat.

The fact is, if

> I have developed a preference for run length searching from other
> efforts which were based on human originated keys, since the ascii
> text and key generation algorithms tend to perserve the non-random
> nature of the text originally entered. That perference, might well
> not make sense here, IF the random number generator used was truely
> verifiably random.

MD5 is random enough. SHA1 is random enough. If they weren't, there 
would be no point using them. You're talking about probably the biggest 
encryption company in the world, and you'd think they'd make 
not-so-random keys?

The argument from your original post was that "since half the keys have 
run lengths of 4 and 5, it's better to search there first". Similarly, 
"since half the keys have the high bit on, it's better to search there 
first".

Okay, here's a crappy random number generator, coded on the spot. Pick 
two primes between 2^15 and 2^16, PRIME1 and PRIME2.

int random(unsigned int entropy) {
	static unsigned int number;
	number ^= entropy;
	number = ((number * PRIME1) + PRIME2) ^ (number + 1) ^ (number >> 16) 
^ entropy;
	return number;
}

Here's how you seed it cheaply every time:

int random2() {
	struct timeval tv;
	if (gettimeofday(&tv, NULL)) { exit(1); }
	return random(tv.tv_sec ^ tv.tv_usec);
}

Here's how you start it off:

void randominit() {
	unsigned int x;
	x = time(NULL) + 1;
	while (x < time(NULL)) {;}
	while (x == time(NULL)) {
		random(random2());
	}
}

random2() is the secret key. Calculate the number of keys you'd have to 
search if you started from 0. Calculate the number of keys you'd have 
to search if you did desired-run-length numbers first (calculating the 
max run length of the secret key is easy. calculating the number of 
secret keys of each run length isn't too hard. Figuring which key out 
of n secret keys of run length 5 is hard).

Get 1000 secret keys. Add up the total number of keys you'd've searched 
through starting from 0 (use of long longs is recommended). Add up the 
total number of keys by run-length-preference. Try to save 10% of the 
effort.

If you can get it to work in a simulator, then feel free to propose 
strange ways of handing out blocks. If not, don't make blind 
speculation. For all you know, any given random function may end up 
making longer runs than usual, or shorter runs than usual, or be random 
enough to avoid making funny runs.

For the record, by calculation, 84.88% of 6-digit PINs contain at least 
two of the same digit. Oddly, I'm often getting values 4 or 5 standard 
deviations (either side) of the mean.

- Purr

_______________________________________________
Hardware mailing list
Hardware-Ra3b/QYEcJ3d140v2zMXi0fjHoOT/h/[email protected]
http://lists.distributed.net/mailman/listinfo/hardware