Hash Functions, Message Authenticity & SHA-1: Properties, Workings & Attacks

Core Concepts: What is a Cryptographic Hash Function?

Definition and Purpose

A cryptographic hash function $H$ is a deterministic algorithm that:

• Takes an input (message $M$) of arbitrary length.
• Produces a fixed-size output (hash value $h$) of length $n$ bits.
• Must satisfy four critical properties (see table below).

Why use hashes?

• Data integrity: Detect tampering (e.g., downloaded files, software updates).
• Password storage: Store only hashes, not plaintext (e.g., bcrypt in Linux /etc/shadow).
• Digital signatures: Sign hashes, not entire documents (e.g., PDF signatures).
• Blockchain: Bitcoin uses SHA-256 to link blocks via hash chains.

classDiagram
    class HashFunction {
        +Input: Arbitrary-length message M
        +Output: Fixed-length hash h (e.g., 256 bits)
        +Properties: Preimage resistance, 2nd preimage resistance, Collision resistance, Avalanche effect
        +Example: SHA-1, SHA-256, MD5
    }
    class SHA1 {
        +Output: 160-bit hash
        +Steps: Padding → Parse into 512-bit blocks → Process blocks → Produce hash
        +Weakness: Vulnerable to collision attacks
    }
    HashFunction <|-- SHA1

The Four Properties (with Visuals)

How SHA-1 Works: Step-by-Step with Diagram

SHA-1 processes messages in 512-bit blocks using the Merkle-Damgård construction. Here’s the pipeline:

1. Padding: Append bits to make message length a multiple of 512 bits.

   • Original message $M$ → Append 1 + 0s + 64-bit length of $M$.

2. Parse into 512-bit blocks: Split padded message into $B_1,B_2,\dots ,B_n$.

3. Initialize hash buffers: Five 32-bit registers:

   • $H_0=67452301$
   • $H_1=EFCDAB89$
   • $H_2=98BADCFE$
   • $H_3=10325476$
   • $H_4=C3D2E1F0$

4. Process each block:

   • For each 512-bit block $B_i$, perform 80 rounds of bitwise operations:
     • Break block into 16 32-bit words $W_0\dots W_{15}$.
     • Extend to 80 words using $W_t=\text{rotate}(W_{t-3}\oplus W_{t-8}\oplus W_{t-14}\oplus W_{t-16})$.
     • Update registers using non-linear functions (e.g., f(t, B, C, D) = (B AND C) OR ((NOT B) AND D)).

5. Final hash: Concatenate $H_0\dots H_4$ to get 160-bit output.

flowchart TD
    A["Input Message M"] --> B["Padding: Append '1' + '0's + length"]
    B --> C["Parse into 512-bit blocks B1, B2, ..., Bn"]
    C --> D["Initialize H0-H4"]
    D --> E["For each block Bi:<br/>1. Break into 16 words<br/>2. Extend to 80 words<br/>3. 80 rounds of bitwise ops"]
    E --> F["Update H0-H4"]
    F --> G["Concatenate H0-H4 → 160-bit hash"]

Worked Example: Hashing "Nepal" with SHA-1

1. Convert "Nepal" to binary: 01001101 01100101 01110010 01100001 01101000 (ASCII).
2. Pad to 512 bits (add 1 + 0s + 64-bit length).
3. Process block (simplified):
   • Initial registers: H0=67452301, H1=EFCDAB89, etc.
   • After 80 rounds, registers become:
     • H0 = 374a4027
     • H1 = 76674785
     • H2 = c081f44e
     • H3 = 342c6526
     • H4 = 15b0fb47
4. Concatenate → Final SHA-1 hash: 374a402776674785c081f44e342c652615b0fb47

Attacks on Hash Functions

1. Length-Extension Attack (SHA-1)

How it works:

• SHA-1 doesn’t hide the length of the original message.
• Attacker appends known data to a hashed message and computes a new valid hash.

Example: HMAC Vulnerability

• Scenario: You receive a signed message from a bank (e.g., "Transfer 1000 NPR to X98765").
• Attack:
  1. You intercept the hash $h=H(\text{secret\_key}\oplus \text{opad}\parallel H(\text{secret\_key}\oplus \text{ipad}\parallel \text{message}))$.
  2. Append || "Transfer 5000 NPR to Y12345" to the original message.
  3. Compute new hash using the same key → valid signature for the new message!

Mitigation: Use HMAC-SHA256 (not HMAC-SHA1) and keyed hashing (e.g., HKDF).

2. Collision Attacks

Real-World Impact:

• DigiNotar (2011): Attackers created a fake certificate for google.com that collided with a legitimate one, tricking users into installing malware.
• SHA-1 Deprecation: NIST banned SHA-1 for new systems in 2011; browsers now reject SHA-1 certificates.

Worked Example: Fake PDF Collision

1. Start with a benign PDF file $F$.
2. Find a malicious PDF $F^{\prime }$ such that $\text{SHA-1}(F)=\text{SHA-1}(F^{\prime })$.
3. Replace a legitimate file on a website with $F^{\prime }$. Users see no warning (same hash), but $F^{\prime }$ installs malware.

Message Authentication: Hash-Based Schemes

