Analysis of the Effect of Padding Schemes on Entropy, Bit Distribution, Hash Collisions, and Processing Time in Merkle-Damgård

Abstract

Data security in cryptographic systems is highly dependent on the strength of the hashing algorithm. One of the most commonly used hashing structures is Merkle-Damgård, which converts the compression function into a fixed-size hashing function. The padding technique in this structure plays an important role in determining the bit distribution, entropy, and the probability of collision in the hash results. This study aims to analyze and compare three padding methods, namely 1 & 0 bit padding, repeating pattern padding (0xAA), and 1 bit padding (0xFF), based on bit distribution parameters, Shannon entropy, hash collision, and processing time. The results show that 1 bit padding (0xFF) has the highest Shannon entropy value (0.9940), indicating a better level of randomness compared to other methods. In terms of bit distribution, this padding also produces better balance than other paddings. However, the hash collision rate (74.90%) is still relatively high, indicating that the padding method alone is not enough to significantly reduce the probability of collision. In terms of time efficiency, padding bits 1 & 0 have the fastest execution time (0.000132 seconds), while padding bit 1 (0xFF) has the longest processing time (0.000177 seconds). With these results, it can be concluded that the padding method affects the hash characteristics, but does not significantly reduce the collision probability. Therefore, further optimization is needed to improve the security of Merkle-Damgård-based hashing.