protocol.tex

\section{Octokey protocol overview}\label{sec:protocol}

Octokey is a user authentication protocol designed to meet the goals stated in the introduction. It
aims to provide good security in a software-only configuration, with cryptographic hardware modules
being an optional enhancement. It strives to be a \emph{trust-free} protocol: it is completely
decentralized, there is no dependency on any identity provider, and the extent to which PKI
certificate authorities need to be trusted is minimized as far as possible.

The basic operation of Octokey is inspired by SSH public key authentication, which is widely used
for shell access to remote servers. When using Octokey for the first time, a user generates a RSA
keypair.\footnote{We hope that the approach could be extended to support other public-key
cryptosystems such as ECC.} When the user signs up to a service, or migrates from another
authentication method to Octokey, the user submits their public key to the service. This is
analogous to creating a password when a user first signs up to a service.

Whenever the user wishes to log in, they must prove ownership of the private key. A client does this
by requesting a challenge from the server, signing it using the private key, and submitting the
signature to the server. The details of this protocol are given below.

We can think of Octokey as a machine-to-machine authentication protocol, and it needs to be preceded
by a human-to-machine authentication step: for example, a password or biometric information can be
used by the client device to unlock or decrypt the private key. However, since this password or
biometric information is not sent over the network, this concern is orthogonal to the
machine-to-machine authentication. Any improvements in biometric sensors, for example, do not
require any changes to the Octokey protocol or any support by service providers.

If a password is used to decrypt the user's private key, they need only remember a single password
per device, but not a separate password for every service where they have an account. We believe
that a single password (like in a password manager) is an acceptable user experience.

\subsection{Challenges}\label{sec:challenges}

A service that accepts Octokey login must generate challenges, which are then signed by clients (see
section~\ref{sec:mandates}). The client does not interpret challenges, but treats them as opaque
byte strings. We propose that a service constructs a challenge from a wall-clock timestamp $t$, a
nonce $x$, and a secret key $K$ that is known only to the service:
$$c = t \concat x \concat \mathrm{HMAC}(K, t \concat x)$$
The symbol $\concat$ denotes encoding and concatenating the values into a byte string. When a client
submits a signed challenge to the service, the service can verify its validity by checking that all
of the following are true:
\begin{itemize}
\item $\mathrm{HMAC}(K, t \concat x)$ is a valid HMAC using the secret key K. This ensures that the
challenge was issued by this service.
\item $t$ is a recent timestamp (e.g. no more than 5 minutes old). This is a guard against offline
brute-force attacks.
\item $x$ has not been used within the time interval $t$. This prevents replay attacks.
\end{itemize}

\subsection{Authentication mandates}\label{sec:mandates}

Each user has a RSA keypair $(n, d, e)$ where $n$ is the modulus, $d$ is the private exponent and
$e$ is the public exponent. A key also has an expiry date $\mathit{ex}$, which is chosen when the
key is generated, and which is used to rotate the user's keypair periodically (see
section~\ref{sec:rotation}). The service may have multiple public keys on record for a user, and
should allow any one of those keys to authenticate as the user.

To log in or sign up, the user's client first requests a challenge $c$ from the service via a HTTP
endpoint. It then calculates $m = H(c \concat u \concat r \concat \mathit{ex})$ where $u$ is the URL
of the service endpoint, $r$ is the user's registered username, and $\mathit{ex}$ is the expiry date
of the key. $H$ is shorthand for the \textsc{EMSA-PSS-Encode} operation (hashing and padding) as
defined in PKCS\#1.~\cite{PKCS1} The RSA signature can then be calculated as $s = m^d \mod n$.

The client then constructs the \emph{mandate}, which is an encoding of the RSA-signed message and
the user's public key: $$\mathit{mandate} = s \concat c \concat u \concat r \concat \mathit{ex} \concat n \concat e.$$
The mandate is sent to the server as part of a HTTP request over TLS, and is handled at the
application layer. The server can verify the mandate by checking that all of the following are true:
\begin{itemize}
\item $s$ is a valid PKCS\#1 signature of the message $c \concat u \concat r \concat \mathit{ex}$,
checked against the public key $(n, e)$.
\item $c$ is a valid challenge, as defined in section~\ref{sec:challenges}.
\item $u$ is a valid URL for this service. A mandate for an unknown URL must be rejected. This
prevents phishing-like attacks, whereby an attacker creates an imitation website under a
similar-looking URL and tricks the user into logging in.
\item For a signup request, the username $r$ is not yet taken. For a login request, $r$ is a
registered username for this service, and $(n, e, \mathit{ex})$ is a public key for that user.
\item $\mathit{ex}$ is in the future.
\end{itemize}

