CDR: Re: why should it be trusted?

[Tim May]

At 1:45 AM -0700 10/17/00, Kerry L. Bonin wrote:
>
>
>Rivest and Schneier's work factor discussions assume brute force or
>streamlined brute force such as GNFS.  These remain exponential in time.
>
>Now hypothesize the effect a new factoring or Feistel cipher attack would
>have on these tables.

Like Nathan Saper, you are now altering the thrust of your arguments. 
You wrote at length about ECL and SOS and gate arrays and all that 
crap, and I said they wouldn't make a hill of beans difference for an 
exptime problem.

("Well, what if you put a _lot_ of them together?" is the refrain I 
expect now.)

And I'm _quite_ aware of factoring algorithms and their importance! 
Several times I mentioned "absent factoring breakthroughs" and 
suchlike and I even went on to quote material on the best known 
factoring methods.

Could a factoring breakthrough happen to convert this exptime problem 
to polynomial time? Maybe. I said as much. Is it likely? See 
discussions on progress toward proving factoring to be NP-hard (it 
hasn't been proved to be such, though it is suspected to be so, i.e., 
that there will never be "easy" methods of factoring arbitrary large 
numbers).

You don't appear to be familiar with the literature. I suggest you do 
some reading.

(BTW, one of the most important brute force breaks of RSA was done 
for the so-called Blacknet key. Cf. Leyland et. al. Irony abounds.)

>
>Too many crypto pundits spout extrapolations of exponential work factor as
>proof that these ciphers are unbreakable.

I made no claims that this was a proof of the unbreakability of RSA. 
I cited the work factors. The burden of proof is on you and on Nathan 
for your claims that such ciphers are in fact being broken by the 
NSA...you even claimed "near realtime," citing NSA VLSI capabilities. 
_This_ is the point being rebutted by me, not some "spouting" of a 
claim that RSA has been "proved" to be "unbreakable."

>
>These are merely postulates based on an assumption of a sort that has
>generally proven wrong throughout the history of science.  "X requires Y,
>but Y is impossible, so X is impossible."  Until Z comes along, and 20
>years later its demonstrated in science or math classrooms as yet another
>example of bad logic.

They laughed at Ludwig Plutonium, they laughed at Detweiler. And now 
they laugh at Kerry Bonin.

"These are merely postulates," said the stuffed shirt.

What happened to "near realtime" and "cracking farms"?


>
>One of the points I believe is sorely missing in these discussions is how
>important "improvements in algorithms" can be.  In the narrowest sense, I
>agree with your statements - but I have also seen what elegant alternative
>approaches can do to systems that were presumed to be vulnerable only to
>brute force, and I've also seen how nicely they may be placed into custom
>hardware.

Repeat after me: polynomial improvements are of no use for solving 
exptime problems where the keylength can be increased trivially. 
Putting things into silicon is just a polynomial improvement...maybe 
a factor of 100, maybe even 100,000. Uninteresting.





>
>>Then I'd have to say your analytical abilities are shallow. If you
>>think one of these ciphers with work factors exponential in modulus
>>size (or "key length," approximately) will fall to custom chips, you
>>don't understand exponential time/space.
>
>I'm not stating that brute force silicon can be scaled to the point it can
>attack a 256 bit key in reasonable time today.  What I do know is that
>alternative attacks, implemented in silicon or sapphire, are another
>matter.  Your position is predicated on the assumption that because no such
>attacks are in the public domain, none must exist.  I believe this is
>faulty logic, and advances a common, yet dangerous position.

A lie, actually. I stated quite clearly that there may be factoring 
breakthroughs. I included an entire paragraph on this, and how big 
the breakthrough--either algorithmic or via a quantum computer, a la 
Shor's algorithm--would have to be to make a difference.

Once again, it was _you_ who spoke of "near realtime" and "cracking farms."

>
>>>I don't think its unreasonable to extrapolate that a sufficiently high
>>>priority message can be cracked by the NSA in near realtime, regardless of
>>>the cipher strength used, without significant knowledge of the nature of
>>>the plaintext.
>>
>>And you believe this?
>
>Most people who have worked with military crypto systems do, off the
>record.

So, these folks think RSA-2048 is being cracked in near realtime?

Or even that the lowly 3DES is being cracked in near realtime? (It 
may be, for a few very, very, very high priority messages...but I 
doubt even this. The MIPS-years are enormous, and the peak compute 
capacity is unlikely to be available to handle a message in seconds 
to minutes, which is what I would call "near realtime.")



>The difference between what is public and what has been developed
>with decades of unlimited resources is staggering.  How many cryptographers
>or discrete math experts work in the public domain?  Now how many work for
>the NSA?  That's how many orders of magnitude?  And how many orders of
>magnitude difference in budgets, ect., even with bureaucratic and civil
>service overhead.

This is a more debatable point. I think there's ample evidence that 
the non-NSA expertise in cutting-edge ciphers has exceeded the NSA 
expertise for the past decade or so. For every Brian Snow the NSA 
has, the universities have their share of Shafi Goldwassers and Adi 
Shamirs and Neal Koblitzs and David Wagners.

The days when NSA was the main source of funding for math guys like 
Berlekamp and number theorists and algebraists are over. Hundreds of 
universities, dozens of crypto companies, massive competition.

And for things like factoring, it is _unlikely_ that some GS-14 at 
the Fort has proved that P = NP or has proved that factoring is not 
hard.

You may claim that this is "just an assumption" and that your spook 
buddies have told you "off the record" that they can factor 700-digit 
numbers in "near realtime."

Whatever.

--Tim May
-- 
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
ComSec 3DES:   831-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
"Cyphernomicon"             | black markets, collapse of governments.