-3
$\begingroup$

$\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)

$\endgroup$
7

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ because you cannot compute the hash value. How this reduces the security? it broke the security guarantee Agree but it does not mean security is decreased, the security can also increase. at most 64 bits of security would you please explain this? would not the security increase due to encryption with aes and adding key to the sha1? $\endgroup$ Dec 15, 2018 at 12:51
  • $\begingroup$ sha1(data||key) could be less secure, aes(sha1) could be less secure. aes(sha1(data||key)); Both together increases protection against weakness of each other. $\endgroup$ Dec 15, 2018 at 13:02
  • $\begingroup$ "How this reduces the security?" Because we can no longer prove security. "the security can also increase" That is something you would need to prove and as it stand cannot. The security of an $2n$ bit tag cannot be better than $n$ bit, since we expect that you'll find a collision after about $2^n$ tries. Appending the key cannot help in the case of SHA-1. Due to the Merkle-Damgård construction two colliding prefixes $m,m'$ imply that also $m\|k$ and $m'\|k$ collide. So if at all you would need to prepend the key. But there's no reason that should help and it definitely breaks the proof. $\endgroup$
    – Maeher
    Dec 15, 2018 at 15:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.