Securing an end-to-end encrypted cloud based address book

Question

I am analyzing an existing end-to-end encrypted, cloud based service (e.g. email, file storage or chat) which also has a public cloud based address book (for managing contacts) so that users of the cloud service can communicate securely between themselves (e.g. send email, share data or chat).

To log into the cloud based service, all that users need to remember is their password. When logging in, the user's password is fed into a password based key derivation function e.g. PBKDF2 which produces a derived key and that is used to verify and decrypt their account's symmetric cryptographic key e.g. AES-256 (for protecting the user's own data and account operations) and their public/private key pair e.g. RSA 3072 (for sharing data with other users, sending email or chatting). These keys are created at account registration time on the client side and uploaded to the cloud service. Everything is persisted on the server, but data is fetched and cryptographic operations are performed client side. Users can log out and log in on another computer or device and have access to all the data they had before logging out.

For a proper end-to-end paradigm, users need to verify each others' public keys in person but store (pin) the fingerprint of the public key they've seen and that they've verified. Otherwise if users do not verify public keys then they would be vulnerable to an active MITM attack by someone on the network path (e.g. Internet) or the cloud service themselves (either the cloud service is secretly malicious, under duress, an employee is a spy, they get hacked, or they receive a court order etc). So in theory nothing from the cloud service should be trusted. Everything should be re-verified by the user on the client side upon being fetched from the service and security is rooted in the secrecy and strength of the password.

When a user adds a contact (via email address) to their address book, the client fetches the public key for that user from the server database as well. The client accepts the default public key from the server and then uploads a data record to the server to retain the information that they have seen that public key fingerprint.

The users table contains a list of user records e.g.

[user id], [user email], [name], [public key], [encrypted private key], [encrypted symmetric key]

A user id / contact id is a 64 bit unique, random string in hex. The users_contacts table contains a mapping of contacts for each user e.g.

[user id], [contact id]

The public key fingerprint records are stored in a separate table contacts_fingerprints. The record that is stored on the server side is authenticated with a MAC e.g. HMAC-SHA256 using the user's symmetric key e.g.

[user id], [contact id], [public key fingerprint e.g. 256 bits hex], [verified flag e.g. 0x00 or 0x01], [MAC(user id || contact id || public key fingerprint || verified flag)]

It will then be up to the users to verify that key is correct (out of band) after that point to set the verified flag to true (0x01).

However after analyzing this design, I see that there are some attacks possible which make this design not truly secure in the end-to-end paradigm:

1. The cloud provider can selectively delete the records in the contacts_fingerprints table, so when a user logs in again to fetch the data, they may not notice that the user they are communicating with is no longer verified. E.g. the client just re-fetches the public key and saves it again because maybe it thinks there was a network error or it got corrupted or something. This can then be used to perform a MITM attack on the user. Because the record is also not encrypted this can be used to target specific users.

2. The cloud provider can archive and keep previous database records e.g. at a time when the contact relationships were created and the fingerprints weren't verified. Then at a later point, after the record was updated with a verified fingerprint, they can choose to roll it back to a previous version that was unverified. Then when the user logs in and re-fetches the data they download the old record and they may not notice that the user is unverified anymore. This could be used as an advantage for the service provider to MITM the user e.g. when the contact relationship is established, the provider always serves up a MITM public key, that gets saved by the user automatically. When they try verifying, then the client fetches the real key for verification and thus when confirming fingerprints out of band it checks out and they update the record with the correct key and verified flag.

What can be done to redesign this system and prevent these attacks?

Answer 1

I thought of a few ideas:

1) For users to have trust in the details of their contacts (their User ID, Name, Email etc.) then the users table records must be signed as well by each user with their private key. All contact records must be verified upon retrieval by the user. For example, for a user record you would store this:

[User ID], [User Email], [Name], [Public Key], [Encrypted Private Key], [Encrypted Symmetric Key], [RSA-SIGN(User ID || User Email || Name || Public Key || Encrypted Private Key || Encrypted Symmetric Key)]

