6 ms·

Attacking Merkle Trees with a second preimage attack

218 points by wepple 9y ago

Everlag 9y ago
This is a well known edge case of Merkle trees; my undergrad security course covered this as an aside and it is prominent on the wikipedia page.[0] For those not familiar with the specific implementation issue, this post should be a fun read. I don't know what's more concerning, that pymerkletools advertises itself for use with Bitcoin or that none of the contributors read the wiki page :| [0] https://en.wikipedia.org/wiki/Merkle_tree#Second_preimage_attack https://en.wikipedia.org/wiki/Merkle_tree#Second_preimage_at...
- kerkeslager 9y ago
  It's a bit strange to consider this even an edge case, and weird that one would even create a diagram (such as the one on the wikipedia page) that doesn't have a solution (such as a leaf node marker prepended). Why isn't the prepended leaf node marker included in the concept of a Merkle tree? Is there ever a situation where you'd want a Merkle tree that allowed this?
  - KMag 9y ago
    The original use case for Merkle trees were to compactly represent sets of one-time-use public keys. In that context, an attacker trying to exploit this sort of collision would end up presenting an interior node as a public key leaf node, but the size of an interior node is too small to be a valid public key, so no party that performs sanity checks on the public keys would be fooled by the attacker. In that case, tagging nodes as leaves or internal nodes is arguably a tiny tiny bit wasteful. That's the only argument I can think of, and it's a poor one. Edit: Okay, the other valid argument for not using prefixes to tag leaves and interior nodes is that you're using the provably secure Sakura construction, which using suffixes rather than prefixes. There are a few advantages to using suffixes, such as being able to have a single node containing both data and child nodes without having to know the length of the data portion before starting to hash the node. There's also better performance due to memory alignment when hashing memory-mapped files (if using block sizes that pack well into memory pages and cache lines) if you use suffixes. But, suffixes vs. prefixes is a tiny nit to pick.
    - kerkeslager 9y ago
      Okay, I guess in mathematical terms a better way to express the whole thing would be in terms of two hash functions: h_leaf(leaf) which takes a leaf. h_branch(branch_left, branch_right) which takes the two branches. The important point being that one should not be able to find a leaf such that h_leaf(leaf) = h_branch(branch_left, branch_right) for any branch_left, branch_right. Prefixes versus suffixes are just implementation details of the hash functions (i.e. h_leaf(x) = "\00" + sha256(x), h_branch(x,y) = "\01" + sha256(x + y) would also work).
- jlrubin 9y ago
  Because Bitcoin's Merkle tree is vulnerable to it as well :) The fix came through a higher order property (duplicate TXs not allowed anyways). https://bitcointalk.org/index.php?topic=102395.0 https://bitcointalk.org/index.php?topic=102395.0
moscovium 9y ago
This was interesting, but when you think about it, this isn't really a flaw as much as something inherent to the way it was designed. Imagine you had some combinations of functions f, g, and h such that f(g(h(x))) = y. Obviously you could calculate that as h(x) -> g(h(x)) -> f(g(h(x)) = y, but then of course knowing h(x), or g(h(x)) would enable you to find y as well. So of course, due to the recursive nature of it, picking any set of inputs that were the outputs of a previous call would give you the same output. That argument doesn't exactly fit multiple inputs, but the idea is the same.
- andrewflnr 9y ago
  You say that like flaws and inherent features are different. I say those are the worst kind of flaw. I guess the point is, this property (value-neutral) of that design makes it unsuitable for real-world purposes. Since the implementations in question are meant for real world use, that makes them flawed, at least. :)
  - aoeusnth1 9y ago
    Though in this case, there's a relatively simple fix...
  - aidenn0 9y ago
    For fixed-depth trees merkle trees are fine though. I have used them for just such a purpose.
