In this work, we formulate a practical ASA on PKE encryption algorithm which, perhaps surprisingly, turns out to be much more efficient and robust than existing ones, showing that ASAs on PKE schemes are far more effective and dangerous than previously believed. We mainly target PKE of hybrid encryption which is the most prevalent way to employ PKE in the literature and in practice. The main strategy of our ASA is to subvert the underlying key encapsulation mechanism (KEM) so that the session key encapsulated could be efficiently extracted, which, in turn, breaks the data encapsulation mechanism (DEM) enabling us to learn the plaintext itself. Concretely, our non-black-box yet quite general attack enables recovering the plaintext from only two successive ciphertexts and minimally depends on a short state of previous internal randomness. A widely used class of KEMs is shown to be subvertible by our powerful attack.
Our attack relies on a novel identification and formalization of certain properties that yield practical ASAs on KEMs. More broadly, it points at and may shed some light on exploring structural weaknesses of other ``composed cryptographic primitives,'' which may make them susceptible to more dangerous ASAs with effectiveness that surpasses the known logarithmic upper bound (i.e., reviewing composition as an attack enabler).
Category / Keywords: public-key cryptography / Algorithm-substitution attacks, public-key encryption, key encapsulation mechanism Original Publication (with minor differences): IACR-ASIACRYPT-2020 Date: received 7 Sep 2020 Contact author: chromao at nudt edu cn Available format(s): PDF | BibTeX Citation Note: A preliminary version of this paper appears at Asiacrypt 2020. This is the full version with more detailed discussions on the countermeasures and ASA on hybrid encryption. Version: 20200909:064650 (All versions of this report) Short URL: ia.cr/2020/1079