50
$\begingroup$

I would like to share access to encrypted data among many recipients. I do not know the recipients ahead of time (when encrypting the data). Once the data is encrypted, I do not have access to the plaintext (so I cannot re-encrypt).

Right now, I have a shared secret key that is distributed to recipients as they are granted access to the data (again, encrypted so I do not have access ot the shared key). Unfortunately, that means any recipient of the shared secret can leak the key, compromising the data for everybody.

I can't really prevent "bad" recipients from the leaking the key (or the plaintext, for that matter), but I would like to be able to distribute unique keys to each recipient so that if a key is leaked, I can determine who did it.

I think I want a symmetric encryption scheme where the ciphertext can be decrypted by a set of keys, rather than a single key. Each secret key is unique and it's hard to derive one secret key from another (so one recipient cannot forge another's key), but its simple for me to generate new secret keys (so I can easily add new recipients).

Does such a schema sound familiar?

$\endgroup$
  • 3
    $\begingroup$ So your role is to just grant / deny access, but not access contents. I'm pretty sure, one could apply some fancy tricks related to proxy re-encryption here (where you'd get a special key, that'd allow you to re-encrypt data without seeing it). But that's not really my field of expertise, so I can't give a full / satisfying answer. $\endgroup$ – SEJPM Aug 16 '16 at 19:44
  • $\begingroup$ Exactly right - I can only grant / deny access. I looked into proxy re-encryption but I think it's too resource intensive. In the full system, each row of data is encrypted with a unique symmetric key. The "shared key" in my description is used to encrypt that unique key. With Proxy Re-Encryption, I could encrypt (and re-encrypt) the unique key and get rid of the shared key, but I would have to do that for each row of data and for each recipient. $\endgroup$ – Justin Bailey Aug 16 '16 at 20:23
  • 3
    $\begingroup$ Is this for data being generated on the fly, or data where there's too much content to simply download? If not, it seems to me the easiest attack is to just use your key, decrypt everything, and the publicize the data, which would not be protected under your approach. $\endgroup$ – Cort Ammon Aug 17 '16 at 0:48
  • 1
    $\begingroup$ They could compromise the key, yes. But they could as easily (technically) leak the whole data instead. From an information point of view, it is the same. $\endgroup$ – Aron Aug 17 '16 at 1:01
  • 3
    $\begingroup$ If you know the number of recipients (and I don't see how you could have an unbounded number of recipients if each needs a unique key), can you use something like GPG to encrypt the file with a set of public keys that you generate, then distribute the individual private keys to whoever needs to unlock the file? $\endgroup$ – Johnny Aug 17 '16 at 15:56
54
$\begingroup$

This is known in the cryptographic literature as "traitor tracing". See, e.g., the following seminal paper:

An efficient public key traitor tracing scheme. Dan Boneh and Matt Franklin. CRYPTO 1999.

They show a public-key encryption scheme where each possible recipient has their own private decryption key. If an authorized recipient discloses their decryption key, it's possible for the authority to figure out whose key it was. Moreover, they consider a further challenge -- what if a coalition of authorized recipients pool everything they know, and come up with another decryption key that is different from each of theirs but still works, and they leak that new key? -- and they show how to deal with that challenge as well.

There is an entire line of research that proceeds forward from there.


That said, this is often the wrong kind of solution in practice, for most situations. You are assuming/hoping that the adversary will publish their decryption key. But what if they don't? What if they do something else? There are all sorts of ways the adversary could cause problems without publishing their decryption key:

  • For instance, the adversary can leak the decrypted data without leaking the decryption key (this is the killer problem with all of these traitor tracing schemes that has rendered them mostly irrelevant in practice).

  • Alternatively, the adversary could make available an API that provides "decryption as a service".

  • Or, the adversary might release software for decryption that embeds the key but in an obfuscated form.

Traitor tracing doesn't help with any of those adversarial strategies. So, beware that your threat analysis might be based on too narrow a view of what an attacker can do.

More fundamentally: this approach has seen no adoption in commercial systems (as far as I am aware), because of the extreme ease of acquiring false identities. If you're going to sell access to paid content for $20, and you accept credit cards for payment, it's far too easy for someone to get a stolen credit card number, sign up and gain access, and then publish the decryption key (or the decrypted content). Now what are you gonna do? Even if you can trace back to the associated credit card number and name provided during signup, that name is surely fake, and the name on the credit card account is someone else. At that point you realistically have no way to identify the perpetrator and no recourse. All the fancy crypto in the world won't save you.

That's why these kinds of schemes might not be as useful as they at first appear, except in some special and limited circumstances.

$\endgroup$
  • $\begingroup$ I didn't read the publication - but wouldn't the possibility of identifying the traitor mean that each party obtains a differnt plaintext? How could I detect the traitor if "ATTACK AT DAWN" is leaked unless the other parties receive a different message? $\endgroup$ – Hagen von Eitzen Aug 17 '16 at 19:27
  • 3
    $\begingroup$ @HagenvonEitzen, nope. In Boneh & Franklin's scheme, there are multiple "equivalent" private keys, and each recipient recieves a different one. They all decrypt correctly and allow everyone to receive the original message (i.e., each party receives the same plaintext, even though they have different private keys). It's amazing stuff! But, like I wrote in my answer, nothing prevents a recipient from leaking the plaintext rather than leaking the key; if they do, traitor tracing won't help you identify who was responsible. $\endgroup$ – D.W. Aug 17 '16 at 19:52
  • 2
    $\begingroup$ @HagenvonEitzen Well, if you don't need the same cleartext result, then that would be trivial - you just make a different message and a separate key for each party, and if it's leaked then the leaked artifact is unique. $\endgroup$ – Peteris Aug 17 '16 at 21:21
  • $\begingroup$ @HagenvonEitzen With "ATTACK AT DAWN" the traitor may wish to prove the authenticity of the plaintext by providing the decrypt. $\endgroup$ – Aron Aug 19 '16 at 9:04
9
$\begingroup$

I can't really prevent "bad" recipients from the leaking the key (or the plaintext, for that matter), but I would like to be able to distribute unique keys to each recipient so that if a key is leaked, I can determine who did it.

If an adversary acquires one of the recipient keys, they can do two things:

  1. Decrypt the ciphertext, which recovers the plaintext.
  2. Disclose the recipient key to you, which identifies the recipient that leaked the copy.

Now, if we apply Kerckhoffs' principle, we assume that the adversary knows the details of your scheme. This means that they would know that they have this choice, and would exercise it to further their own goals, not yours.

So this is a bit funny; to achieve your goal of identifying the leaker, you need the adversary to simultaneously be your collaborator in other regards. This certainly isn't impossible, since their goals may partially align with yours and lead them to choose #2. But it's an unusual scenario, I'd say, and you might want to articulate why they'd do that—what are the adversary's goals?

The other way this could go is that the adversary doesn't know the details of your scheme. In that case if they unwittingly disclose the recipient key you achieve your goal of identifying the leaker. But let's not kid ourselves, this would be security through obscurity.

$\endgroup$
  • $\begingroup$ I can see a scenario where secret keys are distributed to e.g. hacker forums to decrypt content. If that key is unique to a specific recipient then you'd know who leaked the key if you run into it. In other words, the recipient would have good cause not to leak the key to "the masses". $\endgroup$ – Maarten Bodewes Aug 16 '16 at 21:14
  • 2
    $\begingroup$ I agree we need a threat model, but I think Maarten's rationale is more than sufficient to show why this is still valuable. It's easy to see situations where distributing the key would not negatively impact the attacker (such as if all they care is that they decrypt a file). In those cases, they may be willing to throw the original keyholder under a bus, by publicizing their key even if they know. This seems very similar, in fact, to a famous way of detecting moles where you give many people slightly different wordings on the same document, and see which wording surfaces. $\endgroup$ – Cort Ammon Aug 17 '16 at 0:46
  • 1
    $\begingroup$ Security through obscurity is not not security, it's just not sufficient security. $\endgroup$ – user253751 Aug 17 '16 at 6:39
  • $\begingroup$ I've formalized the system a little bit in my "answer". Ignoring the immediately desired use case, it doesn't seem to be any question of security through obscurity , just a system of complementary keys but otherwise much like any other symmetric cipher. $\endgroup$ – Thomas M. DuBuisson Aug 17 '16 at 18:50
4
$\begingroup$

More than a comment and much less than an answer, I believe the desired crypto system is a construct that provides three functions $(G,E,D)$ where

  • $G$ is a random algorithm that results in sets of keys, $\cal K$
  • $E : k \rightarrow \{0,1\}^n \rightarrow \{0,1\}^n$
  • $D : k \rightarrow \{0,1\}^n \rightarrow \{0,1\}^n$
  • $\forall k_i, k_j \in \cal K . D_{k_j}(E_{k_i}(p)) = p$
  • $\forall k \in \cal K$ it is computationally infeasible to find $p$ given $E_{k}(p)$ without a $k_t \in \cal K$
  • Given $k \in \cal K$ it is computationally infeasible to find $k_2 \in \cal K$ s.t. $k \not = k_2$

I've omitted explicit quantification of $\cal K$ from the larger space (set of sets) produced by $G$ but it should be universal.

$\endgroup$
1
$\begingroup$

I would like to share access to encrypted data among many recipients. I do not know the recipients ahead of time (when encrypting the data). Once the data is encrypted, I do not have access to the plaintext (so I cannot re-encrypt). ...

Does such a schema sound familiar?

Except for the multiple private keys, yes it does. It sounds like DRM or IRM. Both are envisioned to restrict the operations users can perform on the data. For IRM, usage tracking is also a design goal. But neither appear to have explicit leakage tracing as part of their goals.

$\endgroup$
1
$\begingroup$

There's something odd with your description: If you give access to Alice and Bob today, but you must be able to give Charlie access tomorrow if he signs up, you need to have access to the data, either with a shared key or a not-yet-used key that is to be given. So I will skip over this requisite.

When encrypting to multiple recipients, the normal approach is that there is an underlying (random) key for a symmetric cipher and this key is then encrypted to each of the recipients with their public key.

Of course, that key is hidden by the implementation. So if you use for instance PGP (as suggested by Johnny), they would simply input the encrypted file (and their private key, which already installed, in PGP would be implicit).

If you used PGP, you could generate a number of keys, encrypt the secret with them and distribute to the recipients. You only need to remember to whom you sent each key.

Or, if they already have a key (either from a previous communication or locally generated), you can simply encrypt to their key. But you will still need some extra dormant keys in order to be able to grant access to old messages to new users.

The alternative would be that another user (with access) had grant him access to the old messages (basically, the re-encryption that is too costly in your setup).

Are all your messages (rows) granted to the same people? That would allow you to treat the as a long message (with different IV, based on a ROWID or from an explicit IV column) with a single key encrypted to the public key of each recipient.

$\endgroup$
-2
$\begingroup$

Assuming your data is sufficiently easy to fake a digital signature is required in order to prove it actually originated from you. Therefore I propose the following:

  • in addition to encrypting the data with the shared secret key, obtain its hash, e.g. sha256
  • whenever someone gets access to the shared key, sign the secret's hash concatenated with a unique identifier for the new recipient and send them that individualized signature

The only way the recipient can prove the secret stems from you is by verifying the signature, which requires their unique identification to be included.

Of course a leak could still try and obtain another recipient's means of verification to frame them, so you should asymmetrically encrypt the individualized signature to the recipient and instruct them to not store it decrypted.

$\endgroup$
-2
$\begingroup$

There are several complicated answers already, but I believe there is actually a simple solution here:

Add extra data to the key that is not needed for decryption

If you do this in a smart way, you would be able to generate as many keys that you need, on the fly. And you would be able to tell whose key has leaked.

Naturally, this requires the person who receives the key to be unaware of the methodology.

Example

Suppose your key is abcdefgh

Then a trivial way to add more information would be to give out a key like this:

abcdefghijk...

And then make sure the external key gets parsed back to the original, before the actual decription is attempted.

Of course you could do this in more complicated ways to prevent people from discovering the methodology by accident.


Note that this solution is not very robust if:

  1. The attacker knows your method
  2. The attacker has several keys

But then again, I believe that is hardly an issue as someone who can leak the key can just as well leak the whole plaintext. Therfore simple is good in this situation!

$\endgroup$
  • $\begingroup$ I see a downvote so I wonder what the problem is with this answers? Is it fundamentally flawed or just impractical to implement? $\endgroup$ – Dennis Jaheruddin Aug 19 '16 at 7:05
  • 1
    $\begingroup$ It's security by obscurity. If we follow Kerckhoff's principle, and assume the attacker knows the security algorithm but not the secret keys, they just have to permute the additional data. I know you point this out in your answer, but see the answer from D.W. for a much more robust scheme (and why it doesn't actually help). $\endgroup$ – Martin Bonner supports Monica Aug 19 '16 at 7:52

protected by Maarten Bodewes Aug 22 '16 at 23:24

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.