Hash Functions: Properties, SHA-1, MD4, and Message Digests

TAKEAWAYS:

• Hash functions convert input data into a fixed-length "digest" (e.g., SHA-1 produces 160-bit hashes) using one-way compression and deterministic rules.
• Key properties: fixed-length output, deterministic, pre-image resistance, collision resistance, and avalanche effect—critical for security.
• SHA-1 processes 512-bit blocks via padding, 80 rounds of bitwise operations (AND, OR, XOR, NOT), and modular addition with constants.
• MD4 uses three passes (rounds) of bitwise operations and modular additions, but is now considered insecure due to collision vulnerabilities.
• Applications: Password storage (e.g., bcrypt), blockchain (e.g., Bitcoin’s Merkle trees), and digital signatures (e.g., eSewa’s transaction hashes).
• Exam focus: Trace SHA-1’s padding steps, compare MD4/SHA-1 rounds, and explain why hash functions cannot be reversed.

1. What Are Hash Functions?

Hash functions map data of arbitrary length to a fixed-size string (hash value or digest). Unlike encryption, they are one-way: given a hash, you cannot reverse-engineer the input. They are fundamental to:

• Data integrity (e.g., verifying downloaded files).
• Password storage (e.g., storing SHA-256(password + salt) instead of plaintext).
• Blockchain (e.g., Bitcoin’s proof-of-work relies on hashing).

Key Properties

A secure hash function must satisfy:

1. Fixed-length output: SHA-1 always produces a 160-bit hash.
2. Deterministic: Same input → same hash (e.g., SHA-1("hello") = 0aae2...).
3. Pre-image resistance: Hard to find input x such that H(x) = y (given y).
4. Collision resistance: Hard to find two inputs x ≠ y with H(x) = H(y).
5. Avalanche effect: A 1-bit change in input drastically changes the hash.

2. How Hash Functions Work: SHA-1

SHA-1 processes data in 512-bit blocks and produces a 160-bit hash. Steps:

1. Padding: Append bits to make input length ≡ 448 mod 512, then append original length (64-bit).
2. Initialize hash values: Five 32-bit registers (H0–H4).
3. Process blocks: For each 512-bit block:
   • Break into 16 32-bit words (W[0]–W[15]).
   • Extend to 80 words using W[t] = (W[t-3] XOR W[t-8] XOR W[t-14] XOR W[t-16]) <<< s.
   • 80 rounds of operations:
     • temp = (H <<< 5) + ((H & I) | (J & K)) + W[t] + K[t] + T[t]
     • Update registers: H = E, E = D, D = C, C = B, B = A, A = temp.

sequenceDiagram
    participant Input
    participant Padding
    participant SHA1
    participant Output
    Input->>Padding: Append bits + length
    Padding->>SHA1: 512-bit blocks
    SHA1->>SHA1: Initialize H0-H4
    loop 80 rounds
        SHA1->>SHA1: temp = (H <<< 5) + (H & I | J & K) + W[t] + K[t] + T[t]
        SHA1->>SHA1: Update registers (A-E)
    end
    SHA1->>Output: 160-bit hash

Worked Example: SHA-1 Padding Input: "hello" (ASCII: 0x68 65 6c 6c 6f).

1. Original length: 5 bytes → 40 bits.
2. Pad to 448 bits: append 1 + 0s → 0x68 65 6c 6c 6f 80 00...00.
3. Append length (64-bit): 0x0000000000000028.
4. Final block: 0x68 65 6c 6c 6f 80 00...00 28 00...00.

3. MD4: A Flawed but Historic Algorithm

MD4 was the precursor to MD5/SHA-1 but is now broken (collisions found). It uses:

• Three passes (rounds) of 16 operations each (total 48 rounds).
• Bitwise operations: AND, OR, XOR, NOT, and left rotations.
• Modular addition: + mod 2³².

MD4 Rounds:

Why MD4 is Insecure:

• Collision attacks: Two different inputs produce the same hash (e.g., MD4("a") = MD4("67e4...")).
• Weak compression: Bitwise operations are easier to reverse than SHA-1’s modular additions.

4. Real-World Applications

eSewa: Transaction Integrity

• When you pay a bill via eSewa, the app computes SHA-256(amount + merchantID + timestamp).
• The server verifies the hash to ensure the transaction wasn’t tampered with.

WhatsApp: Message Authentication

• WhatsApp uses SHA-256 to generate a hash of each message before encryption.
• If the hash changes during transmission, the recipient knows the message was altered.

Nepal Stock Exchange (NEPSE): Blockchain

• NEPSE’s experimental blockchain uses hashing to link trades securely.
• Each trade’s hash is stored in the previous block’s data, creating an immutable chain.

Worked Example: Password Storage (Like eSewa’s User DB)

5. Comparing SHA-1 and MD4

6. Common Pitfalls and Exam Traps

• Padding mistakes: Forgetting to append the original length in bits (not bytes).
• Confusing MD4/SHA-1 rounds: MD4 has 3 passes; SHA-1 has 80 rounds.
• Pre-image vs. collision resistance:
  • Pre-image: Given H(x), find x (hard).
  • Collision: Find any x ≠ y with H(x) = H(y) (even harder).
• Avalanche effect: A 1-bit change in input should change all bits in the hash.

Exam Tip

1. For SHA-1:
   • Memorize the padding steps (append 1, then 0s, then 64-bit length).
   • Know the 80-round structure: temp = (H <<< 5) + (H & I | J & K) + W[t] + K[t] + T[t].
2. For MD4:
   • Recall the three passes (F, G, H functions).
   • State why it’s insecure (collision attacks).
3. Properties:
   • List 5 properties of hash functions (fixed-length, deterministic, etc.).
   • Explain avalanche effect with an example (e.g., changing A to a flips half the hash bits).
4. Applications:
   • Link to eSewa/Khalti (transaction hashes) or WhatsApp (message integrity).