JeremyBanks 9y ago
https://crypto.stackexchange.com/questions/2106/what-is-the-purpose-of-using-different-hash-functions-for-the-leaves-and-internals-of-a-hash-tree https://crypto.stackexchange.com/questions/2106/what-is-the-...
sandralopz5 9y ago
nice
KMag 9y ago
The authors of Keccak / SHA-3 came up with Sakura[0], a hash tree construction that's provably as collision-resistant as the underlying hash function and very flexible. If you're designing a new system using hash trees, you better use Sakura trees or have a good explanation for why not. Edit: I also wrote some demo code[1] for this attack when arguing with one of the IPFS guys about why they really shouldn't use Bittorrent BEP 30-style Merkle Trees. In order to get security with Bittorrent-style trees, the [length, root] pair really needs to be your cryptographic identifier, and you need to make sure they're always properly handled as a pair. There are just too many caveats to usage and we have provably secure alternatives. As a former LimeWire developer, it makes me sad that Gnutella's TigerTrees avoided this vulnerability long before bittorrent's BEP 30 was published, and yet Bittorrent got it wrong. It was a well-known vulnerability, and was covered as part of my interview at LimeWire. [0]https://keccak.team/files/Sakura.pdf https://keccak.team/files/Sakura.pdf [1]https://github.com/kmag/bad_examples/tree/master/bad_merkle_tree https://github.com/kmag/bad_examples/tree/master/bad_merkle_...
- orasis 9y ago
  Brings back good memories. Pad your leaf and inner nodes with different bytes y’all.
- QML 9y ago
  Can I ask you a quick question: do you think Merkle trees are a good model for key revocation? I'm currently working cryptographic file system for a class, and trying to speed up the sharing and de-sharing of files via symmetric keys. Right now, I'm thinking of adapting the tree-based certificate revocation model that Micali talked about [1]. Thanks! [1] https://patents.google.com/patent/US6097811 https://patents.google.com/patent/US6097811
  - KMag 9y ago
    Markle Trees are a good data structure whenever you want to securely represent an ordered set very compactly, with fairly compact proofs of set membership. If you're stuck with an architecture that depends on certificate revocation lists, I think Micali's representation of the CRL is both efficient and secure. On the other hand, blacklists (such as certificate revocation lists) are generally easier to exploit than whitelists (such as the published lists used in certificate transparency). I think we all would have been better off with an infrastructure that mandated certificate transparency, where a Merkle Tree of all valid certificates was published periodically by each Certificate Authority. In other words, keep a cryptographically verifiable whitelist instead of a cryptographically verifiable blacklist. For scalability, you'd want to have the published list be a Merkle Tree root of valid certificates, plus a signed tree hash of a Bloom filter of all of the certificates revoked in (say) the past month. From a signed Merkle Tree root, each site can create a compact proof of validity for its certificate of log(N) size. Using the signed Bloom filter, the site can keep reusing that proof for (say) a month. You'd want the Bloom filter to use a keyed hash function so that a collision in one publishing wouldn't be likely to keep colliding for the whole month.
Agnosco 9y ago
I think the Wikipedia reference doesn't do it justice - the article alone is already ~1500 words. Sorry, I couldn't help myself
bluesign 9y ago
Another solution to this attack can be: hashing root with tree depth as last step.
- kerkeslager 9y ago
  This doesn't work unless you can guarantee that the size of hashed sets is going to be a exact power of two, because otherwise subtree depths can differ.
  - bluesign 9y ago
    Oh I meant the longest subtree, afaik depth of merkel tree is the longest one no? Edit: Also I think element count can be also alternative for depth
    - kerkeslager 9y ago
      > Oh I meant the longest subtree, afaik depth of merkel tree is the longest one no? I get what you meant, but it still doesn't prevent the second preimage attack, unless you're forcing all subtrees to be the same depth. Think about the algorithm for testing set membership. How would they use the tree depth to distinguish between hash(hash(leafA) + hash(leafB)) and hash(leafC) where leafC = hash(leafA) + hash(leafB) but leafC is NOT a member of the set? Keep in mind that leafA and leafB could be leaves of the longest subtree, but other valid leaves could be on valid subtrees that are one node shorter. > Edit: Also I think element count can be also alternative for depth Element count doesn't solve the second preimage attack problem either.
      - bluesign 9y ago
        Oh I maybe wrong on this but I was assuming something like this ABCDEEEE / \ ABCD EEEE / \ / AB CD EE / \ / \ / A B C D E From: https://bitcoin.org/en/developer-guide#transaction-data https://bitcoin.org/en/developer-guide#transaction-data
DennisP 9y ago
I think I might be missing the point...is the attack just to pretend an intermediate hash was a leaf? If you're providing a merkle branch to prove that a document you've hashed is in the set, then I don't see how this helps you at all.
hedora 9y ago
I find this article and discussion unsettling. A large number of people made non-typesafe merkle trees (including bittorrent, apparently), and then were surprised that passing it incorrect types cause it to produce incorrect output. I don’t see how this is a vulnerability in the merkle tree algorithm. It just seems like yet another case of “python libraries contain bugs that are common in idiomatic python”. I guess since so many people have independently implemented the same mistake, the writeup is useful.
CodesInChaos 9y ago
My preferred fix is including the total size of data in the root hash, since it's often convenient to know the total file size before starting a download.

