Does domain name encryption increase users' privacy?

Knowing domain names associated with traffic allows eavesdroppers to profile users without accessing packet payloads. Encrypting domain names transiting the network is, therefore, a key step to increase network confidentiality. Latest efforts include encrypting the TLS Server Name Indication (eSNI extension) and encrypting DNS traffic, with DNS over HTTPS (DoH) representing a prominent proposal. In this paper, we show that an attacker able to observe users' traffic relying on plain-text DNS can uncover the domain names of users relying on eSNI or DoH. By relying on large-scale network traces, we show that simplistic features and off-the-shelf machine learning models are sufficient to achieve surprisingly high precision and recall when recovering encrypted domain names. The triviality of the attack calls for further actions to protect privacy, in particular considering transient scenarios in which only a fraction of users will adopt these new privacy-enhancing technologies.