Cryptanalysis of TEA Using Quantum-Inspired Genetic Algorithms

Wei Hu
DOI: 10.4236/jsea.2010.31006                

Abstract

The Tiny Encryption Algorithm (TEA) is a Feistel block cipher well known for its simple implementation, small memory footprint, and fast execution speed. In two previous studies, genetic algorithms (GAs) were employed to investigate the randomness of TEA output, based on which distinguishers for TEA could be designed. In this study, we used quan-tum-inspired genetic algorithms (QGAs) in the cryptanalysis of TEA. Quantum chromosomes in QGAs have the advan-tage of containing more information than the binary counterpart of the same length in GAs, and therefore generate a more diverse solution pool. We showed that QGAs could discover distinguishers for reduced cycle TEA that are more efficient than those found by classical GAs in two earlier studies. Furthermore, we applied QGAs to break four-cycle and five-cycle TEAs, a considerably harder problem, which the prior GA approach failed to solve.

Keywords

Cryptanalysis, Distinguisher, Feistel Block Cipher, Genetic Algorithms, Optimization, Quantum Computing, TEA

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	D. Wheeler, and R. Needham, “TEA, a tiny encryption algorithm,” Proceedings of the 1995 Fast Software En-cryption Workshop, Springer-Verlag, pp. 97–110, 1995.
[2]	S. J. Shepherd, “The tiny encryption algorithm,” Journal of Cryptologia, Vol. 31, No. 3, pp. 233–245, July 2007.
[3]	D. Wagner, J. Kelsey, and B. Schneier, “Related-key cryptoanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2 and TEA,” Proceedings of the IClCS’97 Conference, Springer-Verlag, pp. 233–246, 1997.
[4]	F. Yang, J. Song, and H. Zhang, “Quantitative cryptana-lysis of six-round DES using evolutionary algorithms,” Proceedings of the 3rd International Symposium on Ad-vances in Computation and Intelligence, LNCS Vol. 5370, Springer-Verlag, pp. 134–141, 2008.
[5]	E. Biham and A. Shamir, “Differential cryptanalysis of DES-like cryptosystems,” CRYPTO’90, LNCS 537, Springer-Verlag, pp. 2–21, 1991.
[6]	J. Song, H. Zhang, Q. Meng, and Z. Wang, “Cryptanaly-sis of two-round DES using genetic algorithms,” ISICA’07: International Symposium on Intelligence Computation and Applications, LNCS, Springer-Verlag, Vol. 4683, pp. 583–590, 2007.
[7]	J. Song, H. Zhang, Q. Meng, and Z. Wang, “Cryptanalysis of four-round DES based on genetic algorithms,” Pro-ceedings of the International Conference on Wireless Communications, Networking and Mobile Computing, Springer-Verlag, LNCS, Vol. 4683, pp. 583–590, 2007.
[8]	J. Holland, “Adaptation in natural and artificial systems,” Ann Arbor, MI: University of Michigan Press, 1975.
[9]	S. Hong, D. Hong, Y. Ko, D. Chang, W. Lee, and S. Lee, “Differential cryptanalysis of TEA and XTEA,” ICISC 2003, LNCS 2971, Springer-Verlag, pp. 402–417, 2004.
[10]	E. Biham, A. Biryukov, and A. Shamir, “Cryptanalysis of skipjack reduced to 31 rounds using impossible differen-tials,” Advances in Cryptology – EUROCRYT’99, LNCS, Springer-Verlag, Vol. 1592, pp. 12–23, 1994.
[11]	D. Moon, K. Hwang, W. Lee, S. Lee, and J. Lim, “Im-possible differential cryptanalysis of reduced round XTEA and TEA,” Fast Software Encryption, LNCS, Springer-Verlag, Vol. 2365. pp. 49–60, 2002.
[12]	L. Knudsen and W. Meier, “Correlations in RC6 with a reduced number of rounds,” Proceedings of the Seventh Fast Software Encryption Workshop, Springer-Verlag, 2000.
[13]	J. C. Hernandez and P. Isasi, “Finding efficient distin-guishers for cryptographic mappings, with an application to the block cipher TEA,” Proceedings of the 2003 Con-gress on Evolutionary Computation CEC2003, pp. 341–348, IEEE Press, 2003.
[14]	A. Garrett, J. Hamilton, and G. Dozier, “Genetic algorithm techniques for the cryptanalysis of TEA,” International Journal on Intelligent Control and Systems Special Session on Information Assurance. Vol. 12, pp. 325–330, 2007.
[15]	J. J. Grefenstette, “Optimization of control parameters for genetic algorithms,” IEEE Transactions on Systems, Man, and Cybernetics, Vol. 16, No. 1, pp. 122–128, 1986.
[16]	R. Penrose, “Shadows of the mind,” Oxford University Press, 1994.
[17]	K. H. Han and J. H. Kim, “Introduction of quantum-inspired evolutionary algorithm,” in Proceedings of the 2002 FIRA Robot World Congress, pp. 243–248, May 2002.
[18]	S. Y. Yang and L. C. Jiao, “The quantum evolutionary programming,” Proceedings of the 5th International Con-ference on Computational Intelligence and Multimedia Applications (ICCIMA’03), pp. 362–367, 2003.
[19]	National Bureau of Standards, Data Encryption Standard, U.S. Department of Commerce, FIPS, Vol. 46, January 1977.