aboutsummaryrefslogtreecommitdiff
path: root/doc/system-documentation/design.tex
diff options
context:
space:
mode:
Diffstat (limited to 'doc/system-documentation/design.tex')
-rw-r--r--doc/system-documentation/design.tex466
1 files changed, 466 insertions, 0 deletions
diff --git a/doc/system-documentation/design.tex b/doc/system-documentation/design.tex
new file mode 100644
index 0000000..650beb1
--- /dev/null
+++ b/doc/system-documentation/design.tex
@@ -0,0 +1,466 @@
1\section{Design} \label{chap:design}
2
3Anastasis is a service that allows the user to securely deposit a {\em core
4secret} with an open set of escrow providers and recover it if the
5secret is lost. The core secret itself is protected from the escrow
6providers by encrypting it with a {\em master key}. The main objective of
7Anastasis is to ensure that the user can reliably recover the core
8secret, while making this difficult for everyone else. Furthermore, Anastasis
9supports situations where the user is unable to reliably remember any secret
10with sufficiently high entropy, so Anastasis does not simply encrypt using some
11other key material in exclusive possession of the user.
12
13To uniquely identify users and to provide a first layer of protection,
14an “unforgettable” identifier is used. This identifier should be
15difficult to guess for anybody but the user. However, the identifier
16is not expected to have sufficient entropy or secrecy to be
17cryptographically secure. Examples for such an identifier would be a
18concatenation of the full name of the user and their social security
19or passport number(s). For Swiss citizens, the AHV number could also
20be used.
21
22\subsection{Overview}
23
24The Figure~\ref{fig:legend_keys_anastasis} shows the legend for the
25illustration of the Anastasis key usage shown in Figure~\ref{fig:keys_anastasis}
26on page~\pageref{fig:keys_anastasis} and in
27Figure~\ref{fig:truth_keys} on page~\pageref{fig:truth_keys}.
28The Figure~\ref{fig:keys_anastasis} gives an overview of the keys used in Anastasis. It also shows how they are created and used.
29Figure~\ref{fig:truth_keys} shows how the keys to sign the (encrypted) truth
30data used during authentication are generated. The truth seed(s) used in
31Figure~\ref{fig:truth_keys} are part of the recovery document.
32\newline
33\begin{figure}[H]
34 \centering
35 \includegraphics[scale=0.48]{images/legend_keys_anastasis.png}
36 \caption{Legend of Figure~\ref{fig:keys_anastasis}} on page~\pageref{fig:keys_anastasis}
37 \label{fig:legend_keys_anastasis}
38\end{figure}
39
40\begin{figure}[H]
41 \centering
42 \includegraphics[scale=0.48]{images/keys_anastasis.png}
43 \caption{Secrets used in Anastasis}
44 \label{fig:keys_anastasis}
45\end{figure}
46
47\noindent In the following the keys shown in the Figure~\ref{fig:keys_anastasis} on
48page~\pageref{fig:keys_anastasis} are explained:
49
50\begin{description}
51 \item[kdf id] {The {\em kdf id} is derived from the user attributes and a
52 randomly generated public and constant salt value provided by the escrow provider using Argon2. It is used to derive
53 the {\em private account key}, the {\em symmetric key 1} and the {\em symmetric key 2}.}
54 \item[private account key] {The {\em private account key} is used to sign the {\em encrypted
55 recovery document}. It is derived from the {\em identity key} using {\em HKDF-1}}.
56 \item[public account key] {The {\em public account key} is derived from its corresponding
57 {\em private account key}. It used to verify the signature of the {\em encrypted recovery
58 document} and also is the identifier of the user which is needed by the provider.}
59 \item[symmetric key 1] {The {\em symmetric key 1} is derived from the {\em identity key} using
60 {\em HKDF-2}. It is used to encrypt and decrypt the {\em encrypted recovery document} which is stored by
61 the provider.}
62 \item[symmetric key 2] {The {\em symmetric key 2} is derived from the {\em identity key} using
63 {\em HKDF-3}. It is used to encrypt and decrypt the different {\em encrypted key shares} which
64 are stored by the escrow providers.}
65 \item[truth key] {The {\em truth key} is randomly generated for each {\em encrypted authentication data}
66 and is stored within the {\em encrypted recovery document}. It may later be disclosed by the user to
67 the escrow provider to let it decrypt the {\em encrypted authentication data} which allows the provider
68 to then run the recovery authorization process.}
69 \item[master key] {The {\em master key} is randomly generated and is used to encrypt and decrypt the
70 {\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}.}
71 \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
72 user. For hashing SHA512 is used here.}
73\end{description}
74\newpage
75
76\begin{figure}[H]
77 \centering
78 \includegraphics[scale=0.48]{images/truth_anastasis.png}
79 \caption{Key generation for signing of encrypted ``Truth'' data in Anastasis}
80 \label{fig:truth_keys}
81\end{figure}
82
83\noindent In the following the keys shown in the Figure~\ref{fig:truth_keys} on
84page~\pageref{fig:truth_keys} are explained:
85\begin{description}
86\item[truth seed] {Clients generate a random {\em truth seed} for each truth
87 which is stored in the encrypted recovery document.}
88\item[private truth key] {{\em Private keys} are derived per truth upload. They
89 are used to sign the uploaded data. This way, the escrow provider
90 can later prove that they preserved the data correctly. We use EdDSA~\cite{josefsson2017} for
91 the signatures.}
92\item[public truth key] {{\em Public keys} are used to identify the truth
93 in the provider's database. Providers only store the first truth upload with
94 a valid signature. Changes to truth are thus not possible, clients must
95 create a fresh seed for every upload.}
96 \end{description}
97
98
99
100\subsection{Adversary model}
101
102The adversary model of Anastasis has two types of adversaries: {\em
103 weak adversaries} which do not know the user’s identifier (the {\em
104 kdf id}), and {\em strong adversaries} which somehow do know a
105user’s identifier. Against weak adversaries, the system guarantees
106full confidentiality, except for a provider-specific public account
107key which links certain requests from the same user, and the data necessary
108for authentication. The latter is only disclosed to the providers when
109the user requests key recovery. Weak adversaries cannot break
110confidentiality even if all escrow providers are part of a conspiracy
111of weak adversaries. For strong adversaries, breaking confidentiality
112of the core secret still requires that a sufficient subset of the
113Anastasis escrow providers must have colluded with the strong
114adversary. The user can specify a set of policies which determine
115which Anastasis escrow providers would need to collude to break
116confidentiality. These policies also set the bar for the user to
117recover their core secret.
118
119Anastasis providers are also not individually trusted to provide
120availability or authenticity. Users can specify multiple policies, and
121satisfying any one of the policies would allow them to recover their
122core secret assuming the subset of providers specified in the policy
123is available (and preserved the authenticity of the data). As clients
124sign their uploads, they can verify the authenticity of the data
125returned by checking the signatures. Only strong adversaries are able
126to forge signatures, so they could create fraudulent recovery
127documents and/or key shares resulting in invalid restored core
128secrets. However, because uploads are never destructive, strong
129adversaries can only succeed in breaking availability if they collude
130with a subset of escrow providers that are present in all policies
131selected by the user.
132
133Thus, users can improve confidentiality by having many different
134escrow providers in their policies, and improve availability by having
135many policies with few escrow providers. Anastasis does not resolve
136this trade-off, but allows users to make individual choices and gives
137them agility with respect to the parties whom they offer their
138trust, resulting in trust agility~\cite{marlinspike2011}.
139
140
141\subsection{Encryption of the core secret}
142
143The {\em core secret} of the user is (AES)~\cite{heron2009} encrypted using a symmetric
144{\em master key}. Recovering the master key requires the user to
145satisfy a {\em policy}. Policies specify a set of escrow methods, each
146of which leads the user to a {\em key share}. Combining those key
147shares (by hashing) allows the user to obtain a policy key, which can
148be used to decrypt the master key. There can be many policies,
149satisfying any of these will allow the user to recover the master key.
150
151Which escrow methods are combined into which policies and which
152providers are involved can be different for each user. As users are
153unlikely to remember all the details, Anastasis needs a way to
154remember the specific configuration a user made.
155
156This process description is provided in a {\em recovery document}.
157
158% Figure~\ref{fig:recoverydoc} gives an example for a the contents of
159% a recovery document.
160% FIXME: actually include example!
161
162
163\subsection{The recovery document}
164
165A {\em recovery document} includes all the information a user needs to
166recover access to their core secret. It primarily identifies a set of
167{\em encrypted key shares} which have been entrusted to different
168Anastasis providers. For each key share, the recovery document
169specifies the respective Anastasis provider and also prescribes the
170{\em authentication method}, which specifies how the user should
171convince the Anastasis server that they are authorized to retrieve the
172encrypted key share. Authentication methods can for example include
173SMS-based verification, video-identification or a security question.
174
175For each authentication method, specific Anastasis providers are separately
176provided (see Section~\ref{sec:truth}) with the associated {\em encrypted key
177 share} and (separately encrypted) {\em authentication
178 data}. Anastasis operators may learn the authentication data during
179the recovery process to authenticate the user. Examples for
180authentication data would be a phone number (for SMS), a picture of
181the user (for video identification), or the (hash of) a security
182answer. A strong adversary is assumed to be able to learn the
183authentication data, while weak adversaries must not (except if they
184are the provider and then they may learn it only during key recovery).
185
186The recovery document also specifies {\em policies}, which describe
187the combination(s) of the key shares (and thus authentication
188processes) that would suffice to obtain access to the core secret. For
189example, a policy could say that the authentication methods ``$A$ and
190$B$'' suffice, and a second policy may permit ``$A$ and $C$''. A
191different user may choose to use the policy that ``$A$ and $B$ and
192$C$'' are all required. Anastasis imposes no limit on the number of
193policies in a recovery document, or the set of providers or
194authentication methods involved in guarding a user’s secret.
195
196Weak adversaries must not be able to deduce information about a user’s
197recovery document (except for meta data such as its length or
198approximate creation time, which may be exposed to an adversary which
199monitors the user’s network traffic or operates an escrow provider).
200
201
202\subsection{Identity-derived encryption}
203
204To start, a user provides their private (alas not really secret),
205unique and unforgettable user attributes as a seed to identify their
206account. For example, this could be a social security number together
207with their full name. Specifics may depend on the cultural context, in
208this document we will simply refer to this information as the
209{\em user attributes}.
210
211For each Anastasis provider, a {\em kdf id} key is derived from the
212user’s attributes and a provider salt using Argon2~\cite{BDK2016}, a
213computationally expensive cryptographic hash function. Using an
214expensive hash algorithm is assumed to make it harder for a weak
215adversary to determine user attributes by brute force guessing. The
216salt ensures that the keys for the same user cannot be easily
217correlated across the various Anastasis servers. However, it is
218assumed that a strong adversary performing a targeted attack can
219compute the {\em kdf id}s.
220
221The listing in Figure~\ref{fig:argon2} provides pseudo-code for
222the computation of the {\em kdf id}. The inputs are:
223
224\begin{description}
225 \item[attributes] {The personal attributes provided by the user.}
226 \item[server\_salt]{The salt from the Anastasis provider.}
227 \item[keysize]{The desired output size of the KDF, here 32 bytes.}
228\end{description}
229
230\begin{figure}[H]
231\begin{lstlisting}
232user_identifier_derive(attributes, server_salt, keysize)
233{
234 kdf_id = Argon2(attributes, server_salt, keysize)
235 return kdf_id
236}
237\end{lstlisting}
238\caption[Use of Argon2 to derive user attributes]{The user's attributes are hashed with Argon2, to provide a
239 kdf\_id which will be used to derive other keys later. The hash must
240 also be made over the respective provider's server\_salt. This
241 ensures that the kdf\_id is different on each server. The use of
242 Argon2 and the respective server\_salt are intended to make it
243 difficult to brute-force kdf\_id values and help protect user’s
244 privacy. Also this ensures that the kdf\_ids on every server
245 differs. However, we do not assume that the identifier or the
246 kdf\_id cannot be determined by an adversary performing a targeted
247 attack, as a user’s identifier is likely to always be known to state
248 actors and may likely also be available to other actors.}
249\label{fig:argon2}
250\end{figure}
251
252Anastasis derives symmetric key material --- but not the master secret --- from the {\em kdf id} using different HKDFs~\cite{krawczyk2010}.
253
254When confidential data --- such as the recovery document or the truth
255--- is uploaded to an Anastasis server, the respective payload is
256encrypted using AES-GCM with the respective symmetric key and
257initialization vector derived key material as shown in
258Figure~\ref{fig:keys_anastasis} and a high-entropy nonce. The nonce
259and the GCM tag are prepended to the ciphertext before being uploaded
260to the Anastasis server. This is done whenever confidential data is
261stored with the server, so both for encrypted authentication data
262(\texttt{/truth} uploads) and encrypted recovery documents
263(\texttt{/policy} uploads).
264
265To ensure that the key derivation for the encryption of the recovery
266document differs fundamentally from that of an individual key share,
267we use different salts for different types of operations (“erd” and
268“eks” respectively):
269
270\begin{lstlisting}
271encryption_key_create(kdf_id, salt, nonce)
272{
273iv, key = HKDF (kdf_id, nonce, salt, keysize + ivsize)
274return iv,key
275}
276\end{lstlisting}
277
278\begin{description}
279 \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.}
280 \item[kdf\_id] {Hashed identifier.}
281 \item[keysize] {Size of the AES symmetric key, here 32 bytes.}
282 \item[ivsize] {Size of the AES GCM IV, here 12 bytes.}
283 \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).}
284 \item[key] {Symmetric key which is later used to encrypt the documents with AES256-GCM.}
285 \item[iv] {IV which will be used for AES-GCM.}
286\end{description}
287
288
289\begin{lstlisting}
290encrypt(kdf_id, data, salt)
291{
292nonce = generate_random_bytes(32)
293iv, key = encryption_key_create(kdf_id, salt, nonce)
294encrypted_data, aes_gcm_tag = AES256_GCM(data, iv, key)
295encrypted_data = nonce + aes_gcm_tag + encrypted_data
296return encrypted_data
297}
298
299key_share_encrypt(kdf_id, key_share)
300{
301encrypted_key_share = encrypt(kdf_id, key_share, "eks")
302return encrypted_key_share
303}
304
305recovery_document_encrypt(kdf_id, recovery_document)
306{
307encrypted_recovery_document =
308encrypt(kdf_id, recovery_document, "erd")
309return encrypted_recovery_document
310}
311
312\end{lstlisting}
313
314\begin{description}
315 \item[encrypted\_recovery\_document] {The encrypted recovery document which contains the authentication methods, policies and the encrypted core secret.}
316 \item[encrypted\_key\_share] {The encrypted key\_share which the escrow provider must release upon successful authentication.}
317 \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.}
318 \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.}
319\end{description}
320
321
322\subsection{Authenticity of recovery documents}
323
324\texttt{/policy/} requests are used to upload new encrypted recovery
325documents. For users to authorize \texttt{/policy} operations, we need
326an account key pair. Thus, in addition to the symmetric keys, an
327EdDSA-based {\em account key} is derived from the {\em kdf id} (see
328Figure~\ref{fig:keys_anastasis}) and used to identify the ``account''
329of the user at each Anastasis server. EdDSA public keys are always
330points on Curve25519 and represented using the standard 256-bit
331Ed25519 compact format. The binary representation is converted to
332Crockford Base32 when transmitted inside JSON or as part of URLs in
333the RESTful API of Anastasis (see Section~\ref{sec:serverarch}).
334EdDSA signatures are also provided in Crockford Base32-encoding and
335transmitted using the HTTP header
336\texttt{Anastasis-Account-Signature}. Encrypted recovery documents
337are stored using the public account key as the identifier.
338
339As the account keys are derived from the {\em kdf id} --- which strong
340adversaries are assumed to know ---, we cannot assure that the corresponding
341private account key is truly secret. Thus, policy operations must
342never be destructive: A strong adversary can derive the private key
343and access (and with the {\em kdf id} also decrypt) the user’s
344recovery document (but not the core secret!), and also upload a new
345version of the encrypted recovery document. However, because uploads
346are not destructive, even a strong adversary cannot delete an existing
347version and thus cannot break availability.
348
349For the generation of the private key we use the {\em kdf id} as the
350entropy source, hash it to derive a base secret which will then be
351processed to fit the requirements for EdDSA private keys. From the
352private key we can then generate the corresponding public key. Here,
353the string “ver” is used for the salt value for the HKDF to ensure
354that the result differs from other cases where we hash {\em kdf id}:
355
356\begin{lstlisting}
357eddsa_keys_create (kdf_id, salt, keysize)
358{
359 ver_secret = HKDF(kdf_id, salt, keysize)
360 eddsa_priv = eddsa_d_to_a(ver_secret)
361 eddsa_pub = get_eddsa_pub(eddsa_priv)
362 return eddsa_priv, eddsa_pub
363}
364\end{lstlisting}
365
366\begin{description}
367 \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.}
368 \item[kdf\_id] {Hashed identifier.}
369 \item[salt] {Is used that different keys are generated, the salt here is "ver".}
370 \item[key\_size] {Size of the output, here 32 bytes.}
371 \item[ver\_secret] {Derived key from the kdf\_id, serves as intermediate step for the generation of the private key.}
372 \item[eddsa\_d\_to\_a()] {Function which converts the ver\_key to a valid EdDSA private key. Specifically, assuming the value eddsa\_priv is in a 32-byte array “digest”, the function clears and sets certain bits as follows:}
373\end{description}
374
375\begin{lstlisting}
376digest[0] = (digest[0] & 0x7f) | 0x40;
377digest[31] &= 0xf8;
378\end{lstlisting}
379
380\begin{description}
381 \item[eddsa\_priv] {The generated EdDSA private key.}
382 \item[eddsa\_pub] {The generated EdDSA public key.}
383\end{description}
384
385
386\subsection{Account signatures}
387
388The EdDSA account keys are used to sign the encrypted recovery
389document sent from the client to the server.
390
391% FIXME: "everything"? I don't think we can sign the encrypted truth
392% with the eddsa_priv, as that would link the truth to the ERD.
393% We need ANOTHER account key here, one per truth + provider?
394
395\begin{lstlisting}
396(anastasis-account-signature) = eddsa_sign(h_body, eddsa_priv)
397ver_res =
398 eddsa_verifiy(h_body, anastasis-account-signature, eddsa_pub)
399\end{lstlisting}
400
401\begin{description}
402 \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).}
403 \item[h\_body] {The hashed body.}
404 \item[ver\_res] {A Boolean value. True: Signature verification passed, False: Signature verification failed.}
405\end{description}
406
407\noindent
408When requesting \texttt{/policy} downloads, the client must also provide a signature:
409\begin{lstlisting}
410(anastasis-account-signature) = eddsa_sign(version, eddsa_priv)
411ver_res =
412 eddsa_verifiy(version, anastasis-account-signature, eddsa_pub)
413\end{lstlisting}
414
415\begin{description}
416 \item[anastasis-account-signature] {Signature over the SHA-512 hash of the body using the purpose code TALER\_SIGNATURE\_ANASTASIS\_POLICY\_DOWNLOAD \\
417 (1401) (see GNUnet EdDSA signature API for the use of purpose).}
418 \item[version] {The version requested as a 64-bit integer, for the “latest version”.}
419 \item[ver\_res] {A Boolean value. True: Signature verification passed, False: Signature verification failed.}
420\end{description}
421
422
423\subsection{Authenticity of truth} \label{sec:truth}
424
425\texttt{/truth/} requests are used to upload encrypted authentication data
426and encrypted key shares to an Anastasis escrow service. As an additional
427layer of protection, an Anastasis escrow service cannot link truth data to
428policy data, except maybe by observing the timing of the requests.
429
430Anastasis uses EdDSA-based {\em truth key}s to identify truth
431objects. For those, the truth keys are derived from a {\em truth
432 seed}, as show in Figure~\ref{fig:truth_keys}. The private truth
433key is used to authorize the truth upload. The signatures also
434authenticate the encrypted key shares returned from the Anastasis
435provider during recovery. The signature process for truth is
436analogous to that for accounts.
437
438
439\subsection{Availability considerations}
440
441Anastasis considers two main threats against availability. First, the
442Anastasis server operators must be protected against denial-of-service
443attacks where an adversary attempts to exhaust operator’s
444resources. The API protects against these attacks by allowing
445operators to set fees for expensive operations. Furthermore, all data stored
446comes with an expiration logic, so an attacker cannot force servers to
447store data indefinitely.
448
449A second availability issue arises from strong adversaries that may be
450able to compute the account keys of some user. While we assume that
451such an adversary cannot successfully authenticate against the truth,
452the account key does inherently enable these adversaries to upload a
453new policy for the account. This cannot be prevented, as the
454legitimate user must be able to set or change a policy using only the
455account key. To ensure that an adversary cannot exploit this, policy
456uploads first of all never delete existing policies, but merely create
457another version. This way, even if an adversary uploads a malicious
458policy, a user can still retrieve an older version of the policy to
459recover access to their data. This append-only storage for policies
460still leaves a strong adversary with the option of uploading many
461policies to exhaust the Anastasis server’s capacity. We limit this
462attack by requiring a policy upload to include a reference to a
463payment identifier from a payment made by the user. Thus, a policy
464upload requires both knowledge of the identity and making a
465payment. This effectively prevents and adversary from using the
466append-only policy storage from exhausting Anastasis server capacity.