Hardware Implementation of TEA
1
Hardware Implementation of TEA
Anoop Kumar Palvai
Abstract—The size of the key employed in the encryption/decryption operation in an algorithm depends on the level of security desired. The time for encryption/decryption is proportional to key length; therefore a compromise has to be made between speed and security. There arises the need for an algorithm that is neither the fastest, nor the shortest but is thought to be the best compromise for safety, ease of implementation, lack of specialized tables, and reasonable performance. Tiny Encryption Algorithm (TEA) is one of the most efficient algorithms having all the above mentioned qualities. The purpose of the paper is to implement TEA in hardware.
Index Terms—TEA, XTEA, IDEA, DES
T
I.INTRODUCTION
INY Encryption Algorithm is a feistel cipher. It is one of the fastest, simplest and secure algorithms.The structure employed in TEA has the advantage that encryption and decryption operations are very similar, requiring only a reversal of the key-scheduling. This results in the size of the code or circuitry required to implement such a cipher is nearly halved. The operations performedduring encryption or decryption, are derived from the mixed (orthogonal) algebraic groups’ i.e. XOR, SHIFT, and Modulo 232 Addition. These operations provide the Shannon’s twin properties of diffusion and confusion without the explicit need of complex S & P boxes.
II.Operation of tea
The input to TEA is a 64 bit plain/cipher text, encrypted/decrypted to a 64 bit cipher/plain text, using a key of 128 bit length. TEA employs a large number of iterations
rather than a complicated program. Here, the message is divided into two halves; one half is used to encrypt/decrypt the other half in each iteration and vice versa in the next iteration, this process continues alternately. The iteration count can readily be varied, or even made part of the key. It is desired that security can be enhanced by increasing the number of iterations. It uses little set up time and does a weak non linear iteration enough rounds to make it secure.
A.Encode Routine
void code (long* v, long* k)
{
Unsigned long y=v[0],z=v[1], sum=0,
/* set up */
delta=0x9e3779b9, n=32; /*a key scheduleconstant */
while (n-->0)
{ /* basic cycle start */
sum += delta ;
y += (z<4)+k[0] ^ z+sum ^ (z>5)+k[1] ;
z += (y<4)+k[2] ^ y+sum ^ (y>5)+k[3] ; }/* end cycle */
v[0]=y ; v[1]=z ; }
Decode Routine
void decode (long* v,long* k)
{
unsigned long n=32, sum, y=v[0], z=v[1],
delta=0x9e3779b9 ;
sum=delta<5 ;
/* start cycle */
while (n-->0)
{
z-= (y<4)+k[2] ^ y+sum ^ (y>5)+k[3] ;
y-= (z<4)+k[0] ^ z+sum ^ (z>5)+k[1] ;
sum-=delta ;
} /* end cycle */
v[0]=y ; v[1]=z ; }
Left(i) Right(i)
Left(i+1) Right(i+1)
Fig2: Two Iterations of Basic TEA
Fig3: Feistel Structure for Encryption
Fig4: Feistel Structure for Decryption
III.Performance comparison
TEA uses the same orthogonal operations as IDEA, but it is very much simpler, hence faster.Its security is comparable with that of IDEA algorithm. The performance of the algorithm is equivalent to that of DES in software, and its code is short enough to write into almost any program on any computer. A 1 bit change at the input results in a change in the output 32 bits within 6 rounds. Therefore 16 rounds are sufficient to make the encryption secure but recommended is 32. The modes of use of DES are all applicable. It can be up to three times faster than a good software implementation of DES.
IV.weakness of tea
The first weakness of TEA is that it suffers from equivalent keys. Each key is equivalent to three others, and this reduces the effective key size to only 126 bits. This has lead to the extended versions of TEA. The related key attacks are possible even though the construction of 232 texts under two related keys seems impractical. Thesecond weakness, that the effective length of the keys is 126 bits not 128 does affect certain potential applications but not the simple cipher decipher mode.
V.xtea
To cater to the weaknesses mentioned, the algorithm can be readily adjusted.
Following are the tasks to be performed.
- To adjust the key schedule.
- To introduce the key material more slowly.
This results in the algorithm being repaired for the two minor weaknesses and retains almost the same simplicity.
In this version, two bits of sum are used to select the keywords in order to save separate count for n. Even though a shift of 11 causes the sequence to be irregular, it ensures that all the 4 keywords are used in the first two cycles.
The price paid for these advantages is the time to complete change diffusion is delayed by one cycle, however it seems unnecessary to increase to increase 32 to 33, as it is still believed that the number needed is about 16, and the safety factor against inadequate analysis is much the same.
Left[i] Right [i]
Left [i+1] Right [i+1]
Fig5: Feistel Structure of XTEA for 2 rounds
Encryption/Decryption Routine:
XTEA (long * v, long * k, long N)
{
unsigned long y = v [0];
unsigned z =v [1];
unsigned DELTA = 0x9e3779b9;
if (N>0)
{
/* coding */
unsigned long limit = DELTA*N;
unsigned long sum = 0;
while (sum!= limit)
y += (z<4 ^ z>5) + z ^ sum + k[sum&3],
sum += DELTA,
z += (y<4 ^ y>5) + y ^ sum + k [sum>11 &3];
}
else
{
/* decoding */
Unsigned long sum=DELTA*(-N);
while (sum)
z -= (y<4 ^ y>5) + y ^ sum + k[sum>11 &3],
sum -= DELTA,
y -= (z<4 ^ z>5) + z ^ sum + k[sum&3] ;
}
v [0] =y;
v [1]=z ;
return ;}
VI.operation of xtea initeration
The relation between the output (Left [i+1], Right [i+1]) and the input (Left[i], Right[i]) for the ith cycle of XTEA is defined as follows:
1. Left [i+1] = Left[i] + F (Right[i], K [2i-1], delta [i-1]),
2. Right [i+1] = Right[i] + F (Left [i+1], K [2i], delta[i]),
3. Delta[i] = (i+1)/2 * delta
The round function, F, is defined by
F (M, K [*], delta [**]) = ((M<4) xor (M>5)) + (M xor sum) + K [*].
The addition employed is of modulo 232.
VII.block tea
In order to cater for larger block sizes, the algorithm can be modified so as to keep intrinsic mixing similar to TEA, but it has to run cyclically round the block. This means the mixing of various stages is done together, a potential saving of time, and a natural binding of a complete block of N words. The key scheduling is also slightly changed, but probably has the same characteristics.
VIII. Implementation of XTEA
Tools used:
The tools used to implement the routines are
- Aldec active HDL7.1 version for simulation.
- Xilinx XST for synthesis.
- Xilinx ISE for implementation
Modules in XTEA:
- RCA- ripple carry adder
- 32-bit Register
- CSA- carry save adder
- XTEA (top module)
1
Fig6.a: Data Path Diagram of XTEA
Operation performed in a single iteration of XTEA
1
1
Fig 7: ASM Chart of XTEA
ix. Results
Device: Xilinx Spartan3 xc3s1500-5fg456
Number of Slice Flip Flops : 118 out of 26,624 1%
Total Number 4 input LUTs : 1,130 out of 26,624 %
Number of occupied Slices : 594 out of 13,312 4%
Number of bonded IOBs : 293 out of 333 87%
Number of MULT18X18s : 3 out of 32 9%
Total equivalent gate count for design: 20,489
Minimum Time Period 19.765 ns
Maximum Frequency 50.6 MHz
x.Conclusion
Tiny encryption algorithm is one of the simplest algorithms to implement in hardware. It can be employed, where time is a constraint, i.e. a tradeoff can be made between the levels of security desired and the time to encrypt or decrypt, in terms of number of cycles.
XI. FUTURE SCOPE
XTEA can be implemented in a way such that the sub-key for each iteration is different.
References
[1]David J. Wheeler. Roger M. Needham,“TEA, a Tiny Encryption Algorithm”.
[2]Vikram Reddy Andem,“A Cryptanalysis of Tiny Encryption Algorithm”.
[3]Wikipedia, “Description of Tiny Encryption Algorithm, XTEA & Block TEA”.
[4]Dukjae Moon, Kyugdeok Hwang, Wonil Lee, Sangjin Lee, and Jongim Lim, “Impossible Differential cryptanalysis of reduced round XTEA and TEA”.
[5]Simon Sheperd, “A description, with source code, of the high-speed TEA cipher algorithm”.
[6]David Wheeler, Roger Needham,“Extended Tiny Encryption Algorithm: article”. This paper addresses some minor flaws in the original TEA.
[7]Feistel. H. (1973, May), “Cryptography and computer privacy”. ScientificAmerican.
[8]Stephen Brown, Zvonko Vranesic, “Fundamentals of Digital Logic with VHDL”.
[9]Behrooz Parhami, Computer Arithmetic, Algorithms and Hardware Designs
Fig1: Block Diagram of TEA