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

  • 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.

    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.

    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).

    So, the user must enter their password to decrypt? That is incompatible with your legal requirement to decrypt on request.

    @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: 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.

    Would the person who gave downvote care to explain why?

    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.

    @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.

    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, 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, 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.

    @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.

    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...

    @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.

    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.

    @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"

    In what country is this, if you don't mind me asking?

    @Monika what country is this?

  • Tom Leek

    Tom Leek Correct answer

    7 years ago

    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.

    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.]

    Does any 'multiple public-key encryption, decrypt with related private key'-scheme exist? or has someone yet to figure this one out?

    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.

    I should enrol myself back into university :-)

    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, Additional Decryption Key (ADK) is interesting. Could you maybe expand your comment into an answer?

    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.

    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.

    @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.

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM

Tags used