PaperlayerView exact revision on arXiv

Source-linked AI summary

Encrypted DNS --> Privacy? A Traffic Analysis Perspective

Sandra Siby, Marc Juarez, Claudia Diaz, Narseo Vallina-Rodriguez, Carmela Troncoso

arXiv:1906.09682v3cs.CR

TL;DR

The paper asks whether encrypted DNS protects browsing activity from traffic analysis. It develops DNS-specific features to identify visited pages and evaluates defenses and censorship. The attacks can be as accurate as web-traffic fingerprinting with much less data, and the tested defenses differ in effectiveness.

  • Problem

    Existing DoH evaluations focused on performance and cost, leaving the effectiveness of traffic analysis in revealing browsing patterns from encrypted DNS unexamined.

    Source: §I · p. 1

  • Method

    The authors develop DNS-specific traffic features and evaluate fingerprinting, environmental variation, standardized padding, Tor, and censorship on encrypted DNS.

    Source: §I · pp. 1–2

  • Results

    DoH fingerprinting achieves the same accuracy as encrypted-web fingerprinting while requiring 124 times less data.

    Source: §I · pp. 1–2

  • Takeaways & Limitations

    Encrypted DNS remains vulnerable to traffic-analysis censorship; padding may not fully prevent attacks unless overhead is large, while Tor is an extremely effective defense for encrypted-DNS fingerprinting.

    Source: §I · pp. 1–2

Abstract

from arXiv · show

Virtually every connection to an Internet service is preceded by a DNS lookup which is performed without any traffic-level protection, thus enabling manipulation, redirection, surveillance, and censorship. To address these issues, large organizations such as Google and Cloudflare are deploying recently standardized protocols that encrypt DNS traffic between end users and recursive resolvers such as DNS-over-TLS (DoT) and DNS-over-HTTPS (DoH). In this paper, we examine whether encrypting DNS traffic can protect users from traffic analysis-based monitoring and censoring. We propose a novel feature set to perform the attacks, as those used to attack HTTPS or Tor traffic are not suitable for DNS' characteristics. We show that traffic analysis enables the identification of domains with high accuracy in closed and open world settings, using 124 times less data than attacks on HTTPS flows. We find that factors such as location, resolver, platform, or client do mitigate the attacks performance but they are far from completely stopping them. Our results indicate that DNS-based censorship is still possible on encrypted DNS traffic. In fact, we demonstrate that the standardized padding schemes are not effective. Yet, Tor -- which does not effectively mitigate traffic analysis attacks on web traffic -- is a good defense against DoH traffic analysis.

I. INTRODUCTION

The paper tests whether traffic analysis can identify browsing activity despite encrypted DNS, developing DNS-specific features and evaluating attacks, defenses, and censorship. It finds that encryption alone does not prevent these attacks, though routing DoH over Tor is effective.

I. INTRODUCTION

  • Differences in location, client application, platform, or resolver between training and deployment reduce attack performance, but environment inference can help tailor attacks.The authors report maintaining high attack performance for each specific environment when the attack is tailored accordingly.Source: §I · p. 1
  • Standardized EDNS0 padding cannot completely prevent attacks unless its overhead is large, whereas Tor is an extremely effective defense against encrypted-DNS fingerprinting.The paper evaluates EDNS0 padding and Tor as transport for encrypted DNS.Source: §I · pp. 1–2
  • Censors can identify the packet carrying the first domain lookup and, to reduce collateral damage, wait for an average of 15% of encrypted DNS traces before blocking.Blocking the response to the first lookup can prevent the user from seeing any content.Source: §I · p. 2
  • Traditional web-traffic features are unsuitable for encrypted DNS, so the authors develop a feature set focused on local traffic characteristics.Encrypted DNS is bursty, chatty, and mostly composed of small packets.Source: §I · pp. 1–2
  • DoH fingerprinting achieves the same accuracy as encrypted-web fingerprinting while requiring 124 times less data.The authors also report their feature set is as effective or more effective than state-of-the-art attacks on web traffic.Source: §I · pp. 1–2
  • The paper gathers the first dataset of encrypted DNS traffic across a wide range of environments.After responsible disclosure of the attacks, Cloudflare changed its DoH resolver to include padding.Source: §I · p. 2

II. BACKGROUND AND RELATED WORK

This section explains DNS resolution and encrypted DNS protocols, reviews prior DNS privacy work, and defines the paper’s threat model. It studies whether an observer of encrypted DNS traffic can infer the websites a user visits.

