4
$\begingroup$

Alice encrypts her data with HER secret key. Then she sends the encrypted data to Bob who should encrypt it with HIS secret key.

Caroline should then eventually get this double encrypted data. Caroline only wants to receive pseudo-random (looking) data which would only be decryptable for her if Alice and Bob BOTH tell her their secret key. She wants to be able to use this fact in court in case she and [Alice XOR Bob] get accused of deliberately saving and/or distributing intellectual property illegally. Caroline therefore wants to be sure that Bob really takes the encrypted data of Alice, encrypts it with HIS secret key and then sends it to her. How can that be achieved? Alice and Bob are allowed to use different encryption algorithms.

I suppose AES is not suitable for this task. I hope I was somehow able to express what I want in a comprehensible way. I know, my English is bad.

Improve this question
$\endgroup$
  • $\begingroup$ Caroline want to check if Bob has encrypted Alice's data when she receives the data, is that correct? $\endgroup$ – SEJPM♦ May 23 '15 at 13:30
  • $\begingroup$ I really like this this question as it's something that may be applicable to many potentially dangerous situations. $\endgroup$ – SEJPM♦ May 25 '15 at 11:48
  • $\begingroup$ @SOJPM Sorry for my late answer. I'm very grateful for your interest in my question. Yes that is what I meant with my question, but for the specific use case I think of it would also be sufficient if Alice could check that Bob encrypted her data. I haven't mentioned that fact in my question because I thought it would cause confusion. $\endgroup$ – user74088 May 25 '15 at 19:34
  • $\begingroup$ In my specific use case Caroline only demands from the protocol that she can only be tricked if Alice and Bob BOTH play against the rules of the protocol. Tricked in this case means that Caroline keeps data which is not [encrypted once with Alice and once with Bob secret key] (The not belongs to the whole [..] expression). Furthermore, contrary to the bounty text in my specific use case the assumption is allowed that Alice stores the message and that she buffers her own symmetric key. Like in the bounty text in my use case Alice can't be trusted to only place correct signatures. $\endgroup$ – user74088 May 25 '15 at 19:38
  • $\begingroup$ ooops, then it was misinterpretation from my side :( But nonetheless I think JD answers your question. $\endgroup$ – SEJPM♦ May 25 '15 at 19:39
5
+100
$\begingroup$

I may be interpreting your question incorrectly, but it sounds to me like you are asking if Caroline can prove (in court or whatever) that she can only gain access to some secret $S$ if both Alice and Bob collaborate in revealing it to her. Unfortunately as you have currently set up the question, I don't think that is possible, because your question establishes that Alice knows the secret $S$ before any encryption is applied (it's "her data", as you put it). Hence, it is always possible for Alice to simply tell Caroline $S$, regardless of whether Bob collaborates.

But, if we modify the set-up a bit, it is possible to prove what you want. We need to assume that neither Alice nor Bob knows $S$, and in addition we need a trusted third party and a secret sharing scheme. Only the trusted third party, Tim, starts off knowing $S$, and he can be trusted to a) not leak any information about $S$ to anyone at any point, and b) to reliably carry out the following three steps:

  1. Tim generates a pad $P$ - a random string of bits equal to the length of $S$.
  2. Tim establishes a secure channel with Alice (using e.g. secure public key exchange and PKI methods to prevent Man In the Middle attacks), and sends her the string $P \oplus S$.
  3. Tim similarly establishes a different secure channel with Bob, and securely sends him $P$.

At this point, Tim has split the secret into two 'shares', and Alice and Bob only know what their own share looks like (i.e. random nonsense).

  1. Alice and Bob then each encrypt their own share using authenticated encryption (e.g. AES-GCM) and their own secret keys.
  2. Alice and Bob now send Caroline the encrypted shares.

This way, no one (aside from Tim) can know what $S$ is unless both Alice and Bob reveal their shares (e.g. by sharing their keys with Caroline). Knowing only one share gives you zero information about $S$ (besides the length), and as such if either Bob or Alice don't reveal their share then $S$ is safe.

As to any concerns about ensuring that Alice and Bob do their part (i.e. properly encrypt their shares) and don't simply forward their shares unencrypted to Caroline, I would note that simply forwarding the unencrypted shares to Caroline is equivalent to encrypting the shares but then revealing the keys to her -- so long as either Alice or Bob does their part properly Caroline cannot know $S$. It takes collaborative effort / incompetence by both Alice and Bob for $S$ to be revealed. If we cannot trust that at least one of the two will keep their key secret and properly run their part of the protocol then no scheme will succeed (so my scheme is not unique in that respect). But given my described scheme, one person doing their part properly is sufficient to keep Caroline provably in the dark.

