is MAC double-hashing enough to prevent length extension attacks?

Question

I know that $$mac=\operatorname{SHA1}(secret\mathbin\|message)$$

is prone to length extension attacks, but what about:

$$mac=\operatorname{SHA1}(\operatorname{SHA1}(secret\mathbin\|message))?$$

In order for someone to do a length extension attack of that, won't they either have to bruteforce the secret or bruteforce the initial $\operatorname{SHA1}$ itself? (the first of which should be unfeasible with a good secret, and the second of which should be just as expensive, or maybe even more expensive, than just bruteforcing the new hash itself?)

(edit: originally had a second question about HMAC here as well, but I think I'll take that in a separate thread, sorry about the confusion in the comments)

Answer 1

$$mac=\operatorname{SHA1}(\operatorname{SHA1}(secret\mathbin\|message))$$

is mac double-hashing enough to prevent length extension attacks?

Double hashing is defined by Ferguson and Schneier in their book Practical Cryptography in Chapter 6.3.1 to countermeasure again length extension attacks (and SHA256D used in Bitcoin). The details in their book, I don't have a copy. So, we can assume it has resistance to length extension attacks. Or, one can give a simple argument as;

To execute the length extension attack, the attacker needs to produce $$mac=\operatorname{SHA1}(\operatorname{SHA1}(secret\mathbin\|message\|pad\mathbin\|message_2\mathbin\|pad_2))$$ But they can only control the $h$ and the actual length extenstion attack can work on the outer call like this

$$mac=\operatorname{SHA1}(\operatorname{SHA1}(secret\mathbin\|message\|pad)\mathbin\|message_2\mathbin\|pad_2)$$. And even the attacker can forge the mac (i.e. the result is same) it will fail since it will not work.

In order for someone to do a length extension attack of that, won't they either have to bruteforce the secret or bruteforce the initial SHA1 itself? (the first of which should be unfeasible with a good secret, and the second of which should be just as expensive, or maybe even more expensive, than just bruteforcing the new hash itself?)

So, you want to use this as a Message Authentication Code (MAC). If the secret is at least 128 bits, then there is no way to brute-force the secret.

Bruteforce the initial here is called a preimage attack that is given a hash value $h$ find an input $x$ such that $h=H(x)$ ( or $h=H(H(x))$). The cost of the generic pre-image attack is $\mathcal{O}(2^n)$ where $n$ is the output size of the hash function $h$. For SHA-1 this makes $\mathcal{O}(2^{160})$. SHA-1 is shattered but not broken in the pre-image resistance. Therefore pre-image attack is infeasible. Actually, the pre-image attack doesn't guarantee to return the actual message used to create the hash value. One may fail there too.

There is no security proof of this construction as far as I know as a secure MAC. There is one extensive answer that on the upper level $H(k\mathbin\|H(k\mathbin\|m))$.

Instead, use the proven one; the HMAC-SHA256, or the new one with SHA3; KMAC. Since SHA3 has resistance to length extension attacks, the construction of KMAC is much easier.

SHA3 design makes the prefix construction $H(k\mathbin\|m)$ a secure PRF, and come with built-in PRF mode, the keyed KMAC. Is comes with a theorem that connects the security of the PRF to the primitive.

Also, note that the trimmed versions of SHA2 series also have resistance to length extension attacks like SHA-512/256. The trim prevents to add an extension message and the padding to continue to hashing. One has to guess/try the trimmed amount that is impossible if the trim > 120.

---

update: I've looked into the book section 6.4. It turns out that they propose two methods and a new one in the new book.

1. propose is replacing $m \to h(m)$ with $m \to h(h(m)\mathbin\|m))$. And they defined $h_{DBL} := h(h(m)\mathbin\|m))$

   They believe that if $h$ is a secure cryptographic hash function with $n$ nit output then it has a security level $n$. This is slow and you need to has the entire message twice.

2. propose is the double hashing $h(h(m))$ with only claimed claimed that it is has $min(k,n/2)$ where $k$ is the security level of $h$ and $n$ is the output size.

3. proposal is in the new book Cryptography Engineering: Design Principles and Practical Applications 1st Edition

$$h_d := h(h(0^b\mathbin\|m)$$

and claimed that it has $min(k,n/2)$ where $k$ is the security level of $h$ and $n$ is the output size.