User: Password:
Subscribe / Log in / New account

Secrecy and the DNS flaw

Secrecy and the DNS flaw

Posted Jul 11, 2008 0:12 UTC (Fri) by njs (guest, #40338)
In reply to: Secrecy and the DNS flaw by copsewood
Parent article: Secrecy and the DNS flaw

It seems unlikely that the problem is really a PRNG flaw, because we know how to build good
PRNGs.  Not every implementation might *use* such a PRNG, but if it were a PRNG flaw then it
would only affect those implementations that were using poor PRNGs, not every implementation.

(Log in to post comments)

Secrecy and the DNS flaw

Posted Jul 12, 2008 10:32 UTC (Sat) by copsewood (subscriber, #199) [Link]

What do you mean by a "good" PRNG ? I think what we understand to be good here might have to
change. It's one thing for a PRNG to generate a sequence of numbers with good statistical
properties and which doesn't repeat its inherently predictable sequence until a very large
integer number space is exhausted. It's entirely another to have a PRNG with a published
algorithm and an attacker able to obtain prior information relevant to its internal state but
provably unable to predict the subsequent sequence of numbers generated. The P here means
pseudo, because the randomness isn't randomness at all - it means that the sequence of numbers
is generated using an algorithm and not a noise source. Certainly the developer and
administrator can attempt to reseed such an algorithm periodically and cryptically. The issue
is how much can an attacker learn by knowing previous numbers in the sequence in order to
predict subsequent numbers in the sequence.

One solution for the paranoid is to use /dev/random instead of /dev/urandom as the entropy
source. This is a good idea when generating cryptographic keys intended for medium-long term
use, but running a DNS recursive resolving server which needs to generate thousands of
unpredictable source port numbers and transaction IDs a second is going to need a faster
entropy source than /dev/random hence the need for a PRNG in the first place.

Secrecy and the DNS flaw

Posted Jul 12, 2008 20:56 UTC (Sat) by njs (guest, #40338) [Link]

Indeed, the study of PRNGs splits into two parts: scientific PRNGs, where the emphasis is on
provable uniformity, provably large period, and speed, versus cryptographic PRNGs, where the
emphasis is on resistance to prediction, judicious incorporation of true entropy, and speed.
As you suggest, since DNS port randomization is effectively using the source port as part of a
secret key, it's important that the the source ports be generated by a cryptographic PRNG.

Fortunately, these days we can build very good PRNGs of both types.  For cPRNGs, the
constructions usually involve using some other crypto algorithm as part of the generation
process (e.g., a strong hash or cipher like SHA-256 or AES).  This is exactly what /dev/random
and /dev/urandom do, and it's what good-quality DNS server implementations will do too.  In
practice, attacking such a PRNG is about as easy as inverting SHA or AES -- not gonna happen.
(And yes, I know that SHA-1 has been recently weakened.)

If you want to know more about these issues, then I can recommend Schneier's paper on
yarrow[1] for a great discussion of the issues faced by such a design, and [2] for a fun and
famous discussion of exploiting such flaws in TCP sequence numbers (with pretty pictures!).


Secrecy and the DNS flaw

Posted Jul 17, 2008 10:29 UTC (Thu) by copsewood (subscriber, #199) [Link]

Thanks for these links which are very interesting.

Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds