Today we released MS08-020 to address a weakness in the Transaction ID (TXID) generation algorithm in the DNS client resolver. The TXID is a 16-bit entity that is primarily used as a synchronization mechanism between DNS servers/clients; in fact, you can think of it as an Initial Sequence Number (ISN) for DNS query/response exchanges. Consequently, the TXID is intended to be somewhat random and difficult to predict. If both the TXID and hostname are predictable, an attacker can forge malicious DNS replies which the DNS client resolver will believe to be from the legitimate DNS server. The client would then use the spoofed information to make an outbound connection to a (potentially) attacker-controlled IP.
We wanted to explain a little more about the weakness to help you recognize potential attacks on the wire. Remember that an attacker needs to match the request TXID exactly in the spoofed response before the legitimate DNS server replies with a valid response. This was facilitated by our previous implementation of this PRNG algorithm being weak and hence vulnerable to prediction attacks. Given the previous consecutive TIDs, x_n, x_{n+1}, x_{n+2}, the attacker may be able to determine the PRNG state and predict x_{n+3}, x_{n+4}, … with a high degree of confidence. The old TXID generation algorithm was as follows (revised pseudo-code for technical accuracy):
<font face="Courier New"> GlobalSeed++;<br> </font><font face="Courier New">SomeNumber = (WORD)GetTickCount()+(SomeRandomAddress>>6)+GlobalSeed;<br> </font><font face="Courier New">SomeNumber = (SomeNumber%487)+1+GlobalLastTXID);<br> </font><font face="Courier New">GlobalLastTXID = SomeNumber;<br> </font><font face="Courier New">XID = SomeNumber^XIDMask;</font>
Below is a log of sequential TXID’s sent from the old client resolver. Notice the predictable patterns that develop in bit positions 4,5,6,7 and 8.
As you can see, attackers cannot predict a guaranteed, known-next TXID exactly even with this weakness. But limited entropy in those middle bits does cut down the search space substantially to predict the next TXID. If you are watching for attacks on the wire, continue to look for the same pattern as previous DNS spoofing attacks: a steady flood of DNS “replies” with thousands of different TXID’s targeting a client lookup for a single host.
To address this weakness, we simply replaced the algorithm with a cryptographically secure PRNG: CryptGenRandom(). You can read about how it works at http://msdn2.microsoft.com/en-us/library/aa379942(VS.85).aspx.
Blog Update - April 29: Revised pseudo code above for technical accuracy.
- Security Vulnerability Research & Defense Bloggers
*Postings are provided “AS IS” with no warranties, and confers no rights.*