From: "brian m. carlson" <firstname.lastname@example.org> To: Jonathan Nieder <email@example.com> Cc: firstname.lastname@example.org, Johannes Schindelin <Johannes.Schindelin@gmx.de>, demerphq <email@example.com>, Linus Torvalds <firstname.lastname@example.org>, Adam Langley <email@example.com>, The Keccak Team <firstname.lastname@example.org> Subject: Re: Hash algorithm analysis Date: Mon, 11 Jun 2018 22:35:20 +0000 [thread overview] Message-ID: <20180611223520.GF38834@genre.crustytoothpaste.net> (raw) In-Reply-To: <20180611192942.GC20665@aiede.svl.corp.google.com> [-- Attachment #1: Type: text/plain, Size: 4498 bytes --] On Mon, Jun 11, 2018 at 12:29:42PM -0700, Jonathan Nieder wrote: > 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? https://github.com/bk2204/git.git, test-hashes branch. You will need to have libb2 and OPENSSL_SHA1 set. It's a bit of a hack, so don't look too hard. > [...] > > 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 Thanks for that reference. > 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. I agree. Implementation availability is important. Whatever we provide is likely going to be portable C code, which is going to be slower than an optimized implementation. > [...] > > * 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? You'll notice below that I have both BLAKE2bp with and without threading. I recompiled libb2 to not use threading, and it still didn't perform as well. libb2 is written by the authors of BLAKE2, so it's the most favorable implementation we're likely to get. > [...] > > |=== > > | 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. Correct. BLAKE2b in OpenSSL is currently 512-bit only, but it's intended to add support for 256-bit versions soon. I think the benefit of sticking to one hash function altogether is significant, so I think we should one that has good all-around performance instead of trying to split between different ones. > 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. With the exception of variations in preimage security, I expect that's correct. I think implementation availability and performance are the best candidates for consideration. > My understanding of the discussion so far: > > Keccak team encourages us to consider a variant like K12 instead of > SHA3. While I think K12 is an interesting algorithm, I'm not sure we're going to get as good of performance out of it as we might want due to the lack of implementations. -- brian m. carlson: Houston, Texas, US OpenPGP: https://keybase.io/bk2204 [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 867 bytes --]
next prev parent reply other threads:[~2018-06-11 22:35 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 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 [this message] 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=20180611223520.GF38834@genre.crustytoothpaste.net \ --email@example.com \ --cc=Johannes.Schindelin@gmx.de \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --subject='Re: Hash algorithm analysis' \ /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
Code repositories for project(s) associated with this inbox: https://80x24.org/mirrors/git.git This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).