path: root/doc/system-documentation/introduction.tex

\section{Introduction}

Keys are used to encrypt high sensitive personal data and therefore
they must be kept safely.  Secure storage of private keys is known to
be a difficult problem --- especially for end-users with limited
skills in system administration and insufficiently redundant hardware.
A central objective for any solution is that only the legitimated
owner of a key must have the possibility to recover a lost key.

But how can one create a confidential backup of a key? It certainly
makes no sense to encrypt a key with a different password and then use
the result as a backup. After all, this merely shifts the problem from
the original key to the password, which is basically yet another key.
So simply encrypting the key is not helpful.  But without encryption,
any copy of a key increases availability, but also the risk of the
key's confidentiality being compromised.

Most people have difficulties memorizing a high-entropy
passphrase. Hence, existing key management ``solutions'' often reduce
the problem of memorizing one or more high-entropy passphrases or keys
to memorizing a single low-entropy passphrase. This is not a good
solution, as the low-entropy passphrase undermines security.

In this thesis, we describe a software solution for the described
problem using secret splitting.  We call our solution ``Anastasis'',
which is a medical term for the prognosis of full recovery.  We will
call the information that Anastasis allows the user to recover their
{\em core secret}.

\subsection{Principles}

For Anastasis we have following design objectives, in order of importance:

