4 ms·

That is good because, provided there is not some enormous leap forward in number theory in the meantime, they can keep working on trying to break 256-bit key RS

That is good because, provided there is not some enormous leap forward in number theory in the meantime, they can keep working on trying to break 256-bit key RSA encryption "indefinitely" as well thanks to a higher law by the name of thermodynamics.

mindslight 13y ago
256-bit RSA, eh?
- croikle 13y ago
  To expand on this a little, 256-bit RSA is easily crackable, since there are good algorithms for integer factorization. You need a significant increase in key length to get equivalent security to symmetric keys: Wikipedia claims 3072-bit RSA ~ 128-bit symmetric, 15360-bit RSA ~ 256-bit symmetric. [0] [0]: https://en.wikipedia.org/wiki/Key_size#Asymmetric_algorithm_key_lengths https://en.wikipedia.org/wiki/Key_size#Asymmetric_algorithm_...
grecy 13y ago
Wait 25 years until Moore's Law catches up, and they can break all those 256-bit encrypted things you did back in 2013.
- thomasjames 13y ago
  From Schneier in "Applied Cryptography" (1996): "Longer key lengths are better, but only up to a point. AES will have 128-bit, 192-bit, and 256-bit key lengths. This is far longer than needed for the foreseeable future. In fact, we cannot even imagine a world where 256-bit brute force searches are possible. It requires some fundamental breakthroughs in physics and our understanding of the universe. One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. 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. (Stick with me; the physics lesson is almost over.) Given that k = 1.38 × 10^−16 erg/K, and that the ambient temperature of the universe is 3.2 Kelvin, an ideal computer running at 3.2 K would consume 4.4 × 10−16 ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump. Now, the annual energy output of our sun is about 1.21 × 10^41 ergs. This is enough to power about 2.7 × 10^56 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2^192. Of course, it wouldn't have the energy left over to perform any useful calculations with this counter. But that's just one star, and a measly one at that. A typical supernova releases something like 1^051 ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states. These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. 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."
  - ISL 13y ago
    I've seen this argument quoted a couple of times and blindly accepted it as a traditional Fermi-style attack on the problem. This is the first time I've pondered the implementation. Schneier's argument that 3.2K is a limit is perhaps not the best one? Dilution fridges let you into the millikelvin quickly. Optical cooling can readily reach nanokelvin. Power dissipation remains a significant problem, but the power requirement is reduced by ~10^9. From the quantum-computing side of things, it's not that crazy to imagine a 256 bit quantum computer, especially if you have a GDP-caliber budget. Researchers worldwide are working hard on the relevant technological precursors.
    - peterwaller 13y ago
      I'm under the impression that quantum computers buy you a square root. So instead of doubling the number of bits in your key to improve the strength of a key by a ludicrous amount, you should quadruple them. In addition to this, I don't know how well quantum computers help against (good) symmetric encryption. They help against certain types of PKI because they give you the aforementioned speedup in factoring large integers. However, I think Schneier's argument holds, because brute forcing 2^256 possible keys is.. well, see the argument above about forcing a counter through all those states. (apologies for not citing sources. Hopefully someone more knowledgeable can weigh in)
      - archgoon 13y ago
        For AES you are correct. The best known quantum attack is Grover's Search Algorithm (but emphasis on 'known' here), reducing the key space to 2^128. RSA, however, is based on prime factors, so it can be broken with Shor's Algorithm, which means it will take on the order of (256)^3 operations.
  - croikle 13y ago
    Limiting the energy source to a single star is weak. If you use a whole galaxy (or several) you can easily bring that up to 256 bits. For example, the Milky Way has on the order of 10^11 stars; most of those aren't supernova-sized, but if we use a few million galaxies we can get that many. That gives you an extra 37 bits, bringing the counter to 256. So, if you have terrifically huge enemies, who will burn galaxies to get at your secrets, you might want to use a few more bits. You might worry about quantum computers, too, since afaik Grover's algorithm halves effective key size.
- assafs 13y ago
  Even if Moore's Law holds up that long, Second Law of Thermodynamics says you can't brute-force 256-bit keys[1]. However, it's entirely possible (though unlikely) that actual, significant progress will be made either in DLP or in attacking AES/RC4 -- at which case, yeah, that data is as good as clear. [1]https://www.schneier.com/blog/archives/2009/09/the_doghouse_cr.html https://www.schneier.com/blog/archives/2009/09/the_doghouse_...

