256 bit security and the laws of physics
December 17, 2012 4:29 AM   Subscribe

Why 256 bit keys are long enough. A nice graphic explanation by Schneier why brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

On the other hand, never underestimate the skills of a ninja with enough coffee.
posted by Twang (34 comments total) 19 users marked this as a favorite
 
Like Schneier also said... "Attacks always get better; they never get worse." Now I don't know which Schneier to believe!

Maybe the 256-bit key will eventually be brought down by A Fancy Rig or some Obscure Academic Paper that finds some flaw.
posted by Blake at 4:35 AM on December 17, 2012 [1 favorite]


until computers are built from something other than matter and occupy something other than space.

Just give away the plans for iPhone 7, why don't you.
posted by twoleftfeet at 4:37 AM on December 17, 2012 [11 favorites]


I've got a microchip from Setec Astronomy that begs to differ.
posted by Halloween Jack at 4:48 AM on December 17, 2012 [10 favorites]


All I can find is someone posting an excerpt from Applied Cryptography, which is well known and has been around forever. Did Schneier write something new on stackexchange and you mis-linked, or was that it?
posted by indubitable at 4:49 AM on December 17, 2012 [2 favorites]


One thing is, for many purposes, it's actually not desirable to have perfect, forever-uncrackable security. Like if you encrypted your files, forgot your password, and need to recover the system, you can easily hose yourself that way. Of course, any system you use to decrypt your files can be used by outside agencies. Then there's using strong encryption to make hateful, locked-down proprietary computing devices harder to jailbreak.

I'm sure NSA/CIA people would also make an argument about not giving the "bad guys" access to strong encryption technology, of which I'm not insensible, although I strongly suspect any argument that comes from that direction as what little I hear about their institutional culture seems likely to be very insular and circular in its reasoning. A favorite Blake quote is "a man who never alters his opinion is like standing water, and breeds reptiles of the mind." You see Dr. Thomson, I remember stuff from those old classes! I think it probable those organizations tend to engage in lizard thinking.

The history of technology is filled with instances where it has advanced further than society is ready for. In fact, those cases are a driving force of research, where one aggrieved group is left without social recourse for overcoming some power bloc, and seeks an external remedy. I can't say whether that's ultimately caused more problems than it's solved or not, only that it is the way the world works, and trying to stop it favors entrenched interests and is probably a mistake.
posted by JHarris at 5:18 AM on December 17, 2012 [8 favorites]


Thank you for tuning to JHarris's weekly ramble.
posted by JHarris at 5:18 AM on December 17, 2012 [1 favorite]


...."A favorite Blake quote".... I'll go ahead and assume I said that at some point.
posted by Blake at 5:27 AM on December 17, 2012 [5 favorites]


Note: there is a difference between a properly implemented strong 256 bit crypto system and a poorly implemented one.

If you screw up the implementation, 1024 bits won't help you.

There's also the legion of attacks based on getting the key. Doesn't matter how strong, or well implemented, the system is, if the key is known, the plaintext is know. That is, after all, the whole point.

What Bruce is saying here is that there is currently no reason to build a key longer than 256 bits in a symmetrical key crypto system.

Note Well: this does *not* apply to public/private key systems. 256 bits is uncomfortably short for those.
posted by eriko at 5:52 AM on December 17, 2012 [7 favorites]


You should clarify that Schneier only defends 256bit symmetric keys, ala AES keys. I believe Schneier has already advised going beyond 2048bits for public keys that must survive for a prolonged period, ala a PGPG/GPG RSA key.
posted by jeffburdges at 6:00 AM on December 17, 2012 [2 favorites]


Again humans' inability to fully grasp exponential growth is demonstrated.

An increase from 128 bits to 256 doesn't make your key twice as strong. It makes a key that is roughly 340,000,000,000,000,000,000,000,000,000,000,000,000 times as strong.
posted by cotterpin at 6:23 AM on December 17, 2012 [7 favorites]


Nice try, NSA.
posted by T.D. Strange at 6:23 AM on December 17, 2012 [7 favorites]