II. BACKGROUND AND RELATED WORK

  • DNS resolution maps a domain name to an IP address through a recursive resolver, which contacts authoritative servers when the answer is not cached.The client then uses the resolved IP address to connect to the destination host.Source: §II · p. 2
  • DoT carries DNS queries and responses over an encrypted TLS session, while DoH encodes queries in HTTPS requests and can use existing HTTPS connections.DoT uses a dedicated TCP port; DoH can also use HTTP/2 Server Push to send likely DNS responses preemptively.Source: §II · p. 2
  • DNS privacy work has examined encryption and tracking, but prior studies either lacked experiments on encrypted DNS or did not consider encryption.Privacy leaks between recursive and authoritative resolvers are outside this study’s scope because DoH does not protect that traffic.Source: §II · p. 3

III. PROBLEM STATEMENT

  • The central question is whether an observer of encrypted DNS traffic can infer which websites a user visits.The paper notes that such inferences may interest entities conducting usage statistics, malicious-activity detection, surveillance, or censorship.Source: §III · p. 3
  • The adversary may observe traffic between the user and recursive resolver without being on the path between the user and destination host.The model includes observers who see only DoH traffic and can link lookups to an origin IP address.Source: §III · p. 3
  • A DoH trace includes the first-party domain lookup and subsequent lookups for page resources; monitoring uses full traces, while censorship acts on partial traces.The two goals differ because monitoring can wait to collect full traces, whereas censorship must identify a requested domain quickly enough to interrupt communication.Source: §III · p. 3

IV. DATA COLLECTION

The study collected encrypted DNS traces across website, client, resolver, location, and platform conditions, then curated the data to reduce errors unrelated to DNS traffic. It defines DNS fingerprinting as identifying a webpage from its encrypted DNS trace using traffic analysis.

IV. DATA COLLECTION

  • 1,500 webpages from Alexa’s top, middle, and bottom 500 were sampled, with up to 200 traces per page and 5,000 additional webpages for open-world analysis.Collection used two separate periods; data from them was never mixed.Source: §IV · p. 3
  • Datasets varied client, resolver, location, platform, and defenses; DoT data lacked an unpadded Cloudflare condition because padding was already implemented.Unless otherwise specified, the experiments used Cloudflare’s DoH client.Source: §IV · pp. 3–4
  • Curation removed collection errors and website behaviors that could create classification errors unrelated to DNS traffic, including redirects and identical traces.HTTP status and request-response checks identified conflicting or invalid webpages.Source: §IV · p. 4

V. DNS-BASED WEBSITE FINGERPRINTING

  • DNS fingerprinting is traffic analysis that identifies the webpage responsible for an encrypted DNS trace, based on the order of DNS queries generated by loaded resources.The paper distinguishes this from traditional website fingerprinting on HTTPS traffic.Source: §V · p. 4

A. DNS fingerprinting

The paper frames DNS fingerprinting as supervised classification and introduces local sequence features tailored to encrypted DNS traffic. Its evaluation finds these features effective across closed- and open-world settings, while showing that the traces require substantially less data than web traffic attacks.

A. DNS fingerprinting

  • DNS fingerprinting uses labeled encrypted traces to train a classifier that identifies visited pages; evaluation uses precision, recall, and F1-score in closed- and open-world settings.The classifier is a Random Forest, evaluated with 10-fold cross-validation.Source: A. DNS fingerprinting · pp. 4–5
  • Traditional aggregate traffic features are inadequate for chatty, small-packet DNS traces; their performance drops by 20% on DoH traces.The paper attributes the mismatch to DNS responses being smaller and chattier than web resources.Source: A. DNS fingerprinting · p. 5
  • N-grams count consecutive signed TLS-record lengths, capturing request-response size patterns and local packet order; burst n-grams aggregate consecutive records in one direction.The experiments concatenate unigrams and bigrams of record sizes and bursts; trigrams add marginal improvement at substantial memory cost, while timing is unreliable.Source: A. DNS fingerprinting · p. 5

