Expected date of solution

Rocke Verser (rcv@dopey.verser.frii.com)
Fri, 6 Jun 1997 12:34:12 -0600


-----BEGIN PGP SIGNED MESSAGE-----

RSA DES Challenge Time-Of-Completion estimate
- ---------------------------------------------

Produced 12:00 MDT 06/06/97

Introduction:

Many people have observed that DESCHALL's "time to 50% completion"
published in the statistics Web pages is rapidly becoming a
meaningless statistic.

A more accurate measure is the expected date of solution.

Noting that SolNet and SGI are major players in the RSA DES Challenge,
I've developed a model that accounts for DESCHALL, SolNet, and SGI
as the only three major players in the RSA DES Challenge.

[There are other teams participating in other RSA Challenges, but
I am not aware of any other major players undertaking the RSA DES
Challenge, privately.]

Given the "factual data" and the "assumptions" below, the "results"
of this model are believed (not guaranteed) to be mathematically
correct to within 1 day and to within 2 percentage points.

Factual data:

Recent DESCHALL keyrate: 4.125 billion keys per second
Recent SolNet keyrate: 2.125 billion keys per second
Recent SGI keyrate: 2.890 billion keys per second

DESCHALL keyspace complete: 16.503%
Solnet keyspace complete: 10.0896%
SGI keyspace complete: 19.573%

Assumptions:

DESCHALL, SolNet, and SGI are working independently.

Each group's keyspace rate remains constant at the levels shown above.

Nobody else on the planet is working on the RSA DES Challenge.

Results:

Expected date of solution: 56 days from now.

Probability that a DESCHALL client will find the key: 51%
Probability that a SolNet client will find the key: 18%
Probability that a SGI client will find the key: 31%

Notes:

These results are highly sensitive to each group's keyspace rates
(billions of keys per second).

If each group doubled our keyspace rates every 28 days, the "expected
date of solution" would be 31 days from now.

Giving SolNet an instant 30% increase in keyspace rate, while
holding DESCHALL's and SGI's rate constant would shorten the "expected
date of solution" to 53 days and changes the probabilities of each
group finding the key to 48/24/29 (DESCHALL/SolNet/SGI).

Giving SGI an instant 30% increase in keyspace rate, while
holding DESCHALL and SolNet's rate constant would shorten the "expected
date of solution" to 51 days and changes the probabilities of each
group finding the key to 44/16/40 (DESCHALL/SolNet/SGI).

Giving DESCHALL in instant 30% increase in keyspace rate, while
holding SolNet's and SGI's rate constant would shorten the "expected
date of solution" to 47 days and changes the probabilities of each
group finding the key to 60/15/25 (DESCHALL/SolNet/SGI).

Other observations:

Keyspace searched by just 1 group: 33.4%
Keyspace searched by exactly 2 groups: 5.9%
Keyspace searched by all 3 groups: 0.3%
Total Keyspace Searched 39.6%

If all 3 groups combined forces and fully cooperated, the "expected
date of solution" would be 28 days from now.

If all 3 groups combined forces and fully cooperated, and if the
combined effort doubled every 28 days, the "expected date of solution"
would be 20 days from now.

- -- Rocke Verser
- -- PGP Fingerprint PGP ID = 1025/00000001
- -- EE 73 A9 78 60 9C BA CA DF FC 68 37 CD 73 F3 96

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBM5hXIXI7TKUAAAABAQGgiQP/UMJLuyv6q5OawQMDjTwTmTylk/miLqHp
lyChxVAByjgbYrH4LgAk9pI0VDYQ6g4Dlt+X2zNejmi/yDtP/v0YlLrCH9pvNNi7
J5AfWm10A4jSSrJ1oc4VsQWDcooQQKvvLlTKHAM7k/Yh8Sw1Ygo7Lny5v+u9NyTC
13uqtXevLOY=
=BbGp
-----END PGP SIGNATURE-----