Chaining calls to the only available hash function to “increase” the entropy

by

Summary

The question revolves around increasing entropy in a hash function by chaining multiple calls to the same hash function. The goal is to determine if this approach can artificially increase the entropy of a 64-bit hash function, specifically a custom MD5 implementation, to a higher bit length such as 96-128 bits or even 256 bits through bitwise concatenation.

Root Cause

The root cause of the issue is the limited entropy provided by the 64-bit hash function, leading to a high chance of collisions (approximately 2.5%) when hashing a large number of entries (10^9). The proposed solution attempts to mitigate this issue by chaining multiple hash calls with concatenated inputs.

Why This Happens in Real Systems

This scenario occurs in real systems when:

  • Limited cryptographic primitives are available.
  • Legacy systems or framework constraints restrict the use of more secure or higher-entropy hash functions.
  • Misconceptions about entropy lead to attempts to artificially increase entropy through naive methods.

Real-World Impact

The real-world impact includes:

  • Increased collision rates, leading to data corruption or security vulnerabilities.
  • Performance degradation due to excessive computation required for the chained hash calls.
  • Potential for denial-of-service (DoS) attacks** if the hashing mechanism is exploited.

Example or Code

import hashlib

def encode(x):
    return len(x).to_bytes(4, byteorder='big') + x.encode()

def compoundHash(str):
    h1 = hashlib.md5(encode("round1") + encode(str)).digest()
    h2 = hashlib.md5(encode("round2") + h1 + encode(str)).digest()
    h3 = hashlib.md5(encode("round3") + h2 + encode(str)).digest()
    h4 = hashlib.md5(encode("round4") + h3 + encode(str)).digest()
    finalHash = h1 + h2 + h3 + h4
    return finalHash

# Example usage
input_str = "example_input"
result = compoundHash(input_str)
print(result.hex())

How Senior Engineers Fix It

Senior engineers address this issue by:

  • Using established cryptographic hash functions with sufficient entropy (e.g., SHA-256 or BLAKE2).
  • Implementing proper key stretching or password hashing algorithms (e.g., Argon2, PBKDF2, or Bcrypt).
  • Avoiding homemade or naive entropy-increasing schemes.

Why Juniors Miss It

Juniors may miss this because they:

  • Lack understanding of cryptographic principles and the limits of hash functions.
  • Overestimate the effectiveness of simple entropy-increasing techniques.
  • Fail to consider the performance and security implications of their solutions.

Leave a Comment