How to Find and Avoid Collisions for the Knapsack Hash Function

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.