The protocol's description includes "Alice then encrypts $R_B$ with her private key". This has no standard meaning. Comments have clarified it is used an "RSA encryption scheme with proper padding" and I am taking as granted that encryption of $R_B$ using the private key half of $K_A$, denoted $K_A^-(R_B)$, is obtained by padding $R_B$ as in encryption, then applying the RSA private key exponentiation of $K_A$. This can be a valid form of signature (while RSA signature and encryption usually use different padding, it is possible to define a secure padding that works for both encryption and signature).
The protocol does nothing to prevent a MitM attack. In the usual definition of that, Charlie's goals are:
- impersonate as Alice to Bob, or/and to Bob as Alice;
- be able to understand all that Alice says to Bob, or/and Bob says Alice;
- be able to make Alice believe that something Charlie decides comes from Bob, or/and make Bob believe that something Charlie decides comes from Alice.
In order to achieve every single of these goals, Charlie:
- receives "I'm Alice" from Alice, relays that to Bob;
- receives "I'm Bob" from Bob, relays that to Alice;
- receives $K_A^+(R_B)$ from Bob, relays that to Alice; (I'm using the first drawing as reference, where's that before the next step)
- receives $K_B^+(R_A)$ from Alice, relays that to Bob;
- receives $K_A^-(R_B)$ from Alice, relays that to Bob, and also applies Alice's public key to that and removes any padding, thus getting $R_B$;
- receives $K_B^-(R_A)$ from Bob, relays that to Alice, and also applies Bob's public key to that and removes any padding, thus getting $R_A$.
From then on, Charlie acts with respect to Alice using the (unspecified) protocol defined for Bob, including deciphering Alice's messages, and forwarding anything Charlie decides to Alice, which has no way to tell that it comes from Charlie rather than Bob; and similarly acts with respect to Bob using the (unspecified) protocol defined for Alice.
Charlie reached all his goals. The only thing that Charlie does not know is the padding used in $K_A^+(R_B)$ and $K_B^+(R_A)$ if that's random padding, but there is no indication that some use is made of it.
Further, if for some reason Charlie wants to choose his own nonce $R_C$ as in the second drawing, rather than use $R_A$ or $R_B$ (perhaps because the protocol is extended with "After authentication, perform the action defined in the low 20 bytes of the $R$ that I sent"), Charlie can still achieve that. In order to impersonate Alice w.r.t. Bob using an $R_C$ of Charlie's choice instead of $R_A$ chosen by Alice, Charlie
- receives "I'm Alice" from Alice, relays that to Bob;
- receives "I'm Bob" from Bob, relays that to Alice;
- receives $K_A^+(R_B)$ from Bob, relays that to Alice;
- receives $K_B^+(R_A)$ from Alice, discards this, computes $K_B^+(R_C)$ and sends that to Bob;
- receives $K_A^-(R_B)$ from Alice, relays that to Bob, and also applies Alice's public key to that and removes any padding, thus getting $R_B$;
- kills the session with Alice;
- receives $K_B^-(R_A)$ from Bob, discards it.
From then on, Charlie acts with respect to Bob using the (unspecified) protocol defined for Alice, including deciphering Bob's messages, and forwarding anything Charlie decides to Bob, which has no way to tell that it comes from Charlie rather than Alice.
Kudos to mikeazo for finding a mistake, hopefully fixed.
In a comment to the present answer, the protocol is extended by adding:
Alice sends Bob a pre-master secret encrypted in Bobs public key; then
both of them use this premaster to calculate master secret.. and
communicate using that key"
That extended protocol is still vulnerable to an attack where Charlie impersonate Alice with respect to Bob. Charlie performs as in the first attack, then
- kills the session with Alice;
- pretending to be Alice, sends Bob a pre-master secret of Charlie's choice encrypted in Bobs public key;
- then Bob and Charlie use this premaster to calculate the master secret.
In fact, no addition after the protocol can protect against a MitM attack, unless it uses another public key of the participants, or another padding scheme with the existing key.
That's because Alice's behavior allows using her as a decryption oracle: by participating in the beginning of whatever extension of the protocol, Alice accepts doing steps that can be abused into the equivalent of decrypting anything with her private key, and since no other use is defined for her private key, making a fake connection attempt with Alice is as good as having Alice's private key.
The protocol can be strengthened, and the unclear "encrypt with private key" removed, as follows.
We consider an asymmetric encryption scheme with encryption $E_{Pub}(P)\mapsto C$ and decryption $D_{Priv}(C)\mapsto P$. We assume an infrastructure to verify the validity of public keys.
A participating entity $A$, when communicating with (alleged) entity $B$
- sends I'm $A$, and receives I'm $B$;
- checks that $B\ne A$;
- obtains the authentic public key $Pub_B$ of $B$ (how is not part of this protocol; a common technique is that $Pub_B$ is sent together with I'm $B$ as part of a certificate, which is verified according to a master public key);
- draws a secret random $R_A=R_{A0}||R_{A1}||R_{A2}$ where each $R_{Aj}$ is 256-bit;
- enciphers $R_A$ using $Pub_B$, yielding $C_A=E_{Pub_B}(R_A)$, sends it, and receives an alleged $C_B$;
- deciphers $C_B$ using $Priv_A$, yielding $R_B=D_{Priv_A}(C_B)$ (or an error, which aborts the protocol);
- breaks $R_B=R_{B0}||R_{B1}||R_{B2}$ into $R_{B0}$, $R_{B1}$, $R_{B2}$;
- sends $R_{B0}$ and receives an alleged $\widehat{R_{A0}}$;
- compares $R_{A0}$ and $\widehat{R_{A0}}$ (an inequality aborts the protocol);
- uses $R_{A1}\oplus R_{B2}$ as an AES-GCM key for communication from $A$ to $B$, and uses $R_{A2}\oplus R_{B1}$ as an AES-GCM key for communication from $B$ to $A$.
Messages are exchanged at steps 1, 5, 8, and 10 only. The order in which messages are sent and received in these steps is left unspecified, so that $A$ and $B$ can proceed without waiting for the other side between steps involving message exchange. Step 2. is necessary, otherwise an adversary reflecting what Alice sends will successfully make Alice accept whatever information she sends at step 10.
This protocol is better than the original. At least, a passive eavesdroper can not decode the information exchanged at step 10, as would have been possible in the original protocol. However this scheme is still NOT secure against a MitM attack assuming only that $E_{Pub}(P)\mapsto C$ perfectly preserves confidentiality. In particular, an attack is possible when $E_{Pub}$ encrypts each bit of the plaintext $P$ separately; finding this attack is left as an absolutely necessary exercise to any reader diving into protocol design.
When $E_{Pub}(P)\mapsto C$ is one of the RSA encryption scheme in PKCS#1, or when we remove steps 7. and 8. (making $R_{A0}$ and $R_{B0}$ pointless), I can not think of any mean for a MitM to intercept or alter any part of the plaintext exchanged at step 10, provided $A$ and $B$ act according to the protocol, and in particular never disclose or use any of $R_A$, $R_B$, $R_{A1}\oplus R_{B2}$, $R_{A2}\oplus R_{B1}$ other than as instructed.
