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

Elektron elektron_rc5 at yahoo.ca
Mon Aug 16 13:35:34 EDT 2004


> 	And you have not yet found a way to calculate your search order in a
> 	reasonable number of cycles. 144 cycles is far too many. Write the
> 	code, and someone may implement it. That is the d.net way.
>
> pre-computed 16 bit segments, sorted, and table indirect .. cycle or 
> two
> to fetch from cache on a typical cpu, stored in FPGA block ram as ROM, 
> nearly
> free in cost. So claiming a huge overhead without thinking about 
> better ways
> to implement the function is just how clueless?

What about the bits in between? Moving 16-bit segments? At least 5 
loads are required, adding 5 cycles to 300, or about 2%. 2% is a hell 
of a lot when you're talking about a 2^72 keyspace.

> I don't need to defend jack for expressing a preferrence that you 
> turned into
> a personal attack claiming absolute fore knowledge, and appear unable 
> to defend
> your assertions on the grounds that YOU don't know JACK about the 
> deterministic
> algorithms used to generate the keys for the challenge that you assert 
> are pure
> random in your not so professional attacks. So get off your hobby 
> horse, and
> start acting like a grownup.

Sure, rand() is flawed. random() isn't so flawed, and there are plenty 
of better random number generators too. Like RC5.

> So drop it OK ... this is not the forum for asserting you are GOD and 
> calling
> everyone else clueless shitheads for doing something you don't like or 
> approve
> of.

I may be argumentative, but at least I am civil.

> Elektron <elektron_rc5 at yahoo.ca> writes:
>> How can I prove something about an algorithm I don't know about?
>>
>> I'm not sure if you can prove that a given hash is 'strong'. As far as
>> I know, it's only possible to prove that the hash is weak.
>
> That has been my point all along ... that I do know enough about the 
> math
> to know that you can not claim with absolute certainty that the RSA 
> functions
> used to generate the contest keys are in fact free of nth order 
> artifacts, and
> are in fact perfectly random. We know by definition that all computer 
> generated
> pseudo random sequences are in fact deterministic functions.
>
> So I have a perfectly reasonable conjecture, based solely on personal 
> observation
> that there might be a bias in the key length bit run lengths. Even in 
> math, it's
> acceptable practice to form conjectures, and freely examine the 
> possibilities that
> they are true or not. Is that not the definition of "conjecture"?

No. In math, a conjecture is something that you suspect to be true 
based on some sort of evidence, but has not been proven ("any even 
integer greater than 2 can be expressed as the sum of two primes", 
IIRC). You have made a conjecture about a set of bits on RSA's website, 
which probably come from a function you know nothing about, whose input 
you know nothing about, and may as well have come from the spin of an 
electron somewhere. The function may be deterministic. The input 
probably isn't, at least in the realm of math.

There appears to be bias in OSX's /dev/random (the variance is greater 
than what it should be), but it's questionable as to whether you could 
make use of this. Perhaps it would result in more small run lengths 
than usual. Perhaps it would result in more large run lengths than 
usual. Perhaps it produces slightly more dictionary words than usual. 
Perhaps it decodes messages from aliens.

> I carefully said "may" when I proposed this ... I did not say that it 
> was true
> for certain, just that I suspect it might be lacking a formal proof 
> based on
> extensive foreknowedge of the algorithms and processes that had been 
> used. In
> looking at the contest keys, none appear to have significant run 
> lengths, which
> is not suprising, as they are rare anyway.

Paraphrased: The contest keys are about as random as you'd expect.

Combined with your original argument, you also say, paraphrased, "We 
would save 30 years by not searching keys which make an insignificant 
portion of the keyspace".

> and make the claim that this conjecture is "completely unfounded". You
> then attempt to "prove something about an algorithm I don't know 
> about".
> Which when pushed to defend your unsubstantiated claims, you then 
> claim:
>
> 	"How can I prove something about an algorithm I don't know about?"
>
> If that is truely the case, then where is this magic proof you claim?

