[openpgp] Clarify status of subkeys with certification use

[Kristian Fiskerstrand]

Hi,

From time to time there have been discussions about whether
certification subkeys are valid according to rfc4880. I don't believe
they should be, and I also believe the current specs can be read in a
way that it isn't, however I would ask that we are more explicit on it
in 4880bis in order to avoid any ambiguity. As far as I'm aware current
implementation will ignore certify capabilities of such subkeys.

Some background; section 11.1 of rfc4880 includes;

After the User ID packet or Attribute packet, there may be zero or
more Subkey packets. In general, subkeys are provided in cases where
the top-level public key is a signature-only key. However, any V4
key may have subkeys, and the subkeys may be encryption-only keys,
signature-only keys, or general-purpose keys. V3 keys MUST NOT have
subkeys.
...
Each Subkey packet MUST be followed by one Signature packet, which
should be a subkey binding signature issued by the top-level key.
For subkeys that can issue signatures, the subkey binding signature
MUST contain an Embedded Signature subpacket with a primary key
binding signature (0x19) issued by the subkey on the top-level key.

Arguably if certification was intended for subkeys, the list in the
former paragraph would likely not be explicitly mentioning
encryption-only and signature-only as well as general purpose keys,
without mentioning certifying keys, but rather say all subkeys or
similar. This is further strengthened by the second part that mentions
signatures (which is used for data in our context, whereby the use flag
for certifying other keys is clearly marked as such)

In any case, there have been discussions along the way, so I propose we
explicitly mark certification subkeys forbidden and ignored by
implementations.

Maybe something like;
"when generating a subkey binding signature, the implementation MUST NOT
set the certify usage flag. When interpreting a subkey binding
signature, implementations MUST ignore the certify subkey binding usage
flag if it is set."

PS! As a tangent point, we likely also want to change the default
behavior for no usage flag specified for v5 to be ignored as not having
a recognized flag, instead of defaulting to all features, although I
don't have a specific proposal for this.
--
----------------------------
Kristian Fiskerstrand
Blog: https://blog.sumptuouscapital.com
Twitter: @krifisk
----------------------------
Public OpenPGP keyblock at hkp://pool.sks-keyservers.net
fpr:94CB AFDD 3034 5109 5618 35AA 0B7F 8B60 E3ED FAE3
----------------------------
Ab esse ad posse
From being to knowing

[Neal H. Walfield]

Hi Kristian,

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.

We also want the master device to be able to revoke individual devices
if the device is compromised or retired, etc. Using certification
subkeys, it is straightforward to revoke an individual device: we just
revoke its certification subkey, which automatically revokes any
self-signatures that that certification subkey might have made.

(For those familiar with object capability terminology: one way to
think of a certification subkey is like a capability wrapper.)


Consequently, please do not remove certification subkeys from RFC
4880bis. If anything, I would prefer that RFC 4880bis clarifies that
certification subkeys should be supported.

Thanks,

:) Neal & Justus

On Mon, 07 May 2018 20:09:01 +0200,

