Subject: [DNSOP] key lengths for DNSSEC

From: Jim Reid <[email-masked]>
Date: Wed, 2 Apr 2014 15:19:20 +0100

There's been a lot of noise and very little signal in the recent discussion.

It would be helpful if there was real data on this topic. Is an RSA key of N bits too "weak" or too "strong"? I don't know. Is N bits "good enough"? Probably. Change the algorithm and/or value of N to taste.

My gut feel is large ZSKs are overkill because the signatures should be short-lived and the keys rotated frequently. Though the trade-offs here are unclear: is a 512-bit key that changes daily (say) better than a 2048-bit key that gets rotated once a week/month/whatever? Remember too we're not talking about keys to launch ICBMs or authenticate billion dollar transactions. I doubt it matters if a previous key can be cracked provided it gets retired before the bad guys can throw enough CPU-years to break it.

However I'm just going on my own gut feel and common sense which could be wrong. Large keys might well be advisable at the root and/or for TLD KSKs. But so far there does not appear to have been much science or engineering on just how large those keys should be or how frequently they change. So in the absence of other firm foundations the established wisdom becomes "do what gets done for the root".

If there is a threat or risk here, please present solid evidence. Or, better still, an actual example of how any DNSSEC key has been compromised and then used for a real-world (or proof of concept) spoofing attack. 

BTW, the apparent profanity on an earlier thread was annoying because it didn't spell "whisky" correctly. As every drinker of fine single malt knows. :-)

---

From: Ted Lemon <[email-masked]>
Date: Wed, 2 Apr 2014 10:26:47 -0400

> My gut feel is large ZSKs are overkill because the signatures should be short-lived and the keys rotated frequently. Though the trade-offs here are unclear: is a 512-bit key that changes daily (say…

The problem with the way you've phrased this question is that there does not seem to be agreement amongst the parties to this discussion whether old keys matter.   If you think they do, you need longer keys.   If you think they don't, you need shorter keys.   So rather than talking about key lengths first, it would be more productive to come to a consensus about which threat model we are trying to address.

---

From: Joe Abley <[email-masked]>
Date: Wed, 2 Apr 2014 10:49:30 -0400

> The problem with the way you've phrased this question is that there does not seem to be agreement amongst the parties to this discussion whether old keys matter.   If you think they do, you need lo…

I'm trying to understand the time-based attack, but I'm not seeing it.

The gist seems to be that if I can turn back the clock on a remote resolver, I can pollute its cache with old signatures (made with an old, presumably compromised key) and the results will appear to clients of the resolver to validate.

This sounds plausible, but without administrative compromise of the remote resolver (in which case you have much simpler options) this attack seems to involve:

1. subverting sufficient NTP responses over a long enough period to cause the remote resolver's clock to turn back in time (long period suggested due to many/most? implementations' refuse large steps in times, and hence many smaller steps might be required)

2. replacing every secure response that would normally arrive at the resolver with a new one that will validate properly at whatever the resolver's idea of the time and date is (or, if not every, sufficient that the client population don't see validation failures for non-target queries). This potentially involves having factored or otherwise recovered every ZSK and KSK that might be used to generate a signature in a response to the resolver, for the time period between now and then.

This seems like an intractably difficult thing to accomplish.

What am I missing?

Joe

---

From: 🔒 Roy Arends <[email-masked]>
Date: Wed, 2 Apr 2014 16:19:25 +0100

> BTW, the apparent profanity on an earlier thread was annoying because it didn't spell "whisky" correctly. As every drinker of fine single malt knows. :-)

:-)

Jim,

Just a thought that occured to me. Crypto-maffia folk are looking for a minimum (i.e. at least so many bits otherwise its insecure). DNS-maffia folk are looking for a maximum (i.e. at most soo many bits otherwise fragmentation/fallback to tcp). It seems that the cryptomaffia’s minimum might actually be larger than the DNS-maffia’s maximum.

As an example (dns-op perspective). 

Average case: 2 keys (KSK/ZSK) + 1 sig (by KSK) with 2048 bit keys is at least 768 bytes (and then some).
Roll case: 3 keys(2 KSK/1 ZSK) + 2 sig (by KSK) with 2048 bit keys is at least 1280 bytes (and then some).

Then there is this section in SAC63: "Interaction of Response Size and IPv6 Fragmentation” 

Which relates to response sizes larger than 1280 and IPv6 and blackhole effects.

https://www.icann.org/en/groups/ssac/documents/sac-063-en.pdf

Hope this helps

Roy

---

From: Phil Regnauld <[email-masked]>
Date: Wed, 2 Apr 2014 16:55:23 +0200

