61

Current setup

We have a service that allows users to upload documents through a website and stores the uploaded documents encrypted on disk.

The documents on disk are encrypted with a per-user key, which is randomly generated upon account creation. This document key is stored in a database field which is encrypted with the user's password as the key. When the user (owner) want to download a document, they need to provide their password, which is used to decrypt the document key which is in turn used to decrypt the document.

We have chosen this pattern to negate the need to re-encrypt all encrypted documents when the user chooses to change their password: we only need to re-encrypt the document key.

This setup work fine (and we think it is a secure pattern1).


Required changes

Unfortunately, we have two new requirements to implement.

  1. By law, we are required to be able to decrypt any documents we have on disk, upon request by the government;
  2. Someone has decided that the owner of a document should be able to share the uploaded document with other users.

I don't know how to implement those requirements while keeping the documents stored with per-user encryption.

So, my question is:

Is there a known pattern that allows for encrypting documents so that they can be decrypted by one or more parties, where the parties in question are to be determined upon document encryption?



Update:

Some background information on the law mentioned above:
In fact, the law does not state that we are required to build in a back door. The law makes it a criminal offence to not hand over the key to any encrypted data you have2 if the police requests the key3. A result of this is that we who host the data need to have a back door, or face prosecution in case we cannot decrypt the data when requested. However, other than in some other countries, we are free to communicate the fact that we received an order to decrypt documents. These laws are unfortunately not uncommon.

Informing our customers and the public:
As I indicated in a comment before, I fully intend to pull my weight to makes sure this policy is clearly communicated to our customers. Privacy statements need be changed and TOS need to be updated.
Public awareness on the one hand and making sure 'bad laws cost money' on the other, are the best method I have available to protest against such laws.
However, at the same time I'm kinda sceptical about the impact of such statement. Most people simply don't care. At the same time, many people use their email and inbox to store and share documents. So from that perspective our service is (still) a huge improvement (and it is the reason some of our customers require their employees to use it).