[1 <multipart/signed (7bit)>]
[1.1 Clarify status of subkeys with certification use <multipart/mixed (7bit)>]
[1.1.1 <text/plain; utf-8 (quoted-printable)>]
Hi,
From time to time there have been discussions about whether
certification subkeys are valid according to rfc4880. I don't believe
they should be, and I also believe the current specs can be read in a
way that it isn't, however I would ask that we are more explicit on it
in 4880bis in order to avoid any ambiguity. As far as I'm aware current
implementation will ignore certify capabilities of such subkeys.
Some background; section 11.1 of rfc4880 includes;
After the User ID packet or Attribute packet, there may be zero or
more Subkey packets. In general, subkeys are provided in cases where
the top-level public key is a signature-only key. However, any V4
key may have subkeys, and the subkeys may be encryption-only keys,
signature-only keys, or general-purpose keys. V3 keys MUST NOT have
subkeys.
...
Each Subkey packet MUST be followed by one Signature packet, which
should be a subkey binding signature issued by the top-level key.
For subkeys that can issue signatures, the subkey binding signature
MUST contain an Embedded Signature subpacket with a primary key
binding signature (0x19) issued by the subkey on the top-level key.
Arguably if certification was intended for subkeys, the list in the
former paragraph would likely not be explicitly mentioning
encryption-only and signature-only as well as general purpose keys,
without mentioning certifying keys, but rather say all subkeys or
similar. This is further strengthened by the second part that mentions
signatures (which is used for data in our context, whereby the use flag
for certifying other keys is clearly marked as such)
In any case, there have been discussions along the way, so I propose we
explicitly mark certification subkeys forbidden and ignored by
implementations.
Maybe something like;
"when generating a subkey binding signature, the implementation MUST NOT
set the certify usage flag. When interpreting a subkey binding
signature, implementations MUST ignore the certify subkey binding usage
flag if it is set."
PS! As a tangent point, we likely also want to change the default
behavior for no usage flag specified for v5 to be ignored as not having
a recognized flag, instead of defaulting to all features, although I
don't have a specific proposal for this.
--
----------------------------
Kristian Fiskerstrand
Blog: https://blog.sumptuouscapital.com
----------------------------
Public OpenPGP keyblock at hkp://pool.sks-keyservers.net
fpr:94CB AFDD 3034 5109 5618 35AA 0B7F 8B60 E3ED FAE3
----------------------------
Ab esse ad posse
From being to knowing
[1.2 OpenPGP digital signature <application/pgp-signature (7bit)>]
[2 <text/plain; us-ascii (7bit)>]
_______________________________________________
openpgp mailing list
https://www.ietf.org/mailman/listinfo/openpgp

[Leo Gaspard]

Post by Neal H. Walfield
Hi Kristian,
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.
We also want the master device to be able to revoke individual devices
if the device is compromised or retired, etc. Using certification
subkeys, it is straightforward to revoke an individual device: we just
revoke its certification subkey, which automatically revokes any
self-signatures that that certification subkey might have made.
(For those familiar with object capability terminology: one way to
think of a certification subkey is like a capability wrapper.)
Consequently, please do not remove certification subkeys from RFC
4880bis. If anything, I would prefer that RFC 4880bis clarifies that
certification subkeys should be supported.
Thanks,
:) Neal & Justus

Another use case supporting this opinion: certification subkeys are also
a way to increase the security of an offline OpenPGP key, as with them
it becomes possible to put the master key behind a diode while still
being able to certify keys, and only ever move data out:
1. On the machine with the master key, generate a certification subkey
2. Move the certification subkey to another system, less trusted
3. Push the to-be-signed key to this other system
4. On this other system, certify the to-be-signed key
5. Rotate the certification subkey from time to time to be able to
revoke one were it compromised

This thus enables people to participate to the WoT without compromising
master key security. I wanted to do this for my key, but learned that it
was a not-very-supported capability bit, and had to fallback to pushing
the to-be-signed keys to my offline system, thus making it handle
untrusted data.

So I think clarifying that certification subkeys MUST be supported would
be better indeed, so that people can assume RFC4880bis-compliant
implementations do support them, both for the use case described by Neal
(ie. usability) and this one (ie. security).

Just my 2¢,
Leo

[Kristian Fiskerstrand]

Post by Leo Gaspard
Another use case supporting this opinion: certification subkeys are also
a way to increase the security of an offline OpenPGP key, as with them
it becomes possible to put the master key behind a diode while still
1. On the machine with the master key, generate a certification subkey
2. Move the certification subkey to another system, less trusted
3. Push the to-be-signed key to this other system
4. On this other system, certify the to-be-signed key
5. Rotate the certification subkey from time to time to be able to
revoke one were it compromised

I'm not sure I buy this argument, the WoT is expected to be long-term,
if needing to do rotation of certification subkey, it sounds like you're
making it more temporary of sorts. Wouldn't just having a separate CA
key that is fully trusted (presumably locally signed and not exportable)
accomplish much of the same for more "temporary" signatures, i.e those
not exported to view of the rest of the ecosystem / external users?
--
----------------------------
Kristian Fiskerstrand
Blog: https://blog.sumptuouscapital.com
Twitter: @krifisk
----------------------------
Public OpenPGP keyblock at hkp://pool.sks-keyservers.net
fpr:94CB AFDD 3034 5109 5618 35AA 0B7F 8B60 E3ED FAE3
----------------------------
There are two tragedies in life. One is to lose your heart's desire. The
other is to gain it.
- George Bernard Shaw

