Authentication 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

In step 2 for Alice, what is the purpose of including Bob's public key in the hash? you can include a timestamp to prevent replay attacks instead.

In step 2 for Bob, there is a typo - should use Alice's public key instead of her private key.

Actually your protocol is similar to PGP, and I dont think it provides deniability because if Bob can prove that the public key belongs to Alice then the owner of the private key is most likely Alice.