HI-1 1 Abstract — Some very important factors to consider when designing a cryptographic system are performance, speed, size, and security. Sometimes the designer of the cryptosystem decides to prioritize these factors based on specific objectives of the cryptosystem. Tiny Encryption Algorithm (TEA), and the Extension of TEA (XTEA) are examples of cryptographic algorithms that were designed with size and simplicity as the main design criteria. Since TEA’s presentation to the public in 1994 and XTEA’s presentation in 1997, many software implementations have been designed of both algorithms. However, not nearly as many hardware designs of TEA have been implemented. This report details a hardware implementation of XTEA (Extension of TEA), with a design goal with speed as the main priority as opposed to size. Index Terms — Cryptography, TEA (Tiny Encryption Algorithm), XTEA (Extension of Tiny Encryption Algorithm) I. INTRODUCTION HE Tiny Encryption Algorithm, or TEA, is a block cipher which was originally designed by David Wheeler and Roger Needham of the Cambridge Computer Laboratory. It was first presented at the Fast Software Encryption Workshop in 1994. TEA was designed with the idea that a cryptographic algorithm could be implemented with smaller code size and less complexity, and still execute with similar or better performance measurements than other popular cryptographic algorithms such as DES [1]. II. TINY ENCRYPTION ALGORITHM (TEA) A. Background Information As discussed above, TEA is a block cipher. A block cipher takes a specific input size of plaintext, and the cryptographic algorithm produces a corresponding ciphertext of identical size. For TEA, the block size is defined as 64 bits. TEA uses a Feistel structure. Cryptographic algorithms that use a Feistel structure have similar operations for encryption or decryption. For example, the decryption algorithms may require only a reversal of the encryption algorithm or the key schedule. Cryptographic algorithms that use a Feistel structure also use operations such as bit shuffling or linear mixing to help produce an output that is very different from the input. These operations may be repeated for several rounds for increased security. For TEA, the suggested number of rounds is 64. The rounds are implemented in pairs, which results in 32 cycles for one block of plaintext. The fact that there are 32 cycles for encryption or decryption of the TEA block cipher is to ensure a higher level of security. This is related to the avalanche effect, which states that in order to provide a secure cryptosystem, when one bit of input is changed, then about half of the output bits should change. In the case of TEA, the number of cycles that must occur before changing one input bit effects 32 output bits (half of the 64-bit block) is roughly six cycles. The designers of TEA claim that sixteen cycles should be good enough, but recommend 32 cycles for enough permutation of the output [2]. Since TEA uses a Feistel structure, it uses addition, subtraction, and XOR as reversible operations. The use of addition, subtraction, and XOR operations helps eliminate the need to implement Substitution boxes (S-Box) and Permutation boxes (P-Box) as a part of the design [3]. For security reasons the key length is set to 128 bits to help prevent simple search techniques or persuade attackers against brute force attacks. The key used for TEA is also sometimes called the master key. This is because in the implementation discussed in the original presentation, the master key is subdivided into other derived keys, K[0…3]. The key scheduling method used in TEA is also a simple design. For odd cycles, subkey K[0] and K[1] are used, and for even cycles, subkey K[2] and K[3] are used. Each cycle takes into consideration a variable called “delta” and is used as a part of the key scheduling. A different value for delta is used in each cycle of TEA. The number delta is derived from the following equation: The equation above for delta yields the following rounded number, 2654435769. This number in hexadecimal format is 0x9E3779B9. The following diagram shows encryption for the TEA algorithm. As previously stated, the only operations performed during encryption include addition, XOR, and shift right or shift left. The diagram shows two rounds or one pair/cycle for TEA. The Feistel structure for TEA, and the 4 subkeys used for encryption are also easily seen. Hardware Implementation of XTEA Steven M. Aumack, Michael D. Koontz Jr. THI-1 2++++<< 4>> 5DeltaK[0]K[1]++++<< 4>> 5DeltaK[2]K[3] Figure 1 - TEA Block Diagram B. Software Implementation In the original presentation of TEA, David Wheeler and Roger Needham also included some source code for software implementation. The designer’s state that the particular algorithm used in the source code for the software implementation of TEA was chosen because it was thought to be a compromise between security and simplicity of design. This algorithm was neither the fastest nor the slowest of those tested prior to the final down selection to one algorithm [2]. As a part of the original presentation of TEA, Wheeler and Needham published the following source code. In the software implementation, the source code separates the 64-bit block into two 32-bit numbers labeled y and z. As previously stated, TEA contains two rounds for one cycle of encryption or decryption. Round one (and subsequent odd rounds) operates on y, and subkeys K[0] and K[1]. Round two (and subsequent even rounds) operates on z, and K[2] and K[3]. void code(long* v, long* k) { unsigned long y=v[0],z=v[1], sum=0, /* set up */ delta=0x9e3779b9, /* a key schedule constant */ n=32 ; 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 ; } void decode(long* v,long* k) { unsigned long n=32, sum, y=v[0], z=v[1],delta=0x9e3779b9 ;
View Full Document
Unlocking...