B. Evaluating n-grams features

  • Per-class results vary: some pages have high recall but low precision, while others have low recall but high precision, creating different false-positive risks.The figure colors each class by the absolute Precision–Recall difference, from low (blue) to high (red).Source: Figure 2 · p. 6, B. Evaluating n-grams features · p. 6
  • At t = 0.8, open-world monitored-class F1-score is ≈ 0.7, with the threshold varied from 0 to 0.99.The figure presents a precision–recall ROC curve for the monitored class.Source: Figure 3 · p. 6, B. Evaluating n-grams features · p. 6
  • On DNS traffic, n-grams improve performance by more than 10% over traditional features; isolated HTTPS attacks perform best, while DNS offers comparable results when only DNS is visible.When DoH and HTTPS share an inseparable tunnel, performance decreases, with n-grams offering a 10% improvement.Source: Table III · p. 7, B. Evaluating n-grams features · p. 7
  • After 20 samples per domain, additional samples bring diminishing returns; collecting 10 to 20 yields only a small increase in performance.The comparison with earlier Tor website-fingerprinting studies reports increases above 10% for 10 to 20 samples and 2% to 10% for 100 to 200 samples.Source: Table IV · p. 7, B. Evaluating n-grams features · p. 7
  • The WEB dataset’s HTTPS traces require 73GB, while the DoH-only dataset fits in 0.6GB.Individual web traces average 1.842 MB ± 2.620 MB, versus 0.012 MB ± 0.012 MB for corresponding DoH traces.Source: B. Evaluating n-grams features · p. 7

C. DNS Fingerprinting Robustness

The attack’s robustness varies across time, location, resolver, and platform: changes in these conditions can reduce classification performance, though continuous data collection can help maintain it. Feature differences help explain asymmetric cross-resolver results.

Robustness over time

  • F1-score drops by more than 10% when training and testing data are separated by eight weeks, while combining two- and three-week-old samples causes only a small decrease.The authors suggest continuous collection can maintain performance without periodic heavy collection efforts.Source: 1) Robustness over time · pp. 7–8

Robustness across locations

  • Cross-location F1-score decreases by 16%–27%, with the greatest drop for the farthest location, LOC3 in Asia.Precision and recall are asymmetric for some location pairs; the exact cause of the LOC2 network configuration effect remains open.Source: 2) Robustness across locations · p. 8

Robustness across infrastructure

  • Training and testing on the same resolver yields the best results, but cross-resolver performance is asymmetric: Google-trained classification on Cloudflare data reaches 13% F1-score.Important Google features are often missing or unimportant in Cloudflare, while only one top Cloudflare feature is missing in Google.Source: 3) Robustness across infrastructure · p. 8, Figure 4 · p. 8
  • Cross-platform classification falls to almost zero, but adding 8 bytes to Raspberry Pi TLS record sizes significantly improves cross-classification F1-score.Desktop TLS records average 7.8 bytes longer than Raspberry Pi records; performance still does not reach the base experiment’s level.Source: 3) Robustness across infrastructure · p. 8

Resolver GOOGLE CLOUD

Changing client setup can sharply reduce classification performance, while TLS record lengths can identify the resolver and client. Firefox traces also include additional DNS lookups beyond those related to the visited URL.

Platform

  • Cross-platform F1-scores are 0.614 when training on DESKTOP and testing on RPI, and 0.535 for the reverse direction.Source: Resolver GOOGLE CLOUD · p. 9

Client setup

  • Classifier performance drops dramatically across client setups and reaches zero when the browsers differ.The authors hypothesize that the decrease between CL-FF and LOC2 reflects differences between Firefox’s built-in and Cloudflare’s standalone DoH clients.Source: Resolver GOOGLE CLOUD · p. 9
  • Firefox traces are four times longer than Chrome’s and include lookups for OSCP servers, captive-portal detection, profiles, extensions, and other Mozilla servers.The authors conjecture Chrome makes similar requests, but believe the checks are fewer because its traces are shorter.Source: Resolver GOOGLE CLOUD · p. 9

Robustness analysis takeaways

  • TLS-record-length classifiers identify resolvers with 95% accuracy and clients with 100% accuracy.The authors conclude that an adversary needs a classifier for each targeted setting and must identify the victim’s configuration.Source: 4) Robustness Analysis Takeaways · p. 9

Client CLOUD CL-FF LOC2

Fingerprinting performance varies across websites and can weaken when the platform changes. Some sites consistently resist classification, while continuous sample collection can help keep training data current.

Platform

  • Desktops, laptops, and AWS servers show little platform-related difference, but accuracy drops when comparing a desktop with a constrained device such as a Raspberry Pi.Source: Client CLOUD CL-FF LOC2 · p. 9

Longitudinal analysis

  • Continuously collecting samples and incorporating them into the training set can keep up with DNS-trace changes at low cost.Source: Client CLOUD CL-FF LOC2 · p. 9

