Security of S/MIME in case of CA compromise

Suppose Alice and Bob are exchanging messages using S/MIME, protected by certificates that have been issued by either the same CA or by two mutually independent CAs. There exists an adversary Mallory who wants to get the ability to compromise the confidentiality of the communication, or the integrity, or both. We may assume Mallory is subject to the following restrictions:

• Mallory does not have access to the private keys of Alice or Bob. Mallory might however have access to the private certificate signing keys of the CAs.
• Mallory has full access to the network communication between Alice and Bob.
• Mallory wants to avoid detection. Primarily, Mallory wants an attack that is completely transparent to both Alice and Bob, and in worst case, an attack that will interfere in a detectable way with the communication, but only infrequently and can be rationally explained as network failure, software failure or hardware failure.
• Normally, we might assume Mallory delegates most actions to an automated service. In particular, we might assume that even if Mallory has managed to compromise both confidentiality and integrity and in both directions, most of the time the exchanged messages will be let through without interference, and it might be hard for Mallory to alter the messages in real time, when some information (such as certificate thumbprints) is exchanged that might lead to exposure of the compromise.

Technically, Alice and Bob will normally establish a confidential channel by Alice sending a signed only message to Bob, Bob extracting the certificate of Alice, and replying with a signed-then-enveloped message to Alice. Given the first three restrictions, such an exchange might be trivially compromised in the following way:

1. Mallory creates a key pair $Pub_{FA},Priv_{FA}$ and a certificate $Cer_{FA}$ that is signed by a CA that Bob trusts and which (dishonestly) identifies Alice. Mallory creates a key pair $Pub_{FB},Priv_{FB}$ and a certificate $Cer_{FB}$ that is signed by a CA that Alice trusts and which (dishonestly) identifies Bob.
2. Alice sends a message $Sign_{Priv_A}(M_A,Cer_A)$ to Bob which is intercepted by Mallory who replaces it with $Sign_{Priv_{FA}}(M_A,Cer_{FA})$.
3. Bob sends a message $Env_{Pub_{FA}}(Sign_{Priv_B}(M_B,Cer_B))$ which is intercepted by Mallory who replaces it with $Env_{Pub_{FA}}(Sign_{Priv_{FB}}(M_B,Cer_{FB}))$.

Now, my concern is that this attack does not necessarily comply with the fourth restriction. For instance, if Alice and Bob somehow manages to, without detection, exchange certificate thumbprints over the compromised channel, the compromise will be detected immediately.

Are there any better attacks, or might we assume that the four restrictions make S/MIME relatively safe from attackers such as Mallory?

Edit: Mallory is a threat to the confidentiality and integrity of Alice and Bob. Conversely, Alice and Bob are a threat to the transparency of Mallory. Considering that Mallory gets to pick the targets Alice and Bob, but not the other way around, to what extent might Alice and Bob trust their confidentiality and integrity, based on their being such a threat to the transparency of Mallory, that Mallory might be safely assumed to not attack them?

-
Wow, those LaTeX equations (well, they're not really equations, but work with me here) have some serious rivers in them. –  orlp Sep 8 '13 at 7:06
@nightcracker: Sorry, didn't catch what you meant. Do you want me to change the formatting? –  Henrick Hellström Sep 8 '13 at 7:07
No, don't worry about it. I was talking about a river in terms of typography. –  orlp Sep 8 '13 at 7:14

No, since

compromising the communication $\:\implies\:$ compromising the PKI setup $\:\implies$
falsely claiming that a party generated a particular public key $\:\implies\:$ "if Alice … immediately."

.

Yes, we might assume that.

Note that, if the channel can carry voice, then faking a comparison can require voice impersonation.
This is the idea behind ZRTP (which admittedly is not for email).

-
I am inclined to accept this answer, since it is indeed a valid conclusion from my assumptions. But are my assumptions and my usage of the term "relatively secure" really that unproblematic? –  Henrick Hellström Sep 9 '13 at 8:54
I may be able to address that, but it will probably be over 12 hours from now. $\;$ –  Ricky Demer Sep 9 '13 at 9:20
I attempted to address that. $\;$ –  Ricky Demer Sep 9 '13 at 22:53
I take it that you are not aware of any formal security model, in which either Alice and Bob, or Mallory, by adding a few steps can get provable security against the respective adversary? –  Henrick Hellström Sep 10 '13 at 7:15
I'm not. $\:$ However, in the "short authentication string" model, multi-string setup $\hspace{1.58 in}$ is sufficient for provable security against Mallory. $\;\;\;$ –  Ricky Demer Sep 10 '13 at 7:29

Are you doubting the last paragraph in my answer to this question? :-)

Yes, any such tampering can always be detected after the fact.

The message I send to you (call it $\mathcal{M}$) depends on what I think is your public key. The message you receive (call it $\mathcal{M}'$) must decrypt with your actual private key.

Your hypothesis is that the adversary does not know your private key, thus he can only read the message if $\mathcal{M}$ and $\mathcal{M}'$ are different. Obviously we can detect that after the fact by comparing them.

Note that a similar argument applies to MITM attacks against on-line key exchange protocols like Diffie-Hellman, where the adversary cannot intercept the traffic without negotiating a different shared secret with each of us. If we each save that shared secret (or just a hash to preserve PFS), we can compare them later to detect the attack.

So, once again, compromise of CA certs is not very useful for large-scale attacks since you will eventually be caught. Just ask Iran.

-
if these kinds of attacks are effective depends much on the domain. If you have just automated services then the attack may never be noticed. If you attack the use of a service of the users or the CA itself, then it is certainly very effective as well (that CA you are talking about ceased to exist, temporarily taking out a lot of services and requiring each and every web-browser to purge the CA certificate from cache). –  Maarten Bodewes Sep 8 '13 at 20:10
@Nemo: Are Alice and Bob a threat to the transparency of Mallory, only if the attack is large scale, Alice and Bob have an out-of-band channel, and they go the extra length to somehow compare the cipher text? –  Henrick Hellström Sep 9 '13 at 6:57
@HenrickHellström : $\:$ No, for the reasons given in my answer. $\;\;\;$ –  Ricky Demer Sep 9 '13 at 8:13