Why doesn't this dummy mutual authentication protocol provide mutual authentication?

Question

I am a student taking a cryptography course so forgive me if this comes off as a silly question.
This is an assignment question:

$Alice \rightarrow R \rightarrow Bob$
$Alice \leftarrow [R]B \leftarrow Bob$
$Alice \rightarrow [R+1]A \rightarrow Bob$

Why doesn't this protocol provide mutual authentication?

Here's a plausible scenario:

Alice sends $R$. Trudy intercepts it and sends it to Bob impersonating Alice. Bob sends back $R$ signed by him to Trudy. Trudy now impersonates Bob and sends $R$ with Bob's signature to Alice impersonating Bob. Alice sends $[R+1]$ signed by Alice which Trudy can now use to impersonate as Alice to Bob.

If that is a valid attack. Wouldn't this work with every protocol? After all we're merely just relaying message back and forth among the two parties.

Answer 1

I think you've got all the right ideas but I think you're lacking an understanding about how Public Key Cryptography works.

Trudy can only impersonate Alice in this scenario with a replay attack (or if some kind of authentication credentials are returned...like an http cookie, Trudy could steal that too). Since she does not have Alice's private key, she can only successfully respond to Bob's challenge by waiting for Alice to respond and stealing response. In this simple scenario, Bob will be unable to tell if Trudy sent the message or if Alice did.

In reality, Bob and Alice have everything needed to create a secure protocol. Because Bob and Alice have the capability to verify the message was sent (using eachother's public keys), they can also encrypt messages only the other can decrypt. Bob can sign his challenge he has generated, encrypt this using Alice's public key, and then send it all to Alice.

Alice then decrypts, verifies Bob sent it using his public key, and can generate the response, sign it, and encrypt the same way Bob did.

Answer 2

Assuming that Alice and Bob have exchanged keys before, when Alice receives the message [R]B, she knows that B has sent that message at some point. Therefore she knows (at most) that B has participated in the protocol. She doesn't know that Bob has ever sent the message [R]B to her, maybe he sent it to Charlie and Charlie or Mallory resent it. There is no way in which this protocol can be interpreted as authenticating Bob to Alice: all it proves is that Bob has once participated in the protocol as initiator.

Bob does see a response to his message from Alice — assuming that R is a proper nonce, he knows that [R+1]A has to be in response to his message. However, Alice may not have realized that R originally came from Bob. Eve may have seen the message [R]B sent to someone else, and sent Alice the message [R]E; Alice would have replied [R]B all the same, which Eve may then have forwarded to B. Thus all the protocol proves to Bob is that Alice participated in the protocol as respondent at a time after Bob send [R]B out.