1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
|
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<style type="text/css">
html{overflow-y:scroll;background-color:#042424}
body{font-family:"Noto Sans","Droid Sans","DejaVu Sans","Arial",sans-serif;line-height:1.5}
tt,code{background-color:#f0f0f0;font-family:"Noto Sans Mono","Droid Sans Mono","DejaVu Sans Mono","Courier New",monospace,sans-serif;font-size:1em;}
pre{margin-left:3em}
p,ul,ol,blockquote,pre{font-size:1.0em;line-height:1.6}
li p{font-size:1.0em}
blockquote p{font-size:1.0em}
h1{font-size:1.5em}
h2{font-size:1.3em}
h3{font-size:1.0em}
h1 a{text-decoration:none}
table{border-collapse:collapse}
th,td{border:1px solid black}
table a{text-decoration:none}
table tr{font-size:1.0em;line-height:1.6em}
table tr{font-size:1.0em;line-height:1.5}
tbody tr:nth-child(12n+1){background-color:#f0ffff}
tbody tr:nth-child(12n+2){background-color:#f0ffff}
tbody tr:nth-child(12n+3){background-color:#f0ffff}
tbody tr:nth-child(12n+4){background-color:#f0ffff}
tbody tr:nth-child(12n+5){background-color:#f0ffff}
tbody tr:nth-child(12n+6){background-color:#f0ffff}
tbody tr:nth-child(12n+7){background-color:#fffff0}
tbody tr:nth-child(12n+8){background-color:#fffff0}
tbody tr:nth-child(12n+9){background-color:#fffff0}
tbody tr:nth-child(12n+10){background-color:#fffff0}
tbody tr:nth-child(12n+11){background-color:#fffff0}
tbody tr:nth-child(12n+12){background-color:#fffff0}
.headline{padding:0;font-weight:bold;font-size:1.0em;vertical-align:top;padding-bottom:0.5em;color:#ffffff;background-color:#042424}
.navt{display:block;box-sizing:border-box;-moz-box-sizing:border-box;-webkit-box-sizing:border-box;margin:0;padding:0;vertical-align:center;font-size:1.0em}
.here{background-color:#042424}
.here{color:#ffffff}
.away{background-color:#042424}
.away a{text-decoration:none;display:block;color:#ffffff}
.away a:hover,.away a:active{text-decoration:underline}
.main{padding:5px}
.main{background-color:#ffffff}
.pagetitle{font-size:1.4em;font-weight:bold}
.logo img{width:100px}
@media only screen and (min-width:512px) {
.fixed{margin:0;padding:0;width:160px;height:100%;position:fixed;overflow:auto}
.main{margin-left:170px}
}
</style>
<title>
PQConnect: Cryptography</title>
</head>
<body>
<div class=fixed>
<div class=headline>
<div class=logo><img src=topleft.png></div>
PQConnect</div>
<div class="navt away"><a href=index.html>Intro</a>
</div><div class="navt away"><a href=user.html>For users</a>
</div><div class="navt away"><a href=sysadmin.html>For sysadmins</a>
</div><div class="navt away"><a href=compat.html>Compatibility</a>
</div><div class="navt away"><a href=security.html>Security</a>
</div><div class="navt here">Cryptography
</div><div class="navt away"><a href=changes.html>Changes</a>
</div><div class="navt away"><a href=papers.html>Papers</a>
</div></div>
<div class=main>
<div class=pagetitle>PQConnect: Cryptography</div>
<p>This page explains PQConnect's top three cryptographic goals,
and various aspects of how PQConnect aims to achieve those goals.
There is a
<a href="security.html">separate page</a>
looking more broadly at security.</p>
<h2><a name="encryption">Priority 1: post-quantum encryption</a></h2>
<p>Attackers are
<a href="https://www.theguardian.com/uk-news/2021/may/25/gchqs-mass-data-sharing-violated-right-to-privacy-court-rules">carrying out mass surveillance of Internet traffic</a>.
They are
<a href="https://www.forbes.com/sites/andygreenberg/2013/06/20/leaked-nsa-doc-says-it-can-collect-and-keep-your-encrypted-data-as-long-as-it-takes-to-crack-it/">saving encrypted data to break later</a>.
They are years ahead of the public in
<a href="https://www.washingtonpost.com/world/national-security/nsa-seeks-to-build-quantum-computer-that-could-crack-most-types-of-encryption/2014/01/02/8fff297e-7195-11e3-8def-a33011492df2_story.html">investing in quantum computers</a>.
The ciphertexts we send are irrevocably shown to any attackers monitoring the network;
we cannot retroactively improve the encryption of that data.</p>
<p>The top priority for PQConnect
is to switch as much Internet traffic as possible,
as quickly as possible,
to high-security end-to-end post-quantum encryption.</p>
<p>To the extent that some applications have already been
rolling out post-quantum encryption, great!
PQConnect adds another layer of defense in case that fails,
a layer systematically designed for high security.
But the more obvious benefit of PQConnect
is for applications that are still using pre-quantum encryption
or no encryption at all.
PQConnect provides a fast application-independent path to post-quantum cryptography.</p>
<h2><a name="authentication">Priority 2: post-quantum authentication</a></h2>
<p>Another important goal of PQConnect
is to switch as much Internet traffic as possible,
as quickly as possible,
to high-security end-to-end post-quantum <em>authentication</em>.</p>
<p>The urgency of post-quantum authentication is not as obvious
as the urgency of post-quantum encryption.
Consider,
for example,
an application relying on pre-quantum signatures for authentication.
Assume that the application is upgraded so that all verifiers accept post-quantum signatures,
and then upgraded to replace all generated pre-quantum signatures with post-quantum signatures,
and then upgraded so that verifiers stop accepting pre-quantum signatures,
with all of these upgrades deployed by all signers and verifiers
before the attacker has a quantum computer.
There will then be no verifiers accepting the attacker's forged pre-quantum signatures.</p>
<p>However,
the timeline for upgrades is variable and often extremely slow.
For example,
within web pages loaded by Firefox,
the <a href="https://letsencrypt.org/stats/">percentage using HTTPS</a>
was around 30% in 2014, around 80% in 2020, and still around 80% in 2024.
There are clear risks that,
when the first public demonstrations of quantum attacks appear,
many applications will still be using pre-quantum cryptography,
while real quantum attacks will already have been carried out in secret.
Starting earlier on upgrades will reduce the damage.</p>
<h2><a name="key-erasure">Priority 3: fast post-quantum key erasure</a></h2>
<p>Sometimes a user's device is stolen or otherwise compromised by an attacker.
Perhaps this allows attackers to find decryption keys inside the device,
and to use those keys to decrypt ciphertexts that the attacker previously recorded.</p>
<p>Of course,
the big problem here is that secrets stored on a user device
were exposed in the first place.
What one wants is better protection for all data stored on the device.
However,
in case that protection fails,
the damage may be reduced if keys are preemptively erased.</p>
<p>PQConnect sets a goal of having each ciphertext no longer decryptable 2 minutes later,
even if the client and server devices are subsequently compromised
by an attacker also having a quantum computer.
Concretely, PQConnect encrypts each ciphertext using a post-quantum key
that is erased by the client and by the server within 2 minutes.
This erasure happens <em>within</em> each PQConnect tunnel,
no matter how long the tunnel lasts.</p>
<p>For comparison,
the "ephemeral" options in TLS are often claimed to provide
<a href="https://datatracker.ietf.org/doc/html/rfc5246">"Perfect Forward Secrecy"</a>,
but these options still allow ciphertexts to be decryptable for
<a href="https://www.imperialviolet.org/2013/06/27/botchingpfs.html">as long as a TLS session lasts</a>.
A <a href="https://jhalderm.com/pub/papers/forward-secrecy-imc16.pdf">2016 study</a> found that
"connections to 38% of Top Million HTTPS sites are vulnerable to decryption if the server is compromised up to 24 hours later, and 10% up to 30 days later".
Current security guides that ask TLS applications to
<a href="https://docs.veracode.com/r/harden-tls-session-resumption">disable session resumption</a>
do not prevent sessions from lasting for hours or longer.</p>
<h2><a name="full">Full-packet encryption</a></h2>
<p>PQConnect encrypts the complete packets sent by applications,
including protocol headers and port numbers.
Attackers may be able to deduce
the same information by analyzing metadata
such as the timings and lengths of packets,
but this is not a reason to simply give the data away.</p>
<h2><a name="bpn">VPNs and BPNs</a></h2>
<p>VPNs typically share PQConnect's features
of being application-independent and encrypting full packets.
However,
VPNs generally do not provide end-to-end security.
A client sets up a VPN to encrypt traffic to a VPN proxy,
but then traffic is exposed at the VPN proxy,
and at every point between the VPN proxy and the ultimate server.</p>
<p>It is possible to manually configure typical VPN software
so that a connection to <code>www.your.server</code>
goes through a VPN tunnel to <code>www.your.server</code>,
a connection to <code>www.alices.server</code>
goes through a VPN tunnel to <code>www.alices.server</code>,
etc.,
when this is supported by the servers.
PQConnect <em>automates</em> the processes of announcing server support
and of creating these tunnels.</p>
<p>In English,
"boring a tunnel" means creating a tunnel by digging, typically with a tool.
PQConnect is a "BPN": a "Boring Private Network".</p>
<p>The PQConnect mascot is a Taiwanese pangolin.
Pangolins dig tunnels and are protected by their armor.
The Mandarin name for pangolins is 穿山甲,
literally "pierce mountain armor".
Legend says that pangolins travel the world through their tunnels.</p>
<p>There is another use of the word "boring" in cryptography:
<a href="https://cr.yp.to/talks.html#2015.10.05">"boring cryptography"</a>
is cryptography that simply works, solidly resists attacks,
and never needs any upgrades.
PQConnect also aims to be boring in this sense.</p>
<h2><a name="double">Double public-key encryption: ECC+PQ</a></h2>
<p>To the extent that applications have upgraded to post-quantum public-key encryption,
they are normally using it as a second layer
on top of pre-quantum public-key encryption (typically X25519),
rather than as a replacement for pre-quantum public-key encryption.
This <a href="security.html#non-nocere">reduces the damage</a>
in case of a security failure in the post-quantum software:
the impact is delayed until the attacker has a quantum computer.</p>
<p>PQConnect follows this approach.
One difference in details is that
PQConnect replaces typical concatenated encryption
with nested encryption to reduce attack surface.</p>
<h2><a name="mceliece">Conservative public-key encryption: McEliece</a></h2>
<p>PQConnect does not use the presence of an ECC backup
as an excuse for risky PQ choices.
A devastating PQ failure would mean that goal #1 is not achieved.</p>
<p>The foundation of security in PQConnect is the
<a href="https://classic.mceliece.org">Classic McEliece</a>
encryption system at a
<a href="https://cat.cr.yp.to/cryptattacktester-20240612.pdf#page.28">very high security level</a>,
specifically <code>mceliece6960119</code>;
the software uses
<a href="https://lib.mceliece.org">libmceliece</a>.
Among proposals for post-quantum public-key encryption,
the McEliece cryptosystem is unique in how strong its security track record is:
more than
<a href="https://isd.mceliece.org">50 papers</a> attacking the system since 1978
have produced
<a href="https://cr.yp.to/talks/2024.09.17/slides-djb-20240917-mceliece-16x9.pdf#page.16">only tiny changes in the McEliece security level</a>.
Classic McEliece is also used in
the
<a href="https://mullvad.net/en/blog/stable-quantum-resistant-tunnels-in-the-app">Mullvad</a>
and
<a href="https://rosenpass.eu/">Rosenpass</a>
VPNs, and in various
<a href="https://mceliece.org">other applications</a>.</p>
<p>Each PQConnect server has a long-term 1MB Classic McEliece key
that it sends out upon request.
To prevent amplification,
PQConnect pads the request to 1MB.
This cost is only per-client, not per-tunnel or per-connection.
The PQConnect client software generates and saves many Classic McEliece ciphertexts
so that it can immediately generate fresh tunnels to the server
without re-requesting the key;
an alternative would be to save the full key.</p>
<p>Of course,
if your smartphone's mobile-data plan
has a 10GB-per-month data cap,
and this month your phone wants to contact
5000 PQConnect servers that it has never talked to before,
then you'll have to get on Wi-Fi.</p>
<h2><a name="enc-auth">Public-key encryption for authentication</a></h2>
<p>PQConnect uses Classic McEliece
not just to protect the confidentiality of user data
but also to protect the user data against forgeries.
The client sends a ciphertext to the server's public key
to establish a secret session key known to the client and server.
The session key is the key for an authenticated cipher
that protects each packet of user data.</p>
<p>Reusing encryption for authentication
avoids the need for a separate signature system.
Some references:
<a href="https://eprint.iacr.org/1998/009">1998</a>,
<a href="https://dnscurve.org">2009</a>,
<a href="https://cr.yp.to/talks.html#2016.02.24">2016</a>,
<a href="https://www.pqcrypto.eu/deliverables/d2.5.pdf">2018</a>,
<a href="https://eprint.iacr.org/2020/534">2020</a>.</p>
<h2><a name="auth-pk">Authenticating public keys</a></h2>
<p>TLS relies on DNS to be secure.
An attacker that controls the DNS records for <code>www.your.server</code>
(for example,
an attacker that compromises the root DNS servers,
that exploits continuing holes in the deployment of cryptography for DNS,
or that uses a quantum computer to break pre-quantum cryptography used for DNS)
can obtain <code>www.your.server</code> certificates from Let's Encrypt
and can then freely impersonate <code>www.your.server</code>,
even if applications stop trusting all CAs other than Let's Encrypt.
"Certificate transparency" sees the new certificate but does not stop the attack.</p>
<p>Similarly,
an attacker controlling the DNS records for <code>www.your.server</code>
can turn off PQConnect for <code>www.your.server</code>,
or replace the legitimate PQConnect public key for <code>www.your.server</code>
with the attacker's public key.</p>
<p>The PQConnect protocol supports three approaches to stopping this attack.
First,
the PQConnect protocol is capable of protecting DNS itself.
We are planning more documentation and software for this;
stay tuned!</p>
<p>Second,
to the extent that other security mechanisms are deployed successfully for DNS,
they also protect PQConnect's server announcements.</p>
<p>Third,
the PQConnect protocol lets you use a high-security name that includes your server's public key.
For example,
instead of linking to
<a href="https://www.pqconnect.net">https://www.pqconnect.net</a>,
you can link to a
<a href="https://pq1u1hy1ujsuk258krx3ku6wd9rp96kfxm64mgct3s3j26udp57dbu1.yp.to">high-security PQConnect name</a>
for the same server,
as long as the application does not impose severe length limits (in, e.g., certificates).
Some client-side software steps are necessary to make sure that
all paths for attackers to substitute other names are closed off
(e.g., the key extracted from the PQConnect name
has to override any keys provided by CNAMEs,
and DNS responses sent directly to applications have to be blocked),
but this is conceptually straightforward.</p>
<h2><a name="ntruprime">Public-key encryption for fast key erasure: NTRU Prime</a></h2>
<p>Beyond encrypting data to the server's long-term McEliece public key,
a PQConnect client
applies another layer of encryption to a short-term public key provided by the server,
to enable fast key erasure.</p>
<p>This short-term public key uses a small-key lattice-based cryptosystem.
This choice has the advantage of reducing per-tunnel costs,
although this does not matter when there is a large amount of data per tunnel.
The disadvantage is that
lattice-based cryptography has
<a href="https://ntruprime.cr.yp.to/warnings.html">higher security risks</a>
than the McEliece cryptosystem,
and a break of the lattice-based cryptosystem would mean that keys are not erased,
although this does not matter unless the attacker also steals secrets from the device.</p>
<p>Trigger warning:
If you find patents traumatic,
or if your company has a policy to not learn about patents,
please stop reading at this point.</p>
<p><a href="https://patents.google.com/patent/US9094189B2/en">Unfortunately</a>,
<a href="https://patents.google.com/patent/US9246675B2/en">lattice</a>-<a href="https://patents.google.com/patent/CN107566121A/en">based</a>
<a href="https://patents.google.com/patent/CN108173643A/en">cryptography</a>
<a href="https://patents.google.com/patent/KR101905689B1/en">is</a>
<a href="https://patents.google.com/patent/US11050557B2/en">a</a>
<a href="https://patents.google.com/patent/US11329799B2/en">patent</a>
<a href="https://patents.google.com/patent/EP3698515B1/en">minefield</a>.
NIST has published
<a href="https://web.archive.org/web/20240331123147/https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/selected-algos-2022/nist-pqc-license-summary-and-excerpts.pdf">edited excerpts of a license</a>
that appears to cover two older patents (9094189 and 9246675),
but the license is only for Kyber;
meanwhile another patent holder, Yunlei Zhao,
has
<a href="https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Fm4cDfsx65s/m/F63mixuWBAAJ">written</a>
that "Kyber is covered by our patents".</p>
<p>Fortunately,
there is one lattice-based cryptosystem old enough for its patent to have
<a href="https://patents.google.com/patent/US6081597A">expired</a>,
namely NTRU.
Various security problems were discovered the original version of NTRU,
but all of the known issues
(and some other issues that make audits unnecessarily difficult)
are addressed by tweaks in
<a href="https://ntruprime.cr.yp.to">Streamlined NTRU Prime</a> (<code>sntrup</code>),
which was published in
<a href="https://ntruprime.cr.yp.to/ntruprime-20160511.pdf">May 2016</a>.
There were not many post-quantum patents at that point.
The current version of <code>sntrup</code> differs only in
some small tweaks to serialization and hashing published in
<a href="https://ntruprime.cr.yp.to/nist/ntruprime-20190330.pdf">April 2019</a>,
and patent searches have found no issues here.</p>
<p>Streamlined NTRU Prime was added to TinySSH and OpenSSH in 2019,
and was made default in OpenSSH in <a href="https://www.openssh.com/txt/release-9.0">2022</a>,
with no reports of any problems.
PQConnect also uses Streamlined NTRU Prime,
specifically <code>sntrup761</code>.
The software uses <a href="https://libntruprime.cr.yp.to">libntruprime</a>.</p>
<h2><a name="verif">Formal verification</a></h2>
<p>Most of the PQConnect security analysis so far is manual,
but symbolic security analysis of one component of PQConnect, namely the handshake,
is within reach of existing automated tools
and has been carried out using an existing prover,
namely Tamarin.
Running</p>
<pre><code>scripts/install-tamarin
scripts/run-tamarin
</code></pre>
<p>inside the PQConnect software package
will install Tamarin and verify the handshake.
See Section V of the
<a href="papers.html">NDSS 2025 paper</a>
for more information.</p><hr><font size=1><b>Version:</b>
This is version 2024.12.27 of the "Cryptography" web page.
</font>
</div>
</body>
</html>
|
