10 ms·

Why 256 bit keys are large enough

281 points by mef 14y ago

donpark 14y ago
IMO the most vulnerable part of AES is not the side-channels but key generation. Compromise the source of entropies, preferably only for processes with specific signatures, just enough to be crackable on-demand then capture everything on the wire remotely.
dfc 14y ago
For further reference and a more detailed discussion of algo / key length selection take a look at NIST's Recommendation for Key Management [1], specifically section 5.6 "Guidance for Cryptographic Algorithm and Key-Size Selection." [1] http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57_part1_rev3_general.pdf http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57_p...
hartror 14y ago
Wow computer science meets Greg Bear, I think I need to now go write a short story featuring a supernova powered super computer.
- keithpeter 14y ago
  "And they strongly imply that 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." Or about a computer that isn't made of matter as we understand it...
  - ars 14y ago
    How is what you said any different from what he said?
    - keithpeter 14y ago
      He said a super nova powered computer. A super nova is matter as we understand it....
cjg 14y ago
Something that many of these answers fail to address is that a 256-bit key isn't big enough, if you can do 2^128 computations. This is due to the probability of key collision. See http://en.wikipedia.org/wiki/Birthday_attack http://en.wikipedia.org/wiki/Birthday_attack Not that I'm saying 2^128 calculations isn't a lot, but compared to 2^256, it's a tiny speck.
- mrb 14y ago
  You are confusing different things. You are talking about hash algorithms, whereas the OP is about encryption algorithms. And it is not proper terminology to refer to hashes as "keys". What you are trying to convey, is that hash algorithms need to generate hash sizes of 512 bits if they want to make collision generation as hard as bruteforcing a 256-bit symmetric encryption key. This is true. But please use proper terminology.
- grandsham 14y ago
  a birthday attack reduces the number of keys you have to search by half, not half the number of bits. This means that you would have to search 2^255 keys instead of 2^256 keys.
  - pjscott 14y ago
    Look again. Finding a collision in a hash function with n possible values takes an expected number of guesses proportional to sqrt(n). If n = 2^256, then sqrt(n) = (2^256)^(1/2) = 2^(256/2) = 2^128.
