Shadowsocks-libev: `udns` stub resolver vulnerable to DNS spoofing attacks

[cpu]

Hi folks :wave:,

I spent some time over the past two weeks fiddling with shadowsocks-libev and the udns stub resolver it links in order to determine how viable it is to perform DNS spoofing attacks against a shadowsocks-libev server. My detailed findings are below. I apologize for the volume of text but I wanted to make this as concrete as possible to reduce the chance that the claims are dismissed as unrealistic. If interested I can provide more information about the experimental setup that I used to prove the viability of this against a mock server. For now I've stuck to findings.

I apologize for not accompanying this with a pull request but my ability to write production quality C is fairly limited and I suspect replacing udns will be a more involved job.

Summary

The stub resolver that shadowsocks-libev uses, udns, has made several design decisions that introduce increased vulnerability to DNS spoofing attacks on the shadowsocks server. Further, udns does not implement protocol features key to modern DNS making the shadowsocks server fragile and holding back protocol advancement. The udns author intends for it to be used exclusively in LAN environments where a trusted recursive resolver is nearby, likely making it a bad fit for most shadowsocks-libev deployments.

Recommendation

The shadowsocks-libev codebase should migrate to a better supported stub resolver such as c-ares or ldns. Both projects randomize the UDP source port on a per-query basis and generate transaction IDs using a more robust design than udns. Similarly both projects support TCP and handle truncated replies correctly.

Detailed Explanation

The shortcomings of udns fall into two categories: robustness & security. Universally my findings and descriptions pertain to udns 0.4, the most current release from three years ago, 2014-01-23.

From a robustness perspective, udns has made design choices that simplify the API but ignore real world protocol considerations that other stub resolvers handle with more care:

1. udns only supports UDP. Where EDNS-0 is not supported to negotiate larger UDP response packets all replies must fit within 512 bytes.
2. where replies are larger and returned with the truncated (TC) bit set, udns treats the response as an error
3. if there is an error in recvfrom in reading the response, udns does not retry the query and it fails silently.

From a security perspective, udns has made two design choices that greatly increase the server's vulnerability to DNS spoofing:

1. by design udns uses one UDP socket for all queries. The port is selected randomly by the OS but remains static across all queries made.
2. udns uses a PRNG (not a CSRNG) to generate random transaction IDs, and by default on UNIX systems it is seeded with the number of microseconds since epoch, meaning there are only one million possible seeds.

Issue 1 - Static UDP source port

We can see the first security issue in action with a live shadowsocks-libev server by first using tshark to capture DNS traffic:

 tshark -i any -w /tmp/dns.test.cap 'udp port 53'

and then by pulling out the UDP source port, query ID and query name from the packet dump:

 tshark -r /tmp/dns.test.cap -Y "ip.src == $SERVER_IP" -e udp.srcport -e dns.id -e dns.qry.name -T fields | sort

Make sure $SERVER_IP is the public IP of your shadowsocks server. If there are Shadowsocks clients active you will see all of their DNS queries are sourced from the same port #, in this case 33630:

33630   0x00000178  images.mentalfloss.com
33630   0x000001a3  www.google.com
33630   0x000002f0  fonts.gstatic.com
33630   0x0000046a  assets-cdn.github.com
33630   0x00000626  images.mentalfloss.com
33630   0x0000065a  images.mentalfloss.com
33630   0x00000756  cdn.static-economist.com
33630   0x000008fa  csync.yahooapis.com
33630   0x000008fa  js-sec.indexww.com
33630   0x00000b08  assets-cdn.github.com
33630   0x00000bd1  www.cbc.ca
33630   0x00000c8e  cdn.static-economist.com
<snipped>

Using a random source port has been best practice since 2008 when the "Kaminski attack" was in the news. It's also considered a best practice as part of RFC 5452, "Measures for Making DNS More Resilient against Forged Answers". Section "9.2. Extending the Q-ID Space by Using Ports and Addresses" describes using a random source port as a MUST. Without using a random source port an attacker intending to spoof a response to a query only needs to guess the transaction ID of the query. In practice I found that if a server repeatedly queried a name I was able to spoof a response successfully in under a minute from a host in the same datacentre by randomly guessing transaction IDs.

The author of udns is aware of the security implications of this design and says the following in the NOTES file:

Ok, udns is a stub resolver, so it expects sorta friendly environment, but on LAN it's usually much easier to fire an attack, due to the speed of local network, where a bad guy can generate alot of packets in a short time.

