Moving forward: Forward Secrecy in OpenPGP
Justus Winter <justus@sequoia-pgp.org>

DeltaX Freiburg, 2018-07-21
https://sequoia-pgp.org/talks/2018-08-moving-forward

Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

1 / 19Forward Secrecy

compromise of long-term keys does not compromise session keys
not: Backward Secrecy aka Future Secrecy aka Post Compromise
Security

TLS (DHE-*), OTR, Signal, OMEMOin short:
use Diffie-Hellman key exchange to derive session keys
use long-term keys to authenticate the exchangeForward Secrecy is a property of transport security

Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

2 / 19

Data at rest vs. data in motion
OpenPGP may also be used for backups, archives, etc.
OpenPGP already supports this distinction!
Key Flags1 to the rescue:
0x04 - This key may be used to encrypt communications.
0x08 - This key may be used to encrypt storage.

Compatibility
Sequoia
31

GnuPG
7

OpenKeychain
7

openpgp.js7

rnp7

Section 5.2.3.21 of RFC4880

Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

3 / 19Approximating Forward Secrecy I
suggested by Brown et al in 20012
use short-lived encryption subkeys
generate and publish in advance
trivial to implement, requires no changes to peers% gpg -k futura
pubed25519 2018-06-11 [SC] [expires: 2019-06-10]
D2784F6DDEB59AB4162CCD3E0F08F2796B0B71E2
uid[ unknown] Futura Proofa <futura@example.org>[...]
subcv25519 2018-07-23 [E] [expires: 2018-07-30]
subcv25519 2018-07-16 [E] [expires: 2018-07-23]
subcv25519 2018-07-09 [E] [expires: 2018-07-16]2https://tools.ietf.org/html/draft-brown-pgp-pfs-03

Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

4 / 19Approximating Forward Secrecy II
example:encryption keys valid for a weekpublish half a year worth of keys

cons:
all messages sent in a week are encrypted using the same key
generating keys in advance is a window for compromise

pros:
good backwards compatibility
way better than the status quoCompatibility
Sequoia
3GnuPG
3OpenKeychain
3

openpgp.js3rnp
7

Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

5 / 19Interludum: Multi-device support
OpenPGP lacks a convincing story for multi-device support. Two options3 :1 sharing decryption-capable keys across devices+ hides number of devices– requires synchronization between co-agents
2

distinct per-device decryption-capable keys
+ requires synchronization only at setup± requires synchronization with remote peers+ still possible to hide number of devices by sharing– requires minor modifications– size of the certificate– complexityp≡p and Autocrypt synchronize using hidden mails:
OpenPGP is transport protocol independent
how does that work in practice?
3dkg’s post to the MLS list

Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

6 / 19

Simple per-device encryption keys

% gpg -k two
pub
ed25519 2018-06-08 [SC] [expires: 2019-06-07]
2B7757D8AF283468A0574699910E554478CCDE00
uid[ unknown] Two Fish <two@example.org>
subcv25519 2018-06-08 [E] [expires: 2019-06-07]
subcv25519 2018-06-08 [E] [expires: 2019-06-07]

Compatibility
Sequoia
3

GnuPG
7

OpenKeychain
3

openpgp.js
7

rnp
7

Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

7 / 19

Certification-capable subkeys
short-lived encryption subkeys require recurrent synchronization
our proposal4 :use a set of keys per device:a certification subkey: to issue their own subkeys
a signing subkey
n encryption subkeys

use e.g. a QR-code containing an encrypted key and a binding
signature to provision a new device
requires clarification in the RFC, minor changes in implementations

CompatibilitySequoia
74GnuPG
7

OpenKeychain
7

openpgp.js
7

rnp3!?!

Post to openpgp@ietf.org

Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

8 / 19Per-device keys: Example
Example key

new key, maybe on a Gnuk

primary key [C]subkey [Er ]subkey [A]Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

9 / 19Per-device keys: Example
Example key

new key, maybe on a Gnuk

primary key [C]subkey [Er ]commission desktop

subkey [A]subkey [C]: "desktop"
subkey [S]n subkeys [Et ]Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

9 / 19Per-device keys: Example
Example key

new key, maybe on a Gnuk

primary key [C]subkey [Er ]commission desktop

subkey [A]subkey [C]: "desktop"

commission laptop fromdesktop

subkey [S]n subkeys [Et ]subkey [C]: "laptop"
subkey [S]n subkeys [Et ]Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

9 / 19Per-device keys: Example
Example key

new key, maybe on a Gnuk

primary key [C]subkey [Er ]commission desktop

subkey [A]subkey [C]: "desktop"

commission laptop fromdesktopsubkey [S]n subkeys [Et ]subkey [C]: "laptop"
subkey [S]n subkeys [Et ]commission phone fromdesktopsubkey [C]: "mobile phone"
subkey [S]n subkeys [Et ]Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

9 / 19Per-device keys: Example
Example key

new key, maybe on a Gnuk

primary key [C]subkey [Er ]commission desktop

subkey [A]subkey [C]: "desktop"

commission laptop fromdesktopsubkey [S]n subkeys [Et ]subkey [C]: "laptop"
subkey [S]n subkeys [Et ]subkey [C]: "mobile phone"
subkey [S]n subkeys [Et ]commission phone fromdesktopdecommissioning desktop
recursively decommissions alldevices

Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

9 / 19Per-device keys: Example
Example key
primary key [C]subkey [Er ]subkey [A]subkey [C]: "desktop"