[Leo Gaspard]

Post by Kristian Fiskerstrand

Post by Leo Gaspard
Another use case supporting this opinion: certification subkeys are also
a way to increase the security of an offline OpenPGP key, as with them
it becomes possible to put the master key behind a diode while still
1. On the machine with the master key, generate a certification subkey
2. Move the certification subkey to another system, less trusted
3. Push the to-be-signed key to this other system
4. On this other system, certify the to-be-signed key
5. Rotate the certification subkey from time to time to be able to
revoke one were it compromised

I'm not sure I buy this argument, the WoT is expected to be long-term,
if needing to do rotation of certification subkey, it sounds like you're
making it more temporary of sorts. Wouldn't just having a separate CA
key that is fully trusted (presumably locally signed and not exportable)
accomplish much of the same for more "temporary" signatures, i.e those
not exported to view of the rest of the ecosystem / external users?

Sorry if I was unclear, the idea was not to make the certification
subkey temporary, but to only use it for a given period of time, and
then delete it (while not revoking or expiring it).

This way so long as there is no compromise of the certification subkey
things stay exactly the same, but when a certification subkey is
compromised (eg. because it had to parse a malformed public key to sign
it, or due to an attack on the way the data was transferred or any other
attack), it can simply be revoked, without compromising the master key
and its UID signatures.

The idea of rotation was thought to not invalidate all the
previously-made signatures in case of compromise, but an alternative
could be to not rotate so long as the certification subkey is not
compromised, and on certification subkey compromise tighten the WoT by
that much.

Sorry for the wording of point 5, it was not clear at all indeed.
Hopefully it's better now.

[Daniel Kahn Gillmor]

Post by Leo Gaspard
Another use case supporting this opinion: certification subkeys are also
a way to increase the security of an offline OpenPGP key, as with them
it becomes possible to put the master key behind a diode while still

you might have made the master key "more secure", but you've done so by
transfering the capabilities of the master key (certification) out to
the less-controlled keys. what's the win here? secret keys are not in
themselves important objects -- what's important is the capabilities
that the network assigns to the corresponding public keys.

Also, when some certification in a chain has an expiration date on it,
is the whole chain of certifications bound by the narrowest
("bottleneck") expiration date, or is there some other governing
principle?

And when a leaf certifiation expires earlier than marked because some
middle element in the chain becomes unusable (remember, subkey
expiration dates can change; subkeys can be revoked), how would you
present this change to the user?

And further still: how many levels deep should such a certification
chain go?

I think it's pretty easy to argue "0 levels" (i.e. "no
certification-capable subkeys") for simplicity of implementation and
usability concerns.

I'd suggest that no implementation is willing to argue for "∞ levels"
because at some point the chain of verification becomes too expensive to
cope.

Are you arguing for some particular limited level of depth? if so, how
do you justify that level?

--dkg

[Leo Gaspard]

Post by Daniel Kahn Gillmor

Post by Leo Gaspard
Another use case supporting this opinion: certification subkeys are also
a way to increase the security of an offline OpenPGP key, as with them
it becomes possible to put the master key behind a diode while still

you might have made the master key "more secure", but you've done so by
transfering the capabilities of the master key (certification) out to
the less-controlled keys. what's the win here? secret keys are not in
themselves important objects -- what's important is the capabilities
that the network assigns to the corresponding public keys.

Well, I'd argue the master secret key *is* an important object: it has
accumulated UID signatures that may become impossible to recover were it
to have to be revoked.

Hence this idea, allowing to revoke a certification subkey, that in
itself has no value indeed.

Post by Daniel Kahn Gillmor
Also, when some certification in a chain has an expiration date on it,
is the whole chain of certifications bound by the narrowest
("bottleneck") expiration date, or is there some other governing
principle?

I'd say the narrowest expiration date would make most sense (actually, I
can't think of any other reasonable way to handle expiration dates).