and:

Udns is designed to work in a LAN, it needs full recursive resolver nearby, and modern LAN usually uses high-bandwidth equipment which makes the Kaminsky attack trivial. The problem is that even with qID (16 bits) and random UDP port (about 20 bits available to a regular process) combined still can not hold enough randomness, so on a fast network it is still easy to flood the target with fake replies and hit the "right" reply before real reply comes. So random qIDs don't add much protection anyway,
even if this feature is implemented in udns, and using all available techniques wont solve it either.

I think this position is unique to the udns author. All other stub resolvers and recursive resolvers I've looked at do randomize the source port. Further, in the case of shadowsocks-libev it seems unwise to make assumptions that the datacenter the server is located in is a friendly LAN. Second, I believe common deployment practice will be to run shadowsocks-libev on a server that has no local recursive resolver and instead sets /etc/resolv.conf to 8.8.8.8 or equivalent, a recursive resolver that may not be nearby at all and greatly increases the chances an attacker nearby could race the responses from the real server successfully.

As we'll see next the method that udns uses to generate random transaction IDs is also lacking, further exacerbating the impact of using a static source port.

Issue 2 - Transaction ID PRNG weak, seeded unsafely

udns generates transaction IDs using a PRNG based on smallprng by Bob Jenkins.

This is a small fast pseudorandom number generator, suitable for large statistical calculations, but not of cryptographic quality

The udns implementation is located in src/udns_jran.c. The PRNG is initialized in src/udns_resolver.c's dns_init_rng() function (beginning on L413). It invokes the udns_jraninit function of udns_jran.c providing it the return value of dns_nonrandom_32 as the seed.

The implementation of dns_nonrandom_32 is as follows:

static unsigned dns_nonrandom_32(void) {                                                       
#ifdef WINDOWS                                                                           
  FILETIME ft;                                                                           
  GetSystemTimeAsFileTime(&ft);                                                          
  return ft.dwLowDateTime;                                                               
#else                                                                                    
  struct timeval tv;                                                                     
  gettimeofday(&tv, NULL);                                                               
  return tv.tv_usec;                                                                     
#endif                                                                                   
}                                                                                    

On a non-Windows system this means that ultimately udns_jraninit is given a seed value of timeval.tv_usec. The timeval struct and the tv_usec field are described in the man page for gettimeofday:

           struct timeval {
               time_t      tv_sec;     /* seconds */
               suseconds_t tv_usec;    /* microseconds */
           };

This means that the udns prng is only ever initialized with one of 1,000,000 possible seeds. A value of more than 1,000,000 would not be a microsecond and would reset tv_usec to 0 while incrementing tv_sec. This is an unsuitably small search space.

Further, since udns uses a PRNG not a CSRNG it is not designed to resist next-bit attacks or state compromise. In practice I found that if I could learn any two query transaction IDs from a running udns stub (not necessarily two immediately subsequent transaction IDs) I could brute force the seed that the server used within seconds using an unoptimized C program. I don't believe there is an easy way to learn transaction IDs without being on the network path but it will be catastrophic to the TX ID security if two are leaked.

Once the seed is known the attacker is able to guess transaction IDs for future queries with great accuracy. Combined with knowing the static source port the adversary could spoof DNS responses reliably using many, many fewer UDP guess packets.

In comparison c-ares generates a random RC4 key using the system randomness devices resulting in a construction that is safer to state leaks & initialized with a much larger seed space. Similarly ldns uses OpenSSL RAND_bytes to generate cryptographically secure pseudo-random data for transaction IDs.

Countermeasures/Practical Experience

One counter measure that udns properly implements is enforcing that the source IP address of the UDP packets it receives matches the IP address of the recursive resolver the question was sent to. This means that attacking the udns stub resolver requires spoofing source IP addresses. This is certainly possible but requires finding a host/environment that doesn't use the best practices from BCP-38.

RFC 5452 Section 4.4 "Matching the Source Address of the Authentic Response" says:

While two Best Current Practice documents ([RFC2827] and [RFC3013] specifically) direct Internet access providers to prevent their customers from assuming IP addresses that are not assigned to them, these recommendations are not universally (nor even widely) implemented.

I don't believe this countermeasure alone (e.g. without stronger TX ID generation and random source ports) is sufficient to protect the shadowsocks-libev queries from spoofing.