Survivors and Easy Preys

  • Up to 15% of websites have mean F1-score at or below 0.5, and more than 50% have mean F1-score at or below 0.7.The distribution is heavily skewed across websites’ mean F1-scores over all configurations.Source: Client CLOUD CL-FF LOC2 · p. 9, Figure 5 · p. 9
  • Google and sites that return errors appear among the consistent survivors, while low-F1 sites often have long domain names, few resources, and low apparent variability.The authors found no pattern in site structure or resource loads that explained other low-F1 survivors.Source: Client CLOUD CL-FF LOC2 · p. 9

VI. DNS DEFENSES AGAINST FINGERPRINTING

The paper evaluates padding, ad blocking, and Tor as defenses against encrypted-DNS fingerprinting, alongside their communication overhead. Padding does not stop the attack, whereas Tor provides strong protection for DoH and DoT performs better than DoH.

Countermeasures

  • The tested countermeasures include EDNS(0) padding, ad blocking, perfect padding, and DNS over Tor.The recommended EDNS(0) policy pads client requests to multiples of 128 bytes and resolver responses to multiples of 468 bytes.Source: §VI · pp. 9–10

Padding

  • EDNS0 padding at the recommended setting still yields an F1-score of 0.45, six orders of magnitude above random guessing; ad blocking helps as much as increased padding.Perfect padding would deter the attack, but at high communication cost.Source: Table VII · p. 10, §VI · p. 10

Communication overhead

  • EDNS0 padding incurs the least communication overhead but offers the least protection, while DNS over Tor has lower overhead than perfect padding.The overhead comparison measures total exchanged traffic volume with and without each countermeasure.Source: Figure 6 · p. 10, §VI · p. 10

DNS over Tor

  • Tor hides DNS-origin websites effectively because DNS lookups and responses fit in at most two Tor cells, leaving few observed TLS record sizes; length features add only 1% performance.Tor’s protection against DNS fingerprinting contrasts with its limited effectiveness against web-traffic analysis.Source: §VI · p. 10

Padding and Tor

  • Tor and perfect padding have similar protection, but their misclassifications form six and 12 clusters, respectively, leaving smaller effective anonymity sets than the full dataset.Source: §VI · p. 10

DoT comparison

  • DoT reduces F1-score by about 0.3 compared with DoH, and its traffic has less variance and is less unique.The record-size distributions are compared for 100 webpages; the encrypted flows prevent investigation of the underlying cause.Source: §VI · pp. 10–11, Figure 7 · p. 11

VII. CENSORSHIP ON ENCRYPTED DNS

The section considers traffic analysis as an alternative to blocking encrypted DNS resolvers, then measures how quickly partial DoH traces distinguish websites. Its findings connect early trace uniqueness to the location of the first-party DNS query.

VII. CENSORSHIP ON ENCRYPTED DNS

  • Because encryption prevents content-based lookup identification, a censor can use traffic analysis instead, but must identify a lookup early to stop content downloads.Blocking the resolver IP is another option, but can prevent users from browsing any web and may affect other services.Source: §VII · p. 11

A. Uniqueness of DoH traces

  • Conditional entropy H(W | S_l) measures how distinguishable websites are after observing l TLS records; zero means the sites are perfectly distinct.A trace is a sequence of TLS-record sizes, with positive values for client-to-resolver traffic and negative values for incoming traffic.Source: A. Uniqueness of DoH traces · p. 11
  • With 5,000 pages, conditional entropy falls below 1 bit after 15 packets, averaging 15% of a trace and making one domain more likely than all others combined.The first 15 packets can therefore identify a domain more confidently than a random choice between two domains.Source: A. Uniqueness of DoH traces · p. 11, Figure 8 · p. 11
  • The fourth TLS record often contains the first-party DoH query: its size distribution nearly matches domain-name lengths with a 51-byte HTTPS-header offset.Some queries appear earlier, consistent with the entropy decrease after the second packet.Source: A. Uniqueness of DoH traces · p. 12, Figure 9 · p. 12

B. Censor DNS-blocking strategy

The section evaluates blocking encrypted DNS using traffic-analysis inferences, weighing blocked content against collateral damage to other sites. It compares early blocking with waiting for higher-confidence identification and discusses the limits of the damage estimates.

