Does encrypting a hash of the message yield a secure MAC? Is $mac = enc(hash(x))$ a secure MAC for hash = SHA256 and enc AES in CBC mode or ECB mode. Normally AES-CBC is malleable. But in this case I use a hash function for the one-way property. 

For example, an attacker can change the iv vector: 

In CBC c[0] = enc(m[0] ^ iv) an attacker chooses m'[0] and computes iv' by m[0] ^ iv = m'[0] ^ iv'. So, in this case I find 2 digests with the same MAC: hash(x) = m[0]||m[1] and hash(x') = m'[0]||m[1]. But I have found 2 digests, I can't find x' than hash(x') = m'[0]||m[1]. 

Is my MAC a secure MAC?
Yes, your MAC is secure.  It's probably not quite as secure as you're expecting it to be, and it's not a construction I would recommend to anyone, but it should be secure.



Let's start with a simpler variant: $F_K(M) = E_K(H(M))$ where $H(\cdot)$ is a 128-bit collision-resistant hash (say, the first 128 bits of SHA1) and where $E_K(\cdot)$ is a 128-bit block cipher in ECB mode.

This is secure, under the assumption that $H$ is collision-resistant and $E$ is a secure block cipher, as can be shown using standard methods.  Since $E$ is a secure block cipher, it is a secure PRP, which implies that it is a secure PRF (by the PRP/PRF switching lemma).  Now it is known that applying a PRF to the hash of a message yields a secure MAC.

However, this still isn't a very good construction to use in practice.  It offers weaker security than, say, SHA1-HMAC.  Indeed, the authors of SHA1-HMAC explicitly considered something like this and rejected it; instead, they decided to design something new that would be better.  Read the SHA1-HMAC research paper for details (it is very readable and a classic), but concisely, one problem with your scheme is that it is susceptible to offline attacks.  Someone can try to find a collision in the hash function using an offline attack, and if they succeed, they immediately have broken the MAC.  SHA1-HMAC does not have this limitation.



Now I know that's not quite what you proposed, but it's still instructive.  What you proposed is a more complicated version of that scheme, but the complications don't really make it much better; they just it make it harder to analyze its security.

For instance, let's look at the scheme where encrypt the SHA256 hash using AES in ECB mode.  Is this secure?  Yes, it's secure, but less secure than you might expect.  If an attacker has observed the MAC on $m$ known messages, then the attacker knows a set of $2m$ known plaintext/ciphertext pairs for AES; let $\mathcal{P}$ denote the set of known plaintexts for which the corresponding ciphertext is known to the attacker.  Now suppose the attacker picks a new message $M$ (different from any of the $m$ known messages) and checks if he knows enough to predict its MAC.  Let $X,Y$ denote the left and right half of SHA256($M$), respectively.  If $X \in \mathcal{P}$ and $Y \in \mathcal{P}$, then the attacker can predict the MAC on the message $M$ with certainty, which is a break of the scheme.  What's the probability that this happens?  The probability is

$$\Pr[X \in \mathcal{P} \wedge Y \in \mathcal{P}] = \Pr[X \in \mathcal{P}] \times \Pr[Y \in \mathcal{P}] = |\mathcal{P}|^2/2^{256} = 4m^2/2^{256}.$$

So, if the attacker picks a message $M$ at random, he has a $m^2/2^{254}$ chance of being able to guess its MAC.  If the attacker picks $2^{90}$ messages $M$ at random, there's roughly a $m^2/2^{154}$ chance that one of their MAC's can be predicted, which breaks the scheme.  The attacker can do all of those calculations offline.  So, if we consider an attacker who observes the MACs on $m$ known messages and who does $2^{90}$ offline calculations, that attacker can break your scheme with probability $m^2/2^{154}$.  If $m=2^{77}$, this is a break with probability close to 1.

This attack is not a serious problem in practice.  However, it demonstrates that the security level is less than one might expect from a 256-bit MAC.  For this reason alone, I don't recommend your scheme.  Instead, something like AES-CMAC or SHA256-HMAC is a better choice.

The good news is that I would expect that one can prove that this is the best an attacker can do (modelling SHA256 as a random oracle, and assuming the block cipher is secure).  I haven't tried to write out and verify all the details, so take this with a grain of salt, but I fully expect that the proof should work out.

I haven't tried to think about what happens if you encrypt the SHA256 hash using AES in CBC mode.  That seems a bit sketchy; I'm not sure why we'd introduce an extra IV and lengthen the MAC for no apparent reason.  I don't think the construction is of any practical interest, given that better schemes exist, and that the better schemes are well-vetted and plenty good enough in practice.