Safety Analysis of Various Padding Techniques on Padding Oracle Attack

Kimoon Kim, Myungseo Park, Jongsung Kim, Changhoon Lee, Dukjae Moon, Seok-Hee HongJournal of the Korea Institute of Information Security and Cryptology 2015 · DOI

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."

The interaction between a user and a padding 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.

CBC mode decryption process highlighting padding bytes in the final block.

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:

  1. Avoid Length Leakage: Do not include padding length information that can be manipulated.
  2. Content Independence: Padding should not reveal any information about the message content.
  3. Indistinguishable Modification: Ensure that modified padding cannot be easily detected by the oracle.
  4. Incorporate Randomness: Use Random Number Generators (RNGs) to increase the brute-force complexity for attackers.
  5. 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

Abstract

인터넷 뱅킹이나 전자상거래 같은 응용 환경에서 개인정보 및 민감한 정보를 보호하기 위해서 다양한 암호 알고리즘들을 사용한다. 하지만 안전성이 검증된 암호 알고리즘을 사용하여 중요 정보를 암호화 하더라도 운영모드, 패딩방법등 암호화를 적용하는 방법이 올바르지 못하면 암호화된 중요 정보들이 노출 된다는 연구결과와 방법들이 소개되고 있다. 이러한 공격방법 중 대표적인 사례가 패딩 오라클 공격(Padding Oracle Attack)이다. 본 논문에서는 블록암호의 CBC(Cipher Block Chainning) 운영모드에 적용 가능한 12가지 패딩방법에 대하여 패딩오라클 공격의 가능성을 분석하였다. 그 결과, 3가지의 안전한 패딩방법과 9가지의 안전하지 않은 패딩방법으로 분류할 수 있다. 3가지의 안전한 패딩방법 분석을 통해 패딩 오라클 공격에 내성을 가질 수 있도록 안전한 패딩방법 설계 시 고려해야 할 5가지 사항에 대하여 제안하고자 한다. We use various types of cryptographic algorithms for the protection of personal and sensitive informations in the application environments, such as an internet banking and an electronic commerce. However, recent researches were introduced that if we implement modes of operation, padding method and other cryptographic implementations in a wrong way, then the 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 of 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 a safe padding techniques to have a resistance to the padding oracle attack through the analysis of three kinds of safe padding techniques.
BibTeX
@article{kim2015safety,
  author = {Kimoon Kim and Myungseo Park and Jongsung Kim and Changhoon Lee and Dukjae Moon and Seok-Hee Hong},
  title = {{Safety Analysis of Various Padding Techniques on Padding Oracle Attack}},
  journal = {Journal of the Korea Institute of Information Security and Cryptology},
  year = {2015},
  doi = {10.13089/jkiisc.2015.25.2.271},
}
Figure