Tiny Encryption Algorithm

From Wikipedia, the free encyclopedia

Jump to: navigation, search
This article is about the TEA encryption algorithm. For other meanings, see TEA (disambiguation).
TEA

Two Feistel rounds (one cycle) of TEA
General
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 (Kelsey et al, 1996) and can be broken using a related-key attack requiring 223 chosen plaintexts and a time complexity of 232.[1]

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

The cipher is not subject to any patents.

Contents

[edit] Properties

TEA operates on 64-bit blocks 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 9E3779B916 is chosen to be \lfloor 2^{32}/\phi\rfloor where \phi\, is the golden ratio.

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.[3] 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.[4] TEA is also susceptible to a related-key attack which requires 223 chosen plaintexts under a related-key pair, with 232 time complexity.[1] Because of these weaknesses, a number of revisions of TEA have been designed.

The unusually small size of the TEA 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.

[edit] Versions

The first published version of TEA was supplemented by a second version that incorporated extensions to make it more secure. Block TEA (sometimes referred to as 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.

[edit] 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, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0, i;           /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t k0=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;
}
 
void decrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0xC6EF3720, i;  /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t k0=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 is bound to specific microprocessor architecture meaning that byte order considerations are important when cyphertext is shared and processed on different systems. The original paper does not specify any details about microprocessor architecture and so anyone implementing a system using TEA would need to make those specifications for themselves.

[edit] See also

  • RC4 - A stream cipher that, just like TEA, is designed to be very simple to implement.
  • XTEA - First version of Block TEA's successor.
  • XXTEA - Corrected Block TEA's successor.

[edit] References

  1. ^ a b Kelsey, John; Schneier, Bruce; Wagner, David (1997). "Related-key cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X NewDES, RC2, and TEA". Lecture Notes in Computer Science 1334: 233–246. doi:10.1007/BFb0028479. http://citeseer.ist.psu.edu/318172.html. 
  2. ^ Wheeler, David J.; Needham, Roger M. (1994-12-16). "TEA, a tiny encryption algorithm". Lecture Notes in Computer Science (Leuven, Belgium: Fast Software Encryption: Second International Workshop) 1008: 363–366. http://citeseer.ist.psu.edu/102148.html. 
  3. ^ Kelsey, John; Schneier, Bruce; Wagner, David (1996). "Key-schedule cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES". Lecture Notes in Computer Science 1109: 237–251. doi:10.1007/3-540-68697-5_19. http://www.schneier.com/paper-key-schedule.pdf. 
  4. ^ Michael Steil. "17 Mistakes Microsoft Made in the Xbox Security System". http://www.xbox-linux.org/wiki/17_Mistakes_Microsoft_Made_in_the_Xbox_Security_System#Startup_Security.2C_Take_Two. 

[edit] Other References

[edit] External links

v • d • e
 
Block ciphers

Common algorithms: AES | Blowfish | DES | Triple DES | Serpent | Twofish

Other algorithms: 3-Way | ABC | Akelarre | Anubis | ARIA | BaseKing | BassOmatic | BATON | BEAR and LION | C2 | Camellia | CAST-128 | CAST-256 | CIKS-1 | CIPHERUNICORN-A | CIPHERUNICORN-E | CLEFIA | CMEA | Cobra | COCONUT98 | Crab | CRYPTON | CS-Cipher | DEAL | DES-X | DFC | E2 | FEAL | FEA-M | FROG | G-DES | GOST | Grand Cru | Hasty Pudding cipher | Hierocrypt | ICE | IDEA | IDEA NXT | Intel Cascade Cipher | Iraqi | KASUMI | KeeLoq | KHAZAD | Khufu and Khafre | KN-Cipher | Ladder-DES | Libelle | LOKI97 | LOKI89/91 | Lucifer | M6 | M8 | MacGuffin | Madryga | MAGENTA | MARS | Mercy | MESH | MISTY1 | MMB | MULTI2 | MultiSwap | New Data Seal | NewDES | Nimbus | NOEKEON | NUSH | Q | RC2 | RC5 | RC6 | REDOC | Red Pike | S-1 | SAFER | SAVILLE | SC2000 | SEED | SHACAL | SHARK | Skipjack | SMS4 | Spectr-H64 | Square | SXAL/MBAL | Threefish | TEA | Treyfer | UES | Xenon | xmx | XTEA | XXTEA | Zodiac

Standardization: AES process | CRYPTREC | NESSIE
v • d • e
 
Cryptography
Retrieved from "http://en.wikipedia.org/wiki/Tiny_Encryption_Algorithm"
Personal tools