You should clarify that Schneier only defends 256bit symmetric keys, ala AES keys. I believe Schneier has already advised going beyond 2048bits for public keys that must survive for a prolonged period, ala a PGPG/GPG RSA key.

This is worth repeating, so I'm Qing it for T, and clarifying that because of differences between the algorithms involved, it's indeed important to specify the type of encryption when talking key length.
posted by kengraham at 6:36 AM on December 17, 2012 [4 favorites]


Expanding on eriko's comment: it's not just that he's only talking about symmetric keys. It's also that he's talking about brute-force attacks.

"Brute force" means, basically, that you set your hardware to just chugging through every possibility until you hit on the right one. In the context of AES, that basically means you generate every possible 256-bit key, and try each of them, one by one, until you hit the one that works. This is, as the quote in the linked comment points out, infeasible.

For, say, RSA -- an asymmetric system -- a brute-force attack would be different. RSA involves publishing a large number which is the product of two primes, and breaking it requires figuring out what those two primes (which are kept secret) are. So brute force would mean, for a key of length n, enumerating every prime less than n/2 and trying all the possible pairings to see which one produces the public key. This can also be made infeasible by a suitably large key; in fact, I'm pretty sure the same "thermodynamic problem" makes brute force infeasible for RSA at smaller key lengths than AES. But 768-bit RSA keys still aren't safe, and people are nervous about 1024 bits, because there are factoring algorithms that are faster than brute force, and they've already been demonstrated to be feasible on real, existing hardware, for 768 bits.
posted by ubernostrum at 6:38 AM on December 17, 2012 [1 favorite]


This argument works under the assumption that brute-force search over the entire key-space is the most viable attack.

No cryptosystem to date, aside from a one-time pad, has been proven to have that level of security.

So while it is a nice argument, it does not address the main issue with pretty much any cryptosystem aside from a one-time pad: they rely on functions that are easy to compute in one direction, but _appear_ to be hard to invert (for all we know).
posted by TheyCallItPeace at 6:42 AM on December 17, 2012 [3 favorites]


Approaching the notion of strong security from the perspective of Psychology rather than Physics, I liked Hristo Bojinov's proposed countermeasure to rubber hose cryptanalysis: passwords based on information stored in our procedural memory. Computers can identify us by a unique skill that is stored in a part of our memory that we are not able to articulate to others.
posted by rongorongo at 6:45 AM on December 17, 2012


TheyCallItPeace: "This argument works under the assumption that brute-force search over the entire key-space is the most viable attack.

No cryptosystem to date, aside from a one-time pad, has been proven to have that level of security.

So while it is a nice argument, it does not address the main issue with pretty much any cryptosystem aside from a one-time pad: they rely on functions that are easy to compute in one direction, but _appear_ to be hard to invert (for all we know).
"

Of course it doesn't, because Schneier was talking specifically about brute force attacks in that part of his book, and the book this passage comes from (Applied Cryptography, a really great read, by the way) deals with your concerns as well.

that said, the most effective attacks rely on massively parallel key searches (like the EFF's Deep Crack), attacks on specific implementation of attacks (like the PS3's implementation of DSA) or side channel attacks like timing attack or power analysis attacks.

if it takes an hour of timing responses to retrieve a 256-bit key, quadupling the key length doesn't provide much more of a margin of security, same with implementation issues that allow a key to be determined with a few lines of linear algebra. that just leaves brute force attacks, and as Schneier says, 256-bit keys are secure enough for that.

Cryptanalysis can create a theoretical attack can reduce an algorithm with a 256-bit key to 230 bits of security is a major break, but in this case it still means a supernova doesn't put out enough energy to fully brute force it with your magical ideal computer. So 256 bit keys are honestly probably enough.
posted by grandsham at 7:04 AM on December 17, 2012 [1 favorite]


So while it is a nice argument, it does not address the main issue with pretty much any cryptosystem aside from a one-time pad: they rely on functions that are easy to compute in one direction, but _appear_ to be hard to invert (for all we know).

