[dave@farber.net: [IP] on crypto systems from CTO PGP]
----- Forwarded message from David Farber <dave@farber.net> -----
Jon Callas <jon@pgp.com> wrote:
Imagine a computer that is the size of a grain of sand that can test keys against some encrypted data. Also imagine that it can test a key in the amount of time it takes light to cross it. Then consider a cluster of these computers, so many that if you covered the earth with them, they would cover the whole planet to the height of 1 meter. The cluster of computers would crack a 128-bit key on average in 1,000 years.
The error in this argument is the assumption that the computers aren't all partially replicating each others computations.
If you want to brute-force a key, it literally takes a planet-ful of computers. And of course, there are always 256-bit keys, if you worry about the possibility that government has a spare planet that they want to devote to key-cracking.
Suppose I give you one NAND gate, and ask you to build an encryption function that inputs 64 bits of data and 256 bits of key, and outputs 64 bits of data. Couldn't build a very complicated one, could you? Wouldn't take a very big computer to sweep the entire 256 bit key space, as long as you did no redundant computation. Now suppose I give you ten NAND gates. Now you can build a more complicated encryption function. Nonetheless, it is still greatly limited with regard to what it does with each of the the 2^256 keys being different from what it does with the others. Sweeping the key space is still practically instantaneous, as long as you don't do redundant computation. Now suppose I give you 100,000 NAND gates. Now you can build a really complicated encryption function, that passes all the tests of whether encryption functions are good. But the number of ways you can hook even 100,000 gates together is a small drop in the bucket compared to the confusion and diffusion necessary to make all 2^256 permutations on 2^64 integers truly statistically independent of one another. How fast can I sweep the key space now, modding out redundant computation? An interesting question you would do well to ponder. Many things that take a long time in the domain of data, happen quite speedily if you do them by transformations in the domain of the function representation.
Now of course, there are other ways to break the system.
They could know something we don't.
You think?
They could know some fundamental truth about mathematics (like how to factor really fast), some effective form of symmetric cryptanalysis, or something else. They could know about quantum computers, DNA computers, systems based upon non-Einsteinian physics, and so on. Yes, it's possible. But this quickly gets into true paranoid thought. There isn't a lot of difference between the *presumption* that they have such things and the presumption that they have aliens in a vault in Nevada. It isn't falsifiable. It gets irrational quickly. The evidence that we have about this suggests quite the opposite, but more on that later.
There are an unlimited number of surprising algorithms whose direct derivation lies just beyond the range of human ingenuity. This is why we have Experimental Mathematics and other techniques for grepping the fabric of reality for things we could never figure out on our own through a random walk of the solution space.
The last bit of evidence we have that suggests that they can't break the crypto is that they are apparently devoting a lot of effort to traffic analysis.
I'd bet money the NSA has been able to crack RSA since 1996. -- Eric Michael Cordian 0+ O:.T:.O:. Mathematical Munitions Division "Do What Thou Wilt Shall Be The Whole Of The Law"
I was thinking about this statement...
I'd bet money the NSA has been able to crack RSA since 1996.
-- Eric Michael Cordian 0+ O:.T:.O:. Mathematical Munitions Division "Do What Thou Wilt Shall Be The Whole Of The Law"
By this I assume you don't mean through buffer overflows or exploiting obscure bits of cluelessness. You mean "brute force", but (obviously) through the use of algorithms we Spy-ees aren't aware of. I'd say that's absurd paranoid thinking, but on the other hand... 1. There's been no 'proof' per se about the intractability of factoring, correct? 2. Seems like the Feds veryu suddenly gave up fighting encryption a few years ago. I assumed this was because of the rapid rise of electronic transactions and communications, but maybe... 3. We never discover anything that makes us realize that the factoring problem is a lot HARDER than we realized....every few years there's a small inroad made here for this kind of prime factor, another discovery there and so on that renders RSA fairly trivial for certain categories of primes. Given several footbalfields' worth of well-payed encryption talent working for several decades, seems to me they could certainly at least be ahead of the civilian world in this area (silicon chip fabrication is another issue entirely, however). Is this correct? If the statement is true (ie, 'NSA has been able to crack RSA...'), it's not necessarily the end of the world. I'd bet that it's still potentially VERY expensive on average, though the scary thing is that some messages might fall apart easily. In fact...a search for a subtle and inexplicable steering of the prime space used by some implementations would be telling. Am I talking out my ass here? Another interesting thing is that it almost doesn't matter. Buffer overflows and other indirect attack are such that one should consider a lone encrypted message sitting out there like a sitting duck painted bright red. Better still to paint that duck white and stick him in a bigass flock. In other words, it might make sense at this point to regard RSA as crackable and then rethink how to hide the significance of encryption itself... -TD
There is a constant 20 years lag between a crack and public awareness of the same. We'll know in 2016. But you are reasonably safe in the meantime - remember, during WW2 Germans submarines were allowed to sink many ships in order to mask breaking of Enigma. The tactic for others was to send planes to 'accidentally' spot the submarine. All analogies are perfectly valid today. To maintain the potential crack technology an asset, they will have to use plausible classical means of discovering the plaintext.
I'd bet money the NSA has been able to crack RSA since 1996.
end (of original message) Y-a*h*o-o (yes, they scan for this) spam follows: __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
There is a constant 20 years lag between a crack and public awareness of
On Thu, Jul 20, 2006 at 08:57:23AM -0700, Morlock Elloi wrote: the
same. We'll know in 2016.
It's too bad gpg doesn't support use of large one-time pad files, one for a single recipient, or a group of recipients.
But you are reasonably safe in the meantime - remember, during WW2 Germans
I use encryption for the same reason I use envelopes for my mail. It puts up a higher threshold for getting at the contents. NSA recommends to move on to elliptic curve crypto http://www.nsa.gov/ia/industry/crypto_elliptic_curve.cfm whether this is something they can break far more easily, or because nobody can crack it but them, or because nobody can yet crack it. Related question: do you think AES is weaker than 3DES?
submarines were allowed to sink many ships in order to mask breaking of Enigma. The tactic for others was to send planes to 'accidentally' spot the submarine. All analogies are perfectly valid today. To maintain the potential crack technology an asset, they will have to use plausible classical means of discovering the plaintext.
-- Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org ______________________________________________________________ ICBM: 48.07100, 11.36820 http://www.ativel.com 8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE [demime 1.01d removed an attachment of type application/pgp-signature which had a name of signature.asc]
participants (4)
-
Eric Cordian -
Eugen Leitl -
Morlock Elloi -
Tyler Durden