mindslight 13y ago

256-bit RSA, eh?

croikle 13y ago
To expand on this a little, 256-bit RSA is easily crackable, since there are good algorithms for integer factorization. You need a significant increase in key length to get equivalent security to symmetric keys: Wikipedia claims 3072-bit RSA ~ 128-bit symmetric, 15360-bit RSA ~ 256-bit symmetric. [0] [0]: https://en.wikipedia.org/wiki/Key_size#Asymmetric_algorithm_key_lengths https://en.wikipedia.org/wiki/Key_size#Asymmetric_algorithm_...

grecy 13y ago

Wait 25 years until Moore's Law catches up, and they can break all those 256-bit encrypted things you did back in 2013.

thomasjames 13y ago
From Schneier in "Applied Cryptography" (1996): "Longer key lengths are better, but only up to a point. AES will have 128-bit, 192-bit, and 256-bit key lengths. This is far longer than needed for the foreseeable future. In fact, we cannot even imagine a world where 256-bit brute force searches are possible. It requires some fundamental breakthroughs in physics and our understanding of the universe. One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. 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. (Stick with me; the physics lesson is almost over.) Given that k = 1.38 × 10^−16 erg/K, and that the ambient temperature of the universe is 3.2 Kelvin, an ideal computer running at 3.2 K would consume 4.4 × 10−16 ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump. Now, the annual energy output of our sun is about 1.21 × 10^41 ergs. This is enough to power about 2.7 × 10^56 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2^192. Of course, it wouldn't have the energy left over to perform any useful calculations with this counter. But that's just one star, and a measly one at that. A typical supernova releases something like 1^051 ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states. These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. 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."
- ISL 13y ago
  I've seen this argument quoted a couple of times and blindly accepted it as a traditional Fermi-style attack on the problem. This is the first time I've pondered the implementation. Schneier's argument that 3.2K is a limit is perhaps not the best one? Dilution fridges let you into the millikelvin quickly. Optical cooling can readily reach nanokelvin. Power dissipation remains a significant problem, but the power requirement is reduced by ~10^9. From the quantum-computing side of things, it's not that crazy to imagine a 256 bit quantum computer, especially if you have a GDP-caliber budget. Researchers worldwide are working hard on the relevant technological precursors.
  - peterwaller 13y ago
    I'm under the impression that quantum computers buy you a square root. So instead of doubling the number of bits in your key to improve the strength of a key by a ludicrous amount, you should quadruple them. In addition to this, I don't know how well quantum computers help against (good) symmetric encryption. They help against certain types of PKI because they give you the aforementioned speedup in factoring large integers. However, I think Schneier's argument holds, because brute forcing 2^256 possible keys is.. well, see the argument above about forcing a counter through all those states. (apologies for not citing sources. Hopefully someone more knowledgeable can weigh in)
    - archgoon 13y ago
      For AES you are correct. The best known quantum attack is Grover's Search Algorithm (but emphasis on 'known' here), reducing the key space to 2^128. RSA, however, is based on prime factors, so it can be broken with Shor's Algorithm, which means it will take on the order of (256)^3 operations.
- croikle 13y ago
  Limiting the energy source to a single star is weak. If you use a whole galaxy (or several) you can easily bring that up to 256 bits. For example, the Milky Way has on the order of 10^11 stars; most of those aren't supernova-sized, but if we use a few million galaxies we can get that many. That gives you an extra 37 bits, bringing the counter to 256. So, if you have terrifically huge enemies, who will burn galaxies to get at your secrets, you might want to use a few more bits. You might worry about quantum computers, too, since afaik Grover's algorithm halves effective key size.
assafs 13y ago
Even if Moore's Law holds up that long, Second Law of Thermodynamics says you can't brute-force 256-bit keys[1]. However, it's entirely possible (though unlikely) that actual, significant progress will be made either in DLP or in attacking AES/RC4 -- at which case, yeah, that data is as good as clear. [1]https://www.schneier.com/blog/archives/2009/09/the_doghouse_cr.html https://www.schneier.com/blog/archives/2009/09/the_doghouse_...