4 ms·

You should already have switched to AES256 or better. The data can be captured and processed once a machine is available.

cyphar 7y ago
The risk with quantum computers is with public-key cryptography (where all modern PK crypto is broken with a sufficiently-powerful quantum computers). It is believed that attacks with a quantum computer against symmetric-key cryptography (like AES) gain no better than a square-root improvement (meaning that doubling key sizes eliminates the risk).
- ChrisLomont 7y ago
  >where all modern PK crypto is broken with a sufficiently-powerful quantum computers This isn't true - only methods based on Discrete Log are at risk, which includes RSA and ECC, but there are a lot of PK algos that are not at risk, like NTRU. Here's a bunch of stuff related https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography
  - cyphar 7y ago
    PQ-Crypto is still a very young research area. There is no widespread (or even niche) use of PQ-Crypto algorithms, no consensus on how safe any of the proposed algorithms are (and many proposals were found to be exceptionally broken -- on classical hardware -- within weeks of their submission[1]). I'm not really sure it's fair to say that just because there are some on-paper algorithms (which have no usage outside academia at the moment) that might solve the problem that it's false to say that "all modern PK crypto is broken with quantum attackers". But if you prefer, you could imagine that I said "all modern PK crypto [that is actually in use today] is broken". Because, at the end of the day, that's all that really matters. [As an aside, for RSA the security is provided by the hardness of factorisation which also breaks under QC attackers, not discrete log (it's discrete log for DH, and EC discrete log for ECDH).] [1]: https://www.youtube.com/watch?v=ZCmnQR3_qWg https://www.youtube.com/watch?v=ZCmnQR3_qWg
    - sweis 7y ago
      It not exactly a young research area. We have had post-quantum public key cryptosystems based on linear codes for over 40 years. Classic McEliece (https://classic.mceliece.org https://classic.mceliece.org) was created in 1978 and is in the 2nd round of NIST's PQ-crypto contest ( https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions https://csrc.nist.gov/projects/post-quantum-cryptography/rou...). The PQCrypto conference started 13 years ago: https://pqcrypto.org/conferences.html https://pqcrypto.org/conferences.html Chrome ran large scale experiments with NewHope support 3 years ago: https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html https://security.googleblog.com/2016/07/experimenting-with-p...
      - deleted 7y ago
        [deleted]
    - ChrisLomont 7y ago
      Shor factoring for RSA works by period finding, which is all modern PK crypto discrete log. Read the wiki page. I wrote a decently cited paper summarizing all this when I worked in quantum computing research around 2005, on arxiv. Track it down if you’re interested. I’ve followed the field for decades, giving talks once in a while on it. So I do know a bit of the details. The computational power of QC is very well studied. It is certain that it cannot crack certain (most) problems any faster than a classical computer. Thus algorithms not isomorphic to the few problems QC is better at are just as secure on both classical and quantum computers. There is consensus on this - there is no question about it. >all modern PK crypto [that is actually in use today] NTRU is an IEEE standard, and is in wolfSSL, which is on many platforms. NTRU is also used in many commercial products from chat to relays. Other non DLP methods are also used in commercial products and standards.
      - cyphar 7y ago
        > Shor factoring for RSA works by period finding, which is all modern PK crypto discrete log. Read the wiki page. But is it not the case that the original Shor algorithm was specifically about using periodicity for integer factorisation (and the wiki page for "RSA problem"[1] also refers to integer factorisation, not discrete log). > It is certain that it cannot crack certain (most) problems any faster than a classical computer. Yes, I was already well-aware of that. My point was that the overwhelming majority of PK crypto used today depends on the hardness of problems that are exponentially accelerated by QC algorithms. > NTRU is an IEEE standard, and is in wolfSSL, which is on many platforms. Okay, maybe then it has some non-academic use. But the overwhelming majority of PK crypto in use today (TLS, PGP, the vast majority of E2EE systems) is not secure against quantum attackers. Can we agree on that at least? [1]: https://en.m.wikipedia.org/wiki/RSA_problem https://en.m.wikipedia.org/wiki/RSA_problem
  - mjevans 7y ago
    With 'the unknown' I prefer to focus very strongly on where known and theoretically known truths are. Based on your statement (I don't recall offhand), it might be said that it is widely believed RSA and ECC algorithms are vulnerable in a world where quantum computing is plausible. The safety of other systems would require a more rigorous proof; the absence of known vulnerability does not imply safety. I am not an expert in this field, but the understanding I have from the last time I spent an afternoon reading about it might be summarized as: * Known/Suspected vulnerable systems use "classically-hard" problems with vulnerability based on small key (or subkey) size. * Most of the 'theoretically more secure' systems make the working set size large enough, and complex enough, to eclipse the scope of stable quantum computers. * Thus, the two attack vectors to consider for 'post quantum' cryptography are currently unthinkably large systems or weaknesses in algorithms that allow for attacking a subset which does fit within a quantum system. If my understanding/memory is incorrect updates would be very helpful.
    - ChrisLomont 7y ago
      The other systems are provably as secure on quantum computers as they are on classical computers. Quantum complexity classes are well mapped out, and it s known certain things cannot b one faster on quantum. Related to crypto, only systems reducible to DLP (well, technically Hidden Subgroup Problem but only for certain groups) are affected. This has the rigor of mathematical proof: it’s not handwaving. And many systems do not reduce to this.
  - steelframe 7y ago
    > only methods based on Discrete Log are at risk, which includes RSA and ECC RSA's security is based on the presumption that factorization is hard, which is a different problem than finding the discrete log. To attack RSA you would use Shor's algorithm, and to attack ECC you would use Grover's. See page 2 of this paper: https://arxiv.org/pdf/1804.00200.pdf https://arxiv.org/pdf/1804.00200.pdf
    - ChrisLomont 7y ago
      See my answer above. Shoes factoring is efficient because period finding mod N is exactly discrete log. To attack ECC it is directly discrete log, where quantum is exponentially faster than classical. Grover reduces unstructured search from O(N) to O(sort N), only a quadratic speedup, insufficient to weaken crypto more than 1 bit out of a key length, which is too weak to be a threat. Page 2 of your link does not state how QC attacks problems; it dies say ECC is discrete log, though. Both systems break precisely because QC solve DLP in these cases exponentially faster than classical, and this is all that’s needed.
ccozan 7y ago
But maybe then is already irrelevant?
steelframe 7y ago
> AES256 or better I'm not aware of any symmetric cipher that the industry in broad consensus would consider "better" than AES-256.

cyphar 7y ago

The risk with quantum computers is with public-key cryptography (where all modern PK crypto is broken with a sufficiently-powerful quantum computers). It is believed that attacks with a quantum computer against symmetric-key cryptography (like AES) gain no better than a square-root improvement (meaning that doubling key sizes eliminates the risk).

ChrisLomont 7y ago
>where all modern PK crypto is broken with a sufficiently-powerful quantum computers This isn't true - only methods based on Discrete Log are at risk, which includes RSA and ECC, but there are a lot of PK algos that are not at risk, like NTRU. Here's a bunch of stuff related https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography
- cyphar 7y ago
  PQ-Crypto is still a very young research area. There is no widespread (or even niche) use of PQ-Crypto algorithms, no consensus on how safe any of the proposed algorithms are (and many proposals were found to be exceptionally broken -- on classical hardware -- within weeks of their submission[1]). I'm not really sure it's fair to say that just because there are some on-paper algorithms (which have no usage outside academia at the moment) that might solve the problem that it's false to say that "all modern PK crypto is broken with quantum attackers". But if you prefer, you could imagine that I said "all modern PK crypto [that is actually in use today] is broken". Because, at the end of the day, that's all that really matters. [As an aside, for RSA the security is provided by the hardness of factorisation which also breaks under QC attackers, not discrete log (it's discrete log for DH, and EC discrete log for ECDH).] [1]: https://www.youtube.com/watch?v=ZCmnQR3_qWg https://www.youtube.com/watch?v=ZCmnQR3_qWg
  - sweis 7y ago
    It not exactly a young research area. We have had post-quantum public key cryptosystems based on linear codes for over 40 years. Classic McEliece (https://classic.mceliece.org https://classic.mceliece.org) was created in 1978 and is in the 2nd round of NIST's PQ-crypto contest ( https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions https://csrc.nist.gov/projects/post-quantum-cryptography/rou...). The PQCrypto conference started 13 years ago: https://pqcrypto.org/conferences.html https://pqcrypto.org/conferences.html Chrome ran large scale experiments with NewHope support 3 years ago: https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html https://security.googleblog.com/2016/07/experimenting-with-p...
    - deleted 7y ago
      [deleted]
  - ChrisLomont 7y ago
    Shor factoring for RSA works by period finding, which is all modern PK crypto discrete log. Read the wiki page. I wrote a decently cited paper summarizing all this when I worked in quantum computing research around 2005, on arxiv. Track it down if you’re interested. I’ve followed the field for decades, giving talks once in a while on it. So I do know a bit of the details. The computational power of QC is very well studied. It is certain that it cannot crack certain (most) problems any faster than a classical computer. Thus algorithms not isomorphic to the few problems QC is better at are just as secure on both classical and quantum computers. There is consensus on this - there is no question about it. >all modern PK crypto [that is actually in use today] NTRU is an IEEE standard, and is in wolfSSL, which is on many platforms. NTRU is also used in many commercial products from chat to relays. Other non DLP methods are also used in commercial products and standards.
    - cyphar 7y ago
      > Shor factoring for RSA works by period finding, which is all modern PK crypto discrete log. Read the wiki page. But is it not the case that the original Shor algorithm was specifically about using periodicity for integer factorisation (and the wiki page for "RSA problem"[1] also refers to integer factorisation, not discrete log). > It is certain that it cannot crack certain (most) problems any faster than a classical computer. Yes, I was already well-aware of that. My point was that the overwhelming majority of PK crypto used today depends on the hardness of problems that are exponentially accelerated by QC algorithms. > NTRU is an IEEE standard, and is in wolfSSL, which is on many platforms. Okay, maybe then it has some non-academic use. But the overwhelming majority of PK crypto in use today (TLS, PGP, the vast majority of E2EE systems) is not secure against quantum attackers. Can we agree on that at least? [1]: https://en.m.wikipedia.org/wiki/RSA_problem https://en.m.wikipedia.org/wiki/RSA_problem
- mjevans 7y ago
  With 'the unknown' I prefer to focus very strongly on where known and theoretically known truths are. Based on your statement (I don't recall offhand), it might be said that it is widely believed RSA and ECC algorithms are vulnerable in a world where quantum computing is plausible. The safety of other systems would require a more rigorous proof; the absence of known vulnerability does not imply safety. I am not an expert in this field, but the understanding I have from the last time I spent an afternoon reading about it might be summarized as: * Known/Suspected vulnerable systems use "classically-hard" problems with vulnerability based on small key (or subkey) size. * Most of the 'theoretically more secure' systems make the working set size large enough, and complex enough, to eclipse the scope of stable quantum computers. * Thus, the two attack vectors to consider for 'post quantum' cryptography are currently unthinkably large systems or weaknesses in algorithms that allow for attacking a subset which does fit within a quantum system. If my understanding/memory is incorrect updates would be very helpful.
  - ChrisLomont 7y ago
    The other systems are provably as secure on quantum computers as they are on classical computers. Quantum complexity classes are well mapped out, and it s known certain things cannot b one faster on quantum. Related to crypto, only systems reducible to DLP (well, technically Hidden Subgroup Problem but only for certain groups) are affected. This has the rigor of mathematical proof: it’s not handwaving. And many systems do not reduce to this.
- steelframe 7y ago
  > only methods based on Discrete Log are at risk, which includes RSA and ECC RSA's security is based on the presumption that factorization is hard, which is a different problem than finding the discrete log. To attack RSA you would use Shor's algorithm, and to attack ECC you would use Grover's. See page 2 of this paper: https://arxiv.org/pdf/1804.00200.pdf https://arxiv.org/pdf/1804.00200.pdf
  - ChrisLomont 7y ago
    See my answer above. Shoes factoring is efficient because period finding mod N is exactly discrete log. To attack ECC it is directly discrete log, where quantum is exponentially faster than classical. Grover reduces unstructured search from O(N) to O(sort N), only a quadratic speedup, insufficient to weaken crypto more than 1 bit out of a key length, which is too weak to be a threat. Page 2 of your link does not state how QC attacks problems; it dies say ECC is discrete log, though. Both systems break precisely because QC solve DLP in these cases exponentially faster than classical, and this is all that’s needed.

ccozan 7y ago

But maybe then is already irrelevant?

steelframe 7y ago

> AES256 or better I'm not aware of any symmetric cipher that the industry in broad consensus would consider "better" than AES-256.