How are side-channel attacks executed? What does an attacker need to execute a side channel attack?

Question

I've been reading about side-channel attacks on Wikipedia, and it seems that some of these can only be executed on the victim's computer. (I am specifically asking about the side-channel attacks listed on the Wikipedia page and any more that are theoretically possible)
What would an attacker need to execute each side channel attack?
How are side-channel attacks executed?

Answer 1

Here's a very simple timing side channel attack that you might even see in movies. Suppose you're trying to log in to a computer with a password, and the victim compares your password byte by byte but stops early if there's a mismatch:

for (i = 0; i < n; i++)
  if (password[i] != input[i])
    return EFAIL;

How do you attack this?

Try a password like aaaaaaa, and use a stopwatch to measure how long it takes; then try baaaaaa, caaaaaa, and so on, and whichever one takes the longest time—say haaaaaa—tells you what the first letter is.

Of course, there may be noise in the timings, so you may have to try each one several times and gather statistics to see the signal through the noise, or carefully arrange that input[i] is in an unmapped or uncached virtual page to amplify the signal of whether the comparison routine reached it.

Then repeat with hbaaaaa, hcaaaaa, etc., until you find huaaaaa; then hunaaaa; then huntaaa; until you've got the password.

How do you defend against such an attack? Standard countermeasures: rewrite the logic in constant time so that the time it takes is the same for all inputs, and/or judiciously randomize the problem so that any variation in the time is independent of the variation in inputs.

---

This is only one of many, many types of side channels. Here are a few other examples and roughly what you need to pull them off:

