git.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Johannes Schindelin <Johannes.Schindelin@gmx.de>
To: Joan Daemen <jda@noekeon.org>
Cc: Gilles Van Assche <gilles.vanassche@st.com>,
	Linus Torvalds <torvalds@linux-foundation.org>,
	demerphq <demerphq@gmail.com>,
	Brandon Williams <bmwill@google.com>,
	Junio C Hamano <gitster@pobox.com>,
	Jonathan Nieder <jrnieder@gmail.com>,
	Git Mailing List <git@vger.kernel.org>,
	Stefan Beller <sbeller@google.com>,
	Jonathan Tan <jonathantanmy@google.com>,
	Jeff King <peff@peff.net>, David Lang <david@lang.hm>,
	"brian m. carlson" <sandals@crustytoothpaste.net>,
	Keccak Team <keccak@noekeon.org>
Subject: Re: RFC v3: Another proposed hash function transition plan
Date: Mon, 2 Oct 2017 16:26:49 +0200 (CEST)	[thread overview]
Message-ID: <alpine.DEB.2.21.1.1710021601380.40514@virtualbox> (raw)
In-Reply-To: <6d96ec902dc1d500ba3fcb11d31b2015@mail.noekeon.org>

Hi Joan,

On Sun, 1 Oct 2017, Joan Daemen wrote:

> On 30/09/17 00:33, Johannes Schindelin wrote:
> 
> > As far as Git is concerned, we not only care about the source code of
> > the hash algorithm we use, we need to care even more about what you
> > call "executable": ready-to-use, high quality, well-tested
> > implementations.
> > 
> > We carry source code for SHA-1 as part of Git's source code, which was
> > hand-tuned to be as fast as Linus could get it, which was tricky given
> > that the tuning should be general enough to apply to all common intel
> > CPUs.
> > 
> > This hand-crafted code was blown out of the water by OpenSSL's SHA-1
> > in our tests here at Microsoft, thanks to the fact that OpenSSL does
> > vectorized SHA-1 computation now.
> > 
> > To me, this illustrates why it is not good enough to have only a
> > reference implementation available at our finger tips. Of course,
> > above-mentioned OpenSSL supports SHA-256 and SHA3-256, too, and at
> > least recent versions vectorize those, too.
> 
> There is a lot of high-quality optimized code for all SHA-3 functions
> and many CPUs in the Keccak code package
> https://github.com/gvanas/KeccakCodePackage but also OpenSSL contains
> some good SHA-3 code and then there are all those related to Ethereum.
> 
> By the way, you speak about SHA3-256, but the right choice would be to
> use SHAKE128. Well, what is exactly the right choice depends on what you
> want. If you want to have a function in the SHA3 standard (FIPS 202), it
> is SHAKE128.  You can boost performance on high-end CPUs by adopting
> Parallelhash from NIST SP 800-185, still a NIST standard. You can
> multiply that performance again by a factor of 2 by adopting
> KangarooTwelve. This is our (Keccak team) proposal for a parallelizable
> Keccak-based hash function that has a safety margin comparable to that
> of the SHA-2 functions. See https://keccak.team/kangarootwelve.html May
> I also suggest you read https://keccak.team/2017/is_sha3_slow.html

Thanks.

I have to admit that all those names that do not start with SHA and do not
end in 256 make me a bit dizzy.

> > Back to Intel processors: I read some vague hints about extensions
> > accelerating SHA-256 computation on future Intel processors, but not
> > SHA3-256.
> > 
> > It would make sense, of course, that more crypto libraries and more
> > hardware support would be available for SHA-256 than for SHA3-256
> > given the time since publication: 16 vs 5 years (I am playing it loose
> > here, taking just the year into account, not the exact date, so please
> > treat that merely as a ballpark figure).
> > 
> > So from a practical point of view, I wonder what your take is on, say,
> > hardware support for SHA3-256. Do you think this will become a focus
> > soon?
> 
> I think this is a chicken-and-egg problem. In any case, hardware support
> for one SHA3-256 will also work for the other SHA3 and SHAKE functions
> as they all use the same underlying primitive: the Keccak-f permutation.
> This is not the case for SHA2 because SHA224 and SHA256 use a different
> compression function than SHA384, SHA512, SHA512/224 and SHA512/256.

