Towards
Post-Quantum
TLS

ECC 2019
Kris Kwiatkowski

DECEMBER 2, 2019

OVERVIEW● OUR APPROACH TO REAL WORLD CRYPTOGRAPHY● DESIGNING THE EXPERIMENT● RESULTS● QUESTIONS

2

INTRODUCTION: TEAM

=Adam
Langley

Luke
Valenta@agl__@lukevalenta

Kris
Kwiatkowski@_henrycase

Nick
Sullivan

Dave
Levin

Alan
Mislove@grittygrease@DistributedDave@amislove3

Our Approach toReal World
Cryptography

MOTIVATION

How best to contributeto the PQC
standardization
process?
Pick an ecosystem andexplore the upgradepath.

5MOTIVATION

Meaningful deployment and impact

Non-trivial complexity

Methodology for migration establishedThe cryptographic system should be widely

Deployments with many diﬀerent

There should be well-establisheddeployed and relied on by millions of people

dependencies and complex moving parts

requirements and norms for upgrading thefor important communications.

are trickier to upgrade. Pick a project that

ecosystem based on previous upgrades.

helps uncover potential stumbling blocks.

6

MOTIVATIONHTTPS in browsers

Meaningful deployment and impact

Non-trivial complexity

Methodology for migration establishedThe cryptographic system should be widely

Deployments with many diﬀerent

There should be well-establisheddeployed and relied on by millions of people

dependencies and complex moving parts

requirements and norms for upgrading thefor important communications.

are trickier to upgrade. Pick a project that

ecosystem based on previous upgrades.

helps uncover potential stumbling blocks.

7

MOTIVATION

Meaningful
deployment andimpact

Online life is encrypted
Web traﬃc is 75% HTTPSThis includes almost all banking, eCommerce, social
media, search, webmail, video streaming, news, and other
online activity in a browser or mobile app
Cloudﬂare well positioned as a CDN

Non-trivialcomplexity

Browser complexity

Other “hidden” participantsServer complexity● Variety of browser implementations● Anti-virus proxies● Possibility of DDoS

● TCP proxies of other types● Slow updates that require downtime● National Firewalls● Hardware-accelerated TLS oﬄoaders●● Library dependencies: OpenSSL etc.

○ OS, vendor, devices● SSL Libraries○ BoringSSL, NSS, CommonCrypto,sChannel…

Forward Proxies (with SNI-ﬁltering)● TLS terminator boxes/cloud services● Compatibility● Embedded app browsing● HTTPS API clients● Old (archaic) browsers
9

Methodology formigration
established•HTTPS is HTTP with TLS/SSL• Requirements clearly deﬁned in a form of RFC•

Tooling & methodology for measurements in place

10Rule of thumb
DEPLOYABLE PROTOCOLS

Breakage rate should be comfortably
below 1%STICKERSpecify

DeployMeasureAdjust20082012

2012-132012-2014

Publish the speciﬁcation

Use test population

Detect various breakages

Fix bad servers and middleboxes
until breakage is low enoughInsecure fallback

Rule of thumbDEPLOYABLE PROTOCOLS

Breakage rate should be comfortably
below 1%Specify

DeployMeasureAdjust2014-20182016-20182016-20182016-2018

Develop draft speciﬁcations

Use test population

Detect various breakages

Change the speciﬁcation to adjust for
the reality of the world

Designing theexperimentDESIGNING THE EXPERIMENT

ProtocolShapeCPU Usage
Key Size

Latency

14

Protocol Shape
1-RTT
The client initiates with its key share, the server respondswith its key share, signature and potentially initial data.
Post-quantum KEMs ﬁt nicely into this model.

No client challenge
There is no current requirement for a proof-of-work to bedone on the client side. Expensive key exchange is a DoSrisk.

DESIGNING THE EXPERIMENT

15

DESIGNING THE EXPERIMENTCPU Usage
Higher latency
If an algorithm takes clock time on the order of network
time (10ms+), it may noticeably delay the connection.

Power consumption
Mobile and lightweight devices optimize for battery life.
Expensive computations hurt this.

Asymmetry risk
If an attacker can cause a lot of work using only a small
amount of work, it is an ampliﬁcation attack vector.

Key SizeHard-coded sizes in legacy systems
Network congestion causes latency
Unknowns
17

DESIGNING THE EXPERIMENT

Previous work
Post-quantum conﬁdentiality for TLS
2018 experiment by Adam Langley to measure impact ofkey size on latency. Implemented “dummy” extension tosimulate larger key sizes.

