7 ms·

If this can exhaust the DES keyspace in 26hrs, what’s the time to exhaust triple-DES?

by xref 6y ago

LeoPanthera 6y ago
2̵6̵^̵3̵ ̵=̵ ̵1̵7̵,̵5̵7̵6̵ ̵h̵o̵u̵r̵s̵ ̵=̵ ̵2̵ ̵y̵e̵a̵r̵s̵ I am wrong.
- segfaultbuserr 6y ago
  It's a great underestimation. Breaking 3DES is not 3 times more complex than DES, but 2^56 times more complex. 26 x 2^56 = 1873497444986126336 hours. It's why we still trust 128-bit encryption when the total computing power of humanity already exceeded 2^80 operations per seconds. It's frustrating that I has to refute the argument many times: "If 80-bit is insecure today, 128-bit will be insecure soon any cryptosystem can only guarantee a few decades of security because Moore's Law..." No, it's not how it works (although quantum computers will make 128-bit insecure, but the solution is already available today: 256-bit). The human brain is not wired to understand exponential growth.
  - chmod775 6y ago
    >It's frustrating that I has to refute the argument many times: "If 80-bit is insecure today, 128-bit will be insecure soon any cryptosystem can only guarantee a few decades of security because Moore's Law..." I believe you are doing the people you are talking about an injustice here, because assuming Moore's Law held, we would be doubling computing power every two years (well, transistors really). Doubling... what comes to mind... Ah yes! Bits! Because with every bit you are doubling the number of keys, meaning that you could crack an 81 bit key today in the same it would have taken you to crack an 80 bit key two years ago. So that gives you 100 years, or about 10 decades, to go from 80 bit to 128 bits. Or, in other words, Moore's law is also about exponential growth. So if those people you quoted did indeed say "a few decades" they were right on.
    - segfaultbuserr 6y ago
      I don't agree that a century is "a few decades", my understanding of a "few decades" (and I believe, the person who was discussing this problem with me) is no more than 50 years. If you are clearly talking at the time scale of a century, I'll have no problem with this statement.
    - tialaramex 6y ago
      > assuming Moore's Law held, we would be doubling computing power every two years So the correct realisation here is that Moore's law (an observation by an engineer) doesn't trump laws of physics. The transistors Moore was talking about have to be made from something. When they're made of a lump of material you can actually see under a microscope this feels both very real and as if it could be shrunk indefinitely. Just keep cutting that material in half! But it can't. Matter is made of atoms. If you double the number of transistors you must halve the number of atoms in each transistor. Today's transistors have a few hundred atoms in them. Guess what happens when there's one atom in each transistor and you try to halve that? There's no such thing as "half" an atom, what you've got there isn't an atom any more, and so what you're making isn't a transistor. The argument that we will never need larger symmetric encryption isn't based on ignorance of Moore's law, it's based on knowledge of the laws of physics. You can't make a 256-bit AES cracker by "just" converting the entire planet into Computronium, that's not enough compute power.
RcouF1uZ4gsC 6y ago
triple-DES has a 112bit key space. So it would take 26 hours * 2^56 which is a very long time. UPDATE: A quick calculation on Google yields: (2^56) * 26 hours = 2.13727751 × 10^14 years
dgacmu 6y ago
The triple-DES keyspace is 168 bits, vs 56 bits, so 2^112 times longer to do a complete scan of the keyspace. If you have a known plaintext and can do a meet-in-the-middle attack, it's approximately "only" 2^56 times longer. I'm not aware of words for the length of time this would take other than "past the heat death of the sun".
- segfaultbuserr 6y ago
  Yes. This is completely true if we assume there are no large quantum computers with practical error correction - we probably won't have one in the foreseeable future. But beware that a sufficiently large quantum computer will be able to run Glover's algorithm and reducing the brute-force attempts required from N to sqrt(N), making all 128-bit ciphers be 64-bit and turning 3DES back to DES. And I won't be surprised if it happens within my lifetime. But the solution for symmetric encryption is simple, just use 256-bit ciphers, fast and effective, and many are already in use today. Public-key encryption is the real trouble, many candidates, much higher cost, somewhat untested constructions.
  - kevin_thibedeau 6y ago
    AES-256 has issues if you're planning for long term security: https://soatok.blog/2020/05/13/why-aes-gcm-sucks/ https://soatok.blog/2020/05/13/why-aes-gcm-sucks/
    - segfaultbuserr 6y ago
      It's indeed a potential concern, basically the quantum edition of the Sweet32 attack. History will repeat itself (Although I wonder how much pre-quantum AES-256 traffic will really be vulnerable in practice. I think an interactive attack will be very unlikely, the concern is mostly pre-existing ciphertext. I guess most OpenPGP traffic will probably be secure? And even HTTPS will be okayish as long as you don't send too much data in a single connection? It would be an interesting study...) Fortunately, start using ChaCha20 or XChaCha20 is easy, unlike inventing and deploying a new public-key cryptosystem. So symmetric ciphers are still an "easy" problem. [0] https://sweet32.info/ https://sweet32.info/