Okay.

So given that Git does not exactly have a big sway on hardware vendors, we
would have to hope that some other chicken lays that egg.

> > Also, what is your take on the question whether SHA-256 is good
> > enough?  SHA-1 was broken theoretically already 10 years after it was
> > published (which unfortunately did not prevent us from baking it into
> > Git), after all, while SHA-256 is 16 years old and the only known
> > weakness does not apply to Git's usage?
> 
> SHA-256 is more conservative than SHA-1 and I don't expect it to be
> broken in the coming decades (unless NSA inserted a backdoor but I don't
> think that is likely). But looking at the existing cryptanalysis, I
> think it is even less likely that I SHAKE128, ParallelHash or
> KangarooTwelve will be broken anytime.

That's reassuring! ;-)

> > Also, while I have the attention of somebody who knows a heck more
> > about cryptography than Git's top 10 committers combined: how soon do
> > you expect practical SHA-1 attacks that are much worse than what we
> > already have seen? I am concerned that if we do not move fast enough
> > to a new hash algorithm, and somebody finds a way in the meantime to
> > craft arbitrary messages given a prefix and an SHA-1, then we have a
> > huge problem on our hands.
> 
> This is hard to say. To be honest, when witnessing the first MD5
> collisions I did not expect them to lead to some real world attacks and
> just a few years later we saw real-world forged certificates based on
> MD5 collisions. And SHA-1 has a lot in common with MD5...

Oh, okay. I did not realize that MD5 and SHA-1 are so similar in design,
thank you for educating me!

> But let me end with a philosophical note. Independent of all the
> arguments for and against, I think this is ultimately about doing the
> right thing. The choice is here between SHA1/SHA2 on the one hand and
> SHA3/Keccak on the other.  The former standards are imposed on us by NSA
> and the latter are the best that came out of an open competition
> involving all experts in the field worldwide.  What would be closest to
> the philosophy of Git (and by extension Linux or open-source in
> general)?

Heh. Do you realize that you are talking to a Microsoftie, i.e. one of the
"evil company"? ;-)

So philosophically, I am much more pragmatic. Or maybe I am not, after
all, I joined a company at a time when it is arguably going through one of
the most dramatic cultural changes any company has seen lately (a year
ago, we became #1 contributor on GitHub according to Business Insider, and
as far as I can tell, we're not willing to pass that belt to anyone else).

But when it comes to the philosophy of Git, I fear I have to disappoint
you: Git's fundamental concepts were not developed in an open process. Git
even so much as rejected professional advice *not* to bake SHA-1 into
everything.

Of course, we are undoing this damage right now, and your input helps
greatly, I would think.

While I feel reassured by your response that SHA-256 would be "good
enough" and would have some real-life benefits of announced hardware
support, I would now also feel comfortable if my preference was overruled
in the end, in favor of a hash from the Keccak family. I would understand,
for example, if the parallel option turned out to be enticing enough for
other core Git contributors to aim for, say, K12).

Again, thank you very much for chiming in,
Johannes

  reply	other threads:[~2017-10-02 14:27 UTC|newest]