UnoriginalGuy 14y ago
I wish I knew more about encryption. Unfortunately it isn't a very accessible area, even if you have a degree in CS you aren't really qualified to even touch the stuff, you need a maths degree at the very least. Plus every time anyone brings up the subject the answer is always the same: "If you roll your own crypto you're an idiot." Which is not very encouraging. Likely why crypto' libraries are so antiquated and terrible.
- ars 14y ago
  By far the simplest encryption to understand is the factorization problem. If you have two prime number it's trivial to multiply them and get the result. Or if you have the result and one prime number, it's also trivial to divide and get the second prime number. But if you have that result, figuring out which two prime numbers divide it requires you to check every single one of them - which takes much longer. Now imagine your password is one of the prime numbers, and your secret message is converted to a different prime number. Multiply your password with the secret message and you have your result. That's the encrypted message. Without knowing what the password was, there is no feasible way to figure out what the message was - you would have to divide by every prime number looking for another prime number that evenly divides into the encrypted message. (Technically once you do that you don't know if that prime number was the message or the password.) This is the core of encryption - the trouble is the side-details can mess you up, and they are really not obvious. For example: How do you securely convert a message into a prime number? Or a password into a prime number? You can't use the entire message as one enormous prime number, that's not feasible, so you have to break it up. How do you do that properly, without leaking information? There are other issues with the math (I'm not familiar enough with encryption to even know what they are, but they are things like certain primes have patterns that make themself obvious in the result). See http://en.wikipedia.org/wiki/Semiprime http://en.wikipedia.org/wiki/Semiprime for some primes patterns to avoid. Then there are issues with the implementation - if you are on a multi user system (or a remote system) you want to make sure people can't figure out the password by watching which system resources you use, or how long things take you. And then issues with the algorithm: If you encrypt two documents with the same password it can be possible to compare them and figure out what you used. So you want to add some randomization to the password to make that impossible. But getting good random numbers isn't always easy. And you have to store that random number in the message so it can be reversed - but watch out that you didn't do that in a way that negates the advantage of the random number.
ars 14y ago
One reason for extra large keys is for headroom in case of partial breakage. Usually when a cipher is broken, they don't break it fully, but rather reduce the keyspace. By making your starting keyspace even larger you make even a broken cypher secure (up to a point).
- VLM 14y ago
  You are correct but its also extremely educational to graph the decrease over time, for various cryptosystems both real/pro and "roll your own". The difference between a professionally designed algo and a "roll your own" algo is the roll your own is usually extremely brittle and shatters to nothing in one discovery vs a professionally designed algo usually has multiple generations of grad students chip away maybe an average of 10 bits per decade as newer forms of analysis are slowly invented and/or declassified. If you roll your own, its at least several orders of magnitude more likely to break than a pro algo, and when it does, unlike the pro algo, it'll almost certainly snap all the way at once, so using a large keyspace just means more of an epic fail and wasted processor power. On the other hand if you use a real algo, then a loss of 20 bits per decade or whatever average really does help, so crank the keyspace to the max. So I'd have to disagree with you there, if you're using a broken (homemade?) algo don't bother with more than 8 bits or so, any more is just wasting processor time, homemade is only useful for casual obfuscation. If you're using a real algo, then, and only then, larger keyspace actually will save you over the long run...
bajsejohannes 14y ago
This a very good explaination of why 256 bits is enough against a brute force attack. The goal of breaking cryptographic systems is of course not brute force, but to reduce the actual key space you have to search. This is frequently measured in how many redundant bits you can shave off. So for AES, we might find in the future that 256 bits isn't enough after all.
- p4bl0 14y ago
  Actual implementations of 256 bits AES are already breakable using side-channel attacks.
  - chii 14y ago
    so if that key size is increased, would these side channel attacks be either mitigated, or made impractical?
    - p4bl0 14y ago
      No that's not the way to go for countermeasures against side-channel attacks (breaking 4096 bits key in asymmetric crypto is also doable using side-channel attacks, even in the cloud [1]). Since it is a physical attack rather than a mathematical one, the countermeasures are at the physical level too: the idea is to make the cryptosystem leak less information through channel such as power consumption, computation or memory access time, electromagnetic radiation… Currently most of these countermeasures are at hardware level. [1] https://news.ycombinator.com/item?id=4865516 https://news.ycombinator.com/item?id=4865516 Edit: forgot to add reference link.
mtgx 14y ago
So even a quantum computer wouldn't be enough then?
- Devilboy 14y ago
  Quantum computers can, in general, provide up to a quadratic speedup over classical algorithms and WILL in fact be enough. Once we have QCs all bets are off.
  - VLM 14y ago
    No, not really. Run the same example from the article with a quadratic speedup and see how scalable it is. 56 bit DES should be nervous. 256 bit AES, not so much. There is a tiresome often repeated quantum computing meme or anti-pattern where QC is a magic implementation such that "my magic can do anything I can dream of". Well no, not really. Oh it could be powerful, maybe even implementable, but not limitless.
    - apawloski 14y ago
      To clarify a bit further, only a few cryptosystems (certain public key systems) are really threatened by quantum computers. Theoretically, literature indicates that quantum computers are really good at factoring large numbers [1], and they are really good at solving discrete log problems [2]. So yes, QCs are theoretically able to crack in linear time some systems whose security depends on those problems being hard (eg ElGamal, RSA). But systems that don't rely on large primes/discrete logs (eg symmetric algorithms like AES) are not vulnerable to quantum computers. (At least not vulnerable in the "throw them out, they're useless now" sense.) In fact, there's even asymmetric cryptosystems that aren't threatened by quantum computers [3]. Again, any system that doesn't rely on large primes, or the difficulty of the discrete log problem, is not significantly threatened. [1]http://arxiv.org/abs/quant-ph/9503007 http://arxiv.org/abs/quant-ph/9503007 [2]http://epubs.siam.org/doi/abs/10.1137/S0097539795293172?journalCode=smjcat http://epubs.siam.org/doi/abs/10.1137/S0097539795293172?jour... [3]http://link.springer.com/chapter/10.1007%2F3-540-44586-2_2?LI=true http://link.springer.com/chapter/10.1007%2F3-540-44586-2_2?L...
  - 14y ago
NicoJuicy 14y ago
Just use the slowest algorithm to delay brute-force attacks :)
- zaptheimpaler 14y ago
  I believe this is the idea behind bcrypt - it can be made slower and slower based on a parameter as larger computations become feasible.
  - merijnv 14y ago
    bcrypt is a hashing algorithm for securely hashing passwords, this is something you want to be slow, yes. However, the discussion in the link is about encryption, which you want to be fast. A popular webserver serving HTTPS to thousands of clients can't afford a 10x overhead on the speed of encryption.
    - VLM 14y ago
      Encryption and decryption speeds need not be symmetric. Salted passwords are a stereotypical example... Lets say my password is "password" and I salt it with a random 8 bit value to make rainbow tables 256 times longer than unsalted. I can encrypt the salted password in one round. However on the decrypt side a salty password is going to have to average 128 rounds before a match and a worst case failure / non-match means you have to run ALL 256 rounds just to make sure. Obviously we're talking salty passwords not secure web traffic, but the point is off the shelf systems have existed for decades where the decrypt system is orders of magnitude more expensive than the encrypt system. Implementing an algo with those characteristics for web traffic "superficially seems feasible" although the details are fuzzy. As an example of a rough guess, 16 bits of salt would scale pretty well for "thousands of clients" if the server and client are more or less similar performance level (which within an order of magnitude or two is probably about right). Simple salt is the wrong algo for this job, but...
    - finnw 14y ago
      bcrypt is actually a cipher, like standard blowfish but with a much more expensive key expansion function. When you call the bcrypt "hash function", what it is really doing is performing this key expansion then using the resulting key to encrypt a constant string. GP is right - you can use bcrypt as a regular cipher, and the extended key schedule will make brute-forcing harder. It is inefficient and unnecessary though - a 384-bit key will not be attacked by brute force anyway, and blowfish's small block size of 64 bits can be problematic (you need to change the key quite frequently to prevent active attacks.)
