# Is Joux's multicollision attack applicable for truncated SHA256?

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?

• Hint; what's a multicollision for SHA-70? Understand that and you'll be able to answer this homework. – fgrieu May 22 '20 at 8:06
• @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. – Anonymous May 22 '20 at 8:25
• 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? – fgrieu May 22 '20 at 8:53