6 ms·

The whole premise of the article is broken: 1. Every respectable cryptographic protocol designer would hedge their bets by combining a post-quantum cryptograph

The whole premise of the article is broken: 1. Every respectable cryptographic protocol designer would hedge their bets by combining a post-quantum cryptography (PQC) algorithm with a classical one, preferable elliptic curve cryptography (ECC), such that you first have to break ECC in order to attack the post-quantum cryptography. ECC is great in that it is both fast, secure, its signatures, ciphertexts and keys are small. Every post-quantum algorithm fails in at least one of the categories, but as ECC excels everywhere, the overhead is basically bound by a factor of two. 2. Our focus can't be on choosing one PQC algorithm now (and keep it forever), as it is a very young field comparably (as the article agrees). Instead, we need to built up algorithm agility in our protocols and software, as we are probably going to change PQC algorithms at least once, when the cryptographic community has gained experience in PQC design/cryptanalysis and we switch to the second wave PQC algorithms. In practice that means: Never assume keys, ciphertext, signatures are small. Investigate whether it is possible for keys to have state (see Lamport signature). And the only way to show these properties about protocols and software is to try out some PQC algorithms now. (Why the urgency? Because software and protocol turnaround time is bonkers in commercial applications. Heck, parts of the payment industry still use single DES in 2019...) Given that the NSA knows both of this, the question is whether the author was clueless or the NSA spokesperson is malicious.

morelisp 7y ago
Algorithm agility has been a hilarious disaster for designing secure systems. In reality even protocols like TLS that are nominally agile advance primarily by versioning, not agility - and TLS is somewhat of a best case here compared to e.g. the mess of JOSE.
- tptacek 7y ago
  You're more right than the parent comment --- algorithm agility is, I believe, an increasingly discredited idea among cryptography engineers --- but there's truth to the idea that a serious PQC scheme is going to be paired with a conventional key exchange, so that a new lattice crypto attack won't break the whole handshake. That's not "agility" --- the schemes will almost certainly be hermetically sealed, one PQC KEX and one curve KEX --- but it does mean you can deploy PQC now without compromising your whole cryptosystem. The big issue here is that this observation doesn't break the premise of the article. It remains true that we don't know enough about how real-world quantum computers, if they ever exist at scales useful to attack cryptography, will work.
- stouset 7y ago
  This was the reply I came here to write.
- throw0101a 7y ago
  > In reality even protocols like TLS that are nominally agile advance primarily by versioning, not agility In the last ten years we've been able to disable CBC-based ciphers to protect against POODLE and BEAST, and disable RC4 to protect against Bar-mitzvah and NOMORE, all the while a legacy device could stick with TLS 1.0 without any code changes. All that was necessary was to tweak the cipher preferences. Being able to support both AES and ChaCha20 is a good thing, and when AESng/Mambo40 come along it will be easier to add them to the protocol in a rolling fashion IMHO.
  - morelisp 7y ago
    If that TLS 1.0 device had never needed to support RC4 in TLS to begin with, which practically speaking it never really needed to, we could've done less work at implementation time, provided clearer guidance to users when the vulnerabilities were discovered, and likely had fewer affected users to begin with.
    - throw0101a 7y ago
      > If that TLS 1.0 device had never needed to support RC4 in TLS to begin with, which practically speaking it never really needed to ... Except that we did not know about not needing to. When BEAST came out a lot of recommendations said to switch over to RC4: * https://en.wikipedia.org/wiki/Transport_Layer_Security#BEAST_attack https://en.wikipedia.org/wiki/Transport_Layer_Security#BEAST...
