From: Jonathan Nieder <jrnieder@gmail.com> To: "brian m. carlson" <sandals@crustytoothpaste.net> Cc: git@vger.kernel.org, Johannes Schindelin <Johannes.Schindelin@gmx.de>, demerphq <demerphq@gmail.com>, Linus Torvalds <torvalds@linux-foundation.org>, Adam Langley <agl@google.com>, The Keccak Team <keccak@noekeon.org> Subject: Re: Hash algorithm analysis Date: Mon, 11 Jun 2018 12:29:42 -0700 Message-ID: <20180611192942.GC20665@aiede.svl.corp.google.com> (raw) In-Reply-To: <20180609224913.GC38834@genre.crustytoothpaste.net> Hi, brian m. carlson wrote: > == Discussion of Candidates > > I've implemented and tested the following algorithms, all of which are > 256-bit (in alphabetical order): Thanks for this. Where can I read your code? [...] > I also rejected some other candidates. I couldn't find any reference or > implementation of SHA256×16, so I didn't implement it. Reference: https://eprint.iacr.org/2012/476.pdf If consensus turns toward it being the right hash function to use, then we can pursue finding or writing a good high-quality implementation. But I tend to suspect that the lack of wide implementation availability is a reason to avoid it unless we find SHA-256 to be too slow. [...] > * BLAKE2bp, as implemented in libb2, uses OpenMP (and therefore > multithreading) by default. It was no longer possible to run the > testsuite with -j3 on my laptop in this configuration. My understanding is that BLAKE2bp is better able to make use of simd instructions than BLAKE2b. Is there a way to configure libb2 to take advantage of that without multithreading? E.g. https://github.com/sneves/blake2-avx2 looks promising for that. [...] > |=== > | Implementation | 256 B | 1 KiB | 8 KiB | 16 KiB | > | SHA-1 (OpenSSL) | 513963 | 685966 | 748993 | 754270 | > | BLAKE2b (libb2) | 488123 | 552839 | 576246 | 579292 | > | SHA-512/256 (OpenSSL) | 181177 | 349002 | 499113 | 495169 | > | BLAKE2bp (libb2) | 139891 | 344786 | 488390 | 522575 | > | SHA-256 (OpenSSL) | 264276 | 333560 | 357830 | 355761 | > | KangarooTwelve | 239305 | 307300 | 355257 | 364261 | > | SHAKE128 (OpenSSL) | 154775 | 253344 | 337811 | 346732 | > | SHA3-256 (OpenSSL) | 128597 | 185381 | 198931 | 207365 | > | BLAKE2bp (libb2; threaded) | 12223 | 49306 | 132833 | 179616 | > |=== That's a bit surprising, since my impression (e.g. in the SUPERCOP benchmarks you cite) is that there are secure hash functions that allow comparable or even faster performance than SHA-1 with large inputs on a single core. In Git we also care about performance with small inputs, creating a bit of a trade-off. More on the subject of blake2b vs blake2bp: - blake2b is faster for small inputs (under 1k, say). If this is important then we could set a threshold, e.g. 512 bytes, for swtiching to blake2bp. - blake2b is supported in OpenSSL and likely to get x86-optimized versions in the future. blake2bp is not in OpenSSL. [...] > == Summary > > The algorithms with the greatest implementation availability are > SHA-256, SHA3-256, BLAKE2b, and SHAKE128. > > In terms of command-line availability, BLAKE2b, SHA-256, SHA-512/256, > and SHA3-256 should be available in the near future on a reasonably > small Debian, Ubuntu, or Fedora install. > > As far as security, the most conservative choices appear to be SHA-256, > SHA-512/256, and SHA3-256. SHA-256x16 has the same security properties as SHA-256. Picking between those two is a tradeoff between performance and implementation availability. My understanding is that all the algorithms we're discussing are believed to be approximately equivalent in security. That's a strange thing to say when e.g. K12 uses fewer rounds than SHA3 of the same permutation, but it is my understanding nonetheless. We don't know yet how these hash algorithms will ultimately break. My understanding of the discussion so far: Keccak team encourages us[1] to consider a variant like K12 instead of SHA3. AGL explains[2] that the algorithms considered all seem like reasonable choices and we should decide using factors like implementation ease and performance. If we choose a Keccak-based function, AGL also[3] encourages using a variant like K12 instead of SHA3. Dscho strongly prefers[4] SHA-256, because of - wide implementation availability, including in future hardware - has been widely analyzed - is fast Yves Orton and Linus Torvalds prefer[5] SHA3 over SHA2 because of how it is constructed. Thanks, Jonathan [1] https://public-inbox.org/git/91a34c5b-7844-3db2-cf29-411df5bcf886@noekeon.org/ [2] https://public-inbox.org/git/CAL9PXLzhPyE+geUdcLmd=pidT5P8eFEBbSgX_dS88knz2q_LSw@mail.gmail.com/ [3] https://www.imperialviolet.org/2017/05/31/skipsha3.html [4] https://public-inbox.org/git/alpine.DEB.2.21.1.1706151122180.4200@virtualbox/ [5] https://public-inbox.org/git/CA+55aFwUn0KibpDQK2ZrxzXKOk8-aAub2nJZQqKCpq1ddhDcMQ@mail.gmail.com/
next prev parent reply other threads:[~2018-06-11 19:29 UTC|newest] Thread overview: 66+ messages / expand[flat|nested] mbox.gz Atom feed top 2018-06-09 20:56 State of NewHash work, future directions, and discussion brian m. carlson 2018-06-09 21:26 ` Ævar Arnfjörð Bjarmason 2018-06-09 22:49 ` Hash algorithm analysis brian m. carlson 2018-06-11 19:29 ` Jonathan Nieder [this message] 2018-06-11 20:20 ` Linus Torvalds 2018-06-11 23:27 ` Ævar Arnfjörð Bjarmason 2018-06-12 0:11 ` David Lang 2018-06-12 0:45 ` Linus Torvalds 2018-06-11 22:35 ` brian m. carlson 2018-06-12 16:21 ` Gilles Van Assche 2018-06-13 23:58 ` brian m. carlson 2018-06-15 10:33 ` Gilles Van Assche 2018-07-20 21:52 ` brian m. carlson 2018-07-21 0:31 ` Jonathan Nieder 2018-07-21 19:52 ` Ævar Arnfjörð Bjarmason 2018-07-21 20:25 ` brian m. carlson 2018-07-21 22:38 ` Johannes Schindelin 2018-07-21 23:09 ` Linus Torvalds 2018-07-21 23:59 ` brian m. carlson 2018-07-22 9:34 ` Eric Deplagne 2018-07-22 14:21 ` brian m. carlson 2018-07-22 14:55 ` Eric Deplagne 2018-07-26 10:05 ` Johannes Schindelin 2018-07-22 15:23 ` Joan Daemen 2018-07-22 18:54 ` Adam Langley 2018-07-26 10:31 ` Johannes Schindelin 2018-07-23 12:40 ` demerphq 2018-07-23 12:48 ` Sitaram Chamarty 2018-07-23 12:55 ` demerphq 2018-07-23 18:23 ` Linus Torvalds 2018-07-23 17:57 ` Stefan Beller 2018-07-23 18:35 ` Jonathan Nieder 2018-07-24 19:01 ` Edward Thomson 2018-07-24 20:31 ` Linus Torvalds 2018-07-24 20:49 ` Jonathan Nieder 2018-07-24 21:13 ` Junio C Hamano 2018-07-24 22:10 ` brian m. carlson 2018-07-30 9:06 ` Johannes Schindelin 2018-07-30 20:01 ` Dan Shumow 2018-08-03 2:57 ` Jonathan Nieder 2018-09-18 15:18 ` Joan Daemen 2018-09-18 15:32 ` Jonathan Nieder 2018-09-18 16:50 ` Linus Torvalds 2018-07-25 8:30 ` [PATCH 0/2] document that NewHash is now SHA-256 Ævar Arnfjörð Bjarmason 2018-07-25 8:30 ` [PATCH 1/2] doc hash-function-transition: note the lack of a changelog Ævar Arnfjörð Bjarmason 2018-07-25 8:30 ` [PATCH 2/2] doc hash-function-transition: pick SHA-256 as NewHash Ævar Arnfjörð Bjarmason 2018-07-25 16:45 ` Junio C Hamano 2018-07-25 17:25 ` Jonathan Nieder 2018-07-25 21:32 ` Junio C Hamano 2018-07-26 13:41 ` [PATCH v2 " Ævar Arnfjörð Bjarmason 2018-08-03 7:20 ` Jonathan Nieder 2018-08-03 16:40 ` Junio C Hamano 2018-08-03 17:01 ` Linus Torvalds 2018-08-03 16:42 ` Linus Torvalds 2018-08-03 17:43 ` Ævar Arnfjörð Bjarmason 2018-08-04 8:52 ` Jonathan Nieder 2018-08-03 17:45 ` brian m. carlson 2018-07-25 22:56 ` [PATCH " brian m. carlson 2018-06-11 21:19 ` Hash algorithm analysis Ævar Arnfjörð Bjarmason 2018-06-21 8:20 ` Johannes Schindelin 2018-06-21 22:39 ` brian m. carlson 2018-06-11 18:09 ` State of NewHash work, future directions, and discussion Duy Nguyen 2018-06-12 1:28 ` brian m. carlson 2018-06-11 19:01 ` Jonathan Nieder 2018-06-12 2:28 ` brian m. carlson 2018-06-12 2:42 ` Jonathan Nieder
Reply instructions: You may reply publicly 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 using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20180611192942.GC20665@aiede.svl.corp.google.com \ --to=jrnieder@gmail.com \ --cc=Johannes.Schindelin@gmx.de \ --cc=agl@google.com \ --cc=demerphq@gmail.com \ --cc=git@vger.kernel.org \ --cc=keccak@noekeon.org \ --cc=sandals@crustytoothpaste.net \ --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 list mirror (unofficial, one of many) This inbox may be cloned and mirrored by anyone: 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 # If you have public-inbox 1.1+ installed, you may # initialize and index your mirror using the following commands: public-inbox-init -V1 git git/ https://public-inbox.org/git \ git@vger.kernel.org public-inbox-index git Example config snippet for mirrors. 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.io/gmane.comp.version-control.git note: .onion URLs require Tor: https://www.torproject.org/ code repositories for the project(s) associated with this inbox: https://80x24.org/mirrors/git.git AGPL code for this site: git clone https://public-inbox.org/public-inbox.git