Is TEA considered secure?

Question

Wikipedia claims that the best attack on the surprisingly simple TEA block cipher, that isn't a related-key attack, has a time complexity of $2^{121.5}$.

So despite how unsophisticated the cipher looks, if I use a KDF properly and don't use related keys, TEA is secure?

Answer 1

Yes, AFAIK the original TEA is safe and generally fine when

• keys are random (key change should be atomic and with a fresh random key);
• the 64-bit block size is not a concern (say, an operating mode other than ECB is used and the key is changed before a gigabyte worth of data);
• the relative slowness is not a show-stopper;
• side-channels are not an issue, or are taken care of (which is not especially hard; in particular TEA is inherently immune to timing attacks).

I'm not aware of any attack in a random key setup requiring much less work than $2^{126}$ encryptions (as required for brute force given known equivalent keys). The best result I know is Jiazhe Chen, Meiqin Wang and Bart Preneel's Impossible Differential Cryptanalysis of the Lightweight Block Ciphers TEA, XTEA and HIGHT (AfricaCrypt 2012) (alternate link to free, updated paper), which claims success against 17 rounds out of 64. This suggests there is some safety margin.

Vikram R. Andem's thesis (University of Chicago, 2003) also concluded TEA is safe, but the work is a bit outdated.

---

Answering the comment, reasons TEA is not much used:

1. TEA came much after DES, which was standard and pushed by authorities (initially, because DES could be broken if needed due to its purposely small key size).
2. 3DES is adequate for many uses, and most importantly is standard.
3. TEA came significantly after IDEA, which was faster on most CPUs of the time.
4. The security claims made by David J. Wheeler and Roger M. Needham in TEA, a Tiny Encryption Algorithm (proceedings of FSE 1994) where non-committing ("It is hoped it is safe") and came only with very basic justification.
5. TEA was not defined in a manner suitable for interoperability: the mapping of octet strings to key and data has no standard definition (if I want TEA test vectors as octet strings endorsed by some official body, I do not know where to look! DES is much better in this regard). Even the number of rounds was not carved into stone: the article says "sixteen cycles may suffice and we suggest 32"; notice that this sentence recommends 64 rounds!
6. TEA quickly turned out to be vulnerable under related-key attacks. This is not a problem when the key is random, but does not inspire confidence (especially since that, and the trivial equivalent keys, was not considered in the original article).
7. XTEA was introduced shortly after TEA to fix related-keys attacks; XTEA did not meet its design goals, and needed a correction XXTEA; the later lost some of the simplicity of TEA, and requires slightly more rounds for equivalent security under random key when used as a 128-bit block cipher; also, XXTEA is badly broken in its wide-block variant (essentially because it uses too few rounds), see Elias Yarrkov's Cryptanalysis of XXTEA (2010).
8. Each TEA key has a trivial equivalent key; normally this is a non-issue (when keys are 8-octet strings, DES is much worse); but amazingly, one of the few notable uses of TEA (as a building block in a poorly designed hash used in the original XBOX) fell precisely because of that!
9. The above 4..8 tarnished the image of TEA (decision-maker often choose ciphers based on how they perceive its security or professionalism, or even on how they believe customers will perceive the choice!); 5 and 7 even created confusion about what TEA actually is (as illustrated by linking to the wrong algorithm in the initial question, and my mistake about the number of rounds in my initial answer).
10. In hardware, TEA would be high-latency (and thus slow in CBC, OFB, CFB modes), because of its many rounds; as a mater of fact (and perhaps consequence) there is no hardware for TEA when there is for DES, 3DES and AES, including for the later in many modern CPUs; that often makes TEA much slower than competitors.
11. Nowadays, 64-bit ciphers are passé.

Note: The most recent related-key attack on TEA that I know is by John Kelsey, Bruce Schneier, and David Wagner, Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, and TEA (ICICS 1997); it claims success with only $2^{23}$ chosen plaintexts and single related key query, but of a kind quite unrealistic: the related key swaps the halves of the original, plus other minute changes. However attacks only get better, and any key used for TEA really should be random.