editor's blog
Subscribe Now

Through-The-Looking-Glass Security

Aliceroom3.jpgBuckle up folks, because we’re about to take a ride through the looking glass, where computations can happen in an obscure way sure to confuse unauthorized snoops, until we arrive at an answer and can pop back through the glass into our normal world.

It’s become a truism that using hardware for security is best. But what if that’s not an option? Doing calculations and manipulations of keys and secrets out in the open is a foolish business. You could opt for a trusted execution platform, but, to date, that’s not a common feature of Internet of Things (IoT) edge nodes.

So if you have to do it out in the open, the least you can do is try to disguise what it is that you’re doing so that anyone watching will have a hard time pulling apart layers of diversions and head-fakes to figure out what’s really going on underneath – and, in particular, what numbers mean what. (Like the key.)

It’s called obfuscation. It’s also called whitebox computing, because, unlike the opaque approach taken by TPMs and SEs and their ilk, here the computations are done in full daylight. In other words, if you can’t use an approach where no one can see, then might as well optimize your approach assuming everyone can see. They can see, but can they figure out what’s going on? That’s the trick.

I’ll attempt to walk through what I’ve learned about it, with special thanks to Microsemi’s Dr. Scott Miller. He managed to squeeze the basic notions through my thick skull; what follows is my retelling of those points while they’re still warm in my brain. No fair quizzing me a week from now.

Alternate realities

It very much reminds me of the Laplace transform we learned back in undergrad classes (and which I’ve never, ever, not even once used since – but I guess the notion is paying off now). In that case, there are mathematical functions like convolutions that are messy to do – unless you transform into the s-plane, in which case they’re done as multiplication. You convert back down once you have your answer. Here, the s-plane resides behind the looking glass.

Obfuscation is similar, but not for purposes of simplifying calculations. If anything, this will make them seem more complicated. It relies on isomorphic algebraic fields – two very different-looking fields could have the same form, with one feeling natural and the other not. You could have a field of integers and remap the integers to colors. As long as you capture a table that defines the arithmetic rules so that you know how to add blue to yellow, you can do everything as colors and only map back to numbers when you’re done.

In case you’re thinking, “Well, that’s not so hard,” it’s just the concept; it’s not an actual example of what they do because, yeah, it’s not so hard. Instead, as one example, we’ll enter the world of Rijndael fields. There’s some theory behind them that I’m not going to get into, but because it’s a modulus 2 field, addition and subtraction are the same, and they’re implemented by the XOR function. It’s a relevant example because, with AES encryption, each byte of the message and the key can be interpreted as a Rijndael field element.

So normal multiplication and division would be done using shift and add/subtract algorithms. Which someone snooping could recognize and say, “Aha! And that bit there’s the key!” Which we’re trying to avoid. So instead, the same functions are done a completely different way that involves no shift/add operations.

There are a few steps to the process, and honestly, I had to think hard about this before it started getting clearer in my mind. Let’s just start with the “pure” math part. Imagine a sphere, and from the origin comes a unit-length vector a = (0,1,1). We’re going to use this as an axis of rotation: picture a vector orthogonal to a and spin that vector around a. Since we’re talking modulo math here, we always come back on ourselves once we hit the modulus. It’s just like this circle; if you rotate far enough, you come back on yourself.

We can use this to implement addition. If we have a 255-element field (that is, modulo 256), then we can divide up our circle into 255 mini-rotations. From some starting point, if we want to add 1, we rotate by 2π/255. If we want to add 20, we rotate by 2π20/255.

So why do we want this addition? We’re trying to do multiplication in a way that doesn’t look like shift/add. We need a way to make multiplication look like addition. So we need some more abstract algebra first.

With these fields, the “multiplicative group” is “cyclic.” Let’s break that down. The “multiplicative group” is the entire field minus the addition identity. So, given the modulus 3 group (0,1,2), the addition identity is 0, so the multiplicative group is (1,2).

“Cyclic” means that one of the members of the field can be used as a “generator” such that raising it to different powers (that are also members of the field – no fair tossing irrational numbers into this integer math), you can generate all of the members of the multiplicative group. In the example above, the generator is 2, since 20=1 and 21=2. For different groups, you might have to – in the worst case – do a member-by-member test to figure out which one is the generator, but you will find it.

So that means that each member of the field can be expressed as gn, where g is the generator. That means that multiplication of two numbers x = ga and y = gb is xy = ga*gb = g (a+b). In other words, as long as we know g, then we can do the additions instead. We’re now operating in the exponent space, through the looking glass.

And now we can use those rotations to do this addition: to add a and b, we select the vector for a, rotate it by an amount corresponding to b, and we have our answer. Using the numbers above, multiplying g3 and g5 means taking the vector at 2π3/255 and rotating it 2π5/255, which would place it at 2π8/255. And our answer would be g8.

