[Hardware] Notes... The case for an open client
Elektron
elektron_rc5 at yahoo.ca
Sun Aug 15 16:37:20 EDT 2004
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
More information about the Hardware
mailing list