\section{Related work}

This chapter explains some important cryptographic functions and which
are used in Anastasis or related to our work. We also describe issues
with existing solutions in this domain.

\subsection{Cryptographic primitives}

\subsubsection{Pseudo-randomness}

A pseudo random generator (PRG) is an algorithm producing an infinite
sequence of bits for which there is no efficient algorithm to
distinguish it from a truly random sequence~\cite{vadhan2012}. The
algorithm ``takes as input a short, perfectly random
seed''~\cite{vadhan2012} which determines the output value.\\

A pseudo random function (PRF) is a deterministic function which
output is finite and indistinguishable from a true random
function.~\cite{nielsen2002} PRFs can be constructed using
PRGs.~\cite{GGM1986}

\subsubsection{Hash function}

Hash functions "compress a string of arbitrary length to a string of
fixed length [...]"~\cite{Preneel1999}. The output of a hash function
often is called a "hash".  Hash functions in general should be very
fast to compute. Cryptographic hash functions need to fulfil
additional security requirements which are

\begin{itemize}
 \item (first) pre-image resistance,
 \item second pre-image resistance,
 \item collision resistance,
 \item pseudo randomness, and the
 \item avalanche effect.
\end{itemize}

Pre-image resistance, also called the ``one way property'', means that
for a given hash function $H$ and a hash value $H(x)$, it is
computationally infeasible to find $x$.~\cite{SG2012} For example,
since in Anastasis we derive the key to encrypt the personal details
required for user authentication (e.g. the mobile phone number for
authentication via SMS) using functions based on hash functions (see
HKDF), it is very important that you cannot derive the corresponding
input values from the key.

The second pre-image resistance is described by following: For a given
hash function $H$ and a hash value $H(x)$, it is computationally
infeasible to find $x$ and $x'$ such that $H(x) = H(x')$ and $x \not=
x'$.~\cite{SG2012} In Anastasis hash functions also are involved in
signing our so called recovery document. Hence an attacker should not
be able to create a malicious recovery document with the same hash
value as the original one.

The definition of collision resistance slightly differs from the
second pre-image resistance: For a given hash function $H$, it is
computationally infeasible to find a pair $x, y$ such that $H(x) =
H(y)$ \cite{SG2012}.
%CG: the text below does NOT related to collision resistance!
%As we are using HKDFs for deriving keys in
%Anastasis, an attacker should not be able to find some other input
%values also leading to the same keys we use.
Anastasis does not rely upon collision resistance in its use of hash
functions. % CG: at least no case comes to mind for me right now...

A cryptographic hash function should also behave as a pseudo random
function. This means that although a hash function is purely
deterministic, the output must not be predictable.

The avalanche effect describes the property of an algorithm that
causes a significant change of the output value, usually a bit
flipping of more than half the output is desired, if the input is
changed slightly (for example, flipping a single bit).~\cite{RK2011}
The more bits are flipping in the output value the higher the entropy
of the randomness of the hash function.

There are many applications for cryptographic hash functions. For
example, you can store the hash value of a passphrase instead of the
passphrase itself in a computer to protect the passphrase. Another
important application is verification of message integrity: Before and
after transmission of a message one can calculate the hash values of
it and compare hashes later to determine if the message changed during
transmission.

In Anastasis we use SHA-512~\cite{GJW2011} for fast hash functions.

\subsubsection{HMAC}

When it comes to integrity of messages during communication of two
parties over an insecure channel Keyed-Hash Message Authentication
Codes (HMAC) are used as check values. An HMAC function is based on a
hash function and takes two arguments, a key $K$ and a message $M$:

$HMAC_{K}(M) = H(K \oplus opad,H(K \oplus ipad, M))$ with "ipad" and
"opad" being constants which fill up the key $K$ to the blocksize of
the hash function~\cite{BCK1996}. The blocksize of a modern hash
function like SHA-512 is 64 bytes.

