Is Encrypt(m||k2, k1) secure authenticated encryption? I don't fully understand the need for MAC algorithms to authenticate encrypted messages. As I understand, the standard is to send something like
$\mathrm{E}(m,k) \| \mathrm{MAC}(m,k)$ where $E$ is an error-propagating block cipher, $k$ is an encryption key.

Would it not be easier simply to send
$\mathrm{E}(m\|s,k)$ where $s$ is a salt shared across the system? After decryption, the receiving user can simply check that the last $\mathrm{len}(s)$ bytes of the message match $s$ to check its authenticity.
Would it not be easier simply to send $E(m||s,k)$ where s is a salt shared across the system?


Yes, that would be simpler; however, that would not (in general) be secure.

The assumption you are making is that if someone modifies the ciphertext in any way, then the last few bits of the resulting plaintext must also be modified.  This is often not the case:


If we are using CTR mode, then someone modifying byte $i$ of the ciphertext will cause byte $i$ of the plaintext to be modified, without any other changes.  So, the attacker can avoid this protection by simply limiting his changes to the first part ($len(m)$) of the ciphertext
If we are using CBC mode, then someone modifying block $i$ of the ciphertext will cause blocks $i$ and $i+1$ of the plaintext to be modified; assuming that attacker does not modify that last two blocks of the ciphertext, his modifications will be undetected.