  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.