Improve this answer
$\endgroup$
  • $\begingroup$ I think the question rather aims at: Assuming Alice is given some secret message $m$, now Alice encrypts it and sends it to Bob who has to encrypt it himself. Bob now sends the double-encrypted message to Carol. How can Carol make sure Bob actually encrypted the message (in a way (only) he can decrypt later) and not just forwarded Alice's message? $\endgroup$ – SEJPM♦ May 25 '15 at 14:35
  • $\begingroup$ sorry, the above note doesn't apply, your answer answers that (to some extent). So this leaves the question: How can Caroline make sure / check that Bob and/or Alice not simple just foward the shares to her but encrypt them? $\endgroup$ – SEJPM♦ May 25 '15 at 14:49
  • $\begingroup$ @SOJPM - Simply forwarding the unencrypted shares to Caroline is equivalent to encrypting the shares but then revealing the keys to her -- so long as either Alice or Bob do their part properly Caroline cannot know $S$. It takes collaborative effort / incompetence by both Alice and Bob for $S$ to be revealed. If we cannot trust that at least one of the two will keep their key secret and properly run their part of the protocol then no scheme will succeed (so my scheme is not unique in that respect). But given my described scheme, one is sufficient. $\endgroup$ – J.D. May 25 '15 at 14:58
  • $\begingroup$ Thank you as this basically answers the (second part?) of the question. Please add this to your answer and I'd say (if no better answer rises, we never know) chances are you get the bounty. $\endgroup$ – SEJPM♦ May 25 '15 at 15:03
  • $\begingroup$ @SOJPM - I took your suggestion (see above edits). $\endgroup$ – J.D. May 25 '15 at 15:18
1
$\begingroup$

Here's a simple solution, but with some proviso's that may or may not be acceptable...

Alice's private and public key: $skA$, $pkA$
Bob's private and public key: $skB$, $pkB$
Encryption is $E_x(P)$, where $x$ is the key, and $P$ is the plaintext.
Decryption is $D_x(C)$, where $x$ is the key, and $C$ is the ciphertext.

Summary of Protocol

  1. $A \rightarrow C: E_{pkA}(E_{pkB}(S)) = e_1$
  2. $C \rightarrow B: E_{pkB}(e_1) = e_2$
  3. $B \rightarrow C: D_{skB}(e_2) = e_3$
  4. $C:$ if $e_3 <> e_1 $ abort. Retry from step 2.
  5. $C: purge(e_1,e_3) $

Explanation

  1. Alice encrypts with Bob's public key, followed by her public key, and sends the encrypted data ($e_1$) to Caroline.

  2. Caroline encrypts $e_1$ with Bob's public key, and sends the result ($e_2$) to Bob for decryption.

  3. Bob decrypts $e_2$ and sends the result ($e_3$) back to Caroline.

  4. Caroline can now check that Bob was able to decrypt $e_2$ using his secret key, by checking $e_1$ against $e_3$. If they are the same, it was Bob's public key, and she can continue otherwise she aborts and tries again.

  5. Caroline then chucks away $ e_1 $ and $ e_3 $ and keeps $ e_2 $.

Discussion

  • Alice could simply not encrypt using Bob's public key when computing $e_1$ but this situation is countered by Caroline ensuring that she keeps only $e_2$ and not $e_1$ or $e_3$.
  • Bob cannot learn $S$ without Alice's secret key.
  • Bob cannot cheat because his decryption of $e_2$ is checked against $e_1$.
  • This solution requires 3 encryptions, not 2 as indicated in the question.
  • Lawyers could always argue that $e_1$ was only ever encrypted with Alice's key (and Bob's key wasn't used), and that Caroline kept $e_1$ and then used Alice's corresponding key to decrypt $e_1$. This could be countered by using a third party machine to run the protocol on, the end result of which would be that Caroline takes away only $e_2$ on a usb stick, and the associated data is then securely purged.
  • The end result, if the protocol is followed correctly, is that Caroline can be sure she has something that has at least been encrypted with Bob's public key. To ensure that it is also encrypted with Alice's key, she could run steps 2 and 3 with Alice as well as Bob, with their respective keys, but this would add another round encryption to the scheme. Unfortunately, she doesn't know what has been encrypted but what she does know is she does have something that was.
