XXTEA - Misplaced Pages

Block cipher

Corrected Block TEA (XXTEA)
General
One round of XXTEA
Designers	David Wheeler, Roger Needham
First published	October 1998
Derived from	Block TEA
Cipher detail
Key sizes	128 bits
Block sizes	arbitrary, at least two words (64 bits)
Structure	Unbalanced Feistel Network
Rounds	depends on the block size; ~52+6*words (6-32 full cycles)
Best public cryptanalysis
XXTEA is vulnerable to a chosen-plaintext attack requiring 2 queries and negligible work.

In cryptography, Corrected Block TEA (often referred to as XXTEA) is a block cipher designed to correct weaknesses in the original Block TEA.

XXTEA is vulnerable to a chosen-plaintext attack requiring 2 queries and negligible work. See cryptanalysis below.

The cipher's designers were Roger Needham and David Wheeler of the Cambridge Computer Laboratory, and the algorithm was presented in an unpublished technical report in October 1998 (Wheeler and Needham, 1998). It is not subject to any patents.

Formally speaking, XXTEA is a consistent incomplete source-heavy heterogeneous UFN (unbalanced Feistel network) block cipher. XXTEA operates on variable-length blocks that are some arbitrary multiple of 32 bits in size (minimum 64 bits). The number of full cycles depends on the block size, but there are at least six (rising to 32 for small block sizes). The original Block TEA applies the XTEA round function to each word in the block and combines it additively with its leftmost neighbour. Slow diffusion rate of the decryption process was immediately exploited to break the cipher. Corrected Block TEA uses a more involved round function which makes use of both immediate neighbours in processing each word in the block.

XXTEA is likely to be more efficient than XTEA for longer messages.

Needham & Wheeler make the following comments on the use of Block TEA:

For ease of use and general security the large block version is to be preferred when applicable for the following reasons.

A single bit change will change about one half of the bits of the entire block, leaving no place where the changes start.

There is no choice of mode involved.

Even if the correct usage of always changing the data sent (possibly by a message number) is employed, only identical messages give the same result and the information leakage is minimal.

The message number should always be checked as this redundancy is the check against a random message being accepted.

Cut and join attacks do not appear to be possible.

If it is not acceptable to have very long messages, they can be broken into chunks say of 60 words and chained analogously to the methods used for DES.

However, due to the incomplete nature of the round function, two large ciphertexts of 53 or more 32-bit words identical in all but 12 words can be found by a simple brute-force collision search requiring 2 memory, 2 time and 2+2 chosen plaintexts, in other words with a total time*memory complexity of 2, which is actually 2 for any such cipher. It is currently unknown if such partial collisions pose any threat to the security of the cipher. Eight full cycles would raise the bar for such collision search above complexity of parallel brute-force attacks.

The unusually small size of the XXTEA algorithm would make it a viable option in situations where there are extreme constraints e.g. legacy hardware systems (perhaps embedded) where the amount of available RAM is minimal, or alternatively single-board computers such as the Raspberry Pi, Banana Pi or Arduino.

Cryptanalysis

An attack published in 2010 by E. Yarrkov presents a chosen-plaintext attack against full-round XXTEA with wide block, requiring 2 queries for a block size of 212 bytes or more, and negligible work. It is based on differential cryptanalysis.

To cipher "212 bytes or more" algorithm performs just 6 rounds, and carefully chosen bit patterns allows to detect and analyze avalanche effect.

Reference code

The original formulation of the Corrected Block TEA algorithm, published by David Wheeler and Roger Needham, is as follows:

  #define DELTA 0x9e3779b9
  #define MX ((z>>5^y<<2) + (y>>3^z<<4) ^ (sum^y) + (k^z))
  long btea(long* v, long n, long* k) {
    unsigned long z=v, y=v, sum=0, e, DELTA=0x9e3779b9;
    long p, q ;
    if (n > 1) {          /* Coding Part */
      q = 6 + 52/n;
      while (q-- > 0) {
        sum += DELTA;
        e = (sum >> 2) & 3;
        for (p=0; p<n-1; p++) y = v, z = v += MX;
        y = v;
        z = v += MX;
      }
      return 0 ; 
    } else if (n < -1) {  /* Decoding Part */
      n = -n;
      q = 6 + 52/n;
      sum = q*DELTA ;
      while (sum != 0) {
        e = (sum >> 2) & 3;
        for (p=n-1; p>0; p--) z = v, y = v -= MX;
        z = v;
        y = v -= MX;
        sum -= DELTA;
      }
      return 0;
    }
    return 1;
  }

According to Needham and Wheeler:

BTEA will encode or decode n words as a single block where n > 1
v is the n word data vector

k is the 4 word key

n is negative for decoding

if n is zero result is 1 and no coding or decoding takes place, otherwise the result is zero

assumes 32 bit 'long' and same endian coding and decoding

Note that the initialization of z is Undefined behavior for n < 1 which may cause a segmentation fault or other unwanted behavior – it would be better placed inside the 'Coding Part' block. Also, in the definition of MX some programmers would prefer to use bracketing to clarify operator precedence.

