Cryptanalysis of MDC-2

Lars Ramkilde Knudsen, Florian Mendel, Christian Rechberger, Søren Steffen Thomsen

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


    We provide a collision attack and preimage attacks on the MDC-2 construction, which is a method (dating back to 1988) of turning an $n$-bit block cipher into a $2n$-bit hash function. The collision attack is the first below the birthday bound to be described for MDC-2 and, with $n=128$, it has complexity $2^{124.5}$, which is to be compared to the birthday attack having complexity $2^{128}$. The preimage attacks constitute new time/memory trade-offs; the most efficient attack requires time and space about $2^n$, which is to be compared to the previous best known preimage attack of Lai and Massey (Eurocrypt '92), having time complexity $2^{3n/2}$ and space complexity $2^{n/2}$, and to a brute force preimage attack having complexity $2^{2n}$.
    Original languageEnglish
    Title of host publicationAdvances in Cryptology - EUROCRYPT 2009 : 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26-30, 2009. Proceedings.
    EditorsAntoine Joux
    Place of PublicationBerlin / Heidelberg
    Publication date2009
    Publication statusPublished - 2009
    EventEUROCRYPT 2009 - Cologne, Germany
    Duration: 1 Jan 2009 → …


    ConferenceEUROCRYPT 2009
    CityCologne, Germany
    Period01/01/2009 → …
    SeriesLecture Notes in Computer Science


    Dive into the research topics of 'Cryptanalysis of MDC-2'. Together they form a unique fingerprint.

    Cite this