Improve this answer
$\endgroup$
  • $\begingroup$ I have recognized that my question (probably) is quite vague. Your suggested protocol doesn't work the way I want. But this is not your fault. I will reformulate my question. Maybe someone has the nerves and will answer my reformulated question. Sorry for the confusion I caused and the lifetime that it cost you to think about my question. I'm new to the cryptography scene. $\endgroup$ – user74088 May 27 '15 at 18:16
  • $\begingroup$ @user74088, well I guess the open bounty is somewhat a motivation to answer your question :) $\endgroup$ – SEJPM♦ May 27 '15 at 18:51
0
$\begingroup$

After having thought about this for a considerable amount of time I came up with the following as the easiest and best solution I could think of.

The following protocol assumes that Alice is trusted whereas Bob isn't.
$S_X(P)$ denotes signature by $X$ on $P$.
$E_X(P)$ denotes encryption using the public key of $X$ of message $P$.
$E_{K_X}(P)$ denotes symmetric AES-GCM encryption using the key $K_X$ of the message $P$.
$N_X$ denotes the $X$-th nonce which is used in combination with $E_{K_X}(P)$.

This is a three-way protocol that lets only Alice know the message.

  1. $A\rightarrow B: N_1||E_{K_1}(m)$
  2. $B\rightarrow A: E_A(K_2)||auth_B=S_B(E_A(K_2))||N_1||N_2||E_{K_2}(E_{K_1}(m))$
  3. $A\rightarrow C: E_B(K_1)||auth_A=S_A(E_B(K_1))||E_A(K_2)||auth_B||N_1||N_2||E_{K_2}(E_{K_1}(m))$

Now the protocol actions:

  1. Alice retrieves the message and encrypts using a random key $K_1$ which is stored (short-term). She finishes by sending the above message.
  2. Bob generates a random key $K_2$ himself, which he uses to encrypt the provided message (by Alice). He then encrypts the symmetric key using Alice's public key and signs the resulting ciphertext. After this he sends the signature, the encrypted key and the resulting ciphertext.
  3. Alice decrypts the provided ciphertext using the asymmetrically encrypted key and decrypts the resulting ciphertext using her symmetric key. She then checks that the $m$ value is correct. If this is the case she verifies $auth_B$ and if it's valid she calculates $E_B(K_1)$ and the signature $auth_A$. Alice deletes $K_1$ and $K_2$
  4. Upon receivement Carol checks $auth_A$ and $auth_B$ and assumes correct treatment by trusting that Alice has validated Bob's encryption.

Note that $auth_A$ is neccessary to prove that Alice trusts the key.

Now only Alice and Bob together can decrypt the message $m$ as only Alice can decrypt $K_2$ and only Bob can decrypt $K_1$. Note further that AES-GCM uses CTR-mode internally resulting in the fact that $E_{K_2}(E_{K_1}(m))$ isn't vulnerable to meet-in-the-middle as this is basically $StreamPad_1 \oplus StreamPad_2 \oplus m$ and hence it's needed to have both keys to decrypt.

I hope this solves your problem.

Improve this answer
$\endgroup$
  • $\begingroup$ I'll happily promote any other answer using a well-analyzed solution to this problem. $\endgroup$ – SEJPM♦ May 23 '15 at 19:00
  • $\begingroup$ Alice can cheat in this case, and simple create a double encrypted message of anything of her choice even after the 2. step, under $K_1$ and $K_2$, which she both knows. Bob only signed the key $K_2$ (well, encrypted with Alice public key), not the message itself. $\endgroup$ – tylo May 26 '15 at 12:17
  • $\begingroup$ Thank you for your clearly written out protocol suggestion. If we would use your protocol, at the end Alice will always know Bobs symmetric key. Therefore following protocol would have the same end result: Alice just creates two random symmetric keys (K1 and K2). She encrypts m first with K1 and the result of this encryption with K2. She then sends the double encrypted result K2(K1(m)) to Caroline. Then she sends K2 to Bob. (All this with authenticated massages, of course) Now Alice knows both symmetric keys and Bob knows only his symmetric key. The same holds for your protocol. $\endgroup$ – user74088 May 26 '15 at 14:37

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.