Joux presents an elegant way to generate k-way multi-collisions with about as much effort as generating a single collision: https://www.iacr.org/archive/crypto2004/31520306/multicollisions.pdf

However, so far I have only found applications of this attack on full-length hash functions like SHA-256 or MD-5. Therefore, consider this following scenario:

An attacker wants to find a 2^70-way multicollision of the first 70 bits of a SHA-256 output. In essence, the output of SHA-256 is truncated to 70 bits (let's call this function SHA-70). Can Joux's multicollision attack be applicable in this scenario? If so, how much effort would be required?

  • $\begingroup$ Hint; what's a multicollision for SHA-70? Understand that and you'll be able to answer this homework. $\endgroup$ – fgrieu May 22 '20 at 8:06
  • $\begingroup$ @fgrieu I was thinking that a k-way multicollision for SHA-70 is basically finding k SHA-256 inputs that would produce k outputs that collide in the first 70 bits. $\endgroup$ – Anonymous May 22 '20 at 8:25
  • $\begingroup$ Then your $k$ is Joux's $2^t$, since that's how many inputs giving the same output his attack generates. Hint: what does $t$ count in Joux's attack as applied on SHA-256? Does the truncation to 70 bits change that? $\endgroup$ – fgrieu May 22 '20 at 8:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.