<p>(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)</p>

<p>I think it is indeed a collision attack.</p>

<blockquote>
  <p>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). </p>
</blockquote>

<p>That's not how I understand a second-preimage attack (SPA).  The goal of
an SPA is to find an alternative message that matches <em>one</em> 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.</p>

<blockquote>
  <p>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. </p>
</blockquote>

<p>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.</p>

<blockquote>
  <p>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. </p>
</blockquote>

<p>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.</p>

<p>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.</p>

<blockquote>
  <p>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. </p>
</blockquote>

<p>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.</p>

<p>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.)</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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:</p>

<pre><code>H(seed) -&gt; 0123
H(0123) -&gt; 4567
H(4567) -&gt; 89ab
H(89ab) -&gt; cdef
H(cdef) -&gt; 0123
H(0123) -&gt; 4567
...forever...
</code></pre>

<p>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.</p>

<p>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).</p>

<p>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.</p>

<p>The noteworthy part is that both attacks <em>do</em> 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.</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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.</p>

CC BY-SA 4.0
2019-06-22T20:36:21.517Z
2019-06-22T20:36:21.517Z
Kalle Rosenbaum
<p>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).</p>
<p>In the newsletter text, the author describes what is supposedly a collision attack on RIPEMD160(SHA256):</p>
<blockquote>
<p>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.</p>
<p>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).</p>
<p>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.</p>
<p>This type of attack is called a collision attack.</p>
</blockquote>
<p>My question is: <strong>Isn't the described attack actually a second-preimage attack, and not a collision attack?</strong></p>
<p>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.</p>
<p>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.</p>
<p>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?</p>
<hr />
<p>(1) <a href="https://bitcoinops.org/en/newsletters/2019/06/19/" rel="nofollow noreferrer">https://bitcoinops.org/en/newsletters/2019/06/19/</a></p>
<p>(2) <a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012198.html" rel="nofollow noreferrer">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012198.html</a></p>
<p>(3) <a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012205.html" rel="nofollow noreferrer">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012205.html</a></p>
<p>(4) <a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012202.html" rel="nofollow noreferrer">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012202.html</a></p>
<p>(5) <a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012218.html" rel="nofollow noreferrer">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012218.html</a></p>

<security><hash><attack>
Is this a collision attack or a 2nd-preimage attack?
Kalle Rosenbaum
# Is this a collision attack or a 2nd-preimage attack?

(Asked by: username_0 on 2019-06-22)

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>

**Tags:** security, hash, attack


---

## 1 answers

### Answer by username_0 on 2019-06-22. Score: 3

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


---