218 points by wepple 9y ago

This is a well known edge case of Merkle trees; my undergrad security course covered this as an aside and it is prominent on the wikipedia page.[0] For those not familiar with the specific implementation issue, this post should be a fun read. I don't know what's more concerning, that pymerkletools advertises itself for use with Bitcoin or that none of the contributors read the wiki page :| [0] https://en.wikipedia.org/wiki/Merkle_tree#Second_preimage_attack https://en.wikipedia.org/wiki/Merkle_tree#Second_preimage_at...

kerkeslager 9y ago
It's a bit strange to consider this even an edge case, and weird that one would even create a diagram (such as the one on the wikipedia page) that doesn't have a solution (such as a leaf node marker prepended). Why isn't the prepended leaf node marker included in the concept of a Merkle tree? Is there ever a situation where you'd want a Merkle tree that allowed this?
- KMag 9y ago
  The original use case for Merkle trees were to compactly represent sets of one-time-use public keys. In that context, an attacker trying to exploit this sort of collision would end up presenting an interior node as a public key leaf node, but the size of an interior node is too small to be a valid public key, so no party that performs sanity checks on the public keys would be fooled by the attacker. In that case, tagging nodes as leaves or internal nodes is arguably a tiny tiny bit wasteful. That's the only argument I can think of, and it's a poor one. Edit: Okay, the other valid argument for not using prefixes to tag leaves and interior nodes is that you're using the provably secure Sakura construction, which using suffixes rather than prefixes. There are a few advantages to using suffixes, such as being able to have a single node containing both data and child nodes without having to know the length of the data portion before starting to hash the node. There's also better performance due to memory alignment when hashing memory-mapped files (if using block sizes that pack well into memory pages and cache lines) if you use suffixes. But, suffixes vs. prefixes is a tiny nit to pick.
  - kerkeslager 9y ago
    Okay, I guess in mathematical terms a better way to express the whole thing would be in terms of two hash functions: h_leaf(leaf) which takes a leaf. h_branch(branch_left, branch_right) which takes the two branches. The important point being that one should not be able to find a leaf such that h_leaf(leaf) = h_branch(branch_left, branch_right) for any branch_left, branch_right. Prefixes versus suffixes are just implementation details of the hash functions (i.e. h_leaf(x) = "\00" + sha256(x), h_branch(x,y) = "\01" + sha256(x + y) would also work).
jlrubin 9y ago
Because Bitcoin's Merkle tree is vulnerable to it as well :) The fix came through a higher order property (duplicate TXs not allowed anyways). https://bitcointalk.org/index.php?topic=102395.0 https://bitcointalk.org/index.php?topic=102395.0

moscovium 9y ago

This was interesting, but when you think about it, this isn't really a flaw as much as something inherent to the way it was designed. Imagine you had some combinations of functions f, g, and h such that f(g(h(x))) = y. Obviously you could calculate that as h(x) -> g(h(x)) -> f(g(h(x)) = y, but then of course knowing h(x), or g(h(x)) would enable you to find y as well. So of course, due to the recursive nature of it, picking any set of inputs that were the outputs of a previous call would give you the same output. That argument doesn't exactly fit multiple inputs, but the idea is the same.

andrewflnr 9y ago
You say that like flaws and inherent features are different. I say those are the worst kind of flaw. I guess the point is, this property (value-neutral) of that design makes it unsuitable for real-world purposes. Since the implementations in question are meant for real world use, that makes them flawed, at least. :)
- aoeusnth1 9y ago
  Though in this case, there's a relatively simple fix...
- aidenn0 9y ago
  For fixed-depth trees merkle trees are fine though. I have used them for just such a purpose.

JeremyBanks 9y ago

https://crypto.stackexchange.com/questions/2106/what-is-the-purpose-of-using-different-hash-functions-for-the-leaves-and-internals-of-a-hash-tree https://crypto.stackexchange.com/questions/2106/what-is-the-...

sandralopz5 9y ago

nice

KMag 9y ago

