git@vger.kernel.org mailing list mirror (one of many)
 help / Atom feed
From: The Keccak Team <keccak@noekeon.org>
To: Jonathan Nieder <jrnieder@gmail.com>,
	git@vger.kernel.org
Cc: sbeller@google.com,
	bmwill@google.com,
	jonathantanmy@google.com,
	peff@peff.net,
	Linus Torvalds <torvalds@linux-foundation.org>
Subject: Re: RFC: Another proposed hash function transition plan
Date: Mon, 13 Mar 2017 10:24:25 +0100
Message-ID: <91a34c5b-7844-3db2-cf29-411df5bcf886@noekeon.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 [1], 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 [2]), 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) [3] 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 [4].


Lately, we made a presentation at FOSDEM covering the latest development
over the Keccak family [5].  You can find reference and optimized
implementations of the algorithms listed above in the Keccak Code
Package [6]. Also, if you have questions, don't hesitate to contact us.


Kind regards,
The Keccak Team

Links
 [1]   FIPS 202,
       http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf.
 [2]   NIST SP 800-185,

http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-185.pdf.
 [3]   KangarooTwelve, http://keccak.noekeon.org/kangarootwelve.html.
 [4]   Keccak Crunchy Crypto Collision and Pre-image Contest,
       http://keccak.noekeon.org/crunchy_contest.html.
 [5]   FOSDEM 2017, Portfolio of optimized cryptographic functions based
       on Keccak, https://fosdem.org/2017/schedule/event/keccak/.
 [6]   Keccak Code Package, https://github.com/gvanas/KeccakCodePackage.



  parent reply index

Thread overview: 33+ 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-03-07  0:17   ` RFC v3: Another proposed hash function transition plan 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 ` 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   ` 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 \
    --in-reply-to=91a34c5b-7844-3db2-cf29-411df5bcf886@noekeon.org \
    --to=keccak@noekeon.org \
    --cc=bmwill@google.com \
    --cc=git@vger.kernel.org \
    --cc=jonathantanmy@google.com \
    --cc=jrnieder@gmail.com \
    --cc=peff@peff.net \
    --cc=sbeller@google.com \
    --cc=torvalds@linux-foundation.org \
    /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

git@vger.kernel.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