Subject: [dnsext] Problem with Section 2.2 of RFC 4035

From: Edward Lewis <[email-masked]>
Date: Tue, 17 Aug 2010 10:24:41 -0400

On another list, operators have identified an issue with this passage

>     "There MUST be an RRSIG for each RRset using at least one DNSKEY of
>     each algorithm in the zone apex DNSKEY RRset.  The apex DNSKEY RRset
>     itself MUST be signed by each algorithm appearing in the DS RRset
>     located at the delegating parent (if any)."

and being able to "roll an algorithm."

The problem is - what if a cache has a copy of a DNSKEY set with 
algorithms 5 and 7 and it receives a set only signed with algorithm 7?

(A longer winded discussion is available here:
http://dnssec-deployment.org/pipermail/dnssec-deployment/2010-August/004330.html
)

The problem I see is that validators are inappropriately enforcing 
the first MUST.  The MUST was for generation, not for validation.

My suggestion is to add text like this around that section (or added 
to the DNSSECbis document):

To clean up the specification, "it should be emphasized that although 
the signer is supposed to supply one of every signature, the 
validator only needs
one working signature to okay the data."

-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis             
NeuStar                    You can leave a voice message at +1-571-434-5468

Spouses, like Internet protocols, lack necessary troubleshooting tools. Sigh.

---

From: "W.C.A. Wijngaards" <[email-masked]>
Date: Tue, 17 Aug 2010 16:47:58 +0200

Hi Ed,

> algorithms 5 and 7 and it receives a set only signed with algorithm 7?

If the validator does not support algorithm 7, then the validator has to
mark that set as bogus.  Thus this rollover is a failure - it does not
support validators that do not support algorithm 7 - they get a BOGUS
outage for a TTL.

Therefore during rollover you have to accomodate validators that support
one of the algorithms but not the other.  Thus distribute data sets
signed with both algorithms during the TTL when validators can have both
algorithms in the DNSKEY.  (Thus a check that signatures 5 and 7 are
present is a good thing?  Zone-lint tools should do this?)

And, no, you cannot require validators to 'fetch data from the
authority', because they cannot signal an intermediate cache to do so.
(unless you think sending queries to cause cache memory-exhaustion is ok
:-) ).  (Not sure you claim this, but people may be tempted to use this
to 'fix' things).

Best regards,
   Wouter

---

From: Edward Lewis <[email-masked]>
Date: Tue, 17 Aug 2010 14:07:48 -0400

This isn't the same problem.

If a validator understands 5, sees 5 and 7 in the DNSKEY set it 
holds, and then gets a data set signed only with 7, that's an error 
and rather insurmountable because we don't want to allow a downgrade 
to succeed.

If a validator understands 5 and 7, sees 5 and 7 in the DNSKEY set it 
holds, and then gets a data set signed only with 7, this is a 
non-problem unless the validator gets pedantic and demands  the 5 
signature be there.

In the other-list discussion, I used this matrix:

>>   The cache has:-->    old-alg-only        both-alg-keys         new-alg-only
>>   The cache gets-v
>>   Old sig only              I                   II                  III
>>   Both sigs                 IV                   V                   VI
>>   New sig only             VII                 VIII                  IX

That assumed that the validator understood both the old and new algorithm.
If the validator only understands the old algorithm, then states II, V, and
VIII become the same as I, IV, and VII.

The states to avoid are III and VII.  So, the first situation above, 
which matches VIII, folded into VII, yeah, we have to avoid that.

Thinking...

The best I can come up with now, is that if you only know of the old 
keys, and the new DNSKEY set shows that there's a new algorithm and 
it is matching the signature you have, you can reliably deduce that 
"something is up" in the sense that the authority is changing the 
zone.  Even though you cannot validate the signature, you can 
validate the expectation that the data is still signed.

