Illuminating Side Channel Attacks

Joshua Taylor

16 August 2022

A Riddle

Our CEO recently posed a riddle in a monthly newsletter. It’s an old classic, and it’s been republished in many places, and in several variations:

You’re in a room with three switches that control three lightbulbs in another room. You can’t see the light bulbs until you go into the other room, and once you go, you can’t come back to the switches. You can set the switches however you want. How can you figure out which bulb is controlled by each switch?

It’s worth spending some time to come up with a solution on your own if you haven’t encountered this riddle before. See if you can come up with a solution before peeking.

Is it a Trick Question?

I don’t think this is a really a trick question, and you didn’t need to ask about weird cases like:

• Is each light bulb controlled by exactly one of the switches?
• Are there any other lightbulbs in the other room?
• Do any switches control multiple light bulbs?
• Are we sure no one will come in and flip the switches when we leave the room?

It is reasonable to assume under the cooperative principle that the riddle as stated means what most people would probably mean if they said it. There’s no trick language. There are exactly three light bulbs, and extractly three switches, and each switch controls exactly one light bulb, and each light bulb is controlled by exactly on switch, and so on. Don’t worry too much about questions like those.

But some questions about built-in assumptions of the riddle are a bit harder to dismiss so easily. Folks who deal with edge cases on a regular basis (e.g., programmers, lawyers) might ask questions like:

• Do all the lightbulbs actually work?
  • It’s OK if you put this question into the first category. Maybe we should just assume that “yes, the lightbulbs work, because if you don’t know that, then you can’t really expect to interact with them using the switches.”
• Can we distinguish each switch’s on and off position?
  • This one isn’t all that far-fetched; a common 2-way toggle switch has on/off labels, but a 3-way switch is unlabeled, since either position could be on or off, depending on position of the other switch.
• Do we know the switches are initially in an off position?
  • This ties into the previous question: if we know all the switches are initially OFF, then it doesn’t matter whether ON looks different from OFF, since we can keep track of how many times we flip a switch.

Those questions feel more legitimate, but the simplest answers (“yes, the lightbulbs work”, “yes, you can tell whether the switch is on or off”) apply, so there’s still no real trickery.

About the Solution

The solution is clever and requires some out-of-the-box thinking. It’s satisfying, in part, because these kind of puzzles prime us to think about the logical structure of a problem domain, and they trigger our abstract reasoning, but the solution brings us back down into the physical reality of how a traditional, incandescent light bulb works in the physical world.

My first thoughts about the logical structure of the puzzle didn’t include the idea that timing delays (waiting between flipping switches, and before entering the other room) would be important. Nor did they include the fact that light bulbs get warm when they’ve been left on for a while. Those kinds of facts aren’t part of the my typical “light bulb user story.”(Although I do usually remember to let a light bulb cool off before I try to change it.)

There are other solutions out there that involve waiting a very long time (e.g., a few years) to let one bulb burn out (hopefully it’s not the Centennial Light), and then re-installing the other bulbs.

It’s interesting that those solutions, which seem to reach past the logical structure and out to the physical world, seems acceptable and clever, when other solutions that use the physical world like, “cut a hole in the wall so you can see the light bulbs,” don’t. There’s probably a whole sub-field within the study of riddles dedicated to describing which rules in a riddle can be broken.

What all of “acceptable” solutions seem to have in common, though, is that they depend upon the fact that most light bulbs generate noticeable amounts of heat and stay warm for some time even after they are switched off, and that they are in locations that are accessible enough to examine for heat once you’re in the other room (e.g., they’re not recessed lights in a vaulted ceiling). And yet, until the solution is revealed, questions like these don’t seem to come up:

• Are the light bulbs incandescent, florescent, or LEDs?
• Will the light bulbs be within reach for me once I’m in the other room?

The typical solution exploits a leaky abstraction around light bulbs. The purpose of a light bulb is to provide light, but it does that by heating a wire filament until it glows. Most of the time we don’t care about the fact that it’s a wire filament, or that it’s being heated. If it instead produced light by cooling a clay cube, it wouldn’t matter most of the time. Joel Spolsky coined the Law of Leaky Abstractions:

