TEA Encryption

TEA (Tiny Encryption Algorithm) is a simple encryption algorithm that is meant to be simple enough to memorize. It uses a 128 bit key to encrypt 64 bits of plaintext with the following C code:

void tea_encrypt(uint32_t* v, uint32_t* k)
{
    uint32_t sum=0, i;
    uint32_t delta= 0x9e3779b9;
    for (i=0; i < 32; i++) {
        sum  += delta;
        v[0] += ((v[1]<<4) + k[0]) ^ (v[1] + sum) ^ ((v[1]>>5) + k[1]);
        v[1] += ((v[0]<<4) + k[2]) ^ (v[0] + sum) ^ ((v[0]>>5) + k[3]);
    }
}

If you're used to looking at the AES algorithm, this one probably looks extremely simple. However, it is surprisingly secure. As of 2016, very few attacks on TEA are known - the best cryptanalysis results require guesses against a shortened version of the algorithm! The only real weakness is that every key has three other equivalent keys - that is, there are four different keys that all give the exact same encrypted output. This is not a showstopper because keys is still too many to brute-force.

In order to complete a CPA attack, we need to find some sensitive points of the algorithm. Breaking up the first round of the one-liner

v[0] += ((v[1]<<4) + k[0]) ^ (v[1] + sum) ^ ((v[1]>>5) + k[1]);

gives

uint32_t a = (v[1] << 4) + k[0]; // Attack point 1
uint32_t b = v[1] + 0x9e3779b9;  //
uint32_t c = (v[1] >> 5) + k[1]; // Attack point 2
v[0] += (a ^ b ^ c);             // Attack point 3

The three attack points here are good spots to attack because they are non-linear: addition can cause a single changed bit to carry through to several bits of the result. However, all three of these points have limitations.

1. This expression includes a left-shift of 4 bits, so we have no control over the bottom 4 bits. This means we cannot use CPA to recover all 32 bits of k[0] - we can only get 28 of them.
2. Similarly, this expression includes a right-shift of 5 bits, so we can only get at the bottom 27 bits.
3. The last XOR combines the first two results, which use both words of the key (k[0] and k[1]). This means that we can only use it if we already know some of the bits in one of these keys (ie: we can only find the first byte of k[0] if we know the first byte of k[1]).

However, this is enough information to recover both of these words. Once we know these 64 bits, the second half of the key can be recovered in exactly the same way.

Firmware

The AES SimpleSerial target was adapted to use TEA encryption instead of AES. This new target uses the exact same commands as the original SimpleSerial target:

• kKEY loads KEY as the 128 bit encryption key
• pPLAINTEXT loads PLAINTEXT as the 64 bit plaintext and begins the encryption routine
• rRESPONSE is the reply from the target, where RESPONSE is the 64 bit ciphertext

This firmware is available in chipwhisperer/hardware/victims/firmware/simpleserial-tea. It uses the same build process as the other targets - simply run make to produce the hex file.

Capture

The setup for this capture routine will be pretty straightforward because the firmware is so close to the SimpleSerial targets we've attacked before. Only a small number of modifications need to be made to adapt the capture script for TEA.

1. First, run the AES SimpleSerial example script (Project > Example Scripts > ChipWhisperer-Lite: AES SimpleSerial on XMEGA). This will connect to the hardware and prepare most of the settings.
2. Open the programmer (Tools > CW-Lite XMEGA Programmer) and find the hex file that we made in the previous section. Flash this program onto the target.
3. Under Target Settings, change the Input Length and Output Length from 16 to 8 bytes to match the TEA code (64 bit plaintext and ciphertext).
4. Under Scope Settings, change the trigger offset to 0 samples.

All of the other default settings are fine.

Before starting the full captures, open the Encryption Monitor (Tools > Encryption Status Monitor) and press Capture 1. Confirm that the Text In and Text Out are 8 bytes long, like we specified above. If you want to test a specific case, when the input and key are both all 0s, the output is 41 EA 3A 0A 94 BA A9 40.

For our analysis, we'll need two sets of data. The first should have random keys and plaintexts, and the second should have a fixed ("secret") key and random plaintexts. For this guide, I'll be using a fixed key of 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F. Capture about 1000 traces for each set and put all of the data files in a convenient place.

Analysis

More Ideas

This guide has walked through a very basic CPA attack on TEA encryption. However, we could take this a lot further...

• This was a very "manual" attack: we had to guide our code through each of the single-byte attacks. It would be good to have a more automatic attack that combines all of the information from all three attack points, rather than picking and choosing bytes to attack.
• We had to use a lower optimization level so that we could see the power signature from the sensitive attack points. Can we avoid this? Maybe it's possible to use a different sampling method to find more leakage.
• A template attack might be a more powerful way to perform this attack. There are several points that we could create a template for, including the three points that we examined in this attack.