path: root/slides/2021-pets/src/body.tex

\begin{frame}
	%
	% The problem that we are trying to take on in this paper is adding support
	% for CT in Tor Browser.  In other words, right now CT is not enforced at
	% all and that is something we would like to change.
	%
	% The reason why we would like to change that is - first of all - we don't
	% want users of Tor Browser to be subject to DigiNotar style attacks.  This
	% is in fact easier against Tor Browser because you can position
	% yourself in the network by volunteering to run Tor relays.  This type of
	% attacker has been observed several times in Tor - for example by
	% using self-signed certificates or simply targeting HTTP traffic.  Now that
	% encryption on the web matured and continues to mature, you kind of need a
	% mis-issued certificate to pull of these attacks.  So, this is probably a
	% good enough argument already to add CT in Tor Browser.
	%
	% The second threat that is very important for Tor is that an attacker may
	% rely on interception to de-anonymize a subset of users.  For context,
	% recall that Tor is a low-latency anonymity network that routes your
	% traffic through a guard relay, a middle relay, and an exit relay.  At
	% each hop a layer of encryption is pealed off, such that the guard only
	% learns the sender's identity and the exit only learns the visited website.
	% 
	% If the attacker can intercept the encrypted traffic at the exit - using a
	% mis-issued certificate - it would be trivial to de-anonymize a user that
	% logs in to a service.
	%
	% We have also observed cases in the past where attackers break Tor's
	% anonymity by serving zero-day exploits to the browser.  A pre-requisite to
	% serve such an exploit is the ability to make it load.  Again, because the
	% web is mostly encrypted these days, a mis-issued certificate can help to
	% make the loading procedure happen.
	%
	% So, in terms of threat modelling we assume a powerful attacker that has
	% access to a browser zero-day exploit.  The attacker also has the usual Tor
	% capabilities like controlling and denying service to a fraction of relays,
	% and in addition to that the attacker has access to a Certificate Authority
	% that can mis-issue certificates on request.
	%
	% Our design further permits the attacker to control enough CT logs, so that
	% you can trivially bypass today's definition of CT compliance.
	%
	% This is actually one of the reasons why we started looking into Tor in
	% the first place.   If a major problem with full decentralized verification
	% is privacy, then we might have better luck in Tor's more private setting.
	%
	\mktitle{Problem statement}
	\begin{columns}
		\begin{column}{0.5\textwidth}
			\begin{itemize}
				\item Tor Browser does not enforce CT
				\item Guard against prominent threats
					\begin{itemize}
						\item DigiNotar style attacks
						\item Interception to deanonymize
					\end{itemize}
				\item Aim higher than CT compliance
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\centering\includegraphics[width=.5\columnwidth]{img/tb}
		\end{column}
	\end{columns}
	\vfill
	\pause
	\centering\alert{%
		Attacker with browser exploit, CA, CT logs, and usual Tor capabilities
	}
\end{frame}

\begin{frame}
	%
	% What we are proposing is a gradual roll-out plan.
	%
	% The first step is to catch up with today's CT compliant browsers.  Pairs
	% of logs are trusted blindly because there is no follow-up verification
	% of the log's SCTs.  Recall from earlier that SCTs are promises of public
	% logging.  In an ideal world, these promises are also verified by someone.
	%
	% Is this first step suboptimal?
	% - Yes.
	% Is it a significant improvement when compared to what we had before?
	% - Also yes.
	%
	% How to do this is not really a research problem to be honest.  It is,
	% however, a reasonable starting point that we know doesn't break the web.
	% The reason why we know that is because other browsers already do it.
	% I like to think of this first increment as ruling out many weaker
	% attackers that may control certificate authorities but not enough CT logs.
	%
	% Next, we propose some incremental steps to get started with the
	% decentralized verification that will reduce trust in the log ecosystem.
	% I will get back to this later, because it is more intuitive to introduce
	% the full design that places no blind trust in the log ecosystem.
	%
	% In terms of trust assumptions we go from
	%   pairs of logs that are trusted blindly,
	%   to some log that is trusted blindly,
	%   to no log that is trusted blindly.
	%
	\vfill
	\mktitle{Gradual roll-out plan}
	\begin{enumerate}
		\item Catch up with CT compliant browsers
			\floatright{\emph{pairs of logs} are trusted blindly}
		\item Steps towards decentralized verification
			\floatright{\emph{some log} is trusted blindly}
		\item Fully decentralized verification
			\floatright{\emph{no log} is trusted blindly}
	\end{enumerate}
	\vfill