casca 14y ago
The reason 256 bit AES keys are large enough is that in order to brute-force them, one of 2 things needs to happen: (1) We need to build computers out of something other than matter or (2) A weakness in AES must be discovered that will need to reduce the search space significantly We can disregard (1) as it will probably require changing (almost) all encryption algorithms that we currently use. (2) will most likely break all key-lengths so any use of AES will be weakened.
- tcoppi 14y ago
  Interestingly with regard to (2), there is actually a (totally impractical) attack on AES that only affects the larger key 192 and 256-bit versions and not 128-bit AES - http://eprint.iacr.org/2009/317 http://eprint.iacr.org/2009/317
  - kzrdude 14y ago
    Does that mean that AES-256 is 'broken' in crypto terms?
    - debacle 14y ago
      No.
      - kzrdude 14y ago
        Wikipedia _does_ put AES inside Category:Broken block ciphers.. "Widely cryptanalysed ciphers like Advanced Encryption Standard are considered stronger than un-cryptanalysed ciphers even if there are impractical attacks against them."
    - finnw 14y ago
      It means that if you generate a series of keys by simply incrementing a counter, your 192- and 256-bit keys will be cracked before my 128-bit key. But if you are generating keys that way, you should probably be more concerned about attacks against the RNG that generated the starting key.
deleted 14y ago
[deleted]
mjs 14y ago
Doesn't that Schneier quote only apply to symmetric algorithms (e.g. AES)? I thought asymmetric algorithms (e.g. public/key systems like RSA, as in the original question) have completely different characteristics and rules. "NIST key management guidelines further suggest that 15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys." http://en.wikipedia.org/wiki/Key_size#Asymmetric_algorithm_key_lengths http://en.wikipedia.org/wiki/Key_size#Asymmetric_algorithm_k...
- dfc 14y ago
  NIST citation: Page 64 of Recommendation for Key Management [1] [1] http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57_part1_rev3_general.pdf http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57_p...
