**Generalized Tiny Encryption Algorithm
**Based on the work of David J. Wheeler and Roger M. Needham

** Abstract. **This paper proposes extensions and variations to the proposed TEA algorithm, while maintaining the same objectives as the original TEA algorithm.

**Introduction
**In the original paper that describes TEA [1], the authors left out one crucial aspect of the algorithm, which lead to related key attacks [3]. Although the algorithm was still effective the authors proposed X-TEA [2]. They believed that this new algorithm was more resistant to the related key attack.

The goal of Generalized Tiny Encryption Algorithm (GTEA) is to define and explore a family of algorithms based on the basic TEA algorithm. In this paper, variations will be explored and documented with reference to cryptanalysis and levels of diffusion/confusion.

To avoid confusion of the terminology, all numbers are in decimal, except hexadecimal which are denoted by a 0x. Function names are all in bold, and variables are not in bold.

sum = 0

for r = 1 to rounds

P1 = P1

P2 = P2

sum = sum + 0x9E3779B9

K =

next r

Where the following functions and variables are used

P Plaintext, divided into two halves, P

K Key, divided into four parts, K

n is the rotation amount.

sum A simple linear sequence used to avoid degenerative cycles. The value 0x9E3779B9 was taken from golden number ()

The decryption is the same, except you use subtraction as the first operator, instead of addition. The idea is that the mixed addition and xor operations are non-linear. (One proof is that addition is in the GF(2

Despite it's simplicity, the algorithm in theory can be made quite resistant to known attacks. This requires the use of properly created functions which are resistant to differential and linear attacks. We can describe TEA [1], using this model describing the functions

For

P

For

X-TEA

For

P

For

Where

Both algorithm feature similar diffusion techniques. They use a feedback function similar to

F(x) =

Which is used to diffuse bit errors in the register. This called a feedback because when the wrong values enter at the first round of the iteration, they will cause errors in the destination register, which in turn is the input for the next round. This turns out to be quite effective in causing diffusion of bit errors. It requires at least five rounds (not iterations) to cause at least 32 bit errors. Although this level of diffusion (50% of the block) is not always achieved so quickly,and that is why the authors of TEA have suggested a bare minimum of 8 rounds (4 iterations) for at least that much diffusion.

The confusion sequence is different in both algorithms. In the original TEA, the odd rounds used K

In

The choice of the sum delta value and it's bits in the index were not arbitrary. The delta is used to avoid degenerative rounds where patterns can appear, which is due to weak keys. The key of all zero for example is considered weak, if there is no sum register. The sum register basically maintains that all the bits of the result change with a probability of 1/2 in every round. This provides for nice statistical results.

Although

A simple correction for this could be

P

P

Where r is the current iteration number in the round function. The even round uses 'r + 1' to help deter similar keys from being used in any round by a factor of 2

This model will have a maximum (after 128 rounds) of 128 scheduled keys. They will be used in a fixed order too.

The above can be extended similar to [4] using data dependant rotations on the subkeys.

P

P

This will allow 'random' rotations of the subkeys, controlled by input plaintext register. The idea is that each different plaintext block will produce different sets of scheduled keys during encryption. There are essentially 32*4 or 128 scheduled keys, which have no preset order of use. Assuming that the probability of each bit in the plaintext registers is 1/2, then each rotation amount will have a probability of 1/32 (or 1/2 * 1/2 * 1/2 * 1/2 * 1/2 for each of the five bits). Which extends to the actual keys (given each key has a probability of 1/4 of being used) then each 'scheduled key' has a probability of 1/4 * 1/32 or 1/128. This extension is actually quite efficient on most computers (such as x86 systems), which support rotations directly.

The security of this design requires hiding the rotation amounts used. If the rotation amounts can be obtained then there are essentially four scheduled keys. To properly mask the rotations amounts pre-whitening and post-whitening are required, which is pretty easy to implement. Using K

A nice benefit of this is that although there are 128 scheduled keys, none of which have to be stored in memory (except for the four original sub keys). This indicates a good use of memory while extending security.

This idea can be extended to provide more scheduled keys. You could create extra subkeys by deriving them from the original key. It must be noted this does not complicate a brute force search.

A = K

B = K

C = K

D = K

Each extra subkey are independent of each other. This is hardly one way, but provides four extra sub keys. You could then extend

P

P

This extension is quite a bit slower then the previous. Assuming that each value in NK has a probability of 1/2

The major draw back is that there are two rotations per round, double that of

The benefit of

A natural extension would be to create the NK set from actual key entries, which would make collisions nonexistent, and extend the key from 128 bits to 256 bits. This is also quite practical given the design.

Another design criteria for

Another possible extension to

The pseudo code would resemble

P

P

sum = 0x9E3779B9

for r = 1 to rounds

P

sum = sum + 0x9E3779B9

P2 = P

next r

P

P

Yet another extension to this would be to rotate the entire key after every two rounds. This idea could be aplied to any of the GTEA algorithms.

This idea would also slow down the process, but provide for up to 128*128 (in the case of

In subsequent blocks you would use different states of the key. For example if you have 32 iterations (64 rounds) after four encrypted blocks you would start to use the same key state. A better idea would to use a number of iterations that does not evenly divide 128. In this manner the cycle will not always begin at the start or end of a block (for example 26 rounds would ensure that the key state is different in each subsequent block). Key rotation can also be easily to the original

This extension would provide more scheduled keys, and would be more resistant to differential analysis. The individual scheduled keys would also be more complicated and harder to analyze. If security is of a high concern, studying

Still other areas of improvement include using a more irregular order for the subkeys. Currently the (sum mod 4) will always be in order of '1, 2, 3, 4, ...'. While it is not required (at all, and is really not needed if you rotate the entire key), it may be an area of interest for future development.

Having the key words (and the key as a whole) being rotated is a quite natural method to have such a nice influence which is what this paper has explored.

Both algorithms require at least five rounds (2.5 iterations) to complete diffusion of a single bit error (in the very first round). It is assumed that at least eight to sixteen rounds are required to strengthen this effect, this is because single bit errors can either propagate zero, one or two error bits. The most common result would be that a single bit error would propagate two error bits for the next round. Each of these errors would be about 9 bits away, which means that a single bit error requires at most seven rounds to effect the key schedule of

Overall both proposals are for further study only. While they are based on good theory, they require further study, and research to back up the claims made. A promising area of research would be an actual key rotation. As described key rotation could be used for file encryption or a communication link, and would make electronic code book mode a valuable tool.

[2] X-TEA, Tea Extensions, David J. Wheeler & Roger M. Needham.

[3] Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDes, RC2 and TEA, John Kelsey, Bruce Schneier & David Wagner.

[4] The RC5 Encryption Algorithm, March 20th 1997, Ronald L. Rivest.

[5] The RC6 Block Cipher, A submission to AES, Ronald L. Rivest, M.J.B Robshaw, R. Sidneyt & Y.L. Yin.

Appendix A

/* Tea related source code */

#define DELTA 0x9E3779B9UL

#define ROUNDS 64

/* macro to perform cyclic bit rotations left */

#define rol(x, y) ( ((x) << ((y) & 31)) | ((x) >> (32 - ((y) & 31))) )

void tea(unsigned long key[4], unsigned long plain[2])

{

unsigned long y, z, sum, r;

sum = 0;

y = plain[0]; z = plain[1];

for (r = 0; r < (ROUNDS / 2); r++) {

sum += DELTA;

y += ((z << 4) + key[0]) ^ (z + sum) ^ ((z >> 5) + key[1]);

z += ((y << 4) + key[2]) ^ (y + sum) ^ ((y >> 5) + key[3]);

}

plain[0] = y; plain[1] = z;

}

/* X-TEA */

void xtea(unsigned long key[4], unsigned long plain[2])

{

unsigned long y, z, sum, r;

sum = 0;

y = plain[0]; z = plain[1];

for (r = 0; r < (ROUNDS / 2); r++) {

y += ((z << 4) ^ (z >> 5)) + (z ^ sum) + key[sum & 3];

sum += DELTA;

z += ((y << 4) ^ (y >> 5)) + (y ^ sum) + key[(sum >> 11) & 3];

}

plain[0] = y; plain[1] = z;

}

/* TEA-N1 */

void tean1(unsigned long key[4], unsigned long plain[2])

{

unsigned x, y, sum, r;

sum = 0;

u = plain[0] + key[0]; z = plain[1] + key[2];

for (r = 0; r < (ROUNDS / 2); r++) {

y += ((z << 4) ^ (z >> 5)) + (z ^ sum) + rol(key[sum & 3], z);

sum += DELTA;

z += ((y << 4) ^ (y >> 5)) + (y ^ sum) + rol(key[(sum >> 11) & 3], y);

}

plain[0] = y ^ key[1]; plain[1] = z ^ key[3];

}