2

In the traditional form, a password database is similar to any other database file, except the contents are encrypted using a key derived from a passphrase entered by the user. The user enters their passphrase, decrypts the database, reads some entries, writes/changes some other entries, re-encrypts the database and writes it back to disk.

Say we wanted to extend this concept to a shared environment. Say our database has ten entries (0 through 9) and three users (Alice, Bob, and Carl), each with their own unique passphrase. To further complicate the scenario, Alice should be able to access all the entries, Bob should only be able to access entries 0-4, and Carl should only be able to access entries 5-9. If Alice changes one of the entries, Bob or Carl should see the updated value (if they have access). If Bob or Carl changes one of the entries that they have access to, Alice should see the updated value.

I'm curious if there is a way something like this could be implemented securely. All the approaches I've been able to come up with either require there being some sort of "master" key being stored alongside the database, thus leaving a big opportunity for anybody who gains access to the filesystem or memory of the server -- or storing a uniquely encrypted copy of each set of entries for each user. But that would break the scenarios where one user needs to update a value in a way that the other users can see.

Is there a way to do this, or some subtle way the requirements could be tweaked to make the system less paradoxical?

2

I thought a bit about the answers that have been posted so far, and there's interesting promise in the idea of using a public-key algorithm. Thinking out loud, each user could have a public/private key pair (where each public key is stored on the central server alongside the databases).

Public key storage on the server:

+-------+------------------------+
| Alice | [public key for Alice] |
+-------+------------------------+
| Bob   | [public key for Bob]   |
+-------+------------------------+
| Carl  | [public key for Carl]  |
+-------+------------------------+

Each entry would be stored encrypted, using a symmetric cipher with a per-entry key that is generated randomly by the server each time an entry is written:

+---+-------------------------------------------------+
| 0 | symmetric_cipher([plaintext 0], [random key 0]) |
+---+-------------------------------------------------+
| 1 | symmetric_cipher([plaintext 1], [random key 1]) |
+---+-------------------------------------------------+
|   ...                                               |
+---+-------------------------------------------------+
| 9 | symmetric_cipher([plaintext 9], [random key 9]) |
+---+-------------------------------------------------+

For the access control, a third mapping could store the randomly-generated key for each entry, which has been encrypted using each authorized user's public key:

+-------+---+-------------------------------------------------------+
| Alice | 0 | pubkey_cipher([random key 0], [public key for Alice]) |
+-------+---+-------------------------------------------------------+
| Bob   | 0 | pubkey_cipher([random key 0], [public key for Bob])   |
+-------+---+-------------------------------------------------------+
| Alice | 1 | pubkey_cipher([random key 1], [public key for Alice]) |
+-------+---+-------------------------------------------------------+
| Bob   | 1 | pubkey_cipher([random key 1], [public key for Bob])   |
+-------+---+-------------------------------------------------------+
|   ...                                                             |
+-------+---+-------------------------------------------------------+
| Alice | 8 | pubkey_cipher([random key 8], [public key for Alice]) |
+-------+---+-------------------------------------------------------+
| Carl  | 8 | pubkey_cipher([random key 8], [public key for Carl])  |
+-------+---+-------------------------------------------------------+
| Alice | 9 | pubkey_cipher([random key 9], [public key for Alice]) |
+-------+---+-------------------------------------------------------+
| Carl  | 9 | pubkey_cipher([random key 9], [public key for Carl])  |
+-------+---+-------------------------------------------------------+

(From what I've read, this is sort of what GPG does when you send an encrypted message to multiple recipients.)

Each user can use their private key to decrypt the symmetric "entry" key that is only good for that one specific entry. That key will allow them to decrypt and read that entry. If they need to change and re-save it, they could either use the same key that they read with and overwrite -- or the server could generate a fresh entry key, and use the public key for each authorized user to update the other affected rows.

De-authorizing a user would be as simple as removing their row from the user-to-entry mapping table. If there was concern that they may have stored one or more of the entry keys, those can all be regenerated transparently for each remaining user without any intervention on their part.

Seems like the main concern then would shift to ensuring that the client-server communication channels were secure, and that the client can keep its secrets a secret.

  • Interesting write-up. Can I ask what the interface looks like from the user's perspective, and also whether this is a personal project development (making it as secure as possible for novelty vs. business with deadlines)? If it's the latter, I can find you a good existing solution. You also said it was a shared environment, so if the users are literally just coexisting on one secure file system then you really could just use the built-in file permissions for a lot of this. – AJAr Feb 5 '15 at 22:05
  • It's more a personal curiosity, where multiple users could interact via either a command line or a web browser. It would've come in handy a few times in a workplace context, but no immediate need. – smitelli Feb 6 '15 at 14:57
1

For each shared database, use a random generated key for its encryption. Don't store the key as is, but store it encrypted in three copies (Alice has a key encrypted with her password, Bob has a key encrypted with his password and so on). If Alice wants to change her encryption password, first decrypt her key copy and then encrypt it with the new password; the underlying random-generated encryption key doesn't change in this scenario and Bob's and Carl's keys will therefore still work. - I guess some kind of salting would be preferable; if not one would easily be able to detect if two users have chosen the same personal password.

I dont't know exactly how the sharing would be set up; you will have to transmit the true encryption key from one user to the other without leakage. Maybe you could split the key in two parts (XOR it with a cryptosafe random string) and share one half within your database system, and the other half by cut-and-paste from screen to e-mail?

Good luck.

0

If you are already re-encrypting the entire database on each write, then I suppose it wouldn't be that big of a leap to maintain a separate data store for each reader (or group of readers in the same way). It might prove more efficient to keep a ledger of transactions for each reader, then also specify write permissions in the metadata for each entry listing/table to be referenced in authenticating write transactions.

Perhaps an interface somewhat like this:

<writer>: <key> = <value> -> <reader>(<permissions>)

For example, this command would identify the writer, set 3 to "hello", and define authorized users:

Alice: 3 = "hello" -> Alice(r+u+d), Bob(r)

That might prompt Alice's client to sign the above transaction string and encrypt it two times—once for Alice and once for Bob—before commiting the transaction to persistent memory shared by Alice, Bob, and possibly Carl and an attacker. Each of Alice and Bob would see and decrypt the transaction, verify permissions and authenticate signatures, apply it to their respective databases, and look for new ones.

For group permissions, replace Alice and Bob with group names on the right side of the example and add metadata as needed (via the same mechanism or otherwise). There also need to be timestamps with every transaction to provide a clear order of mutation, but I wanted to keep it simple here.


Essentially describing encrypted/authenticated pub-sub, perhaps with long-term serializations of the data encrypted for each person and backed up to long-term persistent memory by each person themselves to enable quick bootstrapping on new machines and discourage long-term storage on less secure personal media (vs. having them traverse the entire ledger of transactions and process them all sequentially during the synchronization process).

There certainly exist systems like this with a far more efficient/practical approach already implemented within an established codebase. I do not know of any because I have not needed to work with a system like this to date, but I will look around and edit the answer if I find one. As a final thought, take a look at how PGP supports multiple recipients of a message in one encoding—it may offer some insight.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.