Cybersecurity: Length Extension Attack

A length extension attack exploits a structural flaw in cryptographic hash functions using the Merkle-Damgård construction, allowing attackers to append data to a message and generate a valid hash without knowing the original message or secret key. This vulnerability affects widely used algorithms like MD5, SHA-1, and SHA-256, compromising message integrity and authentication.

---

Key Points

• Vulnerable algorithms: MD5, SHA-1, SHA-256, and SHA-512 due to their Merkle-Damgård construction
• Attack requirements:
  • Original hash value
  • Message length (or estimate)
  • Knowledge of padding rules
• Mechanism: Uses the final hash as an internal state to continue hashing with appended data
• Impact: Compromises integrity and authentication, not confidentiality
• Primary defense: Use HMAC or SHA-3

---

How the Attack Works

The Vulnerability

The Merkle-Damgård construction processes data in sequential blocks, maintaining an internal state that passes from one block to the next. The final hash output is the internal state after processing the last block, which creates an exploitable weakness:

1. The final hash reveals the internal state of the hash function.
2. This state can be used as a starting point to continue hashing.
3. An attacker appends new data and produces a valid hash.
4. No knowledge of the original message or secret key is required.

Critical Insight: The hash function cannot distinguish between a genuine message and one that has been extended using this technique.

---

Attack Prerequisites

To execute a length extension attack, an attacker needs:

• Hash of the original message: Often publicly available or transmitted over networks.
• Message length: Can be determined from application behavior, guessed, or brute-forced.
• Padding rules: Standardized and publicly documented for MD5, SHA-1, and SHA-256.

---

Step-by-Step Attack Process

1. Obtain the original hash: Capture the hash representing the internal state.
2. Reconstruct the padding: Apply the same padding rules the hash function used.
3. Initialize with the hash: Use the obtained hash as the starting internal state.
4. Append malicious data: Add the attacker's chosen content after the padding.
5. Continue hashing: Process the new data blocks using the hash function's algorithm.
6. Generate valid hash: Produce a legitimate hash for the extended message.

---

Practical Example

Legitimate Scenario

Message: secret_key + "user=alice&role=user"
Hash: abc123def456...

Attack Scenario

Original: secret_key + "user=alice&role=user"
Original Hash: abc123def456...

Attacker reconstructs:
secret_key + "user=alice&role=user" + [padding]

Attacker appends: "&role=admin"

Extended message:
secret_key + "user=alice&role=user" + [padding] + "&role=admin"

New valid hash: xyz789ghi012...

Result: The system accepts the modified message as authentic, allowing the attacker to escalate privileges from user to admin.

---

Vulnerable Hash Functions

Hash Function	Vulnerability Status	Notes
MD5	Highly vulnerable	Deprecated; broken for collision resistance
SHA-1	Highly vulnerable	Phased out in modern systems
SHA-256	Vulnerable	Cryptographically strong but susceptible
SHA-512	Vulnerable	Same Merkle-Damgård weakness as SHA-256
SHA-3	Not vulnerable	Uses Keccak sponge construction

Important: Even strong functions like SHA-256 are vulnerable when used for message authentication without proper construction like HMAC.

---

Mitigation Strategies

Use HMAC (Recommended)

HMAC prevents length extension attacks through its double-hashing construction:

HMAC(K, M) = H((K ⊕ opad) || H((K ⊕ ipad) || M))

Why HMAC works:

• The internal state after processing the message is not the final output.
• The secret key is processed both before and after the message.
• The nested structure prevents attackers from using the output to continue hashing.

Alternative Approaches

• Use SHA-3: Immune to length extension attacks due to its Keccak sponge construction.
• Use authenticated encryption: Schemes like AES-GCM or ChaCha20-Poly1305 provide both encryption and authentication.
• Append key at the end: Use H(M || K) instead of H(K || M). Less secure than HMAC and not recommended for production.

---

Security Implications

This attack compromises:

• Message integrity: Modified messages appear unaltered and valid.
• Authentication: Forged messages seem to come from legitimate sources.
• Authorization: Attackers can escalate privileges or modify permissions.
• API security: Signed API requests can be manipulated to perform unauthorized actions.

Note: This is not a confidentiality attack. The original message content remains unknown to the attacker.

---

Common Vulnerable Scenarios

• API authentication: Systems using hash(secret + request_data) for API signatures.
• Cookie signing: Web applications using hash(secret + cookie_value) to prevent tampering.
• Token generation: Authentication tokens created with hash(secret + user_data).
• File integrity: Systems verifying file integrity with hash(key + file_content).

---

Summary

Length extension attacks exploit the Merkle-Damgård construction by using the hash output as an internal state to continue processing additional data. While MD5, SHA-1, SHA-256, and SHA-512 are vulnerable when used directly for message authentication, HMAC or SHA-3 completely neutralize this threat. Always use HMAC, SHA-3, or authenticated encryption schemes for message authentication.

---

Learn More

• Explore HMAC implementations in your preferred programming language.
• Study the Keccak sponge construction used in SHA-3.
• Review OWASP guidelines for secure cryptographic practices.