pass15.tex

\documentclass{llncs}
\usepackage{amsmath} % for \mod
\usepackage[hyphens]{url}
\usepackage{hyperref}

\newcommand*{\concat}{\mathbin{\|}}

\begin{document}
\title{Strengthening Public Key Authentication against Key Theft}
\subtitle{Short Paper}
\author{Martin Kleppmann\inst{1} \and Conrad Irwin\inst{2}}
\institute{
    University of Cambridge Computer Laboratory, \email{mk428@cl.cam.ac.uk} \and
    Superhuman Labs, San Francisco, \email{conrad.irwin@gmail.com}
}
\maketitle

\begin{abstract}
Authentication protocols based on an asymmetric keypair provide strong authentication as long as the
private key remains secret, but may fail catastrophically if the private key is lost or stolen. Even
when encrypted with a password, stolen key material is susceptible to offline brute-force attacks.
In this paper we demonstrate a method for rate-limiting password guesses on stolen key material,
without requiring special hardware or changes to servers. By slowing down offline attacks and
enabling easy key revocation our algorithm reduces the risk of key compromise, even if a low-entropy
password is used.
\end{abstract}

\section{Introduction}\label{sec:intro}

Although passwords are the prevalent authentication mechanism on the internet today, there are some
niches in which public key authentication systems have been successfully adopted. For example, SSH
public key authentication~\cite{SSH} is widely used for remote login to servers, TLS client
certificates~\cite{TLS} are used in some countries for access to public services~\cite{Parsovs14},
and FIDO U2F~\cite{FIDOOverview} provides 2-factor authentication for web applications.

In these protocols, a user account is associated with a public key, and a client authenticates
itself to a server by computing a digital signature using the corresponding private key. The private
key is stored on the client device (perhaps using a cryptographic hardware module), so the signature
implements a machine-to-machine authentication protocol (a ``something you have'' factor). Since the
device may be lost or stolen, an additional human-to-machine authentication step is employed to
prevent an attacker using the key: for example, a password or biometric information can be used to
unlock or decrypt the private key.

However, passwords and biometric identifiers are typically low in entropy, making them susceptible
to offline attacks if a device is stolen. Our contribution in this paper is a scheme for storing an
RSA private key in a way that makes it harder for an attacker to make use of stolen key material. We
build upon the mRSA key-splitting scheme~\cite{Boneh01,Kutyiowski12}, which provides instantaneous
key revocation, and extend it with a novel protocol for rate-limiting password guesses, which has
the effect of slowing down offline attacks against stolen key material. In this work
we limit our attention to RSA keys, but we hope to extend our approach to support other public-key
cryptosystems such as ECC in future.

\subsection{Threat Model}\label{sec:threatmodel}

In our scenario, a client stores an RSA private key encrypted with a password. The client wishes to
authenticate itself to a server as username $r$. We assume the server already knows which RSA public
key belongs to which username. We require that all communication occurs over TLS, and that the
client verifies the identity of the server using its existing PKI certificate or a pinned public
key.

Our adversary is an active network attacker, but we assume that our use of TLS prevents the attacker
from eavesdropping or tampering with messages. The attacker can steal encrypted private key material
from a client device (e.g.\ by stealing the physical device or by compromising it remotely). We
assume the attacker can trick the user into accessing fake services, but cannot trick the user into
revealing the key encryption password to the attacker. We assume that the user is aware when a
device has been lost or compromised, and that they are willing to take steps to revoke it.

In Sect.~\ref{sec:mediator} we introduce a semi-trusted service called the \emph{mediator}. We
assume that data stored at the mediator is not accessible to the adversary who can steal private key
material from clients. The mediator cannot authenticate on the client's behalf, and it need not be
trusted as an authority.

\section{Revocable Public Key Authentication}\label{sec:revocation}

In this section we review an existing technique for instant revocation called \emph{mediated RSA}
(mRSA)~\cite{Boneh01,Kutyiowski12}. We demonstrate it by example, using a simplified version of the
FIDO protocols~\cite{FIDOOverview}. We build upon mRSA in Sect.~\ref{sec:ratelimit} to explain our
algorithm for rate-limiting password guesses.

\subsection{Basic RSA Authentication}\label{sec:signature}