Post by Daniel Kahn Gillmor
And when a leaf certifiation expires earlier than marked because some
middle element in the chain becomes unusable (remember, subkey
expiration dates can change; subkeys can be revoked), how would you
present this change to the user?

Well, isn't that the same issue as when a previously-trusted master key
that had signed the end-of-chain key expires / is revoked?

Post by Daniel Kahn Gillmor
And further still: how many levels deep should such a certification
chain go?
I think it's pretty easy to argue "0 levels" (i.e. "no
certification-capable subkeys") for simplicity of implementation and
usability concerns.
I'd suggest that no implementation is willing to argue for "∞ levels"
because at some point the chain of verification becomes too expensive to
cope.
Are you arguing for some particular limited level of depth? if so, how
do you justify that level?

For my use case (ie. protecting the master key), a single level is
necessary, and there is a need only for a single certification subkey

For Neal's use case, I haven't thought extensively about it, but think
one could be enough, depending on whether we want the user to have to
access his master key when adding a device (and I guess we want, as
otherwise revocation of a device-that-had-signed-another-device becomes
a UI nightmare)

So, I'd say, one ?

[Neal H. Walfield]

On Fri, 25 May 2018 21:46:42 +0200,

Post by Daniel Kahn Gillmor
you might have made the master key "more secure", but you've done so by
transfering the capabilities of the master key (certification) out to
the less-controlled keys. what's the win here? secret keys are not in
themselves important objects -- what's important is the capabilities
that the network assigns to the corresponding public keys.

The difference between a primary key and a certification subkey is
that the primary key is the user's globally unique, long-term
identity. If the certification subkey is somehow compromised, it can
be revoked without requiring the user to get a new cryptographic
identity, which is a pain to distribute.

Post by Daniel Kahn Gillmor
Also, when some certification in a chain has an expiration date on it,
is the whole chain of certifications bound by the narrowest
("bottleneck") expiration date, or is there some other governing
principle?

I'm not sure what you mean here. It seems obvious to me that if any
edge in a trust path is broken, then the path becomes invalid just
like in the WoT.

Post by Daniel Kahn Gillmor
And when a leaf certifiation expires earlier than marked because some
middle element in the chain becomes unusable (remember, subkey
expiration dates can change; subkeys can be revoked), how would you
present this change to the user?

Why do you think it is necessary to present this information to the
use? Right now, signatures and keys can be revoked and this breaks
trust paths in the WoT in a similar way, but there is no UI to show
what happened.

But, if you wanted to, sure, you could create some UI to prompt the
user to either extend the expiration of the middle certification
subkey or to hoist up the leaf certification subkey, but signing it
with a still-valid certification key.

Post by Daniel Kahn Gillmor
And further still: how many levels deep should such a certification
chain go?
I think it's pretty easy to argue "0 levels" (i.e. "no
certification-capable subkeys") for simplicity of implementation and
usability concerns.
I'd suggest that no implementation is willing to argue for "$B!g(B levels"
because at some point the chain of verification becomes too expensive to
cope.

Unless it is possible to create a quine, the chain can't be infinite.
(But, it is worth pointing out that we do need to detect cycles.)

Because I think auditable delegation of authority is useful, I'd argue
for something like 32 levels as a recommended limit. 32 levels is
probably more than enough for most uses without requiring too much
acrobatics from the implementations.

:) Neal

[Neal H. Walfield]

On Fri, 25 May 2018 12:26:54 +0200,

Post by Leo Gaspard
Another use case supporting this opinion: certification subkeys are also
a way to increase the security of an offline OpenPGP key, as with them
it becomes possible to put the master key behind a diode while still

FWIW, this workflow does not require certification subkeys. You can
instead create two keys, an offline key and an online
certification-only key. Then, you *t*sign the certification key using
the offline key. This means that anyone who adds your offline key as
a trusted introducer will automatically trust your online
certification key. Check out Section 6.3.12 of the following text for
more details:

https://gnupg.org/ftp/people/neal/an-advanced-introduction-to-gnupg/an-advanced-introduction-to-gnupg.pdf

:) Neal

[Leo Gaspard]

Post by Neal H. Walfield
On Fri, 25 May 2018 12:26:54 +0200,

