Subject: [openpgp] Keyserverless Use of OpenPGP in Email

From: Vincent Breitmoser <[email-masked]>
Date: Tue, 12 Apr 2016 14:15:49 +0200

Hi,

(crossposting to openpgp-email and openpgp-wg, the lists where I expect
the highest rates of interested people)

I'd like to discuss a thought that has come up in my work on k9 mail:
Using OpenPGP in E-Mail without relying on keyservers.  As a motivation,
just consider someone spins up their botnet to add 1000 or more keys per
second to the pool - aaaaand it's gone. Other aspects are that a
keyserver lookup requires network connectivity, introduces noticable
delay, and has privacy implications which prevent us from doing the
lookup in an automated fashion.

First, some basic considerations:  To obtain the public key of a
communication partner, we obviously have to rely on said communication
partner to make their key available to us one way or another.  The only
deployed lookup mechanism are keyservers, but we said we don't have
that.  The alternative is sending the key in-band with the particular
communication protocol: No problem for synchronous communication such as
XMPP because we can simply request them, more difficult for e-mail where
that option is not available.

If we don't have bandwidth constraints, we can solve this by sticking
the public key block right next to every signature we make, which
effectively eliminates the need for keyservers (with the possible
exception of the distribution of revocation certs).  However, it also
adds ~10kb of size to every signature.  This is a rather extreme
approach, and although 10kb are not a lot these days, they add up.

To counteract this, we can significantly reduce the number of attached
public keys if we are just a little bit clever about the decision of
when to add it.  Roughly, it makes sense to attach the public key to the
first message of a conversation with each recipient.

Another question is, where to place the key. In email, we have two
options: in a separate mime part, or directly next to the pgp signature
data. I favor the second option, for two reasons:
- the email client has to know a lot less about openpgp for this to
  work, the public key is naturally handed to the openpgp-implementation
  together with the signature data.
- there isn't yet another weird attachment for recipients who don't have
  openpgp support
- the intended purpose of the key is clear, because there are no other
  circumstances where a key might end up in this position.

The drawback with this approach is implementation support.  If an
implementation doesn't expect a public key next to the signature data,
it's just bloat (or even worse, produces a warning about trailing data.
I did some tests and this is the case in mutt, but not enigmail), and
does not even show an option for the user to manually import the key.