> 1. subverting sufficient NTP responses over a long enough period to cause the remote resolver's clock to turn back in time (long period suggested due to many/most? implementations' refuse large ste…

	Many systems will run ntpdate on startup.

> This seems like an intractably difficult thing to accomplish.

	It does seem far fetched.

> What am I missing?

	There may be good reasons to increase key length, this is not one I'm
	worried about (then again, no one worried about source port randomization
	before 2008 :)

	P.

---

From: Christopher Morrow <[email-masked]>
Date: Wed, 2 Apr 2014 11:31:53 -0400

> Roll case: 3 keys(2 KSK/1 ZSK) + 2 sig (by KSK) with 2048 bit keys is at least 1280 bytes (and then some).

Part of jim's query is of interest:
  "Where are the requirements?" (boiled down some to that I think)

There's also a point I asked about previously in jim's note:
  "Where's the POC at?"

I don't think anyone's going to change anything without your referred
to 2008-like incident... and without some requirements at least as a
swag, right?

I'd expect the key length discussion relates pretty closely to:
  "If I can factor the key in less time than you will rotate keys..."

So, how often to the keys rotate? at least every 30 days? So you have
to be able to be 'secure' longer than 30 days of compute resources
time, right?

> https://www.icann.org/en/groups/ssac/documents/sac-063-en.pdf

