Certificate Transparency is an ecosystem of logs, monitors, and auditors that hold certificate authorities accountable while issuing certificates. We show how the amount of trust that TLS clients and domain owners need to place in Certificate Transparency can be reduced, both in the context of existing gradual deployments and the largely unexplored area of Tor. Our contributions include improved third-party monitoring, a gossip protocol plugging into Certificate Transparency over DNS, an incrementally deployable gossip-audit model tailored for Tor Browser, and using certificates with onion addresses. The methods used range from proof sketches to Internet measurements and prototype evaluations. An essential part of our evaluation in Tor is to assess how the protocols used during website visits—such as requesting an inclusion proof from a Certificate Transparency log—affect unlinkability between senders and receivers. We find that most false positives in website fingerprinting attacks can be eliminated for all but the most frequently visited sites. This is because the destination anonymity set can be reduced due to how Internet protocols work: communication is observable and often involves third-party interactions. Some of the used protocols can further be subject to side-channel analysis. For example, we show that remote (timeless) timing attacks against Tor’s DNS cache reliably reveal the timing of past exit traffic. The severity and practicality of our extension to website fingerprinting pose threats to the anonymity provided by Tor. We conclude that access to a so-called website oracle should be an assumed attacker capability when evaluating website fingerprinting defenses.

Projektet Certificate Transparency är ett ekosystem av loggar, övervakare och granskare som håller certifikatutfärdare till svars för utfärdade webbcertifikat. Vi visar hur säkerheten kan höjas i ekosystemet för både domäninnehavare och TLS-klienter i nuvarande system samt som del av anonymitetsnätverket Tor. Bland våra större bidrag är förbättrad övervakning av loggarna, ett skvallerprotokollsom integrerats med DNS, ett skvaller- och granskningsprotokoll som utformats specifikt för Tors webbläsare och ett förslag på hur domännamn med adresser i Tor kan bli mer tillgängliga. De metoder som använts varierar från säkerhetsbevis till internetmätningar och utvärderingar av forskningsprototyper. En viktig del av vår utvärdering i Tor är att avgöra hur protokoll som används av webbläsare påverkar möjligheten att koppla ihop användare med besökta webbplatser. Detta inkluderar existerande protokoll samt nya tillägg för att verifiera om webbplatsers certifikat är transparensloggade. Våra resultat visar att i många fall kan falska positiva utslag filtreras bort vid mönsterigenkänning av Tor-användares krypterade trafik (eng: website fingerprinting). Orsaken är att besök till de flesta webbplatser kan uteslutas till följd av hur internetprotokoll fungerar: kommunikation är observerbar och involverar ofta interaktioner med tredjeparter. Vissa protokoll har dessutom sidokanaler som kan analyseras. Vi visar exempelvis att Tors DNS-cache kan undersökas med olika varianter av tidtagningsattacker. Dessa attacker är enkla att utföra över internet och avslöjar vilka domännamn som slagits upp vid angivna tidpunkter. De förbättrade mönsterigenkänningsattackerna mot webbplatser är realistiska och hotar därför Tors anonymitet. Vår slutsats är att framtida försvar bör utvärderas utifrån att angripare har tillgång till ett så kallat webbplatsorakel.

We show that Tor's DNS cache is vulnerable to a timeless timing attack, allowing anyone to determine if a domain is cached or not  without any false positives.  The attack requires sending a single TLS record. It can be repeated to determine when a domain is no longer cached to leak the insertion time.  Our evaluation in the Tor network shows no instances of cached domains being reported as uncached and vice versa after 12M repetitions while only targeting our own domains. This shifts DNS in Tor from an unreliable side-channel---using traditional timing attacks with network jitter---to being perfectly reliable.  We responsibly disclosed the attack and suggested two short-term mitigations.

