KEMTLS vs. Post-Quantum TLS

Performance on embedded systems

Ruben Gonzalez and Thom Wiggers

Post-Quantum

image of a dragon breathing fire, edited such that the dragon has the label 'Peter Shor', and it's breathing fire on text labels saying g^x, RSA and ECC

Quantum attacks on cryptography

  • Quantum computers are not generally faster
  • Shor's Algorithm specifically efficiently solves factoring and discrete log problems
  • Need new cryptographic primitives to replace them

NIST PQC competition

Key Exchange

  • Kyber ⭐
  • SABER
  • NTRU

Signatures

  • Dilithium ⭐⭐
  • Falcon ⭐
  • Rainbow ðŸŠĶ
  • SPHINCS+ ⭐

KEM key exchange

sequenceDiagram Alice->>Bob: public key Note right of Bob: shared secret, ciphertext = KEM.Encapsulate(pk) Bob->>Alice: ciphertext Note Left of Alice: shared secret = KEM.Decapsulate(sk, ct) Note over Alice, Bob: encrypt traffic with shared secret

Tradeoffs

KEMs

  • Fast
  • Smallish

Signatures

  • Dilithium: huge pk, signature
  • Falcon: FPU usage in signing
  • Rainbow: enormous public key, tiny signature

Q: how can we best use these tradeoffs?

Post-Quantum TLS

sequenceDiagram Client->>+Server: ClientHello: ephemeral kex Server->>-Client: ServerHello: ephemeral kex rect rgba(0,0,0,0) Server->>Client: Certificate: static signing pk Server->>Client: Signature end Server->>Client: ServerFinished rect rgba(0, 0, 0, 0) Server-->>Client: Application Data end Client->>Server: ClientFinished Client-->>Server: Application Data
sequenceDiagram Client->>+Server: ClientHello: ephemeral kex Server->>-Client: ServerHello: ephemeral kex rect rgba(2, 100, 2, 0.3) Server->>Client: Certificate: static signing pk Server->>Client: Signature end Server->>Client: ServerFinished rect rgba(0, 0, 0, 0) Server-->>Client: Application Data end Client->>Server: ClientFinished Client-->>Server: Application Data
sequenceDiagram Client->>+Server: ClientHello: ephemeral kex Server->>-Client: ServerHello: ephemeral kex rect rgba(0, 0, 0, 0) Server->>Client: Certificate: static signing pk Server->>Client: Signature end Server->>Client: ServerFinished rect pink Server-->>Client: Application Data end Client->>Server: ClientFinished Client-->>Server: Application Data
  • Ephemeral KEM key exchange
  • Signature public key in certificate
  • Server can send data immediately

KEMTLS

sequenceDiagram Client->>+Server: ClientHello: ephemeral kex Server->>-Client: ServerHello: ephemeral kex rect rgba(0,0,0,0) Server->>+Client: Certificate: static KEM pk Client->>-Server: Ciphertext end Client->>Server: ClientFinished rect rgba(0, 0, 0, 0) Client-->>Server: Application Data end Server->>Client: ServerFinished Server-->>Client: Application Data
sequenceDiagram Client->>+Server: ClientHello: ephemeral kex Server->>-Client: ServerHello: ephemeral kex rect rgba(2, 100, 2, 0.3) Server->>+Client: Certificate: static KEM pk Client->>-Server: Ciphertext end Client->>Server: ClientFinished rect rgba(0,0,0,0) Client-->>Server: Application Data end Server->>Client: ServerFinished Server-->>Client: Application Data
sequenceDiagram Client->>+Server: ClientHello: ephemeral kex Server->>-Client: ServerHello: ephemeral kex rect rgba(0, 0, 0, 0) Server->>+Client: Certificate: static KEM pk Client->>-Server: Ciphertext end Client->>Server: ClientFinished rect pink Client-->>Server: Application Data end Server->>Client: ServerFinished Server-->>Client: Application Data
  • Ephemeral KEM key exchange
  • KEM public key in certificate
  • Avoid extra round-trip by letting client send data immediately

Existing work:

  • Server-only and client authentication
  • Proofs, Tamarin analysis
  • Variant with pre-distributed keys
  • Benchmarks using large-scale computers

Embedded devices

Picture of a development board microcomputer

Silicon Labs STK3701A "Giant Gecko"

CPU72 MHz Cortex-M4F
FPU✅
Flash2 MB
SRAM512 kB
Giant?Definitely.

The network

Abbrev.ProtocolLink speedRTT
BBBroadband1 Mbit26 ms
LTE-MLTE Machine Type Communication1 Mbit120 ms
NB-IoTNarrowband IoT46 kbit3 s

Implementation

  • WolfSSL client on Giant Gecko
  • Rustls server on desktop computer
  • Ethernet connection
  • Apache Zephyr RTOS

Results

Code size results

  • Both KEMTLS and PQTLS need key exchange and signature verification code
    • (KEM)TLS clients do not need signing code
  • Large differences in sizes of necessary certificate authority (CA) public keys: KEMTLS certs slightly smaller
  • PQTLS mixed certificate chains require more code
  • KEMTLS peak memory usage is lower

Communication time

  • KEMTLS handshake traffic generally much lower
    • KEMTLS: Kyber-Kyber-Dilithium: 6.3 kB
    • PQTLS: Kyber-Dilithium-Dilithium: 8.4 kB
  • Less traffic = faster handshake on low-bandwidth connections
  • PQTLS with Falcon certificates still very fast
    • Falcon is very small
    • Falcon verification very fast on Cortex-M4F
    • Requires Falcon online signing on the server

Wrap-up

KEMTLS vs. Post-Quantum TLS: performance on embedded systems

Conclusions

  • KEMTLS saves bytes on the wire, which really matters
  • Without client authentication no big code size differences
  • Paper at https://kemtls.org/.

Future work

  • Client authentication
  • KEMTLS with Pre-Distributed Key

Thanks for your attention

🌐 ruben-gonzalez.de · 🌐 thomwiggers.nl