2) The contacts_fingerprints table should be eliminated and the Public Key Fingerprint and Verified Flag needs to be grouped into a single record on the users_contacts table. Then if a record is deleted, the user will notice as they will not be contacts anymore and will not be able to communicate with that contact without adding them again. For example:

[User ID], [Contact ID], [Public Key Fingerprint], [Verified Flag], [HMAC-SHA-384(User ID || Contact ID || Public Key Fingerprint || Verified Flag)]

3) The users_contacts table records should be mostly encrypted to prevent targeting individual contacts for man-in-the-middle attacks and determining which users had not been verified yet in order to make the attack less noticeable. For example:

[User ID], [AES-CTR(Contact ID, Public Key Fingerprint, Verified Flag)], [HMAC-SHA-384(User ID || AES-CTR Encrypted Data)]

4) We can go one step further and instead of storing individual database records we can store them all concatenated together, encrypted and authenticated. If the items are separated by tag length values (or even comma separated or JSON) this may simplify retrieval. This would prevent tampering with any of the contacts as they are a blob of random data so targeting and deleting particular contacts is not possible. For example, this could be stored as:

[User ID], [AES-CTR(Contact ID 1 || Public Key Fingerprint 1 || Verified Flag 1 || ... || Contact ID 24 || Public Key Fingerprint 24 || Verified Flag 24)], [HMAC-SHA-384(User ID || AES-CTR Encrypted Contact Data)]

5) To prevent rollback to a previous database record where the contacts were not verified we should store a Last Updated Timestamp. The timestamp would be updated any time there is a change to any contact's Public Key Fingerprint or Verified Flag. That timestamp would need to be converted to a human readable date and shown to the user as a full screen interstitial modal dialog when they log in to the client app and have fetched the data from the server, for example, with the message: "Your contact data was last modified at 15:34, 7 May 2017. If this time is earlier than you remember then your address book has been tampered with. Re-verify your contacts before performing any actions with them.". Then they can make an educated decision about whether their account was tampered with. For example, they remember verifying contacts with Bob 2 days ago, but when they log in and fetch all the data from the server again, the last updated date is shown as two weeks ago. Sure enough Bob is missing his Verified check/tick icon next to his contact name. Now the user knows something fishy is going on. For example, to store this you would do:

[User ID], [AES-CTR(Last Updated Timestamp || Contact ID 1 || Public Key Fingerprint 1 || Verified Flag 1 || ... || Contact ID 24 || Public Key Fingerprint 24 || Verified Flag 24)], [HMAC-SHA-384(User ID || AES-CTR Encrypted Contact Data)]

6) The final improvement along with the previous improvements would be to prevent users from creating a contact relationship without them verifying the Public Key Fingerprint first. This means the client user interface forces them to verify it before saving the contact record and allowing them to communicate. This may be a bit less user friendly however it definitely prevents completely relying on the user's memory. It also prevents rollback back to an earlier database record because if there is a rollback, then that contact disappears and they can no longer communicate with them. They have to re-add them and re-verify the public key again. Also because users are forced to verify it provides less incentive for the service provider to try perform a man-in-the-middle attack as they will likely be found out immediately.

---

In summary, the purpose is to make it as difficult as possible for an attacker or the server to tamper with the server side data. If they do tamper with it then it will be detected and if 6) is also implemented also it will prevent an insecure communication from taking place to the elimination of the possibility of man-in-the-middle.

Answer 2

The encrypting party should sign or MAC a "hash chain" of the records in the database upon save, and validate on read.

Basically, do things the same way Git handles adding or removing files from a directory, but use HMACs or RSA signatures instead of plain SHA-1 hashes. So you would compute HMAC(newdata,HMAC(olddata)) on each save, and store that result with the data. newdata and olddata are some canonical sorted encoding of each data collection (or subset).

This encodes the entire history of the database into the data itself. As it can be expensive to compute MACs of everything on every save, you can break things up like Git does, into "directories" of object groups, so you don't need to re-MAC all items on every save. Basically, a Merkle Tree.