[RC5] Re: rc5-digest V1 #225 (LONG reply)

Greg Delisle gdelisle at indiana.edu
Tue Jul 28 16:26:11 EDT 1998


Wow! I'm really glad that I've started up this discussion (so much more
interesting than the wonky K5 vs. PII stuff), and I'd hate to see it stop
here, even though no one has yet to support me :) -- really, you all make
some good points, quite a few, and I don't want you to feel like I'm a pain
in the ass, but in the interest of playing Devil's advocate, I'm going to
try to reply to as much of the digest as possible, quoting as efficiently
as I can. Here goes.

At 11:44 AM -0500 on 7/28/98, rc5-digest wrote:

> From: gindrup at okway.okstate.edu
> Subject: Re: [RC5] [RC5-Mac] the DEATH of d.net?
>      So, has there been a benefit from maintaining this presence on the
>      clients?  Yes.  D.Net is vastly outperforming Moore's Law.  You
>      state a version of this law, but don't do the obvious comparison.
[snip]
This is true. I'd like to come back to this later, though.

>         You suggest abandoning D.Net and joining another effort.
[snip]
Not really. What I suggested was *finding* another effort, that is,
creating an all-new project that seems very timely and relevant not only to
those of us in the effort, but to those who are not. I don't think such a
project exists yet.

>         D.Net originally had tons of independent motives for joining the
>      effort:
[snip]
>      Are all the reasons currently obviated?  I don't think so.  And now,
>      there are more reasons
[snip]
>      None of these reasons is currently pointless or redundant.
[snip]
True again, but none of them seems very compelling either. One thing I
noticed about the EFF's press release was that they not only claimed
victory, but tried very hard to show how this victory was relevant to
everyone in the world, which it is. I'd like to have that sort of relevancy
as well. Yes, we were both working on the same project, but Deep Crack's
urgency is that this machine can be re-created, in secret, by "anyone,"
whereas distributed.net cannot.

>         You mention a few applications to be run on Jini nd I had to
>      chuckle a little.  One of the reasons that encryption is well-suited
[snip]
Really, I don't know a durned thing about Jini, only that it sounds like
distributed computing for the masses for "real" computing tasks like
spreadsheets and PDAs. I don't want to champion Jini, just point to it. If
not Jini, then the next thing, or the thing after that.

>         You say that the speed of D.Net is being challenged by Deep
>      Crack.  Just because the two power curves intersect currently does
>      not mean that Deep Crack can keep up.  If Deep Crack is to keep up
[snip]
>         Deep Crack was not faster than D.Net.  The D.Net peak speed had
>      not been reached, but at the end, was matching the average rate of
>      Deep Crack.  Further, if a smarter algorithm is used by D.Net, the
>      effective keyrate of D.Net will be much higher.  Remember also that
>      D.Net is using brute force while Deep Crack is being mildly more
>      subtle.  Don't think that this minor spped-up is unavailable to us
>      as well.
[snip]
If Deep Crack was not faster than d.net, then how did it win? It beat us to
the finish line, therefore it is faster in the one way that counts. We
can't just say woulda-coulda-shoulda, we LOST, and we could lose again. The
algorithm does not exist in the d.net client and I don't see it coming. I
haven't heard any true solutions for the latency/ramp up problem. We may
eventually flop more teras than a hundred Intel Reds, but if we lose, we
are slower at the one task we have been designed to perform. Speed not in
mips or flops, but in time required to complete a goal.

[snip]
>         Further, there are *many* people who need encryption to do their
>      daily business.  RSA is an obvious candidate.  Banks are obvious
>      candidates.  These people need tha abilith to encrypt to do their
>      work.  They need good encryption and they need strong encryption.
>      If running the D.Net client on their machine can help them obtain
>      better encryption, then there is a good economic motive to do so.
[snip]
Two things. First, banks have all the encryption they currently need.
Triple-DES is to plain old DES as an ocean to a droplet. Secondly, I don't
see many banking teams in the distributed.net listings. The economic motive
here is equivalent to bending down to pick up a penny -- if the banks feel
they need stronger encryption for their transactions, they know the most
efficient way to get it is to contribute more money to campaigns and call
for Congressional hearings. DES is not banking encryption.

>         Next, you mention some other distributed contests to join in lieu
>      of D.Net.  I have something to say about almost all of them.  Almost
[snip]
Actually, I didn't. That must have been someone else, so I'll let them
answer you. I will say, though, that I agree that unless you're a
mathematician, there are no other compelling projects. I, for one, would
gladly join SETI if they would get out a client.

