1
$\begingroup$

We already have recommendations on what PQCrypto to use: PDF (page 11)

Symmetric encryption Thoroughly analyzed, 256-bit keys:

  • AES-256
  • Salsa20 with a 256-bit key

Symmetric authentication Information-theoretic MACs:

  • GCM using a 96-bit nonce and a 128-bit authenticator
  • Poly1305

Public-key encryption McEliece with binary Goppa codes:

  • length n = 6960, dimension k = 5413, t = 119 errors

Public-key signatures Hash-based (minimal assumptions):

  • XMSS with any of the parameters specified in CFRG draft
  • SPHINCS-256

What would it cost to upgrade to those recommendations?

We assume that the recommendations will survive further scrutiny and that upgrading software is for free. In practice it will happen as part of a software upgrade that will happen anyway.

What is the additional:

  • Disk usage
  • RAM usage
  • CPU usage
  • Bandwidth usage

for a normal user and for a normal website?

Since users mostly visit the same websites as they did the day before I am thinking that the key exchange may not be so scary after all. If the SSL certificate is only downloaded every few months, then it will be very little extra bandwidth.

Improve this question
$\endgroup$
  • 2
    $\begingroup$ This entails some rather open-ended speculation about what post-quantum crypto will survive scrutiny. Some relevant references about trials and practical engineering concerns: imperialviolet.org/2018/04/11/pqconftls.html Notes on a second preliminary trial at Google: imperialviolet.org/2018/12/12/cecpq2.html $\endgroup$ – Squeamish Ossifrage Mar 7 '19 at 8:17
  • $\begingroup$ Let's assume the current recommendation are safe to use. $\endgroup$ – Ole Tange Mar 7 '19 at 8:36
  • $\begingroup$ So are you just looking for a table of the parameter choices and current cycle counts of all the NIST PQCRYPTO candidates, like you can find at bench.cr.yp.to? $\endgroup$ – Squeamish Ossifrage Mar 7 '19 at 8:40
  • $\begingroup$ I am more after something a bit closer to what normal users will experience in their daily life, so thanks for the imperialviolet link. Are computers and bandwidths no longer a limiting factor for the adoption of PQCrypto? I still recall the time when https was visibly slower than http due to slow CPUs. That is no longer the case. $\endgroup$ – Ole Tange Mar 7 '19 at 11:57
4
$\begingroup$

Using AES-256 or Salsa20, Poly1305 or GCM authentication should come at no to little additional cost if you are already using HTTPS. If your server is somewhat modern bandwidth cost is about 16 bytes per HTTPS data packet sent and a few hundred bytes (at most) of RAM and rather minimal performance overhead compared to the actual business logic running on the server. You shouldn't worry about this part.

The asymmetric part is the interesting one. As a server you'll have to generate 1 signature for TLS per handshake (so at most one per request) and SPHINCS-256 costs 43M cycles on Intel Kaby Lake CPUs which is about 20ms on a 2GHz CPU. Signatures are 41kB though which means the RAM overhead is probably about ~40kB per handshake and the bandwidth overhead is about the same. Now if you deliver 2MB of JavaScript anyways this will hurt less than if you're only using a very simple static website... I haven't found data on XMSS so won't comment on that.

As for McEliece, performance data suggests it needs about 2M cycles for decryption, which happens once during a TLS handshake, so about 1ms on a 2GHz CPU. However, the public key is 1.3MB which is usually transferred once per handshake. The actual ciphertext is only $n$ bits and so only a bit larger than a comparable RSA encryption. You may want to note though that modern TLS 1.3 doesn't support key transport (ie public-key encryption for key agreement) anymore.

So, in total we get an overhead of about 45M CPU cycles and about 1.4MB per TLS handshake which is about 23ms on a modern server CPU.

Improve this answer
$\endgroup$
  • $\begingroup$ Have there been any improvements in the code-based or hash-based NIST PQCRYPTO candidates vs. what had been published years before? How about any of the lattice-based or isogeny-based NIST PQCRYPTO candidates? $\endgroup$ – Squeamish Ossifrage Mar 9 '19 at 16:02
  • $\begingroup$ (XMSS is bad because it requires that the signer keep state, so don't feel bad about omitting it.) $\endgroup$ – Squeamish Ossifrage Mar 9 '19 at 16:03
  • $\begingroup$ How long is the public key cached? The 45M cycles is hardly scary these days, but the 1.3M for the public key can be on slow connections. $\endgroup$ – Ole Tange Mar 24 '19 at 21:38
  • $\begingroup$ @OleTange Usually 1h, configurable up to 24h / until the client restarts. This is handled by "TLS Session Resumption". $\endgroup$ – SEJPM♦ Mar 24 '19 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.