Subject: [ietf-dkim] New Issue: 512 too short?

From: Stephen Farrell <[email-masked]>
Date: Thu, 16 Mar 2006 09:53:52 +0000

Section 3.3.3 includes 512 bit rsa as a MUST. I think that that
might be an error. Is there really any need for anything smaller
than 1024 in any case?

S.

_______________________________________________
NOTE WELL: This list operates according to 
http://mipassoc.org/dkim/ietf-list-rules.html

---

From: Michael Thomas <[email-masked]>
Date: Thu, 16 Mar 2006 07:07:09 -0800

> might be an error. Is there really any need for anything smaller

Isn't there something of a calculation which equates effort to
break over time? DKIM lifetimes are normally quite short, so
smaller keys are not implausible, especially given the level
of protection DKIM actually provide (weakest link: DNS).

Anecdotally, I have noticed there is a perceivable performance
difference between 512 and 1024. IIRC, 768 seems still imperceptible.

		Mike

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 16 Mar 2006 15:16:29 +0000

> of protection DKIM actually provide (weakest link: DNS).

That's a defensible argument. Just to be clear though - there
are two lifetimes in DKIM - signature lifetime, related to
message transit times, and key lifetime, related to some unknown
management cycle, and its the latter (and presumably longer) one
that's in question here. From painful experience, changing keys
is something that some enterprises are really, really bad at.

If we were to continue to allow (let alone MUST) 512, then I
think there'd need to be a serious warning to change those
keys pretty often. I'd rather we did without that if its
possible.

> difference between 512 and 1024. IIRC, 768 seems still imperceptible.

Fair enough. Though h/w acceleration is widely, cheaply available
as used for https, and there's no real difference here (modulo
sha256 support I guess).

Stephen.

---

From: Michael Thomas <[email-masked]>
Date: Thu, 16 Mar 2006 07:22:04 -0800

> is something that some enterprises are really, really bad at.

Ah, yes, and I agree that key rollover is probably the
larger problem. Is 768 an implausable lower bound? We
could even perhaps go so far as to say SHOULD sign/1024
(where the wiggle room is if you have a good rollover
story, and the performance difference is worthwhile).

		Mike

---

From: Mark Delany <[email-masked]>
Date: Thu, 16 Mar 2006 15:31:33 +0000

> might be an error. Is there really any need for anything smaller

It might not be significant, but I presume there are deployed 512
DomainKey Selectors, excluding 512 from DKIM would break those
deployments.

We *could* deprecated that size by saying verifiers MUST and signers
MAY if the consensus is that 512 should not be used henceforth.

Mark.

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 16 Mar 2006 15:42:12 +0000

> story, and the performance difference is worthwhile).

That may be ok. But I'm guessing that a "MUST support 768"
(even with caveats) will raise some eyebrows and we'll have
to go over it all a number of times. So I'm not sure if the
CPU cycle improvement is worthwhile here or not.

My gut inclination would be MUST 1024 & 2048 and deprecate
all shorter keys to the extent that the deployed base permits.

If there are deployed 512 domains, one thing that could be done
would be to have a "MUST NOT use 512 after <<date>>" to try
get people to change their shorter keys. Or Mark's suggestion
may be better. Do we have any data on deployed key sizes?

S.

---

From: Michael Thomas <[email-masked]>
Date: Thu, 16 Mar 2006 07:54:04 -0800

> MAY if the consensus is that 512 should not be used henceforth.

We'd probably have less of a fight if we mandated stronger on
signers, and require/allow receivers to verify with weaker. It's
not entirely clear to me that a receiver would be doing justice
to a weak, but valid signature by ignoring it. At some level, it's
the sending domain's problem -- does the threat really outweigh
the benefit? It sure seems like a pretty theoretical attack to
me.

		Mike

---

From: Mark Delany <[email-masked]>
Date: Thu, 16 Mar 2006 16:20:12 +0000

> may be better. Do we have any data on deployed key sizes?

Unfortunately we don't and getting it is non-trivial as it involves
deploying s/w. Maybe someone else does. I expect 512 to be rare, but
768 might be common.

I will note that it actually takes work to check the key size, so it's
an artificial constraint that may or may not be implemented very
well. (As an implementor I hold the belief that all artificial
constraints eventually bit-rot to zero).

Further, that sort of constraint is algorithm dependent. So the true
test is: if (rsa && keySize < limit)). A new algorithm may well have
completely different size limits or different safety dimensions to
check.

Is there experience in similar fields to the success or otherwise of
imposing minimum safety limits? S/MIME, PGP, SSL?

Mark.

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 16 Mar 2006 08:39:15 -0800

