Paper 2006/104
Fast Collision Attack on MD5
Marc Stevens
Abstract
In this paper, we present an improved attack algorithm to find two-block collisions of the hash function MD5. The attack uses the same differential path of MD5 and the set of sufficient conditions that was presented by Wang et al. We present a new technique which allows us to deterministically fulfill restrictions to properly rotate the differentials in the first round. We will present a new algorithm to find the first block and we will use an algorithm of Klima to find the second block. To optimize the inner loop of these algorithms we will optimize the set of sufficient conditions. We also show that the initial value used for the attack has a large influence on the attack complexity. Therefore a recommendation is made for 2 conditions on the initial value of the attack to avoid very hard situations if one has some freedom in choosing this initial value. Our attack can be done in an average of about 1 minute (avg. complexity
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- MD5collisiondifferential cryptanalysis
- Contact author(s)
- m m j stevens @ student tue nl
- History
- 2006-03-19: received
- Short URL
- https://ia.cr/2006/104
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2006/104,
author = {Marc Stevens},
title = {Fast Collision Attack on {MD5}},
howpublished = {Cryptology {ePrint} Archive, Paper 2006/104},
year = {2006},
url = {https://eprint.iacr.org/2006/104}
}
