Jump to content

XTEA

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 217.140.106.52 (talk) at 17:02, 2 November 2018. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

XTEA
Two Feistel rounds (one cycle) of XTEA
General
DesignersRoger Needham, David Wheeler
First published1997
Derived fromTEA
SuccessorsCorrected Block TEA
Cipher detail
Key sizes128 bits
Block sizes64 bits
StructureFeistel cipher
Roundsvariable; recommended 64 Feistel rounds (32 cycles)
Best public cryptanalysis
A related-key rectangle attack on 36 rounds of XTEA (Lu, 2009)[vague]

In cryptography, XTEA (eXtended TEA) is a block cipher designed to correct weaknesses in TEA. The cipher's designers were David Wheeler and Roger Needham of the Cambridge Computer Laboratory, and the algorithm was presented in an unpublished technical report in 1997 (Needham and Wheeler, 1997). It is not subject to any patents.[1]

Like TEA, XTEA is a 64-bit block Feistel cipher with a 128-bit key and a suggested 64 rounds. Several differences from TEA are apparent, including a somewhat more complex key-schedule and a rearrangement of the shifts, XORs, and additions.

Implementations

This standard C source code, adapted from the reference code released into the public domain by David Wheeler and Roger Needham, encrypts and decrypts using XTEA: 

#include <stdint.h>

/* take 64 bits of data in v[0] and v[1] and 128 bits of key[0] - key[3] */

void encipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9E3779B9;
    for (i=0; i < num_rounds; i++) {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
    }
    v[0]=v0; v[1]=v1;
}

void decipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], delta=0x9E3779B9, sum=delta*num_rounds;
    for (i=0; i < num_rounds; i++) {
        v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
        sum -= delta;
        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
    }
    v[0]=v0; v[1]=v1;
}

The changes from the reference source code are minor:

  • The reference source code used the unsigned long type rather than the 64-bit clean uint32_t.
  • The reference source code did not use const types.
  • The reference source code omitted redundant parentheses, using C precedence to write the round function as e.g. v1 += (v0<<4 ^ v0>>5) + v0 ^ sum + k[sum>>11 & 3];

The recommended value for the "num_rounds" parameter is 32, not 64, as each iteration of the loop does two Feistel-cipher rounds. To additionally improve speed, the loop can be unrolled by pre-computing the values of sum+key[].

Cryptanalysis

In 2004, Ko et al. presented a related-key differential attack on 27 out of 64 rounds of XTEA, requiring 220.5 chosen plaintexts and a time complexity of 2115.15 (Ko et al., 2004).

In 2009, Lu presented a related-key rectangle attack on 36 rounds of XTEA, breaking more rounds than any previously published cryptanalytic results for XTEA. The paper presents two attacks, one without and with a weak key assumption, which corresponds to 264.98 bytes of data and 2126.44 operations, and 263.83 bytes of data and 2104.33 operations respectively.[2]

Block TEA

Presented along with XTEA was a variable-width block cipher termed Block TEA, which uses the XTEA round function, but Block TEA applies it cyclically across an entire message for several iterations. Because it operates on the entire message, Block TEA has the property that it does not need a mode of operation. An attack on the full Block TEA was described in (Saarinen, 1998), which also details a weakness in Block TEA's successor, XXTEA.

See also

  • RC4 — A stream cipher that, just like XTEA, is designed to be very simple to implement.
  • XXTEA — Block TEA's successor.
  • TEA — Block TEA's precursor.

References

  1. ^ Tea extensions (PDF). Computer Laboratory, University of Cambridge (Technical report). October 1997. {{cite tech report}}: Unknown parameter |authors= ignored (help)
  2. ^ Lu, Jiqiang (2 July 2008). "Related-key rectangle attack on 36 rounds of the XTEA block cipher". International Journal of Information Security. 8 (1): 1–11. doi:10.1007/s10207-008-0059-9. ISSN 1615-5262.

Further reading

Retrieved from "https://en.wikipedia.org/w/index.php?title=XTEA&oldid=866951997"