\end{frame}

\begin{frame}
	%
	% Okay.  What I'm hoping to do for the remainder of this presentation is to
	% give you an intuition of
	% a) how we arrived at the full design that is now in front of us, and
	% b) what complexities can we get rid of to roll it out gradually
	%
	% To help us think and reason about the design we divided it into phases.
	%
	% Phase 1 takes place before phase 2.
	% Phase 2 takes place before phase 3.
	% And so forth.
	%
	% For security, it should be difficult for the attacker to reliably
	% interfere without detection in any phase.  Misbehavior of Certificate
	% Authorities and/or CT logs are detected after the final phase played out.
	%
	% Examples of misbehavior include creating a mis-issued certificate or not
	% making it available to the public after promising to do so.
	%
	% Let's look at each phase separately.
	%
	\mktitle{Overview of the full design}
	\centering\includegraphics[height=.5\textheight]{img/design-full}
	\vfill
	\pause
	\alert{Security? Difficult to interfere without detection in any phase}
\end{frame}

\begin{frame}
	%
	% The first phase happens in Tor Browser.
	% A so-called SFO, which is really just a certificate chain and its
	% associated SCTs, is presented to Tor Browser during a website visit.
	% If this SFO is CT compliant, we accept the connection to avoid any
	% blocking and degraded user experience.
	%
	% Now we want to do better than just trusting the logs' promises of public
	% logging.  This means that we will need to audit encountered SFOs by
	% interacting with the logs.
	%
	% The simplest thing that comes to mind is to fetch an inclusion proof from
	% a log.  This interaction is privacy invasive with a regular browser, but
	% less so with Tor Browser because of its anonymity properties.
	%
	% An immediate problem, however, is that Tor Browser has a disk avoidance
	% criteria.  This means that no browsing related activity can be persisted
	% after closing Tor Browser.  This includes encountered SFOs that have yet
	% to be audited.  In practise, it takes up to 24 hours before a certificate
	% is logged.  This follows from a so-called Maximum Merge Delay.
	%
	% In other words, we will have to wait at least 24 hours before a newly
	% issued certificate can be audited.  Tor Browser has likely been shutdown
	% by then, which means that the SFO will be deleted and thus not audited.
	%
	% A second problem is that the attacker controls the log, and in our threat
	% model the attacker also has a zero-day exploit against the browser.  The
	% attacker could trivially delay the log's response while taking control of
	% the browser to disable the auditing mechanism all together.
	%
	% So, what we need is to get the encountered SFO away from Tor Browser as
	% soon as possible so that _someone_ can audit it.  A straw man design would
	% be to send all SFOs to a centralized third-party that is trusted.
	% However, that party would get a considerable aggregation of browsing
	% history.  Such population data is valuable and better not collected.
	%
	% Another problem is that a centralized solution does not scale with the
	% network.  What we do instead is to utilize Tor's existing relays to help
	% with CT auditing.  Such Certificate Transparency Relays are called CTRs in
	% our design.  Relays may be assigned the CTR flag similar to how a Tor
	% relay may be assigned the HSDir flag if some conditions are met.
	%
	% To reduce overhead, only a sample of SFOs are submitted to randomly
	% selected CTRs.  The probability of detection can therefore not be larger
	% than the probability that an encountered SFO is submitted for auditing.
	%
	% Note that it is important that the attacker cannot infer which CTR
	% received an SFO because Tor's threat model includes DoS attacks on
	% individual CTRs.  If you can take the right CTR offline, the submitted
	% SFO would not be audited and any misbehavior would thus not be detected.
	%
	% We discuss how the attacker can try to infer this in the paper using their
	% zero-day exploit.  It boils down to winning a race against us submitting
	% the SFO on a one-time Tor circuit that was prepared ahead-of-time.
	%
	\mktitle{Submission phase}
	\centering\includegraphics[width=.75\textwidth]{img/phase-1}
	\vfill
	\begin{columns}
		\begin{column}{.1\textwidth}
		\end{column}
		\begin{column}{.4\textwidth}
			\textbf{Straw man proposals}
			\begin{itemize}
				\item Fetch an inclusion proof
				\item Rely on a centralized party
			\end{itemize}
		\end{column}
		\begin{column}{.1\textwidth}
		\end{column}
		\begin{column}{.4\textwidth}
			\textbf{What we do instead}
			\begin{itemize}
				\item Use Tor relays, ``CTRs''
				\item Probabilistic submit
			\end{itemize}
		\end{column}
	\end{columns}
	\vfill
	\pause
	\centering\alert{It must be difficult to infer which CTR received an SFO}
