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

<span class="mw-page-title-main">International Data Encryption Algorithm</span>

In cryptography, the International Data Encryption Algorithm (IDEA), originally called Improved Proposed Encryption Standard (IPES), is a symmetric-key block cipher designed by James Massey of ETH Zurich and Xuejia Lai and was first described in 1991. The algorithm was intended as a replacement for the Data Encryption Standard (DES). IDEA is a minor revision of an earlier cipher Proposed Encryption Standard (PES).

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

In cryptography, Triple DES, officially the Triple Data Encryption Algorithm, is a symmetric-key block cipher, which applies the DES cipher algorithm three times to each data block. The Data Encryption Standard's (DES) 56-bit key is no longer considered adequate in the face of modern cryptanalytic techniques and supercomputing power. A CVE released in 2016, CVE-2016-2183 disclosed a major security vulnerability in DES and 3DES encryption algorithms. This CVE, combined with the inadequate key size of DES and 3DES, led to NIST deprecating DES and 3DES for new applications in 2017, and for all applications by the end of 2023. It has been replaced with the more secure, more robust AES.

In cryptography, an S-box (substitution-box) is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext, thus ensuring Shannon's property of confusion. Mathematically, an S-box is a nonlinear vectorial Boolean function.

<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, where it was 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.

<span class="mw-page-title-main">One-key MAC</span>

One-key MAC (OMAC) is a message authentication code constructed from a block cipher much like the CBC-MAC algorithm.

<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">RC2</span> Block cipher

In cryptography, RC2 is a symmetric-key block cipher designed by Ron Rivest in 1987. "RC" stands for "Ron's Code" or "Rivest Cipher"; other ciphers designed by Rivest include RC4, RC5, and RC6.

In cryptography, the eXtended Sparse Linearization (XSL) attack is a method of cryptanalysis for block ciphers. The attack was first published in 2002 by researchers Nicolas Courtois and Josef Pieprzyk. It has caused some controversy as it was claimed to have the potential to break the Advanced Encryption Standard (AES) cipher, also known as Rijndael, faster than an exhaustive search. Since AES is already widely used in commerce and government for the transmission of secret information, finding a technique that can shorten the amount of time it takes to retrieve the secret message without having the key could have wide implications.

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 Flemish cryptographer and cryptanalyst. He is a professor at Katholieke Universiteit Leuven, in the COSIC group.

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

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.

References