A clarified version including those improvements is as follows:

  #include <stdint.h>
  #define DELTA 0x9e3779b9
  #define MX (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key ^ z)))
  void btea(uint32_t *v, int n, uint32_t const key) {
    uint32_t y, z, sum;
    unsigned p, rounds, e;
    if (n > 1) {          /* Coding Part */
      rounds = 6 + 52/n;
      sum = 0;
      z = v;
      do {
        sum += DELTA;
        e = (sum >> 2) & 3;
        for (p=0; p<n-1; p++) {
          y = v; 
          z = v += MX;
        }
        y = v;
        z = v += MX;
      } while (--rounds);
    } else if (n < -1) {  /* Decoding Part */
      n = -n;
      rounds = 6 + 52/n;
      sum = rounds*DELTA;
      y = v;
      do {
        e = (sum >> 2) & 3;
        for (p=n-1; p>0; p--) {
          z = v;
          y = v -= MX;
        }
        z = v;
        y = v -= MX;
        sum -= DELTA;
      } while (--rounds);
    }
  }

References

^ Elias Yarrkov (2010-05-04). "Cryptanalysis of XXTEA". Cryptology ePrint Archive.
Matthew D. Russell (2004-02-27). "Tinyness: An Overview of TEA and Related Ciphers". Archived from the original on 2007-08-12.
Roger M. Needham and David J. Wheeler (October 1997). "Tea extensions" (PDF). Computer Laboratory, Cambridge University, England. Retrieved 2008-07-04.
David J. Wheeler and Roger M. Needham (October 1998). "Correction to XTEA" (PDF). Computer Laboratory, Cambridge University, England. Retrieved 2008-07-04.

v t e Block ciphers (security summary)
Common algorithms	AES Blowfish DES (internal mechanics, Triple DES) Serpent SM4 Twofish
Less common algorithms	ARIA Camellia CAST-128 GOST IDEA LEA RC5 RC6 SEED Skipjack TEA XTEA
Other algorithms	3-Way Adiantum Akelarre Anubis Ascon BaseKing BassOmatic BATON BEAR and LION CAST-256 Chiasmus CIKS-1 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA CMEA Cobra COCONUT98 Crab Cryptomeria/C2 CRYPTON CS-Cipher DEAL DES-X DFC E2 FEAL FEA-M FROG G-DES Grand Cru Hasty Pudding cipher Hierocrypt ICE IDEA NXT Intel Cascade Cipher Iraqi Kalyna KASUMI KeeLoq KHAZAD Khufu and Khafre KN-Cipher Kuznyechik Ladder-DES LOKI (97, 89/91) Lucifer M6 M8 MacGuffin Madryga MAGENTA MARS Mercy MESH MISTY1 MMB MULTI2 MultiSwap New Data Seal NewDES Nimbus NOEKEON NUSH PRESENT Prince Q RC2 REDOC Red Pike S-1 SAFER SAVILLE SC2000 SHACAL SHARK Simon Speck Spectr-H64 Square SXAL/MBAL Threefish Treyfer UES xmx XXTEA Zodiac
Design	Feistel network Key schedule Lai–Massey scheme Product cipher S-box P-box SPN Confusion and diffusion Round Avalanche effect Block size Key size Key whitening (Whitening transformation)
Attack (cryptanalysis)	Brute-force (EFF DES cracker) MITM Biclique attack 3-subset MITM attack Linear (Piling-up lemma) Differential Impossible Truncated Higher-order Differential-linear Distinguishing (Known-key) Integral/Square Boomerang Mod n Related-key Slide Rotational Side-channel Timing Power-monitoring Electromagnetic Acoustic Differential-fault XSL Interpolation Partitioning Rubber-hose Black-bag Davies Rebound Weak key Tau Chi-square Time/memory/data tradeoff
Standardization	AES process CRYPTREC NESSIE NSA Suite B CNSA
Utilization	Initialization vector Mode of operation Padding

v t e Cryptography
General	History of cryptography Outline of cryptography Classical cipher Cryptographic protocol Authentication protocol Cryptographic primitive Cryptanalysis Cryptocurrency Cryptosystem Cryptographic nonce Cryptovirology Hash function Cryptographic hash function Key derivation function Secure Hash Algorithms Digital signature Kleptography Key (cryptography) Key exchange Key generator Key schedule Key stretching Keygen Machines Cryptojacking malware Ransomware Random number generation Cryptographically secure pseudorandom number generator (CSPRNG) Pseudorandom noise (PRN) Secure channel Insecure channel Subliminal channel Encryption Decryption End-to-end encryption Harvest now, decrypt later Information-theoretic security Plaintext Codetext Ciphertext Shared secret Trapdoor function Trusted timestamping Key-based routing Onion routing Garlic routing Kademlia Mix network
Mathematics	Cryptographic hash function Block cipher Stream cipher Symmetric-key algorithm Authenticated encryption Public-key cryptography Quantum key distribution Quantum cryptography Post-quantum cryptography Message authentication code Random numbers Steganography
Category

External links

Categories:

Cryptanalysis

Reference code

See also

References

External links