Control group: no extension sent
Supersingular isogenies (SI): 400 bytes
Structured lattices (SL): 1 100 bytes
Unstructured lattice standing (ULS): 3 300 bytes

https://www.imperialviolet.org/2018/04/11/pqconftls.html

Our experiment

OUR EXPERIMENT

Implement and deploy two realistic key
agreement ciphers
HRSS-SXY (NTRU)

SIKE (Isogeny)

20

OUR EXPERIMENT

Integrate two PQ KEMs into TLS and deploy at scaleCharacteristics• Latency• Key sizes• CPU utilization• Use of existing hardware capabilities for fast implementation

CECPQ2

CECPQ2b

NTRU (Round 2)

SIKE/p434 (Round 2)• NIST level 1• NIST level 1• 1138 byte public key/ciphertext• 330 byte public key, 346 byte ciphertext• Fast Encaps, Decaps, Acceptable KeyGen• Slow KeyGen, Encaps, Decaps• 76000, 22000, 4000/s on Skylake (<1ms)• 420, 265, 245/s on Skylake (~5ms)• 33287, 13605, 2057/s on ARM Cortex-A75• 269, 165, 155/s on ARM Cortex-A75● No decryption errors● SIDH as a “drop-in” replacement of DH in TLS
21

OUR EXPERIMENT

Some tweaks
No SHA-3

Combined mode with X25519

SHA-256 instead of SHAKE for KEM

Concatenate and combine with HKDF

Code available
SIKE : https://github.com/post-quantum-cryptography/c-sikeNTRU: https://github.com/google/boringssl/tree/master/crypto/hrss

22

TLSintegration● TLSv1.3 only: sends
algorithm ID and public keys
in TLS ClientHello● Based ondraft-kiefer-tls-ecdhe-sidh● Both client and server useephemeral keys
● Shared secret is aconcatenation of X25519
and KEM secrets

OUR EXPERIMENT

Ensuring results quality● Client browsers splitted into 3 groups○ CONTROL: using X25519 for key
exchange○ CECPQ2: using NTRU combinedwith X25519○ CECPQ2b: using SIKE combinedwith X25519● “PQ signal” - TLS extension
exchanged between client and server
to indicate participation in theexperiment

OUR EXPERIMENTYou could be using
post-quantum
cryptography
A25

DEPLOYMENT

Deployment
Cloudﬂare edge
Over 20 million Internet properties
Both suites supported
Located “close” to users
Note: SIKE not cleared for Google servers due to DoS risk
Chrome Canary
A diverse group of beta testers
usually using Intel-based desktop
computers and ARM-based mobile devices

Biases of the population● 64-bit x86 and ARM CPUs only
○ population signiﬁcantly biased towards powerful CPUs
● “Chrome Canary and Dev Chrome users tend to have worse
networks than the Chrome user population as a whole”, A. Langley
https://www.imperialviolet.org/2019/10/30/pqsivssl.html● Biases result in favoring isogenies over lattices in terms ofperformance

SCollected dataDuration● August & September 2019
● 53 days in total

Data● 10 millions of data samples collected● represents 5% of TLS connections
sampledSERVER-SIDE RESULTS

NTRU
SIKE

NTRU
SIKE

SERVER-SIDE RESULTS

NTRU
SIKE

NTRU
SIKE

SERVER-SIDE RESULTSSERVER-SIDE RESULTS

Configuration

Additional latency over control group w/ 95% confidence intervals (ms)X25519NTRU

SIKE

LatencyDifference

Mobile, 50th

[133,135][138, 140]

[196, 198]

29.44%

Mobile, 95th

[774, 818]

[1001, 1060][978, 1026]

2.77%

Mobile, 99th

[2783, 3097][4057, 4478][3276, 3646]

18.90%

Desktop, 50th

[55, 55][58, 58][74, 76]

22.67%

Desktop, 95th

[350, 354]

[417, 421]

[421, 425]

0.95%

Desktop, 99th

[1226 1246][1481, 1509][1344, 1368]

9.30%
Maritz-Jarrett estimators

33

Challenges: pre-production testing● Pre-production performance testing○ Send hardcoded ClientHello and drop connection just after○ Distribute injectors on multiple machines

SIKENTRUNTRUConclusion● Lattice vs Isogeny based key exchange:○ NTRU looks like better candidate for TLS○ High-performance isogeny-based public key crypto
less developed than lattice based● At 50th percentile, the CPU cost dominates handshakelatency● However, key size plays a factor at 99th percentile○ Root cause not found

NTRU

SIKE37

Questions?