\subsubsection{HKDF}

A HKDF is a key derivation function (KDF) based on HMAC. A KDF ``is a
basic and essential component of cryptographic systems: Its goal is
to take a source of initial keying material, usually containing some
good amount of randomness, but not distributed uniformly or for which
an attacker has some partial knowledge, and derive from it one or more
cryptographically strong secret keys''~\cite{krawczyk2010}.

Anastasis uses HKDFs based on SHA-512 to derive symmetric keys for
encryption.

\subsubsection{Argon2}

Hash functions like SHA-512 are designed to be very fast. Therefore
passwords being stored using this kind of hash are vulnerable to
dictionary attacks with new hardware architectures like
FPGAs~\cite{trimberger2012} and dedicated ASIC~\cite{madurawe2006}
modules. But those architectures ``experience difficulties when
operating on large amount of memory''~\cite{BDK2016}.

In contrast to standard hash functions there are functions designed to
be memory-hard. Argon2 is such a memory-hard function that won the
Password Hashing Competition in 2015. It minimizes time-memory
tradeoff~\cite{stamp2003} and thus maximizes the costs to implement an
ASIC for given CPU computing time~\cite{BDK2016}. Aside from the fact
that Argon2 makes dictionary attacks much harder, Argon2 can be used
for another feature too: Memory-hard schemes like Argon2 are very
useful for key derivation from low-entropy sources~\cite{BDK2016}.

Argon2 is used in Anastasis to derive an identifier for the user from
the user's attributes, which serve as low-entropy inputs.


\subsection{Secret sharing}

Secret splitting, also known as secret sharing, is a technique for
distributing a secret amongst multiple recipients. This is achieved by
assigning a share of the secret to each recipient. By combining a
sufficient number of those shares, it is possible to reconstruct the
secret.  In a secret sharing theme the recipients of a share often are
called \textit{players}. The figure who gives a share of the secret to
the players is called \textit{dealer}.

In Anastasis the user is the trusted dealer who splits the secret and
also reconstructs it.

