Preimages for Step-Reduced SHA-2

Kazumaro Aoki, Jian Guo, Krystian Matusiewicz, Yu Sasaki, Lei Wang

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

    Abstract

    In this paper, we present preimage attacks on up to 43-step SHA-256 (around 67% of the total 64 steps) and 46-step SHA-512 (around 57.5% of the total 80 steps), which significantly increases the number of attacked steps compared to the best previously published preimage attack working for 24 steps. The time complexities are 2^251.9, 2^509 for finding pseudo-preimages and 2^254.9, 2^511.5 compression function operations for full preimages. The memory requirements are modest, around 2^6 words for 43-step SHA-256 and 46-step SHA-512. The pseudo-preimage attack also applies to 43-step SHA-224 and SHA-384. Our attack is a meet-in-the-middle attack that uses a range of novel techniques to split the function into two independent parts that can be computed separately and then matched in a birthday-style phase.
    Original languageEnglish
    Title of host publicationAdvances in Cryptology -- ASIACRYPT 2009
    EditorsMitsuru Matsui
    Number of pages722
    Volume5912
    PublisherSpringer
    Publication date2009
    Pages578-597
    ISBN (Print)978-3-642-10365-0
    DOIs
    Publication statusPublished - 2009
    Event15th Annual International Conference on the Theory and Application of Cryptology and Information Security - Tokyo, Japan
    Duration: 6 Dec 200910 Dec 2009
    Conference number: 15
    http://asiacrypt2009.cipher.risk.tsukuba.ac.jp/

    Conference

    Conference15th Annual International Conference on the Theory and Application of Cryptology and Information Security
    Number15
    CountryJapan
    CityTokyo
    Period06/12/200910/12/2009
    Internet address
    SeriesLecture Notes in Computer Science
    Number5912
    ISSN0302-9743

    Fingerprint

    Dive into the research topics of 'Preimages for Step-Reduced SHA-2'. Together they form a unique fingerprint.

    Cite this