Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions
- Type
- Paper
- Tags
- cryptography
- Indexed on
- Mar 25, 2013
- URL
- http://web.cecs.pdx.edu/~teshrim/spring06/papers/general-attacks/multi-joux.pdf
- File name
- multi-joux.pdf
- File size
- 180.4 KB
- MD5
- 04b96b431354b00725d24fffced96c7c
- SHA1
- 8d767e5daee98ba1879b8c8e66299b0e22c4fd95
In this paper, we study the existence of multicollisions in it- erated hash functions. We show that finding multicollisions, i.e. r-tuples of messages that all hash to the same value, is not much harder than finding ordinary collisions, i.e. pairs of messages, even for extremely large values of r. More precisely, the ratio of the complexities of the attacks is approximately equal to the logarithm of r. Then, using large multi- collisions as a tool, we solve a long standing open problem and prove that concatenating the results of several iterated hash functions in or- der to build a larger one does not yield a secure construction. We also discuss the potential impact of our attack on several published schemes. Quite surprisingly, for subtle reasons, the schemes we study happen to be immune to our attack.
About us
Secdocs is a project aimed to index high-quality IT security and hacking documents. These are fetched from multiple data sources: events, conferences and generally from interwebs.
Statistics
Serving 8166 documents and 531.0 GB of hacking knowledge, indexed from 2419 authors from 163 security conferences.
Contribute
To support this site and keep it alive, you can click on the buttons below. Any help is really appreciated! This service is provided for free, but real money is needed to pay bills.