If a login mandate is successfully verified, the user is logged in by the server in the usual
manner, for example by setting an appropriate session cookie. If a signup mandate is successfully
verified, the signup flow continues as usual, e.g. asking for the user's name and verifying their
email address.

\subsection{Protection against key theft}\label{sec:revocation}

Many users have multiple devices (e.g. laptop, smartphone, tablet, game console) on which they need
to be able to log in to their accounts with online services. As described above, the private key
$(n, d, e)$ would need to be copied to each of those devices. If any of those devices is lost or
compromised, and an attacker can break the human-to-machine authentication step (perhaps due to a
weak password on the private key), the attacker could gain access to all of a user's accounts.

To mitigate this risk, we ensure that the private exponent $d$ is never stored on any one device.
Instead, we split it into key fragments that are distributed among the user's devices. We use the
\emph{mediated RSA} (mRSA) scheme~\cite{Boneh01,Kutyiowski12} which is based on the fact that
$$s = m^d = m^{d_a + d_b} = m^{d_a} m^{d_b} \mod n$$ provided that $d = d_a + d_b \mod \phi(n)$.

If two devices $a$ and $b$ each have a key fragment $d_a$ and $d_b$ respectively, and those
fragments sum to the private exponent $d$, then we call those devices \emph{paired}. In order to
generate a valid signature, any two paired devices need to collaborate. If device $a$ wants to
generate a mandate, it can send a signing request $\mathit{req}$ to device $b$:
$$\mathit{req} = H(c \concat u \concat r \concat \mathit{ex}) \concat n \concat e$$
where the public key $(n, e)$ indicates which key should be used, in case device $b$ stores multiple
keys. Device $b$ then uses its key fragment $d_b$ to calculate a response:
$$\mathit{resp} = H(c \concat u \concat r \concat \mathit{ex})^{d_b} = m^{d_b} \mod n$$
and returns $\mathit{resp}$ to $a$. Now, $a$ can calculate
$$s = H(c \concat u \concat r \concat \mathit{ex})^{d_a} \cdot \mathit{resp} = m^{d_a} m^{d_b} \mod n,$$
construct a mandate with a valid signature, and thus log in.

If a device is lost, stolen or compromised, this scheme allows the user to revoke that device's
login capability: every device that is paired with the lost device must be instructed to delete the
key fragment from the pairing with the lost device. When all the paired fragments have been deleted,
the key fragments on the lost device become useless. Thus, even if the human-to-machine
authentication is weak, not all is lost: the user only needs to revoke the lost device's key
fragments faster than an attacker can break the human-to-machine authentication.

A key could also be split into more than two fragments; we discuss this in section~\ref{sec:multiway}.

\subsection{The mediator service}\label{sec:mediator}

Authenticating by using paired physical devices (e.g.\ a laptop and a smartphone) yields a similar
user experience to current 2-factor authentication solutions, whereby the user must fetch the phone
from their pocket, launch the appropriate app, and perform some kind of handshake. This is
possible, but distinctly less convenient for users than typing a password, so it is not the simple
user experience we are looking for.

However, there is a simple solution within the mRSA framework: one of the user's `devices' may be a
remote service on the internet, which we call the \emph{mediator}. This service stores key fragments
that are paired with each of the user's physical devices, and responds to signing requests by
performing the modular exponentiation using its key fragments. This allows a user to authenticate
with services using only one physical device -- the coordination with the mediator happens
automatically behind the scenes.

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 not
collude with 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 u \concat r \concat \mathit{ex}$ before sending it to the mediator, so it does not learn
which services the user is logging in to, or which usernames they are using.

From the point of view of a service that accepts Octokey login, the mediator does not even exist: a
service simply verifies the RSA signature on a mandate, and does not care how that signature was
constructed. This is in contrast to federated login systems, where the relying party must trust the
identity provider.

\subsection{Rate limiting password guesses}\label{sec:ratelimit}

Besides enabling key revocation, mRSA can also be used to strengthen the human-to-machine
authentication step against offline attacks.