Post by Leo Gaspard
Another use case supporting this opinion: certification subkeys are also
a way to increase the security of an offline OpenPGP key, as with them
it becomes possible to put the master key behind a diode while still

FWIW, this workflow does not require certification subkeys. You can
instead create two keys, an offline key and an online
certification-only key. Then, you *t*sign the certification key using
the offline key. This means that anyone who adds your offline key as
a trusted introducer will automatically trust your online
certification key. Check out Section 6.3.12 of the following text for
https://gnupg.org/ftp/people/neal/an-advanced-introduction-to-gnupg/an-advanced-introduction-to-gnupg.pdf
:) Neal

Indeed it's already possible, the issue with this solution being that
people willing to rely on signatures by the master key now need to
download two keys (the master key and the trusted introducer), and
another one after any compromise, while certification subkeys are
downloaded and updated at the same time as the master key, thus making
for more easy-to-use WoT.

Then, I do agree that it's a somewhat infrequent use case, which is the
reason why I did not post it here until you came with a more convincing
one :)

Leo

[Neal H. Walfield]

On Sun, 27 May 2018 19:00:04 +0200,

Post by Leo Gaspard
Indeed it's already possible, the issue with this solution being that
people willing to rely on signatures by the master key now need to
download two keys (the master key and the trusted introducer), and
another one after any compromise, while certification subkeys are
downloaded and updated at the same time as the master key, thus making
for more easy-to-use WoT.

That's true. But, I'd argue that this is more of a tooling problem:
when the tool is computing the WoT and it encounters a trusted
introducer has tsigned a key, which is not available, it should
proactively download the key.

:) Neal

[Leo Gaspard]

Post by Neal H. Walfield
On Sun, 27 May 2018 19:00:04 +0200,

Post by Leo Gaspard
Indeed it's already possible, the issue with this solution being that
people willing to rely on signatures by the master key now need to
download two keys (the master key and the trusted introducer), and
another one after any compromise, while certification subkeys are
downloaded and updated at the same time as the master key, thus making
for more easy-to-use WoT.

when the tool is computing the WoT and it encounters a trusted
introducer has tsigned a key, which is not available, it should
proactively download the key.

Hmm, I'm not sure it's possible? I mean, if I'm a user, there are 3 keys
to me:
1. The master key that I trust
2. The trusted introducer
3. The key whose validity I want to check

As a user, I have only access to 1 and 3: 1 because I signed it, and 3
because I want to check it. I have /a priori/ no access to key 2. When
could I fetch it?

By policy (and I think it's reasonable for metadata protection reasons),
(most?) implementations do not fetch keys on-the-fly during things like
signature checking or encryption. So I must have had access to the key 2
before that.

However, there is no way (as far as I know) to fetch key 2 when I have
only key 1, as the information of which key a key has tsigned is not
stored in the tsigning key.

So the only moment left for the tooling to download key 2 is when
fetching key 3: when downloading a key, it would automatically download
all keys that have signed it. I think that's possible, but not
necessarily reasonable, as it'd lead to surprising behaviour (importing
more keys than expected), and thus potentially to vulnerabilities on
other tools that wouldn't expect this behaviour.

Now, I was putting this forward mostly for giving another use case that
would naturally benefit from certification-able subkeys, I agree that it
certainly wouldn't deserve the added complexity were it the only use
case of them :)

[Neal H. Walfield]

On Sun, 27 May 2018 23:31:39 +0200,

Post by Leo Gaspard

Post by Neal H. Walfield
On Sun, 27 May 2018 19:00:04 +0200,

Post by Leo Gaspard
Indeed it's already possible, the issue with this solution being that
people willing to rely on signatures by the master key now need to
download two keys (the master key and the trusted introducer), and
another one after any compromise, while certification subkeys are
downloaded and updated at the same time as the master key, thus making
for more easy-to-use WoT.

when the tool is computing the WoT and it encounters a trusted
introducer has tsigned a key, which is not available, it should
proactively download the key.

Hmm, I'm not sure it's possible? I mean, if I'm a user, there are 3 keys
1. The master key that I trust
2. The trusted introducer
3. The key whose validity I want to check
As a user, I have only access to 1 and 3: 1 because I signed it, and 3
because I want to check it. I have /a priori/ no access to key 2. When
could I fetch it?

