Score:5

Does hashing an ECB encryption with a strong hash function produce a secure MAC?

ng flag

Does applying a strong hash function like SHA-256 to the ECB-encryption of a message (using some secret key $K$) produce a secure mac? For example, given a message $m$, would a simple mac construction $H(E_K(m))$ be considered a secure mac if we used a strong hash $H$ like SHA-256?

Compared to standard HMAC, this construction seems simpler and might even execute a little faster too. Also, it doesn't seem like this mac scheme is vulnerable to length extension attacks either since without knowledge of $K$, it doesn't seem like the attacker can "extend" the input to the hash function $H$ since the output of $E_K(m)$ never gets "exposed" to the attacker but only consumed as just some intermediate computation step inside of $H(E_K(m))$.

Of course, the standard $\text{HMAC}(K,m)$ construction is likely more secure against the usage of "weak hash functions", so I'm purposefully requiring $H$ in my construction to be a "strong" hash function (e.g., SHA-256) that should be collision-resistant and (of course) preimage-resistant as well.

Likewise, this key $K$ would only be used for generating mac's only, and not "shared" for other encryption purposes elsewhere. This is because if some "other part of the application" reuses $K$ for general encryption elsewhere, an attacker might take advantage of that to determine $c=E_K(p)$ for some known or chosen (or even "derived") plaintext $p$, and thus trivially forge some message $m = p$ along with its valid mac $H(c)$.

**Edit: this is essentially the reverse of this scheme...

Maarten Bodewes avatar
in flag
Note that HMAC is still a single pass of the underlying H over the data - even if the ECB + hash scheme works for larger amounts of data (and I wouldn't be sure about that either because of key reuse), it would be a two pass scheme, rather than a single pass scheme.
Score:8
ng flag

No, the proposed construction is not secure, unless the block size $b$ of the block cipher is unusually large, or much wider than the MAC. Assuming $p$ known distinct message/MAC pairs $(m_i,h_i)$ with $b$-bit message $m_i$ and $h_i$ at least $b$-bit, there's a simple attack of expected cost dominated by $2^b/p$ hashes and searches among the $h_i$.

The attack simply hashes arbitrary distinct $b$-bit values $c$ until $H(c)$ is one of the $h_i$. With good probability, the encryption of the corresponding $m_i$ is $c$. This allows to trivially compute the MAC for $m_i\mathbin\|m_i$ as $H(c\mathbin\|c)$, which counts as forgery.

The attack is quite feasible when the block cipher is $64$-bit, e.g. 3-keys 3DES or IDEA. With AES-256 and $p=2^{40}$, it costs a borderline plausible $2^{88}$ hashes and searches among $p$ values.

Note: the construction as stated in the question works only for messages of size a multiple of $b$. Common block encryption padding (like appending a one bit then $0$ to $b-1$ zero bits as necessary to reach the end of a block) can fix this, but the attack is easily adapted.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.