68

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.

Community
  • 1
Monika
  • 1,092
  • 1
  • 10
  • 21
  • 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
  • 1
    The benefit of per-user encryption is that all decryption sequences require password. In other words, there are no decryption keys stored anywhere on disk (in unencrypted form). – Monika Oct 29 '14 at 16:12
  • 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
  • 2
    @paj28, exactly. That is why I asked the question. Note that while the law requires us to be able to decrypt any document, it does not require this to be an automated process. So we can still keep our 'master-password' a secret. – Monika Oct 29 '14 at 16:36
  • 1
    @Monika: if you store your "master password" in an offline machine or in a piece of paper, there's indeed additional security in per-user encryption. – Emilio M Bumachar Oct 29 '14 at 19:24
  • Would the person who gave downvote care to explain why? – Monika Oct 29 '14 at 22:20
  • I would consider it dishonest to offer this service, as you legal requirement to be able to decrypt and document is not compactable with what your customers can reasonable expect. – Ian Ringrose Oct 30 '14 at 10:00
  • @IanRingrose, The service offers users the option to store documents so they can access them whenever they need. We encrypt the documents because we respect the idea of privacy, not because the contract with the customer requires it. As a second note: the service is used by business customers exclusively, who typically would otherwise (or simultaneous) use their email inbox to the same effect. – Monika Oct 30 '14 at 11:15
  • 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
  • @JMK, If you cannot provide the password, the law assumes you to be working against the request. The law tries to prevent people from claiming they 'forgot' their password and is formulated as such. The side effect of this formulation of the law (the case in this question) is not something they mind. – Monika Oct 30 '14 at 12:04
  • 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
  • 2
    @IanRingrose, I'm not a lawyer and I don't think this is the place to discuss whether or not the this law should be interpreted as they did. In the mean time, I *do* have to come up with a solution that satisfies the two requirements as described in my question. – Monika Oct 30 '14 at 12:21
  • 1
    A strictly practical question: While you can change key storage as suggested below for new documents, how do you intend to handle anything uploaded before the change was made where only the user has a copy of the decryption key... – Dan Is Fiddling By Firelight Oct 30 '14 at 13:25
  • @DanNeely, that one is bugging me also. The whole thing with this issue is that the law has been designed by people who apparently did not think it through or, more likely, lack the technical 'know how' to see all the implications and impossibilities it creates. For now, I think I should a) ignore it or b) find myself another job or something. – Monika Oct 30 '14 at 14:03
  • 2
    Wait, it is not YOUR encrypted data and keys - it's USER's. Why YOU required to give keys to whatever law agencies? You only store random data for users so send them to recover keys from users. – Oleg V. Volkov Oct 30 '14 at 16:18
  • 3
    @Monika If the lack of ability do decrypt can be held against you, this makes you subject to some kind of blackmailing: Imagine a user uploads a random bit sequence and tricks the govt into asking you for a "decryption" – Hagen von Eitzen Oct 30 '14 at 16:21
  • 4
    In what country is this, if you don't mind me asking? – apnorton Oct 30 '14 at 22:12
  • 1
    Possibly related: [SuperUser: Encrypting a document with multiple keys, and making people accountable for those keys](http://superuser.com/q/638358/53590) – user Oct 31 '14 at 08:15
  • @Monika what country is this? – simbo1905 Jan 11 '15 at 12:33

6 Answers6

81

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.

Community
  • 1
Tom Leek
  • 170,038
  • 29
  • 342
  • 480
  • 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
  • I should enrol myself back into university :-) – Monika Oct 29 '14 at 18:56
  • 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 06:38
  • @dave_thompson_085, Additional Decryption Key (ADK) is interesting. Could you maybe expand your comment into an answer? – Monika Oct 30 '14 at 14:42
  • 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
  • Arguably, if the K_D key is document-specific, then sharing the key and the document are the same thing. One could say that you cannot force somebody to forget a document any more than you can force him to forget a key. In that sense, "revoking" an access is not well-defined. – Tom Leek Oct 31 '14 at 11:34
  • @Chris I think the best tradeoff here would be if there were a new key generated each time the document was edited.. Part of the upload process would then be encryping the new key for each person that should be allowed to write to the document. – iCodeSometime Jun 20 '19 at 14:43