B. Censor DNS-blocking strategy

  • Waiting until conditional entropy falls below one bit requires observing, on average, 15% of TLS records, allowing first-party content but leaving later queried domains vulnerable.Clients could use one connection per lookup to mix connections, but this increases traffic and could force a censor to block or throttle all DoH traffic from the user’s IP.Source: B. Censor DNS-blocking strategy · p. 12
  • Blocking on the first DoH response prevents access to any content, but also censors all domains with the same name length.In the five-country analysis, blocking domains of length 13 can block 97 domains while affecting 86,557 websites; worst-case collateral damage is at most 8.6% of the Alexa top 1M.Source: B. Censor DNS-blocking strategy · pp. 12–13
  • At most 51% of domains on the five countries’ Citizen Lab test lists appear in Alexa’s top 1M, indicating that likely censored domains are mostly not popular.The study uses the global Alexa ranking because country rankings were limited to 500 sites or unavailable, and treats the test lists as potential—not confirmed—censorship targets.Source: B. Censor DNS-blocking strategy · p. 12, Table VIII · p. 12
  • The minimum-collateral-damage strategy blocks domains of length 5, affecting 1,318 websites; its impact varies by country and Alexa rank.The maximum-gain and most-popular-site strategies block more websites, but their median rank is above 500,000; Figure 11 compares rank distributions across the three strategies.Source: B. Censor DNS-blocking strategy · pp. 12–13, Figure 11 · p. 13
  • The authors say further research should refine the analysis using large per-country rankings or exact lists of blacklisted domains.The conclusion characterizes blocking the first DoH query as aggressive but potentially affordable in terms of collateral damage.Source: B. Censor DNS-blocking strategy · p. 13

VIII. LOOKING AHEAD

The paper concludes that DNS encryption does not fully prevent monitoring or censorship, while Tor’s constant-size-cell repacketization offers the best practical protection examined. It proposes mimicking that repacketization without Tor’s rerouting and encryption, while noting that DoH leaves users exposed to resolvers themselves.

VIII. LOOKING AHEAD

  • Encrypting DNS does not completely prevent monitoring or censorship, and current padding strategies fall short against resourceful adversaries monitoring web activity.The conclusion says padding has potential to prevent censorship, but the analysis finds it insufficient to stop such monitoring.Source: §VIII · p. 13
  • Tor’s constant-size-cell repacketization provides the best practical protection examined, but adds bandwidth overhead and download time.The added download time comes from rerouting packets through the Tor network.Source: §VIII · p. 13
  • The authors propose that DoH clients mimic Tor’s repacketization without its encryption or rerouting, potentially improving the overhead–resistance trade-off.Reducing DNS header bits could help fit queries and responses into one constant-size packet with small overhead.Source: §VIII · p. 13
  • DoH deployment concentrates lookups among a small number of resolvers and browsers that can observe user behavior, so resolver privacy remains a concern.The paper calls for more research on Oblivious DNS to avoid creating main surveillance actors.Source: §VIII · p. 13

APPENDIX

The appendix defines per-webpage precision, recall, and F1-score, then estimates the probability of a website given an observed trace using Bayes’ rule and a uniform-prior assumption. It notes that uniform priors are unrealistic and describes how future work could incorporate estimated priors.

A. Performance metrics.

  • Precision, recall, and F1-score are computed per webpage using a one-versus-all classification setup.Each webpage is treated as one class; its samples are positives and samples from other classes are negatives.Source: A. Performance metrics · p. 16

B. Estimation of Probabilities

  • The posterior probability of a website given a trace is computed using Bayes’ rule, with trace likelihoods estimated from dataset samples.With equal sample sizes across sites, the posterior simplifies to website multiplicity divided by the trace’s anonymity-set size.Source: B. Estimation of Probabilities · p. 16
  • Uniform website priors simplify the Bayes formula, but the authors acknowledge this assumption is unrealistic.They provide a mathematical model for incorporating priors if future work can estimate them.Source: B. Estimation of Probabilities · p. 16

C. Extra results on attack robustness

The appendix reports that TLS record-size distributions are similar across platforms but shifted, and that removing the shift improves cross-platform performance. It also presents survivor/easy-prey rankings and confusion graphs to examine classifier errors.

C. Extra results on attack robustness

D. Survivors and Easy Preys

E. Confusion Graphs

  • Confusion graphs encode domains as nodes and misclassifications as directed edges, with node size showing degree and color showing detected community.Edge direction is encoded clockwise in the curvature; communities are identified by the Louvain algorithm.Source: E. Confusion Graphs · p. 17
  • LOC1 errors include repeated confusions between domains from the same CDN or entity, while other repeated errors remain unexplained.The graphs also show clusters sharing domain-name length and a Google cluster linked to one mostly Chinese-domain cluster.Source: Figure 13 · p. 17, Figure 16 · p. 19
  • Tor and perfect-padding errors form petals of mutually confused domains, with more petals under perfect padding than DNS-over-Tor.Domains in a petal tend to be classified as one another.Source: Figure 15 · p. 18, Figure 14 · p. 18
Loading 1906.09682v3…