1. HMAC (Hash-Based Message Authentication Code)

How it works:

• Combines a hash function with a secret key to authenticate messages.
• Formula: $\text{HMAC}(K,M)=H((K\oplus \text{opad})\parallel H((K\oplus \text{ipad})\parallel M))$ where:
  • $\text{opad}=0x5c5c5c\dots 5c$ (64 bytes)
  • $\text{ipad}=0x363636\dots 36$ (64 bytes)

Example: Secure File Download (e.g., eSewa App Updates)

• Step 1: eSewa signs the update file with HMAC-SHA256 using a secret key.
• Step 2: User downloads file + HMAC.
• Step 3: User recomputes HMAC locally. If it matches → file is authentic.

2. Kerberos Authentication (Hash-Based Trust Framework)

How it works (simplified):

1. Client requests a Ticket Granting Ticket (TGT) from Key Distribution Center (KDC).
2. KDC returns $\text{TGT}=\{\text{Client},\text{TGS},\text{timestamp},H(\text{Client},\text{TGS},\text{secret\_key})\}$.
3. Client uses TGT to request a service ticket for a server (e.g., database).
4. Server verifies the hash to authenticate the client.

Real-World Use: Microsoft Active Directory uses Kerberos for Windows domain authentication.

sequenceDiagram
    participant Client
    participant KDC
    participant Server
    Client->>KDC: Auth request (ID, timestamp)
    KDC->>Client: TGT = {Client, TGS, timestamp, H(Client, TGS, secret_key)}
    Client->>KDC: Service request (TGT, Server ID)
    KDC->>Client: Service ticket = {Client, Server, timestamp, H(Client, Server, secret_key)}
    Client->>Server: Service ticket + auth request
    Server->>Client: Verify H() → Grant access

Comparison of Hash Algorithms

Exam Tip: Always prefer SHA-256 or SHA-3 over SHA-1/MD5. SHA-1 is only acceptable for legacy systems with no upgrade path.

In the Real World

1. eSewa and Khalti (Nepal)

   • Idea Used: HMAC-SHA256 for transaction authentication.
   • How: When you pay via eSewa, the app computes HMAC(K, "Transfer|Amount|Recipient") and sends it to the server. The server verifies the HMAC to ensure the request wasn’t tampered with.
   • Why It Matters: Prevents man-in-the-middle attacks where an attacker alters your payment details.

2. Ncell and NTC Billing Systems

   • Idea Used: Cryptographic hashes for invoice integrity.
   • How: Your monthly bill is stored as a hash (e.g., SHA-256) in the NTC database. When you download the bill, the app verifies the hash matches the server’s stored hash to ensure no one altered the charges.
   • Real Example: If an attacker changes your usage data from "500 MB" to "5000 MB", the hash won’t match, and the system flags the tampering.

3. Daraz and Amazon Order Processing

   • Idea Used: Merkle trees (hash chains) for blockchain-like order tracking.
   • How: Daraz uses hashes to link orders in a tree structure. If a single order is altered, the root hash changes, invalidating the entire batch. This helps detect fraud in bulk order processing.
   • Worked Example:
     • Suppose Daraz processes 1000 orders in a batch. Each order’s hash is computed, then hashed again with the next order (like a linked list). The final root hash is stored. If Order #456 is altered, the root hash changes, and Daraz’s system rejects the batch.

4. WhatsApp End-to-End Encryption

   • Idea Used: SHA-256 for message integrity.
   • How: When you send a message, WhatsApp computes SHA-256(message + timestamp) and sends both the encrypted message and the hash. The recipient decrypts and verifies the hash to ensure the message wasn’t modified in transit.

Exam Tip: How to Score Full Marks

Do’s:

1. Diagrams are mandatory for SHA-1 steps. Draw the Merkle-Damgård pipeline (padding → blocks → rounds → hash) and label all parts.
2. Define properties with examples:
   • For preimage resistance, say: "Finding the original password from its MD5 hash is computationally infeasible (e.g., md5("password") cannot be reversed quickly)."
3. Compare algorithms in a table (like above) for questions on "differences between MD5 and SHA-256."
4. Use real-world examples in explanations:
   • "Like how eSewa uses HMAC to verify your payment request hasn’t been altered by a hacker."
5. For Kerberos, always show the sequence diagram with:
   • Client → KDC (TGT request)
   • KDC → Client (encrypted TGT)
   • Client → Server (service ticket)

Don’ts:

1. Don’t describe SHA-1 as "just hashing"—explain the 5-step process (padding, parsing, rounds, etc.).
2. Avoid vague statements like "hashes are secure." Instead, say: "SHA-256 is collision-resistant up to 2^128 operations, making it secure for current applications."
3. Never skip the math in worked examples. Show:
   • Padding calculation (e.g., "Original length: 56 bits → padded to 64 bits").
   • Register updates (e.g., "After Round 10, $H_0$ becomes 0x374a4027").

Common Pitfalls:

• Mixing up HMAC and digital signatures:
  • HMAC = hash + secret key (for authentication).
  • Digital signature = hash + private key (for non-repudiation).
• Forgetting the avalanche effect: Always mention it when listing properties.
• Using SHA-1 in answers: Examiners deduct marks if you don’t note its deprecation.