Memoryless Near-Collisions, Revisited
This work addresses incremental improvements in cryptographic security analysis for researchers in cryptography.
The paper analyzes the trade-off between truncated bits and success probability in memoryless near-collision finding for cryptographic hash functions, and shows that memoryless methods cannot match the query complexity of memory-full approaches.
In this paper we discuss the problem of generically finding near-collisions for cryptographic hash functions in a memoryless way. A common approach is to truncate several output bits of the hash function and to look for collisions of this modified function. In two recent papers, an enhancement to this approach was introduced which is based on classical cycle-finding techniques and covering codes. This paper investigates two aspects of the problem of memoryless near-collisions. Firstly, we give a full treatment of the trade-off between the number of truncated bits and the success-probability of the truncation based approach. Secondly, we demonstrate the limits of cycle-finding methods for finding near-collisions by showing that, opposed to the collision case, a memoryless variant cannot match the query-complexity of the "memory-full" birthday-like near-collision finding method.