Tiny Encryption Algorithm - Misplaced Pages

This article is about the Tiny Encryption Algorithm. Not to be confused with the TETRA encryption algorithm.Block cipher

TEA
General
Two Feistel rounds (one cycle) of TEA
Designers	Roger Needham, David Wheeler
First published	1994
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 2 chosen plaintexts and a time complexity of 2. The best structural cryptanalysis of TEA in the standard single secret key setting is the zero-correlation cryptanalysis breaking 21 rounds in 2 time with less than the full code book

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.

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 ⌊2⁄𝜙⌋, where 𝜙 is the golden ratio (as a nothing-up-my-sleeve number).

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. 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. TEA is also susceptible to a related-key attack which requires 2 chosen plaintexts under a related-key pair, with 2 time complexity. 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:

#include <stdint.h>
void encrypt (uint32_t v, const uint32_t k) {
    uint32_t v0=v, v1=v, sum=0, i;           /* set up */
    uint32_t delta=0x9E3779B9;                     /* a key schedule constant */
    uint32_t k0=k, k1=k, k2=k, k3=k;   /* 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=v0; v=v1;
}
void decrypt (uint32_t v, const uint32_t k) {
    uint32_t v0=v, v1=v, sum=0xC6EF3720, i;  /* set up; sum is (delta << 5) & 0xFFFFFFFF */
    uint32_t delta=0x9E3779B9;                     /* a key schedule constant */
    uint32_t k0=k, k1=k, k2=k, k3=k;   /* 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=v0; v=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.

Notes

Matthew D. Russell (27 February 2004). "Tinyness: An Overview of TEA and Related Ciphers". Archived from the original on 12 August 2007.
^ 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.
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.
^ 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)
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.
Michael Steil. "17 Mistakes Microsoft Made in the Xbox Security System". Archived from the original on 16 April 2009.

References

Andem, Vikram Reddy (2003). "A Cryptanalysis of the Tiny Encryption Algorithm, Masters thesis" (PDF). Tuscaloosa: The University of Alabama.
Hernández, Julio César; Isasi, Pedro; Ribagorda, Arturo (2002). "An application of genetic algorithms to the cryptoanalysis of one round TEA". Proceedings of the 2002 Symposium on Artificial Intelligence and Its Application.
Hernández, Julio César; Sierra, José María; Isasi, Pedro; Ribargorda, Arturo (2003). "Finding efficient distinguishers for cryptographic mappings, with an application to the block cipher TEA". The 2003 Congress on Evolutionary Computation, 2003. CEC '03. Vol. 3. pp. 2189–2193. doi:10.1109/CEC.2003.1299943. hdl:10016/3944. ISBN 978-0-7803-7804-9. S2CID 62216777.
Hernández, Julio César; Sierra, José María; Ribagorda, Arturo; Ramos, Benjamín; Mex-Perera, J. C. (2001). "Distinguishing TEA from a Random Permutation: Reduced Round Versions of TEA do Not Have the SAC or do Not Generate Random Numbers". Cryptography and Coding (PDF). Lecture Notes in Computer Science. Vol. 2260. pp. 374–377. doi:10.1007/3-540-45325-3_34. ISBN 978-3-540-43026-1. Archived from the original (PDF) on 26 April 2012.
Moon, Dukjae; Hwang, Kyungdeok; Lee, Wonil; Lee, Sangjin; Lim, Jongin (2002). "Impossible Differential Cryptanalysis of Reduced Round XTEA and TEA". Fast Software Encryption (PDF). Lecture Notes in Computer Science. Vol. 2365. pp. 49–60. doi:10.1007/3-540-45661-9_4. ISBN 978-3-540-44009-3.
Hong, Seokhie; Hong, Deukjo; Ko, Youngdai; Chang, Donghoon; Lee, Wonil; Lee, Sangjin (2004). "Differential Cryptanalysis of TEA and XTEA". Information Security and Cryptology - ICISC 2003. Lecture Notes in Computer Science. Vol. 2971. pp. 402–417. doi:10.1007/978-3-540-24691-6_30. ISBN 978-3-540-21376-5.

External links

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

Categories: