From: doug@netcom.com (Doug Merritt)
Date: Tue, 12 Oct 93 19:29:57 PDT
To: cypherpunks@toad.com
Subject: Re: Breaking DES
In-Reply-To: <pmetzger@lehman.com>
Message-ID: <9310130229.AA09377@netcom5.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


> pmetzger@lehman.com said:
>(2^56)*8 = 576,460,752,303,423,488
>
>(2^56)*8*1000/(10^9) = 576,460,752,303

I was originally assuming a one byte result per calculation and gave a
hashing justification. (I glossed over the overhead for this approach,
but we could analyze this, too, if anyone's interested.) You however are
multiplying by 8 for no clear reason. Feel free to explain, but the way I see
it, the calculation is:

(2^56 calculations) * (1 byte per) * ($1000/disk) / (10^9 bytes/disk)

...which comes to 72 billion dollars. This is significantly larger than
my first calculation, and the difference is purely due to roundoff error,
because I said that 2^56 = 10^16, where it's actually 10^16.8576.

10^16 * $1000 / 10^9 does indeed equal my original figure of $10 billion,
so it's just that I should have left another digit of precision in rounding
the exponent.

Now I agree that 72 billion dollars is a lot. Even 10 billion is a lot.
But all I was trying to establish was that these numbers are not *completely*
impossible, because you were giving Karl a hard time about this.

Ridiculously expensive is a very different thing than *impossible*.
There are schemes that result in figures like 10^9 billion dollars...
*that* I call plainly impossible.

I also projected forward 10 years to let prices come down by a factor
of 10...that's another way of underscoring *possibility*. Over the
last 10 years disk drive prices have fallen significantly more than
a factor of 10 per megabyte, so I am being quite cautious here. A
factor of 30 is justifiable, but I won't go that far, I'll continue
to be conservative.

Even your own figure of $576 billion becomes $57.6 billion in 10 years,
which is merely too expensive, not *impossible*...if WW III were underway
and such a project were of critical importance, it would happen...
$50 billion would not be too much under *those* circumstances. That's
the difference between "impossible" and "expensive".

>Lets think for a moment, shall we? You are encrypting every possible
>block with DES, which results in lots of random blocks. You really
>want to search through the lot of them serially without any indexing
>whatsoever? Seems like you haven't thought this out.

If you want to critique this part of my back-of-the-envelope, its
weakest part is the sorting, in which it is very hard to effectively
serialize disk access.

For the benefit of the doubt, let's give that a factor of 100 slowdown...
so that 10 years from now we have an *average* disk transfer rate of 10^7
bytes per second for this algorithm rather than the 10^9 that I was assuming.
I think it could be done faster, but even so, this increases the time from 1
hour to 4 days...still not an impossibility, just not as *nice* as 1 hour.

Again, I need only establish possibility for the algorithm Karl related;
I'm not saying the NSA *will* do this.

>Oh, now I just realized -- you are going to have to store each source
>block with each output block. That means that even if you don't do any
>indexing, you are going to need twice the disk space I just mentioned,
>or over $1 TRILLION in disk for a very slow DES cracker.

Ok, so figures are doubled...my 72 billion becomes 144 billion. Pretty
expensive. Not *impossible*.

>Sorry, but you lose.

I never claimed this was likely...all I was after was to see whether it
worked out to e.g. 10^9 trillion dollars...*that* I would call impossible.

>Never designed a disk system, have you?

Actually, yes I have; I've been a hardware and software systems architect
in all kinds of different subspecialties. The fact that we may disagree
doesn't make me an idiot...hell, I may even make drastic mistakes and say
things that *are* idiotic. It still doesn't make me an idiot...it would
make me "someone who made a mistake".

Considering that I was doing a quickie back-of-the-envelope, I'm not even
embarassed about such mistakes.  No one else did an estimate. 2^56 *sounds*
ridiculously huge; I'm content to be within a factor of 100 in showing that
it is merely quite expensive. I daresay that you yourself have a better
feel for the expense now than you did when you first critiqued Karl's post.

Flaming me is a poor way to win an inherently technical argument. Stick to
the point.

>Sorry, but you can't actually
>read a disk as fast as you can read RAM. Caching only works if you
>have frequently accessed blocks -- if you are reading a whole disk you
>can't go faster than the disk transfer rate no matter how many gods
>you pray to. Your technical credibility is rapidly plunging.

It is true that you can't do better than the average transfer rate,
and here you have a valid point, I neglected this. It would be unrealistic
given the other assumptions to assume better than 10^7 bytes per second
transfer rate with technology 10 years hence. In fact even 100 megabytes
per second might seem high to you, so let's call it 50Mb/s (surely a
very conservative figure), for a total of 20 times slower than I estimated.

That increases the 4 days to 80 days. Not very nice...but *possible*.

You see the pattern here...you are raising valid technical objections, 
a whole series of good points that I glossed over with my back-of-the-
envelope calculations.

But even so, it doesn't change my basic point that the approach is *possible*.
You need to find a factor of perhaps 1000 in cost and a factor of perhaps
1000 in time in order to demonstrate that this approach is inherently
*impossible*.

The fact that you spot flaws in my back-of-the-envelope also doesn't mean
that it's called for to flame me. Again, let's stick to technical discussion.

>Guess you can't read my calculations, can you?

Tsk, another flame.

>> Skip the sarcasm and pick a different quantity discount. If you don't
>> like my 90% discount for quantity 1 million disk drives, pick another
>> one.
>
>Sort of like saying "if you don't like the laws of physics, pick
>different laws"? 

Even for a flame, I don't get this. I said, if you think that a 90%
discount for quantity-million is unrealistic, tell me what discount
you think *is* realistic. That's a valid question. The $1000 per
gigabyte drive is roughly accurate *today* in quantity *one*. The
higher the quantity you buy, the better a discount you get; that's the
way it works, and I'm sure you know that as well as I. So perhaps my
90% discount is overly optimistic...fine, I say...tell me a different
figure. If you say 10% I'll argue. Anything between 10% and 90% is
conceivable, so pick your figure.

It still doesn't affect the bottom line argument as to whether the algorithm
Karl mentioned will be possible in 10 years. It clearly would be very very
expensive. It would also clearly *not* be completely impossible.

Karl posted something which is theoretically reasonable but that is
nontrivally expensive even ten years from now. He deserves credit for
discussing a theoretical possibility which is even marginally conceivable.
He does not deserve a harsh response...and I think you *were* harsh to
him.

Do me a favor and skip the flames in your future responses; they're not
very much fun.
	Doug
--
Doug Merritt				doug@netcom.com
Professional Wild-eyed Visionary	Member, Crusaders for a Better Tomorrow
     (The above is a joke; the following are mailing lists:)
Unicode Novis Cypherpunks Gutenberg Wavelets Conlang Logli Alife HC_III
Computational linguistics Fundamental physics Cogsci SF GA VR CASE TLAs