Abstract
Klimov and Shamir proposed a new class of simple cryptographic primitives named T-functions. For two concrete proposals based on the squaring operation, a single word T-function and a previously unbroken multi-word T-function with a 256-bit state, we describe an efficient distinguishing attack having a 232 data complexity. Furthermore, Hong et al. recently proposed two fully specified stream ciphers, consisting of multi-word T-functions with 128-bit states and filtering functions. We describe distinguishing attacks having a 222 and a 234 data complexity, respectively. The attacks have been implemented.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baignères, T., Junod, P., Vaudenay, S.: How far can we go beyond linear cryptanalysis? In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 432–450. Springer, Heidelberg (2004)
Benony, V., Recher, F., Wegrzynowski, E., Fontaine, C.: Cryptanalysis of a particular case of Klimov-Shamir pseudo-random generator. In: Helleseth, T., Sarwate, D., Song, H.-Y., Yang, K. (eds.) SETA 2004. LNCS, vol. 3486, pp. 313–322. Springer, Heidelberg (2005)
Hong, J., Lee, D., Yeom, Y., Han, D.: New class of single cycle T-functions and a stream cipher proposal. Presented at SASC – The State of the Art of Stream Ciphers, ECRYPT Workshop, Brugge, Belgium, October 14-15 (2004)
Hong, J., Lee, D., Yeom, Y., Han, D.: A new class of single cycle T-functions. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 68–82. Springer, Heidelberg (2005)
Junod, P.: On the optimality of linear, differential and sequential distinguishers. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 17–32. Springer, Heidelberg (2003)
Klimov, A.: Applications of T-functions in cryptography. PhD thesis, Department of Applied Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel (2004)
Klimov, A., Shamir, A.: A new class of invertible mappings. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 470–483. Springer, Heidelberg (2003)
Klimov, A., Shamir, A.: Cryptographic applications of T-functions. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, pp. 248–261. Springer, Heidelberg (2004)
Klimov, A., Shamir, A.: New cryptographic primitives based on multiword T-functions. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 1–15. Springer, Heidelberg (2004)
Klimov, A., Shamir, A.: The TFi family of stream ciphers. Technical note (2004)
Mantin, I., Shamir, A.: A practical attack on broadcast RC4. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 152–164. Springer, Heidelberg (2002)
Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
Mitra, J., Sarkar, P.: Time-memory trade-off attacks on multiplications and T-functions. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 468–482. Springer, Heidelberg (2004)
Peyrin, T., Muller, F.: Personal communication (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Künzli, S., Junod, P., Meier, W. (2005). Distinguishing Attacks on T-Functions. In: Dawson, E., Vaudenay, S. (eds) Progress in Cryptology – Mycrypt 2005. Mycrypt 2005. Lecture Notes in Computer Science, vol 3715. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11554868_2
Download citation
DOI: https://doi.org/10.1007/11554868_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28938-8
Online ISBN: 978-3-540-32066-1
eBook Packages: Computer ScienceComputer Science (R0)