Abstract
We use various types of cryptographic algorithms for the protection of personal and sensitive information in application environments, such as internet banking and electronic commerce. However, recent research has introduced that if we implement modes of operation, padding methods, and other cryptographic implementations incorrectly, critical information can be leaked even though the underlying cryptographic algorithms are secure. Among these attacking techniques, the padding oracle attack is representative. In this paper, we analyze the possibility of padding oracle attacks on 12 kinds of padding techniques that can be applied to the CBC operation mode of a block cipher. As a result, we discovered that 3 kinds were safe padding techniques and 9 kinds were unsafe padding techniques. We propose 5 considerations when designing safe padding techniques to have resistance to the padding oracle attack through the analysis of three kinds of safe padding techniques.
Introduction
Even with mathematically robust block ciphers like AES or Triple DES, the security of a system often hinges on implementation details. A critical, yet frequently overlooked, component is the padding scheme used to align data to block boundaries. This paper, published in the Journal of The Korea Institute of Information Security & Cryptology, explores how improper padding in Cipher Block Chaining (CBC) mode can lead to a complete compromise of confidentiality through Padding Oracle Attacks (POA).
The Padding Oracle Mechanism
A Padding Oracle Attack is a side-channel attack where an adversary exploits the error messages returned by a server during decryption. If a server distinguishes between a decryption that failed due to incorrect padding versus other errors, it acts as an "oracle."
By iteratively modifying the ciphertext and observing whether the oracle returns a "VALID" or "INVALID" padding response, an attacker can deduce the intermediary values of the decryption process and, ultimately, the plaintext itself, without ever possessing the secret key.
Padding in CBC Mode
In CBC mode, each block of plaintext is XORed with the previous ciphertext block before being encrypted. During decryption, the process is reversed. Because block ciphers require fixed-length inputs, padding is appended to the final block of the message.
As shown in the figure above, the final block often contains specific padding bytes (e.g., 0x05). The vulnerability arises because the validity of these bytes is checked after the XOR operation with the previous ciphertext block, which an attacker can manipulate.
Security Audit of Padding Standards
The researchers performed a theoretical and algorithmic analysis of 12 padding methods, categorized into byte-based (8 types) and bit-based (4 types) schemes.
Key Findings:
- Vulnerability Audit: 9 out of the 12 analyzed techniques were found to be unsafe. Common standards like PKCS #7 (CBC-PAD) are highly vulnerable because they include the padding length within the padding itself, providing a structured target for attackers.
- The "Safe" Trio: Only three methods—PAIR-PAD, ABYT-PAD, and ABIT-PAD—were found to be truly resistant. These succeed by eliminating predictable "invalid" states that an attacker can easily probe.
- Attack Complexity: For standard vulnerable schemes, the attack complexity is remarkably low ($128n + \log_2(n)$), allowing for decryption in a matter of hours through automated querying.
Design Principles for Secure Padding
To mitigate these risks, the authors propose five "Golden Rules" for designing future padding schemes:
- Avoid Length Leakage: Do not include padding length information that can be manipulated.
- Content Independence: Padding should not reveal any information about the message content.
- Indistinguishable Modification: Ensure that modified padding cannot be easily detected by the oracle.
- Incorporate Randomness: Use Random Number Generators (RNGs) to increase the brute-force complexity for attackers.
- Eliminate Invalid States: The system should ideally not have a distinct "Invalid Padding" state.
Conclusion
While CBC mode remains prevalent, this study demonstrates that 75% of common padding techniques are unsafe against oracle attacks. Developers should prioritize the use of authenticated encryption or adopt the "Safe" padding methods identified in this research to ensure robust data protection. Future work will look toward developing secure padding methods that do not require the computational overhead of RNGs, which can be a bottleneck in high-speed environments.
Summary updated