Subject: Defending against the Kaminsky attack

From: "George Barwood" <[email-masked]>
Date: Fri, 22 Aug 2008 12:55:58 +0100

I was wondering whether the Kaminsky attack can be defeated by methods other than adding more entropy.

I think it can. These thoughts are preliminary, came to me in my sleep last night, so I may be mistaken.

o Attack
  Generate multiple questions
  type=A x1.bigbank.com
  type=A x2.bigbank.com
  type=A x3.bigbank.com
  ....
  Cache asks ns1.bigbank.com for each. 
  Bailiwick is bigbank.com.
  Spoof response is:
  Question x1.bigbank.com
  Answers: Empty
  Authority: NS for bigbank.com is ns1.bigbank.com
  Additional: Host for ns1.bigbank.com is 10.0.0.99 ( IP address under control of attacker )

  Is this suspicious?
  Yes. Authority record is not required, Bailiwick = LHS of authority record.
  LHS of NS record should be properly within Bailiwick, this one isn't, it is equal.
  So record is invalid and should be discarded.

  Ok, what about this:
  Question x1.bigbank.com
  Answers: Empty
  Authority: NS for x1.bigbank.com is ns1.bigbank.com
  Additional: Host for ns1.bigbank.com is 10.0.0.99* ( attacker's IP address )

  Is this suspicious?
  Authority record is now ok. 
  But glue record is not. 
  Glue records should only be accepted if they LHS matches RHS of valid Authority record that needs glue.
  An authority record needs glue iff it is of form NS for xxxxx is something.xxxxx

So, resolvers should make these checks.

Apologies in advance if this turns out to be nonsense, or is already well known.

I have not tested it, and am not sure if there are any implications for standards.

George Barwood

---

From: Paul Vixie <[email-masked]>
Date: Fri, 22 Aug 2008 20:16:31 +0000

those are pattern-specific poison avoidances.  i'd much rather we focus
on not accepting the bad response than on not letting its content hurt us.

-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

--
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: "George Barwood" <[email-masked]>
Date: Fri, 29 Aug 2008 12:23:02 +0100

----- Original Message ----- 
From: "Paul Vixie" <[email-masked]>
To: "George Barwood" <[email-masked]>
Cc: <[email-masked]>
Sent: Friday, August 22, 2008 9:16 PM
Subject: Re: Defending against the Kaminsky attack

> on not accepting the bad response than on not letting its content hurt us.

[ I replied some days ago, but it seems to have got lost, possibly because I 
was at the beach so had to use an unsubscribed email address ]

I was not very definite on what checks I think are required, but the 
approach I am advocating ( with some encouragement from Nicholas Weaver via 
private email ), is completely general.

For definiteness, I'm here is the code I am using (see rough English 
translation below). The checking code is applied after parsing a DNS 
response, hopefully the meaning is self-evident. Records in each of the 
sections are initialised to be "Not ok", that is to be discarded.

  public void Check( int T, String Question, String Bailiwick )
  {
    if ( Answers.Length > 0 )
    {
      for (int i=0;i<Answers.Length;i+=1)
      {
        DnsRecord r = (DnsRecord)Answers[i];
        r.Ok = ( r.T == T || r.T == 5 ) && r.Name == Question;
      }
    }
    else // Referral
    {
      Hashtable GlueRequired = new Hashtable();
      for (int i=0;i<NameServers.Length;i+=1)
      {
        DnsRecord r = (DnsRecord)NameServers[i];
        r.Ok = r.T == 2 && r.Name.EndsWith( Bailiwick ) && r.Name != 
Bailiwick;
        if ( r.Ok )
        {
          String Rhs = (String)r.D.Data;
          if ( Rhs.EndsWith(r.Name) && Rhs != r.Name ) // Glue required
          {
            GlueRequired[Rhs] = Rhs;
          }
        }
      }
      for (int i=0;i<Additional.Length;i+=1)
      {
        DnsRecord r = (DnsRecord)Additional[i];
        r.Ok = r.T==1 && GlueRequired[r.Name] != null;
      }
    }
  }
}

This is in addition to "standard" checking of the Question section.

Rough translation into English:

If there are answers, ignore everything else.
Accept only answers where LHS matches the question.
If there are no answers, accept only proper referrals.
Glue is accepted only in one very specific case, that seems to be safe.

At least 3 questions arise:

(1) Is this code sufficient to successfully resolve names for properly 
configured domains?

(2) Does it prevent Kaminsky attacks?

(3) Is the performance penalty acceptable?

I believe the answer to all these questions is yes.

---

From: Paul Vixie <[email-masked]>
Date: Fri, 29 Aug 2008 16:00:02 +0000

> ...

no.  because you don't know whether you have an answer until you've looked
at the authority section.  answers are cacheable facts, not rrsets per se,
and the enumeration is at least:

	authoritative answer, no data for requested type
	nonauthoritative answer, no data for requested type
	name does not exist, not even as an empty nonterminal
	delegation
	server failure

note that the AA bit doesn't help much.  it might be set in an answer from
some zone who also sent you a delegation to a subzone, in which case the
answer isn't authoritative no matter what the AA bit tells you.

in any case, 'if there are answers, ignore all else' is bad out the gate.

> I believe the answer to all these questions is yes.

did you read the proposal i sent out yesterday ("...section by section") ?

---

From: "George Barwood" <[email-masked]>
Date: Sat, 30 Aug 2008 08:58:31 +0100

I now agree that this whole idea ( of performing checks other than the 
standard Bailiwick check ) is a dead end. It just doesn't work, thanks to 
Wouter Winjgaards for pointing me to the case of  Peter Koch's 'phantom 
referral', so the only way forward is getting more entropy.

I believe there are 3 mechanisms that work.

(1) The 0x20 proposal.

(2) For Root and TLD queries, prepending a random nonce to the question.

(3) Repeating the query, and using a temporary data structure to "converge" 
the result.
Recently expired cache entries can be taken into account so that for TTL 
refresh operations, repetition is not required.

[ I am trying this, and so far it works very nicely at  50 bits of entropy, 
without random source port ]