- aneesh 14y ago
  Although you're right that a 256-bit RSA key is weaker than a 256-bit AES key, this is not an intrinsic property of symmetric vs asymmetric encryption. It has to do with how you search the key space. To break 256-bit RSA encryption, it is sufficient (not known whether it is necessary) to factor the 256-bit modulus n, whereas to break 256-bit AES, you have to essentially run AES with the whole keyspace of 2^256 keys.
  - dspillett 14y ago
    If you are trying to brute-force guess an RSA key, the fact that the factors which produce the key should be prime (well, co-prime with respect to each other to be more precise) has the potential to greatly reduce the search space. For small keys it is practical to have precomputed what this limited search space is so of the 2^N possible keys you can be fairly sure that you only need to check a much smaller subset of them. You still have to use brute-force, but unlike with symetic methods your search space can be much smaller than the entire keyspace. For larger keys this pre computation (and storage) becomes impractical (with current tech). I have no idea off the top of my head where the point it currently becomes impractical occurs relative to 256 bit keys though.
ck2 14y ago
128bit will be crackable in 2030 with government-sized resources, last time I read about it? You can be sure taxdollars are powering mind-staggering supercomputers that the public doesn't know about right now.
pfortuny 14y ago
I honestly think that the title should be '256 bits are enough against brute-force' because otherwise this is way way way misleading.
oellegaard 14y ago
"640K ought to be enough for anybody." - Bill Gates, 1981
- tyree732 14y ago
  What exactly are you trying to imply with this quote? It seems like you're suggesting that Schneier's quote may become infamous one day should 256-bit key cryptography become crackable, which it might, but you say nothing as to how Schneier's argument could ever be wrong. He is saying that thermodynamically speaking, brute-forcing 256-bit key symmetric cryptography is unlikely to ever be possible. Do you think that to be false?
  - stcredzero 14y ago
    "1.21 × 1041 ergs/year ought to be enough for anybody." Let me just live to see the day.
- tzs 14y ago
  Gates never said that.
Tichy 14y ago
" To record a single bit by changing the state of a system requires an amount of energy no less than kT, where T is the absolute temperature of the system and k is the Boltzman constant." How does that work? It seems odd that is is independent of the size of the system.
- marcosdumay 14y ago
  That comes from the second law of thermodynamics. Setting a bit on the computer reduces its entropy, so it must dissipate enough heat to increase the entropy of the Universe by at least the same amount. Notice that this only applies to setting it into a known value. In theory there are some operations that we can do without dissipating any heat.
  - Tichy 14y ago
    But how do they know how much energy a bit requires?
    - jessaustin 14y ago
      That is technology-dependent. Mercury-filled-cylinder delay lines took more energy than modern DRAM.
    - marcosdumay 14y ago
      As I said, that's by the second law of thermodynamics... There is a nice <a href="http://en.wikipedia.org/wiki/Maxwell%27s_demon>tought http://en.wikipedia.org/wiki/Maxwell%27s_demon>tought experiment</a> linking thermodynamics to information theory. And guess what, experiments agree with the theory. After you have the theoretical framewok done, it is just a matter of applying the <a href="http://en.wikipedia.org/wiki/Boltzmann%27s_entropy_formula>Boltzmans http://en.wikipedia.org/wiki/Boltzmann%27s_entropy_formula&#... entropy formula</a>, and you are done.
    - caf 14y ago
      We know the minimum amount of energy required, because we exactly know the information content of a bit.
ppierald 14y ago
I have to note that the length and strength of your AES key is no different than the complexity of your password. Once either is compromised, then you are totally exposed. So your attacker will take the path of least resistance. He can either brute-force the key or he can just break into your server and steal your config file or his you over the head with the proverbial $5 wrench.
Jacobi 14y ago
Using brute force is not very effective on 256 keys. But this doesn't exclude the possibility of a breakthrough that reduce enormously the search space. For example even for AES there is an attack faster than brute force by a factor of about four ! http://research.microsoft.com/en-us/projects/cryptanalysis/aesbc.pdf http://research.microsoft.com/en-us/projects/cryptanalysis/a...
lectrick 14y ago
I think the 256 bits are a buffer against non-brute-force attacks, such as undiscovered algorithm weaknesses which may speed up by some factor, the cracking speed.

