Re: On the unpredictability of DNS
It seems like enough time has passed to post publicly, as some of these are now common knowledge: Ben Laurie wrote: William Allen Simpson wrote: Keep in mind that the likely unpredictability is about 2**24. In many or most cases, that will be implementation limited to 2**18 or less. Why? Remember, this is the sum of the range of the 16-bit DNS header identifier and the 16-bit UDP port number. The theoretical maximum is less than 2**(16+16), as the ports less than 4096 are reserved. Many or most implementations use only a pool of ports: 2**[9, 10, 12] have been reported. Some implementations (incorrectly) use positive signed integers for the DNS identifier: 2**15. And in this week's Hall of Shame, MacOSX Leopard patch for servers seems to randomize the BIND request port in a small pool. The next UDP packet ports are sequential, so the range to guess is very small, simply by looking at the following UDP packets. Very strange reports coming out! MacOSX total: about 2**18. Worse, Apple didn't fix Leopard clients, didn't patch the stub resolver library (neither did BIND), didn't patch earlier versions such as Panther. Many, many MacOS systems are still vulnerable. And in case you don't think this matters, once upon a time I helped build an ISP entirely with Macs, resistant to most compromises. There are far more Macs used as resolvers than any other flavor of *nix. I don't see why. A perfectly reasonable threat is that the attacker reverse engineers the PRNG (or just checks out the source). It doesn't need to be common to be predictable. I don't understand this comment. When MD5 is used as a PRNG, in this case the upper 32-bits of its 128-bit output cycle, what amount of samples will reveal the seed, or the current internal state of the sequence? When ARC4 is used as PRNG, what amount of samples will reveal the seed or the current state? Are you only referring to reverse engineering trivially poor PRNG? - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the unpredictability of DNS
William Allen Simpson wrote: I've changed the subject. Some of my own rants are about mathematical cryptographers that are looking for the perfect solution, instead of practical security solution. Always think about the threat first! In this threat environment, the attacker is unlikely to have perfect knowledge of the sequence. Shared resolvers are the most critical vulnerability, but the attacker isn't necessarily in the packet path, and cannot discern more than a few scattered numbers in the sequence. The more sharing (and greater impact), the more sparse the information. In any case, the only perfect solution is DNS-security. Over many years, I've given *many* lectures to local university, network, and commercial institutions about the need to upgrade and secure our zones. But the standards kept changing, and the roots and TLDs were not secured. Now, the lack of collective attention to known security problems has bitten us collectively. Never-the-less, with rephrasing, Ben has some good points I don't see any actual rephrasing below, unless you are suggesting I should have said unpredictable instead of random. I think that's a perfectly fine substitution to make. Ben Laurie wrote: But just how GREAT is that, really? Well, we don't know. Why? Because there isn't actually a way test for randomness. ... While randomness is sufficient for perfect unpredictability, it isn't necessary in this threat environment. I agree, but my point is unaltered if you switch randomness to unpredictability. Keep in mind that the likely unpredictability is about 2**24. In many or most cases, that will be implementation limited to 2**18 or less. Why? Your DNS resolver could be using some easily predicted random number generator like, say, a linear congruential one, as is common in the rand() library function, but DNS-OARC would still say it was GREAT. In this threat environment, a better test would be for determination of a possible seed for any of several common PRNG. Or lack of PRNG. I don't see why. A perfectly reasonable threat is that the attacker reverse engineers the PRNG (or just checks out the source). It doesn't need to be common to be predictable. Oh, and I should say that number of ports and standard deviation are not a GREAT way to test for randomness. For example, the sequence 1000, 2000, ..., 27000 has 27 ports and a standard deviation of over 7500, which looks pretty GREAT to me. But not very random. Again, the question is not randomness, but unpredictability. Again, changing the words does not alter my point in any way, though I do agree that unpredictable is a better word. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.links.org/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the unpredictability of DNS
I've changed the subject. Some of my own rants are about mathematical cryptographers that are looking for the perfect solution, instead of practical security solution. Always think about the threat first! In this threat environment, the attacker is unlikely to have perfect knowledge of the sequence. Shared resolvers are the most critical vulnerability, but the attacker isn't necessarily in the packet path, and cannot discern more than a few scattered numbers in the sequence. The more sharing (and greater impact), the more sparse the information. In any case, the only perfect solution is DNS-security. Over many years, I've given *many* lectures to local university, network, and commercial institutions about the need to upgrade and secure our zones. But the standards kept changing, and the roots and TLDs were not secured. Now, the lack of collective attention to known security problems has bitten us collectively. Never-the-less, with rephrasing, Ben has some good points Ben Laurie wrote: But just how GREAT is that, really? Well, we don't know. Why? Because there isn't actually a way test for randomness. ... While randomness is sufficient for perfect unpredictability, it isn't necessary in this threat environment. Keep in mind that the likely unpredictability is about 2**24. In many or most cases, that will be implementation limited to 2**18 or less. Your DNS resolver could be using some easily predicted random number generator like, say, a linear congruential one, as is common in the rand() library function, but DNS-OARC would still say it was GREAT. In this threat environment, a better test would be for determination of a possible seed for any of several common PRNG. Or lack of PRNG. How many samples would be needed? That's the mathematical limitation. Is it less than 2**9 (birthday attack on 2**18)? It is an issue because of NAT. If your resolver lives behind NAT (which is probably way more common since this alert, as many people's reactions [mine included] was to stop using their ISP's nameservers and stand up their own to resolve directly for them) and the NAT is doing source port translation (quite likely), then you are relying on the NAT gateway to provide your randomness. But random ports are not the best strategy for NAT. They want to avoid re-using ports too soon, so they tend to use an LRU queue instead. Pretty clearly an LRU queue can be probed and manipulated into predictability. Agreed! All my tests of locally accessible NATs (D-Link and Linksys) show that the sequence is fairly predictable. And no code updates available Incidentally, I'm curious how much this has impacted the DNS infrastructure in terms of traffic - anyone out there got some statistics? Some are coming in on another private security list where I and some others here are vetted, but everything is very preliminary. In addition to the publicized attacks on major ISP infrastructure, there are verified scans and attacks against end user home NATs. Oh, and I should say that number of ports and standard deviation are not a GREAT way to test for randomness. For example, the sequence 1000, 2000, ..., 27000 has 27 ports and a standard deviation of over 7500, which looks pretty GREAT to me. But not very random. Again, the question is not randomness, but unpredictability. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
