3 ms·

The article is super misleading. First of all it's no secret that quantum attacks aren't a big problem for hash functions, there's "only" a need to switch to l

by hannob 10y ago

The article is super misleading. First of all it's no secret that quantum attacks aren't a big problem for hash functions, there's "only" a need to switch to longer outputs. The major impact of quantum computers will be shor's algorithm, which affects public key algorithms. But it seems the author of this article also didn't really understand the paper linked. It only looks at preimage attacks. We generally expect hash functions to be resistant to collision attacks, which is a much stronger statement. And here things aren't that rosy. 256 bit algs have by design only 128 bit of collision resistance. Grover's alg reduces that to 64 bit, which is not comfortably secure. Granted, one would need a pretty big cluster of quantum computers to practically break that, but if you go postquantum you should probably better go to 512 bit algs. However none of that changes with this new paper.

acqq 10y ago
As far as I understand, actually both the hashes and symmetric ciphers will continue to work "after quantum" and "just" increasing the number of bits can be enough to keep them secure. And the whole cryptography can be (re)based on these two? Which doesn't sound too bad, just that some of the now used systems will have to be replaced. But first we have to see how many qubits can technically be kept functioning. Anybody knows the current record? Is it better than March 2016: http://www.scottaaronson.com/blog/?p=2673 http://www.scottaaronson.com/blog/?p=2673 "Briefly, the new work uses Kitaev’s version of Shor’s factoring algorithm, running on an ion-trap quantum computer with five calcium ions, to prove that, with at least 90% confidence, 15 equals 3×5." "In any case, regardless of how long it takes until we can factor enormous numbers like 91, congratulations to the MIT and Innsbruck groups on what’s certainly progress toward scalable ion-trap QC!" It's not 91 bits, it's 91 as the number, that is, 7 bits as a goal, 4 bits (for the number 15) in the successful demonstration.
- JohnStrange 10y ago
  AES as standard has only up to 256 bit keys, and I haven't followed closely what was going on in crypto lately. Which secure 512 or 1024 bit symmetric encryption algorithm should I use to be 'quantum proof'?
  - hannob 10y ago
    aes256 is fine. This is a bit different for block ciphers and hashes. The very brief / simplified explanation: Block ciphers have a security level of their key size, so aes256 has a prequantum security level of 256 bit, which means a postquantum security level of 128 bit. Hashes however have - due to the requirement for collision security and the birthday paradox - a security level half of their size. Therefore for 128 bit prequantum security you need a 256 bit hash and for 128 bit postquantum security you need a 512 bit hash.
  - acqq 10y ago
    As far as I know, if you just use symmetric AES 256 it shouldn't be a problem for a while. The potential (I repeat that, see Aaronson's post I linked to earlier) problem is "just" the use of the public keys. And combining the lower-bit algorithms into the bigger ones is relatively easy, as an example from the 56-bit DES a 3DES with security of around 112 bits was made and (is still) used: https://en.wikipedia.org/wiki/Triple_DES https://en.wikipedia.org/wiki/Triple_DES edit: re: the early collisions with 64-bits etc: If I understand, the problem happens only when the soon-enough rekeying doesn't: https://sweet32.info/ https://sweet32.info/ I agree it's better to avoid these altogether.
    - CiPHPerCoder 10y ago
      But don't use 3DES, since the DES block size is 64 bits and you get collisions (e.g. in CBC mode) after 2^32 blocks.
- SilasX 10y ago
  >As far as I understand, actually both the hashes and symmetric ciphers will continue to work "after quantum" and "just" increasing the number of bits can be enough to keep them secure. And the whole cryptography can be (re)based on these two? I don't think so -- that doesn't cover public key cryptography. I'm pretty sure that one-way function and a symmetric cipher (which is basically just a secure RNG) are enough to produce a public key cryptosystem, which requires a trapdoor one-way function.
geofft 10y ago
This question is probably ill-formed, but once we have working quantum computers, does it become easier to cryptanalyze SHA-3 for algorithmic weaknesses?
pbsd 10y ago
Grover's algorithm does not help much against collisions; Brassard-Hoyer-Tapp (which does use Grover internally) does (at ~2^85 time), but requires a large (also ~2^85) amount of quantum storage. Basically: generate ~2^85 random strings and respective hashes, then use Grover to find one new preimage in ~2^85 (instead of classical ~2^170) time. In practice classical rho collision-finding is more resource-efficient: replace the crazy ~2^85 storage by ~2^85 small memoryless computing units, and find a collision in 2^128 / 2^85 ~ 2^43 time. Or match the quantum time with only ~2^43 computing units, and negligible storage.
- hannob 10y ago
  It seems you're right and I'm wrong. The situation for grover and hash collisions seems to be a bit more complex than I thought. Learned something... and feel bad that my slightly wrong comment got upvoted so much :-)

