This is text first appeared in the ISG Newsletter 2019/2020. I’ve added a bunch of links to this version.
RSA encryption with insecure padding (PKCS #1 v1.5) is a gift that keeps on giving variants of Bleichenbacher’s chosen ciphertext attack. As the readers of this newsletter will know, RSA-OAEP (PKCS #1 v2) is recommended for RSA encryption. How do we know, though, that switching to RSA-OAEP will give us an encryption scheme that resists chosen ciphertext attacks? Cryptography has two answers to this. Without any additional assumptions the answer is that we don’t know (yet). In the Random Oracle Model (ROM), though, we can give an affirmative answer, i.e. RSA-OAEP was proven secure. Indeed, security proofs in the ROM (and its cousin the Ideal Cipher Model) underpin many cryptographic constructions that are widely deployed, such as generic transforms to achieve security against active attacks and block cipher modes of operation. This article is meant to give some intuition about how such ROM proofs go by means of an analogy to dynamic malware analysis.