Right. One thing that you can do right now is to fetch the keys that
signed the master key: it is not unusual for key validation to be
symmetric. The other thing is for the key servers to add an extension
to return all keys signed by a given key.

Post by Leo Gaspard
By policy (and I think it's reasonable for metadata protection reasons),
(most?) implementations do not fetch keys on-the-fly during things like
signature checking or encryption. So I must have had access to the key 2
before that.

Accessing the keys via Tor partially mitigates this problem. But,
there is no reason to only fetch the keys when needed. See, for
instance, parcimonie for how to do this in a privacy preserving way.

:) Neal

[Kristian Fiskerstrand]

Post by Neal H. Walfield
Hi Kristian,

Hi Neal and Justus,

Post by Neal H. Walfield
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.

Wouldn't you anyways break the per-device nature if using this
certification subkey to sign a third party keyblock, and the loss of one
of the devices impacted your validity calculation across the ecosystem?

Using this in such a per-device nature also seems to require rather
special attention from the user/client, I could easily imagine ending up
with a web of cross-signatures across multiple devices here.

Post by Neal H. Walfield
Consequently, please do not remove certification subkeys from RFC
4880bis. If anything, I would prefer that RFC 4880bis clarifies that
certification subkeys should be supported.

if we are removing it and not just making the current state more precise :)

In any case; I'm not sure if this is a use-case I favor much personally,
but it is an interesting concept so thanks for bringing it up for
discussion.
--
----------------------------
Kristian Fiskerstrand
Blog: https://blog.sumptuouscapital.com
Twitter: @krifisk
----------------------------
Public OpenPGP keyblock at hkp://pool.sks-keyservers.net
fpr:94CB AFDD 3034 5109 5618 35AA 0B7F 8B60 E3ED FAE3
----------------------------
"Statistics are like a bikini. What they reveal is suggestive, but what
they conceal is vital."
(Aaron Levenstein)

[Daniel Kahn Gillmor]

Post by Neal H. Walfield
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), 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), or they provide a
convenient mechanism for a wiretap capability (sneak in an extra
certification key for a user somehow).

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.

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.

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.

So i'm still on the side of trying to make more explicit the current
assumption that only primary keys hold certification capabilities.

--dkg

[Neal H. Walfield]

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,

Post by Daniel Kahn Gillmor

Post by Neal H. Walfield
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.

Post by Daniel Kahn Gillmor
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.

Post by Daniel Kahn Gillmor
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.

Post by Daniel Kahn Gillmor
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.

Post by Daniel Kahn Gillmor
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.

Post by Daniel Kahn Gillmor
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

[Werner Koch]

Post by Neal H. Walfield
0x04 - This key may be used to encrypt communications.
0x08 - This key may be used to encrypt storage.

Which was done to mimic the X.509 usage. X.509 required such a flag to
differentiate between a sinnging and an encryption certificate. Even in
the case that two certificates are issued (additional costs to the user)
there is no fine grained distinction. Note that I am talking about
certificates for mail processing.

OpenPGP does not need this because subkeys are a more useful thing than
trying to find matching certificates. Fine grain key usage flags
doesn't gain you anything than complexity and unclear semantics. See
X.509's keyUsage and extendedKeyUsage extensions to see where it will
lead.

Post by Neal H. Walfield
the newest one, AFAIK. But, there is precedence for encrypting to all
valid encryption capable subkeys: this is what OpenKeychain does.

I doubt that this has any practical security gain over copying all
needed subkeys to all devices. After all you want to read with all
devices and the sender has no way to tell which device you are currently
using. Rotating the keys is a much cleaner way to limit damage in case
of a device compromise.

Post by Neal H. Walfield
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.

Actually this was implemented ~20 years ago after consultation with
Caspar Bowden of FIPR and Ben Laurie. The use case back then was to
limit the damage done by the RIPA.


Salam-Shalom,

Werner


p.s.
Proper key rotation requires a lot of OPSEC and diligent use of
comminucation tools. The problem we have are not forward secrecy but
the general non-use of encryption and, worse, the insecurity of the
equipment.