Re: [CFRG] [Pqc] New Liaison Statement, "Quantum Safe Cryptographic Protocol Inventory"

["D. J. Bernstein" <[e-mail]>]

Bas Westerbaan writes:
> The key point is the timescale.

Within the proposed text for an IETF position, the text that I was
commenting upon was "The idea that symmetric cryptography will be
practically affected by CRQCs is now seen as a misconception".

I don't see how the reader would expect "will" to be imposing a time
limit. If the intention was to limit the statement to N years, then I'd
like to know what N is (for comparison to the number of years stated as
confidentiality requirements in various applications) and how exactly
that value of N is supposed to be supported by the references cited.

There is one timed statement elsewhere in the proposed text, namely
"classical supercomputers might be able to brute force AES-128 around
the year 2090", but I have other objections to that statement:

   (1) The reader understands "might ... around the year 2090" to mean
       that this risk _begins_ around the year 2090. The underlying data
       actually leads to much wider uncertainty intervals than that.

   (2) Special-purpose attack hardware is much faster than normal
       supercomputers for this cryptanalytic task. (See, e.g.,
       https://cat.cr.yp.to/cryptattacktester-20231020.pdf#subsection.F.11
       quantifying the speed advantage of Bitcoin-mining hardware.)

   (3) If 2^40 128-bit keys encrypt a known plaintext then one of the
       keys will be broken by an attack that is already feasible for
       large-scale attackers _today_. (For further comments on this, see
       https://blog.cr.yp.to/20151120-batchattacks.html.)

The third point by itself is ample reason to move away from 128-bit
keys. Trying to add multi-target protections into every use of 128-bit
keys is much more complicated for designers and for security reviewers
than simply upgrading to 256-bit keys. As an illustration of the
complicated approach damaging security, consider

   * the collapse of the claim that "the FrodoKEM parameter sets
     comfortably match their target security levels with a large
     margin" and

   * the feasibility of a multi-ciphertext attack against FrodoKEM-640,

coming from an attacker being able to test possibilities for a 128-bit
key inside FrodoKEM-640. FrodoKEM was patched in 2023 to try to address
the multi-ciphertext failure, but this doesn't rescue the "comfortably
... large margin" claim. Insisting on 256 bits everywhere would have
avoided the entire security failure in the first place.

Paul Wouters writes:
> There is also a real environmental cost if every server switches from
> say aes128 to aes256 for all its disk/network operations.

What exactly does "real" mean here, and why exactly is the cost of using
256-bit keys being equated with the cost of using AES-256?

I agree that AES-256 uses about 1.4x more bit operations than AES-128.
But ChaCha20

   * uses just 126 bitops/bit, which is 1.4x _fewer_ than AES-128;
   * has none of the key-expansion costs incurred by AES;
   * has much higher PRF security than AES-256;
   * has a much larger security margin than AES-256; and
   * has a 256-bit key, just like AES-256.

ChaCha20 software has even larger advantages over AES software: it uses
the fast addition circuits in CPUs, naturally eliminates the timing
variations exploited in, e.g., https://eprint.iacr.org/2019/996, and
ends up slaughtering AES in performance. Google---which seems satisfied
with the smaller security margins of AES-256 and ChaCha12---rolled out
ChaCha12 for flash encryption for "the next billion users":

   https://security.googleblog.com/2019/02/introducing-adiantum-encryption-for.html

To be clear, this doesn't mean ChaCha software will beat AES on a CPU
that has AES _hardware_. To be concrete, let's look at Zen 3 speeds
(since John Mattsson recently picked a Zen 3 CPU as an example): AES-256
runs at 0.58 cycles/byte with special AES hardware support, while
ChaCha12 runs at 0.68 cycles/byte, so obviously switching from AES-128
to ChaCha on that CPU would cost cycles.

But shouldn't we be more worried about a poor little Raspberry Pi 3,
where SUPERCOP lists ChaCha12 as 3.52 cycles/byte and _variable-time_
AES-128 as 17.22 cycles/byte? More fundamentally, to _really_ save the
environment, shouldn't we be pushing for a future where all CPUs have
ChaCha directly in hardware? Think of the children!

---D. J. Bernstein