[messaging] Advertising public key in email (was: TOFU to ease PGP key discovery)

[David Leon Gil]

On Wed, Feb 11, 2015 at 2:53 PM, Trevor Perrin <trevp at trevp.net> wrote:
> [Tom Ritter wrote]:
>>> I feel like there must be some way in the MIME world to
>>> stash a key somewhere that's hidden from clients but accessible to the
>>> machine.

Indeed there is: simply include a MIME part with type "application/pgp-keys".

> Stick the public key in a header?  If we're sending EC keys and not
> trying to convey PGP key blobs, this is nothing (32 bytes).

No need to transmit the public key for keys used for ECDSA signatures.
Just recover the key (set of equivalent keys) from the signature. Let
'm' be the message (hash) that's signed, and compute:

     x(r) = R
     P = (sR - mG)/r

A similar identity works for EC-Schnorr signatures on "raw" messages.[^RR]

    P = (sG - R)/m

So if you really want to save space, and you're willing to take
Gap-DH, you never need to transmit a public key at all...

> [Mike Hearn wrote]:
>>> But normally you want to authenticate after encryption, right? Otherwise
>>> there can be odd attacks based on bit-flipping that can result in a message
>>> that decrypts successfully but doesn't say what the sender thought they said.

For signed messages, one option is, e.g.:

    Sign(public_sender, AEAD(key=ECDH(ephem_private, public_recip),
n=ephem_pub, ad=public_sender, m=message))

so that you can verify that the sender is "trustworthy" before doing
anything with the message. (Using an AEAD scheme makes the signature
unstrippable, in a weak sense.)

(This, of course, is incompatible with indistinguishability if the
adversary knows the sender's public key. If the adversary doesn't, you
can just encrypt with a symmetric encryption scheme.[^RR])

> S/MIME and PGP commonly do authentication via signatures inside the
> encryption (I believe the formats are flexible, but this is the common
> approach).

S/MIME supports some authenticated encryption schemes. See RFC 5083
for the CMS definitions.

> PGP added the MDC, but it's still inside the encryption,
> and as Andy points out there's a lot of processing after decryption
> but before the MDC is checked (e.g. decompression).

I've always preferred doing things the other way around for RSA with
OpenPGP, at least: encrypt-and-sign. But this requires a rather nasty
looking GnuPG incantation.

> So you don't want to expose PGP or S/MIME decryption errors or
> decryption timings to untrusted parties.  (I don't know that anyone's
> worked out the details, but there was some work on PGP as a decryption
> oracle before MDC was added [1], and also using PGP's ad-hoc CFB
> integrity check as an oracle [2]).

Agreed on this. (Or: opportunistic TLS all over again.)

> [Dkg wrote]:
>>> OpenPGP signatures currently don't contain the full public key or
>>> even a full fingerprint.  What's present is the 64-bit "long keyid",
>>> which i don't think is sufficient
>
> Assuming the fetched public key has to verify the signature, the
> forger has to solve two problems (match the 64-bit key ID and do a
> "duplicate signature key selection").  I believe these are
> individually possible, at least for RSA.  Whether it's feasible to
> solve these simultaneously I don't know, someone would have to do the
> math.

Yes, it's possible to do a dual-share key-share attack at the same
time. (Trickier if you want a strong key at the end, of course.)

The main computational expense is computing discrete logarithms over
sufficiently large primes. (IIRC, an old paper of Dan Boneh shows how
to use LLL to very efficiently find smooth moduli in a range.)


[^rr]: The Schnorr public-key-recovery identity, as well as the idea
to encrypt under the public key, are attributed to Robert Ransom in
[elligator].

[elligator]: http://elligator.cr.yp.to/elligator-20130828.pdf