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
Jul 6, 2020
If you were in the possession of one of these bodacious beauties, what sorts of games and effects would you create using the little scamp?...
Jul 3, 2020
[From the last episode: We looked at CNNs for vision as well as other neural networks for other applications.] We'€™re going to take a quick detour into math today. For those of you that have done advanced math, this may be a review, or it might even seem to be talking down...
Jul 2, 2020
In June, we continued to upgrade several key pieces of content across the website, including more interactive product explorers on several pages and a homepage refresh. We also made a significant update to our product pages which allows logged-in users to see customer-specifi...

Featured Video

Product Update: New DesignWare® IOs

Sponsored by Synopsys

Join Faisal Goriawalla for an update on Synopsys’ DesignWare GPIO and Specialty IO IP, including LVDS, I2C and I3C. The IO portfolio is silicon-proven across a range of foundries and process nodes, and is ready for your next SoC design.

Click here for more information about DesignWare Embedded Memories, Logic Libraries and Test Videos

Featured Paper

Cryptography: A Closer Look at the Algorithms

Sponsored by Maxim Integrated

Get more details about how cryptographic algorithms are implemented and how an asymmetric key algorithm can be used to exchange a shared private key.

Click here to download the whitepaper

Featured Chalk Talk

Power Supply Design

Sponsored by Mouser Electronics and KEMET

There is a bewildering range of choices for components for power supply design. Considering EMI protection, surge protection, transformers, rectifiers - the list goes on and on. In this episode of Chalk Talk, Amelia Dalton chats with Nick Stephen of KEMET to sort out the puzzle of power supply component selection, and to look at the latest trends and best practices in power supply design.

Click here for more information about KEMET Electronics METCOM MPX1 Metal Composite Power Inductors