Hash Functions

Overview

Bitcoin relies on two different hash functions, namely SHA256 and RIPEMD160. These functions have four different applications in Bitcoin:

1. Addresses are mainly derived from a public key $Q$ by

   $$\bar{Q}={\text{RIPEMD160(SHA256(Q)}).}$$

2. Solving the PoW requires finding a nonce $n$, such that

   $${ \text{SHA256(SHA256(headerdata}||n)) }<T$$

   where $T$ is the pre-defined target.

3. Each block header is uniquely defined by its hash $\text{SHA256(SHA256} (H) )$.

4. Transactions are stored in a Merkle tree by applying double SHA256 in each step.

We outline the consequences of a successful attack against a hash function of these applications. For simplification, we consider $\text{RIPEMD160(SHA256}(Q))$ as being one single primitive, which we call the address hash.

Attacks against the address hash in P2PKH transactions

Attacks against the address hash in P2PKH transactions include the following three possibilities:

• Preimage attack: The preimage attack aims at revealing the public key $Q$ from an address hash $\bar{Q}$. As the public key gets revealed during a transaction, there’s no preimage attack against already spent transactions as the public key is already known. A preimage attack against the address hash can thus only be applied to reveal the public key for a UTXO. However, this attack isn’t enough to unlock the UTXO since the unlocking script requires both a public key and a valid signature, as shown in this section. Since the public key $Q$ gives no information about the private key $d$ that’s needed for the signature, a preimage attack against the hash function carries no risk for any UTXO.

• Second preimage attack: The second preimage attack aims at finding a different public key $R$ that hashes to the same address as a given $Q$ does, i.e.,

  $$\bar{Q}=\text{RIPEMD160(SHA256(Q))}=\text{RIPEMD160(SHA256(R))}.$$

  Even if an attacker finds a valid second preimage for $Q$, they can’t steal the coins because they don’t know the corresponding private key $d_{R}$. So, they can’t sign a transaction that would spend the corresponding UTXO.

• Collision attack: The collision attack aims at finding two different public keys $Q_{1} \neq Q_{2}$ that hash to the same address, i.e.,

  $$\text { RIPEMD160(SHA256 } \left.\left(Q_{1}\right)\right)=\text{RIPEMD160}\left(\text{SHA} 256\left(Q_{2}\right)\right).$$

  However, a successful collision attack gives no advantage to the adversary because they control both $Q_{1}$ and $Q_{2}$, but have no knowledge about the corresponding private keys.

In summary, we can say that an attack against the address hash gives no advantage for an attacker, as long as the signature scheme isn’t affected by another attack.

Attacks against the PoW

Attacks against the PoW include in particular the preimage attack. The preimage attack against PoW aims at finding a valid block header $H$ that fulfills

$${\mathrm{SHA} 256(\mathrm{SHA} 256(H))=t<T}$$

for a freely chosen $t$. Such an attack would break Bitcoin’s mining mechanism. However, it’s important to understand that not every preimage that satisfies the previous equation is a valid solution to the PoW. The reason is that the Bitcoin network not only checks if the hash of the header is below the target $T$ but also checks if the metadata of the header is valid as well. So, an attacker can’t simply compute a preimage of any chosen $t$ but must find a $t$ whose preimage is recognized by the network as a valid block header $H$ of 80 -bit size. Looking at the block header’s entries, one sees that the version number, the hash of the previous block, and the difficulty target as well are considered to be fixed. Thus, Giechaskiel et al. (2016,2018)(Ilias Giechaskiel, Cas Cremers, and Kasper B. Rasmussen. On bitcoin security in the presence of broken cryptographic primitives. In Ioannis Askoxylakis, Sotiris Ioannidis, Sokratis Katsikas, and Catherine Meadows, editors, Computer Security ESORICS 2016, pages 201-22, Cham, 2016. Springer International Publishing.) - (Ilias Giechaskiel, Cas Cremers, and Kasper B. Rasmussen. When the crypto in cryptocurrencies breaks: Bitcoin security under broken primitives. IEEE Security Privacy, 16(4): 46-56, July/August 2018.) have shown that there are two different possible attacks:

1. Preimage attack against a fixed Merkle root: This attack assumes a fixed Merkle root. Giechaskiel et al. (2016,2018)(Ilias Giechaskiel, Cas Cremers, and Kasper B. Rasmussen. On bitcoin security in the presence of broken cryptographic primitives. In Ioannis Askoxylakis, Sotiris Ioannidis, Sokratis Katsikas, and Catherine Meadows, editors, Computer Security ESORICS 2016, pages 201-22, Cham, 2016. Springer International Publishing.) - (Ilias Giechaskiel, Cas Cremers, and Kasper B. Rasmussen. When the crypto in cryptocurrencies breaks: Bitcoin security under broken primitives. IEEE Security Privacy, 16(4): 46-56, July/August 2018.) give the following estimation of the probability of a successful attack:

   We are looking for a block header whose $n$-bit hash is below a given $\text{target} \ T$, whose value starts with $d$ zeros. If an attacker controls $b<n$ bits of the input, there are $2^{b}$ possible input values to the hash function, which need to map to a hash value below the target, which means that they need to hash to one of the $2^{n-d}$ values in the target interval. Since these values are uniformly distributed across $2^{n}$ values, we get an expected number $E=2^{b} \cdot 2^{n-d} / 2^{n}=2^{b-d}$ of existing $b$-bit preimages.

   As there are $2^{b-d}$ preimages of size $b$-bit, which are distributed across $2^{n-d}$ values, we get the probability of $P=2^{b-d} / 2^{n-d}=2^{b-n}$ that a given hash below the target has a preimage of size $b$-bit. If we assume that an attacker is able to evaluate $2^{a}$ hash values, we get a probability of $P=2^{a} \cdot 2^{b-n}=$ $2^{a+b-n}$ of breaking the mining process. By observing the unfixed bits of the block header’s entries (the nonce and a part of the timestamp) and the current difficulty, Giechaskiel et al. (2018)Ilias Giechaskiel, Cas Cremers, and Kasper B. Rasmussen. When the crypto in cryptocurrencies breaks: Bitcoin security under broken primitives. IEEE Security Privacy, 16(4): 46-56, July/August 2018. estimate that the probability of success is about $2^{-100}$, which can be considered as negligible.

2. Preimage attack against a variable Merkle root: If the attacker can vary the Merkle root, they get an additional 32 bytes of freedom, and can thus break the mining process because of these considerations. In order to control the variable Merkle root, the attacker mines the block with only a coinbase transaction.