Pattern to allow multiple persons to decrypt a document, without sharing the encryption key?

You need a per-document key, not a per-user key. Well, you also need per-user keys, but that is another matter.

Namely, each document D is encrypted with a key KD. That key is generated randomly the first time the document is imported in the system. Each document has its own key. The key for a document cannot be inferred from the key on any other document.

Each user U also has a key KU. Therefore, if you need document D to be accessible to users U, V and W, then you store EKD(D) (encryption of D with the document key), along with EKU(KD), EKV(KD) and EKW(KD) (encryption of key KD with the keys of user U, V and W). These "encrypted keys" have a small size (a few dozen bytes, regardless of the document size) so this scales up.

To make things more practical, you may need to use asymmetric encryption for user keys: encryption of D uses a convenient symmetric system (say, AES), but the "user keys" will be of type RSA (or another similar algorithm like ElGamal). That way, if user U wants to share the document D with user V, then he:

  1. retrieves EKU(KD) from the server;
  2. uses his own private key to decrypt that and recover KD;
  3. encrypts KD with V's public key, yielding EKV(KD).

The beauty of this scheme is that V needs not be present for this procedure, since only V's public key is used.

At that point, what you really have is OpenPGP, a format meant primarily for secure emails. Emails have this "sharing property" (an email may be sent to several recipient) and are asynchronous (when you send the email, the recipient is not necessarily available right away). You would be well advised to reuse OpenPGP, a format that has been reviewed by many cryptographers, and for which implementations already exist.

When you have a sharing mechanism, you can simply put yourself as implicit recipient for every document, and you can read everything. Regardless of law requirements, be sure to notify users through the "usage conditions" that you can technically read everything; otherwise they may sue you for lack of warning.


BUT, we have two new requirements to implement:

By law, we are required to be able to decrypt any documents we have on disk, upon request by the government;

Wow. I really hope you are planning to inform your users that you will be backdooring your service for law enforcement so that they have enough time to delete their data from your service before that happens. That would be the ethical and honorable thing to do.

If you are being forced to do this e.g. by National Security Letter and you are not allowed to speak out about it due to a gag order, then your options are limited:

  1. Get someone in the company to anonymously leak this information to the free press (that in future your service will be backdoored).
  2. Shut down the service for unspecified reasons. Give your users a few weeks to download their data before it will be deleted forever.
  3. Relocate your company, online service and staff to a country where there are no draconian surveillance laws.

It sounds like you've got a secure service already and have attracted some privacy orientated users. Anything would be better than willfully installing a backdoor for law enforcement and screwing over your users. For all you know, as soon as your proposed system is in place for law enforcement they will send you a warrant for all the users' data.

You would be better off shutting the company down, taking your money and starting up a new venture, but this time doing it properly. Here are my suggestions:

  • Start your company in a country without these laws. Host your servers and user data there too.
  • Use an open source client so that users have trust in the software that is running on their computer/device. It will be very difficult to hide a backdoor in future if you are forced to by authorities because someone will notice.
  • All private data encryption keys are stored client side, never on the server. Only encrypted data is stored on the server. All encryption and decryption is done on the client. The server only holds encrypted data. Users have responsibility for backing up their own private keys. Then your company is literally unable to respond to future NSL requests because you do not have the keys.
  • For authentication with the server and letting the user store and download encrypted data from their account, setup some kind of per user public key authentication protocol. Perhaps the server holds the public key for each user. The user holds the private key, then signs every data upload and request to the server. Each client can have the server's public key embedded (pinned) into it to verify responses and encrypted data downloaded from the server.
  • For sharing files with other users, the user can re-encrypt their file with a new symmetric key and share that key using public key exchange with other users on the system. Your service could handle the sharing of the public key for them. However this is dangerous if users cannot completely trust the server and if the server is in a country with hostile surveillance laws. The users do not know if the server is giving them a fake or real public key for the other user, so they would be vulnerable to MITM attacks. This would be one way law enforcement could use to access the unencrypted data for files shared among other users. In this scenario it would be safer if the users know their own public keys and can share them privately with other users when they wish to share data with them.
  • Use newer public key algorithms that are not vulnerable to quantum computers. No RSA, DSA or elliptic curves.
  • Use newer symmetric key and hash algorithms from authors that care about privacy and do not like mass surveillance. For example, Bruce Schneier & Daniel J. Bernstein.

The solution outlined by Tom Leek above has been implemented by the opensource cloud document store ownCloud. The encryption model is outlined here.

As also pointed out in other answers you can do the same thing with OpenPGP/GPG which I outlined in an answer to a related question. To briefly repeat the standard approach:

  1. Each user has a public/private key pair
  2. Each document is given a unique symmetric key with which the document is encrypted and uploaded into the backing storage container. This is called the file-key
  3. Whenever a user is granted access to the file the file-key is encrypted with the users public key

Specifically you want to be able to supply the file-key when compelled to under law. That's an opt-in feature of ownCloud where every file-key is also encrypted with the public key of the system administrator. With ownCloud the intention of the feature is that the user may have forgotten the passphrase to their private key and can ask the administration to grant them access to the file again.

One thing to note is that ownCloud uses a regular database for the user/group data and the file metadata. The actual file blobs can be stored either locally or on an external provider such as Amazon S3 or Google Drive. You can take the same approach; have the client first encrypt and write to an out-of-jurisdiction external blob store encrypted with their own keys then write only the url (typically a 128bit GUID) into your system. Whilst this is far from ideal in terms of system complexity it may well free you from having to comply with a dangerous and oppressive law; as you can only handover pointers to the data.

I think at least one country which is implementing such totalitarian laws is forcing all offshore cloud providers to move their servers into the country for users domiciled within that country. In which case your last resort is to let the users of the system encrypt and write to their own local network drives and store a file path in your system. It is then down to the customer to make off-site backups of such data.

Tags:

Encryption

Recent Posts