Most of the time, when some data must be encrypted, it must also be protected with a MAC, because encryption protects only against passive attackers. There are some nifty encryption modes which include a MAC (EAX, GCM...) but let's assume that we are doing old-style crypto, so we have a standalone encryption method (e.g. AES with CBC chaining and PKCS#5 padding) and a standalone MAC (e.g. HMAC with SHA-256). How should we assemble the encryption and the MAC?

MAC-then-Encrypt: Compute the MAC on the cleartext, append it to the data, and then encrypt the whole? (That's what TLS does)
Encrypt-and-MAC: Compute the MAC on the cleartext, encrypt the cleartext, and then append the MAC at the end of the ciphertext? (That's what SSH does)
Encrypt-then-MAC: Encrypt the cleartext, then compute the MAC on the ciphertext, and append it to the ciphertext? (In that case, we do not forget to include the initialization vector (IV) and the encryption method identifier into the MACed data.)

The first two options are often called "MAC-then-encrypt" while the third is "encrypt-then-MAC". What are the arguments for or against either?

I'm assuming you actually know all of this better than I do. Anyway, this paper neatly summarizes all these approaches, and what level of security they do or don't provide. I shall paraphrase it in English, rather than Mathematical notation, as I understand it.

Encrypt-then-MAC:

Provides integrity of Ciphertext. Assuming the MAC shared secret has not been compromised, we ought to be able to deduce whether a given ciphertext is indeed authentic or has been forged; for example, in public-key cryptography anyone can send you messages. EtM ensures you only read valid messages.
Plaintext integrity.
If the cipher scheme is malleable we need not be so concerned since the MAC will filter out this invalid ciphertext.
The MAC does not provide any information on the plaintext since, assuming the output of the cipher appears random, so does the MAC. In other words, we haven't carried any structure from the plaintext into the MAC.


MAC-then-Encrypt:

Does not provide any integrity on the ciphertext, since we have no way of knowing until we decrypt the message whether it was indeed authentic or spoofed.
Plaintext integrity.
If the cipher scheme is malleable it may be possible to alter the message to appear valid and have a valid MAC. This is a theoretical point, of course, since practically speaking the MAC secret should provide protection.
Here, the MAC cannot provide any information on the plaintext either, since it is encrypted.


Encrypt-and-MAC:

No integrity on the ciphertext again, since the MAC is taken against the plaintext. This opens the door to some chosen-ciphertext attacks on the cipher, as shown in section 4 of Breaking and provably repairing the SSH authenticated encryption scheme: A case study of the Encode-then-Encrypt-and-MAC paradigm.
The integrity of the plaintext can be verified
If the cipher scheme is malleable, the contents of the ciphertext could well be altered, but on decryption, we ought to find the plaintext is invalid. Of course, any implementation error that can be exploited in the decryption process has been by that point.
May reveal information about the plaintext in the MAC. Theoretical, of course, but a less than ideal scenario. This occurs if the plaintext messages are repeated, and the MACed data does not include a counter (it does in the SSH 2 protocol, but only as a 32-bit counter, so you should take care to re-key before it overflows).



In short, Encrypt-then-MAC is the most ideal scenario. Any modifications to the ciphertext that do not also have a valid MAC can be filtered out before decryption, protecting against any attacks on the implementation. The MAC cannot, also, be used to infer anything about the plaintext. MAC-then-Encrypt and Encrypt-and-MAC both provide different levels of security, but not the complete set provided by Encrypt-then-MAC.
