Cryptographic Hash Functions

calendarDec 12, 2024 · 3 min read · cryptography hashing crypto-knowhow mathematics  ·
Share on: linkedincopy

Cryptographic hash functions with mathematical properties and practical implementations.

Mathematical Definition

A cryptographic hash function $H: {0,1}^* \to {0,1}^n$ maps arbitrary-length input to fixed-length output.

$$ H(m) = h $$

Where:

  • $m$: Message (arbitrary length)
  • $h$: Hash digest (fixed length, e.g., 256 bits)

Security Properties

1. Preimage Resistance (One-Way)

Given $h$, computationally infeasible to find $m$ such that:

$$ H(m) = h $$

Complexity: $O(2^n)$ operations

2. Second Preimage Resistance

Given $m_1$, computationally infeasible to find $m_2 \neq m_1$ such that:

$$ H(m_1) = H(m_2) $$

Complexity: $O(2^n)$ operations

3. Collision Resistance

Computationally infeasible to find any $m_1 \neq m_2$ such that:

$$ H(m_1) = H(m_2) $$

Complexity: $O(2^{n/2})$ operations (Birthday Paradox)

Birthday Paradox

Probability of collision after $k$ hashes:

$$ P(collision) \approx 1 - e^{-\frac{k^2}{2 \cdot 2^n}} $$

For 50% probability:

$$ k \approx \sqrt{2^n} = 2^{n/2} $$

Example: SHA-256 ($n=256$) requires $\approx 2^{128}$ hashes for 50% collision probability.

Avalanche Effect

Small change in input causes large change in output:

$$ \text{If } m' = m \oplus \Delta \text{ (1-bit change)} $$

$$ \text{Then } H(m') \text{ differs from } H(m) \text{ in } \approx 50% \text{ of bits} $$

Common Algorithms

AlgorithmOutput SizeSecuritySpeedUse Case
SHA-256256 bitsHighFastGeneral purpose, Bitcoin
SHA-3VariableHighModerateModern alternative
BLAKE2VariableHighVery fastZcash, general
BLAKE3256 bitsHighFastestModern, parallel
MD5128 bits❌ BrokenFastLegacy only
SHA-1160 bits❌ WeakFastDeprecated

Python Implementation

 1import hashlib
 2
 3# SHA-256
 4data = b"Hello, World!"
 5hash_sha256 = hashlib.sha256(data).hexdigest()
 6print(f"SHA-256: {hash_sha256}")
 7
 8# SHA-3
 9hash_sha3 = hashlib.sha3_256(data).hexdigest()
10print(f"SHA-3: {hash_sha3}")
11
12# BLAKE2
13hash_blake2 = hashlib.blake2b(data, digest_size=32).hexdigest()
14print(f"BLAKE2: {hash_blake2}")
15
16# Verify integrity
17def verify_hash(data, expected_hash):
18    computed = hashlib.sha256(data).hexdigest()
19    return computed == expected_hash
20
21# File hashing
22def hash_file(filename):
23    sha256 = hashlib.sha256()
24    with open(filename, 'rb') as f:
25        for chunk in iter(lambda: f.read(4096), b""):
26            sha256.update(chunk)
27    return sha256.hexdigest()

Merkle Trees

Construction:

$$ \begin{aligned} H_0 &= H(\text{Data}0) \ H_1 &= H(\text{Data}1) \ H{01} &= H(H_0 | H_1) \ \text{Root} &= H(H{01} | H_{23}) \end{aligned} $$

Hash-Based Message Authentication

HMAC Construction

$$ \text{HMAC}(K, m) = H\left((K \oplus opad) | H((K \oplus ipad) | m)\right) $$

Where:

  • $K$: Secret key
  • $opad$: Outer padding ($0x5c$ repeated)
  • $ipad$: Inner padding ($0x36$ repeated)
  • $|$: Concatenation
 1import hmac
 2import hashlib
 3
 4key = b"secret-key"
 5message = b"message"
 6
 7# Create HMAC
 8mac = hmac.new(key, message, hashlib.sha256).digest()
 9
10# Verify HMAC (constant-time comparison)
11def verify_hmac(message, mac, key):
12    expected = hmac.new(key, message, hashlib.sha256).digest()
13    return hmac.compare_digest(mac, expected)

Applications

1. Data Integrity

 1# Download verification
 2import requests
 3import hashlib
 4
 5url = "https://example.com/file.zip"
 6expected_hash = "abc123..."
 7
 8response = requests.get(url)
 9computed_hash = hashlib.sha256(response.content).hexdigest()
10
11if computed_hash == expected_hash:
12    print("File integrity verified!")

2. Proof of Work (Bitcoin)

Find nonce $n$ such that:

$$ H(\text{block_header} | n) < \text{target} $$

1def proof_of_work(block_header, target):
2    nonce = 0
3    while True:
4        data = f"{block_header}{nonce}".encode()
5        hash_result = hashlib.sha256(data).hexdigest()
6        if int(hash_result, 16) < target:
7            return nonce
8        nonce += 1

3. Commitment Schemes

Commit to value without revealing it:

$$ \text{commit}(x, r) = H(x | r) $$

Later reveal $x$ and $r$ to verify.

Related Snippets