Subject: DNSSECbis Q-2: degradation attack

From: Sam Weiler <[email-masked]>
Date: Wed, 13 Aug 2003 12:36:29 -0400 (EDT)

This grew out of Q2 discussions (re: moving DSA to optional).  I like
the idea of moving DSA to optional (it's a weak liking -- I don't
care that much), but we need to address the following first:

A degradation attack is possible when multiple algorithms appear in an
apex DNSKEYset and/or DSset.  If not fixed, this attack will make new
(or optional) algorithms undeployable.  First, the proposed change
that avoids the attack:

   Every RRset MUST be signed by at least one DNSKEY of each algorithm
   in the DSset and each additional algorithm, if any, in the apex
   DNSKEYset.  The apex DNSKEYset itself must be signed by each
   algorithm appearing in the zone's DSset.

And the implications for a validator:

   1) If the only algorithms in a DSset aren't ones you understand,
   you may treat the zone as unsigned (as things are now).

   2) If there are algorithms you grok in the DSset, but the only
   algorithms signing the DNSKEYset are ones you don't understand, you
   should assume something bad is happening.  (this is a change)

   3) And if there are algorithms you grok in the DSset and DNSKEYset,
   but the only signatures on some RRset are made with algorithms you
   don't understand, you should assume something bad is happening
   (this is a change).

This change is based on the premise that the failure mode when "I
don't grok your algorithm(s)" may be different from the "this RRset
looks like it should be signed, but I haven't gotten a good RRSIG"
failure mode.  In the former case, current code may treat the zone as
unsigned and keep giving answers.  In the latter, current code
(generally) won't return an answer.

The Problem:

   As currently specified, it's sufficient for an RRset to be signed
   by any of the zone's apex DNSKEYs.  There's no way for a validator
   to tell which DNSKEYs the zone used (or intended to use) to sign a
   given RRset.

   If a zone includes an optional algorithm in its apex DNSKEYset,
   then signs some RRs with only that algorithm, a validator can't
   tell whether or not it's supposed to be getting other RRSIGs or
   not.  For example, a zone with a type 5 DNSKEY (RSA/SHA-1) and a
   type 42 DNSKEY (CryptSam, yet to be specified) might choose to sign
   its DNSKEYset with the type 5 DNSKEY and everything else with the
   type 42 DNSKEY.  In that case, you'd want a validator that doesn't
   understand type 42 to do something gentle, such as treating the
   zone as unsigned.

   The problem is that an attacker can strip RRSIGs.  Assume, in the
   example above, that the zone owner signed the whole zone with BOTH
   DNSKEYs.  That would let well-behaved clients, absent an attack,
   validate the data.

   But an attacker, knowing that type 42 DNSKEYs aren't widely
   supported, could forge answers in the zone and forge type 42 RRSIGs
   (with random data), knowing that virtually no one would be able to
   validate those signatures.  There's no way for most validators to
   tell the difference between this case and the "I only signed with
   type 42" case above.  Hence, adding a DNSKEY of a non-mandatory
   type to your apex DNSKEYset opens the door to a degradation attack.

   The same problem exists in the DS-->DNSKEYset security chain.  If a
   parent adds a DS record of an optional type, the attacker can forge
   a DNSKEYset signed by only the optional algorithm type that appears
   in the DSset.  A liberal validator, assuming that an RRSIG made by
   any of the DS's is sufficient, will treat the zone as unsigned.
   (Presumably the attacker would want the forged DNSKEYset to include
   the real DNSKEY of the optional algorithm, since any validator can
   at least check to see if there's a DNSKEY corresponding to one of
   the DS RRs and that at least one of the signatures on the DNSKEYset
   purports to have been made by a DNSKEY of the same tag.)

   Both of these problems give zone owners a strong incentive to not
   add optional algorithms.

