CDR: Re: why should it be trusted?
At 01:18 AM 10/17/00 -0700, Tim May wrote:
For a message encrypted (or signed, a related problem) with a PKS cipher, recovering the plaintext involves factoring the modulus...so far as we know. This factoring may be done with conventional computers, special-purpose computers, or even exotic computers (tanks of DNA computers, billions of Net-connected computers, superconducting geodes orbiting around Neptune, quantum computers, whatever.)
[snip]
A look at the work factors (cf. Rivest's paper of circa 1993-4, or Schneier's book, or any of several other books, or one's own calculations) will show the pointlessness of throwing more computer power at sufficiently large moduli.
Absent a breakthrough in factoring (and I mean a _major_ breakthrough, not a polynomial factor speedup), a modulus of thousands of decimal digits will never be factored. The "RSA-129" challenge becomes the "RSA-1000" challenge. Moore's Law won't do any good, nor will using ASICs or gate arrays or even nanotechnology.
A quantum computer _might_ make a difference (though this is unproven).
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. Too many crypto pundits spout extrapolations of exponential work factor as proof that these ciphers are 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.
Talking about SOS and ECL and 1 GHz and all is nonsensical. All of those technologies are as nothing when in comes to problems with work factors exponential in key length!
The exact point at which brute force becomes economically infeasible depends on technologies, improvements in algorithms, etc., but the broad outlines remain as described.
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.
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.
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. 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. Call it threat analysis - I think it is reasonable to assume they know a few tricks that aren't public yet. And any trick related to factoring or Feistel networks is sufficient to obsolete those "age of universe" extrapolations.
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.
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.
When you are talking "heat death of the universe" time lengths, improvement is algorithms don't really add up to all that much time. In the real world (outside of Academentia) we have different threat models that we need Crypto for. To keep a credit card safe, we need only to make sure that a given undesired decrypt be more expensive than it's worth--and the encrypted credit card string has to last what? Three years? before it's worthless anyway. I'll take the risk that someone will improve factoring by what? 6 or 7 orders of magnitude? (that makes 1,000,000,000 years into 1000 years. I think my card will be expired by then). Other sorts of banking operations have an even short life--from minutes to months. They could take almost 9 orders of magnitude(unless I don't understand this order of magnitude thing)--does it really matter if a banking transaction falls to a break in 10 years? One would think that a bank would be wise enough to expire it's keys more regularly than that. Or military secrets--because of the nature of the military, keys can be expired even more rapidly 3 to 5 years ought to be plenty. And hey, if we do get a break through in factoring speed, it seems cheap enough to double our key size. Quantum computers are a different story--and may (may) make a shambles of our current crypto schemes--but as near as we can tell no one is close to a working system.
Call it threat analysis - I think it is reasonable to assume they know a few tricks that aren't public yet. And any trick related to factoring or Feistel networks is sufficient to obsolete those "age of universe" extrapolations.
There is a wide difference between "age of universe" and "age of man". The point of the whole "heat death of the universe" thing is that even if a given brute force decrypt can be made 1000 times faster, it's still going to take a *LONG* time. -- A quote from Petro's Archives: ********************************************** Sometimes it is said that man can not be trusted with the government of himself. Can he, then, be trusted with the government of others? Or have we found angels in the forms of kings to govern him? Let history answer this question. -- Thomas Jefferson, 1st Inaugural
Bruce Schneier, among others, argues that strength of algorithm is not a reliable determinant of security of information. That most successful attacks occur through more accessible weaknesses, the prime one being human. Bruce reviews several of these in his October 15 Crypto-Gram, and refers to his latest book for more cybersecurity threats that crypto cannot defend. Ross Anderson, among others (some here), claim that chips are readily vulnerable to tampering, and that poses a much greater risk than algo attacks. Programs and people which just grab info directly from your box and bunker through B&E software and black bag jobs cannot be stopped by mathematics, though encrypted info might remain inaccessible. Lifting electromagnetically emanated data, say, that from keyboard to cpu, before it is encrypted, is still a threat, not limited to classified technology, as demonstrated by Ross Anderson, Markus Kuhn and others, and reviewed here recently. Cryptanalysis may be the most crucial technology in the world today, as it has been well before mathematical encipherment. How it is being done is probably the most closely guarded secret, and part of that protection is zero information. Share encryption information, yes, but not decrypt, not even a hint. Blow sunshine about algo strength and unbreakability, yes, that would be in order. What intrigues is the national security benefit of fostering the growth of public encryption, despite the claims that it makes global surveillance more difficult. If a public encryption enterprise didn't exist it would have to be invented to divert the attackers from genuine threats and weaknesses, as well as embed in the public realm a technology for covert snooping inside the Medeco pretense. The question occurs: did PK crypto get leaked on purpose? How was it done?
----- Original Message ----- From: John Young <jya@pipeline.com>
The question occurs: did PK crypto get leaked on purpose? How was it done?
It may not be exactly what you had in mind, but I personally _observed_ the "leak" (to the public) of RSA, but I simply didn't recognize what it was at the time! I believe it was late January/early February 1977 (but I could be off a couple of months) and it was the beginning of my second semester of my freshman year at MIT. Due to the location of my dorm, "East Campus," I frequently walked by the mathematics department and its bulletin boards on the main floor. Usually bulletin boards like that are filled with grades, test results, problem set answers, and things like that. But at this point, they had something that wasn't identifiably of any of these categories. "Exponentiation", "modulo arithmetic," "prime numbers", etc. I wish I could see the thing again. I didn't spend a lot of time on it, at the time, but I would have if I'd known what it was. Jim Bell
At 7:24 AM -0400 10/17/00, John Young wrote:
The question occurs: did PK crypto get leaked on purpose? How was it done?
I'm not sure what your implication is, though I have some suspicion you are insinuating that the NSA and Company knew PK was somehow weak and so it leaked it. Well, several points: 1. The public part of the process (not counting the Brits and possible collaborators who may have invented something very similar some years earlier) included several folks many of us know quite well: Whit Diffie, Martin Hellman, and Ralph Merkle are all Bay Area folks from Stanford and Berkeley, then. And Rivest, Shamir, and Adleman are also well known. They have not hinted that they were fed information from NSA, or that key results mysteriously appeared on their desktops one night. Conclusion from this: a deliberate leak seems unlikely. 2. The ideas were "in the air" at the time. Merkle had done some interesting work on speculating about "puzzles" which might be used for encryption. I believe this work went back to around 1974-5, when he was a grad student at Berkeley. His notion was that some problems are easy to work out in one direction, but hard in the other direction. (Think of what we now routinely call one-way functions.) (By the way, there are comments from the 19th century along similar lines, even mentioning cryptography. I think some of the review articles on public key have mentioned these historical comments.) Merkle does not seem to be the kind of person who either would be working for the NSA or whom the NSA would pick to be a conduit for leaked secrets. 3. Ditto in spades for Whit Diffie. And Martin Hellman was, at that time, an active anti-war activist ("Beyond War"). Seems unlikely that NSA would pick them. 4. Once the Diffie-Hellman-Merkle early papers on the ideas of public key systems were out, Rivest-Shamir-Adleman worked on alternatives to the knapsack algorithm. The result was what we know of as RSA. At no point do I see persuasive evidence that PK and/or RSA were "leaked on purpose." Whit Diffie sometimes shows up at Bay Area Cypherpunk events, so someone could ask him. Though I expect he's tired of hearing conspiracy theories. --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.
Merkle does not seem to be the kind of person who either would be working for the NSA or whom the NSA would pick to be a conduit for leaked secrets.
3. Ditto in spades for Whit Diffie. And Martin Hellman was, at that time, an active anti-war activist ("Beyond War"). Seems unlikely that NSA would pick them.
Ah, but that's what /they/ WANT us to think... (yes, I'm joking.) (Or maybe I'm a NSA plant cleverly disguised to something that I can't explain or I'll have to kill myself...) -- A quote from Petro's Archives: ********************************************** Sometimes it is said that man can not be trusted with the government of himself. Can he, then, be trusted with the government of others? Or have we found angels in the forms of kings to govern him? Let history answer this question. -- Thomas Jefferson, 1st Inaugural
-- At 12:34 PM 10/17/2000 -0700, Tim May wrote:
3. Ditto in spades for Whit Diffie. And Martin Hellman was, at that time, an active anti-war activist ("Beyond War"). Seems unlikely that NSA would pick them.
To put this in simple terms. A smart person with a modest computer, familiar with the long history of code creation and code breaking, can create a code that a much smarter person with a vastly more powerful computer cannot break. The codes we are using were created by smart people. We know these people. They are unlikely to be part of a vast conspiracy to put something over us. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG HL2kYDppyJqeq3voMaoHBsK9A7bIEHXh3K/JS6d+ 4eN6Rd5zjWoFZUJ+lf+iltc3DF4g2a6Pa/Wt11mcc
participants (6)
-
James A.. Donald -
jim bell -
John Young -
Kerry L. Bonin -
petro -
Tim May