Tiny Encryption Algorithm

Last updated

TEA
TEA InfoBox Diagram.png
Two Feistel rounds (one cycle) of TEA [1]
General
Designers Roger Needham, David Wheeler
First published1994
Successors XTEA
Cipher detail
Key sizes 128 bits
Block sizes 64 bits
Structure Feistel network
Rounds variable; recommended 64 Feistel rounds (32 cycles)
Best public cryptanalysis
TEA suffers from equivalent keys (see text; Kelsey et al., 1996) and can be broken using a related-key attack requiring 223 chosen plaintexts and a time complexity of 232. [2] The best structural cryptanalysis of TEA in the standard single secret key setting is the zero-correlation cryptanalysis breaking 21 rounds in 2121.5 time with less than the full code book [3]

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

Contents

The cipher is not subject to any patents.

Properties

TEA operates on two 32-bit unsigned integers (could be derived from a 64-bit data block) and uses a 128-bit key. It has a Feistel structure with a suggested 64 rounds, typically implemented in pairs termed cycles. It has an extremely simple key schedule, mixing all of the key material in exactly the same way for each cycle. Different multiples of a magic constant are used to prevent simple attacks based on the symmetry of the rounds. The magic constant, 2654435769 or 0x9E3779B9 is chosen to be ⌊232⁄𝜙⌋, where 𝜙 is the golden ratio (as a nothing-up-my-sleeve number). [4]

TEA has a few weaknesses. Most notably, it suffers from equivalent keys—each key is equivalent to three others, which means that the effective key size is only 126 bits. [5] As a result, TEA is especially bad as a cryptographic hash function. This weakness led to a method for hacking Microsoft's Xbox game console, where the cipher was used as a hash function. [6] TEA is also susceptible to a related-key attack which requires 223 chosen plaintexts under a related-key pair, with 232 time complexity. [2] Because of these weaknesses, the XTEA cipher was designed.

Versions

The first published version of TEA was supplemented by a second version that incorporated extensions to make it more secure. Block TEA (which was specified along with XTEA) operates on arbitrary-size blocks in place of the 64-bit blocks of the original.

A third version (XXTEA), published in 1998, described further improvements for enhancing the security of the Block TEA algorithm.

Reference code

Following is an adaptation of the reference encryption and decryption routines in C, released into the public domain by David Wheeler and Roger Needham: [4] 

#include<stdint.h>voidencrypt(uint32_tv[2],constuint32_tk[4]){uint32_tv0=v[0],v1=v[1],sum=0,i;/* set up */uint32_tdelta=0x9E3779B9;/* a key schedule constant */uint32_tk0=k[0],k1=k[1],k2=k[2],k3=k[3];/* cache key */for(i=0;i<32;i++){/* basic cycle start */sum+=delta;v0+=((v1<<4)+k0)^(v1+sum)^((v1>>5)+k1);v1+=((v0<<4)+k2)^(v0+sum)^((v0>>5)+k3);}/* end cycle */v[0]=v0;v[1]=v1;}voiddecrypt(uint32_tv[2],constuint32_tk[4]){uint32_tv0=v[0],v1=v[1],sum=0xC6EF3720,i;/* set up; sum is (delta << 5) & 0xFFFFFFFF */uint32_tdelta=0x9E3779B9;/* a key schedule constant */uint32_tk0=k[0],k1=k[1],k2=k[2],k3=k[3];/* cache key */for(i=0;i<32;i++){/* basic cycle start */v1-=((v0<<4)+k2)^(v0+sum)^((v0>>5)+k3);v0-=((v1<<4)+k0)^(v1+sum)^((v1>>5)+k1);sum-=delta;}/* end cycle */v[0]=v0;v[1]=v1;}

Note that the reference implementation acts on multi-byte numeric values. The original paper does not specify how to derive the numbers it acts on from binary or other content.

See also