The Fix:

   In broad terms, we need to add a mechanism that says "you can
   expect this RRset to be signed by these algorithms".  Rather than
   specify a new (or per-RRset) mechanism, this fix assigns some
   additional semantics to existing data.  Specifically, "if the
   algorithm is in the DNSKEYset, you have to sign everything with
   it".  This avoids making any bits-on-the-wire protocol changes.

   And for the DSset, the rule looks like "if an algorithm is in the
   DSset, it has to be used to sign the DNSKEYset (hence it has to be
   in the DNSKEYset, hence it has to sign the whole zone)".  Again,
   these are all client (and signer) behavior changes.  Authoritative
   servers don't change, and bits on the wire don't change.

   This isn't to say that each key in the DNSKEYset or each key
   corresponding to a DS must be used, just that every algorithm must
   be used.

   Furthermore, a validator should accept ANY valid signature chain,
   even if it doesn't get RRSIGs of all algorithms types or if some
   RRSIGs fail to validate.  A validator may ignore an algorithm,
   perhaps because that algorithm is weak, in which case it may make
   its validation decision as though the algorithm is completely
   unknown to it.  For example, if the only DS records at a delegation
   are for such an algorithm, the validator probably treats the
   delegation as unsecured.

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>

---

From: "Scott Rose" <[email-masked]>
Date: Wed, 13 Aug 2003 15:13:22 -0400

I agree with the suggested text.  Seems like something that should be stated
in the protocol draft when signed zones are discussed.

Scott

---

From: Ólafur Guðmundsson <[email-masked]>
Date: Fri, 15 Aug 2003 00:27:55 -0400

>    algorithm appearing in the zone's DSset.

IMHO this is an overkill and is restricting operation too much.
What this is saying is if there is more than one alg in DS set then
every RRset MUST be signed by all the algorithms at all times.
How is this to be enforced ?
We can not enforce this is in a signer, as someone may elect to implement
algorithm independent signers.
Should the master server can refuse to load zone that violates this
for a single RRset?
(Current protocol document does not say what to do if a master server
sees an unsigned RRset in a secure zone).

The basic premise for DNSSEC has been: if validator can verify RRset
against ONE temporarily valid RRset signature it may to mark the
RRest as secure. A paranoid validator should validate ALL available valid
signatures before marking the set secure.
I do not think it the protocol document role to dictate one or the
other behavior. IFF we want to dictate behavior there are
many other cases that need to be nailed down.

>    understand type 42 to do something gentle, such as treating the

See RFC3090 sections 2.1 and 2.2. If validator understands type 42
it may elect to use it.  IFF some RRset is only signed with type 42
then any validator that does not understand/use that type, will drop
this RRset as bad, this is the publishers choice.
Unfortunately in 2535 there is no way for validator to detect if this
is by choice or some of the RRSIG's where stripped from the answer.
Your text attempts to differentiate between the cases, but I think
the solution is worse than the problem.

>    DNSKEYs.  That would let well-behaved clients, absent an attack,

according to DNS-Threats document if an attacker can do this,
all bets are off for DNSSEC, thus this is not a justification
for a change.

>    type to your apex DNSKEYset opens the door to a degradation attack.

Validator can attempt to get a SIG(0)/TSIG signed answer from
Authorative server to detect this.

>    purports to have been made by a DNSKEY of the same tag.)

If attacker can do this, it is simpler for him to flip bits in RRsigs
to make zone date look bogus.

>    Both of these problems give zone owners a strong incentive to not

Identifying the problems is a good thing

>    are for such an algorithm, the validator probably treats the

I repeat, IMHO the fix proposed is worse than the problem.

Can you demonstrate a need for this change where attacker can succeed
without gaining access to an Authorative server or see the query ?

After I figure out the private part of the SEP key for the NL. TLD,
what can I do ?
How can I spread a bogus DS set for minbuza.nl ?
         Olafur

---

From: Miek Gieben <[email-masked]>
Date: Fri, 15 Aug 2003 08:59:24 +0200

I tend to agree with Ólafur here. Lesson to be learned from this: if you are connected
to the Internet and thus are expected to be visited by "normal" resolvers that
do not understand CryptSam you should not use that algorithm.

But if you are on a closed enviroment with "special" resolvers that do understand 
CryptSam you are free to use it.

IMHO this should be reworded and be put in a BCP (maybe in the key-handling draft
Olaf and I are writing).

grtz Miek

[On 15 Aug, @06:27, Ólafur wrote in "Re: DNSSECbis Q-2: degradation ..."]
> many other cases that need to be nailed down.

<SNIPPED REST OF THE MAIL>

---

From: Mike StJohns <[email-masked]>
Date: Fri, 15 Aug 2003 12:54:31 -0400