\begin{enumerate}
 \item Anastasis must be Free Software\footnote{\url{https://www.fsf.org/}}. Everyone must have the right to
   run the program, study the source code, make modifications and share
   their modifications with others.
 \item Anastasis must not rely on the trustworthiness of individual providers.
   It must be possible to use Anastasis safely, even if a subset of the
   providers is malicious. Anastasis must minimize the amount of information
   exposed to providers and the network.
 \item Anastasis must put the user in control: They get to decide which
   providers to use, and which combinations of authentication steps will
   be required to restore their core secret. The core secret always remains exclusively
   under the user's control, even during recovery.
 \item Anastasis must be economical viable to operate. This implies usability
   and efficiency of the system.
 \item Anastasis must support a diverse range of use cases.
\end{enumerate}


\subsection{Approach}

\subsubsection*{Secret sharing and recovery}

Our approach to solve the problem of key recovery is to let the user
split their core secret across multiple escrow providers (see
Figure~\ref{fig:system_arch2}). To recover their core secret, the user has to
authorize key the recovery, usually by passing an authentication check
which they configured for the respective provider.

After successful authentication the user receives the secret shares
and is able to reassemble their core secret locally on their computer.

\begin{figure}[H]
\centering
\includegraphics[scale=0.33]{images/system-architecture_2.png}
\caption{System architecture}
\label{fig:system_arch2}
\end{figure}

\subsubsection*{Derive user identifier}

Every person has some hard to guess, semi-private and unforgettable
inherent attributes such as name and passport number, social security
number or AHV~\cite{jerome2015} number (in Switzerland).  We use those attributes to
improve the security and privacy provided by Anastasis.  Basically,
these attributes serve as weak key material, raising the bar for
attackers without the availability disadvantages of passphrases ---
which users may forget.  Anastasis derives a ``user identifier'' from
such a set of unforgettable attributes (see Figure~\ref{fig:user_id}).

\begin{figure}[H]
\centering
\includegraphics[scale=0.3]{images/user_id.png}
\caption{Derivation of a user identifier}
\label{fig:user_id}
\end{figure}

\subsubsection*{Encrypt and encrypt and encrypt}

Anastasis uses several layers of encryption. First, the user's core
secret is encrypted with a master key. The master key is encrypted
with various policy keys. The policy keys are derived from various
secrets which are encrypted and distributed across various providers
together with information about the desired recovery authorization
procedure. This last encryption is done based on keys derived from the
user identity.  These many layers of encryption are designed to
distribute trust and to minimize or delay information disclosure.

\subsubsection*{Private payments are integrated}

The Anastasis protocol includes provisions for privacy-preserving
electronic payments to the service providers, as well as resource
limitations to protect service providers against resource exhaustion
attacks.  This ensures that it should be possible to operate the
service commercially.


\subsection{Use cases}

There are several applications which are in need of a key escrow
system like Anastasis. Some of them shall be introduced in this
section.

\subsubsection{Encrypted email communication}

For email encryption using Pretty Good Privacy
(PGP)~\cite{garfinkel1995} users need a private key which is typically
stored on the device running PGP.  PGP uses a ``Web of trust'' to
establish the authenticity of keys.

Pretty Easy privacy (short p\equiv p) is ``a cyber security solution
which protects the confidentiality and reliability of communications
for citizens, for public offices and for
enterprises''~\cite{pepdoc}. It secures communication via email by
providing end-to-end encryption similar to PGP.  A major difference is
that p\equiv p uses opportunistic encryption and so-called trustwords
to establish authenticity to avoid usability and privacy problems
associated with the ``Web of trust''~\cite{caronni2000}.

The impact of losing control over the private key is similar in both
systems:

\begin{itemize}
  \item If the private key becomes unavailable, all emails which were
encrypted to that key become unreadable. Furthermore, the user would
likely need to rebuild their ``Web of trust''.
  \item If the private key is
disclosed to an adversary, they might be able to decrypt that user's
encrypted emails -- which may go back years and could include highly
sensitive information.  An adversary could also use the private key
to send cryptographically signed emails pretending to be the user.
\end{itemize}


\subsubsection{Digital currencies and payment solutions}

Another application relying on a core secret are cryptocurrencies like
Bitcoin. Each user of Bitcoin needs an electronic wallet which stores
and protects the private keys of the user. Those private keys
legitimate its owners to spend the bitcoins corresponding to the
keys.~\cite{LLLW*2017}

Losing Bitcoin wallet keys means losing all of the corresponding
Bitcoins.  The reader may be familiar with stories from the mass media
about people who claim to have lost their key to their electronic
wallet and therefore huge sums of
cryptocurrency~\cite{millions_lost}. Backup systems are essential to
avoid such cases.

The following graphic illustrates the keys used in Bitcoin
wallets. In this case, the core secret Anastasis would store
is the ``master key'' $m$:

\begin{figure}[H]
	\centering
	\includegraphics[scale=3.5]{images/bitcoin-keys.png}
	\caption[Master key in Bitcoin wallets]{Master key in Bitcoin wallets (from~\cite{bitcoin-keys})}
	\label{fig:bitcoin_keys}
\end{figure}

GNU Taler\footnote{\url{https://taler.net/de/}} is a new electronic instant payment system for
privacy-friendly online transactions. The GNU Taler digital wallets are
storing electronic coins, and backups are protected with a key.
Losing the backup key means losing all the money stored in the wallet,
as well as the transaction history kept in the wallet.

The European Central Bank (ECB) informally informed Taler Systems SA
about the requirement for electronic wallets denominated in Euros to
support password-less data recovery to ensure users would not loose
their electronic funds if their device were to be damaged or lost.

This was the key impulse which motivated us to create Anastasis,
with the goal of enabling recovery of GNU Taler's backup keys via
Anastasis.


\subsubsection{Password managers}

To avoid using low-entropy passwords and password reuse, some people
use software password managers like
KeePass\footnote{\url{https://keepass.info/}}. Such password managers
relieve you of the burden of remembering many passwords and in most
cases allow the generation of high-entropy passwords.

The user only has to remember the password for the password
manager. However, as discussed before, this is still a major problem:
\begin{itemize}
  \item On the one hand, users could use an insecure, easy to
remember password. In this case, an adversary gaining control
over the password manager's database could break into all systems
secured by keys managed by the password manager.
\item On the other hand, users could use a complex, high-entropy
  passphrase.  However, if that passphrase is forgotten, users
  face the loss of all passwords and thus also all online
  services that the password manager controlled for them.
\end{itemize}

Anastasis can be used to enable recovery of strong passphrases,
such as those that should be used to secure password managers.


\subsubsection{Hard drive encryption}

Data at rest is often protected using (full) drive encryption, for
example using software like
LUKS\footnote{\url{https://guardianproject.info/archive/luks/}}.  For
encryption and decryption of the drive a combination of key files,
passphrases and Trusted Platform Modules (TPMs)~\cite{bajikar2002} are
used.

Anastasis can be used to backup and restore such key files or
passphrases.