I feel the need to quibble that RSA is pretty easy to do in both directions. Most people in this thread have probably done it by hand at least once. It relies, as mentioned above, on 'factoring is hard', meaning it's hard to have the requisite information to implement the easy algorithm. Of course, you can say the function you're talking about is factoring, not the Chinese Remainder Theorem.
posted by hoyland at 7:05 AM on December 17, 2012


also, can we talk about how silly it is that Schneier decided to use ergs as his unit of energy for his example? because it's pretty silly.
posted by grandsham at 7:06 AM on December 17, 2012


until computers are built from something other than matter and occupy something other than space.

Just give away the plans for iPhone 7, why don't you.


Well more or less, yes. I have it on the best authority that Iphone 7i will be made of a crystaline form of Steve Jobs' pure distilled liquid genius (kept in glass-lined drums in a climate-controlled sub-cellar at Apple World Headquarters) and powered by fanboy hyperventilation ducted through a system of wormholes resulting from the collapse of ultra-massive stellar marketing campaigns.

Don't go shopping for it. It will find you, if you're worthy.
 
posted by Herodios at 7:14 AM on December 17, 2012 [5 favorites]


also, can we talk about how silly it is that Schneier decided to use ergs as his unit of energy for his example? because it's pretty silly.
Whatchoo got against ergs? Ergs is just joules for tiny people.
posted by introp at 7:20 AM on December 17, 2012 [7 favorites]


Like if you encrypted your files, forgot your password, and need to recover the system, you can easily hose yourself that way.

Silly, that's what Post-Its are for.
posted by dhartung at 7:57 AM on December 17, 2012 [2 favorites]


I'm not sure if he was being facetious, or not, but computers are already "built from something other than matter and occupy something other than space". D-wave sells quantum computers right now. The number of qubits that can be controlled is steadily increasing and if current trends hold, 2048-bit RSA keys will be useless in 2050 or sooner. Shor's algorithm can be used to factor integers much more quickly than classical algorithms and is one of the prime (ha!) motivators of quantum computing.
posted by euphorb at 8:24 AM on December 17, 2012 [1 favorite]


Quantum computers absolutely follow the laws of thermodynamics. They are of normal matter and time.
posted by introp at 8:31 AM on December 17, 2012 [6 favorites]


I'm confused why a quote from a 15 year old book is suddenly a Metafilter post. But the framing is misleading. As TheyCallItPeace notes, this little thermodynamic argument only applies if all 256 bits really need to be brute forced.

Here in the real world, almost every older crypto algorithm has been broken so that the work required is much less than brute forcing the whole keyspace. DES' 56 bit keys, for instance, have been broken down to about 43 bits. Finding a collision in MD5 is also a whole lot easier than searching the whole 128 bit space. (I'm glossing over details about types of attacks, etc.) The key point is that every practical algorithm that's had any time to be analyzed can be attacked more efficiently than a pure brute force. No reason to think this year's crop of 256 bit block ciphers are any different.
posted by Nelson at 8:56 AM on December 17, 2012


JHarris: One thing is, for many purposes, it's actually not desirable to have perfect, forever-uncrackable security. Like if you encrypted your files, forgot your password, and need to recover the system, you can easily hose yourself that way.
Equally true: for many purposes, it's actually not desirable to encrypt the data at all. Like this thread, for instance.

But we aren't interested in situations where less-than-state-of-the-art, crackable encryption is sufficient, any more than one buys a car for how well it runs in 2nd gear, or designs new video technology around 16-bit-color. Technology is driven by the extreme ends of our needs.
posted by IAmBroom at 9:34 AM on December 17, 2012


Nelson: "Here in the real world, almost every older crypto algorithm has been broken so that the work required is much less than brute forcing the whole keyspace. DES' 56 bit keys, for instance, have been broken down to about 43 bits. Finding a collision in MD5 is also a whole lot easier than searching the whole 128 bit space. (I'm glossing over details about types of attacks, etc.) The key point is that every practical algorithm that's had any time to be analyzed can be attacked more efficiently than a pure brute force. No reason to think this year's crop of 256 bit block ciphers are any different."

The point is that the keyspace would need to be massively reduced to reach the relam of possibly brute forceable.