> imposing minimum safety limits? S/MIME, PGP, SSL?

SSL doesn't impose minimum limits, but 1024 is pretty much the 
industry standard AFAIK.

-Ekr

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 16 Mar 2006 10:54:42 -0800

At 7:07 AM -0800 3/16/06, Michael Thomas wrote:
>break over time?

BCP 86 / RFC 3766

>DKIM lifetimes are normally quite short, so

Yes.

At 3:16 PM +0000 3/16/06, Stephen Farrell wrote:
>Just to be clear though - there
>that's in question here.

Correct. On the other hand, there is lots of text in the spec 
indicating that changing keys is likely to happen often for many 
different reasons.

>keys pretty often.

Only if those keys were considered to be valuable by an attacker so 
that it is worth spending thousands of MIPS-years to factor the 
public key.
_______________________________________________
NOTE WELL: This list operates according to 
http://mipassoc.org/dkim/ietf-list-rules.html

---

From: Michael Thomas <[email-masked]>
Date: Thu, 16 Mar 2006 11:11:31 -0800

Paul Hoffman wrote:
> Correct. On the other hand, there is lots of text in the spec indicating 
> that changing keys is likely to happen often for many different reasons.

I'm afraid that Stephen's observation is more likely to be
closer to reality, even if the spec is more optimistic about
it.

> Only if those keys were considered to be valuable by an attacker so that 
> it is worth spending thousands of MIPS-years to factor the public key.

Which leads us back to the original question, I guess. I'm fairly
certain that nobody's going to spend any MIPS-years to factor
mtcc.com's public key. They might consider it for something more
tempting like, oh say, Bigbank.com. Or they might try pharming
instead which is probably an easier tactic.

Ultimately this is far more likely to be a question of what passes
IESG muster though. I don't sense that there's much consensus that
it would be a good fight to pick with them.

How about:

Signers SHOULD NOT use keys less that 1024 bits, receivers MUST
accept keys less that 1024 but MAY consider weaker keys as more
suspicious.

(where "suspicious" has been used before in the draft to mean something 
along the lines of heightened scrutiny, etc).

		Mike

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 16 Mar 2006 11:25:05 -0800

At 11:11 AM -0800 3/16/06, Michael Thomas wrote:
>mtcc.com's public key.

... thousands of MIPS-years for a 512-bit key ...

>They might consider it for something more

Right. Larger targets have both much more access to CPU power (and 
therefore should use larger keys) but are also easier targets for 
social attacks.

>accept keys less that 1024 but MAY consider weaker keys as more

We have a huge problem with SHOULDs and MUSTs in this document: some 
of them are for good security practices, others are for 
interoperability. I'll bring more of these up later, but we might as 
well start getting them right now where we can.

Alternate proposal: Because shorter keys may be able to be 
compromised with off-line computational attacks, signers SHOULD NOT 
use long-lived keys whose length is less that 1024 bits. Receivers 
MUST be able to validate signatures with shorter keys, but may have 
security policies that are linked to the length of the signing key.
_______________________________________________
NOTE WELL: This list operates according to 
http://mipassoc.org/dkim/ietf-list-rules.html

---

From: Douglas Otis <[email-masked]>
Date: Thu, 16 Mar 2006 11:37:12 -0800

> ... thousands of MIPS-years for a 512-bit key ...

http://www.wisdom.weizmann.ac.il/~tromer/papers/twirl.pdf

When the time and resources are minimal, such as 10 minutes and $10K,  
any message signed using a 512 bit keys MUST NOT be considered signed.

This was referenced in the draft:
http://www.sonic.net/~dougotis/id/draft-otis-mass-reputation-03.html

-Doug

---

From: Arvel Hathcock <[email-masked]>
Date: Thu, 16 Mar 2006 13:54:46 -0600

> Do we have any data on deployed key sizes?

FYI, none of our deployments are using less than 1024.  Our software 
generates default keys for the user automatically at 1024.

-- 
Arvel

---

From: Russ Housley <[email-masked]>
Date: Fri, 17 Mar 2006 11:48:07 -0500

Security AD Advice

512-bit RSA keys are too short.  They may be acceptable when the 
crypto period is very short (say a week).  I cannot envision most 
administrators accepting the management burden associated with such 
short crypto periods.

Proposed text:
Since short RSA keys are susceptible off-line attacks, signers MUST 
use RSA keys of at least 1024 bits for long-lived keys. Receivers 
MUST be able to validate signatures with keys ranging from 512 bits 
to 2048 bits, and they MAY be able to validate signatures with larger 
keys.  Security policies may use the length of the signing key as one 
metric for determining whether a signature is acceptable.

Russ

---

