Is this a collision attack or a 2nd-preimage attack?

Question

This question revolves around Bitcoin Optech newsletter #51 (1) and an email thread from the bitcoin-dev mailing list (2). I asked the same question in a reply-email of the newsletter and the response was so enlightening that I thought I'd share my question and quote David Harding's reply email in an answer (I got his permission to do so).

In the newsletter text, the author describes what is supposedly a collision attack on RIPEMD160(SHA256):

However, when multisig addresses are being used, the attacker may be one of the parties involved in generation of the address and so may be able to manipulate what address is finally chosen. For example, Bob sends his pubkey to Mallory expecting that Mallory will send her pubkey back. Then he expects they’ll each put the pubkeys into a multisig script template, hash it into an address, and someone will deposit money into that address.

Mallory instead takes the script template and Bob’s pubkey, inserts one of her pubkeys without telling Bob about it, and hashes it into an address. This allows her to see the address Bob will accept before Mallory has committed to using that pubkey. Mallory can then compare this address to a database of addresses generated from scripts that pay only her. If there’s a match (collision) between two of the addresses, she sends the pubkey back to Bob, waits for money to be deposited into the address, and then uses the script from her database to steal the money. If there’s not a match, Mallory can try again with a different pubkey over and over until she succeeds (if we assume she has unlimited time and resources).

Although this seems like the same brute force attack described earlier with a 1-in-2^160 chance of success per attempt, we have to consider the size of Mallory’s database. If we imagine the database has 100 addresses, then each different pubkey she tries has a 100-in-2^160 chance of success because it succeeds if it matches any one of the addresses in Mallory’s database.

This type of attack is called a collision attack.

My question is: Isn't the described attack actually a second-preimage attack, and not a collision attack?

The attack described is based on a database of preimages and hashes, so I'd call the attack a second-preimage attack (though possibly a highly concurrent one). I wouldn't call it a collision attack because a collision attack is the process of finding two different preimages with the same hash value, no matter the hash value. In your attack the attacker is looking for a set of specific hash values. Your example with a database of 100 addresses makes it pretty clear that we're dealing with a second-preimage attack. It's even more clear if the database only contains 1 entry. The line between a collision attack and a second-preimage attack becomes a bit blurry when the database grows, but I still think it's wrong to call it a collision attack.

The attack described by Pieter Wuille in the email linked to (3) from the newsletter is a pure collision attack where the attacker doesn't have a pre-created database of preimages and hashes. Instead the attacker calculates a collision after the victim's pubkey is received, and doesn't care at all what the hash value is. See for example Ethan Heilman's algorithm (4), which I haven't fully understood yet, but it's an algorithm, that doesn't use a database, to find collisions with the order of ~2^80 work. Anthony Towns later (5) fleshes out an explicit algorithm for finding a collision with a chosen prefix and suffix with about the same complexity.

An important difference between the attack described in the newsletter and Wuille's is that you need a huge database (~2^80 entries) to reach complexity ~2^80 while Wuille doesn't need a database to reach about the same complexity. You kind of emulate a collision attack using a huge number of simultaneous second-preimage attacks. So is the newsletter really describing a collision attack?

---

(1) https://bitcoinops.org/en/newsletters/2019/06/19/

(2) https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012198.html

(3) https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012205.html

(4) https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012202.html

(5) https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012218.html

Answer 1

(This answer is a selection of quotes from an email I got from David Harding where he replied to my email reply to the newsletter. In the answer below, the quoted text is from my email question and the non-quoted text is from David Harding's reply)

I think it is indeed a collision attack.

The attack you describe is based on a database of preimages and hashes, so I'd call your attack a second-preimage attack (though possibly a highly concurrent one).

That's not how I understand a second-preimage attack (SPA). The goal of an SPA is to find an alternative message that matches one particular hash digest. This is the case for the attack described in the beginning of that section of the newsletter where you create a single-sig address. For someone to steal that money, they'd have to find an alternative pubkey that hashed to that one particular address.

I wouldn't call it a collision attack because a collision attack is the process of finding two different preimages with the same hash value, no matter the hash value.

Ah, but that's exactly what's happening in the attack described later in that section of the newsletter. Mallory doesn't care what the ultimate hash digest is as long as she can find two different messages that hash to that digest.

In your attack the attacker are looking for a set of specific hash values. Your example with a database of 100 addresses makes it pretty clear that we're dealing with a second-preimage attack. It's even more clear if the database only contains 1 entry.

A less-technical way to think about the difference between the collision attack and the SPA is how many degrees of freedom the attacker has. With an SPA, the attacker has one degree of freedom---their message. With a collision attack, the attacker has two degrees of freedom---both messages.

Whether Mallory uses a database size of 1, 100, or something else doesn't matter for the attack classification---it's a collision attack if she's involved in creating the ultimate digest, it's an SPA if she has to match a value someone else chose.

The attack described by Pieter Wuille in the email you linked to (2) is a pure collision attack where the attacker doesn't have a pre-created database of preimages and hashes.

Sorry, I didn't mean to imply in the newsletter that the attacker needed a database before they received the victim's pubkey. Precomputing can just be more efficient that way.

I believe the attack I describe is identical to what Wuille described. I just go into more detail. (Though Wuille was probably aware of memory-efficient collision attacks at the time he wrote his email. I certainly was aware of them when I wrote the newsletter.)

See for example Ethan Heilman's algorithm (3), which I haven't fully understood yet, but it's an algorithm, that doesn't use a database, to find collisions with the order of ~2^80 work. Anthony Towns later (4) fleshes out an explicit algorithm for finding a collision with a chosen prefix and suffix with about the same complexity.

Heilman's algorithm finds a cycle by using the digest from the previous hash function as the input to the next hash function. So you could end up with:

H(seed) -> 0123
H(0123) -> 4567
H(4567) -> 89ab
H(89ab) -> cdef
H(cdef) -> 0123
H(0123) -> 4567
...forever...

Heilman's algorithm breaks the loop after 2^80 tries assuming that it found a cycle. If it did, then the final digest in the loop was a member of that cycle because, once you enter a cycle, you never leave it.

The next part of Heilman's algorithm gives you the length of the cycle, allowing you to compute the value before the beginning of the cycle ("seed" in my example) and the value where the cycle loops back on itself ("cdef" in my example).

Heilman's attack is generic against any hash function, but it can't be used directly for stealing bitcoins because a random hash digest is not likely to be a valid script. Towns's attack fills in the missing details for how to apply it to stealing bitcoins.

The noteworthy part is that both attacks do query a large number of previously-generated hashes looking for a match; they just do it in a weird way (hash cycles) rather than looking up values in an in-memory database. If you think of this in abstract terms, I think it's the same thing.

An important difference between your attack and Wuille's is that you need a huge database to reach complexity ~2^80 while Wuille doesn't need a database to reach about the same complexity. You kind of emulate a collision attack using a huge number of simultaneous second-preimage attacks.

Right, as I mentioned in the newsletter, there are different algorithms with different CPU/memory tradeoffs. With a database, you reach 50% chance of success with 2^79 entries in your DB and 2^79 different pubkey trials, so 80 bits work (but a HUGE DB). Heilman's algorithm claims 2^81.5, but I'm not sure he's actually guaranteed to get a cycle in 2^80 work. Towns's claims 2^84 and seems to be more robust against problems finding a cycle.