Each block's contents are hashed into 32 bytes using $\operatorname{SHA-256}$ (call this string $a$). In order for the block to be accepted, there must be a 256bit nonce (call this string $b$) provided such that $\operatorname{SHA-256}(a\mathbin\|b)$ ($a$ concatenated with $b$) has $N$ or more leading zero bits, where $N$ is a difficulty parameter.

Is this simple Proof of Work algorithm based on $\operatorname{SHA-256}$ susceptible to length extension attack?


1 Answer 1

  1. Length extension attack changes the hash result therefore with high probability the difficulty parameters is no longer valid. From this $$ h = \operatorname{SHA-256}(a\mathbin\|b\mathbin\|pad1)$$ in to this*. $$ h'= \operatorname{SHA-256}(a\mathbin\|b\mathbin\| \text{pad1}\mathbin\|\text{appended_data} \mathbin\| \text{pad2})$$ We don't expect them to be equal, the equality is negligible event.

    Of course, the attacker may search for such an extension (appended_data) that has a similar difficulty parameter. However, they don't have much time since one of the clients has already found the nonce that is valid for the difficulty parameter and it is already propagating on the network.

  2. The verifiers will get the $a$ and $b$ and the hash result $h'$ ( the limited size is the key here). When they calculate the hash value they will calculate $h = \operatorname{SHA-256}(a\mathbin\|b)$ and they will see that $h \neq h'$ and the equality is a negligible event.

    Even they have the same same hash value or valid difficulty parameter, a properly implemented client will see the attack.

Therefore with proper implementations, a length extension attack is not a problem. However, don't rely on the implementations since they can be incorrect, use double SHA-256 as Bitcoin did. Alternatively, use length extension resistant hash functions like SHA-512/256, BLAKE2/3, SHA3-256.

Keep in mind that POW is designed to require lots of work, so choosing double SHA-256 was not a bad idea when Bitcoin design started.

*The paddings
$pad1$ is the padding of SHA-256 where fist 1 is appended than as small as possible 0s such that when the length encoding is added the message is multiple of 512. The length extension attacker must use this padding and then add the extended message then that will need additional padding as the $pad2$, too.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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