Remembering the danger is that you could be vulnerable to a 
downgrade, the potential attacker would have had to add a new 
algorithm to the DNSKEY set (signed with the algorithm you do know - 
we call this the both-alg-keys set in the matrix) inorder to pull 
this off.  If the attacker would forge in a new set of keys, they 
could just as easily forge in a new signature and probably get away 
with more.

(Sorry, I haven't been able to fully think this out.)

At 16:47 +0200 8/17/10, W.C.A. Wijngaards wrote:
>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA1
>
>Hi Ed,
>
>-----BEGIN PGP SIGNATURE-----
>Version: GnuPG v2.0.14 (GNU/Linux)
>Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
>
>iEYEARECAAYFAkxqoR4ACgkQkDLqNwOhpPgBWwCcD/Ko1nAVNqZSdQN2U376lBcN
>3lcAnjoOelHn3X4WeWWUxpW+SdSQX36p
>=q3LR
>-----END PGP SIGNATURE-----

---

From: "W.C.A. Wijngaards" <[email-masked]>
Date: Wed, 18 Aug 2010 09:53:14 +0200

Hi Ed,

I do not see how 'fixing this' gains us something.  If somehow the
resolvers that understand both 5 and 7 act differently, how does that
help with rollover?  You must accommodate the resolvers that understand
5, not 7.  (and the ones that understand 7 not 5).

I understand that possibly, we can be more lenient in checking
signatures, in the case where you understand both algorithms and one is
missing.  But that situation should not happen because it breaks all the
resolvers that understand only one and that one is missing?  It can
therefore certainly not be the 'recommended' rollover method.

Your map of cases assumes the target understands both algorithms, and I
am with you and I see it could be made more lenient.  But it is that
same map for resolvers that support one algorithm that is the issue.
And if you accommodate those other maps, I think that the case where you
understand both could just as well validate both signatures (and be
'pedantic' :-) but the pedantry does tell you that you are botching the
rollover ).

Best regards,
   Wouter

On 08/17/2010 08:07 PM, Edward Lewis wrote:
> If a validator understands 5, sees 5 and 7 in the DNSKEY set it holds,
> and then gets a data set signed only with 7, that's an error and rather
> insurmountable because we don't want to allow a downgrade to succeed.
> 
> keys, and the new DNSKEY set shows that there's a new algorithm and it
> is matching the signature you have, you can reliably deduce that
> "something is up" in the sense that the authority is changing the zone. 
> Even though you cannot validate the signature, you can validate the
> expectation that the data is still signed.
> 
> Remembering the danger is that you could be vulnerable to a downgrade,
> the potential attacker would have had to add a new algorithm to the
> DNSKEY set (signed with the algorithm you do know - we call this the
> both-alg-keys set in the matrix) inorder to pull this off.  If the
> attacker would forge in a new set of keys, they could just as easily
> forge in a new signature and probably get away with more.
>

---

From: Chris Thompson <[email-masked]>
Date: 18 Aug 2010 14:48:53 +0100

>one working signature to okay the data."

This seems to completely nullify the protection against the
downgrade attack that the 4035/2.2 text was meant to provide.
(Or else I misunderstsnd what that was.)

A validator can never be sure it has all the RRSIGs signing an RRset,
because the this set is not itself signed. A MitM can selectively
remove RRSIGs to taste. If he can get away with removing all RRSIGs
for a stronger algorithm, he can force the validator to rely on the
weaker one. If he has also cracked the weaker algorithm, he can
start feeding the validator fake responses.

This doesn't depend in any way on the validator only understanding
one of the algorithms.

The conceptual mismatch here is that 4035/2.2 is assuming long-term
signing with more than one algorithm. When doing a prophylactic
algorithm rollover, one usually isn't worried about downgrade
attacks of this sort, because you assume that the old algorithm
isn't broken *yet*, and won't be before the rollover is completed.

-- 
Chris Thompson               University of Cambridge Computing Service,
Email: [email-masked]    New Museums Site, Cambridge CB2 3QH,
Phone: +44 1223 334715       United Kingdom.

