Deriving IV (Nonce) securely with MITM attack

I understand that a good nonce is very important with most ciphers. I am using AES-GCM, and am using a 96-bit nonce with a 256-bit AES key. I have asked a few questions on here before about how to negotiate the nonce over an insecure channel.

I am using ECDH to derive a shared secret and plan on using a X9.63 standard method to derive the keying material from such. I know that it would be possible to just append a randomly generated 96 bits to the end for the salt when negotiating the key. Then I could combine the two somehow (this is a peer to peer system) like XOR, and have a random, good nonce.

Of course this doesn't stop MITM attacks, say via ARP spoofing. The public keys themselves are certified by a central server whose public key is distributed with the application. Therefore, certification can't be tampered with because of the use of GCM. However, the nonces are not certified of course, so one could potentially MITM the peers, keeping their keys identical but replacing the IV with something predictable or static (or all zeroes or whatever) which would result in vulnerabilities to a chosen (known?) plaintext attack.

Here's a scenario of the thing I'm talking about in case it's confusing. Alice (A) and Bob (B) both generate good, random 96 bit nonce material (Am and Bm) and append them to their x.509 certificates. For illustration I'll use the small numbers Am=1234 and Bm=4321. When not MITMed, each would calculate Am⊕Bm = 5171. That will be used as the nonce. Eve decides to MITM them to defeat the IV. She makes sure that they will end up with the constant IV "6666." When A sends Am "1234" to B, Eve ARP spoofs Bm and replaces this with "2795." When B sends Bm "4321" to A, Eve replaces this with "7896." 1234⊕7896 == 4312⊕2795 == 6666.

Here are my ideas/thoughts:

Sign the nonce material with a signing key (ECDSA): At this point I have no facility for authenticating anything outside of GCM itself (i.e. I'm not using ECDSA keys or managing them). I'd like to strictly stick with Suite B algorithms. I know that I can authenticate plaintext with GCM (the "AD" part of AEAD -- Authenticated Encryption with Associated Data) but of course I have no established IV yet... so I can't authenticate the IV material with this, can I? To me it seems like I should be able to authenticate this using only a symmetrical key with GCM (which I have established already via ECDH) because it doesn't need to be encrypted anyway so there's no secret -- just plaintext and the GCM MAC -- but I can't figure out how to initialize the AEADBlockCipher without an IV in BC. Would it be stupid to "fool" the cipher by first initializing it with an all-zero IV, the correct key, then process the Nonce as "associated data" (not encrypted), finalize the buffer (to append the MAC), send this to the peer, then reinitialize the cipher with the real IV and the same key? Alternatively, I'm pretty sure that I could sign the nonce (perhaps along with the ECDH public key if I wanted) using ECDSA, but that would require distributing ECDSA public keys that are also certified by the server which adds complexity that I'd rather avoid (thus my first signing idea)

Record and disallow repeated uses of same IV/Key combo: The important thing with an IV is that it is only used once with a given key. So, if someone does the MITM attack above to replace the IV with a contrived one repeatedly, this idea would just notice and close the connection. If they replace it with a working substitute pair that derives an unused IV, the attacker would gain no advantage (right?). The private key of the ECDH pair in my design never actually hits the disk, so between program invocations I would have all new symmetric keys, so this set of key+IV pairs could easily be kept in memory so I really like this approach :-)

Use the secret material from ECDH as a "mask" to make a secr开发者_高级运维et IV: Take the established ECDH secret material (not yet passed to the X9.63 key generator (ECDHKEKGenerator in BC)). Somehow get 96 bits from it (Km), such as the first 96 of the material itself or the first 96 of the SHA-1 digest of the material. Alice and Bob generate random 96 bit nonce material (Am and Bm). A and B calculate Am⊕Km and Bm⊕Km respectively, then send their values to the other person. Once A has Bm⊕Km and B has Am⊕Km, A performs Km⊕(Bm⊕Km) to get Bm and B performs Km⊕(Am⊕Km) to get Am. Then both A and B perform Am⊕Bm and we have our IV finally. If it's tampered with, A and B will have different IVs because Eve does not know Km so she can't manipulate it precisely, right? That would cause GCM to detect tampering when the first message is exchanged so no harm done. What's wrong with this approach?

Sorry for the long question, and please do not tell me not to implement my own protocol because I'm doing this to learn about implementation details as a CS student -- not how to ignore them.

To answer this question you have to first look at the underlying GHASH, which is used for the integrity check. GHASH is a universal hash function. depends on some secret parameters. The security of GHASH depends on whether you can keep those secret parameters secret. Since GHASH is linear function it is very important that the attacker never learns the result of GHASH. I.e. knowing only a couple of GHASH outputs allows the attacker to derive the secret GHASH parameters.

GCM protects the output of GHASH by encrypting it, that is XORing it with AES(Counter0). It is very important that the Counter never repeats. Assume for example that you encrypt two messages, both using the same value for Counter0. Then the attacker learns

AES(Counter0) Xor GHASH(C1,..)

and

AES(Counter0) Xor GHASH(C2,..)

from which the attacker can derive

GHASH(C1,..) Xor GHASH(C2,..)

which gives one linear equation to the attacker. Knowing two equations allows to solve for the secret parameters. But even knowing one equtions should allow to simplify attacks against GCM.

This shows that the Galois Counter Mode must be used very very carefully. I.e. if you repeat IVs in CTR mode then you potentially leak plaintext. If you repeat IVs in GCM then you leak keys, which is of course worse.

I do not claim that this attack breaks your proposal. For me the description of your proposal is a little too short and I'm not sure I've fully understood it. But I think the description above does describe a potential pitfall when using GCM and I hope it helps you to analyze your proposal yourself.