Removed spaces in path

1 files changed, 338 insertions, 0 deletions

diff --git a/SSHAttackSummary/Summary.tex b/SSHAttackSummary/Summary.tex
new file mode 100644
index 0000000..b32ffca
--- /dev/null
+++ b/SSHAttackSummary/Summary.tex
@@ -0,0 +1,338 @@
+\documentclass[a4paper,8pt,twocolumn]{extarticle}
+
+\usepackage[english]{babel}
+\usepackage[latin1]{inputenc}
+\usepackage[margin=22mm,top=15mm]{geometry}
+\usepackage{amsmath}
+\usepackage{fourier}
+\usepackage{url}
+\usepackage[hidelinks]{hyperref}
+\usepackage{csquotes}
+\usepackage{minted}
+\usepackage{tikz}
+\usetikzlibrary{positioning}
+
+% Not so much list item spacing; see http://tex.stackexchange.com/a/10689/23992
+\usepackage{enumitem}
+\setlist{itemsep=0pt,parsep=1pt}
+
+\title{Plaintext Recovery Attacks Against SSH -- Summary}
+\author{Camil Staps}
+
+\begin{document}
+
+\maketitle
+
+\begin{abstract}
+    Researchers at the university of London have found a couple of plaintext recovery attacks against SSH in 2008-2009 \cite{kp2009}. This document will give a brief summary of the part of the SSH protocol being attacked and an overview of the attacks that were found (theoretical background, steps to reproduce and countermeasures). We will also discuss how it's possible that a scheme proven to be secure in \cite{bellare} could be broken, and what concretely made the attacks possible.
+\end{abstract}
+
+\section{Introduction}
+\label{sec:introduction}
+The Secure Shell protocol, SSH, is defined in a series of RFCs \cite{rfc-arch}, \cite{rfc-auth}, \cite{rfc-transp}, \cite{rfc-conn}. It is ``a protocol for secure remote login
+   and other secure network services over an insecure network'' \cite{rfc-arch}. There are different implementations of the protocol, the most notable being OpenSSH \cite{openssh} with roughly 85\% of all implementations using OpenSSH or a derivative \cite{ssh-usage}. As the authors of \cite{kp2009}, I will be using SSH as a shorthand for SSHv2 as defined in the aforementioned RFCs and OpenSSH as a shorthand for any version of OpenSSH up to 5.1. Code snippets will come from OpenSSH 4.7, against we'll also reproduce the attack.
+
+The attacks from \cite{kp2009} we will consider allow an attacker to ``verifiably recover 14 bits of plaintext with probability $2^{-14}$ and 32 bits of plaintext with probability $2^{-18}$, both from an arbitrary block of ciphertext, assuming the default configuration of a 128-bit block cipher operating in CBC mode'' \cite[abstract]{kp2009}.
+
+\subsection{Contents}
+In section \ref{sec:protocol} the relevant part of the SSH protocol will very briefly be described. In section \ref{sec:openssh}, the relevant specifics of the OpenSSH implementation of the protocol will be discussed. Section \ref{sec:attack} gives a theoretical description of the attacks that were found and their limitations. In section \ref{sec:reproduction}, I will provide steps one could take to reproduce the attack\footnote{\cite{kp2009} lacks this, but it is relevant for anyone who wishes to build further on this attack.}. It is interesting that the attacked part of the SSH protocol was proven secure by Bellare \emph{et al.} \cite{bellare}. How this is possible will be discussed in section \ref{sec:provensecurity}. Countermeasures will be discussed in section \ref{sec:countermeasures}, and section \ref{sec:scope} will look at what other protocols may be affected.
+
+\section{SSH protocol description}
+\label{sec:protocol}
+The part of the SSH protocol under attack is the Binary Packet Protocol (BPP) as defined in \cite[sec.~6]{rfc-transp}. Typically, it is placed directly on top of the TCP layer. It features an encode-then-encrypt-and-mac scheme that can be visualised in figure \ref{fig:bpp}. 
+
+\begin{figure}[h]
+    \centering
+    \begin{tikzpicture}[->, node distance=2pt, every node/.style={rectangle,draw,fill=gray!10,rounded corners=0pt}, every path/.style={rounded corners=4pt}]
+    \node[minimum height=11mm,minimum width=45mm,text depth=7mm] (msg) {padded message};
+    \node[fill=gray!30] (payload) at ([xshift=3mm,yshift=-1.5mm]msg.center) {Payload};
+    \node[fill=gray!30] (padlen) at ([xshift=10mm,yshift=-1.5mm]msg.west) {len(padding)};
+    \node[fill=gray!30] (padding) at ([xshift=-7mm,yshift=-1.5mm]msg.east) {Padding};
+    \node[minimum height=11mm, left=of msg] (len) {len(p. message)};
+    \node[minimum height=11mm, left=of len] (seqnr) {Seq. nr.};
+
+    \node[minimum height=6mm, below=3mm of msg] (encrypt) {Encrypt};
+    \draw (len) |- (encrypt);
+    \draw (msg) -- (encrypt);
+
+    \node[minimum height=6mm, below right=3mm of encrypt] (mac) {MAC};
+    \draw (seqnr) |- (mac);
+    \draw (len) |- (mac);
+    \draw (msg.200) |- (mac);
+    \end{tikzpicture}
+    \caption{Visualisation of the Binary Packet Protocol as described in RFC 4253 \cite[sec.~6]{rfc-transp}}
+    \label{fig:bpp}
+\end{figure}
+
+A payload is first encoded by postpadding with a random number (between $4$ and $255$) of bytes and prepending by one byte describing the padding length and four bytes describing the length of the payload with padding and padding length byte. This encoded message is then encrypted using the block cipher of choice\footnote{SSH supports several block ciphers. The attacks described in \cite{kp2009} are generic.}. A MAC is computed over the message prepended with its length and a sequence number. This sequence number is not transmitted, but the client and the server keep track of it locally. The final ciphertext is the encrypted message concatenated with the MAC.
+
+The SSH RFC \cite{rfc-transp} recommends different block ciphers in CBC mode and one stream cipher to use for encrypting the encoded message. It mandates the use of \emph{initial packet chaining}, so that the last (encrypted) block of a packet is used as the IV for the first block of the next packet.
+
+\subsection{Decryption}
+The only way to know the length of the message one is receiving, is to decrypt the first block and extract the packet length field. The SSH specification \cite{rfc-transp} prescribes that implementations MUST support messages of up to $32768$ bytes and SHOULD support longer messages where necessary. Furthermore, it recommends sanity checking the packet length field, to make sure it is
+
+\begin{itemize}
+    \item at least as long as the cipher's block size,
+    \item long enough to hold one padding length byte and four padding bytes,
+    \item and `reasonable' (e.g., while the maximum value of the length field is $2^{32}$, a 4GiB message should not be considered `sane').
+\end{itemize}
+
+\subsection{The OpenSSH implementation}
+\label{sec:openssh}
+The SSH specification \cite{rfc-transp} doesn't specify when an implementation should perform the above checks, but the OpenSSH implementations follows the straightforward approach of decrypting the first block as soon as it arrives. It then performs the following checks, in this order:
+
+\subsubsection{Length check} 
+In \texttt{packet.c}, the length field is checked to be at least $5$ and at most $2^{18}$, which is in line with the recommended sanity checking and the recommendation to support messages longer than $32768$ bytes where necessary. If this check fails, a \texttt{SSH2\_MSG\_DISCONNECT} is sent to the client, mentioning the value of the length field. The following is an excerpt from \texttt{packet.c}:
+
+\inputminted[fontsize=\footnotesize,linenos,xleftmargin=8mm,breaklines,tabsize=4,gobble=2,firstline=1093,lastline=1098]{c}{openssh-4.7p1/packet.c}
+
+The \mintinline{c}{packet_disconnect()} function terminates the session and sends the \texttt{SSH2\_MSG\_DISCONNECT} signal with the custom message to the client.
+
+\subsubsection{Block length check} 
+It is verified that \texttt{4 + length} is a multiple of the block size, which it has to be because the message with the length field (4 bytes) is encrypted. If this check fails, the TCP connection is terminated.
+
+\inputminted[fontsize=\footnotesize,linenos,xleftmargin=8mm,breaklines,tabsize=4,gobble=1,firstline=1103,lastline=1103]{c}{openssh-4.7p1/packet.c}
+\inputminted[fontsize=\footnotesize,linenos,xleftmargin=8mm,breaklines,tabsize=4,gobble=1,firstline=1106,lastline=1108]{c}{openssh-4.7p1/packet.c}
+
+\subsubsection{MAC check} 
+More data is accepted if the above two checks pass. After the full message and the MAC have been received (which is to be determined based on the length field), the MAC is checked. If it is invalid, a \texttt{SSH2\_MSG\_DISCONNECT} message is sent with the text ``\texttt{Corrupted MAC on input.}''
+
+The MAC is only computed in case the following \mintinline{c}{return} is not executed:
+
+\inputminted[fontsize=\footnotesize,linenos,xleftmargin=8mm,breaklines,tabsize=4,gobble=1,firstline=1113,lastline=1114]{c}{openssh-4.7p1/packet.c}
+
+Note that an eavesdropping attacker may distinguish between failures of the three checks. The first \texttt{SSH2\_MSG\_DISCONNECT} failure may be detected by looking at the size of the SSH responses. The second failure is indicated by the presence of a \texttt{TCP FIN} packet without payload (recall that the SSH BPP is placed on top of TCP, which means that TCP flags can be read without problems). The last failure may again be detected by looking at the size of the SSH responses. It can be distinguished from the first \texttt{SSH2\_MSG\_DISCONNECT} failure because if the MAC check fails, the server has been awaiting data before.
+
+\section{The Attack}
+\label{sec:attack}
+
+\subsection{Notation}
+Following \cite{kp2009}, we will use $K$ to denote the key of our block cipher, and let $F_K$ and $F_K^{-1}$ be the encryption and decryption operations, respectively. Let $L$ be the block size of the block cipher.
+
+Let $p_1,\dots,p_n$ be a sequence of plaintext blocks, then the ciphertext blocks are given by $$c_i = F_K(c_{i-1} \oplus p_i), \qquad i\in[1,n]$$ where $c_0$ is the last ciphertext block of the previous packet. It follows that $$p_i = c_{i-1} \oplus F_K^{-1}(c_i), \qquad i\in[1,n].$$
+
+As we're considering an attacker who wants to recover some plaintext, we let $c_i^*$ denote the block that he is attacking, $p_i^*$ the corresponding plaintext and $c_{i-1}^*$ the block before $c_i^*$. This gives $$p_i^*=c_{i-1}^* \oplus F_K^{-1}(c_i^*).$$ 
+
+At some point, the attacker will inject a ciphertext block as a new packet. We let $c_n$ denote the last ciphertext block of the packet preceding the injected packet (i.e., $c_n$ is the IV of that packet).
+
+I'm also introducing some notation in addition to \cite{kp2009}: \begin{align*}\cdots|_{m,n} \quad \stackrel{\text{def}}{=} \quad &\text{$n$ consecutive bits of $\cdots$ starting with index $m$,}\\&\text{starting with the MSB}\end{align*}
+
+\subsection{Single attack}
+\label{sec:attack-single}
+An attacker would inject $c_i^*$ as the first block of a new message\footnote{Theoretically, it is impossible to detect message boundaries. In practice however, a message end can be assumed to have occurred when the connection goes silent for some timeout.}. OpenSSH will then directly compute the plaintext for this injected block as \begin{equation}\label{eq:attack}p_1' = c_n \oplus F_K^{-1}(c_i^*),\end{equation} and continue to run the length check and block length check using $l=p_1'|_{0,32}$. There are then three possibilities. As mentioned before, the attacker can distinguish between the three cases.
+
+\subsubsection{Recovering 14 plaintext bits}
+The first possibility is that the length check fails, so $l<5$ or $l>2^{18}$. We can consider $c_n$ to be random and thus also $l'$ to be a random pick from $\{0,1\}^{32}$. Hence, the probability that this check fails is approximately $\left(2^{32}-2^{18}\right)/2^{32} = 1 - 2^{-14}$. In this case, the attack has failed.
+
+Now suppose the length check passes, which happens with probability $2^{-14}$. We then know that $5\le l \le 2^{18}$. This means that the first $14$ bits of $l$, and so also of $p_1'$, are all zeros\footnote{At least, that's what \cite{kp2009} claims. Actually, there's a small chance that $l=2^{18}$ in which case only the first $13$ bits are zero and can be recovered. However, if $l=2^{18}$ we can always continue to recover all 32 bits of the length field, so this error is corrected later on.}. We can then calculate the first 14 bits of the plaintext using equation \ref{eq:attack}: $$F_K^{-1}(c_i^*)|_{0,14} = p_1'|_{0,14} \oplus c_n|_{0,14}.$$
+
+\subsubsection{Recovering 32 plaintext bits}
+When the length check passes, OpenSSH continues to the block length check, where the divisability of $l$ by $L$ is checked. Since $l\bmod{L}$ may be considered a random pick, this happens with probability $L^{-1}$, i.e. $2^{-4}$ for $L=16$ and $2^{-3}$ for $L=8$. If the block length check passes, we know that the last $\log_2(L)$ bits of $l$ encode $L-4$ (minus $4$, because we subtract the length of the length field itself). We may then proceed to compute these last $3$ or $4$ bits of the first 32-bit word of $c_i^*$, as we did above with the first 14 bits. The probability that this is possible is then $2^{-14}\cdot2^{-4}=2^{-18}$ for $L=16$ and $2^{-17}$ for $L=8$.
+
+What's more, if the block length check passes, the SSH connection has entered a wait state. An attacker would then continue to feed random blocks to the server. At some point, the connection will however be terminated due to a MAC error. If we count how much data we sent until the MAC error is triggered, we can use this to work out the exact value of the 32-bit length field. We can then compute the first 32 bits of the plaintext of $c_i^*$ using equation \ref{eq:attack}. This final attack succeeds with probability $2^{-18}$ for $L=16$ and $2^{-17}$ for $L=8$.
+
+There is a small chance that we accidentally guess the right MAC. \cite{kp2009} does not go into details what would happen then -- if the attacker could recognise it or not, because the probability of this happening is very low. For example, for \texttt{hmac-md5}, with a 16-byte MAC, the probability is $2^{-128}$ supposing the block length check passed, or $2^{-18}\cdot2^{-128}$ overall (for $L=16$).
+
+\subsection{Limitations}
+\label{sec:attack-limitations}
+There are some serious limitations to this attack that make it difficult to actually use this weakness efficiently. Not all are described in \cite{kp2009}, but they are still worth mentioning.
+
+First of all, it should be noted that not all plaintext bits can be chosen to recover. Only the first 32 bits of any block can be recovered. For $L=8$ this means we can choose half of the bits, for $L=16$ we may choose one in four. Furthermore, we will never be able to recover more than 4 consecutive bytes.
+
+The success probability of the 14-bit recovery attack ($2^{-14}$) is very low. It is equal to that of the attack where an adversary simply guesses the plaintext. The only difference is that the attacker can verify his answer in this attack. 
+
+When the SSH connection enters a wait state and we continue to recover 32 bits with probability $2^{-18}$ (or $2^{-17}$), the success probability is relatively much higher. However, for this attack to work we would need to feed on average $2^{17}$ bytes of random data before the MAC check triggers. More importantly, after every block we feed to the server, we need to wait for some time to make sure the server has had the time to respond with an error -- otherwise, we may think the server is awaiting more data while it's actually already checking the MAC. This could cause our final computations to be slightly incorrect. This means actually exploiting this attack would take a lot of time.
+
+In a response to the vulnerability report the authors of \cite{kp2009} opened, the OpenSSH Security Advisory wrote \cite{openssh-response}:
+
+\begin{displayquote}
+\textit{``The usage pattern where the attack is most likely to succeed is where an automated connection is configured to retry indefinitely in the event of errors. In this case, it might be possible to recover on average 44 bits of plaintext per hour (assuming a very fast 10 connections per second). Implementing a limit on the number of connection retries (e.g. 256) is sufficient to render the attack infeasible for this case.''}
+\end{displayquote}
+
+\subsection{Iterating the attack}
+\label{sec:attack-iterating}
+Simply repeating the above attack would use at most $2^{18}$ SSH connections\footnote{\cite[sec.~3.4]{kp2009} says this is on average, but that would be $2^{17}$ for $L=16$ and $2^{16}$ for $L=8$.} before succeeding to recover 32 bits. By cleverly choosing the moment the attacker injects $c_i^*$, we may reduce this to at most $2^{14}+L$ connections. This attack can be split up in three phases.
+
+\begin{enumerate}
+    \item The attacker waits for a $c_n$ to appear of which he hasn't seen the first 14 bits yet. He then injects $c_i^*$ as a new packet, in an attempt to recover the 14 first bits as above. This phase requires a list of at most $2^{14}$ 14-bit values (28KiB), indicating which 14-bit bit strings have been seen already.
+    \item The attacker has now found the first 14 bits. He continues, to try and get the block length check to pass as well. However, he will only inject $c_i^*$ when he is sure the length check will pass (which he can see from the first 14 bits of an IV candidate). Even though waiting for this to happen may take some time, he only needs to set up at most $L$ connections in this phase before the block length check passes (similar to before, the attacker only tries IVs that are guaranteed to give a different value of $l\bmod{L}$).
+    \item The last phase is the same as the last phase of the 32-bit recovery attack: the attacker simply continues feeding data until the MAC check triggers.
+\end{enumerate}
+
+Under special circumstances it may be the case that the attacker can guess a part of the plaintext (e.g. the first few blocks of a remote login session may always look the same, or it can be assumed that the plaintext is printable ASCII) he can use similar tricks to reduce the number of needed SSH connections even further.
+
+\section{Reproduction}
+\label{sec:reproduction}
+
+The authors of \cite{kp2009} mention their `proof-of-concept code' several times, but didn't publish it. I asked for their code to be able to perform the attack myself in a testing environment, and Martin Albrecht was so kind to provide a link \cite{kp2009-poc}.
+
+To reproduce the attack in sections \ref{sec:reproduction-server} and \ref{sec:reproduction-attacker}, I assume a *nix setup. Section \ref{sec:reproduction-expl} isn't platform-specific.
+
+\subsection{Testing server}
+\label{sec:reproduction-server}
+To not have to worry about network delay and the like, it is very useful to set up some sort of virtual network. This is even more useful because you get to tweak the SSH implementation to disable some checks and increase the attack probability from $2^{-14}$ to $2^{-2}$ in the manner described in \cite[sec.~4]{kp2009}. This can be done using LXC containers \cite{lxc}, \cite{ubuntu-lxc}, which is the approach I will take here. Any method will do, as long as latency can be kept low. 
+
+Assuming you have LXC installed on your machine, you can create and start a container, and get a root console for it, with:
+
+\begin{minted}[fontsize=\footnotesize,breaklines=true]{bash}
+$ lxc-create -t download -n ssh-attack -- -d ubuntu -r trusty -a amd64
+$ lxc-start -n ssh-attack -d
+$ lxc-attach -n ssh-attack
+\end{minted}
+%stopzone
+
+Now download OpenSSH 4.7\footnote{Although versions up to and including 5.1 are vulnerable to the attack, we used the same version as \cite{kp2009}, so that we could search in the source code for code snippets from the paper.}, patch it to ease the length check as described in \cite[sec.~4.1; 2.1.1]{kp2009}, and install:
+
+\begin{minted}[fontsize=\footnotesize,breaklines=true]{bash}
+$ apt-get update
+$ apt-get install wget build-essential zlib1g-dev libssl-dev
+$ wget http://ftp.nluug.nl/pub/OpenBSD/OpenSSH/portable/openssh- 4.7p1.tar.gz
+$ tar -xf openssh-4.7p1.tar.gz
+$ cd openssh-4.7p1
+$ sed -i 's/packet_length\ =\ get_u32(cp);/packet_length\ =\ 0x000fffff\ \&\ get_u32(cp);/g' packet.c
+$ ./configure --prefix=/opt/openssh --exec-prefix=/opt/openssh
+$ make
+$ make install
+\end{minted}
+%stopzone
+
+You could change the \mintinline{bash}{0x000fffff} to ease the length check more, or less. A lower value causes the length check to fail less, but there's no point in going below \mintinline{bash}{0x0003ffff}, which is $2^{18}-1$.
+
+Now add the \texttt{sshd} user and set the password for the \texttt{ubuntu} user to `\texttt{ubuntu}'.
+
+\begin{minted}[fontsize=\footnotesize,breaklines=true]{bash}
+$ useradd -d /var/run/sshd -s /usr/sbin/nologin -r -U sshd
+$ usermod -p $(perl -e 'print crypt("ubuntu", "salt")') ubuntu
+\end{minted}
+%stopzone
+
+You can now run the server with \mintinline{bash}{/opt/openssh/sbin/sshd}. See \texttt{/opt/openssh/share/man/cat8/sshd.8} manpage for command line arguments. Typically you would want to use debug logging and IPv4 only:
+
+    \begin{minted}[fontsize=\footnotesize,breaklines,autogobble]{bash}
+    $ /opt/openssh/sbin/sshd -d4
+    \end{minted}
+    %stopzone
+
+Not detaching \texttt{sshd} with \texttt{-D} could be useful for debugging, but the server would stop after connection termination, so the attack cannot be performed in this mode.
+
+\subsection{Attacker}
+\label{sec:reproduction-attacker}
+The proof-of-concept code \cite{kp2009-poc} is in essence enough to confirm that the attack works. You might need to install \texttt{python-scapy} first. For the LXC setup described above you would normally need to change the configuration to:
+
+\begin{minted}[fontsize=\footnotesize,breaklines=true]{python}
+iface='lxcbr0'
+bob='10.0.1.1'
+alice='10.0.1.30'
+\end{minted}
+
+You also need to replace `\texttt{10.0.0.2}' with `\texttt{alice}' on line 105.
+
+Then simply load the file in a python shell and start the attack:
+
+\begin{minted}[fontsize=\footnotesize,breaklines=true]{bash}
+$ python -i ssh-attack.py 
+>>> ssh_attack()
+\end{minted}
+%stopzone
+
+The output would look somewhat like this:
+
+\begin{minted}[fontsize=\footnotesize,breaklines=true]{text}
+    0: packet_length < 1 + 4 || packet_length > 256 * 1024
+    1: need % block_size != 0
+.    2: buffer_len(&input) < need + maclen
+144204
+\end{minted}
+
+A log message similar to nr. \texttt{0} here means the length check has failed. You will notice this happens by far the most (although this of course depends on how much you eased this check with the patch in section \ref{sec:reproduction-server}). A message similar to nr. \texttt{1} means the block length check failed. The last message means the block length has passed. The python script will then continue feeding random data to the server. It may take a while before this finishes. After that, a number will be outputted. This number is the calculated packet length. The script does \emph{not} output the recovered plaintext -- ``it is very much proof-of-concept only,'' Mr. Albrecht wrote me -- but considering it is not so hard to imagine an attacker that is able to sniff traffic, this should be enough to conclude the attack works.
+
+\subsection{Code explanation}
+\label{sec:reproduction-expl}
+I will just very briefly describe the most important parts from the proof-of-concept code, from a cryptographic point of view, that is. The \mintinline{python}{ssh_attack()} function contains an infinite loop to keep trying to recover new plaintext. It first generates some traffic, for which the username and password you set in section \ref{sec:reproduction-server} are needed (see the top of this section). After that, it injects a sniffed ciphertext as a new block. It then arrives at the following snippet, where we can see how an attacker would distinguish between different failures:
+
+\inputminted[fontsize=\footnotesize,linenos,xleftmargin=3\parindent,breaklines,tabsize=2,gobble=8,firstline=135,lastline=153]{python}{ssh-attack.py}
+
+The \mintinline{python}{if} statement in line 138 checks ``if the packet list has a payload packet (i.e. it is neither only an ACK nor a FIN)'' (lines 71-72). In this case, it can be assumed that that payload is an SSH error message, which would mean that the length check failed.
+The \mintinline{python}{elif} statement in line 142 checks if the block length check failed. Concretely, this would mean for there to appear a FIN flag in the response, which is easy to check.
+The condition of the \mintinline{python}{elif} statement in line 145 is true iff the two conditions above were false, and could have been replaced with a simple \mintinline{python}{else}. The \mintinline{python}{handle_wait_state()} function feeds data to the server and returns when he receives a MAC failure error message. This is detected in the same way as the SSH error message in \mintinline{python}{got_invalid_packet_length()} was detected.
+
+Finally, the packet length is calculated using the selfexplanatory function \mintinline{python}{calc_packet_length()}:
+
+\inputminted[fontsize=\footnotesize,linenos,xleftmargin=3\parindent,breaklines,tabsize=2,gobble=4,firstline=257,lastline=266]{python}{ssh-attack.py}
+
+
+\section{Comparison with proven security}
+\label{sec:provensecurity}
+
+The SSH BPP was discussed by Bellare \emph{et al.} \cite{bellare}, who broke it but also suggested a couple of small changes -- implementing any would improve the protocol and make it provable secure. However, the attacks from \cite{kp2009} are applicable, also to these provable secure variants. It is odd that the attack described in section \ref{sec:attack}, which succeeds with probability \emph{far} from negligible, is possible against a scheme that is proven secure.
+
+What turns out to be the case is that Bellare \emph{et al.} \cite{bellare} considered a single error message (``$\bot$''), which doesn't let an attacker distinguish between failures in the different checks. A single error message would make sense for the length check and the block length check, however, with any natural implementation of the SSH BPP an attacker could distinguish a MAC failure, because the connection has been in a wait state in this case. Hence, one could argue that the choice made in \cite{bellare} to use a single error message wasn't accurate.
+
+This, together with some other minor differences, explains why a system that has been proven secure turned out to be insecure in practice -- at least with the natural implementation OpenSSH uses.
+
+\subsection{SSH-NPC and SSH-\$NPC}
+Suggestions have been made to use random per-packet IVs rather than interpacket chaining. The NPC variant uses fixed padding and was broken by Bellare \emph{et al.} \cite{bellare}, who then directly introduced SSH-\$NPC, which uses random padding and random IVs. The random IV would be transmitted along with the message, in the plain.
+
+Supposing OpenSSH would be extended in the obvious way to support SSH-\$NPC (or SSH-NPC for that matter), this change would not prevent the attacks from \cite{kp2009}. We would only need to replace $c_n$ (the last ciphertext block) by the random IV. The success probabilities remain the same.
+
+In the iterated attack from section \ref{sec:attack-iterating}, the attacker even has an advantage when using SSH-(\$)NPC. He has the ability to control the IV of the injected packet, and may thus systematically build the size $2^{14}$ table instead of having to wait for new IVs to appear on the line.
+
+\cite[sec.~5.1]{kp2009} also describes a distinguishing attack against SSH-(\$)NPC with probability $1$, but as it is irrelevant for the attacks in section \ref{sec:attack}, I won't go into details here. 
+
+Clearly, randomised IVs won't help securing the BPP against the plaintext recovery attacks found in \cite{kp2009}.
+
+\section{Countermeasures}
+\label{sec:countermeasures}
+
+Bellare \emph{et al.} \cite{bellare} also suggested three other variants of the SSH BPP, that actually do protect from these attacks. Two variants (SSH-CTRIV-CBC and SSH-EIV-CBC) use a special way of computing the IV (the encryption of a counter and the encipherment of the last ciphertext block, respectively) which makes computing the IV infeasible for the attacker. This would mean that the attacker cannot use equation \ref{eq:attack} anymore. The last variant, SSH-CTR, uses counter mode, and is resistant to the plaintext recovery attacks due to its stateful nature.
+
+Naturally, changing the BPP is not something anyone is eager to do (although there is an RFC to standardise SSH-CTR). Fortunately, there were other ways of defending against the attacks from section \ref{sec:attack}. 
+
+A first step was to have the length check and the block length check fail in a similar fashion. In version 1.158 of OpenSSH's \texttt{packet.c}, both failed with an SSH error message. This prevents the 14-bit recovery attack, but doesn't prevent the 32-bit recovery attack -- the latter doesn't rely on distinguishing between a length check failure and a block length failure, but on the wait state of the SSH connection.
+
+A very neat countermeasure was suggested by Denis Bider of Bitvise \cite{bider}. He suggests randomising the length field if either of the length checks fails. The connection will then enter a wait state regardless of the checks, meaning an attacker cannot distinguish between any of the three failures (length check, block length check, MAC) anymore.
+
+Another solution would be to send the length field in the plain. If the protocol were adapted in such a way, all attacks described in \cite{kp2009} would be nullified. However, sending the length field in the plain could give other roblems, especially concerning DoS attacks.
+
+It should be noted that removing the length checks, while making sure there is nothing for an attacker to distinguish, only increases the success probability to $1$. However, it should also be noted that this attack would then require 2GiB random data to be fed to the server to recover 32 plaintext bits, on average.
+
+\section{Scope of the attacks}
+\label{sec:scope}
+
+The plaintext recovery attacks described in section \ref{sec:attack} don't only work against SSH. They are at the very least worth trying against any protocol combining the following:
+
+\begin{itemize}
+    \item An encrypted length field
+    \item CBC mode
+    \item The possibility for a client to deliver new data block by block
+    \item Detailed error signaling
+\end{itemize}
+
+However, as said in section \ref{sec:attack-limitations}, the exploitability of the attacks can be considered \emph{low}. As for OpenSSH, several improvements have been made already, in order to decrease success probabilities, making the attacks from \cite{kp2009} an \emph{academic} break only.
+
+\section{Conclusion and epilogue}
+\label{sec:conclusion}
+
+We have seen and discussed the plaintext recovery attacks against SSH described in \cite{kp2009}, and their limitations. We have seen their mathematical background and a proof-of-concept implementation. Moreover, we explained why the attacks are possible against a scheme that was proven secure in \cite{bellare}. We mentioned several countermeasures that may be taken against the attacks. Finally, we discussed what other protocols could be affected by this kind of attacks.
+
+Since the attacks were found in 2008, OpenSSH has been fixed and recent versions are no longer vulnerable to the attacks from \cite{kp2009}. 
+
+Besides that concrete and practical aspect of \cite{kp2009}, the paper also taught us the importance of an accurate threat model. The choice to use a single error message ``$\bot$'' in the paper by Bellare \emph{et al.} \cite{bellare} caused us to think the SSH BPP was secure, while in fact actual implementations weren't. It is therefore important that threat models are accurately chosen. If it is impossible to strictly define an attacker's abilities, it is always better to stay on the safe side and give him more power than he actually has. 
+
+\begin{thebibliography}{9}
+\bibitem{kp2009} Martin R. Albrecht, Kenneth G. Paterson and Gaven J. Watson. Plaintext Recovery Attacks against SSH, University of London, 2009. \url{http://isg.rhul.ac.uk/~kp/SandPfinal.pdf}
+\bibitem{kp2009-poc} Martin Albrecht. Proof-of-concept implementation of [APW09]. \url{https://bitbucket.org/malb/research-snippets/src/HEAD/ssh-attack.py}
+\bibitem{bellare} M. Bellare, T. Kohno, and C. Namprempre. Breaking and Provably Repairing the SSH Authenticated Encryption Scheme: A Case Study of the Encode-then-Encrypt-and-MAC Paradigm. \emph{ACM Transactions on Information and Systems Security}, 7(2):206--241, 2004.
+\bibitem{rfc-arch} T. Ylonen and C. Lonvick. The Secure Shell (SSH) Protocol Architecture, RFC 4251, Jan. 2006. \url{http://www.ietf.org/rfc/rfc4251.txt}
+\bibitem{rfc-auth} T. Ylonen and C. Lonvick. The Secure Shell (SSH) Authentication Protocol, RFC 4252, Jan. 2006. \url{http://www.ietf.org/rfc/rfc4252.txt}
+\bibitem{rfc-transp} T. Ylonen and C. Lonvick. The Secure Shell (SSH) Transport Layer Protocol, RFC 4253, Jan. 2006. \url{http://www.ietf.org/rfc/rfc4253.txt}
+\bibitem{rfc-conn} T. Ylonen and C. Lonvick. The Secure Shell (SSH) Connection Protocol, RFC 4254, Jan. 2006. \url{http://www.ietf.org/rfc/rfc4254.txt}
+\bibitem{openssh} OpenSSH Project. \url{http://www.openssh.org/}
+\bibitem{ssh-usage} SSH usage profiling. \url{http://www.openssh.org/usage/index.html}
+\bibitem{openssh-response} OpenSSH Security Advisor, 21/11/2008. \url{http://www.openssh.com/txt/cbc.adv}
+\bibitem{bider} Denis Bider, personal communication with the authors of \cite{kp2009}, 18/11/2008.
+\bibitem{lxc} LXC at the Linux Containers project. \url{https://linuxcontainers.org/lxc/introduction/}
+\bibitem{ubuntu-lxc} LXC guide for Ubuntu. \url{https://help.ubuntu.com/lts/serverguide/lxc.html}
+\end{thebibliography}
+
+\end{document}