The authors of Keccak / SHA-3 came up with Sakura[0], a hash tree construction that's provably as collision-resistant as the underlying hash function and very flexible. If you're designing a new system using hash trees, you better use Sakura trees or have a good explanation for why not. Edit: I also wrote some demo code[1] for this attack when arguing with one of the IPFS guys about why they really shouldn't use Bittorrent BEP 30-style Merkle Trees. In order to get security with Bittorrent-style trees, the [length, root] pair really needs to be your cryptographic identifier, and you need to make sure they're always properly handled as a pair. There are just too many caveats to usage and we have provably secure alternatives. As a former LimeWire developer, it makes me sad that Gnutella's TigerTrees avoided this vulnerability long before bittorrent's BEP 30 was published, and yet Bittorrent got it wrong. It was a well-known vulnerability, and was covered as part of my interview at LimeWire. [0]https://keccak.team/files/Sakura.pdf https://keccak.team/files/Sakura.pdf [1]https://github.com/kmag/bad_examples/tree/master/bad_merkle_tree https://github.com/kmag/bad_examples/tree/master/bad_merkle_...

orasis 9y ago
Brings back good memories. Pad your leaf and inner nodes with different bytes y’all.
QML 9y ago
Can I ask you a quick question: do you think Merkle trees are a good model for key revocation? I'm currently working cryptographic file system for a class, and trying to speed up the sharing and de-sharing of files via symmetric keys. Right now, I'm thinking of adapting the tree-based certificate revocation model that Micali talked about [1]. Thanks! [1] https://patents.google.com/patent/US6097811 https://patents.google.com/patent/US6097811
- KMag 9y ago
  Markle Trees are a good data structure whenever you want to securely represent an ordered set very compactly, with fairly compact proofs of set membership. If you're stuck with an architecture that depends on certificate revocation lists, I think Micali's representation of the CRL is both efficient and secure. On the other hand, blacklists (such as certificate revocation lists) are generally easier to exploit than whitelists (such as the published lists used in certificate transparency). I think we all would have been better off with an infrastructure that mandated certificate transparency, where a Merkle Tree of all valid certificates was published periodically by each Certificate Authority. In other words, keep a cryptographically verifiable whitelist instead of a cryptographically verifiable blacklist. For scalability, you'd want to have the published list be a Merkle Tree root of valid certificates, plus a signed tree hash of a Bloom filter of all of the certificates revoked in (say) the past month. From a signed Merkle Tree root, each site can create a compact proof of validity for its certificate of log(N) size. Using the signed Bloom filter, the site can keep reusing that proof for (say) a month. You'd want the Bloom filter to use a keyed hash function so that a collision in one publishing wouldn't be likely to keep colliding for the whole month.

Agnosco 9y ago

I think the Wikipedia reference doesn't do it justice - the article alone is already ~1500 words. Sorry, I couldn't help myself

bluesign 9y ago

Another solution to this attack can be: hashing root with tree depth as last step.

kerkeslager 9y ago
This doesn't work unless you can guarantee that the size of hashed sets is going to be a exact power of two, because otherwise subtree depths can differ.
- bluesign 9y ago
  Oh I meant the longest subtree, afaik depth of merkel tree is the longest one no? Edit: Also I think element count can be also alternative for depth
  - kerkeslager 9y ago
    > Oh I meant the longest subtree, afaik depth of merkel tree is the longest one no? I get what you meant, but it still doesn't prevent the second preimage attack, unless you're forcing all subtrees to be the same depth. Think about the algorithm for testing set membership. How would they use the tree depth to distinguish between hash(hash(leafA) + hash(leafB)) and hash(leafC) where leafC = hash(leafA) + hash(leafB) but leafC is NOT a member of the set? Keep in mind that leafA and leafB could be leaves of the longest subtree, but other valid leaves could be on valid subtrees that are one node shorter. > Edit: Also I think element count can be also alternative for depth Element count doesn't solve the second preimage attack problem either.
    - bluesign 9y ago
      Oh I maybe wrong on this but I was assuming something like this ABCDEEEE / \ ABCD EEEE / \ / AB CD EE / \ / \ / A B C D E From: https://bitcoin.org/en/developer-guide#transaction-data https://bitcoin.org/en/developer-guide#transaction-data

DennisP 9y ago

I think I might be missing the point...is the attack just to pretend an intermediate hash was a leaf? If you're providing a merkle branch to prove that a document you've hashed is in the set, then I don't see how this helps you at all.

hedora 9y ago

I find this article and discussion unsettling. A large number of people made non-typesafe merkle trees (including bittorrent, apparently), and then were surprised that passing it incorrect types cause it to produce incorrect output. I don’t see how this is a vulnerability in the merkle tree algorithm. It just seems like yet another case of “python libraries contain bugs that are common in idiomatic python”. I guess since so many people have independently implemented the same mistake, the writeup is useful.

CodesInChaos 9y ago

My preferred fix is including the total size of data in the root hash, since it's often convenient to know the total file size before starting a download.