Creating a secure, web-based password management system with the ability to share data between users

Question

I apologize in advance for the incoming Wall-O-Text. This is (at least, to me) a fairly complex issue that I've put quite a bit of thought into. You can read my question and also see a test implementation in Ruby (very hastily built, not database-backed, and probably very ugly) at this GitHub Gist if you are so inclined.

---

Introduction

Imagine one was required to create a web-based password management system (over SSL! :) with the following requirements:

1. Individual users sign in to the system using their own unique pass phrase.
2. This pass phrase should be enough to allow the user to use the system effectively (e.g. from a smartphone, etc.)--the point being that they should not have to keep a key file with them.
3. Users can store arbitrary-length bits of data in the system ("entries").
4. Entries are encrypted in the database in such a way that there is not enough information in the database or application alone to read the encrypted entries.
5. Users should be able to "share" entries with other users of the system so that the other user(s) can read the contents of the entry.

I'm no expert in cryptography. After thinking about it for a while, I came up with the following. My question is: is this implementation secure? Am I missing something? If so, is the above spec even implementable? Or is this overkill?

Database

The database is set up as such:

+------------------------------------------------------------------------------+
|  users                                                                       |
+---------+--------------+--------------+---------------+----------------------+
| salt    | pub_key      | enc_priv_key | priv_key_hmac |                      |
+---------+--------------+--------------+---------------+----------------------+
|  entries                                                                     |
+---------+--------------+--------------+---------------+----------+-----------+
| user_id | parent_entry | enc_sym_key  | sym_key_sig   | enc_data | data_hmac |
+---------+--------------+--------------+---------------+----------+-----------+

Basic Use Cases

Let's imagine two users of the system, Alice and Bob.

Bob signs up for the site:

• Bob enters a password. This password is sent to the server (but not stored).
• The server generates a random salt and stores it in the salt field.
• The server generates the SHA-256 hash of Bob's password and salt.
• The server generates an RSA key pair. The public key is stored as plain text in the pub_key field. The private key is encrypted via AES-256 using the hash generated from Bob's password and salt as the key and stored in the enc_priv_key field.
• The server generates a hash-based message authentication code for Bob's private key using Bob's password and salt as the key and stores this in the priv_key_hmac field.

Bob stores an entry in the system:

• Bob enters some data to be stored as an entry along with his password. This data is sent to the server.
• The server generates a key to be used as a key for AES-256 encryption.
• The server uses this key to encrypt the data and stores the result in the enc_data field.
• The server generates a hash-based message authentication code for the data using the generated key and stores this in the data_hmac field.
• The symmetric key used to encrypt the data is encrypted with Bob's public key and stored in the enc_sym_key field.
• The server uses Bob's private key to generate a signature for the symmetric key.

Bob retrieves his stored entry:

• Bob enters his password and the ID of the entry to retrieve.
• The server generates the SHA-256 hash of Bob's password and salt.
• Bob's encrypted private key is decrypted via AES-256 encryption using the hash.
• The server verifies that Bob's encrypted private key has not been tampered with by checking the HMAC in priv_key_hmac.
• The server decrypts the symmetric key stored in the enc_sym_key field using Bob's private key.
• The server verifies that the encrypted symmetric key has not been tampered with by verifying the signature in sym_key_sign using Bob's public key.
• The server decrypts the data using the symmetric key.
• The server verifies that the encrypted data has not been tampered with by verifying the HMAC stored in the data_hmac field.
• The server returns the decrypted data to Bob.

Bob shares an entry with Alice:

• Bob wants Alice to have access to an entry he owns. He enters his password and the ID of the entry to share.
• The data for the entry is decrypted using the method in "Bob retrieves his stored entry."
• A new entry is created for Alice in the same fashion as in "Bob stores an entry in the system," with the following exceptions:
  1. The entry's parent_entry is set to Bob's entry.
  2. The signature for the symmetric key is calculated using Bob's private key (since Alice's private key is not available to Bob).
  3. When Alice accesses this new entry, the existence of a non-null parent_entry causes the system to use Bob's public key to verify the signature (since his private key was used to create it).

Bob changes the data in his shared entry:

• Bob decides to change the data in the entry he shared with Alice. Bob indicates the entry ID to modify and the new data it should contain.
• The system overwrites the data created in "Bob stores an entry in the system."
• The system finds every entry with a parent_entry equal to the entry that was just modified, and for each one overwrites the data created in "Bob shares an entry with Alice."

Analysis

Advantages:

• It is impossible to decrypt any data from the database without the password of the user that owns the data, as the private key necessary to decrypt the data is encrypted with the user's password, and that password (and it's hash) is not stored in the database.
• If a user wants to change their password, only their encrypted private key needs to be regenerated (decrypt the private key with the old password/hash, then re-encrypt it with the new password/hash).
• Shared entries are stored as actual separate records in the database, so there is no need to share a key between multiple users/groups of users.

Disadvantages/Problems (that I can think of):

• If a shared entry is modified, the system must re-encrypt every child entry; with a large number of users sharing data, this could potentially be computationally expensive.
• Shared entries depend on the parent user's public key for signature verification. If the user is deleted, or their key changes, the signatures are invalid.

Repeated from the introduction: my question is: is this implementation secure? Am I missing something? If so, is the above spec even implementable? Or is this overkill?

Thanks for sticking it out this long. I'm interested in your opinions! Am I on the right track, or a complete moron? YOU DECIDE! :)

Answer 1

No IV storage? I guess you could use AES-256-ECB, but that only lets users store 32 byte passwords, and you need to make sure that the generated private key is only ever used for one encryption. (Your current design seems safe in this respect, but if you want to allow passwords longer than 32 bytes, or ever think of making this key do double-duty, you'll need to store an IV for every encryption with it.)

I don't see the security value of priv_key_hmac and data_hmac; if either the private key or the encrypted data has been tampered with, then garbage output will result from decrypting with the private key or the symmetric key. Bob will surely be suspicious when he can't figure out how to type the BEL character. :) (Will humans ever see the output? A human will likely realize the returned password is incorrect without needing to be told. A computer couldn't tell the difference, so if automated systems will ever use the resulting passwords, then sure, keep the fields.)

There is no mechanism for "I forgot my password". Make sure your users know that there is no recovering their data if they forget their password. Users are coddled these days, and might expect to be coddled with your service too.

I see no mechanism for users to specify which entry Bob wants decrypted. You should store a name, or, as ssh(1) does in known_hosts, a hashed version of a name, for each entry. Storing a name directly would remove an SHA-256 operation, but a database compromise that reports the cleartext names of services that a user has accounts with might be every bit as damaging. (Perhaps an online escort service, or off-shore bank, or fight club.)