TEA – tiny algorithm but done with big heart

This is an implementation of the tiny encryption algorithm written in python for a computer and network security class. Our professor had specific rudimentary requirements for how it was to be implemented. I expanded upon the assignment by including testing and extra functionality then refactored. The code is public on my github.


This post is somewhat technical but I will explain everything simply for anyone unfamiliar with the concepts. I will introduce and then explain so bear with me if this looks like gibberish at first.

The tiny encryption algorithm is one of the simplest serious block encryption algorithms. The algorithm works on 64 bit blocks of plain text at a time using a 128 bit key. In the diagram above the plain text is divided into two 32 bit blocks L0 and R0 and the 128 bit key is divided into four 32 bit blocks K0-K3. The formula is represented below.

The Encryption uses repeated application of the pair of rounds shown in the diagram above, defined here for rounds i and i+1 starting with i=1
δ Delta is a predetermined constant
田 denotes addition-mod-232
⊕ denotes XOR (exclusive or)
>> denotes logical shift in given direction

All of the variables are declared as unsigned 32-bit integers, I do this in python by importing c_uint32 from ctypes library. An unsigned 32-bit integer is a binary number with 32 places for 1’s or 0’s and is always positive. The program takes input in hexadecimal base 16 format which extends 0-9 with letters A-F. Meaning F in hexadecimal equals 15 in our standard base 10 and 1111 in base 2 binary.

Hexadecimal is much easier for us humans to deal with because rather than having to write each place (bit) as a 1 or 0 we can represent 4 binary places (4 bits) at a time with 1 hexadecimal digit. This allows us to represent ‘10011111111101010111100111100101’ as 9FF579E5. Convention is to write hexadecimal with a prefixed ‘0x’ so 0x9FF579E5.

A logical shift, >> in the formula as well as within the code, is a bit-wise operation that shifts all of the bits of its operand. This means that all of the places (bits) of a number in binary are shifted.

example of logical shift left by 1 from Wikipedia

Addition-mod-232 means that the values are added together and then divided by 232 and the remainder is the result. Another way of thinking about this is that the two values are added together and if they are more than 232 then 232 is subtracted from the total for the result. The processor performs this differently with overflow and wrapping but this is a simple way to represent the math.

XOR, exclusive or, is represented in the formula as ⊕ and within the code by ^ the caret. XOR is a binary operation that compares bit to corresponding bit and the result evaluates to 1 only if exactly one of the bits is a 1. This means the result is 1 only if one of the bits ‘or’ the other is 1 but not if both are 1. I am reiterating this to differentiate it from the usual logical ‘or’ where it is also 1 if both values are 1.

My implementation is verbose in order to try and grok the algorithm. The assignment was to write a program to perform one pair of encryption rounds and to then decrypt the 64 bit ciphertext which after one pair of rounds is L2 and R2 in the diagram. Also recall that K0-K3 are 32-bit blocks of the 128-bit key.

If not familiar with grok, it is a fantastic term. From Robert A. Heinlein's book Stranger in a Strange Land,

'Grok' means to understand so thoroughly that the observer becomes a part of the observed —to merge, blend, intermarry, lose identity in group experience.

Looking again at the diagram, the first step after getting input and setting up all of the variables is to determine L1 and R1. Following the directional arrows we start by taking R0 into three branches and performing a logical shift left by 4 on one and a logical shift right by 5 on another. The logical shift left branch is then added using addition-mod-232 with K0 and the right branch with K1. The third R0 is also added-mod-232 with Delta1. All three branches are then XOR’ed and the result is added-mod-232 to L0 for the value of R1. L1 is an unchanged R0.

Delta is a predetermined constant. In practice it would usually be a magic number but was determined for the assignment

The next round is essentially the same using the new starting points of L1 and R1 with the next blocks for addition. K2 is added to the logical shift left branch, K3 for the logical shift right branch, and Delta2 for the third branch.

Since the assignment was to only do one round, the ciphertext in L2 and R2 can then be decrypted by reversing the process. Reversing the arrows on the diagram we take L2 to perform the three operations on to XOR together. Then perform a subraction-mod-232 with R2. This gives us R0 and L1 which we then use to determine L0 through the same process but with the earlier key blocks and delta.

Decryption algorithm, 曰 denotes subtraction-mod-232

Then again with the L1/R0 bit-string to find L0

In practice it’s recommended to run the algorithm for 64 Feistel rounds (32 pairs of rounds). Feistel refers to the symmetric structure of the algorithm, as clearly seen within the diagram. Also in practice the predetermined Delta would be a magic number, a number chosen to demonstrate that there are no possible hidden properties to it. There are a few weaknesses to TEA which have removed it from common use in cryptography. The code is decent, it’s at 96% coverage on the testing.

Leave a Reply