Notes

  1. ↑ Matthew D. Russell (27 February 2004). "Tinyness: An Overview of TEA and Related Ciphers". Archived from the original on 12 August 2007.
  2. 1 2 Kelsey, John; Schneier, Bruce; Wagner, David (1997). "Related-key cryptanalysis of 3-WAY, Biham-DES,CAST, DES-X, NewDES, RC2, and TEA". Information and Communications Security. Lecture Notes in Computer Science. Vol. 1334. pp. 233–246. CiteSeerX   10.1.1.35.8112 . doi:10.1007/BFb0028479. ISBN   978-3-540-63696-0.
  3. ↑ Bogdanov, Andrey; Wang, Meiqin (2012). "Zero Correlation Linear Cryptanalysis with Reduced Data Complexity". Fast Software Encryption (PDF). Lecture Notes in Computer Science. Vol. 7549. pp. 29–48. doi:10.1007/978-3-642-34047-5_3. ISBN   978-3-642-34046-8.
  4. 1 2 3 Wheeler, David J.; Needham, Roger M. (16 December 1994). "TEA, a tiny encryption algorithm". Fast Software Encryption. Lecture Notes in Computer Science. Vol. 1008. Leuven, Belgium. pp. 363–366. doi:10.1007/3-540-60590-8_29. ISBN   978-3-540-60590-4.{{cite book}}: CS1 maint: location missing publisher (link)
  5. ↑ Kelsey, John; Schneier, Bruce; Wagner, David (1996). "Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES". Advances in Cryptology — CRYPTO '96 (PDF). Lecture Notes in Computer Science. Vol. 1109. pp. 237–251. doi:10.1007/3-540-68697-5_19. ISBN   978-3-540-61512-5. Archived from the original (PDF) on 8 February 2012. Retrieved 25 February 2008.
  6. ↑ Michael Steil. "17 Mistakes Microsoft Made in the Xbox Security System". Archived from the original on 16 April 2009.

Related Research Articles

Blowfish is a symmetric-key block cipher, designed in 1993 by Bruce Schneier and included in many cipher suites and encryption products. Blowfish provides a good encryption rate in software, and no effective cryptanalysis of it has been found to date. However, the Advanced Encryption Standard (AES) now receives more attention, and Schneier recommends Twofish for modern applications.

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

<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.

In cryptography, RC4 is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, rendering it insecure. It is especially vulnerable when the beginning of the output keystream is not discarded, or when nonrandom or related keys are used. Particularly problematic uses of RC4 have led to very insecure protocols such as WEP.

<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">GOST (block cipher)</span> Soviet/Russian national standard block cipher

The GOST block cipher (Magma), defined in the standard GOST 28147-89, is a Soviet and Russian government standard symmetric key block cipher with a block size of 64 bits. The original standard, published in 1989, did not give the cipher any name, but the most recent revision of the standard, GOST R 34.12-2015, specifies that it may be referred to as Magma. The GOST hash function is based on this cipher. The new standard also specifies a new 128-bit block cipher called Kuznyechik.

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

In cryptography, XTEA 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. It is not subject to any patents.

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.

One-key MAC (OMAC) is a family of message authentication codes constructed from a block cipher much like the CBC-MAC algorithm. It may be used to provide assurance of the authenticity and, hence, the integrity of data. Two versions are defined:

<span class="mw-page-title-main">MD4</span> Cryptographic hash function

The MD4 Message-Digest Algorithm is a cryptographic hash function developed by Ronald Rivest in 1990. The digest length is 128 bits. The algorithm has influenced later designs, such as the MD5, SHA-1 and RIPEMD algorithms. The initialism "MD" stands for "Message Digest".

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

In cryptography, DES-X is a variant on the DES symmetric-key block cipher intended to increase the complexity of a brute-force attack. The technique used to increase the complexity is called key whitening.

In cryptography, NewDES is a symmetric key block cipher. It was created in 1984–1985 by Robert Scott as a potential DES replacement.

Bart Preneel is a Belgian cryptographer and cryptanalyst. He is a professor at Katholieke Universiteit Leuven, in the COSIC group.

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.

<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.

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.

PRESENT is a lightweight block cipher, developed by the Orange Labs (France), Ruhr University Bochum (Germany) and the Technical University of Denmark in 2007. PRESENT was designed by Andrey Bogdanov, Lars R. Knudsen, Gregor Leander, Christof Paar, Axel Poschmann, Matthew J. B. Robshaw, Yannick Seurin, and C. Vikkelsoe. The algorithm is notable for its compact size.

Prince is a block cipher targeting low latency, unrolled hardware implementations. It is based on the so-called FX construction. Its most notable feature is the alpha reflection: the decryption is the encryption with a related key which is very cheap to compute. Unlike most other "lightweight" ciphers, it has a small number of rounds and the layers constituting a round have low logic depth. As a result, fully unrolled implementation are able to reach much higher frequencies than AES or PRESENT. According to the authors, for the same time constraints and technologies, PRINCE uses 6–7 times less area than PRESENT-80 and 14–15 times less area than AES-128.

References

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.