Abstract
Knudsen and Preneel (Asiacrypt’96 and Crypto’97) introduced a hash function design in which a linear error-correcting code is used to build a wide-pipe compression function from underlying blockciphers operating in Davies-Meyer mode. In this paper, we (re)analyse the preimage resistance of the Knudsen-Preneel compression functions in the setting of public random functions.
We give a new non-adaptive preimage attack, beating the one given by Knudsen and Preneel, that is optimal in terms of query complexity. Moreover, our new attack falsifies their (conjectured) preimage resistance security bound and shows that intuitive bounds based on the number of ‘active’ components can be treacherous.
Complementing our attack is a formal analysis of the query complexity (both lower and upper bounds) of preimage-finding attacks. This analysis shows that for many concrete codes the time complexity of our attack is optimal.
This work has been supported in part by the European Commission through the ICT programme under contract ICT-2007-216676 ECRYPT II.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Black, J., Rogaway, P., Shrimpton, T.: Black-box analysis of the block-cipher-based hash-function constructions from PGV. In: Yung [26], pp. 320–335
Camion, P., Patarin, J.: The Knapsack Hash Function proposed at Crypto 1989 can be broken. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 39–53. Springer, Heidelberg (1991)
Chose, P., Joux, A., Mitton, M.: Fast correlation attacks: An algorithmic point of view. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 209–221. Springer, Heidelberg (2002)
Dunkelman, O. (ed.): FSE 2009. LNCS, vol. 5665. Springer, Heidelberg (2009)
Fleischmann, E., Gorski, M., Lucks, S.: On the security of Tandem-DM. In: Dunkelman [4], pp. 84–103
Fleischmann, E., Gorski, M., Lucks, S.: Security of cyclic double block length hash functions. In: Parker [14], pp. 153–175
Knudsen, L., Muller, F.: Some attacks against a double length hash proposal. In: Roy, B.K. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 462–473. Springer, Heidelberg (2005)
Knudsen, L.R., Preneel, B.: Hash functions based on block ciphers and quaternary codes. In: Kim, K.-c., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 77–90. Springer, Heidelberg (1996)
Knudsen, L.R., Preneel, B.: Fast and secure hashing based on codes. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 485–498. Springer, Heidelberg (1997)
Knudsen, L.R., Preneel, B.: Construction of secure and fast hash functions using nonbinary error-correcting codes. IEEE Transactions on Information Theory 48(9), 2524–2539 (2002)
Matsumoto, R., Kurosawa, K., Itoh, T., Konno, T., Uyematsu, T.: Primal-dual distance bounds of linear codes with application to cryptography. IEEE Transactions on Information Theory 52(9), 4251–4256 (2006)
Nandi, M., Lee, W., Sakurai, K., Lee, S.: Security analysis of a 2/3-rate double length compression function in black-box model. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 243–254. Springer, Heidelberg (2005)
Özen, O., Stam, M.: Another glance at double-length hashing. In: Parker [14], pp. 176–201
Parker, M.G. (ed.): Cryptography and Coding 2009. LNCS, vol. 5921. Springer, Heidelberg (2009)
Peyrin, T., Gilbert, H., Muller, F., Robshaw, M.: Combining compression functions and block cipher-based hash functions. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 315–331. Springer, Heidelberg (2006)
Preneel, B., Govaerts, R., Vandewalle, J.: Hash functions based on block ciphers: A synthetic approach. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 368–378. Springer, Heidelberg (1994)
Rogaway, P., Shrimpton, T.: Cryptographic hash-function basics: Definitions, implications and separations for preimage resistance, second-preimage resistance, and collision resistance. In: Roy, B.K., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 371–388. Springer, Heidelberg (2004)
Rogaway, P., Steinberger, J.: Security/efficiency tradeoffs for permutation-based hashing. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 220–236. Springer, Heidelberg (2008)
Schroeppel, R., Shamir, A.: A T = O(2n/2), S = O(2n/4) algorithm for certain NP-complete problems. SIAM Journal on Computing 10, 456–464 (1981)
Seurin, Y., Peyrin, T.: Security analysis of constructions combining FIL random oracles. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 119–136. Springer, Heidelberg (2007)
Shrimpton, T., Stam, M.: Building a collision-resistant compression function from non-compressing primitives. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 643–654. Springer, Heidelberg (2008)
Stam, M.: Beyond uniformity: Better security/efficiency tradeoffs for compression functions. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 397–412. Springer, Heidelberg (2008)
Stam, M.: Block cipher based hashing revisited. In: Dunkelman [4], pp. 67–83
Wagner, D.: A generalized birthday problem. In: Yung [26], pp. 288–303
Watanabe, D.: A note on the security proof of Knudsen-Preneel construction of a hash function (unpublished manuscript) (2006), http://csrc.nist.gov/groups/ST/hash/documents/WATANABE_kp_attack.pdf
Yung, M. (ed.): CRYPTO 2002. LNCS, vol. 2442. Springer, Heidelberg (2002)
Yuval, G.: How to swindle Rabin. Cryptologia 3, 187–189 (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Özen, O., Shrimpton, T., Stam, M. (2010). Attacking the Knudsen-Preneel Compression Functions. In: Hong, S., Iwata, T. (eds) Fast Software Encryption. FSE 2010. Lecture Notes in Computer Science, vol 6147. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13858-4_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-13858-4_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13857-7
Online ISBN: 978-3-642-13858-4
eBook Packages: Computer ScienceComputer Science (R0)