Subject: [dispatch] Updating DKIM for stronger crypto

From: "John Levine" <[email-masked]>
Date: 6 Feb 2017 02:08:26 -0000

The DKIM spec RFC 6376 specifies the hash algorithm to use to make
hashes of e-mail message bodies and headers, and the signing algorithm
to use to sign them, with the results placed in a header in the
message.  To check signatures, the recipient looks up the verification
keys in the DNS, where it's stored in TXT records.

Every signature includes a tag saying what hash and signature
algorithms it used, and every key record includes a tag saying what
signature algorithm the key is for.  The plan was always that we'd be
able to move to newer algorithms when needed.  Early versions of DKIM
used SHA1 hashes, but by the time the original spec was published in
2007, we'd added SHA256 and the spec says that everyone should use
SHA256 hashes but also has to verify SHA1 hashes.  In practice everyone
uses SHA256.  

The only signature algorithm is RSA, and the spec says that verifiers
must handle signatures from 512 to 2K bits and strongly suggests at
least 1K bits.  So far, that has not changed.

Needless to say, 512 bits is now way too weak, and 1K is iffy, so it
would be a good idea to update the advice.  Over in DMARC land, there
is an anti-DMARC design called ARC which uses DKIM's signing
algorithms, and it would be nice to launch ARC with up to date crypto
too.

The obvious change would be a one sentence update to the DMARC spec
saying to sign with at least 2K keys and verifiers must handle at
least 4K keys.  The code changes to DKIM signers and verifiers would
be trivial, and it is my impression that most verifiers handle larger
keys now, since they just pass them to OpenSSL or the like.

Unfortunately, we have a stupid but significant problem.  DKIM keys
are published in DNS TXT records, the strings in TXT records are
limited to 256 characters, and keys longer than 1K bits don't fit
in 256 characters.  No problem you might think, since the DKIM spec
says that verifiers catenate multiple strings together, so you just
break the key into two or three strings.

A lot of people manage their DNS using web based crudware at their
registrar or DNS provider, and most of the crudware only handles TXT
records with one string.  You don't have to tell me how broken that
is, but the cruddy state of DNS provisioning has been a problem for
many years, and nothing we say is going to fix it in any finite amount
of time.

I note RFCs 7748 and 8032 which remind us that ed25519 has excellent
performance with much smaller keys.  So I would like to publish a
small update to the DKIM spec to add ed25519 as a signature algorithm,
require that ed25519 signatures use at least 256 bits, and provide
some advice for migration, e.g., publish both keys in separate TXT
records and sign with both algorithms for a while.  256-bit keys fit
in a single TXT string with ease.

Does this seem reasonable?

R's,
John

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 6 Feb 2017 02:15:16 +0000

> Does this seem reasonable?

Eminently, assuming implementers want ed25519 and those
deploying will adopt it. There are, IMO, good reasons for
both to also like that idea, but whether or not they
realise that is to be seen I guess.

S.

---

From: "John R Levine" <[email-masked]>
Date: 5 Feb 2017 21:33:17 -0500

> Eminently, assuming implementers want ed25519 and those deploying will 
> adopt it. There are, IMO, good reasons for both to also like that idea, 
> but whether or not they realise that is to be seen I guess.

It is my impression that the majority of DKIM signing and verifying is 
done using a small number of libraries.  If we can get the big gorillas on 
board, and arrange to upgrade the C opendkim, perl Mail::DKIM, and python 
pydkim, routine upgrades will do most of the rest.

Regards,
John Levine, [email-masked], Taughannock Networks, Trumansburg NY
Please consider the environment before reading this e-mail. https://jl.ly

---

From: Cullen Jennings <[email-masked]>
Date: Mon, 6 Feb 2017 15:22:43 -0800

Hi John, 

Assuming that some groupr of people wnated to work on this, how would you suggest organizing the work in IETF? Is this just a draft that gets AD sponsored be a sec AD, or do we spin up a mini WG that does just one RFC, or is it an amount of work that it ends up with a WG that produces more than one RFC? I'm just trying to get a feel of how much work is involved here. 

Cullen

