From: The Keccak Team <firstname.lastname@example.org> To: Jonathan Nieder <email@example.com>, firstname.lastname@example.org Cc: email@example.com, firstname.lastname@example.org, email@example.com, firstname.lastname@example.org, Linus Torvalds <email@example.com> Subject: Re: RFC: Another proposed hash function transition plan Date: Mon, 13 Mar 2017 10:24:25 +0100 Message-ID: <firstname.lastname@example.org> (raw) In-Reply-To: <20170304011251.GA26789@aiede.mtv.corp.google.com> Hello, We have read your transition plan to move away from SHA-1 and noticed your intent to use SHA3-256 as the new hash function in the new Git repository format and protocol. Although this is a valid choice, we think that the new SHA-3 standard proposes alternatives that may also be interesting for your use cases. As designers of the Keccak function family, we thought we could jump in the mail thread and present these alternatives. SHA3-256, standardized in FIPS 202 , is a fixed-length hash function that provides the same interface and security level as SHA-256 (FIPS 180-4). SHA3-256's primary goal is to be drop-in compatible with the previous standard, and to allow a fast transition for applications that would already use SHA-256. Since your application did not use SHA-256, you are free to choose one of the alternatives listed below. * SHAKE128 SHAKE128, defined in FIPS 202, is an eXtendable-Output Function (XOF) that generates digests of any size. In your case, you would use SHAKE128 the same way you would use SHA3-256, just truncating the output at 256 bits. In that case, SHAKE128 provides a security level of 128 bits against all generic attacks, including collisions, preimages, etc. We think this security level is appropriate for your application since this is the maximum you can get with 256-bit tags in the case of collision attacks, and this level is beyond computation reach for any adversary in the foreseeable future. The immediate benefit of using SHAKE128 versus SHA3-256 is a performance gain of roughly 20%, both for SW and HW implementations. On Intel Core i5-6500, SHAKE128 throughput is 430MiB/s. * ParallelHash128 ParallelHash128 (PH128), defined in NIST Special Publication 800-185 (SP800-185, SHA-3 Derived Functions ), is a XOF implementing a tree hash mode on top of SHAKE128 (in fact cSHAKE128) to provide higher performance for large-file hashing. The tree mode is designed to exploit any available parallelism on the CPU, either through vector instructions or availability of multiple cores. Note that the chosen level of parallelism does not impact the final result, which improves interoperability. PH128 offers the same security level and interface as SHAKE128. So likewise, you just truncate the output at 256 bits. The net advantage of using PH128 over SHAKE128 is a huge performance boost when hashing big files. The advantage depends of course on the number of cores used for hashing and their architecture. On an Intel Core i5-6500 (Skylake), with a single-core, PH128 is faster than SHAKE128 by a factor 3 and than SHA-1 by a factor 1.5 over long messages, with a throughput of 1320MiB/s. * KangarooTwelve KangarooTwelve (K12)  is a very fast parallel and secure XOF we defined for applications that require higher performance that the FIPS 202 and SP800-185 functions provide, while retaining the same flexibility and basis of security. K12 is very similar to PH128. It uses the same cryptographic primitive (Keccak-p, defined in FIPS 202), the same sponge construction, a similar tree hashing mode, and targets the same generic security level (128 bits). The main differences are the number of rounds for the inner permutation, which is reduced to 12, and the tree mode parameters, which are optimized for both small and long messages. Again, the benefit of using K12 over PH128 is performance. K12 is twice as fast as SHAKE128 for short messages, i.e. 820MiB/s on Intel Core i5-6500, and twice as fast as PH128 over long messages, i.e. 2500MiB/s on the same platform. If performance is not your primary concern, we suggest to use SHAKE128 as the default hash function, and optionally use ParallelHash128 for hashing big files. Both functions offer a considerable security margin and are standardized algorithms. On the longer term, provided HW acceleration, SHAKE128 alone would easily outperform SHA-1 thanks to its design. If however you value first performance, or if you would like to promote adoption of the new repository format by offering higher performance, then KangarooTwelve is the right candidate. On modern CPU, K12 offers equal performance as SHA-1 for small messages and outperforms it by a factor 3 for long messages. Regarding security, although K12 offers of course a smaller security margin than other alternatives, it inherits the security assurance built up for Keccak and the FIPS 202 functions. As of today, the best practical attack broke 6 rounds of Keccak-p, with 2^50 computation effort. The 12 rounds of K12 offers then a comfortable security margin . Lately, we made a presentation at FOSDEM covering the latest development over the Keccak family . You can find reference and optimized implementations of the algorithms listed above in the Keccak Code Package . Also, if you have questions, don't hesitate to contact us. Kind regards, The Keccak Team Links  FIPS 202, http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf.  NIST SP 800-185, http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-185.pdf.  KangarooTwelve, http://keccak.noekeon.org/kangarootwelve.html.  Keccak Crunchy Crypto Collision and Pre-image Contest, http://keccak.noekeon.org/crunchy_contest.html.  FOSDEM 2017, Portfolio of optimized cryptographic functions based on Keccak, https://fosdem.org/2017/schedule/event/keccak/.  Keccak Code Package, https://github.com/gvanas/KeccakCodePackage.
next prev parent reply index Thread overview: 56+ messages in thread (expand / mbox.gz / Atom feed / [top]) 2017-03-04 1:12 Jonathan Nieder 2017-03-05 2:35 ` Linus Torvalds 2017-03-06 0:26 ` brian m. carlson 2017-03-06 18:24 ` Brandon Williams 2017-06-15 10:30 ` Which hash function to use, was " Johannes Schindelin 2017-06-15 11:05 ` Mike Hommey 2017-06-15 13:01 ` Jeff King 2017-06-15 16:30 ` Ævar Arnfjörð Bjarmason 2017-06-15 19:34 ` Johannes Schindelin 2017-06-15 21:59 ` Adam Langley 2017-06-15 22:41 ` brian m. carlson 2017-06-15 23:36 ` Ævar Arnfjörð Bjarmason 2017-06-16 0:17 ` brian m. carlson 2017-06-16 6:25 ` Ævar Arnfjörð Bjarmason 2017-06-16 13:24 ` Johannes Schindelin 2017-06-16 17:38 ` Adam Langley 2017-06-16 20:52 ` Junio C Hamano 2017-06-16 21:12 ` Junio C Hamano 2017-06-16 21:24 ` Jonathan Nieder 2017-06-16 21:39 ` Ævar Arnfjörð Bjarmason 2017-06-16 20:42 ` Jeff King 2017-06-19 9:26 ` Johannes Schindelin 2017-06-15 21:10 ` Mike Hommey 2017-06-16 4:30 ` Jeff King 2017-06-15 17:36 ` Brandon Williams 2017-06-15 19:20 ` Junio C Hamano 2017-06-15 19:13 ` Jonathan Nieder 2017-03-07 0:17 ` RFC v3: " Jonathan Nieder 2017-03-09 19:14 ` Shawn Pearce 2017-03-09 20:24 ` Jonathan Nieder 2017-03-10 19:38 ` Jeff King 2017-03-10 19:55 ` Jonathan Nieder 2017-03-05 11:02 ` RFC: " David Lang [not found] ` <CA+dhYEXHbQfJ6KUB1tWS9u1MLEOJL81fTYkbxu4XO-i+379LPw@mail.gmail.com> 2017-03-06 9:43 ` Jeff King 2017-03-06 23:40 ` Jonathan Nieder 2017-03-07 0:03 ` Mike Hommey 2017-03-06 8:43 ` Jeff King 2017-03-06 18:39 ` Jonathan Tan 2017-03-06 19:22 ` Linus Torvalds 2017-03-06 19:59 ` Brandon Williams 2017-03-06 21:53 ` Junio C Hamano 2017-03-07 8:59 ` Jeff King 2017-03-06 18:43 ` Junio C Hamano 2017-03-07 18:57 ` Ian Jackson 2017-03-07 19:15 ` Linus Torvalds 2017-03-08 11:20 ` Ian Jackson 2017-03-08 15:37 ` Johannes Schindelin 2017-03-08 15:40 ` Johannes Schindelin 2017-03-20 5:21 ` Use base32? Jason Hennessey 2017-03-20 5:58 ` Michael Steuer 2017-03-20 8:05 ` Jacob Keller 2017-03-21 3:07 ` Michael Steuer 2017-03-13 9:24 ` The Keccak Team [this message] 2017-03-13 17:48 ` RFC: Another proposed hash function transition plan Jonathan Nieder 2017-03-13 18:34 ` ankostis 2017-03-17 11:07 ` Johannes Schindelin
Reply instructions: You may reply publically to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style List information: http://vger.kernel.org/majordomo-info.html * Reply to all the recipients using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
firstname.lastname@example.org mailing list mirror (one of many) Archives are clonable: git clone --mirror https://public-inbox.org/git git clone --mirror http://ou63pmih66umazou.onion/git git clone --mirror http://czquwvybam4bgbro.onion/git git clone --mirror http://hjrcffqmbrq6wope.onion/git Newsgroups are available over NNTP: nntp://news.public-inbox.org/inbox.comp.version-control.git nntp://ou63pmih66umazou.onion/inbox.comp.version-control.git nntp://czquwvybam4bgbro.onion/inbox.comp.version-control.git nntp://hjrcffqmbrq6wope.onion/inbox.comp.version-control.git nntp://news.gmane.org/gmane.comp.version-control.git note: .onion URLs require Tor: https://www.torproject.org/ or Tor2web: https://www.tor2web.org/ AGPL code for this site: git clone https://public-inbox.org/ public-inbox