good times :(

---

From: Christopher Morrow <[email-masked]>
Date: Wed, 2 Apr 2014 11:32:33 -0400

> to 2008-like incident... and without some requirements at least as a

oops, apologies, phil's 2008 reference.

---

From: Ted Lemon <[email-masked]>
Date: Wed, 2 Apr 2014 11:33:20 -0400

> This seems like an intractably difficult thing to accomplish.

Bear in mind that all you _really_ have to do is get a bogus ZSK with the current time into the resolver, which you may be able to do with some clever NTP shenanigans over a relatively short timescale.   But yeah, this isn't likely to be useful except in cases where a device has been powered off, doesn't have an accurate battery-backed-up clock, and does DNSSEC, which is a weird set of circumstances.

---

From: Evan Hunt <[email-masked]>
Date: Wed, 2 Apr 2014 16:54:53 +0000

On Wed, Apr 02, 2014 at 11:33:20AM -0400, Ted Lemon wrote:
> Bear in mind that all you _really_ have to do is get a bogus ZSK with the
> current time into the resolver, which you may be able to do with some
> clever NTP shenanigans over a relatively short timescale.   But yeah,
> this isn't likely to be useful except in cases where a device has been
> powered off, doesn't have an accurate battery-backed-up clock, and does
> DNSSEC, which is a weird set of circumstances.

I predict that will be a less weird set of circumstances in a year or
so: dnsmasq now has DNSSEC validation in beta.

(Tony Finch has a nifty idea to replace ntpdate with a quorum of tlsdate
responses; it might still be subvertible but it would be a much harder
nut to crack. https://git.csx.cam.ac.uk/x/ucs/u/fanf2/temporum.git)

-- 
Evan Hunt -- [email-masked]
Internet Systems Consortium, Inc.

---

From: Nicholas Weaver <[email-masked]>
Date: Wed, 2 Apr 2014 16:25:10 -0400

> Just a thought that occured to me. Crypto-maffia folk are looking for a minimum (i.e. at least so many bits otherwise its insecure). DNS-maffia folk are looking for a maximum (i.e. at most soo many…

The problem from the dns-op maximalist viewpoint is there is basically two magic numbers: 512B and ~1400B.  As someone who's measured this, the 512B is not a problem, but the 1400B "here be fragments" is.  Yet at the same time, the current 1024B ZSK/2048B KSK configuration on TLDs does blow through it: I reported in the previous thread how org's DNSKEY record already blew past that limit.

And even in that case, resolvers can handle "fragments don't work", albeit with a latency penalty.  So its not a "DNSSEC fails" point but simply "performance degraded".

So the real question is "do the common answers fragment", the ones with short TTLs that are accessed a lot, have a fragment problem.  With 2048b keys, they don't: the one that gets you is NSEC3, and that only blows up in your face on 4096b keys.  (But boy does it, those 3 RRSIGs get big when you're using 4096b keys).

And please don't discount the psychology of the issue.  If DNSSEC wants to be taken seriously, it needs to show it.  Using short keys for root and the major TLDs, under the assumptions that it can't be cracked quickly (IMO, we have to assume 1024b can be.) and that old keys don't matter [1], is something that really does draw criticism.

[1] IMO they do until validators record and use a 'root key ratchet': never accept a key who's expiration is older than the inception date of the RRSIG on the youngest root ZSK seen, or have some other defense to roll-back-the-clock attacks.

--
Nicholas Weaver                  it is a tale, told by an idiot,
[email-masked]                full of sound and fury,
510-666-2903                                 .signifying nothing
PGP: http://www1.icsi.berkeley.edu/~nweaver/data/nweaver_pub.asc

---

From: Frederico A C Neves <[email-masked]>
Date: Wed, 2 Apr 2014 17:45:05 -0300

Nicholas,

On Wed, Apr 02, 2014 at 04:25:10PM -0400, Nicholas Weaver wrote:
... 
> And please don't discount the psychology of the issue.  If DNSSEC
> wants to be taken seriously, it needs to show it.  Using short keys
> for root and the major TLDs, under the assumptions that it can't be
> cracked quickly (IMO, we have to assume 1024b can be.) and that old
> keys don't matter [1], is something that really does draw criticism.
>
> [1] IMO they do until validators record and use a 'root key
> ratchet': never accept a key who's expiration is older than the
> inception date of the RRSIG on the youngest root ZSK seen, or have
> some other defense to roll-back-the-clock attacks.

What do you mean by "..key who's expiration is.."? A new propertie
recorded at this "ratchet", btw what is this?

Fred

---

From: Richard Lamb <[email-masked]>
Date: Wed, 2 Apr 2014 13:49:07 -0700

Speaking for myself:

First:  Thank you Jim and Joe for seeking to increase the signal-to-noise ratio on this thread and for explaining what the attack vector would be for lower IQ folk like myself.

Second: I have always taken my instructions from the community. So regardless of what I believe I will faithfully do my part (with your help) to make it happen.

Third: From my vantage point and as author of the code used for the KSK side of things, I do not see any immediate barriers  to increasing key lengths.  The members of the original root DNSSEC design team have enjoyed a very good working relationship and I expect that to continue.  However, like any other change at this level it must be one that is approached conservatively and thoroughly tested before deployed (software, increased RRSet sizes, IPv6 impact, new ZSK generation).  This will take human resources and time.

I look forward to following further discussions on this topic.

-Rick

-----Original Message-----
From: DNSOP [mailto:[email-masked]] On Behalf Of Joe Abley
Sent: Wednesday, April 02, 2014 7:50 AM
To: Ted Lemon
Cc: IETF DNSOP WG
Subject: Re: [DNSOP] key lengths for DNSSEC

What am I missing?

Joe
_______________________________________________
DNSOP mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/dnsop

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 2 Apr 2014 19:21:11 -0400

On Wed, Apr 2, 2014 at 11:19 AM, 🔒 Roy Arends <[email-masked]> wrote:

> > It would be helpful if there was real data on this topic. Is an RSA key
> of N bits too "weak" or too "strong"? I don't know. Is N bits "good
> enough"? Probably. Change the algorithm and/or value of N to taste.
> >
> > My gut feel is large ZSKs are overkill because the signatures should be
> short-lived and the keys rotated frequently. Though the trade-offs here are
> unclear: is a 512-bit key that changes daily (say) better than a 2048-bit
> key that gets rotated once a week/month/whatever? Remember too we're not
> talking about keys to launch ICBMs or authenticate billion dollar
> transactions. I doubt it matters if a previous key can be cracked provided
> it gets retired before the bad guys can throw enough CPU-years to break it.
> >
> > However I'm just going on my own gut feel and common sense which could
> be wrong. Large keys might well be advisable at the root and/or for TLD
> KSKs. But so far there does not appear to have been much science or
> engineering on just how large those keys should be or how frequently they
> change. So in the absence of other firm foundations the established wisdom
> becomes "do what gets done for the root".
> >
> > If there is a threat or risk here, please present solid evidence. Or,
> better still, an actual example of how any DNSSEC key has been compromised
> and then used for a real-world (or proof of concept) spoofing attack.
> >
> >
> > BTW, the apparent profanity on an earlier thread was annoying because it
> didn't spell "whisky" correctly. As every drinker of fine single malt
> knows. :-)
>
> :-)
>
> Jim,
>
> Just a thought that occured to me. Crypto-maffia folk are looking for a
> minimum (i.e. at least so many bits otherwise its insecure). DNS-maffia
> folk are looking for a maximum (i.e. at most soo many bits otherwise
> fragmentation/fallback to tcp). It seems that the cryptomaffia’s minimum
> might actually be larger than the DNS-maffia’s maximum.
>

There is no doubt that we can get close to the limit on response sizes.
Which is why I have been pushing the notion that if we are going to do DNSE
then part of the DNSE solution should be to get us out of the single
response packet straightjacket.

Its not just crypto that gets crippled by this issue.

We are not in 1995 any more. We have bigger computing resources and bigger
security challenges. The Internet isn't a science project any more.

