220 12569 <53FF9444.4080702@gmail.com> article Path: news.gmane.org!not-for-mail From: Miro Knejp 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:42:44 +0200 Lines: 286 Approved: news@gmane.org Message-ID: <53FF9444.4080702@gmail.com> References: <53F8F620.3090701@gmx.de> <53F989E9.5090701@gmx.net> <53FE5E8A.2090003@gmx.net> <53FE7CFB.1090509@gmail.com> <53FF3BC0.5080802@gmx.net> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1409258583 16907 80.91.229.3 (28 Aug 2014 20:43:03 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 28 Aug 2014 20:43:03 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBC6ONSXJ54LBBTFI72PQKGQERJ4PNHQ@isocpp.org Thu Aug 28 22:42:55 2014 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-wg0-f72.google.com ([74.125.82.72]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1XN6Wz-0006b1-Jy for gclcip-std-proposals@m.gmane.org; Thu, 28 Aug 2014 22:42:53 +0200 Original-Received: by mail-wg0-f72.google.com with SMTP id b13sf1362687wgh.11 for ; Thu, 28 Aug 2014 13:42:53 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:message-id:date:from:user-agent:mime-version:to :subject:references:in-reply-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=GUia7PCgBunCV8a09exeEuR4feOn57UV6j/+HZbewxY=; b=jPxJiwxBMrVvw5ukQ43hSn/I/FrC9B+jTdUSgN3/gI0vYuNGEVQJIHvHzo8CMh7q/y V8ACtQa6MBQIIoQQKPen/iCvGut4fz0ZAfeAa1W7FToQjcriayg8wDeVAuj7PJHJlFpg PQNxe/2VbMhI90MOgCMvrQyY3Tn8FQDQAz6o0bqjBSW/sElJEaAVcPs5Jm6E+U1Y+4bu bzlfe5uAhx6JUrpmzKeQMLf0j3/rOBRp5q2zYiLVtyq4IdOjBtIX7Qni5Na65ixJJ3MH xsrX8R/AbRA0Xy+ryos1hleQOWiOTSnMydIcSc/sYlllOvumW9Ke6OMq5Oz9aVGCfYyG u5n X-Gm-Message-State: ALoCoQnafIzcSFujroYYNMYMWpoxcY06XHBcuL8jndNwoE15sRtwM4tpWFObKab4i3zvpoZLyU+L X-Received: by 10.180.99.74 with SMTP id eo10mr714958wib.2.1409258573220; Thu, 28 Aug 2014 13:42:53 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.180.109.233 with SMTP id hv9ls381580wib.49.canary; Thu, 28 Aug 2014 13:42:52 -0700 (PDT) X-Received: by 10.180.187.20 with SMTP id fo20mr40805318wic.58.1409258572001; Thu, 28 Aug 2014 13:42:52 -0700 (PDT) Original-Received: from mail-we0-x229.google.com (mail-we0-x229.google.com [2a00:1450:400c:c03::229]) by mx.google.com with ESMTPS id up9si9201848wjc.126.2014.08.28.13.42.51 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Thu, 28 Aug 2014 13:42:51 -0700 (PDT) Received-SPF: pass (google.com: domain of miro.knejp@gmail.com designates 2a00:1450:400c:c03::229 as permitted sender) client-ip=2a00:1450:400c:c03::229; Original-Received: by mail-we0-f169.google.com with SMTP id k48so1299994wev.14 for ; Thu, 28 Aug 2014 13:42:51 -0700 (PDT) X-Received: by 10.180.87.161 with SMTP id az1mr29537398wib.13.1409258571640; Thu, 28 Aug 2014 13:42:51 -0700 (PDT) Original-Received: from [192.168.42.33] (ppp-93-104-171-113.dynamic.mnet-online.de. [93.104.171.113]) by mx.google.com with ESMTPSA id pn5sm12823195wjc.4.2014.08.28.13.42.50 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 28 Aug 2014 13:42:50 -0700 (PDT) User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:31.0) Gecko/20100101 Thunderbird/31.0 In-Reply-To: <53FF3BC0.5080802@gmx.net> X-Original-Sender: miro.knejp@gmail.com X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of miro.knejp@gmail.com designates 2a00:1450:400c:c03::229 as permitted sender) smtp.mail=miro.knejp@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:12569 Archived-At: Am 28.08.2014 um 16:25 schrieb Jens Maurer: > On 08/28/2014 02:51 AM, Miro Knejp wrote: >> Maybe this whole issue simply shows that algorithms with strict size >> requirements should not be defined in terms of char, short, int but >> int8_t, int16_t, and so on. If hash_append has (by default) only >> overloads for exactly sized types then the compiler should pick the >> correct one when the user feeds it unsized types like int. On machines >> where no int8_t exists no hash_append overload for int8_t exists. > If we go that route, we should use "uint8_t" etc, not the signed variants= , > which have more platform freedom. Possibly > > And, for a hash algorithm that operates on octets, what does it mean > to hash a uint16_t value, call it x? I think the definition should be > > hash the two octets obtained by x & 0xff and (x>>8) & 0xff, > in sequence > > but that should be stated explicitly, and also how the user can get > that result if he chooses to directly call the hash algorithm. I'd say it's the job of hash_append() provided by the implementation for=20 the native bultin types to take care of this. If the Hasher has endian=20 requirements, x gets swapped as necessary and its contiguous (value=20 representing)*octets* fed to the Hasher in order of least to most=20 significant (or reversed). Every introductory course to programming I=20 have ever witnessed talks in lengths about bytes and how they make up=20 ints and what endianess is and so forth. I consider this basic=20 knowledge. The standardese has to describe this in detail of course (as=20 far as it can considering the C++ abstract machine), but I think for the=20 sake of this discussion what happens is clear. The real challenge I=20 think is figuring out how to define it portably for machines not=20 operating on multiples of 8 bit (if this is deemed relevant). >> Where the same source code is to produce equal hashes for the same data >> structures on different machines then the only portable way is to use >> the explicitly sized types. That is honestly the *only* way to be sure >> of consistent hash values and should maybe be added as a note somewhere. > I don't think so. If you strictly think about portably serializing > values to octets, the types on the platforms (other than the > integer/floating-point distinction) becomes meaningless, and you should > only think about how to represent values in a portable manner, using > (for example) a value-dependent variable-length integer representation. > > (I'm not saying this is the only choice, but we shouldn't claim > hash algorithms such as sha256 if the results aren't really portable.) Then I wonder who you want to put the burden on: the implementation or=20 the user? I do do think portability is possible (certainly for machines=20 with 8*n bits) by only providing hash_append for selected native bultin=20 (maybe only unsigned) types which are either equivalent on all=20 architectures supporting them; or don't exist at all. At least if you=20 are on an architecture without these typedefs the compiler will kindly=20 remind you that your data structure is incompatible, instead of=20 producing funny hashes. >> Though I think "char" (not "signed char" or "unsigned char" as those are >> 3 different types) should be treated implementation-defined as the >> standard uses this type only for character values in strings. > This is not exactly true. Standard filestreams use these for (possibly) > binary data, too. (Unfortunately, in my opinion.) Well sadly we have the sized typedefs officially only since 11... >> hash_append(Hasher&, array_view) // enable if hash_append(Hasher, T) >> is well-formed >> hash_append(Hasher&, basic_string_view) // enable if >> hash_append(Hasher, Char) is well-formed > Yes, this is basic decomposition. We should have something like that. > (I'd be happy to omit the enable_if dance; you'll simply get an error > if T doesn't have a hash_append(), which is good.) Whether it's an enable_if dance or predefined overloads doesn't really=20 matter as long as it does the job. This was more of an exposition. > Question: Do you hash the length of the string or array separately, or > just the elements? In the latter case, hashing two empty strings > is indistinguishable from hashing three empty strings. This seems > undesirable for crypto-hashes. This is an issue that was discussed previously and I don't know if there=20 was a consensus. It's nested containers where it becomes headache-inducing. >> Having is_contiguously_hashable predefined as true for the >> types [u]int[8|16|32|64]_t, char, wchar_t and char[16|32]_t allows the >> implementation to select which integral types are acceptable and can >> then internally provide specializations with tag dispatching. Using >> unsized types like short or int would pick the proper overload depending >> on what int##_t typedefs alias to. > So would std::hash_append() overloads that each take one of the > scalar types mentioned above. (The standard library can avoid > duplicate overloads for the uintX_t typedefs conflicting with char etc.) is_contiguously_hashable for the scalar types was just a tool for the=20 enable_if exposition (which may or may not be used). The implementation=20 should know how to turn these types into octet streams. > I don't see why we need an is_contiguously_hashable trait. As far as I understad it's primarily for optimization and boilerplate=20 reduction. If all bytes of my struct contribute to its value=20 representation without any padding, and endianess doesn't apply, I can=20 shove the entire struct (or array thereof) in the hungry maw of (void*,=20 size_t), and as has been mentioned earlier there are CPUs with hash/CRC=20 instructions so there is optimization potential present. This is usually=20 true for scalar types. For compound types it is upon the author of the=20 type to decide if this is true or not. This is obviouly not a good=20 solution if the hash has to be communicated to the outside world where=20 endianess may matter. The introduction of hash_append_contiguous() may=20 make this trait obsolete. There's only the question left whether=20 defining a class partial specialization or a forwarding function=20 overload is less effort and less prone to error by the user. But I think=20 the trait approach makes it easier to apply the information=20 transitively. Plus you get a query for static_assert to check whether=20 your assumptions about the types of member variables hold: // All three types have no padding, only value bytes, endianess doesn't=20 matter. // Ensured with type_traits and whatnot. struct A { ... }; struct B { ... }; struct C { A a; B b; int i; }; // Overload solution 1 void hash_append(Hasher& h, const A& x) { ... } void hash_append(Hasher& h, const B& x) { ... } void hash_append(Hasher& h, const C& x) { // Compiler may not figure out the entire struct can go in one big=20 gulp, // making the optimization unlikely. hash_append(h, x.a); hash_append(h, x.b); hash_append(h, x.i); } // Overload solution 2 void hash_append(Hasher& h, const C& x) { // There is no way to ensure this is actually correct // because we cannot check it for A and B hash_append_contiguous(addressof(x), sizeof(x)); } // Traits solution struct is_contiguously_hashable : true_type { }; struct is_contiguously_hashable : true_type { }; struct is_contiguously_hashable : true_type { // Sprinkle code with magic static_assert dust to ensure // our assumptions about A and B are true. // (especially if their traits are defined in some other place) }; > >> A further alternative would be to provide a third parameter in the form >> hash_append(Hasher&, const T&, valid_bits), so even on architectures >> without direct int8_t support one could use ints for storage and only >> mask the leading N bits as relevant for the hash. > For scalar T, this should be the job of the standard library implementati= on. > I don't see a need for valid_bits with a generic "T". That said, I'm > not opposed to adding > > hash_append(Hasher&, const std::bitset&); > > where N is divisible by 8. This allows to pass an octet without > concerns about C++ built-in types at all. Good point about bitset. About my motivation: consider you have to use=20 uint32_t for your data type because the machine has no uint8_t but only=20 the lower 8 bit of the integer are to be hashed (the integer is=20 abstracted in a way as to behave like an 8 bit value), the upper 24 bits=20 must be discarded (not masked) in order to produce identical signatures=20 as on some remote machine that has direct 8 bit support. This=20 information cannot be provided using only the builtin scalar types.=20 bitset is a nice solution to this. > >> This should make any need for a hash_append(void*, size_t) overload >> obsolete. The Hasher itself needs a (void* p, size_t n) overload where n >> denotes the number of valid OCTETS pointed to by p. > Then it's hard to call that function in portable code, because > sizeof(int) =3D 1 on some platforms where "int" is 32 bits (and "char", t= oo). I didn't specify n in terms of sizeof() but *octets*. The hasher has to=20 know how to extract the octets from the pointed to contiguous octet=20 stream. Forget sizeof(char), this is very carefully defined as the=20 number of octets pointed to by the pointer. If sizeof(int) =3D=3D=20 sizeof(char) =3D=3D 1, int has 32 bits, and all bits shall be hashed, then= =20 it still holds that n =3D=3D 4. >> hash_append() has >> then already taken care of endianess and other details by applying >> Hasher's traits. The nice hing here is that if a type has no padding and >> the user *decided that endianess, etc. does not matter* then enabling >> is_contiguously_hashable makes hash_append() feed the entire structure >> to (void*, size_t). > I believe it's a user-level policy decision for his struct type T to > determine whether it can be hashed contiguously, possibly depending > on the hasher (think two hash tables keyed off on different things, > both pointing to T objects). And that policy decision is best left > to the user's overload of hash_append(T). The "user-level policy" you refer to is presented by Howard as=20 is_contiguously_hashable. But regardless of any traits one has always=20 the liberty of overloading hash_append() for cases like this or call=20 hash_append for the relevant members manually for a case like you=20 describe. I see is_contiguously_hashable primarily as a hint for=20 optimization (and reduction of boilerplate , and compile time checking=20 with static_assert). > > Jens > Am 28.08.2014 um 20:00 schrieb Howard Hinnant: > On Aug 27, 2014, at 8:51 PM, Miro Knejp wrote: > >> Regarding the void* question, I think Howard's is_contiguously_hashable = covers this nicely. If your type has no padding in it, specialize the trait= .. If it does, provide your own hash_append overload and feed it the require= d members. I think a good set of predefined overloads for hash_append would= be >> >> hash_append(Hasher&, const T&) // enable if is_contiguously_hashable is true >> hash_append(Hasher&, array_view) // enable if hash_append(Hasher, T) = is well-formed >> hash_append(Hasher&, basic_string_view) // enable if hash_= append(Hasher, Char) is well-formed >> >> Having is_contiguously_hashable predefined as true for the ty= pes [u]int[8|16|32|64]_t, char, wchar_t and char[16|32]_t allows the implem= entation to select which integral types are acceptable and can then interna= lly provide specializations with tag dispatching. Using unsized types like = short or int would pick the proper overload depending on what int##_t typed= efs alias to. >> >> A further alternative would be to provide a third parameter in the form = hash_append(Hasher&, const T&, valid_bits), so even on architectures wit= hout direct int8_t support one could use ints for storage and only mask the= leading N bits as relevant for the hash. >> >> This should make any need for a hash_append(void*, size_t) overload obso= lete. The Hasher itself needs a (void* p, size_t n) overload where n denote= s the number of valid OCTETS pointed to by p. hash_append() has then alread= y taken care of endianess and other details by applying Hasher's traits. Th= e nice hing here is that if a type has no padding and the user *decided tha= t endianess, etc. does not matter* then enabling is_contiguously_hashable m= akes hash_append() feed the entire structure to (void*, size_t). Appropriat= e warning signs should be positioned around is_contiguously_hashable to mak= e the user aware of its positive and negative implications. > The implementation should provide: > > hash_apppend(Hasher&, const T&) > > for all arithmetic T, T*, and probably enums and nullptr_t as well. Addi= tionally the spec should provide hash_append for containers, pair, tuple, e= tc. Anything that we today have a std::hash for, we should definitely h= ave a std::hash_append for. And more. > > (...) > > As soon as we start saying something like: "hash_append only exists for = a small set of types", then we have completely changed the entire design, a= nd completely missed the point of it. > > hash_append is not about programmers stuffing bytes into a hash algorithm= (that's the std::lib's job). hash_append is about building a system where= by programmers can write their hashing support just once, for all hashing a= lgorithms, and with absolutely no need for a hash_combine step. I agree, and I was merely talking about the atomic building blocks (the=20 std::lib job of stuffing bytes) which depend on the=20 implementation/machine, Hasher endianess and whatnot. If the arithmetic=20 Ts (and underlying values for enums) are exposed in the interface using=20 explicitly sized integer types. There should of course be further=20 overloads for the compound std types, containers, and stuff. > hash_append should be as ubiquitous as swap, and operator=3D=3D. > > Howard > Miro --=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/. .