KEMTLS vs. Post-Quantum TLS

Performance on embedded systems

Ruben Gonzalez and me

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

<div class="t-container">
  <div class="r-stack col">
    <div class="mermaid" style="background: #fff">
    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
    </div>
    <div class="mermaid fragment" style="background: #fff">
      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
      </div>
      <div class="mermaid fragment" style="background: #fff">
        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
        </div>
  </div>
  <div class="col" >
    <ul>
      <li>Ephemeral KEM key exchange</li>
      <li>Signature public key in certificate</li>
      <li>Server can send data immediately</li>
    </ul>
  </div>
</div>

KEMTLS

<div class="t-container">
  <div class="r-stack col">
    <div class="mermaid">
    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
    </div>
    <div class="fragment mermaid" style="background: #fff">
      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
    </div>
    <div class="fragment mermaid" style="background: #fff">
    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
    </div>
  </div>
  <div class="col" >
    <ul>
      <li>Ephemeral KEM key exchange</li>
      <li>KEM public key in certificate</li>
      <li>Avoid extra round-trip by letting client send data immediately</li>
    </ul>
  </div>
</div>

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"

CPU	72 MHz Cortex-M4F
FPU	✅
Flash	2 MB
SRAM	512 kB
Giant?	Definitely.

The network

Abbrev.	Protocol	Link speed	RTT
BB	Broadband	1 Mbit	26 ms
LTE-M	LTE Machine Type Communication	1 Mbit	120 ms
NB-IoT	Narrowband IoT	46 kbit	3 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

<div class="t-container"  style="font-size: 0.75em">
  <div class="col">
    <h3>Conclusions</h3>
    <ul>
      <li>KEMTLS saves bytes on the wire, which really matters</li>
      <li>Without client authentication no big code size differences</li>
      <li>Paper at <a href="https://kemtls.org">https://kemtls.org/</a>.</li>
    </ul>
  </div>
  <div class="col fragment">
    <h3>Future work</h3>
    <ul>
      <li>Client authentication</li>
      <li>KEMTLS with Pre-Distributed Key</li>
    </ul>
  </div>
</div>


<p class="fragment">Thanks for your attention</p>

<p style="font-family: monospace; font-size: 80%">🌐 <a href="https://ruben-gonzalez.de">ruben-gonzalez.de</a> · 🌐 <a href="https://thomwiggers.nl">thomwiggers.nl</a></p>