Subject: Randomness requirements for message ID generation

From: Florian Weimer <[email-masked]>
Date: Tue, 12 Jul 2005 01:21:36 +0200

Apologies if this is the wrong forum to ask such questions.

What are the randomness requirements for message ID generation?  Are
simple time-dependent IDs acceptable?  What about PRNGs which leak
their internal state?  Would you recommend different levels of
randomness for stub and full resolvers?

(I know it's just a 16-bit number, so we aren't in a very good
position no matter what we do.  But there's no reason to make things
even worse, IMHO.)

--
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: Jim Reid <[email-masked]>
Date: Tue, 12 Jul 2005 10:18:09 +0100

On Jul 12, 2005, at 00:21, Florian Weimer wrote:

> What are the randomness requirements for message ID generation?

The RFCs say nothing about this. Which is hardly surprising. The ID 
field is just to help a resolver match a response to an outstanding 
query. See Section 7.3 of RFC1035.

> Would you recommend different levels of randomness for stub and full 
> resolvers?

There doesn't seem much point. Even if better randomness helped. Stub 
resolvers typically only make one query during their lifetime so 
maintaining extra state so it could use "more random" IDs would be 
futile. And with only 16 bits to play with, it's easy to swamp a 
resolver with bogus responses that exhaust that name space. Besides, it 
would be wise to assume an attacker is able to see the queries (or 
responses) on the wire and either tamper with the replies or fake a 
response for the query that the resolver made. In that context, the 
randomness (or not) of the query ID is moot.

> position no matter what we do.  But there's no reason to make things

Randomising the query IDs barely raises the bar so IMO it's hardly 
worth resolvers investing in strong random number generation. And 
anyone who does this believing it improves security is kidding 
themself. [That said, resolvers should randomise the query IDs as it's 
the Right Thing To Do.] The real solution to this problem is to protect 
the integrity of the DNS data while it's on the wire. Fortunately there 
are two mechanisms for that: TSIG & SIG(0) which are based on crypto 
hashes and DNSSEC which uses public-key signatures over resource 
records. These raise the bar for attackers quite substantially because 
they now have to get the shared secret or private key before they'd be 
able to feed bogus data to the resolver.

---

From: Edward Lewis <[email-masked]>
Date: Tue, 12 Jul 2005 08:48:50 -0400

>Apologies if this is the wrong forum to ask such questions.

This is probably the right one for this.

>randomness for stub and full resolvers?

Shortened answer is - there's no requirement for randomness, but the 
less predictable the number is, the less chance a really lame attempt 
at message stuffing will succeed.  It's similar to playing with the 
TCP sequence numbers.

Another reason to alter the message id is for local-side message 
management.  If you don't change it at all, you have more work in 
trying to match answer to question.  That's probably a bigger 
consideration than defending an "attack."

>position no matter what we do.  But there's no reason to make things

As Jim replied, _message_ "security" is better done via TSIG or 
TKEY/SIG(0) (or to rely on something like IPSEC to protect the 
channel or a VPN).

If you are asking in the context of implementing DNS code - my 
recommendation is to do something cheap to make the id unpredictable 
(or random) and spend time making TSIG/SIG(0) very easy to enable.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                                +1-571-434-5468
NeuStar

If you knew what I was thinking, you'd understand what I was saying.

---

From: Ólafur Guðmundsson /DNSEXT co-chair <[email-masked]>
Date: Tue, 12 Jul 2005 10:56:27 -0400

>Apologies if this is the wrong forum to ask such questions.

<chair-hat-on>
This is the right forum.
<chair-hat-off>

>randomness for stub and full resolvers?

Good randomness should be used by all DNS resolvers on query ID.

For Recursive resolvers, some people (in particular Dr. Bernstein)
that advocate combining query ID and the use of different ports to
make it harder to forge replies, i.e. expanding the 16 bit protection the QID
provides. Recursive resolver that uses 8 different ports in random order, in
practice has a 19 bit QID.

RFC3833 discusses when Query ID offers protection and when it does not
contribute to data protection, if the attacker can see the outgoing query QID
contributes nothing.

<chair-hat-on>
Having a BCP on things to do for security/reliability by DNS resolvers
is a good thing. This includes query ID issues as well as the techniques
used to preventing cache poisoning and message integrity protection.
About 2 years ago I tried to get such a document written but it
never materialized.

Anyone willing and able to be an EDITOR for a document on this topic,
please contact me.

The word EDITOR is capitalized to emphasize the role of documenting the
existing practice and working group knowledge, rather than propose new things
or changes in protocol.

         Olafur

---

From: Jaap Akkerhuis <[email-masked]>
Date: Wed, 13 Jul 2005 08:44:21 +0200

<chair-hat-on>
    
<hard-hat-on>
Isn't dnsops a more appropriate WG?
</hard-hat-off>

	jaap

---

From: Ólafur Guðmundsson<[email-masked]>
Date: Fri, 15 Jul 2005 10:11:03 -0400

>Isn't dnsops a more appropriate WG?

<chair-hat-off>
Though call, but IMHO the cache poisoning documentation is clearly
in the protocol camp, random ID and port usage recommendation
can be in either group.

<chair-hat-on>
So far no person has stepped forward and expressed interest in working
on these items.
I take this as no one cares and the WG should not bother with this.

         Olafur (who by policy will not write ID for WG's he chairs)

---

From: Edward Lewis <[email-masked]>
Date: Mon, 25 Jul 2005 13:12:16 -0400

>Good randomness should be used by all DNS resolvers on query ID.

During some recent testing, I looked at the 
message ID's used by a popular and recent release 
of DNS software.  Over the time period I looked, 
some id numbers were used 6 times, a lot of the 
numbers were not.

Not all that random - without loss of 
functionality.  Although not random, the id 
numbers were somewhat unpredictable.  Well, come 
to think of it, no single id number ever had two 
simultaneously outstanding requests.  It's 
certainly not random, and you can predict that a 
number won't appear if it's outstanding.

I know that this is a dead issue in the WG 
(fortunately), but I had some real data to throw 
in.  And I wanted to kill once and for all the 
notion that the message id had to be "random."

---

From: David Conrad <[email-masked]>
Date: Mon, 25 Jul 2005 10:37:29 -0700

>> Good randomness should be used by all DNS resolvers on query ID.
...
> I know that this is a dead issue in the WG (fortunately), but I had  
> some real data to throw in.  And I wanted to kill once and for all  
> the notion that the message id had to be "random."

Hmm.  Perhaps this has been mentioned:

http://madchat.org/reseau/tcp-ip/tcpip-seqnb/#otherp

In terms of specification, I believe having query ids be as random as  
possible should be a MUST.  Anything else increases the likelihood of  
spoofability.

Rgds,
-drc

---

From: "The Purple Streak, Hilarie Orman" <[email-masked]>
Date: Mon, 25 Jul 2005 12:02:34 -0600

> some id numbers were used 6 times, a lot of the 

That's consistent with randomness.  You should mention the sample
size, though.  It couldn't have been more than 6*2^16, for example.

The restriction to choose from the set of unused numbers should be
mentioned explicitly in requirements ("drawing without replacement"),
that will smooth out the distribution as the number of ids in
use at any given time increases.

Hilarie

---

From: Doug Barton <[email-masked]>
Date: Mon, 25 Jul 2005 16:02:50 -0700

> use at any given time increases.

Would "drawing without replacement up to 1/N of the space" be better, for 
the right value of N?

Doug

-- 

	If you're never wrong, you're not trying hard enough