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

jbass at dmsd.com jbass at dmsd.com
Mon Aug 16 06:13:49 EDT 2004


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"?

>From Websters:

	An opinion, or judgment, formed on defective or presumptive
	   evidence; probable inference; surmise; guess; suspicion.

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.

SO ... you said:

> "Some very significant parts of the key space may have very very low
> probablities" is completely unfounded. Each key has an equal
> probability, which I shall prove below. Choosing a search order other
> than completely random does not decrease the effort of finding the
> correct key. Also, what do you mean by "several choices in key sequence
> generation can impact inner loop performance/work"? Checking each key
> requires a fixed amount of effort.
> 
> If each bit is random (P(bit n is set) = 1/2) and independent of other
> bits (P(n|m) = 1/2), then we can multiply the probabilities together,
> so P(key is x) = 1/2^72 for x in [0,2^72). That is, ALL KEYS ARE
> EQUALLY LIKELY.
> 
> Since you're not a math head, I'll translate: If every bit is
> completely random (therefore independent of other bits), then the
> chance of a bit being set is 1/2. So the chance of any key x being the
> key k is 1/2^72. Please don't talk about "probabilistic number theory"
> without any knowledge; this is A-level statistics, which I learned at
> 15.

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?

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).

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

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.

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.

>   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.

John


More information about the Hardware mailing list