If this can exhaust the DES keyspace in 26hrs, what’s the time to exhaust triple-DES?

by xref 6y ago

If this can exhaust the DES keyspace in 26hrs, what’s the time to exhaust triple-DES?

LeoPanthera 6y ago

2̵6̵^̵3̵ ̵=̵ ̵1̵7̵,̵5̵7̵6̵ ̵h̵o̵u̵r̵s̵ ̵=̵ ̵2̵ ̵y̵e̵a̵r̵s̵ I am wrong.

segfaultbuserr 6y ago
It's a great underestimation. Breaking 3DES is not 3 times more complex than DES, but 2^56 times more complex. 26 x 2^56 = 1873497444986126336 hours. It's why we still trust 128-bit encryption when the total computing power of humanity already exceeded 2^80 operations per seconds. It's frustrating that I has to refute the argument many times: "If 80-bit is insecure today, 128-bit will be insecure soon any cryptosystem can only guarantee a few decades of security because Moore's Law..." No, it's not how it works (although quantum computers will make 128-bit insecure, but the solution is already available today: 256-bit). The human brain is not wired to understand exponential growth.
- chmod775 6y ago
  >It's frustrating that I has to refute the argument many times: "If 80-bit is insecure today, 128-bit will be insecure soon any cryptosystem can only guarantee a few decades of security because Moore's Law..." I believe you are doing the people you are talking about an injustice here, because assuming Moore's Law held, we would be doubling computing power every two years (well, transistors really). Doubling... what comes to mind... Ah yes! Bits! Because with every bit you are doubling the number of keys, meaning that you could crack an 81 bit key today in the same it would have taken you to crack an 80 bit key two years ago. So that gives you 100 years, or about 10 decades, to go from 80 bit to 128 bits. Or, in other words, Moore's law is also about exponential growth. So if those people you quoted did indeed say "a few decades" they were right on.
  - segfaultbuserr 6y ago
    I don't agree that a century is "a few decades", my understanding of a "few decades" (and I believe, the person who was discussing this problem with me) is no more than 50 years. If you are clearly talking at the time scale of a century, I'll have no problem with this statement.
  - tialaramex 6y ago
    > assuming Moore's Law held, we would be doubling computing power every two years So the correct realisation here is that Moore's law (an observation by an engineer) doesn't trump laws of physics. The transistors Moore was talking about have to be made from something. When they're made of a lump of material you can actually see under a microscope this feels both very real and as if it could be shrunk indefinitely. Just keep cutting that material in half! But it can't. Matter is made of atoms. If you double the number of transistors you must halve the number of atoms in each transistor. Today's transistors have a few hundred atoms in them. Guess what happens when there's one atom in each transistor and you try to halve that? There's no such thing as "half" an atom, what you've got there isn't an atom any more, and so what you're making isn't a transistor. The argument that we will never need larger symmetric encryption isn't based on ignorance of Moore's law, it's based on knowledge of the laws of physics. You can't make a 256-bit AES cracker by "just" converting the entire planet into Computronium, that's not enough compute power.

RcouF1uZ4gsC 6y ago

triple-DES has a 112bit key space. So it would take 26 hours * 2^56 which is a very long time. UPDATE: A quick calculation on Google yields: (2^56) * 26 hours = 2.13727751 × 10^14 years

dgacmu 6y ago

The triple-DES keyspace is 168 bits, vs 56 bits, so 2^112 times longer to do a complete scan of the keyspace. If you have a known plaintext and can do a meet-in-the-middle attack, it's approximately "only" 2^56 times longer. I'm not aware of words for the length of time this would take other than "past the heat death of the sun".

segfaultbuserr 6y ago
Yes. This is completely true if we assume there are no large quantum computers with practical error correction - we probably won't have one in the foreseeable future. But beware that a sufficiently large quantum computer will be able to run Glover's algorithm and reducing the brute-force attempts required from N to sqrt(N), making all 128-bit ciphers be 64-bit and turning 3DES back to DES. And I won't be surprised if it happens within my lifetime. But the solution for symmetric encryption is simple, just use 256-bit ciphers, fast and effective, and many are already in use today. Public-key encryption is the real trouble, many candidates, much higher cost, somewhat untested constructions.
- kevin_thibedeau 6y ago
  AES-256 has issues if you're planning for long term security: https://soatok.blog/2020/05/13/why-aes-gcm-sucks/ https://soatok.blog/2020/05/13/why-aes-gcm-sucks/
  - segfaultbuserr 6y ago
    It's indeed a potential concern, basically the quantum edition of the Sweet32 attack. History will repeat itself (Although I wonder how much pre-quantum AES-256 traffic will really be vulnerable in practice. I think an interactive attack will be very unlikely, the concern is mostly pre-existing ciphertext. I guess most OpenPGP traffic will probably be secure? And even HTTPS will be okayish as long as you don't send too much data in a single connection? It would be an interesting study...) Fortunately, start using ChaCha20 or XChaCha20 is easy, unlike inventing and deploying a new public-key cryptosystem. So symmetric ciphers are still an "easy" problem. [0] https://sweet32.info/ https://sweet32.info/