281 points by mef 14y ago

IMO the most vulnerable part of AES is not the side-channels but key generation. Compromise the source of entropies, preferably only for processes with specific signatures, just enough to be crackable on-demand then capture everything on the wire remotely.

dfc 14y ago

For further reference and a more detailed discussion of algo / key length selection take a look at NIST's Recommendation for Key Management [1], specifically section 5.6 "Guidance for Cryptographic Algorithm and Key-Size Selection." [1] http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57_part1_rev3_general.pdf http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57_p...

hartror 14y ago

Wow computer science meets Greg Bear, I think I need to now go write a short story featuring a supernova powered super computer.

keithpeter 14y ago
"And they strongly imply that 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." Or about a computer that isn't made of matter as we understand it...
- ars 14y ago
  How is what you said any different from what he said?
  - keithpeter 14y ago
    He said a super nova powered computer. A super nova is matter as we understand it....

cjg 14y ago

Something that many of these answers fail to address is that a 256-bit key isn't big enough, if you can do 2^128 computations. This is due to the probability of key collision. See http://en.wikipedia.org/wiki/Birthday_attack http://en.wikipedia.org/wiki/Birthday_attack Not that I'm saying 2^128 calculations isn't a lot, but compared to 2^256, it's a tiny speck.

mrb 14y ago
You are confusing different things. You are talking about hash algorithms, whereas the OP is about encryption algorithms. And it is not proper terminology to refer to hashes as "keys". What you are trying to convey, is that hash algorithms need to generate hash sizes of 512 bits if they want to make collision generation as hard as bruteforcing a 256-bit symmetric encryption key. This is true. But please use proper terminology.
grandsham 14y ago
a birthday attack reduces the number of keys you have to search by half, not half the number of bits. This means that you would have to search 2^255 keys instead of 2^256 keys.
- pjscott 14y ago
  Look again. Finding a collision in a hash function with n possible values takes an expected number of guesses proportional to sqrt(n). If n = 2^256, then sqrt(n) = (2^256)^(1/2) = 2^(256/2) = 2^128.

UnoriginalGuy 14y ago

I wish I knew more about encryption. Unfortunately it isn't a very accessible area, even if you have a degree in CS you aren't really qualified to even touch the stuff, you need a maths degree at the very least. Plus every time anyone brings up the subject the answer is always the same: "If you roll your own crypto you're an idiot." Which is not very encouraging. Likely why crypto' libraries are so antiquated and terrible.

