# Encryption and Deniability

I have the following problem: Alice wants to send Bob a message such that Bob knows it is from Alice but at the same time he cannot prove that Alice send him this message.

The solution I came up with, using RSA, is:

1. Alice picks a random key K, and encrypts the message M using this key K. M'= aes(K, M)
2. Alice hashes K and Bob's public key to get H. H = sha(K + Bob's Public Key)
3. Alice signes H using her private key. S = rsa_sign(Alice's private key, H)
4. Alice encrypts K and S using Bob's public key. P = rsa_encprypt(Bob's public key, K + S)
5. Alice sends P, M' to Bob

1. Uses his private key to get K, S.
2. Uses Alice's public key to verify S
3. Uses K to decrypt M'.

Do you see any holes in this?

Thanks!

• Just to be sure, You don't care that you can prove Alice had K in her position at some point? If K is random and not reused, in most places that is enough "evidence" that Alice did send the message. Jan 29, 2014 at 0:22
• No, I don't care if Bob can prove that Alice send him a message, as long as he cannot prove the contents of the message. Thanks for the link. It looks like what I am trying to do.
– user38126
Jan 29, 2014 at 0:40
• What's the use case here? The random key doesn't seem to add anything useful.
– Jack
Jan 29, 2014 at 1:06
• The random key is used to encrypt the original message M. The use case is that Alice wants to send M to Bob in such a way so that Bob is sure that it is from Alice, but without at the same time being able to prove that Alice send M.
– user38126
Jan 29, 2014 at 1:11
• Given the step P = ras_encrypt(Bob's public key, K + S), there isn't really a way for Alice to deny that she knew K, and therefore knew the content of M', and therefore she can't plausibly deny that she sent the message M to Bob. Some other person who does know K could create H, and Alice could have been duped into creating S from H. However, the step that generates P requires Alice to know K, so she can't plausibly deny being able to read M', which for all practical purposes means she knows what was in M and therefore sent M to Bob (and he has proof that she did). Jan 29, 2014 at 2:12

Given the step `P = ras_encrypt(Bob's public key, K + S)`, there isn't really a way for Alice to deny that she knew K, and therefore knew (or could have known) the content of M, and therefore she can't plausibly deny that she sent the message M to Bob. Some other person who does know K could create H, and Alice could have been duped into creating S from H. However, the step that generates P requires Alice to know K, so she can't plausibly deny being able to read M', which for all practical purposes means she knows what was in M and therefore sent M to Bob (and he has proof that she did so).

However, we can consider a variation on the proposed protocol which would mean that Bob knows Alice forwarded the message, but does not prove that Alice knew the content of the message that she forwarded. The alternative solution, using any appropriate public key cryptosystem (PKCS), is:

1. Alice picks a random key K, and encrypts the message M using this key K.
`M' = AES(K, M)`
2. Alice hashes K and Bob's public key.
`H = SHA(K + Bob's Public Key)`
3. Alice encrypts K (plus arbitrary extra material if the key is deemed too short) using Bob's public key:
`K' = PKCS(Bob's public key, K)`
4. Alice encrypts H using her private key.
`S = PKCS(Alice's private key, H)`
5. Alice encrypts K' and S using Bob's public key.
`P = PKCS(Bob's public key, K' + S)`
6. Alice sends P, M' to Bob.

When Bob receives P, M', he:

1. Uses his private key to decrypt P and get K', S.
2. Uses Alice's public key to decrypt S and get H.
3. Uses his private key to decrypt K' and get K.
4. Uses his public key and K to validate H.
5. Uses K to decrypt M' and get M.

Alice can now deny creating the message because she could have been duped by Mallory (the malicious) into taking M', H, and K' and producing S and then P, and sending P and M' to Bob, without actually knowing K or what's in M. It would require some gullibility to have been deceived like that, but deniability may require the appearance of gullibility.

If Eve (the eavesdropper) intercepts P and M', she can do nothing. She cannot decrypt P because she does not have Bob's private key. Therefore, she cannot retrieve K' or S, and therefore cannot get the original K or M.

Clearly SHA and AES can be any agreed upon secure hash algorithm and symmetric (private) key algorithm.

Or have I goofed somewhere?

• Thanks! Looks good. I hope :). Question: why do we first encrypt K to K' in step 3 and then encrypt K' again, with S, in step 5? Can't we just encrypt K + S in step 5 and skip step 3?
– user38126
Jan 29, 2014 at 19:42
• Because Alice wants to be able to deny knowing K. If she did as you suggested, she would have to know K, so she could not deny knowing what is in the message. As shown, she can claim that Mallory sent her K', H and M' (but she can claim that she does not know K or M). If done as you suggest, she could not plausibly claim not to know K and hence M. Jan 29, 2014 at 20:47