Dead Bovine RC5??

[Eric Cordian]

The Bovine RC5 project on distributed.net has so far checked 86.742% of
the keyspace in 1,772 days, without finding the key.

Assuming that all values of the key are equally likely, it is perhaps time
to start thinking about the entertaining prospect that the entire keyspace
will be exhausted without a key being found.

This could happen if there were a bug in the client, a bug in the server,
or if people were spoofing blocks to the server, reporting them as
failures without having actually searched them for the key.

Let's let "eps" in [0,1] be the probability that something is screwed up
in the project which prevents the key from being located.  Let C in [0,1]
be the percentage of the keyspace that has been searched so far, and let F
in [0,1] be the probability that the project is F---ed, which we define as
the project continuing to completion without finding a key.

Obviously 1-eps is the probability that the software will find a key
somewhere, and after searching a C fraction of the keyspace, C*(1-eps) is
the probability that we will have declared victory and gone home, and
(1-C)*(1-eps)+eps is the probability that we are still chugging along.

Ergo, the probability that we will complete without finding a key, over
the probability that we are still in business after searching the fraction
C, becomes after some minor algebraic tweeking...

              F = eps/(1-C*(1-eps))

Let's look at this function for various degrees of completion of the
search, and various probabilities that the software is broken.

For eps = .01, a 1 in 100 chance that the software doesn't work, the
chances that the project is F---ed rachets up in the following manner as
more and more keyspace is searched without a successful conclusion.

                   % Searched     F---ed?
                   ----------     -------
                       86.742      7.0794
                       90          9.1743
                       95         16.807
                       99         50.251
                       99.9       90.992
                       99.99      99.02
                       99.999     99.901

After 99% of the keyspace is searched without finding a key, there is
about a 50-50 chance no key will be found, and if 99.9% of the keyspace is
searched with no key, we may say with 90% confidence that the project will
not end successfully.

For eps = .001, a 1 in 1000 chance that some horrible bug or vindictive
hacker has made an appearance, the table looks like this.

                   % Searched     F---ed?
                   ----------     -------
                       86.742     0.74936
                       90         0.99108
                       95         1.9627
                       99         9.0992
                       99.9      50.025
                       99.99     90.917
                       99.999    99.011

Now, we have to search 99.9% of the keyspace before we have a 50-50 chance
no key will be found at all, and 99.99% before we know that fact with 90%
confidence.

And providing the project checked their code with sufficient sloppiness
that there is a 1 in 10 chance all the CPU spent so far has been wasted,
we have the following table.

                   % Searched     F---ed?
                   ----------     -------
                       86.742      45.595
                       90          52.632
                       95          68.966
                       99          91.743
                       99.9        99.108
                       99.99       99.91
                       99.999      99.991

Here we see they are almost to the point aleady where they are as likely
as not to fail, but we will still need 99% of the keyspace to be searched,
to be able to state that with over 90% confidence.

For a piece of software a complex as the RC5 client, and associated
keyblock server, I think 99% confidence that the software does not have a
major undiscovered bug is a comfortable upper bound.  This means that
there is less than a 10% chance that the project is screwed now, but
things will start to get interesting once we get into the high 90's in
terms of percentage keyspace search, if the key has still not been
located.

I'm sure we'll all be watching with breathless anticipation as the
remaining keyspace is exhausted over the next few months.

-- 
Eric Michael Cordian 0+
O:.T:.O:. Mathematical Munitions Division
"Do What Thou Wilt Shall Be The Whole Of The Law"