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 – 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
  • 172,594
  • 29
  • 349
  • 481
  • 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
  • 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 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 and are hard pressed for 2^128. Wikipedia: publicly known AES 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