Re: [openpgp] Clarify status of subkeys with certification use

["Neal H. Walfield" <[e-mail]>]

Hi Daniel,

Thanks for your comments.  We want to put forth a more complete
proposal so that you hopefully better understand what we are trying to
do.  This will hopefully clarify some of your concerns.

Forward Secrecy and Multi-Device Support
========================================

We want to support automatic forward secrecy in a multiple device
context.  At least initially, we intend to do it a bit like Ian Brown
et al. described in their internet draft [1].

  [1] https://tools.ietf.org/html/draft-brown-pgp-pfs-03

Basically, we want to automatically rotate encryption subkeys on a
regular basis.  (Perhaps later we can figure out how to do something
like Signal's double rachet.)

If the user has multiple devices, we see two ways to do key rotation.

First, the primary device (however that is selected), periodically
generates a new encryption subkey, and somehow(!) shares it with the
other devices.  If the user doesn't use the primary device for awhile,
and the subkeys expire, some other device will have to create the new
keys.  But, this introduces a potential race.

Second, each device rotates its own encryption subkey.  Whereas in the
first case, all devices did not strictly require access to a
certification-capable key, now all devices need access to one.  The
simplest solution would be to just give each device a copy of the
primary key, as you appear to suggest.  But, providing each device
with its own certification-capable subkey has the advantage that it is
possible to revoke a device.  Users already understand this workflow:
if you have a google account, an amazon account, etc., it is possible
to decommission individual devices.  Further, using
certification-capable subkeys makes it possible to keep the primary
key offline.

When the user revokes a device, the UI could ask the user whether
certification-capable subkeys signed by that key, and third-party
certificates created by that key should remain valid.  For instance,
if "laptop" was used to provision "cell phone" and "laptop" is
decommissioned from "desktop", then decomissioning "laptop"
transitively decomissions "cell phone".  To avoid this, "desktop"
could recertify "cell phone".

In the above example, we named the devices.  It might be reasonable to
make this information first class.  This way the UI can use sensible
names.  Also, similar to Jabber with its named resources, it is easy
to imagine some advanced option that allows the sender to make her
message decryptable on only a subset of the recipient's devices.

Finally, if accidental commissioning of a fake device is a real
concern, the user's OpenPGP software could show a note when it detects
that a new device has been commissioned similar to: "It looks like
device 'foo' recently commissioned device 'bar', if this was not
intended, then 'foo' was probably compromised."

Forward Secrecy
===============

The basic idea behind forward secrecy is that old keys are deleted
after a sunset period.  OpenPGP has traditionally been used to protect
both data at rest as well as data in motion.  At first blush, this
usage appears to be at odds with forward secrecy.  But, OpenPGP
actually already has provisions for forward secrecy.  Moreover, it is
possible to have both transport encryption and storage encryption in a
backwards compatible way.

First, OpenPGP foresees two types of encryption keys:

  0x04 - This key may be used to encrypt communications.
  0x08 - This key may be used to encrypt storage.

  https://tools.ietf.org/html/rfc4880#section-5.2.3.21

When generating a key in Sequoia, we intend to generate two encryption
subkeys: a communication encryption subkey, and a storage encryption
subkey.  When a program using Sequoia wants to encrypt a message, it
specify whether protection is only needed during transportation or
whether the message is intended to be archived.

Since only one storage encryption subkey is needed (it is not
rotated), it can be stored on a smart card (along with the primary
certification key!).

It turns out this usage is nearly completely backwards compatible to
GnuPG: when GnuPG generates an encryption capable subkey, it makes it
both a communication and a storage encryption key.  The only issue, is
that if there are multiple valid encryption subkeys, GnuPG only uses
the newest one, AFAIK.  But, there is precedence for encrypting to all
valid encryption capable subkeys: this is what OpenKeychain does.

Session Key Store
=================

People assume that, e.g., their email remains readable long after
they've received it.  Unfortunately, if we use forward secrecy and
don't change the MUAs to locally store the decrypted message, this
will no longer be the case.  To work around this, we can maintain a
session key store.  This is just a map from an encrypted session key
to the decrypted session key.  Then, once a message is decrypted, we
don't need the asymmetric key to decrypt it again.

Unfortunately, if the session key store is somehow compromised, this
means that a copy of the message remains decryptable even if the user
deleted the message.  This can be partially mitigated by allowing
programs (e.g., a MUA) to purge session keys when they delete the
message.  Of course, this is not so easy when there are multiple
devices.  But, even ignoring this problem, having a session key store
is no worse than the status quo.  And, if this behavior is embraced,
developers will hopefully change their software to improve their
behavior.  Changing notmuch would probably be very straightforward.


Alternatively, we could keep old messages readable by reencrypting the
session key using, e.g., the storage encryption key.  This requires
the ability to rewrite the message, which is not always possible or
desirable.

Another option is to not actually delete the old encryption subkeys,
but to encrypt them using the storage encryption key.

Key Distribution
================

If we aggresively rotate keys (and, we are currently thinking of doing
this once a week), then we need to distribute the keys.  The key
servers appear to be a convenient way to do this.  But, many users are
concerned about having their personal information published.  To
resolve this conflict, we plan to *not* publish user id or user
attribute packets.  This is better than Signal's key servers, which,
AIUI, associate keys with telephone numbers.


Key Rotation
============

To avoid having a period of time during which no encryption-capable
key is available for a device either because the device hasn't had an
opportunity to generate new keys, or the sender hasn't been able to
refresh the key from the key servers, we plan to publish keys in
advance.  For instance, we will create keys covering, say, the next 6
months.  By setting the creation time and expiration time
appropriately, only one key per device will be valid at any given
time.  AFAIUI, recent versions of GnuPG respect this.

We plan to generate new keys when a low-water mark is reached, say,
three months before the last key expires.


On Fri, 25 May 2018 22:00:58 +0200,
Daniel Kahn Gillmor wrote:
> On Fri 2018-05-25 11:59:44 +0200, Neal H. Walfield wrote:
> 
> > Justus and I have been thinking about how to realize per-device keys
> > and approximate forward secrecy.  These two things are related: if we
> > want devices to do their own key rotation (and I think this is
> > sensible, as the alternative is to somehow regularly transfer secret
> > key material to each device), then the devices need to be able to
> > generate self-signatures.  Since we don't want all devices to have
> > access to the primary key, each device could have its own
> > certification subkey.
> 
> I've also been thinking about how to do forward secrecy, but i think
> i've come to the opposite result as Neal and Justus here.
> 
> Per-device keys are bad for user privacy (they leak how many devices the
> user has),

This is leaked in other ways.  And, this is also leaked by Signal,
AFAIUI.  If this is a serious concern, it would be possible to publish
decoy keys.

> and they either complicate any potential interface for
> cryptographic identity verification (i now need to somehow both know and
> understand the range of devices held by my peer),

I don't understand this.  Using a certification-capable subkey, there
is still only a single cryptographic identity established by the
primary key.

> or they provide a convenient mechanism for a wiretap capability
> (sneak in an extra certification key for a user somehow).

I don't understand this argument either: if someone is able to trick
me into generating an extra certification subkey and sending it to
them, they could probably just as easily trick me into send them a
copy of my master key.

> you can still keep a primary certification-capable key offline (or on a
> "master" client), while retaining the ability to revoke access to
> certain clients -- you just need to revoke existing subkeys, and provide
> all remaining good clients with the new subkeys, so i don't see
> certification-capable subkeys as a win there either.

If the primary certification-capable key is offline, then we can't
easily do key rotation.

> And i believe that sensible clients connected to a single account will
> need a way to synchronize *other* state as well -- not just secret keys
> -- so there's not much of a savings on the difficulty of state
> synchronization here anyway.

Perhaps.  But, regularly transmitting key material seems like a bad
idea.  If the new subkey is encrypted using the old one, then if an
attacker exfiltrates any subkey, it is possible to get all subsequent
ones.  If the subkeys are created on the device, then when the subkeys
are rotated, the attacker's access is lost and the exfiltration must
be repeated.

> Additionally (as i wrote elsewhere in this thread) i think they
> represent pretty serious implementation complexity, which i don't think
> is healthy for the ecosystem.

I don't think that the added complexity is that large.  When I verify
a signature, I can't assume it was made by the primary key, but I need
to find the right certification key, and also validate that key, if it
is not the primary key.


:) Neal & Justus