Padding Ain't Enough: Assessing the Privacy Guarantees of Encrypted DNS
Pith reviewed 2026-05-25 11:19 UTC · model grok-4.3
The pith
Padding encrypted DNS messages fails to prevent website identification from traffic analysis.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The authors show that a classifier combining message sizes and timing information of padded DNS queries can deanonymize website visits. Using sequences of DNS resolutions instead of single queries, their attack succeeds in labeling at least half the test traces correctly for 80.2% of Alexa top-10k sites and all traces for 32% of them. They conclude that mitigations must remove entropy from inter-arrival timings between query responses.
What carries the argument
A size-and-timing classifier applied to modeled sequences of DNS resolutions triggered by website loads.
If this is right
- Padding alone, as specified in RFC 8467, does not achieve the intended privacy protection for DoT and DoH.
- Website fingerprinting remains feasible even when every DNS message is padded and encrypted.
- Any effective defense must eliminate distinguishable inter-arrival timing patterns between responses.
- DNS sequence modeling captures more identifying structure than single-query analysis.
- The attack works against the full complexity of modern websites that trigger dozens of resolutions.
Where Pith is reading between the lines
- Similar size-timing leaks could appear in other padded encrypted protocols that carry variable-length objects.
- Real deployments may see lower accuracy once unknown sites and changing network conditions are included.
- Combining the DNS classifier with other side channels such as TCP or TLS fingerprints would likely raise success rates further.
- Randomizing or constant-timing DNS response delivery would be a direct way to test the paper's timing-entropy claim.
Load-bearing premise
The attacker possesses a complete, up-to-date model of DNS query sequences for every website and real user traces match the training sequences closely enough for the classifier to succeed.
What would settle it
Collecting fresh padded DNS traces from visits to the same Alexa top-10k sites over varied networks and finding that the size-timing classifier drops to near-random accuracy would falsify the attack's reported effectiveness.
Figures
read the original abstract
DNS over TLS (DoT) and DNS over HTTPS (DoH) encrypt DNS to guard user privacy by hiding DNS resolutions from passive adversaries. Yet, past attacks have shown that encrypted DNS is still sensitive to traffic analysis. As a consequence, RFC 8467 proposes to pad messages prior to encryption, which heavily reduces the characteristics of encrypted traffic. In this paper, we show that padding alone is insufficient to counter DNS traffic analysis. We propose a novel traffic analysis method that combines size and timing information to infer the websites a user visits purely based on encrypted and padded DNS traces. To this end, we model DNS sequences that capture the complexity of websites that usually trigger dozens of DNS resolutions instead of just a single DNS transaction. A closed world evaluation based on the Alexa top-10k websites reveals that attackers can deanonymize at least half of the test traces in 80.2% of all websites, and even correctly label all traces for 32.0% of the websites. Our findings undermine the privacy goals of state-of-the-art message padding strategies in DoT/DoH. We conclude by showing that successful mitigations to such attacks have to remove the entropy of inter-arrival timings between query responses.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims that padding in DoT/DoH is insufficient to prevent traffic analysis. It introduces a sequence-based attack using size and timing features from multi-query DNS traces and reports, in a closed-world evaluation on Alexa top-10k sites, that at least half the test traces can be deanonymized for 80.2% of websites and all traces correctly labeled for 32.0% of websites. The authors conclude that effective mitigations must eliminate entropy in inter-arrival timings between responses.
Significance. If the closed-world results generalize, the work shows that existing padding strategies (per RFC 8467) fail to meet their privacy goals against sequence-aware adversaries and usefully highlights timing as the remaining leakage vector. The modeling of full DNS query sequences (rather than single transactions) is a methodological strength that better reflects real website behavior. The paper provides concrete, falsifiable accuracy numbers that can be tested against the described corpus.
major comments (3)
- [Closed-world evaluation (Section 5)] Closed-world evaluation (Section 5): The reported figures (80.2% of sites with ≥50% trace deanonymization; 32% with 100% accuracy) are obtained under the assumption that the attacker possesses a complete, up-to-date model of DNS sequences for every Alexa top-10k site. This assumption is load-bearing for the central claim that padding fails against practical adversaries, yet no open-world results (precision, recall against a background of unseen sites) are provided to quantify performance when the model is necessarily incomplete.
- [Classifier and feature details (Section 4)] Classifier and feature details (Section 4): The abstract states concrete accuracy numbers, but the manuscript provides insufficient information on the training/test split ratios, exact feature extraction for the size+timing classifier, choice of learning algorithm, and any cross-validation or significance testing. Without these, the 80.2% and 32.0% figures cannot be independently reproduced or assessed for sensitivity to post-hoc choices.
- [Mitigation conclusion (Section 6)] Mitigation conclusion (Section 6): The claim that 'successful mitigations have to remove the entropy of inter-arrival timings' is presented as following from the results, but the manuscript does not include an explicit ablation or countermeasure experiment demonstrating that timing removal defeats the attack while padding alone does not.
minor comments (1)
- [Abstract] The abstract should explicitly qualify the evaluation as closed-world to prevent readers from overgeneralizing the privacy implications.
Simulated Author's Rebuttal
We thank the referee for the constructive and detailed feedback. We address each major comment below, providing clarifications where the manuscript's scope limits new experiments while committing to revisions that strengthen the presentation without altering the core claims.
read point-by-point responses
-
Referee: Closed-world evaluation (Section 5): The reported figures (80.2% of sites with ≥50% trace deanonymization; 32% with 100% accuracy) are obtained under the assumption that the attacker possesses a complete, up-to-date model of DNS sequences for every Alexa top-10k site. This assumption is load-bearing for the central claim that padding fails against practical adversaries, yet no open-world results (precision, recall against a background of unseen sites) are provided to quantify performance when the model is necessarily incomplete.
Authors: We agree that open-world results would better quantify performance against incomplete attacker models. Our closed-world evaluation follows standard practice in traffic analysis to first establish the existence of leakage when an adversary has full knowledge of the target set; the high accuracies demonstrate that sequence and timing features leak website identity despite padding. We will add a new subsection discussing expected open-world degradation, referencing related work on how closed-world baselines inform practical threat models, while noting that collecting a representative background corpus is a substantial undertaking beyond the current scope. revision: partial
-
Referee: Classifier and feature details (Section 4): The abstract states concrete accuracy numbers, but the manuscript provides insufficient information on the training/test split ratios, exact feature extraction for the size+timing classifier, choice of learning algorithm, and any cross-validation or significance testing. Without these, the 80.2% and 32.0% figures cannot be independently reproduced or assessed for sensitivity to post-hoc choices.
Authors: We acknowledge the need for greater reproducibility. The revised manuscript will expand Section 4 to specify the train/test split ratios, the exact construction of the size and timing feature vectors from multi-query sequences, the learning algorithm and hyperparameters, and the cross-validation procedure with any significance testing performed. These additions will allow independent verification of the reported figures. revision: yes
-
Referee: Mitigation conclusion (Section 6): The claim that 'successful mitigations have to remove the entropy of inter-arrival timings' is presented as following from the results, but the manuscript does not include an explicit ablation or countermeasure experiment demonstrating that timing removal defeats the attack while padding alone does not.
Authors: The conclusion is deductive from the experimental design: all traces were already padded per RFC 8467, so the attack's success with combined size+timing features isolates timing as the residual entropy source. Prior literature has already shown size-only attacks are defeated by padding; we will revise Section 6 to make this logical chain explicit, including a brief contrast with size-only baselines, rather than adding a new ablation experiment. revision: partial
Circularity Check
No circularity: standard held-out empirical evaluation on collected traces
full rationale
The paper reports results from a supervised classifier (size+timing features on modeled DNS sequences) trained on one subset of Alexa top-10k traces and evaluated on held-out test traces. No equations, parameter fits, or derivations are presented that reduce the reported deanonymization rates to the inputs by construction. No self-citations are invoked as load-bearing uniqueness theorems or ansatzes. The closed-world setup is an explicit modeling choice whose limitations are acknowledged in the skeptic reading, but the measurement itself is not circular.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Closed-world assumption: attacker knows every possible website the user might visit and has representative training traces for each.
Reference graph
Works this paper leans on
-
[1]
Alexa Internet, “Top 1 million traffic ranking,” Nov. 2018. [Online]. Available: https://alexa.com/
work page 2018
-
[2]
Use of DNSSEC validation for world
APNIC, “Use of DNSSEC validation for world.” [Online]. Available: https://stats.labs.apnic.net/dnssec/XA
-
[3]
A paged domain name system for query privacy,
D. E. Asoni, S. Hitz, and A. Perrig, “A paged domain name system for query privacy,” in Cryptology and Network Security – 16th International Conference, 2017
work page 2017
- [4]
-
[5]
K. Daly, “Add DoH UI setting,” Nov. 2018. [Online]. Available: https://chromium-review.googlesource.com/c/chromium/src/+/1194946
work page 2018
-
[6]
Extension Mechanisms for DNS (EDNS(0)),
J. Damas, M. Graff, and P. A. Vixie, “Extension Mechanisms for DNS (EDNS(0)),” RFC 6891, Apr. 2013. [Online]. Available: https://rfc-editor.org/rfc/rfc6891.txt
work page 2013
-
[7]
A technique for computer detection and correction of spelling errors,
F. Damerau, “A technique for computer detection and correction of spelling errors,” Communications of the ACM , 1964
work page 1964
-
[8]
Chrome devtools protocol viewer
C. Developers, “Chrome devtools protocol viewer.” [Online]. Available: https://chromedevtools.github.io/devtools-protocol/
-
[9]
DNS privacy implementation status,
“DNS privacy implementation status,” Jan. 2019. [Online]. Available: https://dnsprivacy.org/wiki/pages/viewpage.action?pageId=23035950
work page 2019
-
[10]
DNSBL information – spam database and blacklist check,
“DNSBL information – spam database and blacklist check,” 2018. [Online]. Available: https://www.dnsbl.info/
work page 2018
-
[11]
Home page of the DNSCrypt project
“Home page of the DNSCrypt project.” [Online]. Available: https: //dnscrypt.info/
-
[12]
DNSCurve.io – a community for DNSCurve,
“DNSCurve.io – a community for DNSCurve,” Nov. 2018. [Online]. Available: https://dnscurve.io/
work page 2018
-
[13]
“DNSSEC deployment report,” Feb. 2019. [Online]. Available: https://rick.eng.br/dnssecstat/
work page 2019
- [14]
-
[15]
“DNS PRIVate Exchange (dprive).” [Online]. Available: https: //datatracker.ietf.org/wg/dprive/about/
-
[16]
The DNS-Based Authentication of Named Entities (DANE) Protocol: Updates and Operational Guidance,
V . Dukhovni and W. Hardaker, “The DNS-Based Authentication of Named Entities (DANE) Protocol: Updates and Operational Guidance,” RFC 7671, Oct. 2015. [Online]. Available: https://rfc- editor.org/rfc/rfc7671.txt
work page 2015
-
[17]
Peek-a-boo, I still see you: Why efficient traffic analysis countermeasures fail,
K. P. Dyer, S. E. Coull, T. Ristenpart, and T. Shrimpton, “Peek-a-boo, I still see you: Why efficient traffic analysis countermeasures fail,” in IEEE Symposium on Security and Privacy , 2012
work page 2012
-
[18]
Encrypt that SNI: Firefox edition,
A. Ghedini, “Encrypt that SNI: Firefox edition,” Oct. 2018. [Online]. Available: https://blog.cloudflare.com/encrypt-that-sni-firefox-edition/
work page 2018
-
[19]
D. K. Gillmor, “Empirical DNS padding policy,” Mar. 2017. [Online]. Available: https://dns.cmrg.net/ndss2017-dprive-empirical-DNS-traffic- size.pdf
work page 2017
-
[20]
The effect of DNS on Tor’s anonymity,
B. Greschbach, T. Pulls, L. M. Roberts, P. Winter, and N. Feamster, “The effect of DNS on Tor’s anonymity,” in 24th Annual Network and Distributed System Security Symposium , 2017
work page 2017
-
[21]
k-fingerprinting: A robust scalable website fingerprinting technique,
J. Hayes and G. Danezis, “k-fingerprinting: A robust scalable website fingerprinting technique,” in 25th USENIX Security Symposium , 2016
work page 2016
-
[22]
Behavior-based tracking: Exploiting characteristic patterns in DNS traffic,
D. Herrmann, C. Banse, and H. Federrath, “Behavior-based tracking: Exploiting characteristic patterns in DNS traffic,” Computers & Secu- rity, 2013
work page 2013
-
[23]
Evaluating the security of a DNS query obfuscation scheme for private Web surfing,
D. Herrmann, M. Maaß, and H. Federrath, “Evaluating the security of a DNS query obfuscation scheme for private Web surfing,” in ICT Systems Security and Privacy Protection , 2014
work page 2014
-
[24]
P. E. Hoffman and P. McManus, “DNS Queries over HTTPS (DoH),” RFC 8484, Oct. 2018. [Online]. Available: https://rfc- editor.org/rfc/rfc8484.txt
work page 2018
-
[25]
The DNS-Based Authentication of Named Entities (DANE) Transport Layer Security (TLS) Protocol: TLSA,
P. E. Hoffman and J. Schlyter, “The DNS-Based Authentication of Named Entities (DANE) Transport Layer Security (TLS) Protocol: TLSA,” RFC 6698, Aug. 2012. [Online]. Available: https://rfc- editor.org/rfc/rfc6698.txt
work page 2012
-
[26]
Specification for DNS over Transport Layer Security (TLS),
Z. Hu, L. Zhu, J. Heidemann, A. Mankin, D. Wessels, and P. E. Hoffman, “Specification for DNS over Transport Layer Security (TLS),” RFC 7858, May 2016. [Online]. Available: https://rfc-editor.org/rfc/rfc7858.txt
work page 2016
-
[27]
Specification of DNS over Dedicated QUIC Connections,
C. Huitema, M. Shore, A. Mankin, S. Dickinson, and J. Iyengar, “Specification of DNS over Dedicated QUIC Connections,” Internet Engineering Task Force, Internet-Draft draft-huitema-quic-dnsoquic- 05, Jun. 2018, work in Progress. [Online]. Available: https: //datatracker.ietf.org/doc/html/draft-huitema-quic-dnsoquic-05
work page 2018
-
[28]
Network-based HTTPS client identification using SSL/TLS fingerprinting,
M. Hus ´ak, M. Cerm ´ak, T. Jirs ´ık, and P. Celeda, “Network-based HTTPS client identification using SSL/TLS fingerprinting,” in 10th International Conference on Availability, Reliability and Security, 2015
work page 2015
-
[29]
HTTPS traffic analysis and client identification using passive SSL/TLS fingerprinting,
——, “HTTPS traffic analysis and client identification using passive SSL/TLS fingerprinting,” EURASIP Journal on Information Security , 2016
work page 2016
-
[30]
ID4me – one ID for everything, everywhere
“ID4me – one ID for everything, everywhere.” [Online]. Available: https://id4me.org/
-
[31]
Toward an efficient website fingerprinting defense,
M. Ju ´arez, M. Imani, M. Perry, C. D ´ıaz, and M. Wright, “Toward an efficient website fingerprinting defense,” in 21st European Symposium on Research in Computer Security , 2016
work page 2016
-
[32]
M. Kirchler, D. Herrmann, J. Lindemann, and M. Kloft, “Tracked without a trace: Linking sessions of users by unsupervised learning of patterns in their DNS traffic,” in Proceedings of the 2016 ACM Workshop on Artificial Intelligence and Security , 2016
work page 2016
-
[33]
Sender Policy Framework (SPF) for Authorizing Use of Domains in Email, Version 1,
S. Kitterman, “Sender Policy Framework (SPF) for Authorizing Use of Domains in Email, Version 1,” RFC 7208, Apr. 2014. [Online]. Available: https://rfc-editor.org/rfc/rfc7208.txt
work page 2014
-
[34]
DNS over TLS support in Android P developer preview,
E. Kline and B. Schwartz, “DNS over TLS support in Android P developer preview,” Apr. 2018. [Online]. Avail- able: https://android-developers.googleblog.com/2018/04/dns-over-tls- support-in-android-p.html
work page 2018
-
[35]
DomainKeys Identified Mail (DKIM) Signatures,
M. Kucherawy, D. Crocker, and T. Hansen, “DomainKeys Identified Mail (DKIM) Signatures,” RFC 6376, Sep. 2011. [Online]. Available: https://rfc-editor.org/rfc/rfc6376.txt
work page 2011
-
[36]
Binary codes capable of correcting deletions, inser- tions, and reversals,
V . I. Levenshtein, “Binary codes capable of correcting deletions, inser- tions, and reversals,” in Soviet physics doklady , vol. 10, no. 8, 1966, pp. 707–710
work page 1966
-
[37]
A. Mayrhofer, “The EDNS(0) Padding Option,” RFC 7830, May 2016. [Online]. Available: https://rfc-editor.org/rfc/rfc7830.txt
work page 2016
-
[38]
Padding Policies for Extension Mechanisms for DNS (EDNS(0)),
——, “Padding Policies for Extension Mechanisms for DNS (EDNS(0)),” RFC 8467, Oct. 2018. [Online]. Available: https://rfc- editor.org/rfc/rfc8467.txt
work page 2018
-
[39]
Improving DNS privacy in Firefox,
P. McManus, “Improving DNS privacy in Firefox,” Jun. 2018. [Online]. Available: https://blog.nightly.mozilla.org/2018/06/01/improving-dns- privacy-in-firefox/
work page 2018
-
[40]
Domain Names – Implementation and Specification,
P. Mockapetris, “Domain Names – Implementation and Specification,” RFC 1035, Nov. 1987. [Online]. Available: https://rfc-editor.org/rfc/ rfc1035.txt
work page 1987
-
[41]
Website fingerprinting at internet scale,
A. Panchenko, F. Lanze, J. Pennekamp, T. Engel, A. Zinnen, M. Henze, and K. Wehrle, “Website fingerprinting at internet scale,” in23rd Annual Network and Distributed System Security Symposium , 2016
work page 2016
-
[42]
Website finger- printing in onion routing based anonymization networks,
A. Panchenko, L. Niessen, A. Zinnen, and T. Engel, “Website finger- printing in onion routing based anonymization networks,” in Proceed- ings of the 10th annual ACM workshop on Privacy in the electronic society, 2011
work page 2011
-
[43]
DNS performance – compare the speed and uptime of enterprise and commercial DNS services,
PerfOps, “DNS performance – compare the speed and uptime of enterprise and commercial DNS services,” 2018. [Online]. Available: https://www.dnsperf.com/#!dns-resolvers
work page 2018
-
[44]
DNS over Datagram Transport Layer Security (DTLS),
K. T. Reddy, D. Wing, and P. Patil, “DNS over Datagram Transport Layer Security (DTLS),” RFC 8094, Feb. 2017. [Online]. Available: https://rfc-editor.org/rfc/rfc8094.txt
work page 2017
-
[45]
Encrypted Server Name Indication for TLS 1.3,
E. Rescorla, K. Oku, N. Sullivan, and C. A. Wood, “Encrypted Server Name Indication for TLS 1.3,” Internet Engineering Task Force, Internet-Draft draft-ietf-tls-esni-02, Oct. 2018, work in Progress. [Online]. Available: https://datatracker.ietf.org/doc/html/draft-ietf-tls- esni-02
work page 2018
-
[46]
Beauty and the burst: Remote identification of encrypted video streams,
R. Schuster, V . Shmatikov, and E. Tromer, “Beauty and the burst: Remote identification of encrypted video streams,” in 26th USENIX Security Symposium, 2017
work page 2017
-
[47]
Timing analysis in low-latency mix networks: Attacks and defenses,
V . Shmatikov and M. Wang, “Timing analysis in low-latency mix networks: Attacks and defenses,” in 11st European Symposium on Research in Computer Security , 2006
work page 2006
-
[48]
Pretty bad privacy: Pitfalls of DNS encryption,
H. Shulman, “Pretty bad privacy: Pitfalls of DNS encryption,” in Proceedings of the 13th Workshop on Privacy in the Electronic Society , 2014. 14
work page 2014
-
[49]
DNS privacy not so private: the traffic analysis perspective,
S. Siby, M. Juarez, N. Vallina-rodriguez, and C. Troncoso, “DNS privacy not so private: the traffic analysis perspective,” The 11th Workshop on Hot Topics in Privacy Enhancing Technologies , pp. 3– 4, 2018
work page 2018
-
[50]
Deep fingerprinting: Undermining website fingerprinting defenses with deep learning,
P. Sirinam, M. Imani, M. Ju ´arez, and M. Wright, “Deep fingerprinting: Undermining website fingerprinting defenses with deep learning,” in Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, 2018
work page 2018
-
[51]
Stubby – DNS privacy stub resolver
“Stubby – DNS privacy stub resolver.” [Online]. Available: https: //github.com/getdnsapi/stubby
-
[52]
“Nlnet labs – unbound.” [Online]. Available: https://nlnetlabs.nl/ projects/unbound/about/
-
[53]
Website fingerprinting attack method based on DNS resolution sequence,
K. Wang, L. Chen, and X. Chen, “Website fingerprinting attack method based on DNS resolution sequence,” in International Conference on Applications and Techniques in Cyber Security and Intelligence , 2019
work page 2019
-
[54]
Effective attacks and provable defenses for website fingerprinting,
T. Wang, X. Cai, R. Nithyanand, R. Johnson, and I. Goldberg, “Effective attacks and provable defenses for website fingerprinting,” in Proceed- ings of the 23rd USENIX Security Symposium , 2014
work page 2014
-
[55]
Walkie-Talkie: an efficient defense against passive website fingerprinting attacks,
T. Wang and I. Goldberg, “Walkie-Talkie: an efficient defense against passive website fingerprinting attacks,” in 26th USENIX Security Sym- posium, 2017
work page 2017
-
[56]
Traffic morphing: An efficient defense against statistical traffic analysis,
C. V . Wright, S. E. Coull, and F. Monrose, “Traffic morphing: An efficient defense against statistical traffic analysis,” in 16th Annual Network and Distributed System Security Symposium , 2009
work page 2009
-
[57]
Analysis of privacy disclosure in DNS query,
F. Zhao, Y . Hori, and K. Sakurai, “Analysis of privacy disclosure in DNS query,” in 2007 International Conference on Multimedia and Ubiquitous Engineering, 2007. 15 APPENDIX DISTANCES BETWEEN TRACES Fig. 9. Overview over the distances between traces of the same domain. The traces are from the closed-world scenario. The orange line shows the minimal dista...
work page 2007
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.