\end{frame}

\begin{frame}
	%
	% Okay. 
	%
	% A CTR received a submitted SFO.  Now what?
	%
	% The simplest thing would be to challenge the log to prove inclusion if
	% the SFO's Maximum Merge Delay elapsed, and otherwise wait until it does.
	%
	% The problem with contacting the log immediately is that it leaks a lot of
	% valuable information to the attacker.  For example, it is deterministic
	% when the CTR will do its auditing.  That helps with interference planning.
	%
	% It also leaks real-time browsing patterns which are helpful for traffic
	% analysis against Tor.  Since we will anyway need to buffer newly issued
	% SFOs until the Maximum Merge Delay elapsed, it is not an added complexity
	% to always buffer SFOs for a random amount of time to reduce this leakage.
	%
	% Leakage to CT logs are also reduced because CTRs cache audited SFOs.
	%
	% To summarize the basics of the buffer phase then.
	%
	% You receive an SFO.  If you have not seen it before, you buffer the SFO
	% until the log's Maximum Merge Delay elapsed.  You also add a random
	% auditing delay to obfuscate real-time browsing patterns.
	%
	% Phase 3 starts when it is time to do the auditing.
	%
	% The attacker's best bet to interfere in phase 2 is to do a so-called
	% network-wide flush.  Please refer to our paper for more details.  The
	% TL;DR is that we cannot prevent such interference, but it is trivially
	% detected and draws unwanted attention if CTRs publish relevant metrics.
	% 
	\mktitle{Buffering phase}
	\begin{columns}
		\begin{column}{.5\textwidth}
			\begin{itemize}
				\item Buffer until logging is required
				\item Add a random delay to leak less
				\item Cache audited SFOs to leak less
			\end{itemize}
		\end{column}
		\begin{column}{.5\textwidth}
			\centering
			\includegraphics[width=.5\columnwidth]{img/phase-2}
		\end{column}
	\end{columns}
	\vfill
	\pause
	\centering\alert{%
		The attacker's best bet to interfere is trivially detectable
	}
\end{frame}

\begin{frame}
	%
	% After an SFO's buffering phase is over, the CTR will challenge a log to
	% prove inclusion.  This inclusion proof will reference the first signed
	% tree head in Tor's consensus that should have merged it by now.
	%
	% If you are familiar with gossip, notice that the difficulty of presenting
	% an undetected split-view here is as difficult as breaking Tor's consensus
	% mechanism.  Other user agents than Tor Browser can benefit from this.
	%
	% Anyhow, an important detail that we discuss in the paper is that the
	% attacker (who controls the log) can likely infer which CTR queried for
	% inclusion.  Surprisingly, perhaps, it may even be so despite using Tor.
	%
	% It is problematic if the attacker can infer the CTR's identity.  Then you
	% basically do a DoS on that relay and the mis-issued SFO goes unnoticed.
	%
	% To err on the safe side, we decided to assume that the attacker can in
	% fact identify which CTR queried for inclusion.  In other words, once a
	% mis-issued SFO has been queried for, the querying CTR becomes unavailable.
	%
	% To prepare against this threat each CTR collaborates with another CTR.
	% That other CTR is called a watchdog in our design.  Before doing an
	% inclusion query, the CTR sends the SFO upfront to a watchdog.  If the
	% query succeeded the watchdog receives an acknowledgment.  If there is no
	% timely acknowledgment, it is the watchdog's responsibility to report that
	% SFO to a trusted auditor that will investigate the issue further.
	%
	% The reason why it is not the watchdog that does the final investigation is
	% because the average Tor relay operator cannot be expected to do so.  Tor
	% relays are also designed not to write data to disk unless debugging is
	% enabled.  Such disk writes would increase the risk of unwanted search,
	% seizure, and forensic analysis of the operator's physical servers.
	%
	% Now you might feel like you got the run around.  We started by saying that
	% we cannot have a centralized third-party auditor.  Yet, in the end it is a
	% centralized third-party auditor that investigates potential issues.
	%
	% What's different here is that the number of SFOs that reach these auditors
	% are reduced in numbers.  Under normal circumstances, an auditor should not
	% receive any report at all.  If some log suffers from bad availability, the
	% number of reports are also limited in our design because CTRs back-off
	% immediately after a failed query.  What we trust these auditors with is a
	% tiny subset of SFOs that need further investigation.
	%
	% These auditors also do not have to scale with the network because the
	% expected number of reports is very small.
	%
	\begin{columns}
		\begin{column}{.6\textwidth}
			\mktitle{Audit and report phases}
			\begin{itemize}
				\item Fetch inclusion proof against a specific STH
				\item Rely on Tor's consensus to agree on STHs
				\item Watchdog CTRs do the reporting if needed
					\begin{itemize}
						\item Protects against CTR identification
					\end{itemize}
			\end{itemize}
		\end{column}
		\begin{column}{.4\textwidth}
			\includegraphics[width=\columnwidth]{img/phase-3-4}
		\end{column}
	\end{columns}
	\vfill
	\pause
	\centering\alert{Why not just send to a trusted auditor immediately?}