ars 14y ago
By far the simplest encryption to understand is the factorization problem. If you have two prime number it's trivial to multiply them and get the result. Or if you have the result and one prime number, it's also trivial to divide and get the second prime number. But if you have that result, figuring out which two prime numbers divide it requires you to check every single one of them - which takes much longer. Now imagine your password is one of the prime numbers, and your secret message is converted to a different prime number. Multiply your password with the secret message and you have your result. That's the encrypted message. Without knowing what the password was, there is no feasible way to figure out what the message was - you would have to divide by every prime number looking for another prime number that evenly divides into the encrypted message. (Technically once you do that you don't know if that prime number was the message or the password.) This is the core of encryption - the trouble is the side-details can mess you up, and they are really not obvious. For example: How do you securely convert a message into a prime number? Or a password into a prime number? You can't use the entire message as one enormous prime number, that's not feasible, so you have to break it up. How do you do that properly, without leaking information? There are other issues with the math (I'm not familiar enough with encryption to even know what they are, but they are things like certain primes have patterns that make themself obvious in the result). See http://en.wikipedia.org/wiki/Semiprime http://en.wikipedia.org/wiki/Semiprime for some primes patterns to avoid. Then there are issues with the implementation - if you are on a multi user system (or a remote system) you want to make sure people can't figure out the password by watching which system resources you use, or how long things take you. And then issues with the algorithm: If you encrypt two documents with the same password it can be possible to compare them and figure out what you used. So you want to add some randomization to the password to make that impossible. But getting good random numbers isn't always easy. And you have to store that random number in the message so it can be reversed - but watch out that you didn't do that in a way that negates the advantage of the random number.

ars 14y ago

One reason for extra large keys is for headroom in case of partial breakage. Usually when a cipher is broken, they don't break it fully, but rather reduce the keyspace. By making your starting keyspace even larger you make even a broken cypher secure (up to a point).

VLM 14y ago
You are correct but its also extremely educational to graph the decrease over time, for various cryptosystems both real/pro and "roll your own". The difference between a professionally designed algo and a "roll your own" algo is the roll your own is usually extremely brittle and shatters to nothing in one discovery vs a professionally designed algo usually has multiple generations of grad students chip away maybe an average of 10 bits per decade as newer forms of analysis are slowly invented and/or declassified. If you roll your own, its at least several orders of magnitude more likely to break than a pro algo, and when it does, unlike the pro algo, it'll almost certainly snap all the way at once, so using a large keyspace just means more of an epic fail and wasted processor power. On the other hand if you use a real algo, then a loss of 20 bits per decade or whatever average really does help, so crank the keyspace to the max. So I'd have to disagree with you there, if you're using a broken (homemade?) algo don't bother with more than 8 bits or so, any more is just wasting processor time, homemade is only useful for casual obfuscation. If you're using a real algo, then, and only then, larger keyspace actually will save you over the long run...

bajsejohannes 14y ago

This a very good explaination of why 256 bits is enough against a brute force attack. The goal of breaking cryptographic systems is of course not brute force, but to reduce the actual key space you have to search. This is frequently measured in how many redundant bits you can shave off. So for AES, we might find in the future that 256 bits isn't enough after all.

p4bl0 14y ago
Actual implementations of 256 bits AES are already breakable using side-channel attacks.
- chii 14y ago
  so if that key size is increased, would these side channel attacks be either mitigated, or made impractical?
  - p4bl0 14y ago
    No that's not the way to go for countermeasures against side-channel attacks (breaking 4096 bits key in asymmetric crypto is also doable using side-channel attacks, even in the cloud [1]). Since it is a physical attack rather than a mathematical one, the countermeasures are at the physical level too: the idea is to make the cryptosystem leak less information through channel such as power consumption, computation or memory access time, electromagnetic radiation… Currently most of these countermeasures are at hardware level. [1] https://news.ycombinator.com/item?id=4865516 https://news.ycombinator.com/item?id=4865516 Edit: forgot to add reference link.

mtgx 14y ago

So even a quantum computer wouldn't be enough then?

Devilboy 14y ago
Quantum computers can, in general, provide up to a quadratic speedup over classical algorithms and WILL in fact be enough. Once we have QCs all bets are off.
- VLM 14y ago
  No, not really. Run the same example from the article with a quadratic speedup and see how scalable it is. 56 bit DES should be nervous. 256 bit AES, not so much. There is a tiresome often repeated quantum computing meme or anti-pattern where QC is a magic implementation such that "my magic can do anything I can dream of". Well no, not really. Oh it could be powerful, maybe even implementable, but not limitless.
  - apawloski 14y ago
    To clarify a bit further, only a few cryptosystems (certain public key systems) are really threatened by quantum computers. Theoretically, literature indicates that quantum computers are really good at factoring large numbers [1], and they are really good at solving discrete log problems [2]. So yes, QCs are theoretically able to crack in linear time some systems whose security depends on those problems being hard (eg ElGamal, RSA). But systems that don't rely on large primes/discrete logs (eg symmetric algorithms like AES) are not vulnerable to quantum computers. (At least not vulnerable in the "throw them out, they're useless now" sense.) In fact, there's even asymmetric cryptosystems that aren't threatened by quantum computers [3]. Again, any system that doesn't rely on large primes, or the difficulty of the discrete log problem, is not significantly threatened. [1]http://arxiv.org/abs/quant-ph/9503007 http://arxiv.org/abs/quant-ph/9503007 [2]http://epubs.siam.org/doi/abs/10.1137/S0097539795293172?journalCode=smjcat http://epubs.siam.org/doi/abs/10.1137/S0097539795293172?jour... [3]http://link.springer.com/chapter/10.1007%2F3-540-44586-2_2?LI=true http://link.springer.com/chapter/10.1007%2F3-540-44586-2_2?L...
- 14y ago

NicoJuicy 14y ago

Just use the slowest algorithm to delay brute-force attacks :)