by hannob 10y ago

acqq 10y ago

As far as I understand, actually both the hashes and symmetric ciphers will continue to work "after quantum" and "just" increasing the number of bits can be enough to keep them secure. And the whole cryptography can be (re)based on these two? Which doesn't sound too bad, just that some of the now used systems will have to be replaced. But first we have to see how many qubits can technically be kept functioning. Anybody knows the current record? Is it better than March 2016: http://www.scottaaronson.com/blog/?p=2673 http://www.scottaaronson.com/blog/?p=2673 "Briefly, the new work uses Kitaev’s version of Shor’s factoring algorithm, running on an ion-trap quantum computer with five calcium ions, to prove that, with at least 90% confidence, 15 equals 3×5." "In any case, regardless of how long it takes until we can factor enormous numbers like 91, congratulations to the MIT and Innsbruck groups on what’s certainly progress toward scalable ion-trap QC!" It's not 91 bits, it's 91 as the number, that is, 7 bits as a goal, 4 bits (for the number 15) in the successful demonstration.

JohnStrange 10y ago
AES as standard has only up to 256 bit keys, and I haven't followed closely what was going on in crypto lately. Which secure 512 or 1024 bit symmetric encryption algorithm should I use to be 'quantum proof'?
- hannob 10y ago
  aes256 is fine. This is a bit different for block ciphers and hashes. The very brief / simplified explanation: Block ciphers have a security level of their key size, so aes256 has a prequantum security level of 256 bit, which means a postquantum security level of 128 bit. Hashes however have - due to the requirement for collision security and the birthday paradox - a security level half of their size. Therefore for 128 bit prequantum security you need a 256 bit hash and for 128 bit postquantum security you need a 512 bit hash.
- acqq 10y ago
  As far as I know, if you just use symmetric AES 256 it shouldn't be a problem for a while. The potential (I repeat that, see Aaronson's post I linked to earlier) problem is "just" the use of the public keys. And combining the lower-bit algorithms into the bigger ones is relatively easy, as an example from the 56-bit DES a 3DES with security of around 112 bits was made and (is still) used: https://en.wikipedia.org/wiki/Triple_DES https://en.wikipedia.org/wiki/Triple_DES edit: re: the early collisions with 64-bits etc: If I understand, the problem happens only when the soon-enough rekeying doesn't: https://sweet32.info/ https://sweet32.info/ I agree it's better to avoid these altogether.
  - CiPHPerCoder 10y ago
    But don't use 3DES, since the DES block size is 64 bits and you get collisions (e.g. in CBC mode) after 2^32 blocks.
SilasX 10y ago
>As far as I understand, actually both the hashes and symmetric ciphers will continue to work "after quantum" and "just" increasing the number of bits can be enough to keep them secure. And the whole cryptography can be (re)based on these two? I don't think so -- that doesn't cover public key cryptography. I'm pretty sure that one-way function and a symmetric cipher (which is basically just a secure RNG) are enough to produce a public key cryptosystem, which requires a trapdoor one-way function.

geofft 10y ago

This question is probably ill-formed, but once we have working quantum computers, does it become easier to cryptanalyze SHA-3 for algorithmic weaknesses?

pbsd 10y ago

Grover's algorithm does not help much against collisions; Brassard-Hoyer-Tapp (which does use Grover internally) does (at ~2^85 time), but requires a large (also ~2^85) amount of quantum storage. Basically: generate ~2^85 random strings and respective hashes, then use Grover to find one new preimage in ~2^85 (instead of classical ~2^170) time. In practice classical rho collision-finding is more resource-efficient: replace the crazy ~2^85 storage by ~2^85 small memoryless computing units, and find a collision in 2^128 / 2^85 ~ 2^43 time. Or match the quantum time with only ~2^43 computing units, and negligible storage.

hannob 10y ago
It seems you're right and I'm wrong. The situation for grover and hash collisions seems to be a bit more complex than I thought. Learned something... and feel bad that my slightly wrong comment got upvoted so much :-)