Encryption and Deniability

Question

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

Bob receives P, M':

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!

Answer 1

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?