Speeding Up the Wide-Pipe: Secure and Fast Hashing

<!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/2010/12/12/speeding-up-the-widepipe-secure-and-fast-hashing/final","20230923152115","https://web.archive.org/","web","/_static/", "1695482475"); </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>Speeding Up the Wide-Pipe: Secure and Fast Hashing | 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="In this paper we propose a new sequential mode of operation – the Fast wide pipe or FWP for short – to hash messages of arbitrary length. The mode is shown to be (1) preimage-resistance preserving, (2) collision-resistance-preserving and, most importantly, (3) indifferentiable from a random oracle up to O(2^n/2) compression function invocations. In addition, our rigorous investigation suggests that any variants of Joux’s multi-collision, Kelsey-Schneier 2nd preimage and Herding attack are also ineffective on this mode. This fact leads us to conjecture that the indifferentiability security bound of FWP can be extended beyond the birthday barrier. From the point of view of efficiency, this new mode, for example, is always faster than the Wide-pipe mode when both modes use an identical compression function. In particular, it is nearly twice as fast as the Wide-pipe for a reasonable selection of the input and output size of the compression function. We also compare the FWP with several other modes of operation."/>  <meta name="dcterms.title" content="Speeding Up the Wide-Pipe: Secure and Fast Hashing"/> <meta name="dcterms.description" content="In this paper we propose a new sequential mode of operation – the Fast wide pipe or FWP for short – to hash messages of arbitrary length. The mode is shown to be (1) preimage-resistance preserving, (2) collision-resistance-preserving and, most importantly, (3) indifferentiable from a random oracle up to O(2^n/2) compression function invocations. In addition, our rigorous investigation suggests that any variants of Joux’s multi-collision, Kelsey-Schneier 2nd preimage and Herding attack are also ineffective on this mode. This fact leads us to conjecture that the indifferentiability security bound of FWP can be extended beyond the birthday barrier. From the point of view of efficiency, this new mode, for example, is always faster than the Wide-pipe mode when both modes use an identical compression function. In particular, it is nearly twice as fast as the Wide-pipe for a reasonable selection of the input and output size of the compression function. We also compare the FWP with several other modes of operation."/>  <meta name="dcterms.creator" content="Author: Mridul Nandi"/> <meta name="dcterms.creator" content="Author: Souradyuti Paul"/>  <meta name="dcterms.date.created" schema="ISO8601" content="2010-12-12"/> <meta name="dcterms.identifier" content="https://csrc.nist.gov/pubs/conference/2010/12/12/speeding-up-the-widepipe-secure-and-fast-hashing/final"/> <meta name="dcterms.language" scheme="DCTERMS.RFC1766" content="EN-US"/>  <meta name="citation_title" content="Speeding Up the Wide-Pipe: Secure and Fast Hashing"/> <meta name="citation_publication_date" content="2010/12/12"/> <meta name="citation_doi" content="https://doi.org/10.1007/978-3-642-17401-8_12"/> <meta name="citation_publisher" content="Springer"/> <meta name="citation_firstpage" content="144"/> <meta name="citation_lastpage" content="162"/> <meta name="citation_keywords" content="block ciphers,hash functions,indifferentiability,stream ciphers,wide-pipe"/> <meta name="citation_language" content="en"/> <meta name="citation_pdf_url" content="https://doi.org/10.1007/978-3-642-17401-8_12"/> <meta name="citation_abstract_html_url" content="https://csrc.nist.gov/pubs/conference/2010/12/12/speeding-up-the-widepipe-secure-and-fast-hashing/final"/> <meta name="citation_conference_title" content="11th International Conference on Cryptology (INDOCRYPT 2010); 12/12/2010 - 12/15/2010; Hyderabad, India"/> <meta name="citation_inbook_title" content="Progress in Cryptology - INDOCRYPT 2010"/>  <meta name="citation_author" content="Nandi, Mridul"/> <meta name="citation_author" content="Paul, Souradyuti"/>  <meta name="og:site_name" content="CSRC | NIST"/> <meta name="og:type" content="article"/> <meta name="og:url" content="https://web.archive.org/web/20230923152115im_/https://csrc.nist.gov/pubs/conference/2010/12/12/speeding-up-the-widepipe-secure-and-fast-hashing/final"/> <meta name="og:title" content="Speeding Up the Wide-Pipe: Secure and Fast Hashing"/> <meta name="og:description" content="In this paper we propose a new sequential mode of operation – the Fast wide pipe or FWP for short – to hash messages of arbitrary length. The mode is shown to be (1) preimage-resistance preserving, (2) collision-resistance-preserving and, most importantly, (3) indifferentiable from a random oracle up to O(2^n/2) compression function invocations. In addition, our rigorous investigation suggests that any variants of Joux’s multi-collision, Kelsey-Schneier 2nd preimage and Herding attack are also ineffective on this mode. This fact leads us to conjecture that the indifferentiability security bound of FWP can be extended beyond the birthday barrier. From the point of view of efficiency, this new mode, for example, is always faster than the Wide-pipe mode when both modes use an identical compression function. In particular, it is nearly twice as fast as the Wide-pipe for a reasonable selection of the input and output size of the compression function. We also compare the FWP with several..."/> <meta name="article:author" content="Nandi, Mridul"/> <meta name="article:author" content="Paul, Souradyuti"/> <meta name="article:tag" content="block ciphers,hash functions,indifferentiability,stream ciphers,wide-pipe"/> <meta name="article:published_time" content="2010-12-12"/> <meta name="og:image" content="https://web.archive.org/web/20230923152115im_/https://csrc.nist.gov/CSRC/media/images/CSRC-logo-open-graph.png"/> <link rel="apple-touch-icon" sizes="180x180" href="/web/20230923152115im_/https://csrc.nist.gov/images/icons/apple-touch-icon.png"/> <link rel="icon" type="image/png" href="/web/20230923152115im_/https://csrc.nist.gov/images/icons/favicon-32x32.png" sizes="32x32"/> <link rel="icon" type="image/png" href="/web/20230923152115im_/https://csrc.nist.gov/images/icons/favicon-16x16.png" sizes="16x16"/> <link rel="manifest" href="/web/20230923152115/https://csrc.nist.gov/images/icons/manifest.json"/> <link rel="mask-icon" href="/web/20230923152115im_/https://csrc.nist.gov/images/icons/safari-pinned-tab.svg" color="#000000"/> <link href="/web/20230923152115im_/https://csrc.nist.gov/CSRC/Media/images/favicons/favicon.ico" type="image/x-icon" rel="shortcut icon"/> <link href="/web/20230923152115im_/https://csrc.nist.gov/CSRC/Media/images/favicons/favicon.ico" type="image/x-icon" rel="icon"/> <link href="/web/20230923152115cs_/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/20230923152115js_/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/20230923152115js_/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/20230923152115/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/20230923152115im_/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/20230923152115im_/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/20230923152115im_/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/20230923152115im_/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/20230923152115/https://www.nist.gov/" target="_blank" id="navbar-brand-image"> <img src="/web/20230923152115im_/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/20230923152115/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/20230923152115/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/20230923152115/https://csrc.nist.gov/projects">Projects</a></li> <li> <a href="/web/20230923152115/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/20230923152115/https://csrc.nist.gov/publications/drafts-open-for-comment">Drafts for Public Comment</a></p> <p><a href="/web/20230923152115/https://csrc.nist.gov/publications/draft-pubs">All Public Drafts</a></p> <p><a href="/web/20230923152115/https://csrc.nist.gov/publications/final-pubs">Final Pubs</a></p> <p><a href="/web/20230923152115/https://csrc.nist.gov/publications/fips">FIPS <small>(standards)</small></a></p> </div> <div class="col-lg-4"> <p><a href="/web/20230923152115/https://csrc.nist.gov/publications/sp">Special Publications (SP<small>s</small>)</a></p> <p><a href="/web/20230923152115/https://csrc.nist.gov/publications/ir">IR <small>(interagency/internal reports)</small></a></p> <p><a href="/web/20230923152115/https://csrc.nist.gov/publications/cswp">CSWP <small>(cybersecurity white papers)</small></a></p> <p><a href="/web/20230923152115/https://csrc.nist.gov/publications/itl-bulletin">ITL Bulletins</a></p> </div> <div class="col-lg-4"> <p><a href="/web/20230923152115/https://csrc.nist.gov/publications/project-description">Project Descriptions</a></p> <p><a href="/web/20230923152115/https://csrc.nist.gov/publications/journal-article">Journal Articles</a></p> <p><a href="/web/20230923152115/https://csrc.nist.gov/publications/conference-paper">Conference Papers</a></p> <p><a href="/web/20230923152115/https://csrc.nist.gov/publications/book">Books</a></p> </div> </div> </div> </li> <li> <a href="/web/20230923152115/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/20230923152115/https://csrc.nist.gov/Topics/Security-and-Privacy">Security & Privacy</a></p> <p><a href="/web/20230923152115/https://csrc.nist.gov/Topics/Applications">Applications</a></p> </div> <div class="col-lg-4"> <p><a href="/web/20230923152115/https://csrc.nist.gov/Topics/Technologies">Technologies</a></p> <p><a href="/web/20230923152115/https://csrc.nist.gov/Topics/Sectors">Sectors</a></p> </div> <div class="col-lg-4"> <p><a href="/web/20230923152115/https://csrc.nist.gov/Topics/Laws-and-Regulations">Laws & Regulations</a></p> <p><a href="/web/20230923152115/https://csrc.nist.gov/Topics/Activities-and-Products">Activities & Products</a></p> </div> </div> </div> </li> <li><a href="/web/20230923152115/https://csrc.nist.gov/news">News & Updates</a></li> <li><a href="/web/20230923152115/https://csrc.nist.gov/events">Events</a></li> <li><a href="/web/20230923152115/https://csrc.nist.gov/glossary">Glossary</a></li> <li> <a href="/web/20230923152115/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/20230923152115/https://csrc.nist.gov/Groups/Computer-Security-Division">Computer Security Division</a></strong><br/> <ul> <li><a href="/web/20230923152115/https://csrc.nist.gov/Groups/Computer-Security-Division/Cryptographic-Technology">Cryptographic Technology</a></li> <li><a href="/web/20230923152115/https://csrc.nist.gov/Groups/Computer-Security-Division/Secure-Systems-and-Applications">Secure Systems and Applications</a></li> <li><a href="/web/20230923152115/https://csrc.nist.gov/Groups/Computer-Security-Division/Security-Components-and-Mechanisms">Security Components and Mechanisms</a></li> <li><a href="/web/20230923152115/https://csrc.nist.gov/Groups/Computer-Security-Division/Security-Engineering-and-Risk-Management">Security Engineering and Risk Management</a></li> <li><a href="/web/20230923152115/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/20230923152115/https://csrc.nist.gov/Groups/Applied-Cybersecurity-Division">Applied Cybersecurity Division</a></strong><br/> <ul> <li><a href="/web/20230923152115/https://csrc.nist.gov/Groups/Applied-Cybersecurity-Division/Cybersecurity-and-Privacy-Applications">Cybersecurity and Privacy Applications</a></li> <li><a href="/web/20230923152115/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/20230923152115/https://www.nist.gov/nice/">National Initiative for Cybersecurity Education (NICE)</a></li> </ul> </p> <p> <a href="/web/20230923152115/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/20230923152115/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/20230923152115/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/20230923152115/https://csrc.nist.gov/"><img id="img-logo-csrc-lg" src="/web/20230923152115im_/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/20230923152115/https://csrc.nist.gov/"><img id="img-logo-csrc-sm" src="/web/20230923152115im_/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/20230923152115/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">Speeding Up the Wide-Pipe: Secure and Fast Hashing</h1> <div class="page-social-buttons" id=""page-social-buttons""> <a href="https://web.archive.org/web/20230923152115/https://www.facebook.com/sharer/sharer.php?u=https%3A%2F%2Fcontent.csrc.e1c.nist.gov%2Fpubs%2Fconference%2F2010%2F12%2F12%2Fspeeding-up-the-widepipe-secure-and-fast-hashing%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/20230923152115/https://twitter.com/share?url=https%3A%2F%2Fcontent.csrc.e1c.nist.gov%2Fpubs%2Fconference%2F2010%2F12%2F12%2Fspeeding-up-the-widepipe-secure-and-fast-hashing%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">December 12, 2010</span><br/> </p> <h4>Author(s)</h4> <p id="pub-authors-container" data-total="2"> <span id="pub-author-0">Mridul Nandi</span>, <span id="pub-author-1">Souradyuti Paul</span> </p> <h4>Conference</h4> <p> <strong>Name:</strong> <span id="pub-conf-name">11th International Conference on Cryptology (INDOCRYPT 2010)</span><br/> <strong>Dates:</strong> <span id="pub-conf-dates">12/12/2010 - 12/15/2010</span><br/> <strong>Location:</strong> <span id="pub-conf-location">Hyderabad, India</span><br/> <strong>Citation:</strong> <span id="pub-conf-citation">Progress in Cryptology - INDOCRYPT 2010, vol. 6498, pp. 144-162</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">In this paper we propose a new sequential mode of operation – the Fast wide pipe or FWP for short – to hash messages of arbitrary length. The mode is shown to be (1) preimage-resistance preserving, (2) collision-resistance-preserving and, most importantly, (3) indifferentiable from a random oracle up to O(2^n/2) compression function invocations. In addition, our rigorous investigation suggests that any variants of Joux’s multi-collision, Kelsey-Schneier 2nd preimage and Herding attack are also ineffective on this mode. This fact leads us to conjecture that the indifferentiability security bound of FWP can be extended beyond the birthday barrier. From the point of view of efficiency, this new mode, for example, is always faster than the Wide-pipe mode when both modes use an identical compression function. In particular, it is nearly twice as fast as the Wide-pipe for a reasonable selection of the input and output size of the compression function. We also compare the FWP with several other modes of operation.</div> <div class="hidden-lg hidden-md"> <div id="pub-detail-abstract-min"> In this paper we propose a new sequential mode of operation – the Fast wide pipe or FWP for short – to hash messages of arbitrary length. The mode is shown to be (1) preimage-resistance preserving, (2) collision-resistance-preserving and, most importantly, (3) indifferentiable from a random oracle... <a href="#pubs-abstract-header" id="pub-detail-abs-show">See full abstract</a> </div> <div id="pub-detail-abstract-all" style="display: none;"> In this paper we propose a new sequential mode of operation – the Fast wide pipe or FWP for short – to hash messages of arbitrary length. The mode is shown to be (1) preimage-resistance preserving, (2) collision-resistance-preserving and, most importantly, (3) indifferentiable from a random oracle up to O(2^n/2) compression function invocations. In addition, our rigorous investigation suggests that any variants of Joux’s multi-collision, Kelsey-Schneier 2nd preimage and Herding attack are also ineffective on this mode. This fact leads us to conjecture that the indifferentiability security bound of FWP can be extended beyond the birthday barrier. From the point of view of efficiency, this new mode, for example, is always faster than the Wide-pipe mode when both modes use an identical compression function. In particular, it is nearly twice as fast as the Wide-pipe for a reasonable selection of the input and output size of the compression function. We also compare the FWP with several other modes of operation.<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="5"> <span id="pub-keyword-0">block ciphers</span>; <span id="pub-keyword-1">hash functions</span>; <span id="pub-keyword-2">indifferentiability</span>; <span id="pub-keyword-3">stream ciphers</span>; <span id="pub-keyword-4">wide-pipe</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/20230923152115/https://doi.org/10.1007/978-3-642-17401-8_12" id="pub-doi-link"> <i class="fa fa-external-link" aria-hidden="true"></i> https://doi.org/10.1007/978-3-642-17401-8_12 </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"> 12/12/10: <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/20230923152115/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/20230923152115im_/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/20230923152115/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/20230923152115/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/20230923152115/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/20230923152115/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/20230923152115/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/20230923152115/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/20230923152115/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/20230923152115/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/20230923152115/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/20230923152115im_/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/20230923152115/https://csrc.nist.gov/about/contact" id="footer-contact-us-link">Contact Us</a> | <a href="https://web.archive.org/web/20230923152115/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/20230923152115/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/20230923152115/https://www.nist.gov/privacy-policy">Site Privacy</a></li> <li><a href="https://web.archive.org/web/20230923152115/https://www.nist.gov/oism/accessibility">Accessibility</a></li> <li><a href="https://web.archive.org/web/20230923152115/https://www.nist.gov/privacy">Privacy Program</a></li> <li><a href="https://web.archive.org/web/20230923152115/https://www.nist.gov/oism/copyrights">Copyrights</a></li> <li><a href="https://web.archive.org/web/20230923152115/https://www.commerce.gov/vulnerability-disclosure-policy">Vulnerability Disclosure</a></li> <li><a href="https://web.archive.org/web/20230923152115/https://www.nist.gov/no-fear-act-policy">No Fear Act Policy</a></li> <li><a href="https://web.archive.org/web/20230923152115/https://www.nist.gov/foia">FOIA</a></li> <li><a href="https://web.archive.org/web/20230923152115/https://www.nist.gov/environmental-policy-statement">Environmental Policy</a></li> <li><a href="https://web.archive.org/web/20230923152115/https://www.nist.gov/summary-report-scientific-integrity">Scientific Integrity</a></li> <li><a href="https://web.archive.org/web/20230923152115/https://www.nist.gov/nist-information-quality-standards">Information Quality Standards</a></li> <li><a href="https://web.archive.org/web/20230923152115/https://www.commerce.gov/">Commerce.gov</a></li> <li><a href="https://web.archive.org/web/20230923152115/https://www.science.gov/">Science.gov</a></li> <li><a href="https://web.archive.org/web/20230923152115/https://www.usa.gov/">USA.gov</a></li> <li><a href="https://web.archive.org/web/20230923152115/https://vote.gov/">Vote.gov</a></li> </ul> </div> </div> </div> </footer> <script type="text/javascript" src="/web/20230923152115js_/https://csrc.nist.gov/dist/js/quick-collapse.js"></script> <script type="text/javascript" src="/web/20230923152115js_/https://csrc.nist.gov/dist/app.bundle.js"></script> </body> </html>

CINXE.COM

Speeding Up the Wide-Pipe: Secure and Fast Hashing | CSRC