---

From: Edward Lewis <[email-masked]>
Date: Wed, 18 Aug 2010 13:19:14 -0400

>>To clean up the specification, "it should be emphasized that although the
>>signer is supposed to supply one of every signature, the validator only
>>needs one working signature to okay the data."
>

Yes, there's a misunderstanding.  As one operator said "It's not a 
downgrade attack if something removes signatures that I can't 
validate...."  (Operator being Michael Richardson)  The downgrade 
vulnerability is not that a signature can be stripped but rather that 
a data set's protection can be dropped from signed to insecure.  In 
reality, the first step is for the protocol to convey to the 
validator that there is an expectation of a signature, second step is 
to convey the data, and third step to convey the signature.

>start feeding the validator fake responses.

One of the misconceptions is that there a notion of "weaker" and 
"stronger" algorithms.  If the MitM has "cracked the weaker" then why 
not just sign a DNSKEY set with the attacker's key in it and sign the 
rest of the data?  With a "stronger" key?  When RFC 2065 was under 
development (DNSSEC the 1st), we had a notion of strong and weak 
keys.  It just didn't make sense.

>This doesn't depend in any way on the validator only understanding

It changes the state machine.

>isn't broken *yet*, and won't be before the rollover is completed.

I can tell you that is not what was assumed.  The situation behind 
the derivation of the text was this: how does a verifier, in a mixed 
algorithm environment, determine the expected state of security of a 
RR set in a zone?  Starting with being able to validate records from 
the parent, meaning, you can verify a signature over the DS set for 
the child, you can tell if the child is using an algorithm you 
understand.  (States: There is at least one algorithm I understand, 
There is no algorithm I understand, There are no algorithms in use.)

If a zone could choose to sign just some record sets with one 
algorithm and then use another for others, the validator would not be 
able to set up an expectation, especially in a situation in which not 
all algorithms are known.  This is why the requirement for "each 
algorithm" at each set.  Note, the restriction isn't "each key."

The assumption was that signer had a matching DNSKEY an data set for 
zone, matching meaning same serial number.  But the serial number of 
a set is not known by a cache's verifier.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis
NeuStar                    You can leave a voice message at +1-571-434-5468

---

From: Edward Lewis <[email-masked]>
Date: Wed, 18 Aug 2010 13:28:53 -0400

First, it's too late to help the existing deployments.  Given that 
there's little difference between algorithms 5 and 7, that's kind of 
a bad example.

What are we solving?  Two streams here.

One, in operations, the act of algorithm roll over has become a 
significant concern.  I'm avoiding using the word "big" on purpose. 
Operations should not be required to walk a fine, distinct line to 
maintain a healthy system.  DNS has scaled because it has a wide 
tolerance in operations.

Two, in documentation, clearing up the meaning of the section should 
be done in the name of accurately recording the design of the 
protocol.  The intent of the section was to tell the signer what had 
to be done, and to allow verifiers to know what to expect.  However, 
the mistake I made in the analysis period was to neglect to consider 
that a verifier may, unlike the signer, be looking at the DNSKEY set 
and the subject data set from different serial number versions of the 
zone.