bdamm 7y ago
My employer produces low-power devices with hardware cryptography built into them. Without the crypto hardware, almost all crypto (including ECC) is too slow for practical use. It's all well and good to have "crypto agility" but that ends when it comes to depending on silicon. So if we're making our 20 year plan for, say, the next generation hardware platform that we're going to invest many millions of dollars and thousands of engineer hours to build, then which PQC algorithms will we select to be built into our platform? It's very unclear at this point. Certainly we can be flexible in key and cert sizes, but also I happen to live in a world where a 1200 byte MTU actually matters a great deal, so it's easier to just push the requirement for dealing with enormous certificates down the road for the day when we actually have enormous certificates. Future-proofing isn't an issue yet because legacy devices will never be able to do PQC. The premise is not broken at all, for us.
- snagglegaggle 7y ago
  Is that a pertinent question? The availability of devices with integrated cryptography is very, very low due to ITAR. Perhaps the only thing I have encountered is a bluetooth controller. Many things are not space constrained as they are cost constrained. It would be easier to put in a core high power enough to get acceptable performance for the one connection it needs to service. It will be more expensive, probably in terms of development work. Will people do it? Probably not, but people weren't doing security right anyway.
  - tptacek 7y ago
    Devices with integrated cryptography are uncommon? There are AVR parts with integrated AES.
  - debatem1 7y ago
    This just isn't true. Nearly every SoC you can buy today has hardware accelerators in it, from STM32s up to Xeons. You have to be looking at really tiny, generally pretty old micros before you literally don't have any. On top of that, hitting hardware speeds by putting in faster cores just isn't a thing for most parts. It's pretty easy to get 8-9x throughput wins on many primitives with a hardware accelerator, but getting a similar improvement just by getting bigger chips is often impossible and always expensive.
tialaramex 7y ago
1. Yes, https://www.imperialviolet.org/2019/10/30/pqsivssl.html https://www.imperialviolet.org/2019/10/30/pqsivssl.html and https://blog.cloudflare.com/the-tls-post-quantum-experiment/ https://blog.cloudflare.com/the-tls-post-quantum-experiment/ describe actual experiments Google ran using randomly selected Chrome canary users against Cloudflare and indeed their test algorithms CECPQ2 and CECPQ2b are both hybrids built using ECC plus a post-quantum algorithm. 2. However at this present time there is a strong constituency (e.g. see morelisp's comment in this sub-thread) which is happy to blame cryptographic agility for problems it arguably had little or no part in, so you can expect them to fight this while of course not committing to any particular post-quantum crypto because they also hate being wrong and invariably if you pick one now you'll be wrong.
namibj 7y ago
Supersingular isogeny Diffie–Hellman key exchange (SIDH) has post-quantum keys comparable to current RSA keys. It seems limited to DH key exchange with it's favorable properties, however...
- bloomer 7y ago
  It’s downside is that it is computationally very expensive. All of the other NIST candidates are not very computationally demanding, but have much larger keys. So the trade off with SIDH is that it spends a lot of time calculating while the others are transmitting bytes over the network. There are trade offs with all the proposed schemes. a
ShorsHammer 7y ago
> hedge their bets by combining a post-quantum cryptography (PQC) algorithm with a classical one OpenSSH does this with certain algo choices for anyone particularly inclined.

morelisp 7y ago

Algorithm agility has been a hilarious disaster for designing secure systems. In reality even protocols like TLS that are nominally agile advance primarily by versioning, not agility - and TLS is somewhat of a best case here compared to e.g. the mess of JOSE.

tptacek 7y ago
You're more right than the parent comment --- algorithm agility is, I believe, an increasingly discredited idea among cryptography engineers --- but there's truth to the idea that a serious PQC scheme is going to be paired with a conventional key exchange, so that a new lattice crypto attack won't break the whole handshake. That's not "agility" --- the schemes will almost certainly be hermetically sealed, one PQC KEX and one curve KEX --- but it does mean you can deploy PQC now without compromising your whole cryptosystem. The big issue here is that this observation doesn't break the premise of the article. It remains true that we don't know enough about how real-world quantum computers, if they ever exist at scales useful to attack cryptography, will work.
stouset 7y ago
This was the reply I came here to write.
throw0101a 7y ago
> In reality even protocols like TLS that are nominally agile advance primarily by versioning, not agility In the last ten years we've been able to disable CBC-based ciphers to protect against POODLE and BEAST, and disable RC4 to protect against Bar-mitzvah and NOMORE, all the while a legacy device could stick with TLS 1.0 without any code changes. All that was necessary was to tweak the cipher preferences. Being able to support both AES and ChaCha20 is a good thing, and when AESng/Mambo40 come along it will be easier to add them to the protocol in a rolling fashion IMHO.
- morelisp 7y ago
  If that TLS 1.0 device had never needed to support RC4 in TLS to begin with, which practically speaking it never really needed to, we could've done less work at implementation time, provided clearer guidance to users when the vulnerabilities were discovered, and likely had fewer affected users to begin with.
  - throw0101a 7y ago
    > If that TLS 1.0 device had never needed to support RC4 in TLS to begin with, which practically speaking it never really needed to ... Except that we did not know about not needing to. When BEAST came out a lot of recommendations said to switch over to RC4: * https://en.wikipedia.org/wiki/Transport_Layer_Security#BEAST_attack https://en.wikipedia.org/wiki/Transport_Layer_Security#BEAST...