\end{frame}

\begin{frame}
	%
	% Let's put it all together.
	%
	% For each certificate validation in Tor Browser, we basically flip a coin
	% if it should be submitted to a random CTR for auditing.  We made it as
	% difficult as possible for the attacker to identify this CTR.
	%
	% CTRs buffer incoming SFOs until they can be audited.  To reduce leakage
	% to the logs, random delays are added and audited SFOs are cached.
	%
	% SFOs are audited against signed tree heads in Tor's consensus.  This makes
	% it as difficult to fork the log as it is to forge a valid Tor consensus.
	% Other ecosystems can benefit from this and not just Tor.
	%
	% While an SFO is audited we erred on the safe side and assumed that the
	% attacker can infer from the inclusion query which CTR holds evidence of
	% Certificate Authority
	% and/or log misbehavior.  This means that the holding CTR can be knocked
	% offline shortly thereafter.  To guard against this threat, a watchdog
	% receives the SFO upfront.  If there is no timely acknowledgment, a report
	% is sent to a trusted auditor that investigates the issue further.
	%
	% Such reporting should be rare, even if a log becomes unavailable our
	% design ensures that a limited amount of SFOs leak to these auditors.
	%
	% Although these auditors don't have to scale with the network anymore, it
	% requires both new software and operations to be deployed.  The overall
	% complexity in phase two, three, and four, is also quite a leap from just
	% basic CT compliance.  Therefore, we proposed a simplified version that
	% can be deployed incrementally.
	%
	\mktitle{Putting it all together}
	\centering\includegraphics[height=.5\textheight]{img/design-full}
	\vfill
	\pause
	\alert{This is quite a leap from CT compliance}
\end{frame}

\begin{frame}
	%
	% Phase 1 is identical in our incremental design.  The main difference is
	% that no inclusion proofs will be fetched.  Instead, CTRs are going to
	% cross-log certificates and possibly entire SFOs if CT logs allow it.
	%
	% You can think of this as using the log ecosystem against the attacker.  CT
	% logs are basically repurposed as CT auditors.  A cross-logged certificate
	% becomes public so that Certificate Authority misbehavior can be detected
	% by anyone that inspects the logs.
	%
	% Of course, this assumes that at least some log is honest.
	%
	% We can also detect log misbehavior if CT logs allowed logging of SCTs, not
	% just certificates.  That, however, requires an extended CT log API.
	%
	% Personally, I think that would be a valuable addition to the log ecosystem
	% because it provides a well-defined place to do casual SFO reporting.
	%
	\mktitle{Incremental design}
	\centering\includegraphics[height=.33\textheight]{img/design-incremental}
	\vfill
	\pause
	\alert{Use the log ecosystem against the attacker}\\
\end{frame}