Hash Functions & Message Authentication: SHA, MD5, Digital Signatures & Attacks

TAKEAWAYS:

• Hash functions convert variable-length input into fixed-length output (e.g., MD5 → 128-bit, SHA-256 → 256-bit) using one-way compression and avalanche effect.
• Message authentication relies on hash functions + secret keys (MACs) or digital signatures (asymmetric keys) to detect tampering.
• SHA-2 (e.g., SHA-256) is collision-resistant and used in Bitcoin, TLS, and Ncell’s OTP systems, while MD5 is broken (e.g., collision attacks on PDFs).
• Digital signatures (RSA + hash) authenticate senders (e.g., NEPSE stock certificates) and prevent repudiation.
• Attacks: Preimage (find input for given hash), collision (find two inputs with same hash), and birthday (find any collision in $O(2^{n/2})$).
• Real-world use: eSewa uses SHA-256 to hash transaction IDs; WhatsApp uses MACs for end-to-end encryption; banks use digital signatures for cheque authentication.

1. What is a Hash Function?

A hash function $H$ maps an input message $M$ of arbitrary length to a fixed-length hash value $h$: $$h=H(M)$$ Key properties:

1. Deterministic: Same input → same hash.
2. Fixed-length output: MD5 → 128-bit, SHA-256 → 256-bit.
3. Preimage resistance: Hard to reverse $h\to M$.
4. Collision resistance: Hard to find $M_1\ne M_2$ with $H(M_1)=H(M_2)$.
5. Avalanche effect: Small input change → completely different hash.

Visual: Hash Function Workflow

flowchart TD
    A["Input Message (M)\nVariable length"] -->|"Hash Function H"| B["Fixed-length Hash (h)\n(e.g., 256-bit)"]
    B --> C["Stored/Transmitted\n(e.g., password DB, blockchain)"]
    C --> D["Verify Integrity:\nRecompute H(M) and compare"]

2. How Hash Functions Work: MD5 vs. SHA-2

A. MD5 (Broken but Historically Important)

• Output: 128-bit (16 hex chars).
• Process:
  1. Pad input to 512-bit blocks (add 1 + 0s + original length).
  2. Initialize 4 buffers (A, B, C, D) to known values.
  3. Process each 512-bit block with 4 rounds of bitwise operations (AND, OR, XOR, shifts).
  4. Combine results to produce final hash.

Weaknesses:

• Vulnerable to collision attacks (e.g., two different PDFs with same MD5 hash).
• Not secure for cryptographic use (e.g., SSL/TLS, passwords).

B. SHA-2 (Secure Standard)

• Variants: SHA-224, SHA-256, SHA-384, SHA-512 (most common: SHA-256).
• Process (simplified for SHA-256):
  1. Pad input to 512-bit blocks (like MD5 but with stricter rules).
  2. Initialize 8 buffers (H_0 to H_7) to constants.
  3. 64 rounds of operations (bitwise, modular addition, compression).
  4. Final hash is concatenation of all buffers.

Example: Hashing "hello" with SHA-256

import hashlib
print(hashlib.sha256(b"hello").hexdigest())

Output: 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

3. Message Authentication: Hash + Secret (MAC) vs. Digital Signatures

How HMAC Works (Example: HMAC-SHA256)

1. Keyed hash: Combine secret key $K$ with message $M$ using SHA-256 twice.
2. Output: 256-bit MAC (e.g., a7ffc6f8...).
3. Verification: Recipient recomputes HMAC with their copy of $K$.

sequenceDiagram
    Alice->>Bob: M + HMAC-SHA256(K, M)
    Bob->>Bob: Verify HMAC-SHA256(K, M) == received MAC
    alt Match
        Bob->>Alice: "Message is authentic!"
    else Mismatch
        Bob->>Alice: "Tampering detected!"
    end

Real-world example:

• eSewa uses HMAC-SHA256 to authenticate payment requests between user and bank.
• WhatsApp uses MACs to verify end-to-end encrypted messages.

4. Digital Signatures: RSA + Hash

Steps:

1. Sender hashes message $M$ → $h=H(M)$.
2. Signs hash with private key → signature $S$.
3. Sends $(M,S)$.
4. Recipient:
   • Hashes $M$ → $h^{\prime }$.
   • Verifies $S$ with sender’s public key → $h^{\prime \prime }$.
   • If $h^{\prime }=h^{\prime \prime }$, message is authentic and untampered.