I had to think about this for a while and the read the other responses, so 
consider this a response to the chain, not just to Sam's email.  I will 
note that this ends up being more of a DNS ops type of discussion, rather 
than a protocol discussion.

Actually, this goes back to a previous thread about SEP keys and SEP bits.

I think the appropriate logic (and this was related to the discussion on 
secure notify as well as some other discussions) is that

The apex key set SHOULD be signed with all apex KEYs that have the SEP bit 
set.    An apex key signature set is considered incomplete if it is missing 
SIGs against all apex SEP KEYS. [Rationale:  If you have SEP keys at the 
apex that don't sign the apex KEY set, then they are extraneous material so 
why include them. OPS - although it may turn into a protocol issue if 
secure notify goes through]

A DSSet SHOULD be signed at least once with every algorithm that appears in 
a SEP KEY.  This implies that there must be at least one non-SEP KEY for 
every algorithm.  [Rationale:  If you don't do this, then you can end up 
terminating the chain of trust for that algorithm only.  Its an operational 
determination though]

That mostly takes care of the chaining issue.  Its possible there will 
still be lame secure delegations where the parent doesn't sign things with 
all the algorithms in the child, but forcing the parent to have add a 
signing set because one of its children decided to try something new seems 
basically broken.

E.g. I'm annoying.com, I sign my zone with DSA, RSA, classified algorithm 
1, classified algorithm 2, proprietary sig algorithm 23,  etc.  My parent 
may not even be able to know the algorithm for forming a particular 
signature (classified alg 1), let alone being able to do it - correct 
software, licence fees paid, etc.  This is simply an expansion of the 
island of trust discussion.

Hmm... one more possibility -

Say you have zone foo.com.  In the foo.com zone exists a bar.foo.com 
branch.  There is a delegation from that branch of bim.bar.foo.com.  Does 
the bim.bar.foo.com SIG(DS(bim.bar.foo.com)) at the parent have a signer 
name of bar.foo.com or foo.com?  If the former, then bar.foo.com needs its 
own keyset with at least one of each algorithm.  But based on 3008 et al, I 
think the latter is correct these days.

Mike

---

From: Miek Gieben <[email-masked]>
Date: Sun, 17 Aug 2003 04:01:28 +0200

I believe that stuff like this should be treated like an operational issue
first. Make a BCP with all the DNSSEC's does and don'ts.

If it really turns out to be a protocol issue - so be it, it can never be as
bad as DS :P

grtz Miek

---

From: Edward Lewis <[email-masked]>
Date: Sun, 17 Aug 2003 22:32:52 -0400

>If it really turns out to be a protocol issue - so be it, it can never be as

I think it is a protocol issue from this perspective.

DNSSEC has always been about protecting the resolver.  The data 
exchanged in the protocol interaction is designed to allow the 
resolver to put the pieces together and say "yeah, I like this" or 
"umm, something's not right."

DNSSEC doesn't protect the server so much - DNSSEC's data exchanges 
do not over come so-called denial of service issues.

In the situation we are talking about, let's assume that a resolver 
has received an apex's key set with keys in it that the resolver 
understands (as well as the DS set and all needed "above").  Let's 
assume that there are keys the resolver doesn't understand too.

The protocol document says that only one signature is required for 
each set of data in the zone.  It says nothing else about the 
signature.

The server might 1) sign the data with all algorithms or 2) sign the 
sets with just the algorithm the resolver doesn't understand.

Let's say the resolver gets a data set with only a signature from the 
algorithm it doesn't know.  In case 1, this means something was 
stripped.  In case 2, the data arrived safely.

The problem is that the resolver can't determine (it's undecidable) 
whether case 1 is the cause - and the data is fine, or case 2 is in 
effect - and the data has been mucked with.

If I consider example.com to be secured, I expect and can get the DS 
set for sub.example.com.  From that I can see whether sub.example.com 
uses keys I understand.  If so, I troddle on securely, if not, I 
*could* troddle on as it there was no DS set.

What's lacking is a way to "turn off" security inside a zone - not 
desirable with just one algorithm.  But, when it comes to multiple 
algorithms and requiring just one signature, we are inviting zones to 
"turn off" security "per algorithm" in a zone.  We shouldn't make the 
invite.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                            +1-703-227-9854
ARIN Research Engineer

Sponge Bob Square Pants?  I'm still trying to figure out the Macarena.

---