zaptheimpaler 14y ago
I believe this is the idea behind bcrypt - it can be made slower and slower based on a parameter as larger computations become feasible.
- merijnv 14y ago
  bcrypt is a hashing algorithm for securely hashing passwords, this is something you want to be slow, yes. However, the discussion in the link is about encryption, which you want to be fast. A popular webserver serving HTTPS to thousands of clients can't afford a 10x overhead on the speed of encryption.
  - VLM 14y ago
    Encryption and decryption speeds need not be symmetric. Salted passwords are a stereotypical example... Lets say my password is "password" and I salt it with a random 8 bit value to make rainbow tables 256 times longer than unsalted. I can encrypt the salted password in one round. However on the decrypt side a salty password is going to have to average 128 rounds before a match and a worst case failure / non-match means you have to run ALL 256 rounds just to make sure. Obviously we're talking salty passwords not secure web traffic, but the point is off the shelf systems have existed for decades where the decrypt system is orders of magnitude more expensive than the encrypt system. Implementing an algo with those characteristics for web traffic "superficially seems feasible" although the details are fuzzy. As an example of a rough guess, 16 bits of salt would scale pretty well for "thousands of clients" if the server and client are more or less similar performance level (which within an order of magnitude or two is probably about right). Simple salt is the wrong algo for this job, but...
  - finnw 14y ago
    bcrypt is actually a cipher, like standard blowfish but with a much more expensive key expansion function. When you call the bcrypt "hash function", what it is really doing is performing this key expansion then using the resulting key to encrypt a constant string. GP is right - you can use bcrypt as a regular cipher, and the extended key schedule will make brute-forcing harder. It is inefficient and unnecessary though - a 384-bit key will not be attacked by brute force anyway, and blowfish's small block size of 64 bits can be problematic (you need to change the key quite frequently to prevent active attacks.)

casca 14y ago

The reason 256 bit AES keys are large enough is that in order to brute-force them, one of 2 things needs to happen: (1) We need to build computers out of something other than matter or (2) A weakness in AES must be discovered that will need to reduce the search space significantly We can disregard (1) as it will probably require changing (almost) all encryption algorithms that we currently use. (2) will most likely break all key-lengths so any use of AES will be weakened.

tcoppi 14y ago
Interestingly with regard to (2), there is actually a (totally impractical) attack on AES that only affects the larger key 192 and 256-bit versions and not 128-bit AES - http://eprint.iacr.org/2009/317 http://eprint.iacr.org/2009/317
- kzrdude 14y ago
  Does that mean that AES-256 is 'broken' in crypto terms?
  - debacle 14y ago
    No.
    - kzrdude 14y ago
      Wikipedia _does_ put AES inside Category:Broken block ciphers.. "Widely cryptanalysed ciphers like Advanced Encryption Standard are considered stronger than un-cryptanalysed ciphers even if there are impractical attacks against them."
  - finnw 14y ago
    It means that if you generate a series of keys by simply incrementing a counter, your 192- and 256-bit keys will be cracked before my 128-bit key. But if you are generating keys that way, you should probably be more concerned about attacks against the RNG that generated the starting key.

deleted 14y ago

[deleted]

mjs 14y ago

Doesn't that Schneier quote only apply to symmetric algorithms (e.g. AES)? I thought asymmetric algorithms (e.g. public/key systems like RSA, as in the original question) have completely different characteristics and rules. "NIST key management guidelines further suggest that 15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys." http://en.wikipedia.org/wiki/Key_size#Asymmetric_algorithm_key_lengths http://en.wikipedia.org/wiki/Key_size#Asymmetric_algorithm_k...