Lets assume a break similar to the one found against DES is found with AES, which is the standard symmetric encryption algorithms, reducing the number of computations by a similar degree. 56 - 43 = 13. 13/56 = ~0.23. We'll round this to 25 percent, so such an attack against AES-256 would reduce the keyspace from 256 to 192.

If you read the posted quote, you'll note that this still requires a theoretically ideal computer using the entire output of the sun for 32 years without any loss to increment a counter through all of the 2^192 values required (never mind performing the necessary AES encryption)

This also ignores that the DES attack is a known plaintext attack, meaning you will need to expend computation time generating all of those 2^192 special plaintexts.

For reference, the best attack against the full AES-256 algorithm is 2^254.4
posted by grandsham at 9:36 AM on December 17, 2012 [2 favorites]


I'm going to stick with 257 bits, juuuuuust to be safe.
posted by FatherDagon at 10:22 AM on December 17, 2012 [3 favorites]


If it's legal to use a crypto method and talk about it on Metafilter, I assume the NSA already has a backdoor.
posted by deathpanels at 10:59 AM on December 17, 2012


also, can we talk about how silly it is that Schneier decided to use ergs as his unit of energy for his example? because it's pretty silly.

The astrophysical community tends to use ergs (and cgs units in general).
posted by dirigibleman at 11:22 AM on December 17, 2012 [2 favorites]


It's also worth pointing out that, in cases where the attacker has access to the encrypted keystore, the password used for that encryption, and that separate encryption algorithm, may be enough weaker than the main encryption to be much more feasible as an attack vector.

Remembering a password that genuinely represented 256 bits of entropy would be really hard.

So, not only is the algorithm in question important to specify for questions of bit length versus security, so is the attack profile.... what, specifically, is being attacked. Billion-bit AES won't protect you if the passphrase on the encryption key is 'password'.
posted by Malor at 3:06 PM on December 17, 2012 [1 favorite]


Oh, and ergs versus joules is an extremely silly complaint, since the scales are so tiny. He used the smallest common energy measurement, and that's 10^16 too large for the actual amounts of energy in question. And you guys want to use a unit that's another 10^6 larger?

That's vaguely like complaining about measuring transistor density in parsecs, and insisting that light years be used instead.
posted by Malor at 3:16 PM on December 17, 2012 [2 favorites]


We've completed work efforts in the ~60 bits, publically anyway. In practical terms, a brute force effort between 90 and 128 bits is sufficient, maybe even less TBH.

Honestly, this is not where you get attacked anymore. Even the RNG is a better target and that doesn't care how many bits you use.
posted by effugas at 5:13 PM on December 17, 2012 [3 favorites]


"He used the smallest common energy measurement, and that's 10^16 too large for the actual amounts of energy in question. And you guys want to use a unit that's another 10^6 larger?"

Just me that's complaining, not anyone else. seemed like a strange choice of unit, given that joules are the SI unit, and ergs are cgs. didn't realize that they are commonly used in astrophysics (thanks dirigibleman!), which makes sense given we're talking about the output of stars and supernovas. I no longer think its silly.

But to be honest, a error factor of 1 million doesn't really matter in this sort of thing. a millionth of the energy is less than the difference between 192 bits and 219 bits of counting. Still just as mind bogglingly impossible.
posted by grandsham at 10:04 PM on December 17, 2012 [1 favorite]


idn't realize that they are commonly used in astrophysics (thanks dirigibleman!), which makes sense given we're talking about the output of stars and supernovas. I no longer think its silly.

Well, he could have used foe, which is the unit of energy in a supernova. It's 1051 ergs.* The output of our sun, over its entire lifespan, is about 1 foe, and the output of a type II supernova is about 100 foe, with 1 foe being absorbed by the mass of the star, which unbinds and destroys it, and most of the rest being emitted as neutrinos.


* Foe is "Fifty One Ergs."
posted by eriko at 7:16 AM on December 19, 2012 [2 favorites]


« Older Not because it was easy, but because it was hard   |   Dark Field Microscopy Newer »


This thread has been archived and is closed to new comments