  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.
