Breaching Security of Full Round Tiny Encryption Algorithm

Introduction

Tiny encryption algorithm (TEA) makes use of feistel structure iterated large number of times with a 128-bit key. It uses addition and subtraction as reversible operations, and for mixing plaintext and key repetitively, a dual shift is used inside each round. A full round TEA must have 32 feistel cycles i.e. 64 rounds as prescribed by Wheeler and Needham (2005). Due to its small memory imprint and ease of implementation TEA has found its way in smart card, sensor nodes, embedded systems and other handheld devices. Israsena and Wongnamkum (2008) showed that TEA has come across low cost area requisite while consuming significantly less power than AES in secure RFID system. RFID tags have strict requirements, due to the cost related to silicon area. Developers of TEA has set key to 128-bit long so that simple search techniques of finding the relevant key can be prevented. However the block size of 64-bit in TEA limits the number of cipher text to 2^{64}. This gives us the scope of employing search attack that does not involve key as one of the parameter. We implemented a known-plaintext attack wherein we generated set of cipher text and we have corresponding set of plain text. Then we try to acquire as much information about plaintext as we can get from cipher text using statistical affiliation between plaintext and cipher text.

TEA has been scrutinized and attacked by many researchers. Amandeep and Geetha (2014) examined TEA against bit sum attack and presented a set of weak keys for which there are strong correlation between bit sum of cipher text and bit sum of key with particular pattern. Wei (2010) used quantum-inspired genetic algorithms (QGAs) in the cryptanalysis of TEA. Author used informative qubit chromosomes in QGAs to break four-cycle and five-cycle TEA. Garrett and Hamilton (2007) used genetic algorithms to find out whether TEA produces random out or not. Author has created efficient distinguishers for TEA with less than three cycles. Hernandez and Isasi (2004) proved TEA with less than five cycles as weak against the proposed distinguishers. Wagner, Kelsey and Schneier (1997) presented an attack that needs 2^{23} chosen plaintexts, 2^{32} offline computations and one related key query to recover entire TEA key. Author pools ideas from differential cryptanalysis and Biham’s key rotation attack. Reddy V. A. found some of the weakness in TEA but also concludes TEA as the best cryptographic algorithm for small devices when used with more than six rounds of feistel routines (Reddy, 2003). Moon et al. presented impossible differential cryptanalysis of TEA (Moon, Kpngdeok, 2002). Authors were able to find 128-bit key of 11 round TEA by exploiting the design simplicity of algorithm. Saarinen (1998) described differential attack on TEA that solves the secret key using 2^{34} chosen plaintext and with some computation.