A client has a username $r$ and an RSA private key $(n, d)$, where $n$ is the modulus and $d$ the
private exponent. The server knows the corresponding public key $(n, e)$ for $r$, where $e$ is the
public exponent. To authenticate, the client first requests a fresh challenge $c$ from the server.
It then constructs an RSA signature $s$:
\begin{equation}\label{eq:signature}
s = H(c \concat \mathit{cb} \concat u \concat r)^d \mod n \enspace,
\end{equation}
where $u$ is the URL of the server, and $\mathit{cb}$ is the TLS channel
binding~\cite{ChannelBinding} or Origin-Bound Certificate~\cite{Dietz12} of the connection between
server and client. The channel binding prevents MITM and replay attacks. $H$ is shorthand for the
\textsc{EMSA-PSS-Encode} operation (hashing and padding) defined in PKCS\#1~\cite{PKCS1}.

The client then uses TLS to send the authentication request $(s, c, u, r, n, e)$ to the server at
URL $u$, which verifies that $s$ is a valid PKCS\#1 signature of
$c \concat \mathit{cb} \concat u \concat r$ using the public key $(n, e)$, that $c$ and $u$ are
valid for this server, that the channel binding matches, and that $(n, e)$ is a public key for user
$r$.

An adversary who steals the private exponent $d$ can easily impersonate the client. A common
solution is to encrypt $d$ with a key derived from a password using a slow KDF such as
scrypt~\cite{Percival09}. However, password entropy is often low, so this is not sufficient to stop
an attacker with significant computing resources.

\subsection{The Mediator Service}\label{sec:mediator}

To prevent theft of the private exponent $d$, we split it into key fragments using the mRSA
method~\cite{Boneh01,Kutyiowski12}. It is based on the identity:
\begin{equation}
s = m^d = m^{d_a + d_b} = m^{d_a} m^{d_b} \mod n \enspace.
\end{equation}

The private exponent $d$ is split into $d_a$, which is an integer drawn from the uniform random
distribution $U(0, d)$, and $d_b = d - d_a$. Fragment $d_a$ is encrypted with the user's password
and stored on the client device $a$, while fragment $d_b$ is stored on a remote server called the
\emph{mediator}. If the same user has multiple client devices, $d$ can be split in a different way
for each device, with the counterpart of each device's fragment stored on the mediator. It would be
easy to split $d$ into three or more summands, but we focus on the two-fragment case.

After the key has been split, a client device must work together with the mediator in order to
construct a valid signature of the form in (\ref{eq:signature}). When device $a$ wants to generate a
signature, it sends a message $m$ to the mediator:
\begin{equation}\label{eq:mediator-req}
m = H(c \concat \mathit{cb} \concat u \concat r) \enspace.
\end{equation}
The request is sent over TLS and authenticated as described in Sect.~\ref{sec:mediator-auth}. The
mediator uses its key fragment $d_b$ to calculate a response:
\begin{equation}\label{eq:mediator-resp}
\mathit{resp} = m^{d_b} = H(c \concat \mathit{cb} \concat u \concat r)^{d_b} \mod n
\end{equation}
and returns $\mathit{resp}$ to client device $a$. Now, $a$ can calculate the RSA signature $s$:
\begin{equation}\label{eq:assemble-sig}
s = H(c \concat \mathit{cb} \concat u \concat r)^{d_a} \cdot \mathit{resp} = m^{d_a} m^{d_b}
  = m^d \mod n \enspace,
\end{equation}
and thus authenticate with the server at URL $u$.

If a device's key fragment is stolen, it can instantly be revoked by deleting the counterpart
fragment from the mediator, rendering the stolen fragment useless. This deletion request can be
authenticated by another device owned by the same user, as discussed in
Sect.~\ref{sec:mediator-auth}. This implies that a user must enrol at least two physical devices
with the mediator, so that the remaining device can revoke a lost device. A paper print-out of the
key can serve as last resort in case all devices are lost or destroyed.

The mediator need only be partially trusted. It cannot authenticate as the user without the
cooperation of one of the user's physical devices. The user only needs to trust the mediator to be
always online, to keep key fragments safe from attackers who steal devices, and to correctly delete
key fragments when the user requires key revocation. The user's privacy is protected by hashing the
message $c \concat \mathit{cb} \concat u \concat r$ before sending it to the mediator, so the
mediator does not learn which services the user is logging in to, or which usernames they are using.