Too much of the debate here has been for one security approach versus
another. That is obsolete thinking we have been moving to multiple layers
of cryptography for some time now.

-- 
Website: http://hallambaker.com/

---

From: Andrew Sullivan <[email-masked]>
Date: Wed, 2 Apr 2014 19:31:06 -0400

> response packet straightjacket.

I've seen what you've had to say on that, and what I just don't
understand yet is how that answer is deployable.  That is, how is what
you are suggesting there (and in your other discussions of this topic)
not "replace DNS"?  Or, if it is, why don't we just do a new protocol
completely?  We could fix the internationalization issues.  We could
ditch UDP and in a single blow eliminate a major source of DDoS on the
Internet.  And so on.

The only problem is getting everyone to upgrade.  No?

A

-- 
Andrew Sullivan
[email-masked]

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 2 Apr 2014 21:07:07 -0400

> The only problem is getting everyone to upgrade.  No?

There are three different parts of the protocol

1) Client -> Resolver
2) Resolver -> Authoritative
3) The DNS data model

Changing 1 is the easiest and also the part that is most in need. We need
to find a way round all the crud that is making port 53 pretty much
unusable. The privacy concerns are the most restrictive, etc.

Changing 2 is a little harder but changes to BIND etc will eventually
percolate through.

Changing 3 is a ten year program at least and is not feasible unless 1 and
2 are addressed first.

---

From: Andrew Sullivan <[email-masked]>
Date: Wed, 2 Apr 2014 22:48:29 -0400

> Changing 1 is the easiest and also the part that is most in need.

>From where I sit, that project appears to reduce to roughly "upgrade
all the computers on Earth."  It may be that we do not have a common
meaning of "easiest".  Perhaps you could say more.

Best regards,

A

-- 
Andrew Sullivan
[email-masked]

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 2 Apr 2014 23:24:38 -0400

> meaning of "easiest".  Perhaps you could say more.

Nope, just the gateway devices and the main DNS servers.

Legacy DNS over raw UDP will be around for decades to come. But DNS over a
privacy protected transport is quite viable.

The privacy issues are most acute at the network gateway device, the
firewall or the WiFi router.

Privacy protection plus anti-censorship protection is in big demand right
now.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 3 Apr 2014 07:35:52 -0400

> Privacy protection plus anti-censorship protection is in big demand right

Since we have essentially zero DNSSEC stub clients in operation and 100% of
those that are in use are being deployed by aggressive early adopters,
deployment in the stub client -> recursive loop is actually quite easy.

What we can't do is to break legacy DNS without DNSSEC. That is the
deployment scenario that is beyond redemption.

---

From: Tony Finch <[email-masked]>
Date: Fri, 4 Apr 2014 17:05:17 +0100

> I'm trying to understand the time-based attack, but I'm not seeing it.

I think a plausible form of this attack involves DNSSEC validation at
the edge.

(1) DoS your victim, to force them into trouble-shooting mode. Hopefully
they will reboot, at which point you can lie to them about the time, and
they will probably believe you.

(2) You have compromised a key that was valid at the point in time which
your victim now believes is current. The signature chain from the root to
your compromised key works. You have a sample of other records from the
same time so you can maybe make other stuff seem to work.

(3) Go wild signing attack records with your compromised key and sending
them in responses to your victim.

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
Trafalgar: Westerly or southwesterly 4 or 5, occasionally 6 in north. Rough
becoming moderate. Rain or showers, mainly in north. Good, occasionally poor
in north.

---

From: Tony Finch <[email-masked]>
Date: Fri, 4 Apr 2014 17:28:05 +0100

Frederico A C Neves <[email-masked]> wrote:
> > IMO they do until validators record and use a 'root key ratchet':
> > never accept a key who's expiration is older than the inception date
> > of the RRSIG on the youngest root ZSK seen, or have some other defense
> > to roll-back-the-clock attacks.
>

I assume he means that the ratchet would observe when a key is no longer
published in the DNSKEY RRset and treat it as implicitly revoked.

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
Portland, Plymouth: South 4 or 5, occasionally 6 in Plymouth. Slight or
moderate. Rain, fog patches later. Moderate or poor, occasionally very poor.

---

From: Steve Crocker <[email-masked]>
Date: Fri, 4 Apr 2014 14:59:27 -0400

Perhaps this a good time for me to plug adoption of Signaling Cryptographic Algorithm Understanding, per RFC 6975.  The sooner this gets included in the implementation on the query side, the sooner we will have solid information on when it will be ok to phase out an obsolete algorithm.

This is not directly related to changes in key lengths, but it is relevant for the shifts from one algorithm to another, including changes in hash algorithms.

Steve