Hide in plain sight

Of course, to manage this mapping between numbers and rotations, we need a couple of tables. One table is for the first operand, giving its position. The second table is the rotation needed to implement the second operand. (Because they’re both rotating about the same axis, we’ve preserved commutativity.) But an easy-to-read lookup table will also be easy for a snoop to read.

So there’s another trick that’s used: the table entries are scattered out into a much larger table, most of which is filled with what I call “chaff” – fake numbers that look plausible, but are just there to distract and confuse an attacker. You will have some function that directs the mapping of the legitimate numbers in the sea of fakes, but if no one can find that mapping, it makes it very hard to look at the matrix – if big enough – and figure out where the real entries are.

Of course, you have one table for the first operand’s positions and another table for the second operand’s rotations – and they could have different mappings, making things yet harder to decode.

OK, so we’ve taken our original numbers, figured out the generator and exponents, and then mapped the numbers to table entries representing the rotations of their exponents, hidden amongst lots of other meaningless distracting table entries. We did our math and got a result. In the simplest of cases, we can now unmap to find our answer.

But simply reversing the original mapping would be too easy, right? No, can’t do that – it would help provide clues to the mapping. Turns out that there’s a different way to unmap. For tables of size 2000, for example, with mod 256 fields, you would take your rotation addition result v, along with a mysterious vector m, which equals (1/√3, -1/√3, 1/√3), and find a result x as x = 635cos-1(v*m). Obvious, right?

No, not obvious. And that’s the point. And it’s something of an empirical thing; the initial mapping and hiding in the chaff need to be done in a way that makes something like this work.

Of course, if you have more calculations to do, then you can feed the still-mapped result into the next calculations (as long as they know that they’re getting a behind-the-looking-glass number), and those next steps can carry on the obfuscation, reducing to a final result farther down the road. In other words, stay behind the looking glass for as long as you can before popping back out at the end.

So that’s the essence of it. Note that with respect to the Laplace analogy, there’s one Laplace transform: you use it to go in and out of the s-plane. But with obfuscation, part of the strength is that there are a huge number of possible ways to obfuscate, and they can be combined and layered. We already saw that you can use different mappings for different operands (just don’t lose track!).

When doing AES encryption, for example, each output byte of a single round (AES involves multiple rounds of encryption operations) involves four different multiplications. You could map each of those four multiplications differently. The number of combinations and permutations of these mappings sets a high barrier for some attacker trying to unravel the whole thing.

With that in mind, it also bears noting that this example involving rotations is apparently too compute-intensive for actual use, but it serves to illustrate the point. Which is probably convenient for Microsemi, since they can illustrate how this works without giving away the obfuscations that they actually use.

Leave a Reply

featured blogs
Sep 25, 2020
What do you think about earphone-style electroencephalography sensors that would allow your boss to monitor your brainwaves and collect your brain data while you are at work?...
Sep 25, 2020
Weird weather is one the things making 2020 memorable. As I look my home office window (WFH – yet another 2020 “thing”!), it feels like mid-summer in late September. In some places like Key West or Palm Springs, that is normal. In Pennsylvania, it is not. My...
Sep 25, 2020
[From the last episode: We looked at different ways of accessing a single bit in a memory, including the use of multiplexors.] Today we'€™re going to look more specifically at memory cells '€“ these things we'€™ve been calling bit cells. We mentioned that there are many...
Sep 25, 2020
Normally, in May, I'd have been off to Unterschleißheim, a suburb of Munich where historically we've held what used to be called CDNLive EMEA. We renamed this CadenceLIVE Europe and... [[ Click on the title to access the full blog on the Cadence Community site...

Featured Video

Texas Instruments: Pushing Power Further

Sponsored by Texas Instruments

Power is all around us. Every connection, every invention begins with power. Watch this short video to see how we are pushing the limits of power management.

Explore our power density portfolio

Featured Paper

Helping physicians achieve faster, more accurate patient diagnoses with molecular test technology

Sponsored by Texas Instruments

Point-of-care molecular diagnostics (PoC) help physicians achieve faster, more accurate patient diagnoses and treatment decisions. This article breaks down how molecular test technology works and the building blocks for a PoC molecular diagnostics analyzer sensor front end system.

Read the Article

Featured Chalk Talk

Thermal Management Solutions

Sponsored by Mouser Electronics and Panasonic

With shrinking form factors, tighter power budgets, and higher performance, thermal management can be a challenge in today’s designs. It might be time to bust out the thermal grease to help conduct away some of that excess heat. But, before you grab that tube, check out this episode of Chalk Talk where Amelia Dalton chats with Len Metzger of Panasonic about the details, drawbacks, and design considerations when using thermal grease - and its alternatives.

Click here for more information about Panasonic Thermal Management Solutions