Why do nonce misuse resistant schemes mac the plaintext?

Question

Choosing a proper nonce is a vital part of every symmetric-key encrypted communication, and it is mandatory that every encrypted message has a unique nonce. It can be shown that using a nonce twice with the same key has such catastrophic effects on the system. So in every protocol that uses AES-GCM or other AEAD algorithms, there are careful considerations for preventing the re-use of a nonce.

On the other hand, some AEAD recipes are proposed claiming to be resistant to this kind of nonce misuse, such as SIV-AES or AES-GCM-SIV. Let's accept this claim and be confident that misuse of nonce is not a problem anymore in these schemes. But I see a bigger problem: in order to authenticate the messages, they both mac the plaintext.

Quoting Moxie Marlinspike:

When it comes to designing secure protocols, I have a principle that goes like this: if you have to perform any cryptographic operation before verifying the MAC on a message you’ve received, it will somehow inevitably lead to doom.

There are also some other questions about the pros and cons of MAC-then-encrypt vs encrypt-then-MAC. It seems that the general consensus is something like MAC-then-encrypt is bad and encrypt-then-MAC is better. In other words (please correct me if I'm wrong), those block-cipher modes that mac the ciphertext (like GCM or EAX) are a better choice than the ones which authenticate the plaintext (like CCM or OCB).

So the question comes to this: the AES-GCM-SIV mode was seemingly proposed to overcome a possible vulnerability in the GCM mode, but by choosing the MAC-then-Encrypt option, they actually made it worse (or do they?) I doubt that this was a random choice and the designers of the SIV modes were unaware of the doom principle. But they deliberately chose it anyway. Is there any deeper reason behind this?

Answer 1

In other words (please correct me if I'm wrong), those block-cipher modes that mac the ciphertext (like GCM or EAX) are a better choice than the ones which authenticate the plaintext (like CCM or OCB).

What Moxie Marlinspike gives is a "rule of thumb" rather than a universal statement. The ciphertext may be generated by the attacker; whatever processes the ciphertext first may be working on attacker-chosen data, and if it wasn't designed for that, well, perhaps the attacker can exploit that. MACs were consciously designed to work in that scenario, and so they're always a safe choice.

That said, they're not the only safe choice. The innards of AES-SIV (and its cousins) are also designed to be safe.

And, to comment on something you said early on:

Choosing a proper nonce is a vital part of every symmetric-key encrypted communication, and it is mandatory that every encrypted message has a unique nonce.

Actually, that's not true - one can certainly define secure [1] nonceless symmetric key encryption modes. One favorite of mine is "take the plaintext, append a fixed string of zero bits and send it through a Format Preserving Encryption mode (and if you have an AAD, use that as the tweak); on decryption, check and discard the zeros at the end". We don't do this because it is inefficient, however it does show that it is possible.

[1]: Without a nonce (or changing state between sender and receiver), then duplicate plaintext will result in duplicate ciphertexts. On the other hand, we can often live with this caveat, because in many cases in the real world, we will never exactly duplicate the plaintext.