From: "Olaf M. Kolkman" <[email-masked]>
Date: Mon, 18 Aug 2003 12:22:48 +0200

I have been hesitating to participate in this thread for the following 
reason:

    I am not convinced if this _must_ be solved in order for DNSSEC to
    become a proposed standard. There is a operational way to cope
    with a change in algorithm if needed. I realize it involves
    becoming insecure. The last thing DNSSEC needs is yet another
    delay and solving problem will take time! So lets first ask
    ourselves the question: Does this need fixing now ?

    I am not yet convinced this needs fixing now; pointing to this
    issue in the protocol doc security section may be sufficient. What
    do others think?

                        -------------------

I still can not help thinking about a possible way out so here is my
contribution (I fear I am overlooking something and I miss the
sparring partner to go over this, so bare with me if I am uttering
nonsense).

The problem as I read it from Mike's and Ed's message, is that one
wants to turn the use of specific algorithms within a zone on or of,
without imposing requirements on the algorithm used by the parent (and
having the parent impose algorithms on the child).

The scheme below does not require the algorithms of the parent and
child to match.  Besides one can use the keys without the SEP bit to
turn specific algorithms on or off; making the it decidable which
algorithms to expect.

The solution boils down to enforcing the use of a distinct set of key
signing keys and zone signing keys, use the SEP key to distinguish
between them.

Signer requirements:

 1) the apex DNSKEY set MUST only be signed with keys that have the
    SEP bit on. All other RR-sets in the zone MUST be signed with keys
    that do not have the SEP bit set.

 2) For each algorithm occurring for keys with the SEP bit set there
    MUST be one signature over the DNSSKEY set and for each algorithm
    for keys without the SEP bit set there MUST be one signature over
    each RR-set in the zone.

 Note: Except that there MUST be a matching DNSKEY in the apex for
 each DS RR there is no additional requirement with respect to the DS
 RR set.

The Verifier requirements is that this behavior is verified as long
as data is supposed to be secure. This needs proper word-smithing in
MUST/SHOULD/MAY language, but this is the algorithm I am thinking of:

 Following the chain of trust from a trusted root down.

 - For each algorithm that you expect verify if the DNSKEY RR-set is
   properly signed with at least one key with the SEP bit set.

   You expect an algorithm if you have configured it in your trusted
   root or if it is a result from following the chain of trust.

 You now know you can trust the DNSKEY RR-set to be complete.

 - See which algorithms are available in the sub set of keys in the
   DNSKEY RR-set that do not have the SEP bit set.

   If you understand an algorithm, you expect signatures over zone data
   to be generated with it. If you do not understand any of the
   signatures you may, depending on local policy, treat the
   zone as verifiably insecure. 

 At delegation points.

 - Verify if the DS RR-set is signed with all the algorithms you
   expect. 

 You now know you can trust the DS RR-set to be complete.

 - See which algorithms are available in the DS RR-set and change the
   set of algorithms you expect to be the complete set of all algorithms
   you understand from the DS RR-set. If there are no algorithms you
   can deal with you may, depending again on local policy, treat the zone as
   verifiably insecure.

 - Follow the DS pointers for each of the algorithms you understand
   (i.e. expect) and iterate down the chain starting from the first
   step above.

For end-nodes.

 - The data is secure if signed with all algorithms you expect.

*sigh* Lets not discuss this further if there is no real need though.

-- Olaf

---------------------------------| Olaf M. Kolkman
---------------------------------| RIPE NCC

---

From: "Scott Rose" <[email-masked]>
Date: Mon, 18 Aug 2003 10:23:27 -0400

Also, since the attack and defense of this attack is based on the contents
of a zone (that is, what constitutes a "signed zone") it should either be
addressed in the protocol document (where signed/secure zones are discussed)
or in a BCP/policy guide.

Depends on how big of a threat a degradation attack is assumed to be.  If it
is a severe risk, than the protocol document, if not, a BCP or some other
implementation guideline.

Scott
----- Original Message ----- 
From: "Edward Lewis" <[email-masked]>
To: "Miek Gieben" <[email-masked]>
Cc: "Mike StJohns" <[email-masked]>; "Sam Weiler"
<[email-masked]>; <[email-masked]>
Sent: Sunday, August 17, 2003 10:32 PM
Subject: Re: DNSSECbis Q-2: degradation attack