Recovery of private key in AES-CBC from two ciphertexts with different IV, but identical plantext I have a system that encrypts messages for a given user using key K using AES-CBC in response in an external stimulus.  Each message has a randomly generated IV.  The user never decodes these messages, they are used as opaque token.

Under certain circumstances it is possible Mallory can observe the system and infer that two messages (M1, M2) have identical plaintext (P).  My concern is given two messages that are known to have identical plaintext and same key, is it possible to recover the K?

E: AES-128-CBC

IV: randomly generated IV one block size.

IV1 + E(K, P, IV1) => M1

IV2 + E(K, P, IV2) => M2

If it possible to recover K, what mitigations could I put in place?  For example would a nonce within the plaintext help, i.e.:

IVx + E(K, (Nx + P), IVx) => Mx

How would I calculate the size of nonce determine computational difficulty for recovery (within P there is a CRC32 to determine tampering)?
To give a short answer, if an attacker knows ($P$, $IV_1$, $M_1$) and ($P$, $IV_2$, $M_2$) such as :

$M_1 = E_K(P, IV_1)$ 

and

$M_2 = E_K(P, IV_2)$

where $E_K$ is the AES-CBC encryption function with the key $K$ then he doesn't learn anything about $K$ because AES is resistant to known plaintext attacks. As long as the $IV$ is randomly chosen, encrypting the same message with the same key $K$ do not reduce the security of AES-CBC.

Here is a longer answer : Why is AES resistant to known-plaintext attacks?