anastasis

design.tex (23369B)

---

 \section{Design} \label{chap:design}
 
 Anastasis is a service that allows the user to securely deposit a {\em core
 secret} with an open set of escrow providers and recover it if the
 secret is lost. The core secret itself is protected from the escrow
 providers by encrypting it with a {\em master key}. The main objective of
 Anastasis is to ensure that the user can reliably recover the core
 secret, while making this difficult for everyone else. Furthermore, Anastasis
 supports situations where the user is unable to reliably remember any secret
 with sufficiently high entropy, so Anastasis does not simply encrypt using some
 other key material in exclusive possession of the user.
 
 To uniquely identify users and to provide a first layer of protection,
 an “unforgettable” identifier is used. This identifier should be
 difficult to guess for anybody but the user. However, the identifier
 is not expected to have sufficient entropy or secrecy to be
 cryptographically secure. Examples for such an identifier would be a
 concatenation of the full name of the user and their social security
 or passport number(s). For Swiss citizens, the AHV number could also
 be used.
 
 \subsection{Overview}
 
 The Figure~\ref{fig:legend_keys_anastasis} shows the legend for the
 illustration of the Anastasis key usage shown in Figure~\ref{fig:keys_anastasis}
 on page~\pageref{fig:keys_anastasis} and in
 Figure~\ref{fig:truth_keys} on page~\pageref{fig:truth_keys}.
 The Figure~\ref{fig:keys_anastasis} gives an overview of the keys used in Anastasis. It also shows how they are created and used.
 Figure~\ref{fig:truth_keys} shows how the keys to sign the (encrypted) truth
 data used during authentication are generated. The truth seed(s) used in
 Figure~\ref{fig:truth_keys} are part of the recovery document.
 \newline
 \begin{figure}[H]
 	\centering
 	\includegraphics[scale=0.48]{images/legend_keys_anastasis.png}
 	\caption{Legend of Figure~\ref{fig:keys_anastasis}} on page~\pageref{fig:keys_anastasis}
 	\label{fig:legend_keys_anastasis}
 \end{figure}
 
 \begin{figure}[H]
 	\centering
 	\includegraphics[scale=0.48]{images/keys_anastasis.png}
 	\caption{Secrets used in Anastasis}
 	\label{fig:keys_anastasis}
 \end{figure}
 
 \noindent In the following the keys shown in the Figure~\ref{fig:keys_anastasis} on
 page~\pageref{fig:keys_anastasis} are explained:
 
 \begin{description}
 	\item[kdf id] {The {\em kdf id} is derived from the user attributes and a
 	randomly generated public and constant salt value provided by the escrow provider using Argon2. It is used to derive
 	the {\em private account key}, the {\em symmetric key 1} and the {\em symmetric key 2}.}
 	\item[private account key] {The {\em private account key} is used to sign the {\em encrypted
 	recovery document}. It is derived from the {\em identity key} using {\em HKDF-1}}.
 	\item[public account key] {The {\em public account key} is derived from its corresponding
 	{\em private account key}. It used to verify the signature of the {\em encrypted recovery
 	document} and also is the identifier of the user which is needed by the provider.}
 	\item[symmetric key 1] {The {\em symmetric key 1} is derived from the {\em identity key} using
 	{\em HKDF-2}. It is used to encrypt and decrypt the {\em encrypted recovery document} which is stored by
 	the provider.}
 	\item[symmetric key 2] {The {\em symmetric key 2} is derived from the {\em identity key} using
 	{\em HKDF-3}. It is used to encrypt and decrypt the different {\em encrypted key shares} which
 	are stored by the escrow providers.}
 	\item[truth key] {The {\em truth key} is randomly generated for each {\em encrypted authentication data}
 	  and is stored within the {\em encrypted recovery document}. It may later be disclosed by the user to
           the escrow provider to let it decrypt the {\em encrypted authentication data} which allows the provider
           to then run the recovery authorization process.}
 	\item[master key] {The {\em master key} is randomly generated and is used to encrypt and decrypt the
 	{\em encrypted core secret} which is stored within an {\em encrypted recovery document}. The {\em encrypted master key} also is stored within the {\em encrypted recovery document}.}
 	\item[policy key] {The {\em policy keys} are used for encryption and decryption of the {\em encrypted master key}. A {\em policy key} is constructed by hashing a specific combination of {\em key shares} specified by the
 	user. For hashing SHA512 is used here.}
 \end{description}
 \newpage
 
 \begin{figure}[H]
 	\centering
 	\includegraphics[scale=0.48]{images/truth_anastasis.png}
 	\caption{Key generation for signing of encrypted ``Truth'' data in Anastasis}
 	\label{fig:truth_keys}
 \end{figure}
 
 \noindent In the following the keys shown in the Figure~\ref{fig:truth_keys} on
 page~\pageref{fig:truth_keys} are explained:
 \begin{description}
 \item[truth seed] {Clients generate a random {\em truth seed} for each truth
   which is stored in the encrypted recovery document.}
 \item[private truth key] {{\em Private keys} are derived per truth upload. They
   are used to sign the uploaded data. This way, the escrow provider
   can later prove that they preserved the data correctly. We use EdDSA~\cite{josefsson2017} for
   the signatures.}
 \item[public truth key] {{\em Public keys} are used to identify the truth
   in the provider's database. Providers only store the first truth upload with
   a valid signature. Changes to truth are thus not possible, clients must
   create a fresh seed for every upload.}
  \end{description}
 
 
 
 \subsection{Adversary model}
 
 The adversary model of Anastasis has two types of adversaries: {\em
   weak adversaries} which do not know the user’s identifier (the {\em
   kdf id}), and {\em strong adversaries} which somehow do know a
 user’s identifier. Against weak adversaries, the system guarantees
 full confidentiality, except for a provider-specific public account
 key which links certain requests from the same user, and the data necessary
 for authentication. The latter is only disclosed to the providers when
 the user requests key recovery. Weak adversaries cannot break
 confidentiality even if all escrow providers are part of a conspiracy
 of weak adversaries.  For strong adversaries, breaking confidentiality
 of the core secret still requires that a sufficient subset of the
 Anastasis escrow providers must have colluded with the strong
 adversary. The user can specify a set of policies which determine
 which Anastasis escrow providers would need to collude to break
 confidentiality. These policies also set the bar for the user to
 recover their core secret.
 
 Anastasis providers are also not individually trusted to provide
 availability or authenticity. Users can specify multiple policies, and
 satisfying any one of the policies would allow them to recover their
 core secret assuming the subset of providers specified in the policy
 is available (and preserved the authenticity of the data).  As clients
 sign their uploads, they can verify the authenticity of the data
 returned by checking the signatures.  Only strong adversaries are able
 to forge signatures, so they could create fraudulent recovery
 documents and/or key shares resulting in invalid restored core
 secrets. However, because uploads are never destructive, strong
 adversaries can only succeed in breaking availability if they collude
 with a subset of escrow providers that are present in all policies
 selected by the user.
 
 Thus, users can improve confidentiality by having many different
 escrow providers in their policies, and improve availability by having
 many policies with few escrow providers. Anastasis does not resolve
 this trade-off, but allows users to make individual choices and gives
 them agility with respect to the parties whom they offer their
 trust, resulting in trust agility~\cite{marlinspike2011}.
 
 
 \subsection{Encryption of the core secret}
 
 The {\em core secret} of the user is (AES)~\cite{heron2009} encrypted using a symmetric
 {\em master key}.  Recovering the master key requires the user to
 satisfy a {\em policy}. Policies specify a set of escrow methods, each
 of which leads the user to a {\em key share}. Combining those key
 shares (by hashing) allows the user to obtain a policy key, which can
 be used to decrypt the master key.  There can be many policies,
 satisfying any of these will allow the user to recover the master key.
 
 Which escrow methods are combined into which policies and which
 providers are involved can be different for each user. As users are
 unlikely to remember all the details, Anastasis needs a way to
 remember the specific configuration a user made.
 
 This process description is provided in a {\em recovery document}.
 
 % Figure~\ref{fig:recoverydoc} gives an example for a the contents of
 % a recovery document.
 % FIXME: actually include example!
 
 
 \subsection{The recovery document}
 
 A {\em recovery document} includes all the information a user needs to
 recover access to their core secret. It primarily identifies a set of
 {\em encrypted key shares} which have been entrusted to different
 Anastasis providers. For each key share, the recovery document
 specifies the respective Anastasis provider and also prescribes the
 {\em authentication method}, which specifies how the user should
 convince the Anastasis server that they are authorized to retrieve the
 encrypted key share.  Authentication methods can for example include
 SMS-based verification, video-identification or a security question.
 
 For each authentication method, specific Anastasis providers are separately
 provided (see Section~\ref{sec:truth}) with the associated {\em encrypted key
   share} and (separately encrypted) {\em authentication
   data}. Anastasis operators may learn the authentication data during
 the recovery process to authenticate the user. Examples for
 authentication data would be a phone number (for SMS), a picture of
 the user (for video identification), or the (hash of) a security
 answer. A strong adversary is assumed to be able to learn the
 authentication data, while weak adversaries must not (except if they
 are the provider and then they may learn it only during key recovery).
 
 The recovery document also specifies {\em policies}, which describe
 the combination(s) of the key shares (and thus authentication
 processes) that would suffice to obtain access to the core secret. For
 example, a policy could say that the authentication methods ``$A$ and
 $B$'' suffice, and a second policy may permit ``$A$ and $C$''. A
 different user may choose to use the policy that ``$A$ and $B$ and
 $C$'' are all required. Anastasis imposes no limit on the number of
 policies in a recovery document, or the set of providers or
 authentication methods involved in guarding a user’s secret.
 
 Weak adversaries must not be able to deduce information about a user’s
 recovery document (except for meta data such as its length or
 approximate creation time, which may be exposed to an adversary which
 monitors the user’s network traffic or operates an escrow provider).
 
 
 \subsection{Identity-derived encryption}
 
 To start, a user provides their private (alas not really secret),
 unique and unforgettable user attributes as a seed to identify their
 account. For example, this could be a social security number together
 with their full name. Specifics may depend on the cultural context, in
 this document we will simply refer to this information as the
 {\em user attributes}.
 
 For each Anastasis provider, a {\em kdf id} key is derived from the
 user’s attributes and a provider salt using Argon2~\cite{BDK2016}, a
 computationally expensive cryptographic hash function. Using an
 expensive hash algorithm is assumed to make it harder for a weak
 adversary to determine user attributes by brute force guessing.  The
 salt ensures that the keys for the same user cannot be easily
 correlated across the various Anastasis servers.  However, it is
 assumed that a strong adversary performing a targeted attack can
 compute the {\em kdf id}s.
 
 The listing in Figure~\ref{fig:argon2} provides pseudo-code for
 the computation of the {\em kdf id}. The inputs are:
 
 \begin{description}
 	\item[attributes] {The personal attributes provided by the user.}
 	\item[server\_salt]{The salt from the Anastasis provider.}
 	\item[keysize]{The desired output size of the KDF, here 32 bytes.}
 \end{description}
 
 \begin{figure}[H]
 \begin{lstlisting}
 user_identifier_derive(attributes, server_salt, keysize)
 {
   kdf_id = Argon2(attributes, server_salt, keysize)
   return kdf_id
 }
 \end{lstlisting}
 \caption[Use of Argon2 to derive user attributes]{The user's attributes are hashed with Argon2, to provide a
   kdf\_id which will be used to derive other keys later. The hash must
   also be made over the respective provider's server\_salt. This
   ensures that the kdf\_id is different on each server. The use of
   Argon2 and the respective server\_salt are intended to make it
   difficult to brute-force kdf\_id values and help protect user’s
   privacy. Also this ensures that the kdf\_ids on every server
   differs. However, we do not assume that the identifier or the
   kdf\_id cannot be determined by an adversary performing a targeted
   attack, as a user’s identifier is likely to always be known to state
   actors and may likely also be available to other actors.}
 \label{fig:argon2}
 \end{figure}
 
 Anastasis derives symmetric key material --- but not the master secret --- from the {\em kdf id} using different HKDFs~\cite{krawczyk2010}.
 
 When confidential data --- such as the recovery document or the truth
 --- is uploaded to an Anastasis server, the respective payload is
 encrypted using AES-GCM with the respective symmetric key and
 initialization vector derived key material as shown in
 Figure~\ref{fig:keys_anastasis} and a high-entropy nonce.  The nonce
 and the GCM tag are prepended to the ciphertext before being uploaded
 to the Anastasis server. This is done whenever confidential data is
 stored with the server, so both for encrypted authentication data
 (\texttt{/truth} uploads) and encrypted recovery documents
 (\texttt{/policy} uploads).
 
 To ensure that the key derivation for the encryption of the recovery
 document differs fundamentally from that of an individual key share,
 we use different salts for different types of operations (“erd” and
 “eks” respectively):
 
 \begin{lstlisting}
 encryption_key_create(kdf_id, salt, nonce)
 {
 iv, key = HKDF (kdf_id, nonce, salt, keysize + ivsize)
 return iv,key
 }
 \end{lstlisting}
 
 \begin{description}
 	\item[HKDF()] {The HKDF-function uses to phases: First we use HMAC-SHA512 for the extraction phase, then HMAC-SHA256 is used for expansion phase.}
 	\item[kdf\_id] {Hashed identifier.}
 	\item[keysize] {Size of the AES symmetric key, here 32 bytes.}
 	\item[ivsize] {Size of the AES GCM IV, here 12 bytes.}
 	\item[nonce] {32-byte nonce, must never match “ver” (which it cannot as the length is different). Of course, we must avoid key reuse. So, we must use different nonces to get different keys and ivs (see below).}
 	\item[key] {Symmetric key which is later used to encrypt the documents with AES256-GCM.}
 	\item[iv] {IV which will be used for AES-GCM.}
 \end{description}
 
 
 \begin{lstlisting}
 encrypt(kdf_id, data, salt)
 {
 nonce = generate_random_bytes(32)
 iv, key = encryption_key_create(kdf_id, salt, nonce)
 encrypted_data, aes_gcm_tag =  AES256_GCM(data, iv, key)
 encrypted_data = nonce + aes_gcm_tag + encrypted_data
 return encrypted_data
 }
 
 key_share_encrypt(kdf_id, key_share)
 {
 encrypted_key_share = encrypt(kdf_id, key_share, "eks")
 return encrypted_key_share
 }
 
 recovery_document_encrypt(kdf_id, recovery_document)
 {
 encrypted_recovery_document =
 encrypt(kdf_id, recovery_document, "erd")
 return encrypted_recovery_document
 }
 
 \end{lstlisting}
 
 \begin{description}
 	\item[encrypted\_recovery\_document] {The encrypted recovery document which contains the authentication methods, policies and the encrypted core secret.}
 	\item[encrypted\_key\_share] {The encrypted key\_share which the escrow provider must release upon successful authentication.}
 	\item[nonce] {Nonce which is used to generate keys and ivs which are used for the encryption. The nonce must contain either eks or erd.}
 	\item[encrypted\_data] {The encrypted data contains the either a recovery document or a key share which was encrypted and the nonce and the aes\_gcm\_tag. To be able to decrypt it the first 32 Bytes are the nonce and the next 12 Bytes are the aes\_gcm\_tag.}
 \end{description}
 
 
 \subsection{Authenticity of recovery documents}
 
 \texttt{/policy/} requests are used to upload new encrypted recovery
 documents. For users to authorize \texttt{/policy} operations, we need
 an account key pair.  Thus, in addition to the symmetric keys, an
 EdDSA-based {\em account key} is derived from the {\em kdf id} (see
 Figure~\ref{fig:keys_anastasis}) and used to identify the ``account''
 of the user at each Anastasis server.  EdDSA public keys are always
 points on Curve25519 and represented using the standard 256-bit
 Ed25519 compact format. The binary representation is converted to
 Crockford Base32 when transmitted inside JSON or as part of URLs in
 the RESTful API of Anastasis (see Section~\ref{sec:serverarch}).
 EdDSA signatures are also provided in Crockford Base32-encoding and
 transmitted using the HTTP header
 \texttt{Anastasis-Account-Signature}.  Encrypted recovery documents
 are stored using the public account key as the identifier.
 
 As the account keys are derived from the {\em kdf id} --- which strong
 adversaries are assumed to know ---, we cannot assure that the corresponding
 private account key is truly secret. Thus, policy operations must
 never be destructive: A strong adversary can derive the private key
 and access (and with the {\em kdf id} also decrypt) the user’s
 recovery document (but not the core secret!), and also upload a new
 version of the encrypted recovery document. However, because uploads
 are not destructive, even a strong adversary cannot delete an existing
 version and thus cannot break availability.
 
 For the generation of the private key we use the {\em kdf id} as the
 entropy source, hash it to derive a base secret which will then be
 processed to fit the requirements for EdDSA private keys. From the
 private key we can then generate the corresponding public key. Here,
 the string “ver” is used for the salt value for the HKDF to ensure
 that the result differs from other cases where we hash {\em kdf id}:
 
 \begin{lstlisting}
 eddsa_keys_create (kdf_id, salt, keysize)
 {
   ver_secret = HKDF(kdf_id, salt, keysize)
   eddsa_priv = ver_secret
   eddsa_pub = get_eddsa_pub(eddsa_priv)
   return eddsa_priv, eddsa_pub
 }
 \end{lstlisting}
 
 \begin{description}
 	\item[HKDF()] {The HKDF-function uses to phases: First we use HMAC-SHA512 for the extraction phase, then HMAC-SHA256 is used for expansion phase.}
 	\item[kdf\_id] {Hashed identifier.}
 	\item[salt] {Is used that different keys are generated, the salt here is "ver".}
 	\item[key\_size] {Size of the output, here 32 bytes.}
 	\item[ver\_secret] {Derived key from the kdf\_id, serves as intermediate step for the generation of the private key.}
 \end{description}
 
 \begin{description}
 	\item[eddsa\_priv] {The generated EdDSA private key.}
 	\item[eddsa\_pub] {The generated EdDSA public key.}
 \end{description}
 
 
 \subsection{Account signatures}
 
 The EdDSA account keys are used to sign the encrypted recovery
 document sent from the client to the server.
 
 % FIXME: "everything"? I don't think we can sign the encrypted truth
 % with the eddsa_priv, as that would link the truth to the ERD.
 % We need ANOTHER account key here, one per truth + provider?
 
 \begin{lstlisting}
 (anastasis-account-signature) = eddsa_sign(h_body, eddsa_priv)
 ver_res =
   eddsa_verifiy(h_body, anastasis-account-signature, eddsa_pub)
 \end{lstlisting}
 
 \begin{description}
 	\item[anastasis-account-signature] {Signature over the SHA-512 hash of the body using the purpose code TALER\_SIGNATURE\_ANASTASIS\_POLICY\_UPLOAD (1400) (see GNUnet EdDSA signature API for the use of purpose).}
 	\item[h\_body] {The hashed body.}
 	\item[ver\_res] {A Boolean value. True: Signature verification passed, False: Signature verification failed.}
 \end{description}
 
 \noindent
 When requesting \texttt{/policy} downloads, the client must also provide a signature:
 \begin{lstlisting}
 (anastasis-account-signature) = eddsa_sign(version, eddsa_priv)
 ver_res =
   eddsa_verifiy(version, anastasis-account-signature, eddsa_pub)
 \end{lstlisting}
 
 \begin{description}
 	\item[anastasis-account-signature] {Signature over the SHA-512 hash of the body using the purpose code TALER\_SIGNATURE\_ANASTASIS\_POLICY\_DOWNLOAD  \\
 	(1401) (see GNUnet EdDSA signature API for the use of purpose).}
 	\item[version] {The version requested as a 64-bit integer, for the “latest version”.}
 	\item[ver\_res] {A Boolean value. True: Signature verification passed, False: Signature verification failed.}
 \end{description}
 
 
 \subsection{Authenticity of truth} \label{sec:truth}
 
 \texttt{/truth/} requests are used to upload encrypted authentication data
 and encrypted key shares to an Anastasis escrow service.  As an additional
 layer of protection, an Anastasis escrow service cannot link truth data to
 policy data, except maybe by observing the timing of the requests.
 
 Anastasis uses EdDSA-based {\em truth key}s to identify truth
 objects. For those, the truth keys are derived from a {\em truth
   seed}, as show in Figure~\ref{fig:truth_keys}.  The private truth
 key is used to authorize the truth upload. The signatures also
 authenticate the encrypted key shares returned from the Anastasis
 provider during recovery.  The signature process for truth is
 analogous to that for accounts.
 
 
 \subsection{Availability considerations}
 
 Anastasis considers two main threats against availability. First, the
 Anastasis server operators must be protected against denial-of-service
 attacks where an adversary attempts to exhaust operator’s
 resources. The API protects against these attacks by allowing
 operators to set fees for expensive operations. Furthermore, all data stored
 comes with an expiration logic, so an attacker cannot force servers to
 store data indefinitely.
 
 A second availability issue arises from strong adversaries that may be
 able to compute the account keys of some user. While we assume that
 such an adversary cannot successfully authenticate against the truth,
 the account key does inherently enable these adversaries to upload a
 new policy for the account. This cannot be prevented, as the
 legitimate user must be able to set or change a policy using only the
 account key. To ensure that an adversary cannot exploit this, policy
 uploads first of all never delete existing policies, but merely create
 another version. This way, even if an adversary uploads a malicious
 policy, a user can still retrieve an older version of the policy to
 recover access to their data. This append-only storage for policies
 still leaves a strong adversary with the option of uploading many
 policies to exhaust the Anastasis server’s capacity. We limit this
 attack by requiring a policy upload to include a reference to a
 payment identifier from a payment made by the user. Thus, a policy
 upload requires both knowledge of the identity and making a
 payment. This effectively prevents and adversary from using the
 append-only policy storage from exhausting Anastasis server capacity.