Extended Tiny Encryption Algorithm
XTEA | |
---|---|
Two Feistel rounds (one cycle) from XTEA | |
developer | Roger Needham , David Wheeler |
Released | 1997 |
Derived from | TEA |
Key length | 128 bit |
Block size | 64 bit |
structure | Feistel cipher |
Round | variable, 64 Feistel rounds (32 cycles) recommended |
Best known cryptanalysis | |
As of 2004, the best known attack on a reduced number of 26 Feistel rounds is known. |
The XTEA ( e X tended T iny E ncryption A lgorithm ) is a block cipher which an extension and improvement of the block cipher TEA represents. XTEA, like TEA, is known for its ease of description and implementation. The code as a C program usually only comprises a few lines of code. It was developed by David Wheeler and Roger Needham at Cambridge University in 1997. Like its predecessor TEA, XTEA is free of patents.
properties
XTEA works on 64-bit blocks and uses a 128-bit long key. It represents a Feistel cipher with a suggested number of Feistel rounds of 64. It is normally implemented in such a way that 2 rounds represent a cycle. It has a very simple mechanism for generating the respective round key. The introduction of a so-called delta, which is defined as in TEA , prevents an attack based on the symmetry of the individual rounds. However, with XTEA the delta is brought into the group differently, which actually strengthens the algorithm.
In 2009 Jiqiang Lu presented a related-key rectangle attack over 36 rounds. This attack affects the highest number of rounds up to 2015. Andrey Bogdanov and Meiqin Wang also presented a zero correlation linear cryptanalysis on 27 rounds of XTEA in 2012 .
Referral Code
The following is the adaptation of the reference implementation of the encryption and decryption routines in C , which was published as public domain by David Wheeler and Roger Needham:
#include <stdint.h>
/* gegeben sind 64 Datenbits in v[0] und v[1] und 128 Schlüsselbits in k[0] bis k[3] */
/* Die Daten werden mit 2 * num_cycles Runden verschlüsselt */
void encipher (unsigned int num_cycles, uint32_t v[2], uint32_t const k[4]) {
unsigned int i;
const uint32_t delta = 0x9E3779B9;
uint32_t v0 = v[0], v1 = v[1], sum = 0;
for (i=0; i < num_cycles; i++) {
v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + k[sum & 3]);
sum += delta;
v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + k[(sum>>11) & 3]);
}
v[0] = v0; v[1] = v1;
}
void decipher (unsigned int num_cycles, uint32_t v[2], uint32_t const k[4]) {
unsigned int i;
const uint32_t delta = 0x9E3779B9;
uint32_t v0 = v[0], v1 = v[1], sum = delta * num_cycles;
for (i=0; i < num_cycles; i++) {
v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + k[(sum>>11) & 3]);
sum -= delta;
v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + k[sum & 3]);
}
v[0] = v0; v[1] = v1;
}
The adaptation to the original implementation regarding smaller edge points:
- The original implementation uses the types
unsigned long
instead of the 64-bit compatibleuint32_t
types. - The original code did not use any
const
types. - The original code avoids redundant brackets, which reduces the readability of the code.
Web links
- Various TEA and XTEA implementations (English)
- PHP implementation of XTEA
- Test vectors for TEA and XTEA (English)
Individual evidence
- ^ Jiqiang Lu: Related-key rectangle attack on 36 rounds of the XTEA block cipher In: International Journal of Information Security , February 2009, pp. 1-11, Springer-Verlag.
- ↑ Andrey Bogdanov and Meiqin Wang: Zero correlation linear cryptanalysis with reduced data complexity . In: Proceedings of FSE 2012 , pp. 29-48, Springer-Verlag.