Thread overview: 113+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-03-04  1:12 RFC: Another proposed hash function transition plan 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-09-28  4:43       ` [PATCH v4] technical doc: add a design doc for hash function transition Jonathan Nieder
2017-09-29  6:06         ` Junio C Hamano
2017-09-29  8:09           ` Junio C Hamano
2017-09-29 17:34           ` Jonathan Nieder
2017-10-02  8:25             ` Junio C Hamano
2017-10-02 19:41             ` Jason Cooper
2017-10-02  9:02         ` Junio C Hamano
2017-10-02 19:23         ` Jason Cooper
2017-10-03  5:40         ` Junio C Hamano
2017-10-03 13:08           ` Jason Cooper
2017-10-04  1:44         ` Junio C Hamano
2017-09-06  6:28     ` RFC v3: Another proposed hash function transition plan Junio C Hamano
2017-09-08  2:40       ` Junio C Hamano
2017-09-08  3:34         ` Jeff King
2017-09-11 18:59         ` Brandon Williams
2017-09-13 12:05           ` Johannes Schindelin
2017-09-13 13:43             ` demerphq
2017-09-13 22:51               ` Jonathan Nieder
2017-09-14 18:26                 ` Johannes Schindelin
2017-09-14 18:40                   ` Jonathan Nieder
2017-09-14 22:09                     ` Johannes Schindelin
2017-09-13 23:30               ` Linus Torvalds
2017-09-14 18:45                 ` Johannes Schindelin
2017-09-18 12:17                   ` Gilles Van Assche
2017-09-18 22:16                     ` Johannes Schindelin
2017-09-19 16:45                       ` Gilles Van Assche
2017-09-29 13:17                         ` Johannes Schindelin
2017-09-29 14:54                           ` Joan Daemen
2017-09-29 22:33                             ` Johannes Schindelin
2017-09-30 22:02                               ` Joan Daemen
2017-10-02 14:26                                 ` Johannes Schindelin [this message]
2017-09-18 22:25                     ` Jonathan Nieder
2017-09-26 17:05                   ` Jason Cooper
2017-09-26 22:11                     ` Johannes Schindelin
2017-09-26 22:25                       ` [PATCH] technical doc: add a design doc for hash function transition Stefan Beller
2017-09-26 23:38                         ` Jonathan Nieder
2017-09-26 23:51                       ` RFC v3: Another proposed hash function transition plan Jonathan Nieder
2017-10-02 14:54                         ` Jason Cooper
2017-10-02 16:50                           ` Brandon Williams
2017-10-02 14:00                       ` Jason Cooper
2017-10-02 17:18                         ` Linus Torvalds
2017-10-02 19:37                           ` Jeff King
2017-09-13 16:30             ` Jonathan Nieder
2017-09-13 21:52               ` Junio C Hamano
2017-09-13 22:07                 ` Stefan Beller
2017-09-13 22:18                   ` Jonathan Nieder
2017-09-14  2:13                     ` Junio C Hamano
2017-09-14 15:23                       ` Johannes Schindelin
2017-09-14 15:45                         ` demerphq
2017-09-14 22:06                           ` Johannes Schindelin
2017-09-13 22:15                 ` Junio C Hamano
2017-09-13 22:27                   ` Jonathan Nieder
2017-09-14  2:10                     ` Junio C Hamano
2017-09-14 12:39               ` Johannes Schindelin
2017-09-14 16:36                 ` Brandon Williams
2017-09-14 18:49                 ` Jonathan Nieder
2017-09-15 20:42                   ` Philip Oakley
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 ` RFC: Another proposed hash function transition plan The Keccak Team
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 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

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=alpine.DEB.2.21.1.1710021601380.40514@virtualbox \
    --to=johannes.schindelin@gmx.de \
    --cc=bmwill@google.com \
    --cc=david@lang.hm \
    --cc=demerphq@gmail.com \
    --cc=gilles.vanassche@st.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=jda@noekeon.org \
    --cc=jonathantanmy@google.com \
    --cc=jrnieder@gmail.com \
    --cc=keccak@noekeon.org \
    --cc=peff@peff.net \
    --cc=sandals@crustytoothpaste.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
Be sure your reply has a Subject: header at the top and a blank line before the message body.
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 NNTP newsgroup(s).