Abstract
Ivan Damgård [4] suggested at Crypto’89 concrete examples of hash functions including, among others, a knapsack scheme. In [3], P. Camion and myself have shown how to break this scheme with a number of computations in the region of 232 and about 128 Gigabytes of memory. More precisely in [3] we showed how to find an x such that h(x) = b, for a fixed and average b. (1).
But in order to show that h is not collision free, we have just to find x and y, x ≠ y such that h(x) = h(y). (2). This is a weaker condition than (1).
We will see in this paper how to find (2) with a number in the region of 224 computations and about 512 Megabytes of memory. That is to say with about 256 times less computation and memory than [3]. Moreover, ways to extend our algorithm to other knapsacks than that (256, 128) suggested by Damgård are investigated.
Then we will see that for solving problems like (1) or (2) for various knapsacks it is also possible to use less memory if we are allowed to use a little more computing time. This is a usefull remark since the memory needed was the main problem of the algorithms of [3].
Finally, at the end of this paper, we will briefly study some ideas on how to avoid all these attacks by slightly modifying the knapsack Hash functions. However some different attacks could appear, and it is not so easy to find a colision free Hash function, both very quick and with very simple Mathematic expression.
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
P. Camion, “Can a Fast Signature Scheme Without Secret Key be Secure?”, in AAECC-2, Lecture Notes in Computer Science no 228, Springer Verlag.
P. Camion and Ph. Godlewski, “Manipulation and Errors, Localization and Detection”, Proceedings of Eurocrypt’88, Lecture Notes in Computer Science n0 330, Springer Verlag.
P. Camion and J. Patarin, “The Knapsack Hash Function proposed at Crypto’ 89 can be broken”, Proceedings of Eurocrypt’91, pp. 39–53, Springer Verlag.
I. Damgård, “Design Principles for Hash Functions”, Proceedings of Crypto’89, Springer Verlag.
R.L. Rivest, “The MD4 Message Digest Algorithm”, Crypto’90, Springer Verlag, pp. 303–311.
G. Zémor, “Hash Functions and Graphs with Large Girths”, Proceedings of EURO-CRYPT’91, pp 508–511, Springer Verlag.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Patarin, J. (1994). How to Find and Avoid Collisions for the Knapsack Hash Function. In: Helleseth, T. (eds) Advances in Cryptology — EUROCRYPT ’93. EUROCRYPT 1993. Lecture Notes in Computer Science, vol 765. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48285-7_27
Download citation
DOI: https://doi.org/10.1007/3-540-48285-7_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57600-6
Online ISBN: 978-3-540-48285-7
eBook Packages: Springer Book Archive