Re: [CFRG] Millions of dollars of hashing

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

Peter Gutmann writes:
> I was thinking of (EC)DH on an STM32F4.

Just to fill in some STM32F4 quantification for those of us who prefer
to work with numbers rather than trying to figure out the dividing line
between "expensive" and "very fast": The 2019 paper

   https://tches.iacr.org/index.php/TCHES/article/view/7384/6556

reports 655891 X25519 cycles on a STM32F407 running at 168MHz (i.e., 3.9
milliseconds), or 847048 cycles at 168MHz (i.e., 5.0 milliseconds) if
you turn off flash prefetch, or 625358 cycles if you scale down to 16MHz
(so 39.1 milliseconds).

STM32F407VET6TR includes 512KB of flash and is currently $7.42 in bulk
from Mouser. STM32F407VGT7TR includes 1MB and is $9.24 in bulk. If 80MHz
and 64KB are enough then an STM32L412K8U6TR is $1.85 in bulk. There are
many more options.

For people thinking about the post-quantum situation, pqm4 (which uses
an STM32F407VGT6 running at 24MHz) reports 863343 cycles for Kyber-768
enc and 783369 cycles for Kyber-768 dec.

If keys are used only once, then Kyber-768 adds 706531 cycles for
keygen; meanwhile X25519 keygen multiplies CPU cycles on each side by
something between 1.3 and 1.5 for typical table sizes (I'm estimating
here), or by 2 to minimize code size if speed isn't actually an issue.
The one-time scenario also means that these aren't long-term identity
keys, so there's a further cost for another layer of public-key
operations---e.g., encrypting to a long-term key.

Another cost is the network. A 1088-byte Kyber-768 ciphertext takes more
than 10 milliseconds to transmit with the smartcard communication rates
listed in, e.g., slide 6 here ("Communication rates ... < 100 kB/s"):

   https://csrc.nist.gov/CSRC/media/Presentations/smartcard-and-post-quantum-crypto/images-media/session-5-greuet-smartcard-pqc.pdf

That slide also describes a "high-end smartcard" as having a Cortex-M3
CPU running at 100MHz; that was a few years ago. The Cortex-M4 cycle
counts listed above are smaller than Cortex-M3 cycle counts for the same
operations. I don't know how to get data on the distribution of
smartcard CPUs sold today.

---D. J. Bernstein