Abstract
T-functions were introduced by Klimov and Shamir in a series of papers during the last few years. They are of great interest for cryptography as they may provide some new building blocks which can be used to construct efficient and secure schemes, for example block ciphers, stream ciphers or hash functions.
In the present paper, we define the narrowness of a T-function and study how this property affects the strength of a T-function as a cryptographic primitive. We define a new data strucure, called a solution graph, that enables solving systems of equations given by T-functions. The efficiency of the algorithms which we propose for solution graphs depends significantly on the narrowness of the involved T-functions. Thus the subclass of T-functions with small narrowness appears to be weak and should be avoided in cryptographic schemes.
Furthermore, we present some extensions to the methods of using solution graphs, which make it possible to apply these algorithms also to more general systems of equations, which may appear, for example, in the cryptanalysis of hash functions.
Chapter PDF
Similar content being viewed by others
References
Daum, M.: Cryptanalysis of Hash Functions of the MD4-Family. PhD Thesis, Ruhr-University Bochum (in preparation)
Daum, M.: Narrow T-functions. Cryptology ePrint Archive, Report 2005/016 (available under, http://eprint.iacr.org/2005/016 )
Dobbertin, H.: The status of MD5 after a recent attack. CryptoBytes 2(2), 1–6 (1996)
Dobbertin, H.: RIPEMD with two-round compress function is not collision-free. Journal of Cryptology 10, 51–68 (1997)
Dobbertin, H.: Cryptanalysis of MD4. Journal of Cryptology 11, 253–274 (1998)
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. Springer, Heidelberg (2004)
Klimov, A.B., 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.: Applications of T-functions in Cryptography. PhD Thesis, Weizmann Institute of Science (2004) (submitted) , available under http://www.wisdom.weizmann.ac.il/~ask/
Wegener, I.: Branching Programs and Binary Decision Diagrams: Theory and Applications. In: SIAM Monographs on Discrete Mathematics and Applications (2000)
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
Daum, M. (2005). Narrow T-Functions. In: Gilbert, H., Handschuh, H. (eds) Fast Software Encryption. FSE 2005. Lecture Notes in Computer Science, vol 3557. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11502760_4
Download citation
DOI: https://doi.org/10.1007/11502760_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26541-2
Online ISBN: 978-3-540-31669-5
eBook Packages: Computer ScienceComputer Science (R0)