All non-trivial abstractions, to some degree, are leaky.

When a light bulb is working, whether it’s heating up usually doesn’t matter. But if you need to get close to it, that heat suddenly matters, and you can no longer ignore the abstraction that “light bulbs provide light”; you start to care about the difference between LEDs, CFLs, and traditional incandescent bulbs, even though they may all provide light equally well. (The costs to manufacture and operate different type of lighting is another hole where this abstraction leaks!)

But what happens when we, as we do in the light bulb puzzle, take advantage of a leaky abstraction?

Easy-Bake Ovens

The abstraction for a light bulb is “flip a switch, get light”, and one of the ways that abstraction leaks is heat. However, humans have plenty of uses for heat, too, so we can change our perspective a bit and call these devices “heat bulbs” that incidentally happen to emit light. That’s exactly how an Easy-Bake Oven works, for instance. (Current versions of the Easy-Bake Oven actually use a heating element rather than light bulbs.) Lava lamps make use of both features, using a light bulb to warm the wax inside the lamp and to provide light (otherwise, they wouldn’t really be lamps). So, it seems, the abstraction and its leaks are in the eye of the beholder.

Side Channel Attacks

When leaky abstractions are opportunistically used in a way that we don’t anticipate, or for undesireable purposes (for instance, information exfiltration), they become side channel attacks. There are many different types of side channel attacks, and they range from the very simple to understand (and exploit) to the very complex and difficult to detect.

The heat emitted by light bulbs is a physical property of how the light is generated, and provides information the past state of the system. Almost everyone has experience with hot light bulbs, so the riddle solution makes sense to just about everybody.

Some side channel attacks are just as simple to understand, but depend on the digital nature of computer architectures to be made practical. One classic example is a naive password checking routine along the lines of:

boolean checkPassword(char[] guess) {
  for( int i = 0, n = guess.length; i < n; i++ ) {
     if( guess[i] != realPassword[i] ) {
        return false;
     }
  }
  return true;
}

or, in English pseudo-code:

• Given a password guess with n characters for an n character password…
  • check whether the first character in the guess matches the first character in the real password
    • if they’re different report “wrong”
  • check whether the second character in the guess matches the second character in the real password
    • if they’re different, report “wrong”
  • continue until a mismatch is discovered, or else finally report “correct”

This routine iterates through the characters of guess, and returns false as soon as mismatch is encountered. While the routine (ignoring issues of bound checking) may satisfy the functional requirements in that returns true when the guess matches the real password and false when it doesn’t, this routine is vulnerable to a subtle timing attack. Because the routine terminates sooner for earlier mismatches, it is possible for an attacker who can observe how quickly the routine returns false to brute force the first letter, then the second, and so on.

Note that a human could follow the same process for checking a password guess against a known password, but the timing attack probably wouldn’t work against them, and certainly not with the same fidelity. There is simply too much variation in the amount of time that a human checker would take in comparing each letter.

There are many well known cyber-vulnerabilities to side channel attacks, such as 2017’s Meltdown, but side channel attacks affect the physical realm as well. For instance, Allied forces in WWII were able to more accurately predict the production capabilities of enemy forces based on side-channel information in the form of serial numbers following well-defined patterns. (This is now known as the German Tank Problem).

About All This

I’m Dr. Joshua Taylor, your host, and this blog will be evolving into a collection of thoughts and posts related to our cyber-security, research and development, software development, and more. I’ve been with Siege since 2011, working in software engineering, business development, internal R&D, and most recently, as Interim Chief Scientist. Over the past twenty years or so, I’ve been through an odyssey of computer science, logic-based and symbolic artificial intelligence, Semantic Web technology (RDF, OWL, SWRL, SPARQL), programming language development, category theory, software interoperability, with tangents into cognitive science, gardening, reverse engineering, and pipe organs along the way. Along with the rest of Siege, we hope this proves an interesting and informal outlet for what we’re up to. Enjoy!

Pique Your Interest?

Enjoy learning about and working on cyber-security? Approaching technology with the perspective that understanding how it works helps you understand how it breaks? You might be interested in getting to know Siege Technologies!