>      Finally, you mention the waste of running the client.  What waste?
>      The *whole idea* is that this is time that would otherwise be
>      wasted.  DCTI is not asking anyone to leave their machines on any
>      more than usual.  They aren't asking people to do less work on their
[snip]
You're absolutely right, of course. I've started turning off my cracking
machines at night, like they were before I started cracking on them. That
will cause some infinitesimal dip in distributed.net, but I doubt anyone
will notice.

>      If we are trying to establish credentials based on our
>      participation...
No. I am absolutely not trying to do that. I was just trying to put a face
on my words and show that I'm someone who cares about d.net as much as
anyone, and that I was interested in seeing an honest and intelligent
discussion. So far, I am seeing exactly that.


> From: "A. J. Clark" <ajclark at usa.net>
> Subject: Re: [RC5] [RC5-Mac] the DEATH of d.net?

> How does this cause us to be outpaced?  Not only does Moore's Law apply
> to the D.Net machines (we'd have at -least- the average number of people
> upgrading their equipment or purchasing new, faster equipment), but a
> lot of the older machines are kept around as well to do nothing more
> than crack blocks.  Where the machine might become useless for running
> Lose2000, it can still crack blocks.

Perhaps my perception of the d.net "farms" is wrong. I thought that major
contributions, especially corporate ones, come from background clients in
large labs of slow(ish) terminals, DOS machines, Pentium 100s, 486s, etc.
When a lab is upgraded, the old machines go in the garbage, because they
take up space and no longer produce a net return on investment. If they are
not upgraded, they age in place and thus do not get any faster.


> So we have the old machines in ADDITION to Moore's Law recipients, the
> upgrades and the new machines.  Seems to work in our advantage, IMHO.
[me]
> I don't understand your point here - why won't the existing processor
> base upgrade?  I'd bet that D.Net has more technophiles on it than
> average who are upgrading and/or getting new machines.  I could be
> wrong, but I'd like to see some numbers that suggest D.Net machines are
> being upgraded LESS than any national average.

I have no numbers at all. Perhaps technophiles like you and me will get a
new computer this year for the home, but technophiles that run large labs
are at the mercy of their superiors as far as upgrades. The existing
processor base will only UPGRADE as old machines are sent to the landfill
with new ones to replace them. Increasing the processor base is not the
same as upgrading it. Of course, depending on how you look at it,
increasing may be better than upgrading.

> I doubt that D.Net will shrink any time in the near future, unless D.Net
> manages to foul things up on a grand scale, since people like myself are
> interested in helping get the distributed processing power as large as
> possible.  I'm always trying to recruit more people and machines into
> the effort, as I hope it will have a pyramid effect of sorts.  I believe
> that others must be doing it as well, otherwise d.net would not be
> growing.

Absolutely. The only remaining question is: how long will distributed.net
continue to grow at such a rate? As I said, it is my completely unsupported
opinion that we will approach saturation sooner rather than later unless we
come up with a project that more people can give a damn about.


> Regardless, Moore's Law doesn't apply to how many machines we have in
> the effort, it has to do with the growth rate of technology.  Trying to
> say that the growing rate of technology doesn't affect D.Net, or doesn't
> affect it to the degree it affects "other people", is like saying that
> cracking RC5-64 is impossible.

No, it's not "like saying" that at all. RC5-64 is a mathematical certainty.
There is a key, and eventually it will be found. The question(s) I've been
trying to raise are subjective ones, which have few definite answers. D.net
doesn't grow by itself, it grows because people choose to join it. If they
stop choosing to join, or choose to leave in greater numbers, or both, then
we have a major problem. If I'm wrong, I'm wrong, no problem, and
everything's fine.

> From: Jeff Woods <jwoods at delta.com>
> Subject: Re: [RC5] [RC5-Mac] the DEATH of d.net?

> Collectively, yes.   Individually, no.  How much EXTRA did it cost you to
> add your computer to d.net?   The NET cost of d.net is actually ZERO or
> very close to it, since relatively few computers were purchased for the
> SOLE purpose of running them for d.net.   Yes, some of us run our older
> machines as nothing BUT d.net crackers, but they weren't BOUGHT for that
> purpose.... they're just getting a little extra useful life....

True, but the point of Deep Crack is that the design can be replicated for
roughly the same money. Distributed.net cannot be replicated, unless you
have a few spare years and several dozen committed individuals, etc. The
point of the Deep Crack attack was that the government has long said that
DES encryption was good enough for most uses. EFF has demonstrated that
anyone with $250,000 and an unscrupulous mind can decrypt anything, for any
motive, whenever they want, and so DES is not nearly "good enough" for
anything. Distributed.net's efforts prove little in the political arena; we
cracked RC5-56, but did government policy change at all? No, even the FBI
is still whining about key escrow, and why? Because they need it to fight
crime. No, all they need is Deep Crack. In fact, the EFF project heavily
implies that the government has probably had similar machines for a long,
long time. I think I just got off topic there. Sorry.

