Analysis of collision probability in Merkle trees in the Random Oracle Model

This work analyzes the probability of collisions in Merkle graphs, with a focus on a specific class of attacks in balanced Merkle trees. To provide a tractable model, each hash function is modeled as an independent random oracle. A general methodology for computing collision probabilities in arbitrary Merkle graphs is provided, for an arbitrary amount of modified nodes. The main finding of the thesis is the fact that an attack carried out modifying multiple nodes is not necessarily more powerful than the one carried out modifying only one node. Specifically, the collision probability depends on the height of the attacked Merkle tree, increasing for higher trees, and on the position of the modified nodes in the tree. In the last chapter of the thesis, an approximate statistical description of the random variable used in the model is provided, along with the derivation and the proof of the formulas necessary to iteratively compute each term of the moment-generating function.