From the point of view of a server that uses public key authentication, the mediator does not even
exist: a server simply verifies the RSA signature, and does not care how that signature was
constructed. This is in contrast to federated login systems such as OpenID, where the relying party
must trust the identity provider.

\section{Rate Limiting Password Guesses}\label{sec:ratelimit}

In the original proposal of mRSA~\cite{Boneh01}, requests to the mediator are not authenticated. In
this section we show that by adding authentication, we can strengthen mRSA to prevent offline
attacks against stolen private key material.

Consider an attacker who has stolen a client device on which key fragment $d_a$ is stored, encrypted
with password $\mathit{pass}$. The attacker reads the encrypted fragment $E(d_a, \mathit{pass})$
from the device, and mounts an offline attack by repeatedly trying a password guess
$\mathit{pass}^\prime$ (based on a dictionary or brute force) and computing
$D(E(d_a, \mathit{pass}), \mathit{pass}^\prime)$ until the correct $d_a$ is found.

However, an offline attack on the password requires the attacker to be able to determine whether a
decryption attempt has indeed yielded the correct $d_a$. The following protocol ensures that an
attacker must make a request to the mediator for every decryption attempt in order to determine
whether it is correct. This allows the mediator to limit the rate of decryption attempts, giving the
user more time to revoke the stolen device, even if the password is fairly weak.

\subsection{Key Fragment Encryption}\label{sec:fragment-encryption}

Let $k$ be the RSA key length. A key fragment $d_a$ can be encoded as a $k$-bit string, using zero
padding for the most significant bits, since $d_a < d < n < 2^k$. This $k$-bit string can then be
encrypted into a $k$-bit ciphertext $\mathit{efrag}$, using a stream cipher and a key derived from a
password. For example, we can use the scrypt KDF~\cite{Percival09} and AES-128 in CTR
mode~\cite{Lipmaa00} as stream cipher:
\begin{equation}\label{eq:encrypt}
\mathit{efrag} =
    \mathrm{AESCTR}(\mathit{ctr}, \mathrm{scrypt}(\mathit{pass}))_{\{0 \dots k-1\}} \oplus d_a
    \enspace,
\end{equation}
where $\mathit{ctr}$ is a random nonce that is stored in plaintext and incremented by AESCTR for
each block of key stream. An attacker who has stolen $\mathit{efrag}$ and $\mathit{ctr}$ may guess a
password $\mathit{pass}^\prime$, and compute a guess $d_a^\prime$ of the key fragment:
\begin{equation}\label{eq:decrypt}
d_a^\prime =
    \mathrm{AESCTR}(\mathit{ctr}, \mathrm{scrypt}(\mathit{pass}^\prime))_{\{0 \dots k-1\}} \oplus \mathit{efrag}
    \enspace.
\end{equation}

If the password guess $\mathit{pass}^\prime$ is incorrect, $d_a^\prime$ is a uniformly distributed
pseudo-random number between 0 and $2^k$. We deliberately choose \emph{not} to use authenticated
encryption, because the MAC would tell the attacker whether the password guess was correct, making
an offline attack easy.

Note that $d_a$ is drawn from a uniform distribution $U(0, d)$, whereas $d_a^\prime$ is drawn from
$U(0, 2^k)$. Since $d < 2^k$, the distributions are different, which leaks some information: smaller
values of $d_a^\prime$ are more likely to be correct than larger ones. Apart from this bias, there
are no particular features that distinguish the correct $d_a$ from a random bit string.

To quantify this assertion, we generated 50,000 RSA keys ($k=2048$ bits) using OpenSSL, and drew a
uniformly distributed random $d_a$ with $0 \le d_a < d$ for each private exponent $d$.
Table~\ref{tab:bias} shows the bias in the most significant bits of $d_a$ when encoded in $k$ bits.
The key fragments had an entropy of 2047.05 bits, implying that 0.95 bits of information are leaked
by the bias. This can be used by an attacker to prioritize guesses that are more likely to be
correct, but an attacker cannot rule out password guesses from examining $d_a^\prime$ alone.