As a long-term defense for the DNS cache in Tor against all types of (timeless) timing attacks, we propose a redesign where only an allowlist of domains is preloaded to always be cached across circuits.  We compare the performance of a preloaded DNS cache to Tor's current solution towards DNS by measuring aggregated statistics for four months from two exits (after engaging with the Tor Research Safety Board and our university ethical review process). The evaluated preload lists are variants of the following top-lists: Alexa, Cisco Umbrella, and Tranco. Our results show that four-months-old preload lists can be tuned to offer comparable performance under similar resource usage or to significantly improve shared cache-hit ratios (2--3x) with a modest increase in memory usage and resolver load compared to a 100 Mbit/s exit.  We conclude that Tor's current DNS cache is mostly a privacy harm because the majority of cached domains are unlikely to lead to cache hits but remain there to be probed by attackers.

Onion addresses offer valuable features such as lookup and routing security, self-authenticated connections, and censorship resistance. Therefore, many websites are also available as onionsites in Tor. The way registered domains and onion addresses are associated is however a weak link. We introduce sauteed onions, transparent associations from domain names to onion addresses. Our approach relies on TLS certificates to establish onion associations. It is much like today's onion location which relies on Certificate Authorities (CAs) due to its HTTPS requirement, but has the added benefit of becoming public for everyone to see in Certificate Transparency (CT) logs. We propose and prototype two uses of sauteed onions: certificate-based onion location and search engines that use CT logs as the underlying database. The achieved goals are consistency of available onion associations, which mitigates attacks where users are partitioned depending on which onion addresses they are given, forward censorship-resistance after a TLS site has been configured once, and improved third-party discovery of onion associations, which requires less trust while easily scaling to all onionsites that opt-in.

The security of the web improved greatly throughout the last couple of years.  A large majority of the web is now served encrypted as part of HTTPS, and web browsers accordingly moved from positive to negative security indicators that warn the user if a connection is insecure.  A secure connection requires that the server presents a valid certificate that binds the domain name in question to a public key.  A certificate used to be valid if signed by a trusted Certificate Authority (CA), but web browsers like Google Chrome and Apple's Safari have additionally started to mandate Certificate Transparency (CT) logging to overcome the weakest-link security of the CA ecosystem.  Tor and the Firefox-based Tor Browser have yet to enforce CT.

In this paper, we present privacy-preserving and incrementally-deployable designs that add support for CT in Tor. Our designs go beyond the currently deployed CT enforcements that are based on blind trust: if a user that uses Tor Browser is man-in-the-middled over HTTPS, we probabilistically detect and disclose cryptographic evidence of CA and/or CT log misbehavior.  The first design increment allows Tor to play a vital role in the overall goal of CT: detect mis-issued certificates and hold CAs accountable.  We achieve this by randomly cross-logging a subset of certificates into other CT logs.  The final increments hold misbehaving CT logs accountable, initially assuming that some logs are benign and then without any such assumption.  Given that the current CT deployment lacks strong mechanisms to verify if log operators play by the rules, exposing misbehavior is important for the web in general and not just Tor.  The full design turns Tor into a system for maintaining a probabilistically-verified view of the CT log ecosystem available from Tor's consensus.  Each increment leading up to it preserves privacy due to and how we use Tor.

Website Fingerprinting (WF) attacks are a subset of traffic analysis attacks where a local passive attacker attempts to infer which websites a target victim is visiting over an encrypted tunnel, such as the anonymity network Tor. We introduce the security notion of a Website Oracle (WO) that gives a WF attacker the capability to determine whether a particular monitored website was among the websites visited by Tor clients at the time of a victim’s trace. Our simulations show that combining a WO with a WF attack—which we refer to as a WF+WO attack—significantly reduces false positives for about half of all website visits and for the vast majority of websites visited over Tor. The measured false positive rate is on the order one false positive per million classified website trace for websites around Alexa rank 10,000. Less popular monitored websites show orders of magnitude lower false positive rates.

We argue that WOs are inherent to the setting of anonymity networks and should be an assumed capability of attackers when assessing WF attacks and defenses. Sources of WOs are abundant and available to a wide range of realistic attackers, e.g., due to the use of DNS, OCSP, and real-time bidding for online advertisement on the Internet, as well as the abundance of middleboxes and access logs. Access to a WO indicates that the evaluation of WF defenses in the open world should focus on the highest possible recall an attacker can achieve. Our simulations show that augmenting the Deep Fingerprinting WF attack by Sirinam et al. [60] with access to a WO significantly improves the attack against five state-of-the-art WF defenses, rendering some of them largely ineffective in this new WF+WO setting.

