ABSTRACT
In practice, cryptanalytic attacks based on the birthday paradox are often limited by the amount of memory they require. Indeed, the time and memory requirements of birthday paradox based attacks are roughly the same and for practical purposes, memory costs much more than time. Of course, when looking for collisions involving functions, we can use the techniques of Chapter 7, however, their range of applicability is limited. In this chapter, we study other specific instances of the birthday-based attacks for which the techniques of Chapter 7 cannot be applied, but which, nonetheless can be tackled using less memory than the generic methods of Chapter 6. These techniques presented here reduce the required amount of memory, without significantly increasing the running times. In fact, even when there is enough memory available to perform a generic birthday attack, using these variations may improve performance, due to cache effects.