19

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.
antispy
  • 315
  • 1
  • 3
  • 7
    8. Install a warrant canary before getting a secret government subpoena. –  Oct 30 '14 at 03: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](http://www.theguardian.com/world/2013/jun/17/edward-snowden-nsa-files-whistleblower) 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. – user Oct 31 '14 at 08: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](http://security.stackexchange.com/a/6149/2138) and are hard pressed for 2^128. Wikipedia: [publicly known AES attacks](https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#Known_attacks). – user Oct 31 '14 at 08:32
  • "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" - In general I agree, but in the case of quantum computers, all currently secure public key algorithms (against classical computers) will be rendered obsolete and insecure. Also there are time-tested and reviewed post-quantum algorithms that are still considered secure today (if large key sizes are used) e.g. McEliece. There is a post-quantum algorithm competition now to find some secure options for the future. Combining two finalists would be robust. – antispy Feb 26 '18 at 22:30
  • "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." - Government sock puppets *love* to repeat this. Snowden is *not* qualified to say *which* crypto systems can be relied upon. After all the documents he had access to detailed *nothing* about cryptanalysis techniques. In fact the only information we have about BULLRUN was a slide saying "don't ask about it". Know why? It is Top Secret ECI SCI information. Only a few of the NSA cryptanalysts know. – antispy Feb 26 '18 at 22:35
  • " Wikipedia: publicly known AES attacks" - That's just it. *Publicly* known attacks. What do NSA know how to break? There was another leaked NSA slide saying they have classified *in-house* techniques against block ciphers like AES. Trust AES at your own peril. Encrypting with two algorithms is a much safer idea e.g. AES-CTR with one key, then ChaCha20 with another key. – antispy Feb 26 '18 at 22:40
  • @user related key attacks are not related to encryption where we select keys randomly. It is important in the concept of building hash function out of AES which can cause attacks. – kelalaka Dec 01 '21 at 20:40
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.

Community
  • 1
simbo1905
  • 390
  • 2
  • 10
  • 3
    I am very unhappy to learn that I live in a country with such a law http://goo.gl/NdC2T2 – simbo1905 Jan 11 '15 at 14:44
  • This answer unfortunately doesn't work for us because there is enough information stored on the server to be able to decrypt stored documents. Therefore, it is possible for authorities to obtain the plain document. – CompanyDroneFromSector7G Jun 24 '19 at 12:22
  • i answered the body of the question where the author is required by authorities to be able to decrypt the document. if your situation isn't like theirs then the answer to their situation won't help you. it is possible to do encryption and decryption at the client such that the server cannot decrypt any content. use SRP password verifiers (not salted passwords) so that you cannot even authenticate to yourself as your customer (e.g. thinbus-npm). have customers exchange public keys and exchange file keys encrypted with private keys. use shamir's secret sharing for peer-2-peer password recovery. – simbo1905 Jun 27 '19 at 18:27
  • do all encryption at the client (browser/phone). encrypt private keys with password and store on server (srp means you don't know the password). if they lose their phone they can download private key and use it. use shamir secret sharing at phone to backup password to friends. the password can only be recovered on their phone. all you need to ensure is that they use a very strong password. check the hash against Pwned Passwords database and use a strong password checker all at the client. Q.E.D. – simbo1905 Jun 27 '19 at 18:41
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.

paj28
  • 32,906
  • 8
  • 93
  • 130
  • 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 07: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.

CompanyDroneFromSector7G
  • 153
  • 6
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.

madscientist159
  • 111
  • 3
  • 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