intro.tex

\section{Introduction}

Despite their many well-known flaws, passwords are still by far the most commonly used
authentication system on the web.~\cite{Bonneau12} However, as users sign up for ever more services,
their use is becoming increasingly unsustainable: demanding that users choose passwords with
sufficient entropy, use a different password for every site, not write them down and even rotate
passwords periodically is unrealistic for most internet services.

With phishing attacks and leaks of password databases unfortunately commonplace, we seek a better
solution. In this paper we focus on authentication in a consumer internet context, such as social
media or e-commerce websites and mobile apps. For a majority of such use cases, an authentication
system with the following properties is desirable:

\begin{enumerate}
\item The system should minimize exposure to human error (such as falling for a phishing attack).
Even with education, human error cannot be avoided completely, so the system should be designed such
that it minimizes the impact in case of an error.
\item In case a device is lost or stolen, the user should be able to easily revoke any credentials
stored on the device, to minimize the chances that an attacker can use a stolen device to gain
access to other systems.
\item It is not necessary, and often undesirable, for the system to authenticate the user as a
physical person. Many services allow pseudonymous signup, which is desirable for reasons of privacy
or freedom of speech. The purpose of the authentication system is thus only to verify that the
current user is the same person as the one who originally signed up under a particular username; no
authentication is performed at signup.
\item The system should not depend on any trusted third party, to avoid risks arising from failure
of the third party (security compromise, going out of business, change of policies, etc).
\item The system should be easy for end-users to install and use, and easy for service owners to
deploy. Since user signup and user activity rates are important business metrics for many online
services, the system should make signup and login \emph{easier} than using a password.
\item Users should have the freedom to use the system on a variety of devices, including shared or
public computers that are only partially trusted, whilst minimizing their exposure to attackers.
For example, a user may choose log in to `unimportant' services (e.g. casual online games) on a
shared or public computer, knowing that their account on that service may be compromised; however,
they limit their use of `important' accounts (e.g. online banking) to trusted devices. Since there
is no generally agreed boundary between `important' and `unimportant' services, the same
authentication system should be able to support both use cases.
\end{enumerate}

The rest of this paper is structured as follows: in section~\ref{sec:incumbents} we discuss the
advantages and disadvantages of various existing authentication methods, and in
section~\ref{sec:protocol} we introduce Octokey, a new protocol by which websites and online
services can authenticate users. In section~\ref{sec:interdevice} we discuss the communication
amongst several devices owned by the same user. Our threat model and various design trade-offs are
discussed in section~\ref{sec:threat}, and in section~\ref{sec:otherapproaches} we compare Octokey
to other proposals for authentication protocols.

\section{Existing systems}\label{sec:incumbents}
\subsection{Passwords}\label{sec:passwords}

Passwords have many of the desirable properties mentioned above: no dependence on any third party,
pseudonymity, simplicity of implementation, familiarity and cross-device compatibility. However,
remembering a large number of passwords is a big burden on users, and they are highly susceptible to
human error: use of weak passwords, reuse of the same password across different services, phishing
attacks and leaks of unhashed or weakly hashed password databases are sadly common.

Web browsers' built-in password managers, or external password manager products such as 1Password
and LastPass, make it feasible for users to maintain a strong, unique password for each service they
use. However, even when a unique password is used, an attacker who succeeds in stealing a password
(e.g. by phishing, malware, keylogging, man-in-the-middle attack, eavesdropping when it is
accidentally sent over an unencrypted connection, or exploiting a vulnerability in the password
manager~\cite{Li14, Silver14}) has access to that user account until the password is changed, which
is often a long time.

If an attacker steals the encrypted password database (perhaps by stealing user's device, or a
backup of the filesystem), they can mount an offline dictionary or brute-force attack on the
encryption password. If the user fears the password database may have been stolen, they must
manually change the password for each of their services, which is laborious if they use many
services. If an attacker succeeds in breaking the encryption before the passwords are changed, they
may lock the legitimate user out of their accounts.

Password managers also have grave exposure to human error. For example, consider a user who wishes
to log in to an `unimportant' website on an untrusted computer. It is very tempting for the user to
type the master passphrase of their password manager into the untrusted computer, in order to
decrypt the password database. This has the effect of exposing the user's entire password database
to an attacker running malware on the untrusted computer.

\subsection{One-time passwords and 2FA}\label{sec:otp}

One-time passwords (OTPs) are a big security improvement over regular passwords. The user must
download a list of one-time passwords on a trusted device, or register a cryptographic device that
generates a pseudorandom sequence of OTPs~\cite{TOTP}, or register an email address or phone number
to which OTPs can be sent on demand. Some services allow use of OTPs as sole authentication
mechanism, while others use them in conjunction with a regular password (two-factor authentication,
2FA).

The advantage of OTPs is that the exposure to attacks is limited to a single service, and ends when
the user clicks the logout button (assuming the session is correctly invalidated on the server, and
assuming that the attacker does not have a means of extending their privileges, e.g. by granting
themselves OAuth access to the account).

However, OTPs are so inconvenient to use that very few services are willing to adopt them as their
only or primary authentication mechanism, and only the most security-conscious users are willing to
use them. Moreover, the common ``remember me on this device'' feature weakens two-factor
authentication (attackers just need to steal the ``remember me'' cookie as well as keylogging the
password). OTPs are also prone to phishing, just like regular passwords.

OTPs sent on demand via email or SMS have the effect of `outsourcing' the authentication to the
email provider or the mobile network provider, respectively: any attacker who can access the email
provider or SMS messages can also gain access to any service using on-demand OTPs. The same is true
if users can reset their password via a confirmation email. This essentially makes them federated
authentication schemes (see section~\ref{sec:federated}).