The map of cases isn't assuming anything about the recipients 
knowledge of the algorithms.  If it does not understand one, the 
other, or both, there still is a  "old" and a "new" algorithm 
(because the topic is algorithm roll), what differs is how the cases 
"collapse" in analysis.  In essence, "both" is effectively the same 
as "old" or "new" depending on which of the algorithms a recipient 
knows.  (If the recipient knows neither, the change doesn't matter - 
unless there's a third algorithm involved.)

But even if the recipient does not know the new algorithm, the 
recipient is aware of it.  So it's not complete ignorance, it's the 
inability to handle the cryptographic elements.

The problem is that if we have to account for a situation in which a 
verifier has an older version of a DNSKEY set than a received data 
set, it is nearly impossible to retire an algorithm.

I suppose that we would have to have servers that continue to serve 
signatures for which the key has been pulled from the DNSKEY set and 
even if all of the keys of an algorithm were pulled.  IOW, I need to 
simultaneously allow for the old key sets to expire and fill caches 
with the new data sets without distributing the algorithm to be 
retired's keys.

I suppose we could accomplish this by pulling the DS records from the 
parent for an algorithm that is being retired but still push out the 
keys and signatures.  Then the chain of security is quasi-broken for 
that zone, verifiers knowing only the retired algorithm would see it 
as insecure.  For verifiers knowing all the algorithms involved, they 
could use the old algorithm, but also have the new available.

The latter works better if the verifiers do not enforce the "all 
algorithms" rule that was meant to apply to the signing process.

Are any of these reasonings any more convincing?  (I'm still swating 
at flies here and there while I try to think about this.)

At 9:53 +0200 8/18/10, W.C.A. Wijngaards wrote:
>iEYEARECAAYFAkxrkWkACgkQkDLqNwOhpPifLgCdFZobWQj2pttQX3ZutTKEuuGv
>GVAAoJQHLD/OmwUgSM7tyFR6s2XE3K4W
>=qNqd

---

From: "W.C.A. Wijngaards" <[email-masked]>
Date: Thu, 19 Aug 2010 10:41:53 +0200

Hi Ed,

So, going back to your table, go over the issue.  There is an algorithm
rollover.  The cache may support old, support new, or support both old
and new algorithms or support neither.

Caches that support neither old, nor new algorithm will see this when
they encounter the DS record from the parent and go to insecure.  This
is backwards compatibility from the DNSSEC spec.

If the cache supports the old, but not the new algorithm.
* It has the old DNSKEY.
  - It gets the old signature: OK.
  - It gets the old+new signature: OK.  It ignores the extra signature
here.  DNSSEC spec tells validators to ignore 'extra' signatures.
  - It gets the new signature: Bogus.  It looks like the old signature
has been removed and some unknown signature inserted.
* It has the old+new DNSKEYs
  The same as for the old DNSKEY only.
  It might get pedantic and complain if the new signature is not there
that it should be there (but it cannot understand it).
* It has the new DNSKEY.
  Because it does not support the new algorithm, it will see that the DS
record has only unknown algorithms and fall to insecure for this domain.

If the validator supports both the old and the new algorithm.
* It has the old DNSKEY.
  - it gets the old signature: OK.
  - it gets old+new signatures: OK.  Ignores extra signature.
  - it gets new signature, Bogus.  old signature is missing, and there
is no key for this new signature.
* It has the old+new DNSKEYs.
  - it gets the old signature: the strict implementation of 4035-2.2
rejects this because the new signature is missing.  Since the old
signature is understood, this may constitute enough crypto to trust the
data.
  - it gets the old+new signatures: OK.
  - it gets the new signature: same as only the old, strict complains
that this zone is badly signed, lenient may see enough crypto that it
can understand.
* It has the new DNSKEY.
  - it gets the old signature: Bogus.  new signature missing, no old key
present.
  - it gets old+new signatures: OK.  Ignores extra signature.
  - it gets the new signature: OK.

If the cache supports the new algorithm but not the old.
This is similar to supporting only the old algorithm, but with 'old' and
'new' interchanged.  The only thing that is not symmetrical in the
DNSSEC spec is the DS-hash algorithm treatment, where the 'weaker
algorithm is ignored'.

So a successful rollover will have to avoid the Bogus state, it is
undesirable to create outages.  At the end, the validators that support
the old but not the new algorithm end up going to insecure for the zone.

The first thing you want to do is insert the new DNSKEY with the new
algorith, but doing so, because of DNS TTLs, will cause validators to
see the old+new DNSKEYs with old(cached) data with only the old
signature, and validators that support only the new algorithm but not
the old will go BOGUS since the signature they understand is missing.

So, before you can insert the new DNSKEY you have to distribute the new
signatures.  This is fine because the extra signatures are ignored.
Once old+new signatures are distributed, you then can insert the new
key.  Validators that understand only the old algorithm continue
validating the old signature from the old key (and ignore the added new
signature if they encounter it, and do not understand the new key).
Validators that understand the new but not the old algorithms do not get
their hands on the new DNSKEY until the new signatures are also certain
to be available.  Validators that understand both have no reason to
complain as they get both signatures when they hold both keys.

So, then you are in a state with old+new DNSKEY and old+new signatures.

You want to remove the old DNSKEY and old signatures.  You cannot remove
the signatures with the old algorithm right away, because validators
that understand the old but not the new algorithm would go Bogus if the
signature they can understand is no longer available.

You have to remove the old DNSKEY first.  Wait TTL.  Then you can remove
the old signatures.  Because after you waited TTL, the validators that
did not understand the new algorithm have to refetch their DNSKEY and
see it now has only the new algorithm, which they do not support, and
they go to insecure for the zone.  And then you can remove the old
signatures as well.  Validators which understand both old and new
algorithms also pick up the new DNSKEY (without the old) and no longer
have cause to complain about missing old signatures.  Validators that
only understand the new algorithm are fine too.

If you have a parent, then also, you have to in the state when you are
double-signed, perform a DS-exchange.  You can change your DS from the
old to only the new.  (I think you can do this in one go, because you
are neatly double signed).  You then wait TTL before removing the old
DNSKEY.

So, after all this rollover stuff, you can see that you have to
accommodate for validators that do not support both algorithms.  And
that by doing so, you make sure that signatures for every algorithm are
available for validators that hold DNSKEYs with multiple algorithms.
Thus, checking strictly that such signatures are available should only
fail when validators that support only one algorithm go Bogus.  And if
you do the rollover properly, that should never occur.

Best regards,
   Wouter

On 08/18/2010 07:28 PM, Edward Lewis wrote:
> there's little difference between algorithms 5 and 7, that's kind of a
> bad example.
> 
> Two, in documentation, clearing up the meaning of the section should be
> done in the name of accurately recording the design of the protocol. 
> The intent of the section was to tell the signer what had to be done,
> and to allow verifiers to know what to expect.  However, the mistake I
> made in the analysis period was to neglect to consider that a verifier
> may, unlike the signer, be looking at the DNSKEY set and the subject
> data set from different serial number versions of the zone.
> 
> The map of cases isn't assuming anything about the recipients knowledge
> of the algorithms.  If it does not understand one, the other, or both,
> there still is a  "old" and a "new" algorithm (because the topic is
> algorithm roll), what differs is how the cases "collapse" in analysis. 
> In essence, "both" is effectively the same as "old" or "new" depending
> on which of the algorithms a recipient knows.  (If the recipient knows
> neither, the change doesn't matter - unless there's a third algorithm
> involved.)
> 
> But even if the recipient does not know the new algorithm, the recipient
> is aware of it.  So it's not complete ignorance, it's the inability to
> handle the cryptographic elements.
> 
> verifier has an older version of a DNSKEY set than a received data set,
> it is nearly impossible to retire an algorithm.
> 
> simultaneously allow for the old key sets to expire and fill caches with
> the new data sets without distributing the algorithm to be retired's keys.
> 
> that zone, verifiers knowing only the retired algorithm would see it as
> insecure.  For verifiers knowing all the algorithms involved, they could
> use the old algorithm, but also have the new available.
> 
> Are any of these reasonings any more convincing?  (I'm still swating at
> flies here and there while I try to think about this.)
> 
> 
>>>>>>    Old sig only              I                  
>>>>>> II                  III
>>>>>>    Both sigs                 IV                  
>>>>>> V                   VI
>>>>>>    New sig only             VII                
>>>>>> VIII                  IX