dfc 14y ago
NIST citation: Page 64 of Recommendation for Key Management [1] [1] http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57_part1_rev3_general.pdf http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57_p...
aneesh 14y ago
Although you're right that a 256-bit RSA key is weaker than a 256-bit AES key, this is not an intrinsic property of symmetric vs asymmetric encryption. It has to do with how you search the key space. To break 256-bit RSA encryption, it is sufficient (not known whether it is necessary) to factor the 256-bit modulus n, whereas to break 256-bit AES, you have to essentially run AES with the whole keyspace of 2^256 keys.
- dspillett 14y ago
  If you are trying to brute-force guess an RSA key, the fact that the factors which produce the key should be prime (well, co-prime with respect to each other to be more precise) has the potential to greatly reduce the search space. For small keys it is practical to have precomputed what this limited search space is so of the 2^N possible keys you can be fairly sure that you only need to check a much smaller subset of them. You still have to use brute-force, but unlike with symetic methods your search space can be much smaller than the entire keyspace. For larger keys this pre computation (and storage) becomes impractical (with current tech). I have no idea off the top of my head where the point it currently becomes impractical occurs relative to 256 bit keys though.

ck2 14y ago

128bit will be crackable in 2030 with government-sized resources, last time I read about it? You can be sure taxdollars are powering mind-staggering supercomputers that the public doesn't know about right now.

pfortuny 14y ago

I honestly think that the title should be '256 bits are enough against brute-force' because otherwise this is way way way misleading.

oellegaard 14y ago

"640K ought to be enough for anybody." - Bill Gates, 1981

tyree732 14y ago
What exactly are you trying to imply with this quote? It seems like you're suggesting that Schneier's quote may become infamous one day should 256-bit key cryptography become crackable, which it might, but you say nothing as to how Schneier's argument could ever be wrong. He is saying that thermodynamically speaking, brute-forcing 256-bit key symmetric cryptography is unlikely to ever be possible. Do you think that to be false?
- stcredzero 14y ago
  "1.21 × 1041 ergs/year ought to be enough for anybody." Let me just live to see the day.
tzs 14y ago
Gates never said that.

Tichy 14y ago

" To record a single bit by changing the state of a system requires an amount of energy no less than kT, where T is the absolute temperature of the system and k is the Boltzman constant." How does that work? It seems odd that is is independent of the size of the system.

marcosdumay 14y ago
That comes from the second law of thermodynamics. Setting a bit on the computer reduces its entropy, so it must dissipate enough heat to increase the entropy of the Universe by at least the same amount. Notice that this only applies to setting it into a known value. In theory there are some operations that we can do without dissipating any heat.
- Tichy 14y ago
  But how do they know how much energy a bit requires?
  - jessaustin 14y ago
    That is technology-dependent. Mercury-filled-cylinder delay lines took more energy than modern DRAM.
  - marcosdumay 14y ago
    As I said, that's by the second law of thermodynamics... There is a nice <a href="http://en.wikipedia.org/wiki/Maxwell%27s_demon>tought http://en.wikipedia.org/wiki/Maxwell%27s_demon>tought experiment</a> linking thermodynamics to information theory. And guess what, experiments agree with the theory. After you have the theoretical framewok done, it is just a matter of applying the <a href="http://en.wikipedia.org/wiki/Boltzmann%27s_entropy_formula>Boltzmans http://en.wikipedia.org/wiki/Boltzmann%27s_entropy_formula&#... entropy formula</a>, and you are done.
  - caf 14y ago
    We know the minimum amount of energy required, because we exactly know the information content of a bit.

ppierald 14y ago

I have to note that the length and strength of your AES key is no different than the complexity of your password. Once either is compromised, then you are totally exposed. So your attacker will take the path of least resistance. He can either brute-force the key or he can just break into your server and steal your config file or his you over the head with the proverbial $5 wrench.

Jacobi 14y ago

Using brute force is not very effective on 256 keys. But this doesn't exclude the possibility of a breakthrough that reduce enormously the search space. For example even for AES there is an attack faster than brute force by a factor of about four ! http://research.microsoft.com/en-us/projects/cryptanalysis/aesbc.pdf http://research.microsoft.com/en-us/projects/cryptanalysis/a...

lectrick 14y ago

I think the 256 bits are a buffer against non-brute-force attacks, such as undiscovered algorithm weaknesses which may speed up by some factor, the cracking speed.