What is best to use (for message integrity) between…
- AES(Data) + HMAC(Data)
- AES(Data + HMAC(Data))
- AES(Data + Hash(Data))
…and why?
What is best to use (for message integrity) between…
…and why?
"Encrypted hash" totally fails if the encryption uses a malleable mode like CTR. CTR runs AES in a stream-cipher-like mode where the data to encrypt is simply XORed with a key-dependent stream, so the attacker can flip bits with extreme precision; so if the attacker guesses the contents, he can modify them and fix the hash easily.
More generally, if you want a MAC then use a MAC. The "encrypted hash" is just a homemade attempt at a MAC algorithm, and we know that homemade algorithms are rarely strong, and even when they are we cannot make sure that they really are strong.
As for how to combine encryption and a MAC, this is a well-known questions for which a lot of theory and practice has been accumulated; see this question. To sum it up: you want to compute the MAC over the encrypted data, because it avoids any issue with the MAC algorithm leaking information on the processed data, and it protects the decryption implementation from malformed data.
Now, HMAC seems to be reasonably well-behaved and not to leak information about the data on which it is applied. Your setups 1 and 2 are what is used by, respectively, SSH and SSL/TLS. In neither case did it prove fatal; however, the lack of protection on the encrypted format allowed various padding oracle attacks to experience some success on implementations which were not sufficiently careful when decrypting malformed input data.
2, because the only issue is that there might be a feasible way to have a non-negligible
probability of producing a new AES ciphertext that decrypts to already-encrypted data.
(Of course, as pointed to by hunter, AES(data) + HMAC(AES(data)) is even better.)