Strong Adaptive Chosen-Ciphertext Attacks with Memory Dump (or: The Importance of the Order of Decryption and Validation)

Seungjoo Kim, Jung Hee Cheon, Marc Joye, Seongan Lim, Masahiro Mambo, Dongho Won, Yuliang ZhengIMACC 2001 · DOI

TL;DR

This paper introduces a new, more powerful attack model called "strong adaptive chosen-ciphertext attacks" that includes the ability to "dump" intermediate decryption states. They demonstrate that many existing public-key encryption schemes, including OAEP-RSA and some ElGamal variants, are vulnerable to this new attack, highlighting a critical flaw in "decrypt-then-validate" schemes.

What Problem Does This Paper Address?

The paper tackles the problem of ensuring the security of public-key encryption schemes against increasingly sophisticated adversaries. While the standard security notion for these schemes is "indistinguishability under adaptive chosen-ciphertext attacks" (IND-CCA2), this model has limitations. The authors argue that existing security systems, particularly those running on common operating systems like Unix and Windows, allow for more intrusive attacks. Specifically, they point out that the order of decryption and validation in many schemes is crucial, and an adversary might exploit the time between these operations to gain an advantage. They aim to define a stronger security model that better reflects real-world attack capabilities and to show which existing schemes fail under this new model.

Methods

The core contribution is the introduction of a new adversarial model: strong adaptive chosen-ciphertext attacks with memory dump. In this model, an adversary not only has access to a decryption oracle (as in standard adaptive chosen-ciphertext attacks) but can also issue a "dump query" at any point during the decryption process. This dump query reveals intermediate states of the decryption operation that haven't been erased, providing the adversary with potentially valuable information.

The authors then analyze the security of various public-key encryption schemes against this new model. They categorize chosen-ciphertext attacks into static and adaptive, and then extend these to the "strong" version by incorporating the memory dump capability. The analysis focuses on "decrypt-then-validate" type schemes, where decryption is performed first, and then the ciphertext's validity is checked. They demonstrate that by performing a dump query after the raw decryption but before the validation check, an adversary can extract crucial intermediate information that weakens the scheme.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The "dump query" is a game-changer: The ability to inspect intermediate decryption states, even if secret keys are inaccessible, significantly enhances an adversary's power.
  • Order matters: Decrypt-then-validate is vulnerable: Schemes that perform decryption before validating the ciphertext are particularly susceptible. An adversary can exploit the window between these two operations to extract information from the decryption's intermediate results.
  • Real-world systems are more vulnerable than models suggest: The authors argue that their model better reflects the capabilities of attackers on modern operating systems, where memory inspection is more feasible.
  • "Atomic actions" are key to defense: To resist these attacks, operations that use secret keys or are critical for validation must be performed atomically, meaning they cannot be interrupted to allow for a dump query.
  • Not all schemes are equally vulnerable: While many "decrypt-then-validate" schemes are broken, "validate-then-decrypt" schemes appear more robust against this specific attack.

Key Results

The paper demonstrates that several well-known and provably secure encryption schemes, including OAEP-RSA and various ElGamal variants (specifically those that follow a "decrypt-then-validate" paradigm), are insecure under the strong adaptive chosen-ciphertext attack model. They provide concrete examples of how an adversary can exploit the memory dump capability to recover plaintext information or gain other advantages. The paper also includes a table summarizing the analysis of several ElGamal variants, categorizing them by their validation/decryption order and indicating their susceptibility to the attack.

Limitations and Future Work

The authors acknowledge that they did not prove the security of all schemes they analyzed, particularly a modified Baek, Lee, and Kim scheme. They suggest that future work should focus on designing cryptosystems that are provably secure within this stronger attack model. They also propose that the amount of computation within an "atomic action" could be considered a security evaluation criterion. Furthermore, they suggest that the scope of their attacks might extend to other cryptographic primitives like digital signatures.

Summary updated

BibTeX
@inproceedings{kim2001strong,
  author = {Seungjoo Kim and Jung Hee Cheon and Marc Joye and Seongan Lim and Masahiro Mambo and Dongho Won and Yuliang Zheng},
  title = {{Strong Adaptive Chosen-Ciphertext Attacks with Memory Dump (or: The Importance of the Order of Decryption and Validation)}},
  booktitle = {IMACC},
  year = {2001},
  doi = {10.1007/3-540-45325-3\_11},
}
Figure