For example, say the key fragment on a device is encrypted with a symmetric key derived from a
password.\footnote{This discussion also applies to other human-to-machine authentication methods,
for example an encryption key that is derived from biometric measurements.} Consider an attacker who
has stolen this encrypted fragment. In order to brute-force the password, the attacker needs a way
of determining whether a password guess is correct. However, a key fragment is just a uniformly
distributed random number; by itself, the correctly decrypted key fragment is indistinguishable from
the garbage that results from trying to decrypt with the wrong password (see
section~\ref{sec:fragmentenc}).

Assuming the attacker has no other key fragments, they can only determine whether the password guess
was correct by communicating with the mediator and testing whether they are able to construct a
valid PKCS\#1 signature. This gives us an opportunity to rate-limit password guessing attempts: if
the mediator receives too many requests based on an incorrect password, it can block further
attempts and advise the user to revoke the device pairing.

In order to achieve this, we must design the protocol such that an attacker must communicate with
the mediator for every password attempt, but without revealing the password or the decrypted key
fragment to the mediator. We can do this as follows:

Say the key fragment $d_a$ has been encrypted with password $\mathit{pass}$, and the attacker has
stolen the encrypted fragment
$$\mathit{efrag} = \mathrm{encrypt}(\mathrm{PBKDF2}(\mathit{pass}), d_a).$$
The attacker now guesses $\mathit{pass}^\prime$ and computes a guess $d_a^\prime$ of the plaintext:
$$d_a^\prime = \mathrm{decrypt}(\mathrm{PBKDF2}(\mathit{pass}^\prime), \mathit{efrag})$$
To check whether $d_a^\prime = d_a$ the attacker needs to contact the mediator where $d_b$ is held.

We modify the mediator's request processing as follows:
\begin{enumerate}
\item In addition to the signing request $\mathit{req}$, the client is required to submit a
signature $s_\mathit{req}$:
\begin{align*}
    \mathit{req} &= H(c \concat u \concat r \concat \mathit{ex}) \concat n \concat e \\
    s_\mathit{req} &= H(\mathit{req} \concat \mathit{cb})^{d_a^\prime} \mod n
\end{align*}
where $\mathit{cb}$ is the \texttt{tls-unique} channel binding~\cite{ChannelBinding}
of the TLS connection between the client and the mediator. Channel binding is further discussed in
section~\ref{sec:channelbinding}.
\item The mediator queries its database for a key fragment $d_b$ belonging to the user with public
key $(n, e)$. If the device uses a TLS client certificate when connecting to the mediator (see
section~\ref{sec:channels}), it can retrieve the key fragment for the authenticated client device.
\item Using the channel binding $\mathit{cb}^\prime$ of the TLS connection's server side, the
mediator computes
$$s_\mathit{req} H(\mathit{req} \concat \mathit{cb}^\prime)^{d_b} =
  H(\mathit{req} \concat \mathit{cb})^{d_a^\prime} H(\mathit{req} \concat \mathit{cb}^\prime)^{d_b} \mod n$$
and checks whether the result is a valid PKCS\#1 signature of
$\mathit{req} \concat \mathit{cb}^\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}^\prime = \mathit{cb}$
(preventing MITM and replay attacks).
\item If the signature is valid, the mediator computes
$$\mathit{resp} = H(c \concat u \concat r \concat \mathit{ex})^{d_b} \mod n$$
as before, and returns it to the client. If the signature is not valid, the mediator returns ``bad
signature''. A password-guessing attacker learns that the password guess $\mathit{pass}^\prime$ was
incorrect, but otherwise nothing is revealed that would help them guess the password.
\end{enumerate}

Note that although the mediator computes an RSA signature using the user's private key, the value
being signed ($\mathit{req} \concat \mathit{cb}$) cannot be used to construct a mandate, so the
mediator cannot log in to services on the user's behalf.

This protection against password guessing only works if the attacker does not have any knowledge of
previous requests to the mediator. If the attacker knows $x^{d_a} \mod n$ (a request) or
$x^{d_b} \mod n$ (a response) for any $x$, they can brute-force the password without contacting the
mediator, and thus circumvent the rate-limiting.  It is therefore important that communication with
the mediator is protected from eavesdropping (using TLS) and is not logged on the device.

\subsection{Key fragment encryption}\label{sec:fragmentenc}

The method described in section~\ref{sec:ratelimit} for rate-limiting password guesses depends on a
correctly decrypted key fragment being indistinguishable from an incorrect password guess without
contacting the mediator. In this section we propose an encryption scheme which satisfies that
requirement.

