Cryptographic Security Proofs as Dynamic Malware Analysis

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.

The thought experiment in a typical (game-based) cryptographic proof starts by assuming that there is indeed an adversary that breaks the security goal of our cryptographic construction. For example, assume this adversary can decide if some message A or some message B was encrypted in ciphertext C. We are not even asking the adversary to decrypt C but we are merely asking it to decide which of two messages of its choosing we encrypted. If it cannot even do that, it cannot decrypt or learn anything about the underlying plaintext of a ciphertext. So this is the adversary’s goal: to distinguish. Next we need to decide what capabilities our hypothetical adversary has. Here, let’s consider chosen ciphertext security. The adversary gets to ask for decryptions of any ciphertexts it wants except for the “target” ciphertext C we are challenging it to make a distinguishing decision about. We are taunting the adversary: “We’re giving you the ability to decrypt anything you like except this one ciphertext but you still cannot decrypt it. In fact, we let you choose two messages A and B and we will encrypt one of them for you, you won’t even be able to decide which one we picked”; yep, cryptographers taunt algorithms. This is known as IND-CCA security in cryptography and the standard security notion aimed for and achieved by encryption schemes.

Now to illustrate how these proofs proceed, we will think of the adversary as a piece of malware. To analyse it we are going to put it in a sandbox just as we would do in dynamic analysis. We may then use our power over the sandbox to subject the adversary to various conditions and observe its behaviour. As a consequence, the first goal of such a cryptographic security proof is to show that we can simulate the “world” that our malware-née-adversary expects. Just like malware our adversary could decide to behave differently when it detects a simulation to avoid being analysed. In our setting the adversary expects two things – a Random Oracle and a decryption oracle – and we better simulate those (nearly) perfectly.

In this view, the ROM is Hashing-as-a-Service (HaaS). Instead of specifying a compact hash function like SHA2 with all details so that anyone can ship their own implementation, we are just going to define some API with a single calling point H(): put some string in, receive a digest back, e.g. y=H(x). In the ROM, our HaaS also realises a perfect hash function: for each fresh input x it returns a completely random digest y (of course, if we call H() again on the same x we get the same y just as we would expect from a hash function), so the only way to know the output y is to call H(x) via our API. So what we have is something “random” (perfectly random output) from an “oracle” (we can only call the API). This is somewhat similar in spirit to ransomware countermeasures that intercept calls to the cryptographic API provided by the OS. The difference is that ransomware may implement and ship its own cryptography, but in our thought experiment the only way to get access to H() is via our API. Another practical analogy would be HMAC with a secret key running on an HSM, something Facebook is using for password hashing.

Returning to our proof sketch, we want to show that the ability to decrypt every ciphertext except C does not buy the adversary anything. We can accomplish this in the ROM by making our construction dependent on our API s.t. the only way to produce a valid ciphertext is to call H() on the message (and any other randomness used during encryption), everything else produces an error on decryption. When we accomplish this (which isn’t too hard) then the adversary has two choices: it can submit whatever it wants for decryption which will just produce an error or it can dutifully call H() via our API when producing a ciphertext. The key observation now is that in the latter case it sends us the message (and associated randomness) it might ask us to decrypt later. So we can easily provide plaintexts in response to correctly formed ciphertexts: we are cheating and know the answers before seeing the question.

From this we can conclude that if there was an adversary against our scheme that requires a decryption oracle we can run this adversary against our scheme without actually having access to such a decryption oracle (by simulating it using the information the adversary helpfully sends us via calls to H()). This implies that CCA attacks, i.e. active attacks – in the ROM and for schemes where such proofs exists –, are no more powerful than CPA attacks, i.e. passive attacks. To drive home this point, this is not a claim that we prevent the adversary from running specific attack strategies but it rules out any attack using such a decryption oracle. If we can fake it, it offers no advantage.

HaaS/the ROM is an incredibly powerful tool for proving security. Once we have HaaS we can play all kinds of tricks with the adversary. For example, we can start cheating and send specifically chosen answers in response to strategically chosen queries. When H() is used to check the integrity of some input x against some known digest y we can simply make our API return y on input x or z, it is up to us. This is known as “programming the Random Oracle”. An analogy from dynamic analysis could be to provide bad randomness to a piece of malware to break its encryption or to return incorrect time/date information from a system call to trigger some behaviour. Another trick we can play is to restart our VM from a snapshot which is known as “rewinding”. For example, we may choose to rewind the sandbox with the adversary to some point in the past and then provide different responses from our random oracle to provoke a fork in the malware: it started out doing the same but then at some point it performs different steps. The lemma proving that this makes sense in cryptographic security proofs is aptly called the “forking lemma”.

The ROM isn’t without its problems. For starters, HaaS isn’t how we use hash functions, we actually implement them in code. Indeed, there are (arguably contrived) counter examples of cryptographic schemes that can be proven secure in the ROM but are insecure when used with any real hash function. Secondly, when we worry about quantum computers we also need to worry about hash functions being implemented on them. To account for this we would need to define quantum Hashing-as-a-Service where the adversary can send superposition queries and receive a superposition of digests back. In such a setting, the “looking up the plaintext for a ciphertext from previous hash queries” trick doesn’t work any longer. Reproving cryptographic schemes in the Quantum Random Oracle Model (QROM) is an ongoing research endeavour.