Which is more secure? $\operatorname{AES-ECB}(key,\operatorname{SHA1}(data+key))$ vs $\operatorname{HMAC-SHA1}(key, data)$

Question

$\operatorname{AES-ECB}(key,\operatorname{SHA1}(data+key))$ vs $\operatorname{HMAC-SHA1}(key, data)$

1. Which is more secure?
2. Which is faster?

There is a similar comparison here; HMAC-SHA1(key, data) vs sha-1(data+key)

Answer 1

Let's look at the construction more abstractly. Let $F : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$ be a pseudorandom permutation and let $H : \{0,1\}^* \to \{0,1\}^n$ be a collision resistant hash function.

If we look at the simpler construction $$\operatorname{MAC}(k,x) := F_k(H(m))$$ we can actually prove that this is a secure MAC (at least in theory).

The proof can be done via game-hopping in two steps. For that we consider two different Experiments. The first one $E_1$ is the original existential unforgeability experiment for $\operatorname{MAC}$. The second one $E_2$ is the unforgeability experiment for $\operatorname{MAC}$ where we replace $F_k$ with a (lazily sampled) truly random permutation.

We then first show that the success probability of a forger in $E_1$ and $E_2$ can only differ by a negligible amount by reducing to the security of the PRP. This reduction is pretty straightforward. Whenever the forger $\mathcal{A}$ queries a message $m$ to the oracle, the reduction $\mathcal{R}$ hashes the message and sends the hash-value to their own oracle and relays the reply $t$ to $\mathcal{A}$. Eventually $\mathcal{A}$ outputs a supposed forgery $m',t'$. The reduction the queries $H(m')$ and outputs $1$ if the reply is $t'$ and $0$ otherwise.

The advantage of $\mathcal{R}$ is identical to the difference in success probability of $\mathcal{A}$ in $E_1$ and $E_2$. Therefore that difference must be negligible.

In $E_2$ we can now bound the success probability of $\mathcal{A}$ by reducing to the collision resistance of $H$. The reduction in this case lazily samples a truly random permutation instead of using $F$. Therefore the value of any tag for a hash-value that has not been queried is information theoretically hidden among $2^n-q$ values, where $q$ is the number of queries made by $\mathcal{A}$. Thus any successful forgery must result in a collision in $H$ except with probability $2^{-n+\log q}$ which means that $\mathcal{A}'$s success probability is negligible.

The problem is, that you chose to add the key $k$ to the message when hashing it. Which means the above proof breaks in the first step, because you cannot compute the hash value. So not only did adding the key not help, it broke the security guarantee.

Finally, you chose to instantiate $F$ with AES and $H$ with SHA-1. That causes several problems in practice and theory. First SHA-1 outputs 160 bits, which do not fit into AES's 128-bit input size. You may be tempted to just truncate the hash value, however it should be noted, that collision resistance does not imply collision resistance of the truncated version. Moreover, SHA-1 is not collision resistant. And finally, even if it were, with a tag-length of 128 bits, this construction can achieve at most $64$ bits of security in theory and a bit worse than that for AES, which is unacceptable in most concrete settings.