[Hardware] Notes... The case for an open client

Elektron elektron_rc5 at yahoo.ca
Tue Aug 17 00:29:02 EDT 2004

> So when you stand before me in this discussion, huffing and puffing,
> that I don't have a right to explore this line of thought, because
> you are the expert:
> 	> Please don't talk about "probabilistic number theory"
> 	> without any knowledge; this is A-level statistics, which I learned 
> at
> 	> 15.
> and then construct fundamentally flawed arguments as your chest
> thumping proof - don't be suprised if someone calls your bluff.
> I suspect that more than myself in this forum is not impressed
> that your proof in the end was just a trust in RSA.

So's yours. You mention "probabilistic number theory" (there are only 
812 Google matches, which also suggests that most people call it 
something else), and then, without showing that medium run lengths are 
unfairly biased, pretend that they are.

This was my simple proof for why you can't guarantee it's better (or 
even probably better):

>> If, as you claim, some keys are more likely than others, then imagine 
>> there exists the following one-to-one function:
>> f(x) = y, with both x and y in [0,2^72-1], such that P(k=f(x)) >= 
>> P(k=f(x+1)) for x in [0,2^72-2].
>> Imagine you know this function, so you start cracking. You increase x 
>> from 0 to 2^72-1, set y=f(x), and see if k = y. In this way, you 
>> search the more likely keys first.
>> Noq, Imagine I hypothetically work at RSA labs, and have produced a 
>> not-so-random y with the given function. But now, I solve x for f(x) 
>> = y. Then I set k=f(2^31-1-x). Thus, what was the most likely key is 
>> now the least likely key, what was the least likely key is now the 
>> most likely key.
>> So now your algorithm searches all the unlikely keys first, and 
>> searches the likely keys last, making it take longer (on average) to 
>> find the correct key. Except you think it's the other way around. And 
>> while you're searching the wrong keys, d.net has beaten you.

As for why it's worse, I just don't think the overheads are likely to 
be worth the bias, if any, of the random number generator.

Neither have you picked a random number generator, run it several 
thousand times, and showed that the run lengths are biased in your 
favour (and for that matter, picked several more random number 
generators, to show that "most" of them are biased).

There are very many ways to generate 'secure' (very hard for someone 
else to guess) random numbers without additional hardware. They are 
somewhat based on the simple radioactive decay method, which is roughly 
"Take two timings, compare them. for GT or LT, you can generate a 0 or 
1 bit. For =, you do it again. Alternatively, generate a 0 if it was 
even, 1 if it was odd (which is slightly less random)". There are a 
couple of reasonably trivial ones:
1. 'gaps' in the timebase (a PPC on-chip register increasing at, say, 
25 MHz).
2. Number of increments per second { t = time(NULL)+1; i=0; while 
(time(NULL) < t) {;} while (time(NULL) == t) {i++;} return i; }.

With number 2 (which is available on most platforms), we get (if we 
want it secure) 1 bit every 2 seconds. For all the known keys, 15 
minutes. Bad, but certainly doable.

- Purr

More information about the Hardware mailing list