\subsection{Federated authentication}\label{sec:federated}

OpenID~\cite{OpenID} is probably the best-known attempt to remove the need for a separate password
on every service. Some identity providers, such as Google Federated Login~\cite{GoogleOpenID} and
Facebook Connect, combine the ideas of OpenID and OAuth~\cite{OAuth}. Mozilla Persona
(BrowserID)~\cite{Persona, BrowserID} uses a different protocol, but is similar in the way it
delegates authentication to the user's email provider (or a fallback service provided by Mozilla).

Such federated authentication protocols do not solve the fundamental problem of authentication: they
only delegate it to the identity provider, who must then use some other authentication method (most
commonly a password, possibly in conjunction with a OTP from a hardware token). This means that all
the problems discussed above apply to the identity provider, with an additional privilege escalation
problem: if an attacker gains access to the user's account with the identity provider, they can
access any account associated with that identity. Like with a password manager, a single user error
can lead to all of a user's accounts being compromised.

Moreover, the relying party (the service where the user is trying to log in) needs to trust the
identity provider to correctly authenticate the user.  If the identity provider is compromised, the
relying party has no way of detecting unauthorized logins from that identity provider. If the
identity provider experiences an outage or goes out of business, users of that provider lose their
ability to log in (unless they had previously set up delegation of their identity URL, which is
unrealistic to expect of non-technical users). When different services are in competition with each
other, it is typically not in one service's interest to accept a competing service as identity
provider.

For these reasons, OpenID login is typically only accepted by small services; major online services
rarely act as a relying party in OpenID. The competitive dynamic between services makes it unlikely
that a user will ever be able to use a single identity provider across all services.

\subsection{Client certificates}\label{sec:clientcerts}

TLS~\cite{TLS} provides a mechanism for a client to authenticate itself to the server using a X.509
certificate. The server may specify the certificate authority from which it is willing to accept
certificates. By calculating a signature over the TLS key exchange messages, client certificate
authentication also provides protection against man-in-the-middle attacks (a MITM cannot receive a
certificate on one TLS connection and relay it to another TLS connection).

Client certificates are a good solution in situations where the physical identity of the user is
important: certificates might be issued by a government to its citizens (for filing taxes online),
or by a company to its employees (for accessing internal systems). For example, the government of
Estonia issues certificates on smart cards to its citizens through the national ID card scheme, and
the certificates are widely used for authentication by banks, utility companies and other
organisations in Estonia.~\cite{Parsovs14}

Client certificate authentication can be performed by hardware tokens, e.g. using the PKCS \#11
\emph{Cryptoki} API. This provides some protection against private keys being stolen by malware, but
it is inconvenient for users (see section~\ref{sec:hardware}).

Despite their advantages, client certificates are not widely used for consumer internet services.
Problems include:
\begin{itemize}
\item The user interface for installing and managing certificates is unfriendly in most web
browsers and operating systems. Services are not able to customize the look and feel of the signup
and authentication process.
\item It is not possible to be logged in to several accounts on one service at the same time. Even
logging out and switching to another account is awkward.
\item There is no good solution for authenticating on multiple devices, or even on multiple
sandboxed applications on the same device. Either private keys must be copied to each device
(increasing the risk of key theft), or each device must have its own keys (in which case, every time
the user acquires or disposes of a device, they must must manually update each of their services to
reflect the certificates for their current set of devices -- very laborious if they use hundreds of
services).
\item Certificates issued by an external CA typically contain personally identifying information,
such as a real name or email address. In order to enable pseudonymous usage, and to remove the
third-party trust dependency, a service provider must itself act as a CA.
\item Revocation of certificates (which requires CRLs or OCSP~\cite{OCSP}) is often not implemented
correctly. If OCSP servers are slow or unavailable, a service provider must either fail all logins
(unacceptable in practice), or skip revocation checking (allowing stolen certificates to be used).
\end{itemize}

\subsection{Private keys in secure hardware}\label{sec:hardware}

The \emph{Fast Identity Online} (FIDO) Alliance, an industry consortium, has drafted a specification
for new user authentication protocol.~\cite{FIDOOverview, FIDOSpec} Its basic mechanism is that the
user registers a public key when signing up to an online service. Whenever the user wants to log in,
the service provides a challenge, and the user signs the challenge using their private key to prove
their identity.

Unlike TLS client certificates, FIDO is an application-layer protocol. We believe that the basic
components of FIDO (public key authentication at the application layer) are promising. However, much
of the FIDO specification is dedicated to issues of using hardware modules (\emph{authenticators})
to store private keys and perform signing operations. On the other hand, the specification largely
ignores the issue of revoking a key that has been lost or stolen.

Another hardware-based authentication project is Pico~\cite{Stajano11}, which also proves ownership
of a secret key by signing a challenge. Pico addresses the risk of key theft by using $k$-out-of-$n$
secret sharing across several hardware modules carried by the user, such as glasses, belt, wallet,
and jewellery. This approach is theoretically interesting, but the possibility of a large-scale
deployment seems remote.

Whilst the security characteristics of hardware modules are appealing, the user experience is quite
inconvenient at present. For example, a USB-based module cannot be used on a mobile device that has
no USB port. If the cryptographic module is built into the device, the authentication capability is
not portable across devices.

A small number of high-value services (such as online banking) can afford to significantly
inconvenience users in the name of security, but for the majority of online services, any
authentication method that is less convenient than a password is unlikely to gain adoption, even if
it is significantly more secure. We seek a solution that can be deployed today, which does not
inconvenience users, and which does not require new hardware to be developed.