I think that this approach might be a way to overcome the need for a
click from the user (whether it's "Retrieve from Keyserver" or "Import
from Attachment") to be able to import and work with a public key. It's
unacceptable to import a key from keyservers automatically for various
reasons, but I think an opt-out behavior of importing keys retrieved as
part of a message is fine, if that key also signed the message.

I'll leave it at this for now.  I'd be delighted about comments and
thoughts, in particular from those of you who are involved in the
decision making of other implementations.

 - V

---

From: Paul Wouters <[email-masked]>
Date: Tue, 12 Apr 2016 10:15:36 -0300

Have you looked at the openpgpkey DNS record which is going to be an RFC very soon?

https://tools.ietf.org/html/draft-ietf-dane-openpgpkey-07

Paul

Sent from my iPhone

> On Apr 12, 2016, at 09:15, Vincent Breitmoser <[email-masked]> wrote:
> 
> Hi,
> 
> _______________________________________________
> openpgp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/openpgp

---

From: Vincent Breitmoser <[email-masked]>
Date: Tue, 12 Apr 2016 15:40:22 +0200

I have, and it indeed solves the ddos-problem of keyservers. It still
requires connectivity, introduces an arbitrary lookup delay, leaks
metadata, and most importantly - it's not deployed. I would love to see
it in action at scale, but even on my most hopeful of days I reckon it
will be years until it's commonly supported by mail providers.

 - V

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 12 Apr 2016 15:49:18 +0200

> Using OpenPGP in E-Mail without relying on keyservers. 

Important use-case.

> approach, and although 10kb are not a lot these days, they add up.

Not necessarily -- I don't think you have to add all signatures to the
key for this use-case to work, do you?  If you just include a stripped
public key, verification of the signature will work.  It should be max
1-2kb I would guess.

> when to add it.  Roughly, it makes sense to attach the public key to
> the first message of a conversation with each recipient.

It sounds good in theory, but I don't think that will work.  Let's
compare how I use e-mail clients.  I use k9, claws, evolution, webmail,
and probably several other clients that I forgot.  I don't read all
emails in all clients, of course.  I only read the emails that I need
in the client I happen to have available.  So if you only include the
public key in the first message of a conversation, the majority of my
clients would never see that email because of my usage pattern.  None
of any newly installed MUA would ever see the email, which over time
tends to approach 100% of my MUAs since I re-install most of them from
time to time.

Now it may be that my usage pattern is a corner case, but I believe it
is typical for many users today.

> options: in a separate mime part, or directly next to the pgp
> signature data.

You could put it in the email header too.  It would be bizare for
larger keys, but at least possible in theory.

Also, the OpenPGP mail/news url field header was intended to provide an
indirect way to support this:

http://josefsson.org/openpgp-header/

You still have some of the keyserver privacy concerns, and require
a network connection, but I'd just like to mention it as another option
to consider.

> I favor the second option, for two reasons:

I agree it could work.  Write an I-D describing the approach and try to
get MUA client support for it.

/Simon

---

From: "Neal H. Walfield" <[email-masked]>
Date: Tue, 12 Apr 2016 15:58:27 +0200

On Tue, 12 Apr 2016 15:49:18 +0200,
> public key, verification of the signature will work.  It should be max

I think 10kb is accurate.  If you have a primary and three subkeys and
all four have a self-signature, then you are about 10k:

  $ gpg2 -k 0xAACB3243630052D9
  pub   rsa3744/0xAACB3243630052D9 2015-04-07 [SC] [expires: 2025-04-04]
        Key fingerprint = 8F17 7771 18A3 3DDA 9BA4  8E62 AACB 3243 6300 52D9
  uid                   [ultimate] Neal H. Walfield <[email-masked]>
  uid                   [ultimate] Neal H. Walfield <[email-masked]>
  uid                   [ultimate] Neal H. Walfield <[email-masked]>
  sub   rsa2048/0x7223B56678E02528 2015-04-07 [S] [expires: 2017-04-06]
  sub   rsa2048/0xC2B819056C652598 2015-04-07 [E] [expires: 2017-04-06]
  sub   rsa2048/0xA3506AFB820ABD08 2015-04-07 [A] [expires: 2017-04-06]
  $ gpg2 --export-options=export-minimal --export 0xAACB3243630052D9 | wc -c
  9622

Of course, we can leave off the authorization key in this case.  But,
we need the primary key to verify the self-signatures, we need to the
signing key to verify signatures and we need the encryption key to
encrypt.  So, this is pretty minimal.

:) Neal

---

From: Vincent Breitmoser <[email-masked]>
Date: Tue, 12 Apr 2016 16:30:09 +0200

> is typical for many users today.

Good point. I'll think about this some more.  Two related ideas from the
top of my head:
- keyring synchronization. this is necessary to send an encrypted
  message to a known contact from a new device, so it's going to be a
  thing we will have to worry about somewhere down the line for proper
  support of the multi-device scenario.
- store message-id of the message where the pubkey was last sent on the
  sender side, and add it to the mime header of the signature? for
  reasonably recent messages, clients should be able to make that lookup
  without network in many cases, and it avoids the privacy leak.

> larger keys, but at least possible in theory.

Yeah, 10kb header lines don't seem very practical. I also considered the
mime header, but same argument, it's just too unwieldy. :\

> a network connection, but I'd just like to mention it as another option

Indeed: Connectivity, delay, privacy. :)

> get MUA client support for it.

Depending on the resonance I get or further arguments brought up here,
I'm going to implement this in at least K-9 Mail myself. :)

Thanks for the feedback so far!

 - V

---

From: Ruben Pollan <[email-masked]>
Date: Tue, 12 Apr 2016 16:34:30 +0200

Quoting Simon Josefsson (2016-04-12 15:49:18)
> is typical for many users today.

In the multi-device world you are describing I think is pretty important to 
share your keyring among your devices, not just your private keys, but all your 
known public keys and your trust on them.

> a network connection, but I'd just like to mention it as another option

In bitmask we do some of the things you propose Vincent. We attach public keys 
to all sent emails until we get an email encrypted to this public key. We attach 
the key as a mime part, because enigmail already have support for that and is 
one click to import it in your keyring.

We also add the OpenPGP header to all the sent emails and use it to discover 
keys from the 'url' field if it's https and from the same domain than the email 
address.

Even dough I have many concerns about key discovery on the key servers, I think 
we need key servers for key updates. We need to be able to revoke, extend 
expiration, rotate subkeys, ... I think is really important for OpenPGP email 
clients to be able to update periodically the keyring in a 'privacy preserving 
way'. We even dream to have some crappy forward secrecy by rotating encryption 
subkeys often, and deleting them from the keyring.

