Buckle 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.
