With known ciphertext and plaintext, find other party's Three Pass Protocol Key?

Question

If I'm the second party participating in a three pass protocol (for simplicity, let's say Shamir's Three Pass Protocol) such that:

1. Bob sends me a ciphertext
2. I encrypt it and send it back
3. He removes his encryption and sends it back to me
4. I decrypt it fully

Using the information in steps 1 (ciphertext) and 4 (plaintext), how difficult is it for me to determine the key that Bob is using?

I know that this is a somewhat esoteric use-case, but I'm curious.

Answer 1

how difficult is it for me to determine the key that Bob is using?

This is essentially the discrete log problem; Bob's key is a value $b$, and his encryption mechanism is computing the value $P^b \bmod p$. Given $P$, $P^b \bmod p$, recover $b$ is the definition of discrete log.

Actually, you get two pairs of values encrypted with Bob's key; the plaintext (encrypted in step 1, and recovered in step 4), and the exchanged ciphertext (which you see encrypted in step 2 and decrypted in step 3); however having multiple pairs doesn't actually make the discrete log problem any easier.

So, if the group is large enough to make the three pass algorithm secure (for example, large enough that someone hearing the values in steps 2 and 3 could not recover Bob's key), it's also large enough to make recovering the symmetric keys by you infeasible as well.