XTEA

Last updated

XTEA
XTEA InfoBox Diagram.svg
Two Feistel rounds (one cycle) of XTEA
General
Designers Roger Needham, David Wheeler
First published1997
Derived from TEA
Successors Corrected Block TEA
Cipher detail
Key sizes 128 bits
Block sizes 64 bits
Structure Feistel cipher
Rounds variable; 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]

Contents

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] */voidencipher(unsignedintnum_rounds,uint32_tv[2],uint32_tconstkey[4]){unsignedinti;uint32_tv0=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;}voiddecipher(unsignedintnum_rounds,uint32_tv[2],uint32_tconstkey[4]){unsignedinti;uint32_tv0=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 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. [2] [3]

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. [4]

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 by Saarinen, [5] which also details a weakness in Block TEA's successor, XXTEA.

See also

Related Research Articles

<span class="mw-page-title-main">Data Encryption Standard</span> Early unclassified symmetric-key block cipher

The Data Encryption Standard is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryptography.

Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in information input can affect the resultant difference at the output. In the case of a block cipher, it refers to a set of techniques for tracing differences through the network of transformation, discovering where the cipher exhibits non-random behavior, and exploiting such properties to recover the secret key.

<span class="mw-page-title-main">Serpent (cipher)</span>

Serpent is a symmetric key block cipher that was a finalist in the Advanced Encryption Standard (AES) contest, in which it ranked second to Rijndael. Serpent was designed by Ross Anderson, Eli Biham, and Lars Knudsen.

In cryptography, Skipjack is a block cipher—an algorithm for encryption—developed by the U.S. National Security Agency (NSA). Initially classified, it was originally intended for use in the controversial Clipper chip. Subsequently, the algorithm was declassified.

<span class="mw-page-title-main">Tiny Encryption Algorithm</span> Block cipher

In cryptography, the Tiny Encryption Algorithm (TEA) is a block cipher notable for its simplicity of description and implementation, typically a few lines of code. It was designed by David Wheeler and Roger Needham of the Cambridge Computer Laboratory; it was first presented at the Fast Software Encryption workshop in Leuven in 1994, and first published in the proceedings of that workshop.

In cryptography, Camellia is a symmetric key block cipher with a block size of 128 bits and key sizes of 128, 192 and 256 bits. It was jointly developed by Mitsubishi Electric and NTT of Japan. The cipher has been approved for use by the ISO/IEC, the European Union's NESSIE project and the Japanese CRYPTREC project. The cipher has security levels and processing abilities comparable to the Advanced Encryption Standard.

Red Pike is a classified United Kingdom government encryption algorithm, proposed for use by the National Health Service by GCHQ, but designed for a "broad range of applications in the British government" Archived 2004-04-23 at the Wayback Machine. Little is publicly known about Red Pike, except that it is a block cipher with a 64-bit block size and 64-bit key length. According to the academic study of the cipher cited below and quoted in a paper by Ross Anderson and Markus Kuhn, it "uses the same basic operations as RC5" and "has no look-up tables, virtually no key schedule and requires only five lines of code"; "the influence of each key bit quickly cascades" and "each encryption involves of the order of 100 operations". 64 bits of key entropy are not considered secure anymore.

<span class="mw-page-title-main">SHACAL</span> Block cipher

SHACAL-1 is a 160-bit block cipher based on SHA-1, and supports keys from 128-bit to 512-bit. SHACAL-2 is a 256-bit block cipher based upon the larger hash function SHA-256.

<span class="mw-page-title-main">Boomerang attack</span> Form of cryptanalysis

In cryptography, the boomerang attack is a method for the cryptanalysis of block ciphers based on differential cryptanalysis. The attack was published in 1999 by David Wagner, who used it to break the COCONUT98 cipher.

<span class="mw-page-title-main">Salsa20</span> Stream ciphers

Salsa20 and the closely related ChaCha are stream ciphers developed by Daniel J. Bernstein. Salsa20, the original cipher, was designed in 2005, then later submitted to the eSTREAM European Union cryptographic validation process by Bernstein. ChaCha is a modification of Salsa20 published in 2008. It uses a new round function that increases diffusion and increases performance on some architectures.

In cryptography, impossible differential cryptanalysis is a form of differential cryptanalysis for block ciphers. While ordinary differential cryptanalysis tracks differences that propagate through the cipher with greater than expected probability, impossible differential cryptanalysis exploits differences that are impossible at some intermediate state of the cipher algorithm.

In cryptography, integral cryptanalysis is a cryptanalytic attack that is particularly applicable to block ciphers based on substitution–permutation networks. It was originally designed by Lars Knudsen as a dedicated attack against Square, so it is commonly known as the Square attack. It was also extended to a few other ciphers related to Square: CRYPTON, Rijndael, and SHARK. Stefan Lucks generalized the attack to what he called a saturation attack and used it to attack Twofish, which is not at all similar to Square, having a radically different Feistel network structure. Forms of integral cryptanalysis have since been applied to a variety of ciphers, including Hierocrypt, IDEA, Camellia, Skipjack, MISTY1, MISTY2, SAFER++, KHAZAD, and FOX.

In cryptography, SC2000 is a block cipher invented by a research group at Fujitsu Labs. It was submitted to the NESSIE project, but was not selected. It was among the cryptographic techniques recommended for Japanese government use by CRYPTREC in 2003, however, has been dropped to "candidate" by CRYPTREC revision in 2013.

In cryptography, Zodiac is a block cipher designed in 2000 by Chang-Hyi Lee for the Korean firm SoftForum.

In cryptography, ARIA is a block cipher designed in 2003 by a large group of South Korean researchers. In 2004, the Korean Agency for Technology and Standards selected it as a standard cryptographic technique.

In cryptography, Spectr-H64 is a block cipher designed in 2001 by N. D. Goots, A. A. Moldovyan and N. A. Moldovyan. It relies heavily on the permutation of individual bits, so is much better suited to implementation in hardware than in software.

In cryptography, Treyfer is a block cipher/MAC designed in 1997 by Gideon Yuval. Aimed at smart card applications, the algorithm is extremely simple and compact; it can be implemented in just 29 bytes of 8051 machine code.

<span class="mw-page-title-main">XXTEA</span> Block cipher

In cryptography, Corrected Block TEA is a block cipher designed to correct weaknesses in the original Block TEA.

The following outline is provided as an overview of and topical guide to cryptography:

This article summarizes publicly known attacks against block ciphers and stream ciphers. Note that there are perhaps attacks that are not publicly known, and not all entries may be up to date.

References

  1. ↑ Roger M. Needham; David J. Wheeler (October 1997). Tea extensions (PDF). Computer Laboratory, University of Cambridge (Technical report).
  2. ↑ Ko, Youngdai; Hong, Seokhie; Lee, Wonil; Lee, Sangjin; Kang, Ju-Sung (2004). "Related Key Differential Attacks on 27 Rounds of XTEA and Full-Round GOST" (PDF). In Roy, B.; Meier, W. (eds.). Fast Software Encryption. FSE 2004. Lecture Notes in Computer Science. Vol. 3017. Berlin, Heidelberg: Springer. pp. 299–316. doi: 10.1007/978-3-540-25937-4_19 . ISBN   978-3-540-22171-5 . Retrieved October 10, 2018.
  3. ↑ Hong, Seokhie; Hong, Deukjo; Ko, Youngdai; Chang, Donghoon; Lee, Wonil; Lee, Sangjin (2004). "Differential Cryptanalysis of TEA and XTEA". In Lim, JI.; Lee, DH. (eds.). Information Security and Cryptology. ICISC 2003. Lecture Notes in Computer Science. Vol. 2971. Berlin, Heidelberg: Springer. pp. 402–417. doi:10.1007/978-3-540-24691-6_30. ISBN   978-3-540-21376-5.
  4. ↑ Lu, Jiqiang (July 2, 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. S2CID   26794956.
  5. ↑ Saarinen, Markku-Juhani (October 20, 1998). "Cryptanalysis of Block Tea". ResearchGate. Retrieved October 10, 2018.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.