update soledad storage secret doc
[leap_doc.git] / docs / design / soledad.md
1 @title = 'Soledad'
2 @summary = 'A server daemon and client library to provide client-encrypted application data that is kept synchronized among multiple client devices.'
3 @toc = true
4
5 Introduction
6 =====================
7
8 Soledad allows client applications to securely share synchronized document databases. Soledad aims to provide a cross-platform, cross-device, syncable document storage API, with the addition of client-side encryption of database replicas and document contents stored on the server.
9
10 Key aspects of Soledad include:
11
12 * **Client and server:** Soledad includes a server daemon and client application library.
13 * **Client-side encryption:** Soledad puts very little trust in the server by encrypting all data before it is synchronized to the server and by limiting ways in which the server can modify the user's data.
14 * **Local storage:** All data cached locally is stored in an encrypted database.
15 * **Document database:** An application using the Soledad client library is presented with a document-centric database API for storage and sync. Documents may be indexed, searched, and versioned.
16
17 The current reference implementation of Soledad is written in Python and distributed under a GPLv3 license.
18
19 Soledad is an acronym of "Synchronization of Locally Encrypted Documents Among Devices" and means "solitude" in Spanish.
20
21 Goals
22 ======================
23
24 **Security goals**
25
26 * *Client-side encryption:* Before any data is synced to the cloud, it should be encrypted on the client device.
27 * *Encrypted local storage:* Any data cached in the client should be stored in an encrypted format.
28 * *Resistant to offline attacks:* Data stored on the server should be highly resistant to offline attacks (i.e. an attacker with a static copy of data stored on the server would have a very hard time discerning much from the data).
29 * *Resistant to online attacks:* Analysis of storing and retrieving data should not leak potentially sensitive information.
30 * *Resistance to data tampering:* The server should not be able to provide the client with old or bogus data for a document.
31
32 **Synchronization goals**
33
34 * *Consistency:* multiple clients should all get sync'ed with the same data.
35 * *Sync flag:* the ability to partially sync data. For example, so a mobile device doesn't need to sync all email attachments.
36 * *Multi-platform:* supports both desktop and mobile clients.
37 * *Quota:* the ability to identify how much storage space a user is taking up.
38 * *Scalable cloud:* distributed master-less storage on the cloud side, with no single point of failure.
39 * *Conflict resolution:* conflicts are flagged and handed off to the application logic to resolve.
40
41 **Usability goals**
42
43 * *Availability*: the user should always be able to access their data.
44 * *Recovery*: there should be a mechanism for a user to recover their data should they forget their password.
45
46 **Known limitations**
47
48 These are currently known limitations:
49
50 * The server knows when the contents of a document have changed.
51 * There is no facility for sharing documents among multiple users.
52 * Soledad is not able to prevent server from withholding new documents or new revisions of a document.
53 * Deleted documents are never deleted, just emptied. Useful for security reasons, but could lead to DB bloat.
54
55 **Non-goals**
56
57 * Soledad is not for filesystem synchronization, storage or backup. It provides an API for application code to synchronize and store arbitrary schema-less JSON documents in one big flat document database. One could model a filesystem on top of Soledad, but it would be a bad fit.
58 * Soledad is not intended for decentralized peer-to-peer synchronization, although the underlying synchronization protocol does not require a server. Soledad takes a cloud approach in order to ensure that a client has quick access to an available copy of the data.
59
60 Related software
61 ==================================
62
63 [Crypton](https://crypton.io/) - Similar goals to Soledad, but in javascript for HTML5 applications.
64
65 [Mylar](https://github.com/strikeout/mylar) - Like Crypton, Mylar can be used to write secure HTML5 applications in javascript. Uniquely, it includes support for homomorphic encryption to allow server-side searches.
66
67 [Firefox Sync](https://wiki.mozilla.org/Services/Sync) - A client-encrypted data sync from Mozilla, designed to securely synchronize bookmarks and other browser settings.
68
69 [U1DB](http://pythonhosted.org/u1db/) - Similar API as Soledad, without encryption.
70
71 Soledad protocol
72 ===================================
73
74 Document API
75 -----------------------------------
76
77 Soledad's document API is similar to the [API used in U1DB](http://pythonhosted.org/u1db/reference-implementation.html).
78
79 * Document storage: `create_doc()`, `put_doc()`, `get_doc()`.
80 * Synchronization with the server replica: `sync()`.
81 * Document indexing and searching: `create_index()`, `list_indexes()`, `get_from_index()`, `delete_index()`.
82 * Document conflict resolution: `get_doc_conflicts()`, `resolve_doc()`.
83
84 For example, create a document, modify it and sync:
85
86     sol.create_doc({'my': 'doc'}, doc_id='mydoc')
87     doc = sol.get_doc('mydoc')
88     doc.content = {'new': 'content'}
89     sol.put_doc(doc)
90     sol.sync()
91
92 Storage secret
93 -----------------------------------
94
95 The `storage_secret` is a long randomly generated key used to derive the encryption keys for the data stored both in the server and in the local replica. The `storage_secret` is block encrypted using a key derived from the user's password and saved locally on disk in a file called `<user_uid>.secret`, which contains a JSON structure that looks like this:
96
97     {
98       'active_secret': '<secret_id>',
99       'storage_secrets': {
100         '<secret_id>': {
101           'kdf': 'scrypt',
102           'kdf_salt': '<b64 repr of salt>',
103           'kdf_length': <key_length>,
104           'cipher': 'aes256',
105           'length': <secret_length>,
106           'secret': '<encrypted storage_secret>',
107         }
108       }
109       'kdf': 'scrypt',
110       'kdf_salt': '<b64 repr of salt>',
111       'kdf_length: <key length>,
112       '_mac_method': 'hmac',
113       '_mac': '<mac>',
114     }
115
116 The `storage_secrets` entry is a map that stores information about available storage keys. Currently, Soledad uses only one storage key per provider, but this may change in the future.
117
118 The following fields are stored for one storage key:
119
120 * `secret_id`: a handle used to refer to a particular `storage_secret` and equal to `sha256(storage_secret)`.
121 * `kdf`: the key derivation function to use. Only scrypt is currently supported.
122 * `kdf_salt`: the salt used in the kdf. The salt for scrypt is not random, but encodes important parameters like the limits for time and memory.
123 * `kdf_length`: the length of the derived key resulting from the kdf.
124 * `cipher`: what cipher to use to encrypt `storage_secret`. It must match `kdf_length` (i.e. the length of the derived_key).
125 * `length`: the length of `storage_secret`, when not encrypted.
126 * `secret`: the encrypted `storage_secret`, created by `sym_encrypt(cipher, storage_secret, derived_key)` (base64 encoded).
127
128 Other variables:
129
130 * `derived_key` is equal to `kdf(user_password, kdf_salt, kdf_length)`.
131 * `storage_secret` is equal to `sym_decrypt(cipher, secret, derived_key)`.
132
133 When a client application first wants to use Soledad, it must provide the user's password to unlock the `storage_secret`:
134
135     from leap.soledad.client import Soledad
136     sol = Soledad(
137         uuid='<user_uid>',
138         passphrase='<user_passphrase>',
139         secrets_path='~/.config/leap/soledad/<user_uid>.secret',
140         local_db_path='~/.config/leap/soledad/<user_uid>.db',
141         server_url='https://<soledad_server_url>',
142         cert_file='~/.config/leap/providers/<provider>/keys/ca/cacert.pem',
143         auth_token='<auth_token>',
144         secret_id='<secret_id>')  # optional argument
145
146
147 Currently, the `storage_secret` is shared among all devices with access to a particular user's Soledad database. See [Recovery and bootstrap](#Recovery.and.bootstrap) for how the `storage_secret` is initially installed on a device.
148
149 We don't use the `derived_key` as the `storage_secret` because we want the user to be able to change their password without needing to re-key.
150
151 Document encryption
152 ------------------------
153
154 Before a JSON document is synced with the server, it is transformed into a document that looks like this:
155
156     {
157       "_enc_json": "<ciphertext>",
158       "_enc_scheme": "symkey",
159       "_enc_method": "aes256ctr",
160       "_enc_iv": "<initialization_vector>",
161       "_mac": "<auth_mac>",
162       "_mac_method": "hmac"
163     }
164
165 About these fields:
166
167 * `_enc_json`: The original JSON document, encrypted and hex encoded. Calculated as:
168     * `doc_key = hmac(storage_secret[MAC_KEY_LENGTH:], doc_id)`
169     * `ciphertext = hex(sym_encrypt(cipher, content, doc_key))`
170 * `_enc_scheme`: Information about the encryption scheme used to encrypt this document (i.e.`pubkey`, `symkey` or `none`).
171 * `_enc_method`: Information about the block cipher that is used to encrypt this document.
172 * `_mac`: A MAC to prevent the server from tampering with stored documents. Calculated as:
173     * `mac_key = hmac(storage_secret[:MAC_KEY_LENGTH], doc_id)`
174     * `_mac = hmac(doc_id|rev|ciphertext|_enc_scheme|_enc_method|_enc_iv, mac_key)`
175 * `_mac_method`: The method used to calculate the mac above (currently hmac).
176
177 Other variables:
178
179 * `doc_key`: This value is unique for every document and only kept in memory. We use `doc_key` instead of simply `storage_secret` in order to hinder possible derivation of `storage_secret` by the server. Every `doc_id` is unique.
180 * `content`: equal to `sym_decrypt(cipher, ciphertext, doc_key)`.
181
182 When receiving a document with the above structure from the server, Soledad client will first verify that `_mac` is correct, then decrypt the `_enc_json` to find `content`, which it saves as a cleartext document in the local encrypted database replica.
183
184 The document MAC includes the document revision and the client will refuse to download a new document if the document does not include a higher revision. In this way, the server cannot rollback a document to an older revision. The server also cannot delete a document, since document deletion is handled by removing the document contents, marking it as deleted, and incrementing the revision. However, a server can withhold from the client new documents and new revisions of a document (including withholding document deletion).
185
186 The currently supported encryption ciphers are AES256 (CTR mode) and XSalsa20. The currently supported MAC method is HMAC with SHA256.
187
188 Document synchronization
189 -----------------------------------
190
191 Soledad follows the U1DB synchronization protocol, with some changes:
192
193 * Add the ability to flag some documents so they are not synchronized by default (not fully supported yet).
194 * Refuse to synchronize a document if it is encrypted and the MAC is incorrect.
195 * Always use `https://<soledad_server_url>/user-<user_uid>` as the synchronization URL.
196
197
198     doc = sol.create_doc({'some': 'data'})
199     doc.syncable = False
200     sol.sync()  # will not send the above document to the server!
201
202 Document IDs
203 --------------------
204
205 Like U1DB, Soledad allows the programmer to use whatever ID they choose for each document. However, it is best practice to let the library choose random IDs for each document so as to ensure you don't leak information. In other words, leave the second argument to `create_doc()` empty.
206
207 Re-keying
208 -----------
209
210 Sometimes there is a need to change the `storage_secret`. Rather then re-encrypt every document, Soledad implements a system called "lazy revocation" where a new `storage_secret` is generated and used for all subsequent encryption. The old `storage_secret` is still retained and used when decrypting older documents that have not yet been re-encrypted with the new `storage_secret`.
211
212 Authentication
213 -----------------------
214
215 Unlike U1DB, Soledad only supports token authentication and does not support OAuth. Soledad itself does not handle authentication. Instead, this job is handled by a thin HTTP WSGI middleware layer running in front of the Soledad server daemon, which retrieves valid tokens from a certain shared database and compares with the user-provided token. How the session token is obtained is beyond the scope of Soledad.
216
217 Bootstrap and recovery
218 ------------------------------------------
219
220 Because documents stored on the server's database replica have their contents encrypted with keys based on the `storage_secret`, initial synchronizations of newly configured provider accounts are only possible if the secret is transferred from one device to another. Thus, installation of Soledad in a new device or account recovery after data loss is only possible if specific recovery data has previously been exported and either stored on the provider or imported on a new device.
221
222 Soledad may export a recovery document containing recovery data, which may be password-encrypted and stored in the server, or stored in a safe environment in order to be later imported into a new Soledad installation.
223
224 **Recovery document**
225
226 An example recovery document:
227
228     {
229         'storage_secrets': {
230             '<secret_id>': {
231                 'kdf': 'scrypt',
232                 'kdf_salt': '<b64 repr of salt>'
233                 'kdf_length': <key length>
234                 'cipher': 'aes256',
235                 'length': <secret length>,
236                 'secret': '<encrypted storage_secret>',
237             },
238         },
239         'kdf': 'scrypt',
240         'kdf_salt': '<b64 repr of salt>',
241         'kdf_length: <key length>,
242         '_mac_method': 'hmac',
243         '_mac': '<mac>'
244     }
245
246 About these fields:
247
248 * `secret_id`: a handle used to refer to a particular `storage_secret` and equal to `sha256(storage_secret)`.
249 * `kdf`: the key derivation function to use. Only scrypt is currently supported.
250 * `kdf_salt`: the salt used in the kdf. The salt for scrypt is not random, but encodes important parameters like the limits for time and memory.
251 * `kdf_length`: the length of the derived key resulting from the kdf.
252 * `length`: the length of the secret.
253 * `secret`: the encrypted `storage_secret`.
254 * `cipher`: what cipher to use to encrypt `secret`. It must match `kdf_length` (i.e. the length of the `derived_key`).
255 * `_mac_method`: The method used to calculate the mac above (currently hmac).
256 * `_mac`: Defined as `hmac(doc_id|rev|ciphertext, doc_key)`. The purpose of this field is to prevent the server from tampering with the stored documents.
257
258 Currently, scrypt parameters are:
259
260      N (CPU/memory cost parameter) = 2^14 = 16384
261      p (paralelization parameter) = 1
262      r (length of block mixed by SMix()) = 8
263      dkLen (length of derived key) = 32 bytes = 256 bits
264
265 Other fields we might want to include in the future:
266
267 * `expires_on`: the month in which this recovery document should be purged from the database. The server may choose to purge documents before their expiration, but it should not let them linger after it.
268 * `soledad`: the encrypted `soledad.json`, created by `sym_encrypt(cipher, contents(soledad.json), derived_key)` (base64 encoded).
269 * `reset_token`: an optional encrypted password reset token, if supported by the server, created by `sym_encrypt(cipher, password_reset_token, derived_key)` (base64 encoded). The purpose of the reset token is to allow recovery using the recovery code even if the user has forgotten their password. It is only applicable if using recovery code method.
270
271 **Recovery database**
272
273 In order to support easy recovery, the Soledad client stores a recovery document in a special recovery database. This database is shared among all users.
274
275 The recovery database supports two functions:
276
277 * `get_doc(doc_id)`
278 * `put_doc(doc_id, recovery_document_content)`
279
280 Anyone may preform an unauthenticated `get_doc` request. To mitigate the potential attacks, the response to queries of the discovery database must have a long delay of X seconds. Also, the `doc_id` is very long (see below).
281
282 Although the database is shared, the user must authenticate via the normal means before they are allowed to put a recovery document. Because of this, a nefarious server might potentially record which user corresponds to which recovery documents. A well behaved server, however, will not retain this information. If the server supports authentication via blind signatures, then this will not be an issue.
283
284
285 **Recovery code (yet to be implemented)**
286
287 We intend to offer data recovery by specifying username and a recovery code. The choice of type of recovery (using password or a recovery code) must be made in advance of attempting recovery (e.g. at some point after the user has Soledad successfully running on a device).
288
289 About the optional recovery code:
290
291 * The recovery code should be randomly generated, at least 16 characters in length, and contain all lowercase letters (to make it sane to type into mobile devices).
292 * The recovery code is not stored by Soledad. When the user needs to bootstrap a new device, a new code is generated. To be used for actual recovery, a user will need to record their recovery code by printing it out or writing it down.
293 * The recovery code is independent of the password. In other words, if a recovery code is generated, then a user changes their password, the recovery code is still be sufficient to restore a user's account even if the user has lost the password. This feature is dependent on the server supporting a password reset token. Also, generating a new recovery code does not affect the password.
294 * When a new recovery code is created, and new recovery document must be pushed to the recovery database. A code should not be shown to the user before this happens.
295 * The recovery code expires when the recovery database record expires (see below).
296
297 The purpose of the recovery code is to prevent a compromised or nefarious Soledad service provider from decrypting a user's storage. The benefit of a recovery code over the user password is that the password has a greater opportunity to be compromised by the server. Even if authentication is performed via Secure Remote Password, the server may still perform a brute force attack to derive the password.
298
299 Reference implementation of client
300 ===================================
301
302 https://github.com/leapcode/soledad
303
304 Dependencies:
305
306 * [U1DB](https://launchpad.net/u1db) provides an API and protocol for synchronized databases of JSON documents.
307 * [SQLCipher](http://sqlcipher.net/) provides a block-encrypted SQLite database used for local storage.
308 * python-gnupg
309 * scrypt
310 * pycryptopp
311
312 Local storage
313 --------------------------
314
315 U1DB reference implementation in Python has an SQLite backend that implements the object store API over a common SQLite database residing in a local file. To allow for encrypted local storage, Soledad adds a SQLCipher backend, built on top of U1DB's SQLite backend, which adds [SQLCipher API](http://sqlcipher.net/sqlcipher-api/) to U1DB.
316
317 **Responsibilities**
318
319 The SQLCipher backend is responsible for:
320
321 * Providing the SQLCipher API for U1DB (`PRAGMA` statements that control encryption parameters).
322 * Guaranteeing that the local database used for storage is indeed encrypted.
323 * Guaranteeing secure synchronization:
324   * All data being sent to a remote replica is encrypted with a symmetric key before being sent.
325   * Ensure that data received from remote replica is indeed encrypted to a symmetric key when it arrives, and then that it is decrypted before being included in the local database replica.
326 * Correctly representing and handling new Document properties (e.g. the `sync` flag).
327
328 Part of the Soledad `storage_key` is used directly as the key for the SQLCipher encryption layer. SQLCipher supports the use of a raw 256 bit keys if provided as a 64 character hex string. This will skip the key derivation step (PBKDF2), which is redundant in our case. For example:
329
330     sqlite> PRAGMA key = "x'2DD29CA851E7B56E4697B0E1F08507293D761A05CE4D1B628663F411A8086D99'";
331
332 **Classes**
333
334 SQLCipher backend classes:
335
336 * `SQLCipherDatabase`: An extension of `SQLitePartialExpandDatabase` used by Soledad Client to store data locally using SQLCipher. It implements the following:
337   * Need of a password to instantiate the db.
338   * Verify if the db instance is indeed encrypted.
339   * Use a LeapSyncTarget for encrypting content before synchronizing over HTTP.
340   * "Syncable" option for documents (users can mark documents as not syncable, so they do not propagate to the server).
341
342 Encrypted synchronization target
343 --------------------------------------------------
344
345 To allow for database synchronization among devices, Soledad uses the following conventions:
346
347 * Centralized synchronization scheme: Soledad clients always sync with a server, and never between themselves.
348 * The server stores its database in a CouchDB database using a REST API over HTTP.
349 * All data sent to the server is encrypted with a symmetric secret before being sent. Note that this ensures all data received by the server and stored in the CouchDB database has been encrypted by the client.
350 * All data received from the server is validated as being an encrypted blob, and then is decrypted before being stored in local database. Note that the local database provides a new encryption layer for the data through SQLCipher.
351
352 **Responsibilities**
353
354 Provide sync between local and remote replicas:
355
356 * Encrypt outgoing content.
357 * Decrypt incoming content.
358
359 **Classes**
360
361 Synchronization-related classes:
362
363 * `SoledadSyncTarget`: an extension of `HTTPSyncTarget` modified to encrypt documents' content before sending them to the network and to have more control of the syncing process.
364
365 Reference implementation of server
366 ======================================================
367
368 https://github.com/leapcode/soledad
369
370 Dependencies:
371
372 * [CouchDB](https://couchdb.apache.org/] for server storage, via [python client library](https://pypi.python.org/pypi/CouchDB/0.8).
373 * [Twisted](http://twistedmatrix.com/trac/) to run the WSGI application.
374 * scrypt
375 * pycryptopp
376 * PyOpenSSL
377
378 CouchDB backend
379 -------------------------------
380
381 In the server side, Soledad stores its database replicas in CouchDB servers. Soledad's CouchDB backend implementation is built on top of U1DB's `CommonBackend`, and stores and fetches data using a remote CouchDB server. It lacks indexing first because we don't need that functionality on server side, but also because if not very well done, it could lack sensitive information about document's contents.
382
383 CouchDB backend is responsible for:
384
385 * Initializing and maintaining the following U1DB replica data in the database:
386   * Transaction log.
387   * Conflict log.
388   * Synchronization log.
389 * Mapping the U1DB API to CouchDB API.
390
391 **Classes**
392
393 * `CouchDatabase`: A backend used by Soledad Server to store data in CouchDB.
394 * `CouchSyncTarget`: Just a target for syncing with Couch database.
395 * `CouchServerState`: Interface of the WSGI server with the CouchDB backend.
396
397 WSGI Server
398 -----------------------------------------
399
400 The U1DB server reference implementation provides for an HTTP API backed by SQLite databases. Soledad extends this with token-based auth HTTP access to CouchDB databases.
401
402 * Soledad makes use of `twistd` from Twisted API to serve its WSGI application.
403 * Authentication is done by means of a token.
404 * Soledad implements a WSGI middleware in server side that:
405   * Uses the provided token to verify read and write access to each user's private databases and write access to the shared recovery database.
406   * Allows reading from the shared remote recovery database.
407   * Uses CouchDB as its backend.
408
409 **Classes**
410
411 * `SoledadAuthMiddleware`: implements the WSGI middleware with token based auth as described before.
412 * `SoledadApp`: The WSGI application. For now, not different from `u1db.remote.http_app.HTTPApp`.
413
414 **Authentication**
415
416 Soledad Server authentication middleware controls access to user's private databases and to the shared recovery database. Soledad client provides a token for Soledad server that can check the validity of this token for this user's session by querying a certain database.
417
418 A valid token for this user's session is required for:
419
420 * Read and write access to this user's database.
421 * Read and write access to the shared recovery database.
422
423 Tests
424 ===================
425
426 To be sure the new implemented backends work correctly, we included in Soledad the U1DB tests that are relevant for the new pieces of code (backends, document, http(s) and sync tests). We also added specific tests to the new functionalities we are building.