There is no 'proof' in cryptography (except proving that it's weak). 
There is only tons of analysis. But if, as you claim, certain run 
lengths are preferred by the hash algorithm, you should be able to show 
that with a hypothesis test. Feel free.

I'm not sure if you could produce a convincing hypothesis from RSA's 
website.

> Certainly the proof you offer can not be proven to apply ... and in 
> fact
> you go on to admit that you can not prove that the key hash is in fact
> strong (IE free of artifacts).

Neither have you given any evidence that hash is weak, or produces an 
n-bit result with biased run lengths. After your table of run lengths, 
you give this argument:

> Given
> that most crypto algorithms are designed to produce what appears to be
> a random uniform bit field for keys and encrypted data, probability
> theory would suggest searching the key space in the order of the most
> probable bit run lengths in the key space. In this case, I believe
> searching keys with one or two maximum run lengths of 5, then 6 (either
> zeros or ones), is the most probable place to find a solution, then 
> work
> out from there. This generally suggests that checking keys with a run
> of 30 zeros or ones may be spending effort checking a very unlikely 
> key.

30-run keys compose a very unlikely keyspace. This is also a very small 
keyspace, and cost almost nothing to check (in fact, they cost more to 
avoid). You seem to believe that hashes are designed to produce output 
that 'looks random', as opposed to being as random as possible. I'm 
quite sure that this is not the case. Random number generators are 
designed to preserve entropy.

You're argument is analogous to "random password generators are 
designed to make passwords that look random, so they'll never produce 
dictionary words". A truly random password generator would have a small 
probability of producing dictionary words, equal to the proportion of 
dictionary words in the possible password space generated. And surely, 
you'd want the generator to be as random as possible. You wouldn't 
design a random password generator to specifically avoid dictionary 
words.

> If that is truely the case, then where is this magic proof that my
> conjecture is "completely unfounded"?

You have not looked at the keys, and showed that runs in the keyspace 
are biased, except with subjective conclusions.

> I am not a math head, but I am also not clueless ... or you would not
> be staring at your own words, which in fact form an absolutely useless
> proof for your unfounded assertions about what was just conjecture in
> the first place, regarding the keys that we face in this challenge.

I don't see what's unfounded about "all keys are equally likely". It 
may not be entirely true, but without further evidence, it's the least 
biased assertion.

Given that, in 1997, there existed perfectly good ways to produce 
random bits (radioactive decay timings), I don't think they would 
simply use a flawed algorithm and be happy with it.

> So ... as you said "If each bit is random", and my conjecture is that
> they might not be, then your proof would make sense. But the truth is
> that when you started this personal attack you are unable to defend 
> that
> the algorithms used, are in fact perfectly random. We both know that
> by definition, they are pseudo random, and very deterministic.

Radioactive decay may also be deterministic, on some quantum level, but 
it's still very hard to predict, especially since the keys were 
generated 7 years ago.

>>   I'm not sure if you can prove that a given hash is 'strong'. As far 
>> as
>>   I know, it's only possible to prove that the hash is weak.
>
> I at least have the sense to state the conjecture weakly with "may", 
> and
> offer it as pure conjecture. You continue to make the mistake of 
> asserting
> your undefendable position as infalliable fact. Maybe it's not fair 
> that I
> just know a little about the math involved, and have the sense not to
> claim to be some math GOD that conviently forgets how to construct a
> proper verifiable proof.

I don't claim to be a math god. I just doubt that RSA would happily use 
a flawed algorithm, after having designed a decent cipher. Your 
assertion is based entirely on "most crypto algorithms are designed to 
produce what appears to be a random uniform bit field".

 From what I've seen of MD5 and RC5, crypto algorithms are just designed 
to be hard to undo (without knowing the key, in the case of ciphers). 
All ciphers produce a random output for a random input, given a fixed 
key (easily proven). Hashes are designed more to preserve entropy than 
to produce results which "appear to be random".

I only claim that there's no point doing what you suggest if the keys 
are entirely random, and RSA would be smart enough to produce keys that 
are as close to 'entirely random' as possible.

I should make a random number generator out of tbjumps. It requires 
absolutely no external hardware (like something to measure the spin of 
a photon), and is as random as your mouse movements, and OSX's strange 
workings [1].

- Purr

[1] A lot of the things OSX does certainly appear to be senseless and 
otherwise, done entirely at random. =P



More information about the Hardware mailing list