We first derive an encryption key from the password using a slow, memory-hard key derivation
function such as Scrypt~\cite{Percival09}. The parameters of the key derivation function (salt, cost
parameter, pseudorandom function used, etc.) are stored in cleartext. We then generate a key stream
using a symmetric block cipher such as AES-128 in CTR mode.~\cite{Lipmaa00}

Let $k$ be the minimum number of bits required to encode the RSA modulus $n$ (i.e. the RSA key
length). To encrypt the key fragment $d_a$, we first encode it as a $k$-bit string, using zeros for
the most significant bits if necessary. We then take the first $k$ bits of the AES-CTR key stream
and XOR them with the $d_a$ bit string:
$$\mathit{efrag} = \mathit{ctr} \concat
    (\mathrm{AESCTR}(\mathit{ctr}, \mathrm{scrypt}(\mathit{pass}))_{\{0 \dots k-1\}} \oplus d_a)$$
where $\mathit{ctr}$ is a 128-bit random nonce that is incremented by AESCTR for each subsequent
block of key stream.

Any attempt to decrypt the key fragment results in a uniformly distributed pseudo-random number
between 0 and $2^k$, whereas the correct key fragment is uniformly distributed between 0 and $d$.
Since $d < 2^k$, a password guess that results in a larger decrypted value is less likely to be
correct than a password guess that results in a smaller decrypted value. A password-guessing
attacker can use this knowledge to prioritize guesses, but they cannot entirely rule out guesses
without contacting the mediator.

To quantify the bias, we repeatedly generated 2048-bit RSA keys using OpenSSL. Approximately 90\% of
private exponents were in the range $0.05 < 2^{-k} d < 0.8$, with a fairly uniform distribution
within that range. When key fragments $d_a$ (chosen uniformly from $[0, d]$) were encoded in $k$
bits, they had on average 2.8 high-order zero bits, and the top bit was zero in 94\% of key
fragments.

\subsection{Channel binding and preventing MITM}\label{sec:channelbinding}

TLS connections are susceptible to man-in-the-middle attacks -- using forged TLS certificates, due
to users ignoring warnings about invalid certificates, or due to malware. Such incidents have been
observed in practice.~\cite{Huang14,Adkins11} An attacker who succeeds in establishing a MITM
position can steal signed mandates, and use them to impersonate the user. Can we secure the
connection between the device and the service against MITM?

Some authentication methods such as SCRAM-SHA-1-PLUS~\cite{SCRAM} use \emph{channel binding} to
prevent MITM attacks. For example, the \texttt{tls-unique} channel binding type works by hashing the
handshake messages that established the TLS connection: in a direct connection, server and client
obtain the same hash value, but if the connection was terminated and restarted by a MITM, the server
and client's values differ. If the client incorporates this hash value into the mandate (such that
it cannot be changed by the MITM), and the server checks that it equals the server-side view of the
connection, then a mandate is rendered invalid by the presence of a MITM.

Origin-Bound Certificates~\cite{Dietz12} generalize this idea to the web, creating a channel
binding that is not tied to a particular TCP connection. When a client first connects to a
particular domain name, it automatically creates a self-signed TLS certificate (without any user
interaction) and presents it to the server. This certificate does not have any authentication
purpose, but the fingerprint of the certificate could be incorporated into a mandate as a channel
binding.

APIs for accessing TLS channel bindings and creating TLS certificates are currently not readily
available in web browsers and in HTTP server implementations. Thus, while channel binding for
Octokey mandates would yield a significant improvement in security, it would also make the protocol
much harder to deploy, both on the client and on the server side. We therefore propose making it an
optional extension.\footnote{For the communication between Octokey clients and mediator, as
described in section~\ref{sec:ratelimit}, we do require channel binding. As this protocol only needs
to be implemented in the Octokey software, not by every service that accepts Octokey as
authentication mechanism, the burden of deployment is much smaller.}

An alternative effort to prevent MITM is the Certificate Transparency project~\cite{CertTrans},
which aims to strengthen trust in the PKI by providing a public audit log of issued certificates,
and rejecting certificates that do not appear in the log. Certificate Transparency does not protect
against attackers who have stolen a website's private key (or governments, which can obtain the
private key with a court order), but it does prevent more casual kinds of MITM attacks, so it may be
sufficient.