Second Preimage Attacks on Dithered Hash Functions

<!DOCTYPE html> <html lang="en-us" xml:lang="en-us"> <head><script type="text/javascript" src="/_static/js/bundle-playback.js?v=HxkREWBo" charset="utf-8"></script> <script type="text/javascript" src="/_static/js/wombat.js?v=txqj7nKC" charset="utf-8"></script> <script>window.RufflePlayer=window.RufflePlayer||{};window.RufflePlayer.config={"autoplay":"on","unmuteOverlay":"hidden"};</script> <script type="text/javascript" src="/_static/js/ruffle/ruffle.js"></script> <script type="text/javascript"> __wm.init("https://web.archive.org/web"); __wm.wombat("https://csrc.nist.gov/pubs/conference/2008/04/17/second-preimage-attacks-on-dithered-hash-functions/final","20230923152623","https://web.archive.org/","web","/_static/", "1695482783"); </script> <link rel="stylesheet" type="text/css" href="/_static/css/banner-styles.css?v=S1zqJCYt" /> <link rel="stylesheet" type="text/css" href="/_static/css/iconochive.css?v=3PDvdIFv" />  <meta charset="utf-8"/> <title>Second Preimage Attacks on Dithered Hash Functions | CSRC</title> <meta http-equiv="content-type" content="text/html; charset=UTF-8"/> <meta http-equiv="content-style-type" content="text/css"/> <meta http-equiv="content-script-type" content="text/javascript"/> <meta name="viewport" content="width=device-width, initial-scale=1.0"/> <meta name="msapplication-config" content="/CSRC/Media/images/favicons/browserconfig.xml"/> <meta name="theme-color" content="#000000"/> <meta name="google-site-verification" content="xbrnrVYDgLD-Bd64xHLCt4XsPXzUhQ-4lGMj4TdUUTA"/> <meta description="We develop a new generic long-message second preimage attack, based on combining the techniques in the second preimage attacks of Dean and Kelsey and Schneier with the herding attack of Kelsey and Kohno. We show that these generic attacks apply to hash functions using the Merkle-Damg氓rd construction with only slightly more work than the previously known attack, but allow enormously more control of the contents of the second preimage found. Additionally, we show that our new attack applies to several hash function constructions which are not vulnerable to the previously known attack, including the dithered hash proposal of Rivest, Shoup s UOWHF and the ROX hash construction.We analyze the properties of the dithering sequence used in , and develop a time-memory tradeoff which allows us to apply our second preimage attack to a wide range of dithering sequences, including sequences which are much stronger than those in Rivest s proposals. Finally, we show that both the existing second preimage attacks and our new attack can be applied even more efficiently to multiple target messages; in general, given a set of many target messages with a total of 2^R message blocks, these second preimage attacks can find a second preimage for one of those target messages with no more work than would be necessary to find a second preimage for a single target message of 2^R message blocks."/>  <meta name="dcterms.title" content="Second Preimage Attacks on Dithered Hash Functions"/> <meta name="dcterms.description" content="We develop a new generic long-message second preimage attack, based on combining the techniques in the second preimage attacks of Dean and Kelsey and Schneier with the herding attack of Kelsey and Kohno. We show that these generic attacks apply to hash functions using the Merkle-Damg氓rd construction with only slightly more work than the previously known attack, but allow enormously more control of the contents of the second preimage found. Additionally, we show that our new attack applies to several hash function constructions which are not vulnerable to the previously known attack, including the dithered hash proposal of Rivest, Shoup s UOWHF and the ROX hash construction.We analyze the properties of the dithering sequence used in , and develop a time-memory tradeoff which allows us to apply our second preimage attack to a wide range of dithering sequences, including sequences which are much stronger than those in Rivest s proposals. Finally, we show that both the existing second preimage attacks and our new attack can be applied even more efficiently to multiple target messages; in general, given a set of many target messages with a total of 2^R message blocks, these second preimage attacks can find a second preimage for one of those target messages with no more work than would be necessary to find a second preimage for a single target message of 2^R message blocks."/>  <meta name="dcterms.creator" content="Author: Elena Andreeva"/> <meta name="dcterms.creator" content="Author: Charles Bouillaguet"/> <meta name="dcterms.creator" content="Author: Pierre-Alain Fouque"/> <meta name="dcterms.creator" content="Author: Jonathan Hoch"/> <meta name="dcterms.creator" content="Author: John Kelsey"/> <meta name="dcterms.creator" content="Author: Adi Shamir"/> <meta name="dcterms.creator" content="Author: S茅bastien Zimmer"/>  <meta name="dcterms.date.created" schema="ISO8601" content="2008-04-17"/> <meta name="dcterms.identifier" content="https://csrc.nist.gov/pubs/conference/2008/04/17/second-preimage-attacks-on-dithered-hash-functions/final"/> <meta name="dcterms.language" scheme="DCTERMS.RFC1766" content="EN-US"/>  <meta name="citation_title" content="Second Preimage Attacks on Dithered Hash Functions"/> <meta name="citation_publication_date" content="2008/04/17"/> <meta name="citation_doi" content="https://doi.org/10.1007/978-3-540-78967-3_16"/> <meta name="citation_publisher" content="Springer"/> <meta name="citation_firstpage" content="270"/> <meta name="citation_lastpage" content="288"/> <meta name="citation_keywords" content="cryptanalysis,dithering,hash function"/> <meta name="citation_language" content="en"/> <meta name="citation_pdf_url" content="https://doi.org/10.1007/978-3-540-78967-3_16"/> <meta name="citation_abstract_html_url" content="https://csrc.nist.gov/pubs/conference/2008/04/17/second-preimage-attacks-on-dithered-hash-functions/final"/> <meta name="citation_conference_title" content="27th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2008); 04/13/2008 - 04/17/2008; Istanbul, Turkey"/> <meta name="citation_inbook_title" content="Advances in Cryptology - EUROCRYPT 2008"/>  <meta name="citation_author" content="Andreeva, Elena"/> <meta name="citation_author" content="Bouillaguet, Charles"/> <meta name="citation_author" content="Fouque, Pierre-Alain"/> <meta name="citation_author" content="Hoch, Jonathan"/> <meta name="citation_author" content="Kelsey, John"/> <meta name="citation_author" content="Shamir, Adi"/> <meta name="citation_author" content="Zimmer, S茅bastien"/>  <meta name="og:site_name" content="CSRC | NIST"/> <meta name="og:type" content="article"/> <meta name="og:url" content="https://web.archive.org/web/20230923152623im_/https://csrc.nist.gov/pubs/conference/2008/04/17/second-preimage-attacks-on-dithered-hash-functions/final"/> <meta name="og:title" content="Second Preimage Attacks on Dithered Hash Functions"/> <meta name="og:description" content="We develop a new generic long-message second preimage attack, based on combining the techniques in the second preimage attacks of Dean and Kelsey and Schneier with the herding attack of Kelsey and Kohno. We show that these generic attacks apply to hash functions using the Merkle-Damg氓rd construction with only slightly more work than the previously known attack, but allow enormously more control of the contents of the second preimage found. Additionally, we show that our new attack applies to several hash function constructions which are not vulnerable to the previously known attack, including the dithered hash proposal of Rivest, Shoup s UOWHF and the ROX hash construction.We analyze the properties of the dithering sequence used in , and develop a time-memory tradeoff which allows us to apply our second preimage attack to a wide range of dithering sequences, including sequences which are much stronger than those in Rivest s proposals. Finally, we show that both the existing second..."/> <meta name="article:author" content="Andreeva, Elena"/> <meta name="article:author" content="Bouillaguet, Charles"/> <meta name="article:author" content="Fouque, Pierre-Alain"/> <meta name="article:author" content="Hoch, Jonathan"/> <meta name="article:author" content="Kelsey, John"/> <meta name="article:author" content="Shamir, Adi"/> <meta name="article:author" content="Zimmer, S茅bastien"/> <meta name="article:tag" content="cryptanalysis,dithering,hash function"/> <meta name="article:published_time" content="2008-04-17"/> <meta name="og:image" content="https://web.archive.org/web/20230923152623im_/https://csrc.nist.gov/CSRC/media/images/CSRC-logo-open-graph.png"/> <link rel="apple-touch-icon" sizes="180x180" href="/web/20230923152623im_/https://csrc.nist.gov/images/icons/apple-touch-icon.png"/> <link rel="icon" type="image/png" href="/web/20230923152623im_/https://csrc.nist.gov/images/icons/favicon-32x32.png" sizes="32x32"/> <link rel="icon" type="image/png" href="/web/20230923152623im_/https://csrc.nist.gov/images/icons/favicon-16x16.png" sizes="16x16"/> <link rel="manifest" href="/web/20230923152623/https://csrc.nist.gov/images/icons/manifest.json"/> <link rel="mask-icon" href="/web/20230923152623im_/https://csrc.nist.gov/images/icons/safari-pinned-tab.svg" color="#000000"/> <link href="/web/20230923152623im_/https://csrc.nist.gov/CSRC/Media/images/favicons/favicon.ico" type="image/x-icon" rel="shortcut icon"/> <link href="/web/20230923152623im_/https://csrc.nist.gov/CSRC/Media/images/favicons/favicon.ico" type="image/x-icon" rel="icon"/> <link href="/web/20230923152623cs_/https://csrc.nist.gov/dist/app.css" rel="stylesheet"/>  <style> .grecaptcha-badge { visibility: hidden; } </style> <script async type="text/javascript" id="_fed_an_ua_tag" src="https://web.archive.org/web/20230923152623js_/https://dap.digitalgov.gov/Universal-Federated-Analytics-Min.js?agency=nist&subagency=csrc&pua=UA-66610693-15&yt=true&exts=xsd,xml,wav,mpg,mpeg,avi,rtf,webm,ogg,ogv,oga,map,otf,eot,svg,ttf,woff"></script> <style id="antiClickjackCss"> body > * { display: none !important; } #antiClickjack { display: block !important; } </style> <noscript> <style id="antiClickjackNoScript"> body > * { display: block !important; } #antiClickjack { display: none !important; } </style> </noscript> <script type="text/javascript" id="antiClickjackScript"> if (self === top) { // no clickjacking var antiClickjack = document.getElementById("antiClickjackCss"); antiClickjack.parentNode.removeChild(antiClickjack); } else { setTimeout(tryForward(), 5000); } function tryForward() { top.location = self.location; } </script>  <script async src="https://web.archive.org/web/20230923152623js_/https://www.googletagmanager.com/gtag/js?id=G-TSQ0PLGJZP"></script> <script> 聽聽window.dataLayer = window.dataLayer || []; 聽聽function gtag(){dataLayer.push(arguments);} 聽聽gtag('js', new Date()); 聽聽gtag('config', 'G-TSQ0PLGJZP'); </script> </head> <body> <div id="antiClickjack" style="display: none;"> <strong style="font-size: 1.6rem;">You are viewing this page in an unauthorized frame window.</strong> <p>This is a potential security issue, you are being redirected to <a href="https://web.archive.org/web/20230923152623/https://csrc.nist.gov/">https://csrc.nist.gov</a>.</p> </div> <section class="usa-banner" aria-label="Official government website"> <div class="usa-accordion container"> <header class="usa-banner__header"> <noscript> <p style="font-size: 0.85rem; font-weight: bold;">You have JavaScript disabled. This site requires JavaScript to be enabled for complete site functionality.</p> </noscript> <img class="usa-banner__header-flag" src="/web/20230923152623im_/https://csrc.nist.gov/images/usbanner/us_flag_small.png" alt="U.S. flag">   <span class="usa-banner__header-text">An official website of the United States government</span> <button id="gov-banner-button" class="usa-accordion__button usa-banner__button" data-toggle="collapse" data-target="#gov-banner" aria-expanded="true" aria-controls="gov-banner"> <span class="usa-banner__button-text">Here's how you know</span> </button> </header> <div class="usa-banner__content usa-accordion__content collapse in" role="tabpanel" id="gov-banner" aria-expanded="true"> <div class="row"> <div class="col-md-5 col-sm-12"> <div class="row"> <div class="col-sm-2 col-xs-3"> <img class="usa-banner__icon usa-media-block__img" src="/web/20230923152623im_/https://csrc.nist.gov/images/usbanner/icon-dot-gov.svg" alt="Dot gov"> </div> <div class="col-sm-10 col-xs-9"> <p> <strong>Official websites use .gov</strong> <br> A <strong>.gov</strong> website belongs to an official government organization in the United States. </p> </div> </div> </div> <div class="col-md-5 col-sm-12"> <div class="row"> <div class="col-sm-2 col-xs-3"> <img class="usa-banner__icon usa-media-block__img" src="/web/20230923152623im_/https://csrc.nist.gov/images/usbanner/icon-https.svg" alt="Https"> </div> <div class="col-sm-10 col-xs-9"> <p> <strong>Secure .gov websites use HTTPS</strong> <br> A <strong>lock</strong> (<img class="usa-banner__lock" src="/web/20230923152623im_/https://csrc.nist.gov/images/usbanner/lock.svg" alt="Dot gov">) or <strong>https://</strong> means you've safely connected to the .gov website. Share sensitive information only on official, secure websites. </p> </div> </div> </div> </div> </div> </div> </section> <nav id="navbar" class="navbar"> <div id="nist-menu-container" class="container"> <div class="row">  <div class="col-xs-6 col-md-4 navbar-header"> <a class="navbar-brand" href="https://web.archive.org/web/20230923152623/https://www.nist.gov/" target="_blank" id="navbar-brand-image"> <img src="/web/20230923152623im_/https://csrc.nist.gov/CSRC/media/images/svg/nist-logo.svg" alt="National Institute of Standards and Technology" width="110" height="30"> </a> </div> <div class="col-xs-6 col-md-8 navbar-nist-logo"> <div class="form-inline hidden-sm hidden-xs"> <form name="site-search" id="site-search-form" action="/web/20230923152623/https://csrc.nist.gov/search" method="GET"> <label for="search-csrc-query" class="element-invisible">Search</label> <input autocomplete="off" class="form-control" id="search-csrc-query" name="keywords" type="text" size="15" maxlength="128" placeholder="Search CSRC"/> <input type="hidden" name="ipp" value="25"/> <input type="hidden" name="sortBy" value="relevance"/> <input type="hidden" name="showOnly" value="publications,projects,news,events,presentations,glossary,topics"/> <input type="hidden" name="topicsMatch" value="ANY"/> <input type="hidden" name="status" value="Final,Draft"/> <button type="submit" id="search-csrc-submit-btn" class="form-submit"> <span class="element-invisible">Search</span> <i class="fa fa-search"></i> </button> </form> </div> <span id="nvd-menu-button" class="pull-right"> <a href="#" id="nvd-menu-button-link"> <span class="fa fa-bars"></span> <span id="nvd-menu-full-text">CSRC MENU</span> </a> </span> </div> </div> </div> <div class="form-inline hidden-md hidden-lg"> <form name="site-search-mobile" id="site-search-form-mobile" action="/web/20230923152623/https://csrc.nist.gov/search" method="GET"> <label for="search-csrc-query-mobile" class="element-invisible">Search</label> <input autocomplete="off" class="form-control" id="search-csrc-query-mobile" name="keywords" type="text" size="15" maxlength="128" placeholder="Search CSRC"/> <button type="submit" id="search-csrc-submit-btn-mobile" class="form-submit"> <span class="element-invisible">Search</span> <i class="fa fa-search"></i> </button> </form> </div> <div class="main-menu-row container">  <div id="main-menu-drop" class="col-lg-12" style="display: none;"> <ul> <li><a href="/web/20230923152623/https://csrc.nist.gov/projects">Projects</a></li> <li> <a href="/web/20230923152623/https://csrc.nist.gov/publications"> Publications <span class="expander fa fa-plus" id="main-menu-pubs-expander" data-expander-name="publications" data-expanded="false"> <span class="element-invisible">Expand or Collapse</span> </span> </a> <div style="display: none;" class="sub-menu" data-expander-trigger="publications" id="main-menu-pubs-expanded"> <div class="row"> <div class="col-lg-4"> <p><a href="/web/20230923152623/https://csrc.nist.gov/publications/drafts-open-for-comment">Drafts for Public Comment</a></p> <p><a href="/web/20230923152623/https://csrc.nist.gov/publications/draft-pubs">All Public Drafts</a></p> <p><a href="/web/20230923152623/https://csrc.nist.gov/publications/final-pubs">Final Pubs</a></p> <p><a href="/web/20230923152623/https://csrc.nist.gov/publications/fips">FIPS <small>(standards)</small></a></p> </div> <div class="col-lg-4"> <p><a href="/web/20230923152623/https://csrc.nist.gov/publications/sp">Special Publications (SP<small>s</small>)</a></p> <p><a href="/web/20230923152623/https://csrc.nist.gov/publications/ir">IR <small>(interagency/internal reports)</small></a></p> <p><a href="/web/20230923152623/https://csrc.nist.gov/publications/cswp">CSWP <small>(cybersecurity white papers)</small></a></p> <p><a href="/web/20230923152623/https://csrc.nist.gov/publications/itl-bulletin">ITL Bulletins</a></p> </div> <div class="col-lg-4"> <p><a href="/web/20230923152623/https://csrc.nist.gov/publications/project-description">Project Descriptions</a></p> <p><a href="/web/20230923152623/https://csrc.nist.gov/publications/journal-article">Journal Articles</a></p> <p><a href="/web/20230923152623/https://csrc.nist.gov/publications/conference-paper">Conference Papers</a></p> <p><a href="/web/20230923152623/https://csrc.nist.gov/publications/book">Books</a></p> </div> </div> </div> </li> <li> <a href="/web/20230923152623/https://csrc.nist.gov/topics"> Topics <span class="expander fa fa-plus" id="main-menu-topics-expander" data-expander-name="topics" data-expanded="false"> <span class="element-invisible">Expand or Collapse</span> </span> </a> <div style="display: none;" class="sub-menu" data-expander-trigger="topics" id="main-menu-topics-expanded"> <div class="row"> <div class="col-lg-4"> <p><a href="/web/20230923152623/https://csrc.nist.gov/Topics/Security-and-Privacy">Security & Privacy</a></p> <p><a href="/web/20230923152623/https://csrc.nist.gov/Topics/Applications">Applications</a></p> </div> <div class="col-lg-4"> <p><a href="/web/20230923152623/https://csrc.nist.gov/Topics/Technologies">Technologies</a></p> <p><a href="/web/20230923152623/https://csrc.nist.gov/Topics/Sectors">Sectors</a></p> </div> <div class="col-lg-4"> <p><a href="/web/20230923152623/https://csrc.nist.gov/Topics/Laws-and-Regulations">Laws & Regulations</a></p> <p><a href="/web/20230923152623/https://csrc.nist.gov/Topics/Activities-and-Products">Activities & Products</a></p> </div> </div> </div> </li> <li><a href="/web/20230923152623/https://csrc.nist.gov/news">News & Updates</a></li> <li><a href="/web/20230923152623/https://csrc.nist.gov/events">Events</a></li> <li><a href="/web/20230923152623/https://csrc.nist.gov/glossary">Glossary</a></li> <li> <a href="/web/20230923152623/https://csrc.nist.gov/about"> About CSRC <span class="expander fa fa-plus" id="main-menu-about-expander" data-expander-name="about" data-expanded="false"> <span class="element-invisible">Expand or Collapse</span> </span> </a> <div style="display: none;" class="sub-menu" data-expander-trigger="about" id="main-menu-about-expanded"> <div class="row"> <div class="col-lg-6"> <p> <strong><a href="/web/20230923152623/https://csrc.nist.gov/Groups/Computer-Security-Division">Computer Security Division</a></strong><br/> <ul> <li><a href="/web/20230923152623/https://csrc.nist.gov/Groups/Computer-Security-Division/Cryptographic-Technology">Cryptographic Technology</a></li> <li><a href="/web/20230923152623/https://csrc.nist.gov/Groups/Computer-Security-Division/Secure-Systems-and-Applications">Secure Systems and Applications</a></li> <li><a href="/web/20230923152623/https://csrc.nist.gov/Groups/Computer-Security-Division/Security-Components-and-Mechanisms">Security Components and Mechanisms</a></li> <li><a href="/web/20230923152623/https://csrc.nist.gov/Groups/Computer-Security-Division/Security-Engineering-and-Risk-Management">Security Engineering and Risk Management</a></li> <li><a href="/web/20230923152623/https://csrc.nist.gov/Groups/Computer-Security-Division/Security-Testing-Validation-and-Measurement">Security Testing, Validation, and Measurement</a></li> </ul> </p> </div> <div class="col-lg-6"> <p> <strong><a href="/web/20230923152623/https://csrc.nist.gov/Groups/Applied-Cybersecurity-Division">Applied Cybersecurity Division</a></strong><br/> <ul> <li><a href="/web/20230923152623/https://csrc.nist.gov/Groups/Applied-Cybersecurity-Division/Cybersecurity-and-Privacy-Applications">Cybersecurity and Privacy Applications</a></li> <li><a href="/web/20230923152623/https://csrc.nist.gov/Groups/Applied-Cybersecurity-Division/National-Cybersecurity-Center-of-Excellence">National Cybersecurity Center of Excellence (NCCoE)</a></li> <li><a href="https://web.archive.org/web/20230923152623/https://www.nist.gov/nice/">National Initiative for Cybersecurity Education (NICE)</a></li> </ul> </p> <p> <a href="/web/20230923152623/https://csrc.nist.gov/contact"> Contact Us </a> </p> </div> </div> </div> </li> </ul> </div> </div> </nav> <section id="itl-header" class="has-menu"> <div class="container"> <div class="row"> <div class="col-sm-12 col-md-8"> <div class="hidden-xs hidden-sm" id="itl-header-lg"> <a href="https://web.archive.org/web/20230923152623/https://www.nist.gov/itl" target="_blank" id="itl-header-link">Information Technology Laboratory</a> </div> <div class="hidden-xs hidden-sm" id="csrc-header-lg"> <a href="/web/20230923152623/https://csrc.nist.gov/" id="csrc-header-link-lg">Computer Security Resource Center</a> </div> </div> <div class="col-sm-12 col-md-4"> <div class="hidden-xs hidden-sm hidden-md"> <a id="logo-csrc-lg" href="/web/20230923152623/https://csrc.nist.gov/"><img id="img-logo-csrc-lg" src="/web/20230923152623im_/https://csrc.nist.gov/CSRC/Media/images/nist-logo-csrc-white.svg" alt="CSRC Logo" class="csrc-header-logo"></a> </div> <div class="hidden-lg"> <a id="logo-csrc-sm" href="/web/20230923152623/https://csrc.nist.gov/"><img id="img-logo-csrc-sm" src="/web/20230923152623im_/https://csrc.nist.gov/CSRC/Media/images/nist-logo-csrc-white.svg" alt="CSRC Logo" class="csrc-header-logo"></a> </div> </div> </div> </div> </section> <div id="body-section" class="container"> <div class="publications-detail"> <ol class="breadcrumb"> <a href="/web/20230923152623/https://csrc.nist.gov/publications" class="breadcrumb-link">Publications</a> </ol> <h3 id="pub-header-display-container"> <span id="pub-header-full-display"> Conference Paper </span> </h3> <h1 id="pub-title">Second Preimage Attacks on Dithered Hash Functions</h1> <div class="page-social-buttons" id=""page-social-buttons""> <a href="https://web.archive.org/web/20230923152623/https://www.facebook.com/sharer/sharer.php?u=https%3A%2F%2Fcontent.csrc.e1c.nist.gov%2Fpubs%2Fconference%2F2008%2F04%2F17%2Fsecond-preimage-attacks-on-dithered-hash-functions%2Ffinal" class="social-facebook"><i class="fa fa-facebook fa-fw" aria-hidden="true"></i><span class="sr-only">Share to Facebook</span></a> <a href="https://web.archive.org/web/20230923152623/https://twitter.com/share?url=https%3A%2F%2Fcontent.csrc.e1c.nist.gov%2Fpubs%2Fconference%2F2008%2F04%2F17%2Fsecond-preimage-attacks-on-dithered-hash-functions%2Ffinal" class="social-twitter"><i class="fa fa-twitter fa-fw" aria-hidden="true"></i><span class="sr-only">Share to Twitter</span></a> </div> <p class="hidden-lg hidden-md">     <a href="#pubs-documentation" class="btn btn-lg btn-info" id="pub-topics-anchor-sm">Documentation</a> </p> <div class="row"> <div class="col-md-8 col-sm-12 publication-panel"> <p> <strong>Published:</strong> <span id="pub-release-date" data-date-type="release">April 17, 2008</span><br/> </p> <h4>Author(s)</h4> <p id="pub-authors-container" data-total="7"> <span id="pub-author-0">Elena Andreeva</span>, <span id="pub-author-1">Charles Bouillaguet</span>, <span id="pub-author-2">Pierre-Alain Fouque</span>, <span id="pub-author-3">Jonathan Hoch</span>, <span id="pub-author-4">John Kelsey</span>, <span id="pub-author-5">Adi Shamir</span>, <span id="pub-author-6">S茅bastien Zimmer</span> </p> <h4>Conference</h4> <p> <strong>Name:</strong> <span id="pub-conf-name">27th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2008)</span><br/> <strong>Dates:</strong> <span id="pub-conf-dates">04/13/2008 - 04/17/2008</span><br/> <strong>Location:</strong> <span id="pub-conf-location">Istanbul, Turkey</span><br/> <strong>Citation:</strong> <span id="pub-conf-citation">Advances in Cryptology - EUROCRYPT 2008, vol. 4965, pp. 270-288</span><br/> </p> <div class="bs-callout bs-callout-success pub-abstract-callout"> <h4 id="pubs-abstract-header">Abstract</h4> <div class="hidden-sm hidden-xs hidden-xxs" id="pub-detail-abstract-info">We develop a new generic long-message second preimage attack, based on combining the techniques in the second preimage attacks of Dean and Kelsey and Schneier with the herding attack of Kelsey and Kohno. We show that these generic attacks apply to hash functions using the Merkle-Damg氓rd construction with only slightly more work than the previously known attack, but allow enormously more control of the contents of the second preimage found. Additionally, we show that our new attack applies to several hash function constructions which are not vulnerable to the previously known attack, including the dithered hash proposal of Rivest, Shoup s UOWHF and the ROX hash construction.We analyze the properties of the dithering sequence used in , and develop a time-memory tradeoff which allows us to apply our second preimage attack to a wide range of dithering sequences, including sequences which are much stronger than those in Rivest s proposals. Finally, we show that both the existing second preimage attacks and our new attack can be applied even more efficiently to multiple target messages; in general, given a set of many target messages with a total of 2^R message blocks, these second preimage attacks can find a second preimage for one of those target messages with no more work than would be necessary to find a second preimage for a single target message of 2^R message blocks.</div> <div class="hidden-lg hidden-md"> <div id="pub-detail-abstract-min"> We develop a new generic long-message second preimage attack, based on combining the techniques in the second preimage attacks of Dean and Kelsey and Schneier with the herding attack of Kelsey and Kohno. We show that these generic attacks apply to hash functions using the Merkle-Damgård construction... <a href="#pubs-abstract-header" id="pub-detail-abs-show">See full abstract</a> </div> <div id="pub-detail-abstract-all" style="display: none;"> We develop a new generic long-message second preimage attack, based on combining the techniques in the second preimage attacks of Dean and Kelsey and Schneier with the herding attack of Kelsey and Kohno. We show that these generic attacks apply to hash functions using the Merkle-Damg氓rd construction with only slightly more work than the previously known attack, but allow enormously more control of the contents of the second preimage found. Additionally, we show that our new attack applies to several hash function constructions which are not vulnerable to the previously known attack, including the dithered hash proposal of Rivest, Shoup s UOWHF and the ROX hash construction.We analyze the properties of the dithering sequence used in , and develop a time-memory tradeoff which allows us to apply our second preimage attack to a wide range of dithering sequences, including sequences which are much stronger than those in Rivest s proposals. Finally, we show that both the existing second preimage attacks and our new attack can be applied even more efficiently to multiple target messages; in general, given a set of many target messages with a total of 2^R message blocks, these second preimage attacks can find a second preimage for one of those target messages with no more work than would be necessary to find a second preimage for a single target message of 2^R message blocks.<br/> <a href="#pubs-abstract-header" id="pub-detail-abs-hide">Hide full abstract</a> </div> </div> <h4>Keywords</h4> <span id="pub-keywords-container" data-total="3"> <span id="pub-keyword-0">cryptanalysis</span>; <span id="pub-keyword-1">dithering</span>; <span id="pub-keyword-2">hash function</span> </span> </div> <h5>Control Families</h5> <p> <span id="pub-control-fam-container" data-total="0">None selected</span> </p> </div> <div class="col-md-4 col-sm-12"> <div class="bs-callout bs-callout-success" id="pubs-documentation"> <h4>Documentation</h4> <p> <strong>Publication:</strong><br/> <a href="https://web.archive.org/web/20230923152623/https://doi.org/10.1007/978-3-540-78967-3_16" id="pub-doi-link"> <i class="fa fa-external-link" aria-hidden="true"></i> https://doi.org/10.1007/978-3-540-78967-3_16 </a><br/> </p> <p> <strong>Supplemental Material:</strong><br/> <span id="pub-supp-container" data-total="0">None available</span><br/> </p> <p> <strong>Document History:</strong><br/> <span id="pub-history-container" data-total="1"> 04/17/08: <span id="pub-history-link-0" data-current-document="true">Conference Paper (Final)</span><br/> </span> </p> </div> </div> </div> </div> <div id="footer-pusher"></div> </div> <footer id="footer"> <div class="container"> <div class="row"> <div class="col-sm-6"> <span class="hidden-xs"> <a href="https://web.archive.org/web/20230923152623/https://www.nist.gov/" title="National Institute of Standards and Technology" rel="home" target="_blank" class="footer-nist-logo" id="footer-nist-logo-link"> <img src="/web/20230923152623im_/https://csrc.nist.gov/CSRC/Media/images/nist-logo-brand-white.svg" alt="National Institute of Standards and Technology logo" id="footer-nist-logo"/> </a> </span> <div class="row footer-contact-container"> <div class="col-sm-12" id="footer-address"> <strong>HEADQUARTERS</strong><br> 100 Bureau Drive<br> Gaithersburg, MD 20899 </div> </div> </div> <div class="col-sm-6"> <ul class="social-list text-right" style="display: block;"> <li class="field-item service-twitter list-horiz"> <a href="https://web.archive.org/web/20230923152623/https://twitter.com/NISTCyber" class="social-btn social-btn--large extlink ext" id="footer-social-twitter-link"> <i class="fa fa-twitter fa-fw"><span class="element-invisible">twitter</span></i><span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> <li class="field-item service-facebook list-horiz"> <a href="https://web.archive.org/web/20230923152623/https://www.facebook.com/NIST" class="social-btn social-btn--large extlink ext" id="footer-social-facebook-link"> <i class="fa fa-facebook fa-fw"><span class="element-invisible">facebook</span></i><span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> <li class="field-item service-linkedin list-horiz"> <a href="https://web.archive.org/web/20230923152623/https://www.linkedin.com/company/nist" class="social-btn social-btn--large extlink ext" id="footer-social-linkedin-link"> <i class="fa fa-linkedin fa-fw"><span class="element-invisible">linkedin</span></i><span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> <li class="field-item service-instagram list-horiz"> <a href="https://web.archive.org/web/20230923152623/https://www.instagram.com/usnistgov/" class="social-btn social-btn--large extlink ext" id="footer-social-instagram-link"> <i class="fa fa-instagram fa-fw"><span class="element-invisible">instagram</span></i> <span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> <li class="field-item service-youtube list-horiz"> <a href="https://web.archive.org/web/20230923152623/https://www.youtube.com/user/USNISTGOV" class="social-btn social-btn--large extlink ext" id="footer-social-youtube-link"> <i class="fa fa-youtube fa-fw"><span class="element-invisible">youtube</span></i><span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> <li class="field-item service-rss list-horiz"> <a href="https://web.archive.org/web/20230923152623/https://www.nist.gov/news-events/nist-rss-feeds" class="social-btn social-btn--large extlink" id="footer-social-rss-link"> <i class="fa fa-rss fa-fw"><span class="element-invisible">rss</span></i> </a> </li> <li class="field-item service-govdelivery list-horiz last"> <a href="https://web.archive.org/web/20230923152623/https://public.govdelivery.com/accounts/USNIST/subscriber/new?qsp=USNIST_3" class="social-btn social-btn--large extlink ext" title="Subscribe to CSRC and publication updates, and other NIST cybersecurity news" id="footer-social-govdelivery-link"> <i class="fa fa-envelope fa-fw"><span class="element-invisible">govdelivery</span></i><span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> </ul> <p class="text-right"> Want updates about CSRC and our publications? <a href="https://web.archive.org/web/20230923152623/https://public.govdelivery.com/accounts/USNIST/subscriber/new?qsp=USNIST_3" class="btn btn-lg btn-primary" style="background-color: #12659c!important; border-color: #12659c!important;" id="footer-subscribe-link">Subscribe</a> </p> </div> </div> <div class="row hidden-sm hidden-md hidden-lg"> <div class="col-sm-12"> <a href="https://web.archive.org/web/20230923152623/https://www.nist.gov/" title="National Institute of Standards and Technology" rel="home" target="_blank" class="footer-nist-logo" id="footer-bottom-nist-logo-link"> <img src="/web/20230923152623im_/https://csrc.nist.gov/CSRC/Media/images/logo_rev.png" alt="National Institute of Standards and Technology logo" id="footer-bottom-nist-logo"/> </a> </div> </div> <div class="row"> <div class="col-sm-6"> <p> <a href="/web/20230923152623/https://csrc.nist.gov/about/contact" id="footer-contact-us-link">Contact Us</a> | <a href="https://web.archive.org/web/20230923152623/https://www.nist.gov/about-nist/our-organization" style="display: inline-block;" id="footer-org-link">Our Other Offices</a> </p> </div> <div class="col-sm-6"> <span class="pull-right text-right"> Send inquiries to <a href="https://web.archive.org/web/20230923152623/mailto:csrc-inquiry@nist.gov?subject=CSRC Inquiry" style="display: inline-block;" id="footer-inquiries-link">csrc-inquiry@nist.gov</a> </span> </div> </div> <div class="row"> <div class="footer-bottom-links-container" id="footer-bottom-links-container"> <ul> <li><a href="https://web.archive.org/web/20230923152623/https://www.nist.gov/privacy-policy">Site Privacy</a></li> <li><a href="https://web.archive.org/web/20230923152623/https://www.nist.gov/oism/accessibility">Accessibility</a></li> <li><a href="https://web.archive.org/web/20230923152623/https://www.nist.gov/privacy">Privacy Program</a></li> <li><a href="https://web.archive.org/web/20230923152623/https://www.nist.gov/oism/copyrights">Copyrights</a></li> <li><a href="https://web.archive.org/web/20230923152623/https://www.commerce.gov/vulnerability-disclosure-policy">Vulnerability Disclosure</a></li> <li><a href="https://web.archive.org/web/20230923152623/https://www.nist.gov/no-fear-act-policy">No Fear Act Policy</a></li> <li><a href="https://web.archive.org/web/20230923152623/https://www.nist.gov/foia">FOIA</a></li> <li><a href="https://web.archive.org/web/20230923152623/https://www.nist.gov/environmental-policy-statement">Environmental Policy</a></li> <li><a href="https://web.archive.org/web/20230923152623/https://www.nist.gov/summary-report-scientific-integrity">Scientific Integrity</a></li> <li><a href="https://web.archive.org/web/20230923152623/https://www.nist.gov/nist-information-quality-standards">Information Quality Standards</a></li> <li><a href="https://web.archive.org/web/20230923152623/https://www.commerce.gov/">Commerce.gov</a></li> <li><a href="https://web.archive.org/web/20230923152623/https://www.science.gov/">Science.gov</a></li> <li><a href="https://web.archive.org/web/20230923152623/https://www.usa.gov/">USA.gov</a></li> <li><a href="https://web.archive.org/web/20230923152623/https://vote.gov/">Vote.gov</a></li> </ul> </div> </div> </div> </footer> <script type="text/javascript" src="/web/20230923152623js_/https://csrc.nist.gov/dist/js/quick-collapse.js"></script> <script type="text/javascript" src="/web/20230923152623js_/https://csrc.nist.gov/dist/app.bundle.js"></script> </body> </html>

CINXE.COM

Second Preimage Attacks on Dithered Hash Functions | CSRC