-- 
Ruben Pollan  | http://meskio.net/
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
 My contact info: http://meskio.net/crypto.txt
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Nos vamos a Croatan.

---

From: Derek Atkins <[email-masked]>
Date: Tue, 12 Apr 2016 10:45:47 -0400

Hi,

> that option is not available.

This is only an issue on the first communication with someone.  Once you
have your comminicant's key you can cache it locally and re-use it for
all future transmissions without touching the keyserver.

So really it's a question of bootstrapping: When you are sending an
email to a person for the first time (or if you are verifying a
signature for the first time), how do you get their key?

This is, in my experience, a much more limited use-case.  I find that I
rarely send an email to someone for the first time, and rarely do I
receive cold-call emails where I care about validating the signature.
I'm usually sending (and receiving) emails to (from) the same people
over and over.  So once I acquire their key, it's cached and I don't
need to ask for it again.

Okay, so now that we're reduced the issue to first-use, how does one
acquire that data?  There are several options:

1) email unencrypted and ask for it
2) use a PGP keyserver
3) use some other lookup database (LDAP, DNS, etc)

Pretty much every single one of these options implies some amount of
delay and has different trust (and deployment) models.

-derek
-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: "Neal H. Walfield" <[email-masked]>
Date: Tue, 12 Apr 2016 16:53:23 +0200

On Tue, 12 Apr 2016 16:34:30 +0200,
Ruben Pollan wrote:
> We even dream to have some crappy forward secrecy by rotating encryption 

Take a look at puncture encryption:

  https://isi.jhu.edu/~mgreen/forward_sec.pdf

Matt wants to see this get integrated into OpenPGP at some point, but
there are some issues.  For instance, using puncture encryption, the
private key can get larger than 64k, which is the current limit for
OpenPGP private keys.

:) Neal

---

From: Werner Koch <[email-masked]>
Date: Tue, 12 Apr 2016 18:20:45 +0200

> metadata, and most importantly - it's not deployed. I would love to see

Running DNS over Tor heavily mitigates the leak of meta data.  If you
run a decent gpg version on Windows and Tor is running, gpg will do just
that w/o the need for further configuration.  On Unix it is currently
only possible with a patched ADNS version (because upstream is pretty
slow to accept a patch to torify ADNS).

There are privacy aware mail providers who offer OpenPGP DANE.  For
example try my callsign @ posteo.net [1].  We are currently talking to
other mail providers to get them to deploy this or a similar https based
key location mechanism.

Salam-Shalom,

   Werner

[1] For example by putting this into gpg.conf:
      auto-key-locate local,dane,pka,keyserver

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

---

From: Werner Koch <[email-masked]>
Date: Tue, 12 Apr 2016 19:11:26 +0200

> private key can get larger than 64k, which is the current limit for

Fur only for the computation of the fingerprint.  We should address that
for the v5 fingerprint.

Salam-Shalom,

   Werner

---

From: Vincent Breitmoser <[email-masked]>
Date: Wed, 13 Apr 2016 19:19:22 +0200

> one click to import it in your keyring.

That's nice for interoperability but is also, imo, simply one click too
much.

> keys from the 'url' field if it's https and from the same domain than the email 

I don't think the URI field can gain any reach as long as it has to rely
on users manually uploading the key somewhere. If an email provider did
provided this service and added the header, that might work... but then
the DANE approach probably works better for that scenario.

> We need to be able to revoke, extend expiration, rotate subkeys, ...

Timed updates from keyservers aren't as affected by the the
connectivity, delay, and privacy problem as on-the-fly lookup while
reading mail.

 - V

---

From: Ruben Pollan <[email-masked]>
Date: Wed, 13 Apr 2016 23:54:07 +0200

Quoting Vincent Breitmoser (2016-04-13 19:19:22)
> That's nice for interoperability but is also, imo, simply one click too

Yes, that is why we automate the key fetch from this attachments and there is no 
user action involved.

> > keys from the 'url' field if it's https and from the same domain than the 
> > email address.
> 

If I understood correctly DANE your are making public the list of all the email 
addresses (with OpenPGP keys) in your provider. I'm not sure how much I like 
that. But it's probably not worst that uploading the keys to the key servers 
anyway.

We do upload the keys to the provider automatically and publish them in a 
normalized url.

> connectivity, delay, and privacy problem as on-the-fly lookup while

Agree :)