> On Feb 5, 2017, at 6:08 PM, John Levine <[email-masked]> wrote:
> 
> _______________________________________________
> dispatch mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/dispatch

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 6 Feb 2017 15:39:43 -0800

On Sun, Feb 5, 2017 at 6:08 PM, John Levine <[email-masked]> wrote:
> would be a good idea to update the advice.

Well, I certainly agree that at some point it would be good to get to larger
than 1024-bit RSA keys, we're fairly far from the point where it's cheap
to factor a 1024-bit RSA key (absent a quantum computer, in which case
we've got bigger problems), and given that the impact of a complete break
here is you get to forge mail, I'm not sure how urgent this is.

> Does this seem reasonable?

Well, sort of.

It seems like this message suggests that the decision to store the key in
the TXT record is perhaps not the optimal design. If you were storing a
digest (as DANE does) then you could use arbitrary sized RSA keys without
running into the 256-character limit. This would also have the advantage
that if you ever needed to move to some post-quantum algorithm with big
keys (e.g., digest signatures), you would be in a somewhat better position.

With that said, moving to elliptic curve is a good idea and Ed25519 seems
like a reasonable choice. Note that the requirement that "ed25519 signatures
use at least 256 bits" is incoherent. Ed25519 denotes a specific elliptic
curve
of size 255 bits.

-Ekr

---

From: "John R Levine" <[email-masked]>
Date: 6 Feb 2017 18:48:50 -0500

> to factor a 1024-bit RSA key ...

It's not urgent, but given the ARC work, it'd be nice to do this once 
rather than twice.

> keys (e.g., digest signatures), you would be in a somewhat better position.

Hmmn.  So we'd put a copy of the verification key into the signature, and 
the verifier would hash that and see if it matched the hash in the DNS?  I 
suppose that could work, but if we're going to open up the code, given 
that elliptic signers and verifiers are showing up in crypto libraries 
it's be a lot simpler change to DKIM.

Regards,

---

From: "John R Levine" <[email-masked]>
Date: 6 Feb 2017 18:50:23 -0500

> Assuming that some groupr of people wnated to work on this, how would 
> you suggest organizing the work in IETF? Is this just a draft that gets 
> AD sponsored be a sec AD, or do we spin up a mini WG that does just one 
> RFC, or is it an amount of work that it ends up with a WG that produces 
> more than one RFC? I'm just trying to get a feel of how much work is 
> involved here.

I should ask the authors of the current DKIM spec.  If we all agree what 
we need to do, it could be a straightforward AD sponsored draft.  If 
there's disagreement, e.g., about the migration strategy, it'd likely need 
a mini WG.

R's,
John

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 6 Feb 2017 16:05:34 -0800

On Mon, Feb 6, 2017 at 3:48 PM, John R Levine <[email-masked]> wrote:

> the verifier would hash that and see if it matched the hash in the DNS?

Yes.

>   I suppose that could work, but if we're going to open up the code, given
> that elliptic signers and verifiers are showing up in crypto libraries it's
> be a lot simpler change to DKIM.

I don't see why this would be the case. Think of signature verification as
a function

  F(K, M) -> {true, false}

Ordinarily K is the public key, and M is the message, but if you instead
store H(K_pub)
in the DNS, and send M = {K_pub, Message}, it's the same underlying
interface. And
as I indicated, this has other benefits, which include being able to handle
cryptographic
systems with much larger public keys if we ever need them.

-Ekr

---

From: "John R Levine" <[email-masked]>
Date: 6 Feb 2017 19:38:45 -0500

> a function ...

I meant a simpler change to the code.

R's,
John

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 6 Feb 2017 16:40:05 -0800

> I meant a simpler change to the code.

So did I and I don't think it's "a lot simpler"

-Ekr

---

From: Cullen Jennings <[email-masked]>
Date: Fri, 10 Feb 2017 13:50:48 -0700

The Chairs and ADs discussed this today and we plan to allocate some agenda time for it at IETF 98. At the meeting we can try and figure out best way to dispatch this. 

It seems like a mini WG or possibly AD sponsor by ART or SEC AD are within the range of possibilities we should consider for how to move the work forward.