\subsubsection{Shamir's secret sharing} \label{sec:rel:shamir}

The algorithm ``Shamir's secret sharing'' is probably the most well
known secret sharing scheme. It ``divide[s] data D into n pieces in
such a way that D is easily reconstructible from any k pieces, but
even complete knowledge of $k - 1$ pieces reveals absolutely no
information about D''~\cite{shamir_sharing}.

Shamir’s simple secret sharing scheme has two key limitations. First,
it requires a trusted dealer who initially generates the secret to be
distributed, and second the shares are not verifiable during
reconstruction. Therefore, malicious shareholders could submit corrupt
shares to prevent the system from reconstructing the secret --- without
these corrupt shareholders being detectable as malicious. Furthermore,
the dealer distributing the shares could be corrupt and distribute
some inconsistent shares to the others. Also, in some scenarios the
dealer cannot be trusted with the knowledge of the original core
secret.

Additionally, Shamir's secret sharing is inflexible because it is a
simple $k$-out-of-$n$ threshold scheme.  While this makes the scheme
reasonably efficient even for big values of $n$, efficiency with
respect to a large number of escrow providers and authorization
procedures is not important for Anastasis: it is already difficult to
conceive users providing more than a handful of authentication methods
(Section~\ref{sec:rel:authentication} describes common choices.)

For Anastasis, we thus decided to opt for more flexible approach that
allows complex policies for recovery authorization, instead of only
$k$-out-of-$n$. Each user of Anastasis is also able to decide which
combinations of \textit{players}, which in case of Anastasis are the 
escrow providers, shall be permitted.

\subsubsection{Verifiable secret sharing}

Verifiability can be achieved by using so called commitment schemes
like the Pederson commitment. It allows ``to distribute a secret to n
persons such that each person can verify that he has received correct
information about the secret without talking with other
persons''~\cite{pedersen_sharing_0}. In his paper ``A Practical Scheme
for Non-interactive Verifiable Secret
Sharing''~\cite{feldman_sharing}, Paul Feldman combines the two
schemes Shamir Secret Sharing and Pederson commitment. His algorithm
for verifiable secret sharing (VSS), allows each recipient to
verify the correctness of their share. But like in the Shamir Secret
Sharing scheme, the dealer in the VSS scheme
also can't be trusted with the knowledge of the original core secret.

Because in Anastasis each user can act as their own trusted dealer,
the shares must not be verified and therefore Anastasis do not need
any form of VSS.

\subsubsection{Distributed key generation}

Distributed key generation (DKG) algorithms solve the problem of
needing a trustworthy dealer by instead relying on a threshold of
honest persons for key generation. Contrary to the above-mentioned
schemes, in distributed key generation algorithms every participant is
involved in key generation.  The Pederson DKG is such ``a secret
sharing scheme without a mutually trusted
authority''~\cite{pedersen_sharing_5.2}. Basically, this DKG works as
follows: First, each involved party generates a pre-secret and
distributes it to all parties using the verifiable secret sharing
scheme of Feldman.  Afterwards, each party recombines the received
shares, including its own pre-secret, to a share of the main
secret. The main secret can be reconstructed by summing up each
recombination of the shared pre-secrets.

Because in Anastasis each user can act as their own trusted dealer, we
also do not worry about the dealer learning the user's key and hence
Anastasis do not need any form of DKG.

\subsection{Authentication} \label{sec:rel:authentication}

To build a secure authentication procedure, today multi-factor
authentication is the standard~\cite{multifactor_authentication}. A
single authentication method by itself is usually vulnerable.
Multi-factor authentication combines multiple authentication
procedures to enhance the security of the system.

During procedure of some authentication methods a so called token is 
sent to the user. The user than has to provide the token to authorize.\\
The token should be a randomly generated passphrase which has at 
least 128 bits of entropy. It is best practice for a token to have an 
expiration time, although this is not relevant for security of Anastasis.\\

Anastasis is designed to use a wide range of authentication methods to
authenticate its users. Even though the user in Anastasis is free to
specify only one authentication method, we strongly recommend the use
of multi-factor authentication, typically using different
authentication methods at different providers.

A short overview of common authentication methods and issues with
each of them is presented here.

\subsubsection{Password authentication}

Password authentication is probably the most widely used
authentication procedure. But as studies show the procedure has its
drawbacks~\cite{authentication_methods_review}. For example the
handling of the passwords, like storage or transmission, often is done
poorly. Another problem is that the user must remember his
password. Therefore the password is limited to the capabilities of the
user to remember it. Thus people tend to use passwords with low
entropy. Those passwords are vulnerable to brute force attacks or
dictionary attacks. Another problem using passwords is the possibility
of replay attacks: A password can be stolen by an eavesdropper during
online transmission and used by the attacker.

Because passwords can be forgotten, we do not recommend using this
method for provider-authentication in Anastasis. Users could easily
add a passwords into their set of ``invariant'' attributes used to
derive the identity key, and then would automatically obtain all of
the possible benefits (and drawbacks) from using a password.
Specifically, they must make sure that the password cannot be
forgotten, even if it means that the password has low entropy.

\subsubsection{Secure question}

Similar to password authentication the use of an authentication method
based on a secure question requires the user to remember the correct
answer to a specific question. The difference here is that the
question provides a context that helps the user to remember the answer
and the user does not necessarily need to memorize something
new~\cite{just2004}.

There are several variations to implement authentication using a
secure question:

\begin{itemize}
 \item The questions and answers are predefined.
 \item Just the questions are predefined.
 \item The user is free to create custom questions and answers.
\end{itemize}

The first option is the easiest one. But predefining the answers has
the disadvantage being impersonal and inflexible. The questions must
inevitably be general, which may allow an attacker to obtain answers
by collecting public information about the victim, or even simply
solving the challenge by brute-forcing trying all possible choices.
Therefore the first option is not ideal.

The second option is more applicable but has some drawbacks, too. For
example there may be questions whose answers have multiple syntactic
representations (for example, ``St.'' versus
``Street'')~\cite{just2004}. Another problem could be a question whose
answer may change over time. Asking for the favourite actor for
example could be problematic. In addition, there is a challenge to
define questions for all kind of people. Some people for example could
not answer to the question, what the name of their pet is, because
they do not have one.

In case of the third option, we have all of the issues of the second
one, but additionally there is the difficulty for the user to ask
creative questions. A good question should only be answerable by the
user. Also, it would be perfect to have the attacker on the wrong
track by using ambiguous questions with word plays the adversary
cannot easily comprehend.

Authentication using a secure question requires checking the validity
of an answer that may include private personal information.
Consequently, Anastasis does not store the answers of secure questions
in cleartext. Instead, Anastasis only stores the hash value of a
(salted) answer.  Thus the user only has to provide the hash value of
the answer and not disclose the answer itself.

\subsubsection{SMS authentication}

Another way to authenticate users that have a mobile phone is to use
SMS authentication. The most popular use case is the so called Mobile
TAN used to authorize online banking transactions. A Mobile TAN is an
SMS based One-Time Password (OTP), short SMS OTP. SMS OTPs ``were
introduced to counter phishing and other attacks against
authentication and authorization of Internet
services''~\cite{MBSS2013}.

However, SMS authentication is not very secure, as it relies on the
security of the mobile network, which has various
vulnerabilities~\cite{rieck_detection}. There are also specialized
mobile trojans which are used to eavesdrop on these messages directly
on the user's mobile device.

While likely not as sensitive as answers to security questions, we
still consider user's phone numbers as private information that
deserves protection.  Naturally, a service authenticating the user
needs the phone number to send a message to the user during SMS
authentication.

Hence, Anastasis providers have to learn the phone number during SMS
authentication.  However, we can use cryptography to ensure that the
provider only gets the keys to decrypt the phone number when the
authentication process is started by the user as part of a recovery
operation. Thus, a compromise of the provider's database would not
directly reveal the phone numbers to the attacker.


\subsubsection{E-mail authentication}

Authentication by email is similar to SMS authentication. Here,
the user receives a token by email and has to provide it during the
authentication process.

It is important that the email should not already contain the
requested information, so in the case of Anastasis the keyshare.  This
is because the SMTP protocol used for email offers no hard security
assurances. In particular, the email is likely to be stored for a
indefinite period in the user's mailbox, which could be easily
compromised and read by a mailbox provider.~\cite{emailauthowasp}

Like with SMS authentication, Anastasis also encrypts the email
addresses when they are stored at the provider.  The user has to
provide the corresponding decryption key to the server during
the authentication process.


\subsubsection{VideoIdent}

VideoIdent uses a video chat to verify the identity of a user. The
user needs to show their face using a camera to an employee of the
VideoIdent service. The service then verifies the identity of the user
by comparing the video stream to a picture of the
user~\cite{pohlmann2017}.

Prerequisites for error-free identification are a video camera with
good video quality and a high-resolution image of the user on which
the face can be clearly seen. The user should also not change their
outward appearance too much over time. For example, growing or
trimming a beard could lead to the VideoIdent-service employee not
being able to recognise a user with sufficient confidence.

For an attacker who looks similar to the user, there is a chance that
the employee incorrectly confirms the identification.

%CG: that's IMO then e-mail based verification, should not mix
%    the two: this is basically multi-factor, so I'd leave it out here!
%Therefore, some interaction of the user is needed like for example
%telling the employee a short code which has been sent right before to
%the user by mail.

In Anastasis, pictures of users for VideoIdent authentication are
considered private information stored encrypted at the providers.
During the authentication process, the user has to provide the correct
key for decryption to the service.

\subsubsection{PostIdent}

It is also possible to sent a verification code to the user by
physical mail. A major drawback of this authentication method is
that it has high latency, and there is also the possibility that
physical mail gets intercepted or lost during transmission.

Anastasis providers using PostIndent would not store the address of
their users in cleartext. Instead the address is encrypted by the user
and the provider would receive the key to decrypt the address only
during the authentication process.

\subsubsection{Biometric authentication}

Another way of authenticating is the biometric
approach~\cite{biometric_auth}. Biometric authentication is based on
``something you are'', like your iris or your fingerprint.

Biometric authentication is highly problematic because the attributes
are invariant and frequently shared involuntarily.  Unlike passphrases
or phone numbers, users cannot change their genome or fingerprint in
case their private biometric information is exposed.  Furthermore,
there are credible threats against biometric authentication, in
paritcular there are documented inexpensive attacks against
fingerprint and iris scan authentication. For example, a member of the
German CCC e.V. was able to generate replicas from Angela Merkel's
iris and Ursula von der Leyen's fingerprint~\cite{ccc_merkel}.



\subsection{Existing solutions for key recovery}

This section introduces some existing solutions for key recovery and
why they are problematic.


\subsubsection{Coinbase}

Coinbase\footnote{\url{https://www.coinbase.com/}} is a global digital
asset exchange company, providing a venue to buy and sell digital
currencies. Coinbase also uses wallets secured with private keys. To
recover this private key the user has to provide a 12 words recovery
phrase.

Coinbase offers a solution to securely deposit this recovery phrase
onto the users Google Drive or iCloud.~\cite{coinbase} The security
here lies within the Google or iCloud account and another password
used to encrypt the security phrase. The problem here is that this
approach undermines confidentiality, as encrypting a strong key with a
weak key simply reduces the security to that of the weaker key.

\subsubsection{MIDATA}

MIDATA is a project that aims to give patients back control over their
medical data and to enable them to share their data only with those
they trust.\footnote{\url{https://www.midata.coop/}} In case a patient
lost their device with the MIDATA-application and also forgot their
MIDATA password, MIDATA provides a key recovery system using the
Shamir Secret Sharing scheme (as described in
Section~\ref{sec:rel:shamir}).

In their case, a few ``persons working at MIDATA have generated a
public-private key pair (Recovery key) on their own computer. They
keep the private recovery key for themselves and never share it. The
public keys are made public so that the apps can also access
them''~\cite{midata}. Using Shamir's Secret Sharing the MIDATA
application splits the user's app private key into 5 parts which are
encrypted with one of the published recovery keys. The encrypted parts
are then stored into the MIDATA server. During the recovery process at
least two of the 5 parts need to be decrypted by the persons owning
the private key part of the recovery key. ``The decrypted parts are
sent to the server and {\em the server} may now reconstruct the app
private key if enough parts of the key have been
decrypted''~\cite{midata}. (Emphasis ours.)

The security of MIDATA as described in ``Patient empowerment in IoT
for eHealth - How to deal with lost keys?''~\cite{midata} is broken in
three ways:

\begin{enumerate}
 \item The password is reconstructed at {\em the server}, not on the
   patients device. An administrator of the server could thus
   access the recovered password at that time.  It would be better
   to reconstruct the password only on the patients device.
 \item It is not clear which authentication methods the persons
   working for MIDATA use for their decisions and activities regarding
   the key recovery. The business process used here could be
   vulnerable, and it is not clear whether multi-factor authentication
   is used. As a result, we worry that it may be possible for an attacker
   to successfully use social engineering via email (or other means)
   to illegitimately trigger a recovery process.
 \item The MIDATA system also does not offer any trust agility~\cite{marlinspike2011}.
   The user is forced to accept the 2-out-of-5 rule with trustees
   provided by MIDATA.
\end{enumerate}