The current hash calculation has a bug and easy to create collisions.
The current hash calculation is based on the original spec:
https://github.com/murbard/plebeia/blob/95a0eed6f7b8c6836d15032557467a3e93bd83b8/README.md
Here is the minimum model to explain the problem:
The definition of the tree. For simplicity we ignore Internal
here:
node ::= Leaf v
| Extender seg node
| Bud node
where seg is a binary of 224bits.
The definition of the hash calculation H(n)
:
H(Leaf v) = h(v)
H(Extender seg node) = take224(H(node)) || seg
H(Bud node) = H(node)
where
* h(v) is the 448bits of hash of bytes v
* take224 takes the first 224 bits of 448 bits
* (||) is the concatenation of bits
A collision can be made easily:
H(Bud (Extender seg1 (Leaf v)))
= H(Extender seg1 (Leaf v))
= take224(h(v)) || seg1
H(Bud (Extender seg1 (Bud (Extender seg2 (Leaf v)))
= H(Extender seg1 (Bud (Extender seg2 (Leaf v))))
= take224(H(Bud (Extender seg2 (Leaf v)))) || seg1
= take224(H(Extender seg2 (Leaf v)))) || seg1
= take224(take224(h(v)) || seg2) || seg1
= take224(h(v)) || seg1
This is because take224(take224(hash) || x) = take224(hash)
for any hash
and x
.
One of Bud
and Extender
must "shake" the hash of its subnode instead of copying.
Edited by Jun Furuse