bdamm 7y ago

My employer produces low-power devices with hardware cryptography built into them. Without the crypto hardware, almost all crypto (including ECC) is too slow for practical use. It's all well and good to have "crypto agility" but that ends when it comes to depending on silicon. So if we're making our 20 year plan for, say, the next generation hardware platform that we're going to invest many millions of dollars and thousands of engineer hours to build, then which PQC algorithms will we select to be built into our platform? It's very unclear at this point. Certainly we can be flexible in key and cert sizes, but also I happen to live in a world where a 1200 byte MTU actually matters a great deal, so it's easier to just push the requirement for dealing with enormous certificates down the road for the day when we actually have enormous certificates. Future-proofing isn't an issue yet because legacy devices will never be able to do PQC. The premise is not broken at all, for us.

snagglegaggle 7y ago
Is that a pertinent question? The availability of devices with integrated cryptography is very, very low due to ITAR. Perhaps the only thing I have encountered is a bluetooth controller. Many things are not space constrained as they are cost constrained. It would be easier to put in a core high power enough to get acceptable performance for the one connection it needs to service. It will be more expensive, probably in terms of development work. Will people do it? Probably not, but people weren't doing security right anyway.
- tptacek 7y ago
  Devices with integrated cryptography are uncommon? There are AVR parts with integrated AES.
- debatem1 7y ago
  This just isn't true. Nearly every SoC you can buy today has hardware accelerators in it, from STM32s up to Xeons. You have to be looking at really tiny, generally pretty old micros before you literally don't have any. On top of that, hitting hardware speeds by putting in faster cores just isn't a thing for most parts. It's pretty easy to get 8-9x throughput wins on many primitives with a hardware accelerator, but getting a similar improvement just by getting bigger chips is often impossible and always expensive.

tialaramex 7y ago

1. Yes, https://www.imperialviolet.org/2019/10/30/pqsivssl.html https://www.imperialviolet.org/2019/10/30/pqsivssl.html and https://blog.cloudflare.com/the-tls-post-quantum-experiment/ https://blog.cloudflare.com/the-tls-post-quantum-experiment/ describe actual experiments Google ran using randomly selected Chrome canary users against Cloudflare and indeed their test algorithms CECPQ2 and CECPQ2b are both hybrids built using ECC plus a post-quantum algorithm. 2. However at this present time there is a strong constituency (e.g. see morelisp's comment in this sub-thread) which is happy to blame cryptographic agility for problems it arguably had little or no part in, so you can expect them to fight this while of course not committing to any particular post-quantum crypto because they also hate being wrong and invariably if you pick one now you'll be wrong.

namibj 7y ago

Supersingular isogeny Diffie–Hellman key exchange (SIDH) has post-quantum keys comparable to current RSA keys. It seems limited to DH key exchange with it's favorable properties, however...

bloomer 7y ago
It’s downside is that it is computationally very expensive. All of the other NIST candidates are not very computationally demanding, but have much larger keys. So the trade off with SIDH is that it spends a lot of time calculating while the others are transmitting bytes over the network. There are trade offs with all the proposed schemes. a

ShorsHammer 7y ago

> hedge their bets by combining a post-quantum cryptography (PQC) algorithm with a classical one OpenSSH does this with certain algo choices for anyone particularly inclined.