Extended Tiny Encryption Algorithm

from Wikipedia, the free encyclopedia
XTEA
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 longinstead of the 64-bit compatible uint32_ttypes.
  • The original code did not use any consttypes.
  • The original code avoids redundant brackets, which reduces the readability of the code.

Web links

Individual evidence

  1. ^ 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.
  2. ↑ Andrey Bogdanov and Meiqin Wang: Zero correlation linear cryptanalysis with reduced data complexity . In: Proceedings of FSE 2012 , pp. 29-48, Springer-Verlag.