Possible fix for Kaminsky's bug

Wed Aug 27 15:02:27 UTC 2008

On Tue, Aug 26, 2008 at 10:45:27PM -0700, =?BIG5?B?SklOTUVJIFRhdHV5YSAvIK+rqfq5Rqt2IDxKaW5tZWlfVGF0dXlhQGlzYy5vcmc+?= wrote:
> 
> I'm pretty sure that this patch doesn't avoid all variations of
> Kaminsky's attack,

Hehe... I never claimed my one-character patch would fix *all* bugs
in bind -- I don't have *that* kind of power ;)

> but could you be more specific about the intended
> attack scenario you have in your mind, by clarifying:
> 
> - assumption: the cache contents before the attack with the 'trust'
>   level
> - attack packet: a sequence of query that triggers the attack and
>   forged responses
> - resulting cache contents when the attack succeeds

Allright, here's the long version:

Assume a victim server, let's call it victim.net.cmu.edu. Let's try to
get it to think evil.net.cmu.edu is the NS record for cnn.com.

First, let's see what the normal, clean state of things looks like:

dig @victim.net.cmu.edu cnn.com

; <<>> DiG 9.5.0-P1 <<>> @victim.net.cmu.edu cnn.com
; (1 server found)
;; global options:  printcmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 62921
;; flags: qr rd ra; QUERY: 1, ANSWER: 4, AUTHORITY: 4, ADDITIONAL: 0

;; QUESTION SECTION:
;cnn.com.                       IN      A

;; ANSWER SECTION:
cnn.com.                300     IN      A       64.236.16.52
cnn.com.                300     IN      A       64.236.16.20
cnn.com.                300     IN      A       64.236.24.12
cnn.com.                300     IN      A       64.236.29.120

;; AUTHORITY SECTION:
cnn.com.                600     IN      NS      twdns-01.ns.aol.com.
cnn.com.                600     IN      NS      twdns-03.ns.aol.com.
cnn.com.                600     IN      NS      twdns-02.ns.aol.com.
cnn.com.                600     IN      NS      twdns-04.ns.aol.com.

OK, so far so good. Now, the attacker begins sending queries for
<random-host>.cnn.com to victim.net.cmu.edu. A wireshark dump of
the requests looks like this:

Domain Name System (query)
    Transaction ID: 0x0d2e
    Flags: 0x0100 (Standard query)
    Questions: 1
    Answer RRs: 0
    Authority RRs: 0
    Additional RRs: 0
    Queries
        86ANDC8zkC8.cnn.com: type A, class IN
            Name: 86ANDC8zkC8.cnn.com
            Type: A (Host address)
            Class: IN (0x0001)

At the same time, the attacker starts to flood victim.net.cmu.edu with
spoofed replies. If they guess right, victim.net.cmu.edu accepts a reply
which appears to come from e.g. twdns-01.ns.aol.com, with the following
contents:

Domain Name System (response)
    Transaction ID: 0x0267
    Flags: 0x8500 (Standard query response, No error)
    Questions: 1
    Answer RRs: 1
    Authority RRs: 1
    Additional RRs: 1
    Queries
        86ANDC8zkC8.cnn.com: type A, class IN
            Name: 86ANDC8zkC8.cnn.com
            Type: A (Host address)
            Class: IN (0x0001)
    Answers
        86ANDC8zkC8.cnn.com: type A, class IN, addr <Random.Made.Up.IP>
            Name: 86ANDC8zkC8.cnn.com
            Type: A (Host address)
            Class: IN (0x0001)
            Time to live: 13 hours, 44 minutes, 48 seconds
            Data length: 4
            Addr: <Random.Made.Up.IP>
    Authoritative nameservers
        cnn.com: type NS, class IN, ns evil.net.cmu.edu
            Name: cnn.com
            Type: NS (Authoritative name server)
            Class: IN (0x0001)
            Time to live: 13 hours, 44 minutes, 48 seconds
            Data length: 20
            Name server: evil.net.cmu.edu
    Additional records
        evil.net.cmu.edu: type A, class IN, addr <Random.Made.Up.IP>
            Name: evil.net.cmu.edu
            Type: A (Host address)
            Class: IN (0x0001)
            Time to live: 13 hours, 44 minutes, 48 seconds
            Data length: 4
            Addr: <Random.Made.Up.IP>

Now, the authority section of the spoofed reply is considered for caching,
has equal trust with the cached entry. Before my patch, bind would break
the tie in favor of the *new* info, and overwrite the cache if trust were
equal (dns_trust_authauthority). Here's what victim.net.cmu.edu would think
now:

dig @victim.net.cmu.edu cnn.com

; <<>> DiG 9.5.0-P1 <<>> @victim.net.cmu.edu cnn.com
; (1 server found)
;; global options:  printcmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 3138
;; flags: qr rd ra; QUERY: 1, ANSWER: 4, AUTHORITY: 1, ADDITIONAL: 1

;; QUESTION SECTION:
;cnn.com.                       IN      A

;; ANSWER SECTION:
cnn.com.                43      IN      A       64.236.16.52
cnn.com.                43      IN      A       64.236.24.12
cnn.com.                43      IN      A       64.236.16.20
cnn.com.                43      IN      A       64.236.29.120

;; AUTHORITY SECTION:
cnn.com.                44430   IN      NS      evil.net.cmu.edu.

;; ADDITIONAL SECTION:
evil.net.cmu.edu.     82977   IN      A       128.2.XYZ.ABC

The attacker has the "starter pistol" to the "race", because whenever they
do manage to slip victim.net.cmu.edu a spoofed reply, the NS record for
cnn.com gets overwritten, and the attacker wins. They can try as often as
they want, and the more they try, the better their chances of winning.

With my patch applied, the tie between equal dns_trust_authauthority values
of the cached NS record and the new (fake) one is broken in favor of the
cached one, and the attacker is back to where they used to be before
Kaminsky's exploit, which means they have to wait and guess right during the
short window of opportunity when the cache expires, and if they get it wrong,
they have to wait for the next time the TTL runs out.

I believe this was the source of the entire hoopla about Dan's exploit, the
fact that timing of the attack was now under the control of the attacker.

I moved the timing back under the control of the real authority, so everything
should be back to normal.

What's the downside to my patch ? I guess we are now holding an
authoritative server to the promise not to change the NS record for
the duration of the TTL, which is kinda what the TTL is for in the
first place :)

Let me know what you think.

Thanks,
--Gabriel