Types of Attacks on a Hashing Function and How They Apply to Bitcoin

[butka]

This post is my attempt (from my beginner's point of view) to understand the possible types of attacks on a hashing function, especially Bitcoin's SHA256 function. It's a difficult subject and I would appreciate any help from the community.

Bitcoin uses hashing a lot, and obviously the security of the entire system is tied to the security of its Hashing function(s). It's worth noting that most of the time Bitcoin uses SHA256, and not only once but twice, like this: SHA256(SHA256(x))

There are some typical attack scenarios that one can read about in the literature and here on this forum, so I wanted to see if I can identify them and indicate why they are important:

1. Preimage attack
2. Second preimage attack
3. Collision attack
4. Birthday attack
5. Length extension attack

1. Preimage (sometimes referred to as First preimage)

This one is the easy to understand.

A hashing function H produces a hash like this:

Code:

H(x)=y

In the above formula, y is the end result (the hash), while x is the thing being hashed.

A good hashing function has to be resistant to preimage attacks. It merely means that you cannot find x (the thing being hashed) if you know y (the hash).

In other words, the hashing function should work in one (forward) direction only.

It is important to note that this is not an absolute claim. If you invest enough time and computational power (brute force), you should be able to perform any of these attacks successfully (even though the time and computational power needed might be inconceivably high at present). The main thing is that there should be resistance against all possible patterns, methods, or systems that the attacker could use to speed up the brute force process.

How Could Preimage Attack Affect Bitcoin?

Bitcoin uses the SHA256 hashing function, for example, in mining. If SHA256 weren't first preimage resistant, the attacker would be able to find the block header based on the desired hash with enough zeros at the beginning (the target) and gain huge advantage over the other participants in the process.

2. Second Preimage

The second preimage means that if you know x (such as H(x)=y) you shouldn't be able to find another x' that produces the same hash y (such as H(x')=y). In other words:

Code:

given x it's hard to find x' so that H(x)=H(x')

The point here is that your knowledge of x shouldn't be enough to find another x' that produces the same hash, making your hashing function second preimage attack resistant.

(If the hashing function isn't first preimage resistant, it is also very likely not a second preimage resistant.)

How Could Second Preimage Attack Affect Bitcoin?

This is not obvious at first sight. I found this post

https://bitcointalk.org/index.php?topic=928202.0

which I think explains why second preimage resistance is important in Bitcoin and what would happen if it was compromised

The key difference to the two scenarios is what is known to the attacker.  In the first the attacker only has the hash. A good example would be cracking a password.  In the second the attacker has the original input. A good example would be producing a "counterfeit" txn/block/merkletree/pubkey which results in the same hash as an existing one to spoof the network and steal funds.

In Bitcoin every use of SHA256 relies on second not first preimage resistance to provide security.  The input is already known so the interim hash can be computed.  The second hashing step provides no security because if the attacker finds a second input which produces the same interim hash as the target then they both will obviously produce the same final hash.  It is possible that double hashing may harden a hash against first preimage attack but that doesn't enhance the security of Bitcoin.

So Bitcoin seems to rely on good second preimage resistance, as otherwise the transactions or merkletree construction could potentially be compromised.

Also, because of this, Satoshi may have used two hashing functions (one after another), for example, to produce a bitcoin address.

Code:

RIPEMD160(SHA256(public key))

In that sense, if RIPEMD160 was broken against second preimage attack, SHA256 would still hold.

3. Collision Attack

Collision attack is similar to the second preimage attack, but more general. It says that it is not possible (or rather computationally not feasible) to find any pair of x and x' that produce the same hash.

The important to know here is that the hash is not known in advance (nor is any of the inputs x or x'). So the attacker is free to generate and collect a list of hashes searching for a collision.

If the hashing function is prone to a second preimage attack, it will be prone to collision attack, but not the other way around.

How Could Collision Attack Affect Bitcoin?

Obviously this should not really be a problem for Bitcoin and has been discussed many times before. An example would be when one generates private keys trying to find a collision with a known bitcoin address or addresses and spend the funds.

4. Birthday Attack

Birthday attack is very similar to collision attack, but the inputs are truly random. This is unlike the previous scenario where the form of the private keys is not random and have well defined properties (such as the size of the private key).

How Birthday Attack Affects Bitcoin?

This attack is not really applicable to Bitcoin.

5. Length-extension Attacks

If you know y (H(x)) but you don't know x, with attack of this kind you can calculate H(x||y). || means  "extended by some value". Which is not a problem in itself, but there seem to be some cases (not in the implementation of Bitcoin) where security is broken.

How Could Length-extension Attacks Affect Bitcoin?

Some people claim that Satoshi wanted to make sure no single detail is missing so he used double hashing in the block header SHA256(SHA256(block-header)) to prevent exactly this attack.


This post was my attempt to explain certain cryptographic terms (primarily to myself). I hope if something is wrong with some of the claims or conclusions, someone will correct me.

References:

https://en.bitcoin.it/wiki/Hashcash
https://crypto.stackexchange.com/questions/1173/what-are-preimage-resistance-and-collision-resistance-and-how-can-the-lack-ther
https://crypto.stackexchange.com/questions/779/hashing-or-encrypting-twice-to-increase-security
https://bitcoin.stackexchange.com/questions/8443/where-is-double-hashing-performed-in-bitcoin
https://bitcoin.stackexchange.com/questions/4317/why-does-bitcoin-use-two-rounds-of-sha256?rq=1