Example: Signing a NEPSE Trade Order

sequenceDiagram
    Trader->>Trader: M = "Buy 100 shares of NABIL at 1000"
    Trader->>Trader: h = SHA256(M)
    Trader->>Trader: S = RSA_sign(h, private_key)
    Trader->>NEPSE: (M, S)
    NEPSE->>NEPSE: h' = SHA256(M)
    NEPSE->>NEPSE: Verify RSA_verify(h', S, public_key)
    alt Valid
        NEPSE->>Trader: "Order executed!"
    else Invalid
        NEPSE->>Trader: "Rejected: Tampering!"
    end

5. Attacks on Hash Functions

Worked Example: MD5 Collision Attack

• Goal: Find two files $F_1$ and $F_2$ with $\text{MD5}(F_1)=\text{MD5}(F_2)$.
• Result: Researchers created two different PDFs with identical MD5 hashes in 2008.
• Impact: Fake software updates, malicious files bypassing checksums.

6. Real-World Applications

A. eSewa: Secure Transactions

• Problem: Ensure payment requests aren’t altered during transfer.
• Solution:
  1. User’s phone hashes the transaction details (amount, merchant ID) with SHA-256.
  2. eSewa server verifies the hash using the merchant’s public key (digital signature).
  3. If hashes match, the payment is processed.

B. WhatsApp: End-to-End Encryption

• Problem: Prevent MITM attacks on messages.
• Solution:
  • Uses SHA-256 to hash message fragments.
  • HMAC-SHA256 authenticates each message segment.
  • If any segment’s HMAC fails, the message is rejected.

C. NEPSE: Stock Certificate Authentication

• Problem: Prevent forged trade orders.
• Solution:
  • Brokers sign orders with RSA + SHA-256.
  • NEPSE verifies signatures before execution.
  • Example: A signature on "Buy 100 NABIL shares" must match the broker’s public key.

7. Primality Testing and Hash Functions

While not directly part of hashing, primality testing (e.g., Miller-Rabin) is used in:

• Key generation for RSA (hash functions rely on RSA for digital signatures).
• Secure random number generation (e.g., choosing cryptographic keys).

Example: Miller-Rabin Test for 37

1. Write $n-1=36=2^2\times 9$.
2. Pick a random base $a=2$.
3. Compute $a^9\mathrm{mod}37=2^9\mathrm{mod}37=512\mathrm{mod}37=1$.
4. Since $512\mathrm{mod}37=1$, 37 is probably prime (passes test).

Exam Tip

1. Define clearly:

   • "A hash function is a deterministic function $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ that is preimage-resistant and collision-resistant."
   • "Digital signature = hash + asymmetric encryption (e.g., RSA)."

2. Compare MD5 vs. SHA-2:

   Feature	MD5	SHA-256
   Output Size	128-bit	256-bit
   Security	Broken	Secure
   Use Case	Checksums (legacy)	Blockchain, TLS

3. Worked examples:

   • Show one padding step for MD5/SHA-2 (e.g., pad "hello" to 512 bits).
   • Trace one round of SHA-256 (e.g., how A, B, C buffers update).

4. Attacks:

   • Explain birthday attack in terms of $O(2^{n/2})$ complexity.
   • Relate collision attacks to real-world exploits (e.g., fake certificates).

5. Real-world tie-ins:

   • Link HMAC to eSewa/Khalti payments.
   • Link digital signatures to NEPSE or code signing (e.g., Windows executables).

6. Short notes:

   • Phishing Attack: Fake login pages that steal credentials (hashes are useless if passwords are leaked).
   • Two-Factor Authentication (2FA):
     • Something you know (password) + something you have (OTP/SMS).
     • Example: eSewa requires password + OTP sent to your phone.

Final Visual Summary

mindmap
  root((Hash Functions & Auth))
    MD5
      "128-bit output"
      "Broken (collisions)"
      "Used in checksums"
    SHA-2
      "256/512-bit output"
      "Secure (SHA-256)"
      "Used in Bitcoin, TLS"
    MAC
      "Hash + Secret Key"
      "HMAC-SHA256"
      "eSewa, APIs"
    Digital Signatures
      "Hash + Private Key"
      "RSA + SHA256"
      "NEPSE, Code Signing"
    Attacks
      "Preimage"
      "Collision"
      "Birthday"