IoT’s Key-storage conundrum and WhiteBox crypto — Part 1

The messed up world of ‘on-device’ crypto-keys.

If you’ve ever dabbled with ‘cryptography in a constrained (IoT) environment’, you may have come up against an old foe — the question of

Where do I store my crypto keys?

or more precisely, where do we store the pre-shared key (or a private key in the case of asymmetric crypto)?

Examples of areas where this problem pops up -

• IoT device authentication: Where do we store the associated private key of an embedded X.509 digital certificate used to authenticate the device?
• Securing intellectual property: Where do we store the symmetric key used to protect/encrypt intellectual property (Say device firmware)?

In both cases, we need a way to securely store the key on (or off) the device.

So, what are our storage options?

1. Use a hardware store: HSMs, UICC, e-Secure element, smart cards etc.
2. Use a software store: some form of custom code obfuscation technique to conceal the key in the implementation. Note: Full-fledged key-stores aren’t an option for constrained/embedded environments.
3. *Or a hybrid option: some custom key-sharing option where the key is stored on an access-controlled remote server.

All the above options have their pros and cons -

1. Hardware: Probably the most secure option (of them all) but not always a workable one — given cost, integration expertise and maintenance concerns.
2. Software: its obfuscation, a skilled attacker can de-obfuscate it but it could require considerable effort depending on the technique used.
3. Hybrid: we rely on the strength of the authentication mechanism and a trusted 3rd party to vet the remote server. This one’s actually more work considering existing ‘trusted 3rd party systems’ like PKI in-turn rely on CAs and private key security.

But the interesting thing is that more often than not, the preferable solution is a ‘software-store’ for a bunch of different reasons- cost, expertise required, ease of integration, update-ability etc. This begs the question — if it’s the most popular option, then

How secure is it really?

The best way to figure this out would be to explore just how easy it is to extract/recover the secret key from an obfuscated asset. To do this — Let’s start by going over possible attack models/approaches. Technically speaking, any one of these could help us recover the key.

BlackBox model: an attacker has access to inputs and outputs i.e. he can observe/record all plaintext and ciphertext messages

GreyBox model: an attacker has access to inputs, outputs, and some additional data. For Ex: side-channel information such as how much power is being consumed during an encryption operation.

WhiteBox model: an attacker has full access to the target binary and its execution environment. Essentially this means that an attacker can leverage any number of tools or techniques for reverse engineering..like a disassembler to statically reverse engineer the binary or attach a debugger and step through its instructions or read/set/modify registers. Simply put, this model is akin to an attacker’s paradise.

In general, key-recovery attacks against BlackBoxes/GreyBoxes exist but they usually require more effort and in some cases significantly more resources. A BlackBox attack could involve someone like the NSA who spends a ton of cash to collect and store large caches of ciphertext only to decrypt it when a new zero-day exploit (Ex: Heartbleed) is available. A GreyBox attack could mean a hacker who has access to some specialized hardware such as an oscilloscope (at the very least) and knows his way around hardware i.e. about things like bus lines, resistors, level converters etc.

In contrast- attacking a software-store in the WhiteBox model is like child’s play (well, comparatively at least) as you already have full access to the binary and its execution environment.

At this point you realize that in a WhiteBox model, you’re only defense is the implementation itself.

P.s not really — just don’t store the key at all… more on that in another post.

But how do we make the implementation defend itself?

Amongst the many code-obfuscation, anti-tampering solutions out there — a really interesting option is WhiteBox cryptography, a form of software obfuscation (its not really code obfuscation) where instead of obfuscating the actual program code, we modify/alter the underlying implementation of the cryptographic algorithm (such as AES/DES) used for encryption.

Essentially we re-implement our crypto-algorithm as a sequence of obfuscated lookup tables with the secret key embedded in these lookup tables.

For instance, let’s pick AES-128 and walk through the process of white-boxing it. I’m more of a visual person — a visual description of AES is more intuitive than a series of mathematical equations. Let’s use some pictures to simplify AES.

AES-128 basics:

It is a block cipher, takes its input (i.e. plaintext and the corresponding symmetric key) as a block of 16 bytes each and spits out a 16-byte block of ciphertext.

A 16 byte block of plaintext and a 16 byte block of the symmetric key.

This input is looped through a sequence of 4 different transformation operations (multiple times) to produce the final block of ciphertext. The sequence of the 4 types of transformations are

The sequence of the 4 types of transformations in AES

The order and the number of times we loop through these transformations is important. We’re talking about 11 rounds in total. It looks sort of like this

• 1 initial round
• 9 main rounds
• 1 final round

AES in a nutshell

Now let’s break it down.

SubBytes — this operation is just a lookup table. For Ex: if we lookup ‘19’ (the first byte of the initial state) in the S-Box table, we get ‘d4’. Essentially we’re substituting 1 byte of input with that of another byte of S-Box output

S-Box is essentially a look-up table (but you can design complex ones)

Shiftrows — as the name implies, this operation shift bytes in a row. Bytes from the previous output are left shifted by

• 1 byte in the second row,
• 2 bytes in the third row
• Finally 3 bytes in the last one.

Shifted bytes

Mixcolumns — This one’s matrix multiplication. Essentially each column of input (four bytes) on the left is from the previous state. This is multiplied with a fixed 4x4 matrix.

The slightly more complex step in AES — matrix multiplication

AddRoundkey — This one’s just a simple XOR operation. 16 bytes of the round key is XORed with the previous output. Note: Round-keys are derived from the actual key (in blue below) through a process called key expansion.

Summing up — A 10 round operation looks something like this

All 10 rounds in AES. The last round is a little different, doesn’t include Mix-Columns

Great! we have a better understanding of AES, so where does WhiteBox crypto come in. If you think about it, all transformation operations are deterministic and can be replaced with a lookup table.

AES with look-up tables:

Instead of 4 different operations per round, we can merge the AddRoundkey (i.e. key addition), S-box (and Shift-rows*) operations into a single operation. For a given round, we pre-compute a table of values i.e. the result of XORing every possible byte of input with that of each of the 16 bytes in the round-key. (that’s 256*16 bytes per round per table)

Merge AddRoundkey and S-Box steps. *Shiftrows is just re-ordered

We can have a similar table for the MixCoulmns step. This means we can now implement a single round with just 2 lookup tables. (the end result is a network of look-up tables)

Replace all operations with just the 2 tables — ‘T &M’

But as the new T-box and matrix 𝑀 is known, the key can be extracted from the lookup tables. Solution — obfuscate lookup tables by encoding their input and output.

Obfuscating tables with encodings

In the end, a white-boxed implementation of AES looks something like this vis-à-vis a conventional one.

AES on the left — White-boxed AES on the right

Now that we have a good overview of white-boxing an AES implementation, let’s get to the question we’re looking to answer —

Is it possible to recover the secret key from a white-boxed implementation?

This is a 2 part series. We’ll be discussing this question and more (the practicality, scalability, and effort required to defeat white-boxes) in the next one.

References:

Practical attacks on commercial white-box cryptography solutions — Sanghwan Ahn

“Unboxing the White-Box: Practical Attacks Against Obfuscated Ciphers”, J. DeHaas, C. Mune, E. Sanfelix — BlackHat EU 2015 presentation

“Differential Computation Analysis: Hiding Your White-Box Designs is Not Enough”, Joppe W. Bos, Charles Hubain, Wil Michiels, Philippe Teuwen

Credits:

Images- taken from formaestudio, The Hacker News, Riscure, Line corporation.

• Formaestudio has a wonderful animation on AES. I’d recommend checking it out — http://formaestudio.com/