At 04:23 PM 01/11/2003 -0800, Tim May wrote:
On Saturday, January 11, 2003, at 03:47 PM, Bill Stewart wrote:
....
- A distributed computing like this needs several parts:
- A problem to solve - they seem to keep waffling on this;
their FAQ really needs to be upfront about it,
but it only talks about RSA-576, while their forum
says they are or aren't also doing something with X-Box,
depending on their legal worries, but doesn't say what
they're trying to do to it (Cracking a 2048-bit RSA key
certainly isn't a rational problem to solve,
but maybe they're trying to crack something else about it,
like a passphrase used for a key file?)
If neither is solvable in the lifetime of the earth, does it matter which
one they claim to be working on?
RSA-576 is certainly crackable in a reasonable lifetime,
though not likely by these guys. RSA expects it to be done in a year or so.
2048-bit RSA obviously isn't factorable with current mathematics
unless somebody can build a high-resolution quantum computer.
Cracking a 128-bit-entropy passphrase with a 128-or-more-bit algorithm
is not realistic, but cracking a human-chosen passphrase
might or might not be, depending on the competence of the human,
and they're talking about Microsoft here.
(I suppose I should try running pgpcrack on my _own_ passphrases :-)
It's unlikely they'd have such a file unless somebody
leaked it out of Microsoft or put it into the Xbox's code for some reason,
but you never know.
- Some way to hand out work and collect results,
and it's possible that they've done this well,
though I doubt they scale to seti.org sizes.
Although, as simple calculations show (reported here several times
over the past decade), random and overlapping self-apportionment of keyspace
to search is only a factor of 38% or so worse than more careful,
non-overlapping apportionment is. (And random apportionment stops
the attack where someone finds the solution, or knows where it is
and claims that portion of the keyspace to search,
and then doesn't announce a solution.)
That's true for symmetric-key algorithms, but not always for factoring.
Most of the high-end factoring programs work in two phases,
one of which looks for some kind of interesting intermediate result,
and a second phase which takes the intermediate results and crunches on them.
Random keyspace self-apportionment may work well for the first phase,
but for at least some of the recent major algorithms,
the second phase has usually been run on some big computer or cluster
by the people running the project because it required too much RAM
for the vast majority of desktop PCs.
One of the most frustrating things about the Neo Project's web site
was that it's got one forum comment that suggests that they may have
found an efficient way to distribute the second-phase calculations,
but there's no pointer to any way to find out the mathematical work,
if any, to tell if they really meant that or were correct about it.
