Abstract
This paper presents a new type of powerful cryptanalytic attacks on public-key cryptosystems, extending the more commonly studied adaptive chosen-ciphertext attacks. In the new attacks, an adversary is not only allowed to submit to a decryption oracle (valid or invalid) ciphertexts of her choice, but also to emit a “dump query” prior to the completion of a decryption operation. The dump query returns intermediate results that have not been erased in the course of the decryption operation, whereby allowing the adversary to gain vital advantages in breaking the cryptosystem.
We believe that the new attack model approximates more closely existing security systems. We examine its power by demonstrating that most existing public-key cryptosystems, including OAEP-RSA, are vulnerable to our extended attacks.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Baek, B. Lee, and K. Kim, “Secure length-saving ElGamal encryption under the computational Diffie-Hellman assumption”, Information Security and Privacy (ACISP 2000), volume 1841 of Lecture Notes in Computer Science, pages 49–58, Springer-Verlag, 2000.
M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway, “Relations among notions of security for public-key encryption schemes”, Advances in Cryptology —CRYPTO’98, volume 1462 of Lecture Notes in Computer Science, pages 26–45, Springer-Verlag, 1998.
M. Bellare and P. Rogaway, “Random oracles are practical: A paradigm for designing efficient protocols”, First ACM Conference on Computer and Communications Security, pages 62–73, ACM Press, 1993.
M. Bellare and P. Rogaway, “Optimal asymmetric encryption”, Advances in Cryptology — EUROCRYPT’94, volume 950 of Lecture Notes in Computer Science, pages 92–111, Springer-Verlag, 1995.
D. Bleichenbacher, “A chosen ciphertext attack against protocols based on the RSA encryption standard PKCS #1”, Advances in Cryptology — CRYPTO’98, volume 1462 of Lecture Notes in Computer Science, pages 1–12, Springer-Verlag, 1998.
S. Burnett and S. Paine, “RSA Security’s official guide to cryptography”, RSA Press, 2001.
D. Campbell “How your privacy is caught in the Net”, http://www.theage.com.au/daily/990808/news/specials/news1.html, 8 August 1999.
R. Cramer and V. Shoup, “A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack”, Advances in Cryptology — CRYPTO’ 98, volume 1462 of Lecture Notes in Computer Science, pages 13–25, Springer-Verlag, 1998.
O. Dolev, C. Dwork, and M. Naor, “Non-malleable cryptography”, 23rd ACM Annual Symposium on the Theory of Computing, pages 542–552, ACM Press, 1991.
T. ElGamal, “A public key cryptosystems and a signature schemes based on discrete logarithms”, IEEE Transactions on Information Theory, IT-31(4):469–472, 1985.
E. Fujisaki and T. Okamoto, “How to enhance the security of public-key encryption at minimum cost”, Public Key Cryptography, volume 1560 of Lecture Notes in Computer Science, pages 53–68, Springer-Verlag, 1999.
E. Fujisaki and T. Okamoto, “Secure integration of asymmetric and symmetric encryption schemes”, Advances in Cryptology — CRYPTO’99, volume 1666 of Lecture Notes in Computer Science, pages 537–544, Springer-Verlag, 1999.
S. Goldwasser and S. Micali, “Probabilistic encryption”, Journal of Computer and System Sciences, 28:270–299, 1984.
G. Itkis and L. Reyzin, “Forward-secure signatures with optimal signing and verifying”, Advances in Cryptology — CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, pages 332–354, Springer-Verlag, 2001.
M. Joye, J.-J. Quisquater, and M. Yung, “On the power of misbehaving adversaries”, Topics in Cryptology — CT-RSA 2001, volume 2020 of Lecture Notes in Computer Science, pages 208–222, Springer-Verlag, 2001.
J. Manger, “A chosen ciphertext attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as standardized in PKCS #1”, Advances in Cryptology —CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, pages 230–238, Springer-Verlag, 2001.
M. Naor and M. Yung, “Public-key cryptosystems provably secure against chosen ciphertext attacks”, 22nd Annual ACM Symposium on Theory of Computing, pages 427–437, ACM Press, 1990.
T. Okamoto and D. Pointcheval, “REACT: Rapid enhanced-security asymmetric cryptosystem transform”, Topics in Cryptology — CT-RSA 2001, volume 2020 of Lecture Notes in Computer Science, pages 159–175, Springer-Verlag, 2001.
D. Pointcheval, “Chosen-ciphertext security for any one-way cryptosystem”, Public Key Cryptography, volume 1751 of Lecture Notes in Computer Science, pages 129–146, Springer-Verlag, 2000.
C. Racko. and D. Simon, “Noninteractive zero-knowledge proof of knowledge and chosen ciphertext attack”, Advances in Cryptology — CRYPTO’91, volume 576 of Lecture Notes in Computer Science, pages 433–444, Springer-Verlag, 1992.
R.L. Rivest, A. Shamir, and L.M. Adleman, “A method for obtaining digital signatures and public-key cryptosystems”, Communications of the ACM, 21(2):120–126, 1978.
C.P. Schnorr and M. Jakobsson, “Security of Signed ElGamal Encryption”, Advances in Cryptology — ASIACRYPT 2000, volume 1976 of Lecture Notes in Computer Science, pages 73–89, Springer-Verlag, 2000.
V. Shoup, “On formal models for secure key exchange”, version 4, Revision of IBM Research Report RZ 3120(April 1999), November 15, 1999.
V. Shoup and R. Gennaro, “Securing threshold cryptosystems against chosen ciphertext attack”, Advances in Cryptology — EUROCRYPT’98, volume 1403 of Lecture Notes in Computer Science, pages 1–16, Springer-Verlag, 1998.
A. Silberschatz, J. Peterson, and P. Galvin, Operating system concepts, Third edition, Addison-Wesley Publishing Company.
Y. Tsiounis and M. Yung, “On the security of ElGamal-based encryption”, Public Key Cryptography, volume 1431 of Lecture Notes in Computer Science, pages 117–134, Springer-Verlag, 1998.
Y. Zheng and J. Seberry, “Immunizing public key cryptosystems against chosen ciphertext attacks”, IEEE Journal on Selected Area in Communications, 11(5):715–724, 1993.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kim, S. et al. (2001). Strong Adaptive Chosen-Ciphertext Attacks with Memory Dump (or: The Importance of the Order of Decryption and Validation). In: Honary, B. (eds) Cryptography and Coding. Cryptography and Coding 2001. Lecture Notes in Computer Science, vol 2260. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45325-3_11
Download citation
DOI: https://doi.org/10.1007/3-540-45325-3_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43026-1
Online ISBN: 978-3-540-45325-3
eBook Packages: Springer Book Archive