220 12572 article Path: news.gmane.org!not-for-mail From: Howard Hinnant Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Cryptographic hash functions reloaded [was Interest in cryptographic functions within the standard library] Date: Thu, 28 Aug 2014 22:58:25 -0400 Lines: 342 Approved: news@gmane.org Message-ID: References: <53F8F620.3090701@gmx.de> <53F989E9.5090701@gmx.net> <53FE5E8A.2090003@gmx.net> <6B0F9092-02BD-46A1-871F-14746F3938BA@gmail.com> <53FFA90E.4080501@gmx.net> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 (Mac OS X Mail 7.3 \(1878.6\)) Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1409281118 8881 80.91.229.3 (29 Aug 2014 02:58:38 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 29 Aug 2014 02:58:38 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBCK2HM4L6YERBVWY76PQKGQEVKPBBEY@isocpp.org Fri Aug 29 04:58:32 2014 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-ie0-f199.google.com ([209.85.223.199]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1XNCOV-0006nu-Q1 for gclcip-std-proposals@m.gmane.org; Fri, 29 Aug 2014 04:58:32 +0200 Original-Received: by mail-ie0-f199.google.com with SMTP id tr6sf12022522ieb.6 for ; Thu, 28 Aug 2014 19:58:30 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date :message-id:references:to:x-original-sender :x-original-authentication-results:reply-to:precedence:mailing-list :list-id:list-post:list-help:list-archive:list-subscribe :list-unsubscribe:content-type:content-transfer-encoding; bh=+jT3uZ22SDbNcl+Kas3t2fZZuW5x1+Ue0Iq5li290b4=; b=YLDEBaEjUScIUHADXm/vJXElQTm4QC7fOljVm1s2577LE+VVarD8YGZnl8MHzF7qSs 95XnHSaKtWNl3tlWXKEly0Ws78XgoWOQFQbShRlRqvONcn/xboAkf6FQdiv0oMijza7D d9vF4M4xGwBjwRBJ8gbcs77ospm2/Wyzm0UFiJOncyQwRTJzABymU4w9rUL2pG0Von0w 9VC3P++DMcKj5WLESkXf4StIx/Fx01BYRuqwkjml7uo4LI0wgoG0FxizPCyW/pu6x8au Tzdn+wc/Dx8qHaoYzvQV9Ite/R68wPviCUYss7Lt2vUo1GfGrpaIQTX41Ocdvef6uvWF S6xg== X-Gm-Message-State: ALoCoQlycODkU61ASR/8trppy+WQDX2Anh2xBtIslrjshYI/r0jLUEzEzGD6NkwAiIUtGUZLenap X-Received: by 10.50.57.111 with SMTP id h15mr683682igq.3.1409281110803; Thu, 28 Aug 2014 19:58:30 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.50.132.34 with SMTP id or2ls90814igb.33.gmail; Thu, 28 Aug 2014 19:58:29 -0700 (PDT) X-Received: by 10.50.164.202 with SMTP id ys10mr1120747igb.6.1409281109769; Thu, 28 Aug 2014 19:58:29 -0700 (PDT) Original-Received: from mail-ig0-x22d.google.com (mail-ig0-x22d.google.com [2607:f8b0:4001:c05::22d]) by mx.google.com with ESMTPS id uh2si11283876igc.33.2014.08.28.19.58.29 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Thu, 28 Aug 2014 19:58:29 -0700 (PDT) Received-SPF: pass (google.com: domain of howard.hinnant@gmail.com designates 2607:f8b0:4001:c05::22d as permitted sender) client-ip=2607:f8b0:4001:c05::22d; Original-Received: by mail-ig0-f173.google.com with SMTP id h18so9035288igc.12 for ; Thu, 28 Aug 2014 19:58:29 -0700 (PDT) X-Received: by 10.50.80.45 with SMTP id o13mr1012926igx.7.1409281109509; Thu, 28 Aug 2014 19:58:29 -0700 (PDT) Original-Received: from [10.0.1.2] (cpe-24-58-234-96.twcny.res.rr.com. [24.58.234.96]) by mx.google.com with ESMTPSA id ik8sm186154igb.0.2014.08.28.19.58.27 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Thu, 28 Aug 2014 19:58:28 -0700 (PDT) In-Reply-To: <53FFA90E.4080501@gmx.net> X-Mailer: Apple Mail (2.1878.6) X-Original-Sender: howard.hinnant@gmail.com X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of howard.hinnant@gmail.com designates 2607:f8b0:4001:c05::22d as permitted sender) smtp.mail=howard.hinnant@gmail.com; dkim=pass header.i=@gmail.com; dmarc=pass (p=NONE dis=NONE) header.from=gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:12572 Archived-At: On Aug 28, 2014, at 6:11 PM, Jens Maurer wrote: > On 08/28/2014 07:41 PM, Howard Hinnant wrote: >> I suspect you intended this as a private message, but it came through pu= blic.=20 >=20 > It was intended as a public message. Let's try something different: >=20 > Hi everybody! :-) >>> I'll have to ask a few more questions here. If something gets >>> standardized in this area, I'd like to see a roadmap how all >>> platforms supported by C++ can get portable (crypto) hash values, >>> even if not maximally efficient on "strange" environments. >>>=20 >>> I'm assuming that (in an abstract sense) a crypto hash algorithm >>> (and most others) hash a sequence of octets (i.e. 8-bit quantities). >>>=20 >>> (SHA256 and others can do odd trailing bits, but let's ignore >>> this for now.) >>>=20 >>> I presume I'm passing these octets to the hash algorithm using an >>> array of (unsigned) char, right? >>=20 >> As currently coded, there are hash_append overloads for both unsigned ch= ar, C-arrays of unsigned char, std::array, etc. There ar= e also hash_append overloads for all other arithmetic types, and std-define= d containers. For each type, the hash_append function is responsible for d= eciding how that type should present itself to a generic hashing algorithm. >=20 > I agree that the standard library should provide hash_append overloads fo= r > all scalar types and standard containers, including C-style arrays. > (Btw, does hash_append on a container also hash the size, or just the > contents, i.e. the sequence of elements?) As currently coded, the run-time-sized containers append the size of the co= ntainer. This is to prevent hash collision between: vector>{{}, {1}} and vector>{{1}, {}}, which if they did not include a size() in their message, would both result = in the same message to the hash algorithm, and thus both generate the same = the hash code. Append was chosen as opposed to prepend so that forward_list would not h= ave to traverse twice during hash_append. Markers such as "begin container" and "end container" were also considered,= but appending the size was considered to be simpler and more economical th= an the alternatives. > That's not what I'm concerned about here. I'm concerned about writing a > crypto hash sum that plays nicely with the framework, and is maximally > portable both in its implementation and its result value. >=20 >> For example an unsigned char would just say: Consume this byte! >=20 > A byte is not (necessarily) an octet. I'm concerned about this > particular gap. I think designing for a portable implementation of (for example) SHA256 for= non-8-bit-byte platforms is an over-reaching goal. Forgetting hash_append= , and even C++, and designing whatever API you cared for, how would you wri= te an implementation of SHA256 that was byte-size agnostic? And how would = that impact the API of SHA256? Today, the SHA256 implementations I've seen (written in C) are simply #ifde= f'd on endian, and are not portable to non-8-bit-byte platforms. The hash_= append proposal is not trying to impact this status-quo. I consider all of= this HashAlgorithm details to be worked out by the HashAlgorithm author. >>> Is this assumption also true for platforms where (unsigned) char >>> is e.g. 32-bits (DSPs)? If so, the following implementation doesn't >>> work there, because it makes no effort to split e.g. T=3D=3Dint (suppos= e >>> it's 32-bit) into four individual (unsigned) char objects. >>=20 >> The hash_append infrastructure makes no assumptions on the size of a byt= e. However concrete hashing algorithms (such as SHA256) most certainly wil= l make such assumptions. >=20 > I want to write a portable implementation of a hash sum that also > works on a machine where 1 =3D=3D sizeof(char) =3D=3D sizeof(int) (=3D 32= bits). I anxiously await your prototype. > If I've understood the interface correctly, both hashing an int x and > a char c will end up with a call to my hash algorithm h like this: >=20 > h(&x, 1); > h(&c, 1); >=20 > and the interface is type-erased (i.e. uses "void*" or "unsigned char*"). You are correct, assuming on this platform that all bits in both int and c= har participate in the type's representation. OTOH, if char is padded with= 24 bits of random values, the hash_append will be prohibited (by the speci= fication) from sending those random bits to the hash algorithm. hash_appen= d might (for example) zero all the padding bits before sending the byte to = the hashing algorithm. > On a usual platform, the calls will end up like this (ignoring endianess > for now): >=20 > h(&x, 4); > h(&c, 1); Correct again. > I don't think "h" will ever be able to produce the same hash sum on both > platforms, even if specifically tailored for the particular platform. > It seems too much information is lost on the sizeof(char) =3D=3D sizeof= (int) > platform. My understanding is that hash algorithms consume bytes (and sometim= es bits). They don't care what the type is. If we want to enforce that th= e same byte representation for two different types sends different byte str= eams to the hashing algorithm, hash_append is the right place to make that = customization. > One way to address this is to split the "int" into four octets and > assign a separate "unsigned char" for each octet in the hash_append > function on the DSP-style platform. Then both calls end up as >=20 > h(&x, 4); > h(&c, 1); The hash algorithm 'h' is going to see bytes, no matter what we do (void* o= r unsigned char*). Whether hashing algorithms change those bytes into octe= ts (or words) or not is completely within their implementation. If the committee proclaims that the "message" sent by a 32 bit int should b= e different than the "message" sent by a 32 bit char should be different, s= o be it. The current hash_append proposal purposefully does not dictate su= ch details. My feeling is that dictating such details is bound to adversel= y impact efficiency, but I am happy to see those details worked out in comm= ittee. >>> On 08/24/2014 07:39 PM, Howard Hinnant wrote: >>>> If we are dealing with a platform/HashAlgorithm disagreement in endian= , then an alternative hash_append can be used for scalars: >>>=20 >>> So, the endianness is a boolean, not a three-way type? Either you're "= native" or not >>> seems all that matters, from the code you presented. >>=20 >> As currently coded, a hashing algorithm would set a member static const = enum to one of three values: >>=20 >> static constexpr xstd::endian endian =3D xstd::endian::native; >> static constexpr xstd::endian endian =3D xstd::endian::big; >> static constexpr xstd::endian endian =3D xstd::endian::little; >>=20 >> The meaning of these is to ask the hash_append overload for scalars infl= uenced by endian (larger than char) to change the endian from native, to th= e requested endian, prior to sending the bytes into the hashing algorithm. = Concretely, in the order shown above: >>=20 >> 1. Map native endian to native endian (presumably this is always a no-o= p). >> 2. Map native endian to big endian. This will be a no-op on big endian= machines. >> 3. Map native endian to little endian. This will be a no-op on little = endian machines. >=20 >> Non-fingerprinting hash applications will probably always use the native= mapping (i.e. they don't care about endian). >=20 > Yes. >=20 > It seems to me that these choices are, strictly speaking, not a property = of the > (crypto) hash algorithm (that is only concerned with octets coming in), but the algorithm will see bytes, > but with > the preferences / situation in which it is used. As someone else pointed= out, > we're essentially defining an ephemeral serialization format for purposes= of > computing the hash. >=20 > I'd like to ask: >=20 > - that (core) hash algorithm implementations such as SHA256 do not > specify the "endian" thing (it doesn't mean anything at this level) and do you mean aspect 1 (input), or aspect 2 (output), or both? >=20 > - that there is a config option to do scalar endian conversions if so des= ired. >=20 > Example: >=20 > std::uhash // unportable for scalars > char > std::uhash // convert scalars > char to= "big endian" prior to feeding octets to hash algorithm This part sounds exactly what I'm proposing, except that the specification = is applied to std::sha256 (and all hashing algorithms in general), instead = of to std::uhash (and all hash functors in general). The hash functor is the wrong place to specify endian requests because the = hash functor should be as simple as possible. It is only responsible for: 1. Initializing the hash algorithm. 2. Updating the hash algorithm with a single value. 3. Finalizing the hash algorithm. template result_type operator()(T const& t) const noexcept { Hasher h; hash_append(h, t); return static_cast(h); } With as-simple-as-possible hash functor requirements, one maximizes the abi= lity of the programmer to create a custom hash functor to do things such as= seeding and/or salting. On the other hand, hash_append is the perfect place to respond to such a re= quest as hash_append will know what type to be hashed it is dealing with (w= hich may or may not have endian concerns), and what type of hash algorithm = it is dealing with. If the hash algorithm specifies the desired endian inp= ut, this is very easily taken care of. For example: template hash_append(HashAlgorithm& h, char c) noexcept { h(&c, 1); // never any endian concerns } On the other hand, for scalars > 1: template hash_append(HashAlgorithm& h, int i) noexcept { if (HashAlgorithm::endian !=3D endian::native) i =3D convert_native_to(i, HashAlgorithm::endian) h(&i, sizeof(i)); } The above does not have to be the literal implementation. I would prefer c= ompile-time branching instead of run-time branching on the compile-time que= stion of endian. But I'm just trying to simplify the presentation. And no= te that for platforms where sizeof(int) =3D=3D sizeof(char) (and all bits a= re part of the representation), the std::lib implementation simplifies down= to: template hash_append(HashAlgorithm& h, char c) noexcept { h(&c, 1); // never any endian concerns } template hash_append(HashAlgorithm& h, int i) noexcept { h(&i, 1); // never any endian concerns } I.e. the implementation of the std::lib isn't portable. But that's ok. Th= e std::lib implementors write non-portable code so that we don't have to. If all bits *are not* part of the representation, then the std::lib impleme= ntation must mask off or zero the padding bits prior to sending a message t= o the hash algorithm. >=20 > This also supports strange VAX-endianess as the native endian > convention, I believe. Agreed. >=20 >>> The other aspect is the fact that hash algorithms such as sha256 like >>> to process e.g. 32-bits (=3D 4 octets) at once. When reading four >>> octets from memory, it's helpful to be able to simply read them >>> into a register on "suitable" platforms and only do the endianess >>> (or other) conversion on the remainder of the platforms. But, on >>> the abstract level, this is not a configuration option, it's a >>> question of correctness. >=20 >> Agreed. I see the second aspect above is an implementation detail of th= e hashing algorithm. This detail does not impact the hashing algorithm's i= nterface, except as to impact its results. I see no motivation to "leak" t= his implementation detail into a standard specification, unless the standar= d is to specify concrete hashing algorithms. In that event we could choose= any number of options, of which I really have little opinion. For example= : Sha256_output_little_endian as one hashing algorithm and Sha256_output_b= ig_endian as another. Or perhaps Sha256 is another solution. =20 >=20 > Well, there is a lost optimization opportunity if you're hashing an > array of unsigned int (32 bits) on a platform and with an endianess > choice that is just "right". Otherwise, you get two endianess conversion= s > back-to-back: One for the scalar > char thing from above, and one when > sha256 tries to form its internal 32-bit chunks. This is precisely the optimization that my hash_proposal has gone to great = lengths to preserve. And also for std::string, std::vector, std::arra= y, std::pair, std::vector>, std::vector<= std::tuple>, etc, etc. >>> The simple name must result in the portable hash value. >=20 > Let me retract that; see details above. >=20 >> My understanding from http://en.wikipedia.org/wiki/Sha256 is that SHA256= output endian is always big. >=20 > The output is a sequence of octets. It might be that this sequence is in= terpreted in > big endian style for (some) display purposes, but that's a minor detail. If by "display purposes" you also mean transmission across a network, I agr= ee, though for me it is a major detail. Howard --=20 ---=20 You received this message because you are subscribed to the Google Groups "= ISO C++ Standard - Future Proposals" group. To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa= ls/. .