Re: SSL trouble

>>   Please don't do anything like this.  This will prevent
>> people like me who prefer the "random" method from
>> participating.

> You can't use the random method if the CRACK is using a
> sequential search. It just doesn't fit!

  Hehe...  I've always been a bit of a misfit.

> You can't ACK something which has not been allocated to you.

  But I could announce it on the list.

> However, if a CRACK were to be using random, the above would
> be useful as a "progress report" as the rate of reports
> indicates how well the search is going.

  I don't want to make progress reports.

> It would also allow more equal sharing out of the prize money,
> as on average 2**15 "possible" keys would be found, and the
> first finder of each would receive a fraction of the prize.

  Well, if someone starts talking real money, I might change my
tune.


Will French  <wfrench@interport.net>

Will French writes
>>>   Please don't do anything like this.  This will prevent
>>> people like me who prefer the "random" method from
>>> participating.
>
>> You can't use the random method if the CRACK is using a
>> sequential search. It just doesn't fit!
>
>  Hehe...  I've always been a bit of a misfit.
>
>> You can't ACK something which has not been allocated to you.
>
>  But I could announce it on the list.

Then what do you care about the group's procedures?  It doesn't
"prevent you from participating" --- you *aren't* participating.
You're attempting to solve the problem on your own.

Statistically, the "random" methods are no different than everyone just
working independently at solving the problem.

I, too, don't recall my statistics well enough, but let me take a shot
at it, and anyone who wants to, please check me...

The probability of having failed to search a particular segment (the
one with the key) after selecting k of n segments at random with
replacement is (1-1/n)^k, whereas in a sequential search from a random
starting point, (or, equivalently, random without replacement) the
probability is k/n.

Assume the segments are farmed out in 2^24 segments of 2^16 keys each
(I don't recall what the current programs use).  In the sequential case,
it's even money you'll find the key after searching 8,388,609
segments.  In the random case, it's not even money until 11,629,080
segments --- 39% longer.  It's when you're "unlucky" that the random
case gets *much* worse.  To search 90% of the keyspace takes 15,099,495
sequential searches, but 38,630,967 --- a 156% difference.

Here's the table:

% k-space	  random	sequential	percent
searched	  method	  method	difference
--------	----------	---------	----
10		   1767657	  1677722	  5
25		   4826505	  4194305	 15
50		  11629080	  8388609	 39
75		  23258160	 12582913	 85
90		  38630967	 15099495	156
99		  77261933	 16609444	365
99.9		 115892899	 16760439	591

Changing the segment size doesn't affect the results very much, as
a table for 10 bit segments shows:

50		 744261117	536870912	 37
90		2472381916	966367641	156

The random method is a little more than 1/3 worse in the typical
case, but *lots* worse in the worst cases.

Will French <wfrench@interport.net> writes:
>   Well, if someone starts talking real money, I might change my
> tune.

We are talking real money, the guy who hit the key will shortly be
getting c$ 442.30 (DigiCash c$), the amount of c$ donated for the 2nd
challenge on this page:

	http://dcs.ex.ac.uk/~aba/sslprize.html

Now collecting donations for the 3rd challenge which I guess Piete
will be hoping to do in the next few weeks, after a few software
improvements have been made.

You can buy US$ with these on the unofficial digicash exchange:

	http://www.c2.org/~mark/ecash/ecash.html

The current exchange rate is around 100 c$ = 5 US$, so that's ~22 US$,
not a huge prize, but all it needs is more donors to get a bigger
prize fund, if you want to join in to make the prize fund bigger, sign
up for the digicash trial (you get 100 c$ free):

	http://www.digicash.com/ecash/

and buy some c$ on the unofficial exchange.

Adam