desktop is decommissioned

subkey [S]n subkeys [Et ]Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

10 / 19Per-device keys: Example
Example key
primary key [C]subkey [Er ]subkey [A]subkey [C]: "desktop"
subkey [S]n subkeys [Et ]desktop is decommissioned
commission laptop again from
Gnuk

subkey [C]: "laptop"
subkey [S]n subkeys [Et ]Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

10 / 19Per-device keys: Example
Example key
primary key [C]subkey [Er ]subkey [A]subkey [C]: "desktop"
subkey [S]n subkeys [Et ]subkey [C]: "laptop"
subkey [S]n subkeys [Et ]subkey [C]: "mobile phone"

desktop is decommissioned
commission laptop again fromGnukcommission phone from laptop

subkey [S]n subkeys [Et ]Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

10 / 19

Signal’s Double Ratchet

DH and KDFs ratchets toderive session keysa
also provides Backward Secrecy
sending and receiving ratchets
SK derived from KDF ratchet
DH ratchet pingpongs
per device keys
one DR per device pair
Signal and OMEMO use aserver for initial DH keys

aDouble Ratchet specification

Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

11 / 19

Ditching the server

Signal/OMEMO:

Initial message
PKESKSEIPOPS
LiteraldataSignature+DRInitMDC

generate n DH keys on devices, publish
initiator picks one from the server
nasty race condition in OMEMO

our idea:
ditch the server
sacrifice protecting the first mailinclude initialization in a traditional
OpenPGP encrypted message

multiple devices
initiator generates all keys for one’s own
devicesencrypts these keys with the per-device
encryption subkeys

Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

12 / 19Double Ratchet initialization - setting
Alice has two devices, a laptop (L), and a phone (P). Bob has a desktop(D). Alice wants to send Bob a message from her laptop, they have notused the ratchet algorithm before. 3 ratchets: (L,D), (P,D), and (L,P).

L
DHL,D

DHL,P
R(L,P)

R(L,D)
DHD,L

DHP,L
P

R(P,D)

DHP,D

D

DHD,P

Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

13 / 19

Double Ratchet initialization I

Alice generates four DH pairs.
Two for the laptop, two for thephone.
Alice sends a SEIP container
with the message and the DHkeys.

L
DHL,D

DHL,P
R(L,P)

R(L,D)
DHD,L

DHP,LP

R(P,D)

DHP,D

D

DHD,P

AliceL -> Bobpubpub
DRInit{pub: [DHpub
L,D , DHP,D ], sec: [EncP (SgnL (DHP,D , DHP,L , DHL,P ))]}

Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

14 / 19

Double Ratchet initialization II

L
DHL,D

DHL,P

Bob generates two DH key
pairs, initializes his ratchets.
Bob sends his DH public key,
and reflects all secrets.

R(L,P)

R(L,D)
DHD,L

DHP,L
P

R(P,D)

DHP,DD

DHD,P

Bob -> Alicepub
DRESK{pub: DHpub
D,L , sec: EncP (SgnL (DHP,D , DHP,L , DHL,P )), esk: . . . }pub
DRESK{pub: DHpub
D,P , sec: EncP (SgnL (DHP,D , DHP,L , DHL,P )), esk: . . . }Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

15 / 19

Double Ratchet initialization III
Alice’s phone decrypts theinitial DH key pairs generated
on the desktop, and uses themto initialize her ratchets.
The Double Ratchet algorithm
initialization is now complete.
To send more messages, sheadvances her two phoneratchets by creating two new
DH pairs.

L
DHL,D

DHL,P
R(L,P)

R(L,D)
DHD,L

DHP,L
P

R(P,D)

DHP,D

D

DHD,P

AliceP -> Bob
DRESK{pub: DH’pub
P,D , sec: ∅, esk: CipherR(P,D) (SK), PN, Ns }DRESK{pub: DH’pub
P,L , sec: ∅, esk: CipherR(P,L) (SK), PN, Ns }Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

16 / 19

Double Ratchet in OpenPGP
What is needed to implement Forward Secrecy using the Double Ratchetalgorithm?
per-device keys
two new packets, DRInit and DRESK
keeping a lot of state in implementations
Juicy, but tricky. So let’s go for Brown’s short-lived encryption subkeys
version first!

Ask questions! Get involved! Let’s get Forward Secrecy into OpenPGP!

Checkout our repository of weird keys5 .
5https://gitlab.com/sequoia-pgp/weird-keys

Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

17 / 19

Bonus: Long-term Storage

Users expect to be able to read past mails. Two options:store session keys
we (Sequoia) want to do that anyway for speed
compromise of session key store compromises messages
need to purge session key if message is deleteddeletability!

requires one-time synchronization for new devices

re-encrypt with long-term archive key
not desirable if messages are on a server (IMAP)

Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

18 / 19

Bonus: Privacy-preserving keys{,ervers}
critical for revocations/key renewals/new keys
traditional keyservers are problematic
expose the social graphexpose names/email addresses

idea: strip 3rd-party-certificates, uids

Compatibility
null-uid
no-bound-uid
no-uiddirect-key

Sequoia
33
37

GnuPG
377
7

OpenKeychain
377
7

openpgp.js
377?

rnp
777
3

Justus Winter <justus@sequoia-pgp.org>Moving forward: Forward Secrecy in OpenPGP
DeltaX Freiburg, 2018-07-21

19 / 19