Lecture 16: Side-Channel Attacks

What this lecture covers

This lecture introduces side-channel attacks, the general problem of a system leaking secret information through a channel its designers never intended, such as timing, power draw, or sound, rather than through the data it explicitly transmits. It builds toward a detailed case study of the Brumley and Boneh timing attack, which extracts an RSA private key from an Apache web server by measuring microsecond differences in how long the server takes to reject malformed decryption requests.

The lecture follows the course's earlier treatment of RSA and certificates by going one level deeper into how RSA is actually implemented for performance, since the attack depends on details like the Chinese remainder theorem, sliding-window exponentiation, Montgomery multiplication, and Karatsuba multiplication. After watching, you should be able to explain why real-world cryptographic implementations, not just the underlying math, need to resist timing analysis, and describe how each optimization used by OpenSSL becomes an exploitable signal.

Key ideas

• Side channel: any information a system leaks outside its intended communication channel, such as RF emissions, power consumption, sound, or timing.
• Timing attacks favor small secrets: because extracting many bits through a noisy side channel is hard, these attacks typically target compact secrets like cryptographic keys rather than large datasets.
• RSA structure: keys are generated from two large primes p and q; encryption and decryption are modular exponentiation using a public exponent e and private exponent d, where recovering d requires knowing the factorization of n = p * q.
• Padding as an oracle: because the attack sends deliberately malformed ciphertexts, the server always rejects them after decrypting, and the time to reach that rejection reveals how the decryption pipeline behaved internally.
• Chinese Remainder Theorem (CRT): splits decryption mod n into two cheaper computations mod p and mod q, roughly doubling performance.
• Sliding windows and repeated squaring: precompute small powers of the ciphertext to reduce how often the server multiplies by it during exponentiation.
• Montgomery representation: avoids expensive modular division during repeated multiplication by keeping numbers in a transformed form, at the cost of occasional "extra reductions" whose frequency depends on how close the input is to q.
• Karatsuba vs. schoolbook multiplication: OpenSSL switches multiplication strategy depending on whether the two operands have the same bit-length, and that switch point is itself a timing signal.

Walkthrough

What side channels are (0:00)

The lecture opens by defining side channels broadly: situations where a system reveals information through an unintended channel rather than the data it explicitly sends. It gives historical and modern examples, including RF emissions from 1940s teletype machines, power usage patterns, and even the sound of dot-matrix printers, before introducing the day's focus: a timing side channel in RSA implementations.

RSA fundamentals (5:04)

Before attacking RSA, the lecture reviews how it works: generating a key from two large primes, encrypting by exponentiating a message to the public exponent e modulo n, and decrypting with a private exponent d. It explains why e * d must relate to Euler's totient function of n, and why keeping p and q secret is what keeps d unrecoverable.

RSA pitfalls and padding (13:15)

This section covers two properties of naive RSA that implementations must guard against: its multiplicative property, which lets an attacker construct a valid encryption of a product without knowing either factor, and its determinism, which lets an attacker distinguish messages by re-encrypting guesses. It introduces OAEP-style padding, which adds randomness and a fixed, checkable pattern, and explains that this padding check is exactly what the timing attack exploits, since a malformed ciphertext is rejected right after decryption finishes.

Speeding up modular exponentiation: CRT and sliding windows (20:24)

The lecture walks through the Chinese Remainder Theorem optimization, which splits a single large modular exponentiation into two smaller ones mod p and mod q for roughly a 2x speedup, and then sliding-window exponentiation, which precomputes small powers of the ciphertext so the server multiplies by the ciphertext far less often than naive repeated squaring would require.

Montgomery multiplication and extra reductions (34:39)

This is the technical core of the attack. The lecture explains why repeated modular reduction is expensive (division is much slower than multiplication), and how Montgomery representation avoids most of that cost by keeping numbers in a transformed form that only needs a cheap division by a power of two. The catch is that this cheap division can leave a result slightly larger than q, requiring an "extra reduction" step whose probability is proportional to how close the input is to q, a value the attacker does not know but is trying to guess.

Karatsuba multiplication and OpenSSL's switch point (53:04)

The lecture covers Karatsuba multiplication, which reduces the number of sub-multiplications needed to multiply two large numbers, and explains that OpenSSL dynamically chooses between Karatsuba and straightforward "schoolbook" multiplication depending on whether the operands have equal bit-length. This switch point becomes a second timing signal the attack can exploit.

Assembling the attack (1:00:13)

The lecture traces a client-crafted ciphertext through the full OpenSSL pipeline: CRT splitting, conversion to Montgomery form, sliding-window exponentiation with its extra reductions, and the Karatsuba/schoolbook choice, ending in a padding check that always fails and triggers a timed error response. It then explains the actual attack strategy: guessing the bits of the factor q one at a time by sending two carefully constructed guesses that should behave identically if a bit is 1, but differently (through either extra reductions or a multiplication-method switch) if the bit is 0. The lecture also describes practical tricks the original researchers used to make this work over a noisy real-world network, including repeating each guess several times and averaging over a small neighborhood of nearby values to cancel out unrelated timing noise.

Before you watch

• Review the course's earlier lecture on HTTPS/TLS and certificates, since the attack targets a TLS server's RSA decryption step.
• Basic familiarity with modular arithmetic and binary representations of numbers will make the exponentiation and Montgomery sections easier to follow.
• No side-channel background is assumed; the lecture builds the concept from scratch.

Check your understanding

1. Why does a timing side-channel attack typically target a small secret like a cryptographic key rather than a large block of data?
2. What role does message padding play in letting the attacker measure the server's internal computation time?
3. Why does converting numbers into Montgomery representation speed up repeated modular multiplication, and what cost does it introduce that becomes exploitable?
4. How does the attacker use two carefully chosen guess values (g and g_high) to determine a single unknown bit of the prime q?
5. Why did the researchers repeat each guess multiple times and vary it across a small neighborhood of nearby values, rather than sending the exact same guess repeatedly?