> Absolutely.   Yes, RC5 is less susceptible to hardware cracking (twelve
> rounds of rotation/encryption, plus longer keys), but we need to prove that
> even 64-bit keys are insufficient, as opposed to DES's 40.   We need tokeep
> on RC5-64 to make this point, that even the tougher RC5 encryption is
> inadequate without a sufficiently long key.

We have already proved that RC5-56 is insufficient, but have we "made the
point?" That is, has anything or anyone changed because of our efforts?


[snip]
> >Yes, we are nearly as fast -- but who got the headlines? :)
>
> THIS time.

No, this time and every time. Deep Crack has shown us two deep, fundamental
flaws in our effort -- lack of an algorithm and a slow ramp-up time. We may
get the key first next time, but if we do it without addressing these
problems, we are being somewhat lazy on the scientific end. We have been
shown our flaws, and we should fix them. I'd volunteer to help, but I can't
program.

> I tried to address this a few days ago, got a resounding THUD....   We need
> to make sure that in the days leading up to DES-II-3, that all RC5 buffers
> on permanently connected machines or machines to personal proxys are set to
> 1:1, and that proxys don't cache keys very deep.   We need 75% switchover
> within the HOUR the data is posted to have any chance.  To do that, we need
> SHORT buffers on RC5 machines, so that they finish the one block they have,
> and then download another, getting a large chunbk of DES blocks in return.

This might help a lot. But to jump to a new question, what about when
distributed computing, in general, is used in an area where this sort of
close, hands-on supervision is impractical? What if I just discovered a
problem now, and I need an answer later today?

> Please explain this.    Branch all you want, but unless you've found a
> weakness in DES itself (and I don't recall any claim that they had -- Deep
> Crack is still just a brute force cracker AFAIK), they're statistically
> likely to find the key at exactly the midpoint, no sooner or later,
> regardless of how they "branch".

I can only refer you to the articles I read in Wired News, news.com and
other sources who mentioned the branching algorithm. Apparently it was not
a strictly brute force attack, it was an intelligent attack applied with
brute force.

> From: "dan carter" <motion at es.co.nz>
> Subject: Re: [RC5] [RC5-Mac] the DEATH of d.net?

> Todays *old* machines are 386es and 486es, todays new recruits are
> 586es and 686es.
[heinous snip]
> So not only is my new machine upgraded from 686->886, but my old
> machine is upgraded too (486->686)

Eventually, these old machines will clutter up the place and head for
recycling. Computers, by and large, do not stay in use forever, precisely
because Moore's Law gives them a greatly diminishing margin of use. As
computers and computing grow more and more commodified, computing will
eventually become free, and then disposable. I can only have so many
computers in my life before I start to toss them. This may seem like a
distant future for individuals, but for corporations and research
institutions, it's been that way for a while.

> This means the the rest of your conclusions do not hold, because they
> rely on an assumption that the distributed.net mass will grow slower
> than moores law.

It *is* an assumption, and I don't think you've disproven it because you
haven't addressed the sociological concerns that are my point.
Distributed.net will only grow as long as it can motivate people to join
it.

Folks, my point about Moore's Law was addressed specifically to the Deep
Crack-type machine. Distributed.net can leverage Moore's Law, but the
reason we have outgrown the Law by such a vast amount has *nothing whatever
to do with technology.* PEOPLE have grown d.net, and if the people leave,
d.net will shrink, and THAT is our problem. D.net must grow at the same
rate it is growing at now. That is a people problem, and people do not
increase their participation according to Moore's Law or any other law.

> >our acceleration
> >will be linear at best, while Moore's Law will continue to help the
> >competition at a faster rate than it helps us.
> Nope.
"Nope"? Argh, curses! You have refuted me! Seriously, please be specific.

> True, but the competitions get harder 56bit->64bit->72bit etc.
> This is has a reversing effect, giving us more time to catch up to Deep
> Cracks intial lead.

Actually, DES-II-3 is exactly the same size as DES-II-2. RC5 gets larger,
but unless I'm really misunderstanding things, DES is 56 bits and will stay
that way.
[snip]

Thank you all very much for your patience.

-Greg Delisle
Indiana University Press Journals
http://www.indiana.edu/~iupress/journals/


--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list