> Given the extremely small amount of space for randomization (16-bit > query ID's) does a cryptographically strong PRNG really make > difference? For a couple of decades the original algorithm was simply id++. Yes, it makes a difference to use a slightly more sophisticated and essentially "resource-free" algorithm, at least against some of the potential "attacks". Not all attacks stand on their own. The ID behaviour is typically part of the problem space that an attacker has to deal with when some other DNS problem is being attacked. The main problem space people are talking regards DNS servers. But the same (or similar) algorithm can also be used in resolver libraries (ie. inside libc) to deal with other (different or similar...) potential "attacks". The algorithmic complexity of going from id++ to something more sophisticated places no great burden on anyone... the machines can handle it... so why not just do it. We don't need an uber-secure PRNG.... since it is only a 16 bit exposed space. But it is good if it has a few other "characteristics". > Aside from stopping an easy prediction, doesn't it just generate a > little extra work for a determined malicious individual? The worst case for the attacker requires 65536 responses instead of 1. Some style of attacks can require less. If the computation / network costs of predicting a 16-bit PRNG is higher than the cost of simply slamming with 65536 packets, attackers will use the latter method. But there are always mitigating factors... Maybe an attacker can't generate that much traffic, or maybe he doesn't want to because he can be spotted.. etc. There are other factors that select against doing DNS attacks like this, such as the various any-cast architecture some servers are setup with. It _is_ a 16 bit ID space, and that is not fixable inside the strict DNS protocol, but that still leaves us room to do the best job with what we have, rather than do nothing at all. Some people appear to be on the edge of arguing that we do nothing. > Seems to be a moot point to me---whether the PRNG is > cryptographically weak or not because of the small sequence number > space. Around 10 years ago the PRNG used was id++. I still think that the algorithm we invented as a group with Niels Provos, David Mazieres, some researchers at Core SDI, and further improved by David Wagner is better than what ISC is shipping. We've been using our algorithm for 10+ years, too. Not just for DNS ID's but also for the related problem of IP ID's. Every packet our machines generate hits the same algorithm, to help a bit with the IP ID ++ issues. Relative to the new ISC code... ours is not worse. But it is simpler, and non-heuristical in nature. It is just plainly mathematical, designed by math nerds who we asked to help. And it is a lot less code to do the same thing. But perhaps it doesn't matter that much. At least we are not back in the days of id++ on all systems. Though I suspect there are still lots of DNS libraries and other similar subsystems.........