1. If there is a glaring hole in this method, feel free to comment on it.
2. Lawyers have figured that 'data you have' is meant to include all data stored on physical devices you own (I'm not a lawyer, so this my lay-persons translation of what they concluded).
3. Yes, not some fancy security office, but police. There are some safeguards in when they can request password, but that doesn't change the implications of this law. The big question is what happens when you truly forgot the password to some data. The minister has indicated that it is the responsibility of the owner of such encrypted data to then delete it. But no such case has yet (as to my knowledge) been tried in court.

  • 4
    What's the benefit of doing per-user encryption at all? Sounds like you might as well just use full-disk encryption, and have the application verify passwords for downloads. – paj28 Oct 29 '14 at 15:59
  • 3
    So, the user must enter their password to decrypt? That is incompatible with your legal requirement to decrypt on request. – paj28 Oct 29 '14 at 16:21
  • 4
    Surely the law only requires you to decrypt if you are physically able to do so. If you make it impossible for you to decrypt user data then there's no problem right? – JMK Oct 30 '14 at 11:59
  • 3
    @Monika, I don’t believe the law is us you state, as any backup service that backup a file from my machine that I have already encrypted would be required to be able to hand over the key. Likewise if one of your customers encrypt a file themselves before using your system to share it. – Ian Ringrose Oct 30 '14 at 12:12
  • 4
    In what country is this, if you don't mind me asking? – apnorton Oct 30 '14 at 22:12
70

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.

  • 1
    I was hoping for some elegant multiple public-key encryption with related private key decryption scheme, but this is probably simpler (hence, better). [and don't worry, I will see to it that the privacy statement and TOS are changed; public awareness on the one hand and making sure 'bad laws cost money' on the other, are the best method of protest I have available, against such laws.] – Monika Oct 29 '14 at 16:41
  • Does any 'multiple public-key encryption, decrypt with related private key'-scheme exist? or has someone yet to figure this one out? – Monika Oct 29 '14 at 17:10
  • 2
    The OpenPGP scheme is one example; but you still get per-recipient overhead. There are "broadcast encryption" schemes that try to reduce this overhead; but you cannot remove it completely. – Tom Leek Oct 29 '14 at 17:13
  • 3
    And one PGP implementation already does item 1 (govt request) or at least did. The "commercial" version from PGP Inc, back around 2000 when the US govt was pushing Clipper etc, added a kindler gentler alternative called ADK Additional Decryption Key which enables the owner to decrypt when necessary, in this case the govt request. I haven't kept track, but some googling suggests the new owner Symantec maintains this ability. You should certainly setup controls so it is only used when legally proper, whatever that is in your jurisdiction. – dave_thompson_085 Oct 30 '14 at 6:38
  • 4
    Note that the proposed setup does not fulfill the requirement from the question that documents can be shared "without sharing the encryption key". You are sharing it in an encrypted form, but still sharing it. This means that if you want to revoke someone's access you will still need to re-encrypt the document with a new K_D and share that (in encrypted form or not) with all the remaining users who should have access. – Chris Oct 30 '14 at 19:22
18

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.
  • 7
    8. Install a warrant canary before getting a secret government subpoena. – user57007 Oct 30 '14 at 3:22
  • 3
    The newer public key algorithms have a much shorter track record than RSA, DSA and EC. Given that progress in quantum computing has been slow, and progress in breaking the newer algorithms has often been surprisingly fast, it seems reasonably likely that the security services has attacks against some of these algorithms. – James_pic Oct 30 '14 at 11:52
  • 2
    I'm not happy with the ethical part of the whole issue either, in fact fact, I'm trying to see how we can minimize the damage. Please also see update-paragraph in the question. – Monika Oct 30 '14 at 11:55
  • 5
    This was a pretty good answer until the last two bullet points. Using untested algorithms in favor of well known, thoroughly examined ones that have been found to be quite secure in practice is a bad idea, for reasons that have been discussed over and over again. Edward Snowden was confident in using GnuPG to communicate securely, and has stated that "Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on.", with a strong caveat of endpoint security. – a CVn Oct 31 '14 at 8:26
  • 1
    The best publicly known semi-practical attack against AES-256 appears to be a related-key attack with a complexity of about 2^99.5. The best known full key recovery attack again on AES-256 is 2^254.4 complexity. The former can probably be avoided in the key selection, and the latter is more of an academic curiosity than anything else, given that we can't even realistically count to a trivial 2^192 and are hard pressed for 2^128. Wikipedia: publicly known AES attacks. – a CVn Oct 31 '14 at 8:32
7

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.

  • 2
    I am very unhappy to learn that I live in a country with such a law goo.gl/NdC2T2 – simbo1905 Jan 11 '15 at 14:44
4

As a direct answer to your question, Tom Leek's answer is spot on.

However, I recommend you take a different approach: abandon per-user encryption.

You will still use network encryption (HTTPS), password hashing, and if you want, full-disk encryption on the server. However, don't use any encryption beyond that. Your application still decides who can view a particular document: the user who first uploaded, your administrator for legal purposes, and any users who have had the document shared with them. In this arrangement, it's quite easy to meet all your requirements.

So why do I suggest abandoning per-user encryption? Because it's complex and difficult to implement, and it doesn't actually add much security. You haven't really explained what benefit you wanted for per-user encryption, but I presume it's to keep documents safe in case the server is electronically or physically compromised. Both those should be extreme events: you should be taking standard precautions like firewalling to prevent these happening. But if such an extreme event does happen, actually an advanced attacker can get your users' documents anyway. They lie in wait quietly, waiting for your users to login, then capture the password and decrypt the documents.

  • Thanks. The intend is indeed to protect the user uploaded documents against theft by a malicious third-party. The question is formulated from the perspective of our current implementation and how to change it. Yet, whole disk encryption may be a better solution. – Monika Oct 30 '14 at 11:58
  • I agree with most of what you said but the last point. Surely the point is existing documents can only be decoded if the private key is compromised and not login details. – Sydwell Sep 13 '16 at 7:48
3

I know this has already been answered, but...

I have to do something very similar on my website.

Documents are encrypted but may be shared with other users.

Being in the UK, I am required to share security details with the security services if so required, but only if I have them. I don't have access to them so this is not a problem. (I am also not allowed to notify users that details have been requested - the price of freedom!)

Every user has an asymetric key pair which is used to secure their documents. The public keys are stored in plain text but private keys are encrypted using blowfish, with a 128 bit key derived from the users' password.

When a user wants to share a document it is decrypted and a copy is made and encrypted using the public key of the target user, which being in plain text is easy to do. When the target user logs-in they can decrypt the document using their secure private key.

Obviously if shared with several users there must be one copy for each.

1

As the stated requirements force the encryption to be essentially for "show" (security theater?) and basic theft protection, not secure document-level protection, I'd recommend basic full-disk encryption using LUKS or similar. That way you have the master key to the entire archive, and can use non-encryption-based schemes to control per-user access to the various documents. Per-document encryption really doesn't buy you anything except hassle in light of requirement #1.

Also, I would like to second the answer of antispy above. At minimum the proposed service is highly unethical and in some jurisdictions would even be considered fraud depending on the terms of service/what you disclosed to your users.

  • I'm not happy with the ethical part of the whole issue either, in fact fact, I'm trying to see how we can minimize the damage. Please also see update-paragraph in the question. – Monika Oct 30 '14 at 11:54
  • 1
    Understood. Backing off from the technical question and assuming that you and the government have identical access rights (by law) then as stated I see no advantage to per-document encryption. Put another way, you and government share root privileges on a multi-user system; to comply with this law both of you can read any documents at any time. Merely having a root account does not make a multi-user system insecure; it boils down to who will use that power and for what purpose. I do wish I knew what country this was so it could go on a list of places not to live... – madscientist159 Oct 30 '14 at 14:50

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.