8 ms·

True, but as we've seen with RSA et al, algorithms once chosen persist for a long time. It would take time for winning algorithms to trickle down to the librar

True, but as we've seen with RSA et al, algorithms once chosen persist for a long time. It would take time for winning algorithms to trickle down to the libraries, and then time for them to be included in the distros. So, better to get going on this stuff now!

jcranmer 8y ago
These competitions also take time. SHA-3's competition was announced in 2006, and the final standard came out in 2015. By comparison, PQC was announced in 2016, and NIST expects the final results to be out in 2022-2024. We're likely a decade away from PQC to be moderately widespread in implementation.
- randomsearch 8y ago
  Fair point, but breaking crypto will require quantum computers with millions of qubits. Currently I’m not convinced that we’ve built a decent general quantum computer with more than five. Long way to go.
  - xucheng 8y ago
    > breaking crypto will require quantum computers with millions of qubits I don’t think this is true. It is estimated that breaking 2048bits RSA only requires 4000 logical qubits (though the number of physical qubits would be much higher). Ref: https://security.stackexchange.com/questions/87345/how-many-qubits-are-needed-to-factor-2048-bit-rsa-keys-on-a-quantum-computer https://security.stackexchange.com/questions/87345/how-many-...
    - throwawaymath 8y ago
      It is true, the parent is talking about physical qubits. By the most recent 2019 estimate (specifically the National Academies report, which was on HN recently, we'll need to increase our current qubit achievements by a factor of at least 10^5. That equates to millions of qubits, because we've currently achieved tens of qubits.
  - MzxgckZtNqX5i 8y ago
    Where does that estimate come from? My (basic) understanding is that, in order to find the factorization of a composite N, Shor's algorithm requires an amount of qubits (let call it q) such that N^2 =< 2^q =< 2N^2. Right now RSA is at most at 4096 bits, so q=8192 could be enough.
    - abdullahkhalids 8y ago
      For building a quantum computer a distinction is made between logical qubits and physical qubits. The physical qubits correspond 1-to-1 with the underlying physical media i.e. each electron spin makes one physical qubit. The physical qubits have a lot of noise, so can't be used directly to do computation. Instead you do error correction on many (3 to millions or more) physical qubits to make one logical qubit that is noise free. These logical qubits are then used to do the actual computation. Your estimate of q=8192 is for logical qubits. The actual physical qubits will realistically go to millions, unless some really fundamental breakthroughs are made.
    - throwawaymath 8y ago
      If you'd like a specific, authoritative citation confirming what the other responder is saying, read the National Academies 2019 report on QC.
segfaultbuserr 8y ago
> but no, there's absolutely no quantum computer factoring on the horizon Recall the history of ECC. ECC was proposed in the late-1990. Unlike RSA, we already had a solid understanding of its security properties at that time. However, it took 15 years to actually implement and deploy NIST curves on the Internet. And again, another 5 years to deploy a more robust version, Curve25519. Also, there are enough reasons to believe that the NSA and other major agencies around the world have a storage capacity of several hundreds of exabytes. Signal traffic, Tor traffic or OpenPGP traffic today is already being recorded and kept indefinitely, waiting for a usable quantum computer to decrypt them in the future. BTW, here's a fun fact: although cryptographers are still trying, but there is no known exploitable structure in most symmetric encryption algorithms (such as ChaCha20 or AES) or hash functions. The only known attack is the general attack using the Grover's Algorithm. It means, if you are afraid that the NSA may decrypt your message in the future, you can always use 256-bit symmetric encryption with per-shared keys. For example, WireGuard supports using pre-shared keys to encrypt ECC handshakes as a poorman's version of PQC.
- nickpsecurity 8y ago
  That's why I pushed Merkle Trees back in the day when the topic came up. There's been work extending them in recent years, too.
  - segfaultbuserr 8y ago
    Glad to see you again on HN, thanks for your criticism about the security mitigation techniques previously. Recently Merkle Trees have indeed made significant progress. XMSS is already standardized, has an RFC, and my Linux distro is already shipping OpenSSH with XMSS authentication enabled. But I don't think it's something practical that you want people to start using immediately. First, the threats to digital signature created by a quantum computer is not as serious as public-key encryption. If the NSA has intercepted my ECDH handshake, they can recover my session key in the future. But if, by 2045, the NSA has managed to forge my signing key, they cannot use it to log into my server, or create false OpenPGP-signed statements. Either the server has been taken offline for a long time, or at least key has already been retired. Unless it's a digital contract of paramount importance (Excluding blockchains, do we really have digital contracts with a validity of more than 20 years?), I don't think it needs post-quantum capabilities today. Second, XMSS and many other Merkle Trees-based system has a serious limitation - statefulness. If the private key is not updated correct after each signature, and the state is ever reused, the private key is exposed for everyone to forge. It means, starting using XMSS today creates more hazards than not using it. I do see some reasons to standardize XMSS: (1) Unlike public-key encryption schemes, the security properties of Merkle Trees-based signature schemes are well-known, with strong guarantees. (2) Standardizing it early allows people to be familiar with the standardization process, eases the future process of more PQC standardization, (3) Allow people to implement and deploy it in an experimental setup. But I really wished to see the standardization of a stateless hash-based signature, like djb's SPHINCS-256. I'm curious about your takes on this topic.

jcranmer 8y ago

These competitions also take time. SHA-3's competition was announced in 2006, and the final standard came out in 2015. By comparison, PQC was announced in 2016, and NIST expects the final results to be out in 2022-2024. We're likely a decade away from PQC to be moderately widespread in implementation.

randomsearch 8y ago
Fair point, but breaking crypto will require quantum computers with millions of qubits. Currently I’m not convinced that we’ve built a decent general quantum computer with more than five. Long way to go.
- xucheng 8y ago
  > breaking crypto will require quantum computers with millions of qubits I don’t think this is true. It is estimated that breaking 2048bits RSA only requires 4000 logical qubits (though the number of physical qubits would be much higher). Ref: https://security.stackexchange.com/questions/87345/how-many-qubits-are-needed-to-factor-2048-bit-rsa-keys-on-a-quantum-computer https://security.stackexchange.com/questions/87345/how-many-...
  - throwawaymath 8y ago
    It is true, the parent is talking about physical qubits. By the most recent 2019 estimate (specifically the National Academies report, which was on HN recently, we'll need to increase our current qubit achievements by a factor of at least 10^5. That equates to millions of qubits, because we've currently achieved tens of qubits.
- MzxgckZtNqX5i 8y ago
  Where does that estimate come from? My (basic) understanding is that, in order to find the factorization of a composite N, Shor's algorithm requires an amount of qubits (let call it q) such that N^2 =< 2^q =< 2N^2. Right now RSA is at most at 4096 bits, so q=8192 could be enough.
  - abdullahkhalids 8y ago
    For building a quantum computer a distinction is made between logical qubits and physical qubits. The physical qubits correspond 1-to-1 with the underlying physical media i.e. each electron spin makes one physical qubit. The physical qubits have a lot of noise, so can't be used directly to do computation. Instead you do error correction on many (3 to millions or more) physical qubits to make one logical qubit that is noise free. These logical qubits are then used to do the actual computation. Your estimate of q=8192 is for logical qubits. The actual physical qubits will realistically go to millions, unless some really fundamental breakthroughs are made.
  - throwawaymath 8y ago
    If you'd like a specific, authoritative citation confirming what the other responder is saying, read the National Academies 2019 report on QC.

segfaultbuserr 8y ago

> but no, there's absolutely no quantum computer factoring on the horizon Recall the history of ECC. ECC was proposed in the late-1990. Unlike RSA, we already had a solid understanding of its security properties at that time. However, it took 15 years to actually implement and deploy NIST curves on the Internet. And again, another 5 years to deploy a more robust version, Curve25519. Also, there are enough reasons to believe that the NSA and other major agencies around the world have a storage capacity of several hundreds of exabytes. Signal traffic, Tor traffic or OpenPGP traffic today is already being recorded and kept indefinitely, waiting for a usable quantum computer to decrypt them in the future. BTW, here's a fun fact: although cryptographers are still trying, but there is no known exploitable structure in most symmetric encryption algorithms (such as ChaCha20 or AES) or hash functions. The only known attack is the general attack using the Grover's Algorithm. It means, if you are afraid that the NSA may decrypt your message in the future, you can always use 256-bit symmetric encryption with per-shared keys. For example, WireGuard supports using pre-shared keys to encrypt ECC handshakes as a poorman's version of PQC.

nickpsecurity 8y ago
That's why I pushed Merkle Trees back in the day when the topic came up. There's been work extending them in recent years, too.
- segfaultbuserr 8y ago
  Glad to see you again on HN, thanks for your criticism about the security mitigation techniques previously. Recently Merkle Trees have indeed made significant progress. XMSS is already standardized, has an RFC, and my Linux distro is already shipping OpenSSH with XMSS authentication enabled. But I don't think it's something practical that you want people to start using immediately. First, the threats to digital signature created by a quantum computer is not as serious as public-key encryption. If the NSA has intercepted my ECDH handshake, they can recover my session key in the future. But if, by 2045, the NSA has managed to forge my signing key, they cannot use it to log into my server, or create false OpenPGP-signed statements. Either the server has been taken offline for a long time, or at least key has already been retired. Unless it's a digital contract of paramount importance (Excluding blockchains, do we really have digital contracts with a validity of more than 20 years?), I don't think it needs post-quantum capabilities today. Second, XMSS and many other Merkle Trees-based system has a serious limitation - statefulness. If the private key is not updated correct after each signature, and the state is ever reused, the private key is exposed for everyone to forge. It means, starting using XMSS today creates more hazards than not using it. I do see some reasons to standardize XMSS: (1) Unlike public-key encryption schemes, the security properties of Merkle Trees-based signature schemes are well-known, with strong guarantees. (2) Standardizing it early allows people to be familiar with the standardization process, eases the future process of more PQC standardization, (3) Allow people to implement and deploy it in an experimental setup. But I really wished to see the standardization of a stateless hash-based signature, like djb's SPHINCS-256. I'm curious about your takes on this topic.