\renewcommand{\arraystretch}{1.5}
\setlength\tabcolsep{4pt}
\begin{table}[t]
\centering
\caption{Probability that bit $i$ of $d_a$ is 1, when encoded in $k=2048$ bits}\label{tab:bias}
\begin{tabular}{r|rrrrrrrrr}
$i$ & 2047 & 2046 & 2045 & 2044 & 2043 & 2042 & 2041 & 2040 & 2039 \\ \hline
Probability &
0.070 & 0.240 & 0.340 & 0.406 & 0.446 & 0.469 & 0.482 & 0.493 & 0.499
\end{tabular}
\end{table}


\subsection{Authenticating Requests to the Mediator}\label{sec:mediator-auth}

Furthermore, to prevent offline attacks on encrypted key fragments, requests to the mediator must be
authenticated. To see why this is the case, consider an unauthenticated mediator that accepts any
message $m$ and returns $m^{d_b} \mod n$ as in (\ref{eq:mediator-resp}). An attacker could use this
response to test whether a password guess $\mathit{pass}^\prime$ is correct, by using
(\ref{eq:decrypt}) to compute $d_a^\prime$ and checking whether $m^{d_a^\prime} m^{d_b} \mod n$ is a
valid RSA signature.

To prevent this, a client must prove to the mediator that it knows the correct password
$\mathit{pass}$ without revealing the password or the decrypted key fragment $d_a^\prime$. This is
accomplished by the following protocol:

\begin{enumerate}
\item When the client requests the mediator to compute a partial signature on a message $m$, it must
also include a partial signature $s_m$ using $d_a^\prime$:
\begin{align}
    m &= H(c \concat \mathit{cb} \concat u \concat r) \\
    s_m &= H(m \concat \mathit{cb}_m)^{d_a^\prime} \mod n
\end{align}
where $\mathit{cb}_m$ is a channel binding~\cite{ChannelBinding} of the TLS connection between the
client and the mediator. Note that $\mathit{cb}$ is between client and server, whereas
$\mathit{cb}_m$ is between client and mediator.
\item The mediator uses its own channel binding $\mathit{cb}_m^\prime$ of the connection from the
client to compute:
\begin{equation}
s_m \cdot H(m \concat \mathit{cb}_m^\prime)^{d_b} =
  H(m \concat \mathit{cb}_m)^{d_a^\prime} \cdot
  H(m \concat \mathit{cb}_m^\prime)^{d_b} \mod n
\end{equation}
and checks whether the result is a valid signature of $m \concat \mathit{cb}_m^\prime$ for
the user's public key $(n, e)$. This check succeeds if $d_a^\prime = d_a$ (i.e.\ the user's password
was correct), and if $\mathit{cb}_m^\prime = \mathit{cb}_m$ (preventing MITM and replay attacks).
\item If the signature is valid, the mediator computes
\begin{equation}
\mathit{resp} = m^{d_b} = H(c \concat \mathit{cb} \concat u \concat r)^{d_b} \mod n
\end{equation}
as before, and returns it to the client. If the signature is not valid, the mediator returns ``bad
signature''.
\end{enumerate}

When a password-guessing attacker receives a ``bad signature'' response, it learns that the password
guess $\mathit{pass}^\prime$ was incorrect, but it does not gain any additional information that
would help it determine whether any other password guess $\mathit{pass}^{\prime\prime}$ is correct
or not. Thus, the attacker must make a request to the mediator for every guess. If the mediator
receives too many requests for a signature with a particular fragment within a short time, it
returns an error.

The same mechanism can be used to authenticate key revocation: the mediator only processes a
revocation request for a device if it is authenticated by another device of the same user. This
avoids relying on a central authority.

\section{Conclusion}

The security of key-based authentication is only as good as the protection of the private key
material. In this paper we extend mRSA, an existing method for revocation of private keys, by
authenticating requests to the mediator.

Our algorithm ensures that an attacker who has stolen a password-encrypted key, and wants to guess
the password, must make a request to a mediator for every attempt. This gives the mediator the
opportunity to limit the rate at which passwords can be tested, giving the user more time to revoke
the lost device's key. No special hardware is required, and the server just performs standard RSA
signature verification, making our approach compatible with existing systems.

\subsection*{Acknowledgements}

We thank Alastair R.\ Beresford and the reviewers for their helpful feedback.

\bibliographystyle{splncs03}
\bibliography{references}{}

\end{document}