From: Arvel Hathcock <[email-masked]>
Date: Fri, 17 Mar 2006 12:49:16 -0600

> Since short RSA keys are susceptible off-line attacks, signers MUST

That text sounds good to me but maybe "Since short RSA keys more easily 
succumb to off-line attacks, ..." is more precise?

-- 
Arvel

---

From: Douglas Otis <[email-masked]>
Date: Fri, 17 Mar 2006 16:20:56 -0800

On Mar 17, 2006, at 8:48 AM, Russ Housley wrote:

> Since short RSA keys are susceptible [to] off-line attacks, signers  
> MUST use RSA keys of at least 1024 bits for long-lived keys.  
> Receivers MUST be able to validate signatures with keys ranging  
> from 512 bits to 2048 bits, and they MAY be able to validate  
> signatures with larger keys.  Security policies may use the length  
> of the signing key as one metric for determining whether a  
> signature is acceptable.

With respect to 2048 bit keys, there is already a placeholder in the  
base draft for developing a much needed binary DKIM key.  There was a  
concern raised about utilizing the RFC2538 CERT #37 RR for this  
purpose.  I have assurances Paul Vixie will assist an effort by the  
DKIM WG to utilize the CERT RR for the binary version of the DKIM key.

-Doug

---

From: Russ Housley <[email-masked]>
Date: Sat, 18 Mar 2006 10:39:50 -0500

That is a fine improvement.

Russ

At 01:49 PM 3/17/2006, Arvel Hathcock wrote:
>That text sounds good to me but maybe "Since short RSA keys more 
>easily succumb to off-line attacks, ..." is more precise?
>
>--
>Arvel
>
>

---

From: Paul Hoffman <[email-masked]>
Date: Sat, 18 Mar 2006 21:29:58 -0600

At 4:20 PM -0800 3/17/06, Douglas Otis wrote:
>base draft for developing a much needed binary DKIM key.

Why is a binary representation "much needed"? A 2048-bit key will 
only take up 320 of the 512 bytes allowed. Or am I missing something?
_______________________________________________
NOTE WELL: This list operates according to 
http://mipassoc.org/dkim/ietf-list-rules.html

---

From: Mark Delany <[email-masked]>
Date: Sun, 19 Mar 2006 05:16:53 +0000

> only take up 320 of the 512 bytes allowed. Or am I missing something?

Actually, the encoding cost is only a constraint if you want to store
the key in some human renderable form. AFAIK, nothing stops a TXT from
containing the full 256 range of byte values. Though that suggestion
will surely cause more affront to those who abhor the use of TXT in
the first instant.

Mark.

---

From: Douglas Otis <[email-masked]>
Date: Sun, 19 Mar 2006 08:27:27 -0800

> only take up 320 of the 512 bytes allowed. Or am I missing something?

The DNS Message is constrained to 512 bytes. 12 bytes are part of the
DNS message header, the query has 5 bytes plus the name size plus one
byte per label overhead, the answer has 9 bytes + 1 byte per label
followed by the RR data.  Not including the name space, there are only
486 bytes available for data.

As defined using base64 (6 bits per byte) and ASCII parsing syntax,
using TXT character-strings to store this 2048 bit key consumes 345
bytes (plus two bytes for defining the two character-string lengths) and
leaves 139 remaining bytes.

Of those bytes, 8 bytes are used to the version of the TXT record,
leaving 131 bytes.  The "_domainkeys" label consumes another 14 bytes
(assuming pointer compression in the answer section) and that leaves 117
bytes for name space.  From this space, one or more selector labels with
together with the labels for the parent domain must be accommodated
which consumes an additional one byte per label plus the label sizes.

This might seem okay until subtracting from this remainder the overhead
of comparatively wasteful text methods for expressing allowed hash
values and other parameters, and then there is then a much higher
probability this will exceed the DNS UDP message constraint.

The RFC2538 Cert RR can store binary keys needed for DKIM.  The 5 byte
CERT header overhead specifying the type of key, key-tag, and algorithm
is already less than the Version tag used for the TXT record.  The CERT
header clearly assures the algorithm has been defined without resorting
to default or mandated parameters, which may cause a potential security
problem for future upgrades or introduce problematic size constraint
issues confounding an upgrade.

Using binary to store the key should only require 258 bytes which saves
87 bytes from that used by the TXT RR approach.  This savings, together
with binary algorithm definitions, ensures future algorithm upgrades or
features or even utilizing some of the current features are not be in
jeopardy.

-Doug

---

From: Paul Hoffman <[email-masked]>
Date: Sun, 19 Mar 2006 11:37:18 -0600

>which consumes an additional one byte per label plus the label sizes.

