Is this simple Proof of Work algorithm based on SHA256 susceptible to length extension attack?

user491880

5/16/23, 11:46 PM

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?

0 + 0

sha-256

proof-of-work

cryptocurrency

Score:1

Crypto

kelalaka

5/17/23, 12:14 AM

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.
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.}

0 + 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Is this simple Proof of Work algorithm based on SHA256 susceptible to length extension attack?

TH: อัลกอริทึม Proof of Work อย่างง่ายที่ใช้ SHA256 ไวต่อการโจมตีแบบขยายความยาวหรือไม่

RO: Este acest algoritm simplu Proof of Work bazat pe SHA256 susceptibil la atacul de extensie de lungime?

RU: Подвержен ли этот простой алгоритм Proof of Work, основанный на SHA256, атаке с увеличением длины?

VI: Đây có phải là thuật toán Proof of Work đơn giản dựa trên SHA256 dễ bị tấn công kéo dài không?

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.