Certificate Transparency (CT) requires that every certificate which is issued by a certificate authority must be publicly logged. While a CT log can be untrusted in theory, it relies on the assumption that every client observes and cryptographically verifies the same log. As such, some form of gossip mechanism is needed in practice. Despite CT being adopted by several major browser vendors, no gossip mechanism is widely deployed. We suggest an aggregation-based gossip mechanism that passively observes cryptographic material that CT logs emit in plain text, aggregating at packet processors (such as routers and switches) to periodically verify log consistency off-path. In other words, gossip is provided as-a-service by the network. Our proposal can be implemented for a variety of programmable packet processors at line-speed without aggregation distinguishers (throughput), and, based on 20 days of RIPE Atlas measurements that represent clients from 3500 autonomous systems, we show that significant protection against split-viewing CT logs can be achieved with a realistic threat model and an incremental deployment scenario.

We present Steady: an end-to-end secure logging system engineered to be simple in terms of design, implementation, and assumptions for real-world use. Steady gets its name from being based on a steady (heart)beat of events from a forward-secure device sent over an untrusted network through untrusted relays to a trusted collector. Properties include optional encryption and compression (with loss of confidentiality but significant gain in goodput), detection of tampering, relays that can function in unidirectional networks (e.g., as part of a data diode), cost-effective use of cloud services for relays, and publicly verifiable proofs of event authenticity. The design is formalized and security proven in the standard model. Our prototype implementation (about 2,200 loc) shows reliable goodput of over 1M events/s (about 160 MiB/s) for a realistic dataset with commodity hardware for a device on a GigE network using 16 MiB of memory connected to a relay running at Amazon EC2.

We present Steady: an end-to-end secure logging system engineered to be simple in terms of design, implementation, and assumptions for real-world use. Steady gets its name from being based on a steady (heart)beat of events from a forward-secure device sent over an untrusted network through untrusted relays to a trusted collector. Properties include optional encryption and compression (with loss of confidentiality but significant gain in goodput), detection of tampering, relays that can function in unidirectional networks (e.g., as part of a data diode), cost-effective use of cloud services for relays, and publicly verifiable proofs of event authenticity. The design is formalized and security proven in the standard model. Our prototype implementation (2,200 loc) shows reliable goodput of over 1M events/s (160 MiB/s) for a realistic dataset with commodity hardware for a device on a GigE network using 16 MiB of memory connected to a relay running at Amazon EC2. 

Trust in publicly verifiable Certificate Transparency (CT) logs is reduced through cryptography, gossip, auditing, and monitoring. The role of a monitor is to observe each and every log entry, looking for suspicious certificates that interest the entity running the monitor. While anyone can run a monitor, it requires continuous operation and copies of the logs to be inspected. This has lead to the emergence of monitoring as-a-service: a trusted third-party runs the monitor and provides registered subjects with selective certificate notifications. We present a CT/bis extension for verifiable light-weight monitoring that enables subjects to verify the correctness of such certificate notifications, making it easier to distribute and reduce the trust which is otherwise placed in these monitors. Our extension supports verifiable monitoring of wild-card domains and piggybacks on CT’s existing gossip-audit security model. 

A sparse Merkle tree is an authenticated data structure based on a perfect Merkle tree of intractable size. It contains a distinct leaf for every possible output from a cryptographic hash function, and can be simulated efficiently because the tree is sparse (i.e., most leaves are empty). We are the first to provide complete, succinct, and recursive definitions of a sparse Merkle tree and related operations. We show that our definitions enable efficient space-time trade-offs for different caching strategies, and that verifiable audit paths can be generated to prove (non-)membership in practically constant time (<4 ms) when using SHA-512/256. This is despite a limited amount of space for the cache—smaller than the size of the underlying data structure being authenticated—and full (concrete) security in the multi-instance setting.