That sounds correct. And thanks for correcting my miscalcuation of 
base64ing the key.

>probability this will exceed the DNS UDP message constraint.

...and here is where I get confused. I don't see anything in the base 
spec that uses any other hashed values, and the other parameters take 
up small tens of bytes.

I'm not saying that a binary representation is not good, just 
questioning the "need" for it. It doesn't seem needed by the current 
spec, and the current implementations seem just fine (although that 
is probably due to using 1024-bit keys, freeing up 170 bytes).
_______________________________________________
NOTE WELL: This list operates according to 
http://mipassoc.org/dkim/ietf-list-rules.html

---

From: Douglas Otis <[email-masked]>
Date: Sun, 19 Mar 2006 10:48:36 -0800

> is probably due to using 1024-bit keys, freeing up 170 bytes).

About 1 byte per label overhead in the question and answer, with pointer
compression, this could be viewed as 3 bytes per label.  The remaining
117 bytes is quickly consumed with the ASCII options being expressed.
As these become needed in the future, increasing the size of these
parameters will likely also occur and perhaps become problematic.

For example just the g= parameter might contain a 64 byte local-part
with three bytes of syntax.  The remaining space is now only 50 bytes.
With 5 labels, a selector and a four label domain, this now leaves 35
bytes.  The other parameters must still be defined.  When a dozen bytes
are used for expressing the permitted hash algorithms, and another half
dozen to express the type of key, the average label size is going to
become rather small when taken from the remaining dozen bytes.  Of
course there is also a list of applications that might be needed for the
s= parameter as well. : (

-Doug

---

From: Ólafur Guðmundsson <[email-masked]>
Date: Mon, 20 Mar 2006 15:18:48 -0500

Defining a new DKIM specific RR type for DNS will take about the same time
as defining a new CERT type! Furthermore adding a unsigned keying information
into the CERT record will run into resistance as this is not a
properly formatted certificate.

As for the 512 size restriction that was addressed by EDNS0 (RFC2671)
RFC2671 was issued in 1999. Most DNS software in serious use should
support it by now.
DKIM DNS usage requires DNSSEC in which case not having EDNS0
support is fatal.

I would say that the issue is twofold:
Mail servers that intent to do DKIM verifications, MUST have
local DNS stub resolver that support ENDS0 and MUST talk to recursive
nameservers that support EDNS0. (may want to add text that defines
lower limit of buffer size (see RFC3226)).

Sites that sign outgoing messages with DKIM MUST use authorative
nameservers that support ENDS0.

         Olafur
PS: Is the DKK record specification available anywhere ?

---

From: Douglas Otis <[email-masked]>
Date: Mon, 20 Mar 2006 15:04:39 -0600

On Mar 20, 2006, at 2:18 PM, Ólafur Guðmundsson wrote:

> Defining a new DKIM specific RR type for DNS will take about the  
> same time as defining a new CERT type!

Writing the draft, yes.  Accessing this RR type, no.  The CERT has  
made headway since about 1999, where use of this CERT by DKIM  
improves this momentum.

> Furthermore adding a unsigned keying information into the CERT  
> record will run into resistance as this is not a properly formatted  
> certificate.

When viewed in conjunction with the DKIM signature, this does offer  
similar functionality.  As this would be assigned its own CERT type,  
there is no risk of this creating a conflict as it also would only  
exist within a unique name space.  Paul Vixie reviewed this issue and  
considers the selection of the CERT RR a good choice.  What concerns  
do you have?

> As for the 512 size restriction that was addressed by EDNS0  
> (RFC2671) RFC2671 was issued in 1999.

Even when the DNS does support EDNS0, there can still be issues  
elsewhere.

> Most DNS software in serious use should support it by now.

A worthy goal.  Remember the network amplification is also affected,  
so the transition should be done with careful deployment.

> DKIM DNS usage requires DNSSEC in which case not having EDNS0  

Another worthy goal and of course EDNS0 is required by DNSsec.  Does  
that mean DKIM should also demand support for ENDS0?

-Doug

---

From: Jim Fenton <[email-masked]>
Date: Tue, 28 Mar 2006 08:47:07 -0800

Michael Thomas wrote:
> (where "suspicious" has been used before in the draft to mean
> something along the lines of heightened scrutiny, etc).
"Suspicious" is currently only used in the SSP draft; its meaning in
this context would need to be introduced here if it is to be used.

-Jim

---

From: Michael Thomas <[email-masked]>
Date: Tue, 28 Mar 2006 09:03:47 -0800

> this context would need to be introduced here if it is to be used.

FWIW, I'm fine with Russ/Arvel's text.

		Mike