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.