• The CRIME and BREACH exploits take advantage of the compression ratio as a side channel for secret content, namely HTTP cookies.

  If the software foolishly passes secrets through compression and reveals the resulting length, what you need is a JavaScript program to run in the user's browser to trigger HTTPS requests for some target site, and an eavesdropper on the network to watch them.

  (Most browsers don't do this kind of naive compression any more, because of such attacks!)

• Padding oracle attacks like Serge Vaudenay's exploit different types of error messages—padding error vs. authentication failure—as a side channel for secret content of messages.

  If the protocol is badly designed (like the original SSL protocol) and the software behaves differently for padding errors and authentication failures (like early SSL implementations), what you need is a MITM on the network who can intercept packets on the wire and modify them to see how the peer behaves.

  (Modern TLS no longer uses cryptosystems susceptible to padding mistakes like this, and modern implementations of older versions of TLS/SSL take extra effort to avoid padding oracles—but even the countermeasures sometimes admit other side channel attacks like Lucky Thirteen.)

• The Spectre class of attacks exploits side channels arising from timing of speculative execution in CPUs.

  If the CPU naively implements speculative execution like essentially all mass-market desktop, laptop, and server CPUs for the past two decades, and if the software doesn't have extensive countermeasures to thwart this class of attacks, what you need is a JavaScript program running in the browser with access to a reasonably high-resolution timer (which, with extra effort, can be simulated using a lower-resolution timer) to set up a Spectre gadget and measure it—and it works even if all the cryptography is safely implemented without side channels of its own like timing attacks below, because it works by using the CPU's speculative execution to reach into memory it shouldn't have access to at all.

  (Spectre is baaaaaaaaaaaad news.)

• Timing attacks on cryptosystems exploit computations with secret-dependent running times as a side channel for the secrets. There are many reasons computations might take secret-dependent time, a class of side channels reported in Kocher's seminal paper:

  1. When computing, e.g., the RSA private key operation $x^d \bmod n$ for secret $d$, it is tempting to use a standard square-and-multiply algorithm that checks $(d \mathbin\gg i) \mathbin\& 1$ to decide whether to multiply by $x$ or not at the $i^{\mathit{th}}$ step. CPUs are bad at keeping branch decisions secret in the first place; skipping a multiplication can changes the time even more substantially, which may reveal which bits of $d$ are set. What you need to exploit this is an automated system that responds to (say) encrypted queries, and a stopwatch.

  2. When computing, e.g., AES, it is tempting to use secret-dependent table lookups. CPUs are bad at keeping memory addresses secret—CPU caches are crucial for modern CPU performance, but also exploitable as a side channel. What you need to exploit this is a JavaScript program in a web browser that can trigger AES operations under the target key, say the power to trigger and measure disk encryption timing as Tromer, Osvik, and Shamir demonstrated (paywall-free).

  3. When checking whether an attacker-supplied message authentication code matches the legitimate message authentication code to verify a message or drop it as a forgery, a naive implementation might check the code byte-by-byte and stop early when it first mismatches: for (i = 0; i < n; i++) if (p[i] != q[i]) return EFAIL;. If the software does this, what you need is a MITM with a stopwatch to attempt forgeries and guess the correct MAC on a desired forgery byte-by-byte like hackers in movies figure out passwords letter-by-letter.

• The EFAIL attack exploits cryptographic flaws in OpenPGP and S/MIME to selectively modify encrypted email messages so that the recipient's mail reader will act on modified messages to just leak the secrets out directly. What you need to apply this is the dumpster fire of an implementation ecosystem that is OpenPGP and S/MIME.

  (That said, most OpenPGP implementations have now fixed the cryptographic flaw that enables this one.)

• Computers sometimes sound different depending on what operations they're performing and on what data, leading to acoustic cryptanalysis (paywall-free preprint). This may sound far-fetched because you need a sensor with physical proximity to the adversary…but people seem inexplicably excited to buy remote surveillance microphones from Apple, Amazon, and Google and put them in their homes! Alternatively, can you deliver a JavaScript program to a victim that turns on their computer's microphone?

This is not a comprehensive study of side channels. There are other entire classes of side channels like electromagnetic emissions or power analysis or active fault attacks. However, these are a little less compelling as a remote exploitation vector—power analysis (whether simple power analysis or differential power analysis) and fault attacks are most relevant to smart cards, for instance, where the adversary has physical access to the device to begin with.

This is not a comprehensive study of what you need in order to exploit side channels either. There may be countermeasures in place to make them harder. There may be noise that makes them harder. You might run out of patience trying to draft a proof of concept. I drafted a Meltdown exploit but ran out of patience with Spectre, when they were first released, or vice versa, I forget. It was a fun afternoon toy. But the side channels that you have the patience to practically exploit are only a tiny subset of the side channels that an adversary—with a market of off-the-shelf exploitation tools—is potentially able to take advantage of.

Answer 2

This is an attempt to an Explain to me like I'm five style answer:

Assume you have a bank vault with a mechanical combination lock. Your cipher in this case is "combination lock". At first sight it has two channels that the attacker can see and interface to The rotation on the input dial (an input channel) and the open/close status of the vault door (an output channel).

The correct combination to open the door (the secret key) is stored mechanically inside the vault lock, the attacker cannot see it from the outside. To find out the key, the attacker can try a guessed number (a candidate key) and see whether the door opens. When he tries all possible candidates on the lock, eventually he will find the correct combination. This would be a "brute-force" attack on the lock.

However the attacker noticed something: Depending on which number is set on the dial, he hears a faint "clunk" sound. He found an additional channel of information. It is an unintended channel, which is why this is called a side-channel. If it is an output side-channel it is also sometimes called "leakage".

What would an attacker need to execute each side-channel attack?

Multiple things:

• The attacker needs a reliable interface for this channel.
  • In the vault door lock example the attacker might use a stethoscope to get a better "reading" on the clunk-sound side-channel and to dampen other noise e.g. the ticking of a clock on the wall.
• The attacker also needs to know how to interpret the information, for output side-channels this is also called a leakage-model.
  • What does it mean when the attacker hears a clunk sound? How is a clunk sound different from a clank sound? How can he use this information to improve his key guess?
• Lastly the information that he gains from this additional side-channel should depend only on the parts of the secret key. If it depends on the whole key, it is not a win for the attacker because he still has to try all combinations.
  • Counterexample: If the "clunk" sound only occurs if the complete combination is correct, he could've only used the vault-door open/close status as an information channel.