In practice I found that udns in the most verbose configuration did not print any logs when receiving UDP packets with DNS responses that had an incorrect transaction ID. This meant that when guessing transaction IDs incorrectly the attacker is able to retain relative obscurity. The system administrator would have to be looking at the UDP traffic at a layer other than the shadowsocks-libev/udns logs to notice something amiss.

The primary countermeasure that helps this from being a more serious issue is the lack of caching in both udns and shadowsocks-libev. In practice this means that unlike when targetting a recursive resolver the traditional "cache poisoning" attacks do not work. The attacker instead has to poison on a per-query basis which raises the bar significantly. That said, I believe targetting a high-traffic shadowsocks-libev server and a specific high-value, high-traffic domain would be feasible. Certainly feasible if the attacker is able to observe transaction IDs and learn the server's PRNG seed.

[wongsyrone]

Thanks for the information

[wongsyrone]

I would recommend c-ares over ldns since it requires fewer dependencies.

[madeye]

As mentioned in your title, udns works as a stub resolver. It means it's recommended to use udns with a local or nearby recursive resolver if you'd like to improve the "security".

Please find more details here: http://www.corpit.ru/mjt/udns.html

Please note the library is a stub resolver, it is aimed at client programs that uses nearby recursive resolver such as BIND or dnscache from djbdns package or similar. It plays the same role as standard stub resolver from libresolv, and it requires reqursive DNS server.

[cpu]

@madeye Yes, I'm familiar with the author's position. I quoted it in my issue and disagree with that perspective. The other major stub resolvers generate transaction IDs in a stronger way and also randomize the source port. Why is only udns the outlier?

It means it's recommended to use udns with a local or nearby recursive resolver

Do you believe most users deploy shadowsocks-libev in this fashion? Is there any documentation to suggest it's required to help prevent DNS spoofing?

[madeye]

It's a design choice of shadowsocks-libev, as we share the same design object with udns to improve the performance as much as possible as well as keep our implementation as simple as possible.

Actually, even with dynamic UDP ports or strong transaction IDs, DNS spoofing issue still exists, unless DNSSEC or similar protocols are used. In other words, for additional DNS security, a local secure DNS resolver is also required.

IMO, most users of shadowsocks-libev won't have issues with DNS spoofing, as they deploy the service on public cloud, which should use the local resolver setup by the service provider.

[madeye]

BTW, any pull request of adding support of c-ares is still welcome, if anyone really thinks it's necessary.

[wongsyrone]

Found two examples for ppl who want to implement this.

https://gist.github.com/mopemope/992777
https://gist.github.com/Mons/6659163

[cpu]

Actually, even with dynamic UDP ports or strong transaction IDs, DNS spoofing issue still exists, unless DNSSEC or similar protocols are used. In other words, for additional DNS security, a local secure DNS resolver is also required.

Yes, to completely stop DNS spoofing you're correct. Again, all other stub resolvers & RFC5452 agree that randomizing just the transaction ID makes it much easier. Just because something is still possible in a textbook setting when applying the best practice defenses doesn't mean it's worth skipping those defenses. Especially, as I pointed out, when the primary defense (random transaction IDs) is implemented poorly in udns. It _may_ be possible to spoof DNS to other hardened stub resolvers in some settings. It's _definitely_ possible to spoof responses to udns in a variety of real world settings.

It's a design choice of shadowsocks-libev, as we share the same design object with udns to improve the performance as much as possible as well as keep our implementation as simple as possible.

I'm disappointed to hear that. I don't believe using c-ares or ldns would cause performance overhead or significantly complicate the codebase. It seems like the status quo and an argument about performance without data is causing the project to open itself up to unnecessary weakness to DNS spoofing.

Since I'm not in a position to do the work required to change stub resolvers and you seem to disagree with the premise that these are problems specific to udns and not stub resolvers in general I won't press the matter further. Thanks for reviewing.

[wongsyrone]

@cpu

Good news. C-Ares is now in the master branch.

[debiansid]

@wongsyrone will you merge it into simple-obfs too?

[wongsyrone]

ask @madeye

[debiansid]

@madeye coz 703n just has limited rom, i’d Like see it in simple-obfs. Thanks

[cpu]

@wongsyrone @madeye That's great! Thank you both for your hard work. I know this was a non-trivial change and I want to make sure you know it's appreciated :-)