{"thread":{"id":"52507","subject":"NewHash alternatives and SHA benchmarks","startedAt":"2019-12-22T06:48:58Z","lastAt":"2019-12-23T15:15:54Z","messageCount":4,"participants":["Michael Clark","brian m. carlson","Philip Oakley"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"388785","messageId":"20191222064133.35276-1-michaeljclark@mac.com","threadId":"52507","inReplyTo":null,"subject":"NewHash alternatives and SHA benchmarks","fromName":"Michael Clark","fromEmail":"michaeljclark@mac.com","sentAt":"2019-12-22T06:41:33Z","receivedAt":"2019-12-22T06:48:58Z","isPatch":false,"sender":{"key":"michaeljclark@mac.com","avatar":"https://gravatar.com/avatar/0401ef79f84c31ebb15fbd8a308f5eb0b1aac2cc8fd71cc5207a0e236acbdc53?d=mp&s=160"},"body":"Hi Folks,\n\nI have become interested in git's NewHash migration and have been\ninvestigating alternate hash algorithm support in git. It seems\nthat implementation of NewHash is still a way off, and it is still\npossible to revise the choice of SHA256 for a better alternative.\n\nMany of you may already be aware of Hash content Length extension\nattacks [1]. While I am not aware of any git vulnerabilities based\non length extension; it seems to me that choosing a hash algorithm\nthat is not vulnerable to this attack could prevent a future exploit\nbased on some future protocol or other bug. git hashes should be final\nin its usage, so length extension resistance is a good property.\n\nSHA3 is not vulnerable to content length extension because it uses a\nsponge construction internally, meaning state is diffused away, and\nthe state cannot be reconstructed from a hash value. Truncated SHA2\nhashes such as SHA224 and SHA512/256 are also not vulnerable to\nlength extension, however, SHA224 only reduces the probability\nof extension by 1/2^32 which, while not trivial, is a small reduction.\n\nSHA512/256 or SHA3-256 seems to me to be most attractive for safety\nagainst content length extension.\n\nWith this in mind, I decided to investigate performance properties of\nthe alternative SHA hash algorithms. Of particular interest to me is\nSHA3-256 and SHA512/256 (SHA512 truncated to 256-bits) as they are both\nthe same size as SHA256 thus are good NewHash contenders.\n\nI was quite surprised by the benchmark results with SHA512/256 1.5X\nfaster than SHA256. SHA512/256 seems a very good alternative to SHA256:\n\n- SHA256 8 x 32-bit state (256-bits) and 64-byte block, 64 rounds\n- SHA512 8 x 64-bit state (512-bits) and 128-byte block, 80 rounds\n\nSHA512/256 has understandable good performance on 64-bits systems due\nto having only slightly more iterations (80 instead of 64) while\nprocessing 128 bytes per block instead of 64. In practice, this means\nSHA512/256 is about 1.5X faster than SHA256 on 64-bit systems.\n\nSHA3, while competitive, is still significantly slower than SHA512.\nThe AVX512 version of SHA3 is actually faster than SHA256. SHA256 is\nnot the best performing NewHash alternative by a long shot.\n\nSHA Benchmarks on Intel Core i7-7980XE @ 4.6GHz\n===============================================\n\n(MiB/sec)\\      ext      16     128    1024    4096   65536 1048576\n     -----    -----   -----   -----   -----   -----   -----   -----\n      sha1     avx2    37.5   239.6   817.0  1097.5  1231.2  1244.8\n    sha224     avx2    30.8   170.5   439.3   524.3   560.2   564.4\n    sha256     avx2    31.2   171.2   438.7   525.0   560.9   564.8\n    sha512     avx2    27.1   167.2   561.5   747.1   835.7   842.8\nsha512-224     avx2    26.8   164.7   558.8   747.9   836.5   845.1\nsha512-256     avx2    26.6   163.9   557.9   751.4   835.0   843.0\n  sha3-224     avx2    38.9   313.8   411.5   474.6   491.1   490.7\n  sha3-256     avx2    39.7   317.3   414.5   445.3   464.9   464.3\n  sha3-384     avx2    39.8   184.6   338.1   348.4   356.5   358.0\n  sha3-512     avx2    40.0   185.0   228.4   245.9   248.0   249.0\n\n(MiB/sec)\\      ext      16     128    1024    4096   65536 1048576\n     -----    -----   -----   -----   -----   -----   -----   -----\n  sha3-224   avx512    24.3   192.6   506.5   674.3   736.8   740.9\n  sha3-256   avx512    25.0   198.4   511.5   635.4   698.8   698.8\n  sha3-384   avx512    24.8   152.3   429.6   503.9   535.7   540.2\n  sha3-512   avx512    24.8   152.4   307.3   361.2   375.6   374.4\n\nRecommendations\n===============\n\nAfter performing multiple benchmarks and thinking about this for\nseveral weeks I have come to the conclusion that SHA512/256 is a\nvery good alternative to SHA256, both from the perspective of its\nlength extension resistance, and performance. It seems that NewHash\nimplementation is some way off so it is not too late to change.\n\n- Consider SHA512/256 for NewHash\n\nSHA algorithm patches\n=====================\n\nI will be sending a patch series which adds SHA Algorithms which\nare in the sha-algorithms branch of my git tree.\n\n- https://github.com/michaeljclark/git.git\n- https://github.com/michaeljclark/git/tree/sha-algorithms/sha\n\nThis is a precursor to asking some questions about the proposed\nimplementation of multiple or compat hashs (N-hash or 2-hash?).\nI am curious about the pack format and directory structure for\nloose objects. It seems there needs to be a single hash chosen\nfor loose object filenames, and auxilliary hashes will need\nhash to hash map to go from a compat hash to new hash.\n\nI have been reading the code, and it seems like it is going to be\na challenge to change to support more than one hash concurrently.\nMy observation is the content addressable storage layer could do\nwith being a little more abstract, as there seems to be a lot of\ncode that seperately computes hashes by accessing the hash algorithms\ndirectly versus going through an abstract content-addressable storage\nlayer, like the VFS in Linux.\n\nIn any case, I hope you find this benchmark data useful.\n\nRegards,\n\nMichael\n\n[1] https://en.wikipedia.org/wiki/Length_extension_attack\n"},{"id":"388800","messageId":"20191223011306.GF163225@camp.crustytoothpaste.net","threadId":"52507","inReplyTo":"20191222064133.35276-1-michaeljclark@mac.com","subject":"Re: NewHash alternatives and SHA benchmarks","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2019-12-23T01:13:06Z","receivedAt":"2019-12-23T01:13:14Z","isPatch":false,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On 2019-12-22 at 06:41:33, Michael Clark wrote:\n> Recommendations\n> ===============\n> \n> After performing multiple benchmarks and thinking about this for\n> several weeks I have come to the conclusion that SHA512/256 is a\n> very good alternative to SHA256, both from the perspective of its\n> length extension resistance, and performance. It seems that NewHash\n> implementation is some way off so it is not too late to change.\n> \n> - Consider SHA512/256 for NewHash\n\nThis has been discussed extensively on the list.  Git is not in general\nvulnerable to length extension attacks because it hashes the length of\nthe object as part of the object header.  This was documented as one of\nthe known aspects in the transition plan in\nDocumentation/technical/hash-function-transition.txt.\n\nWe've considered a lot of hash algorithms, including BLAKE2b-256,\nSHA-256, SHA-512/256, SHA-3-256, SHAKE256 with a 256-bit length, and\nothers.  This was no doubt controversial, but we discussed the pros and\ncons of many options and this is what we decided.  I will state that\nwhile our choice was not one of my more preferred options, I value that\nwe have a consensus on the way forward.\n\nAmong the reasons we chose SHA-256 is performance on newer x86-64\nprocessors with the SHA extensions, which support only SHA-1 and\nSHA-256, and compatibility with a wide variety of cryptographic\nlibraries.  I have no desire for Git to provide assembly implementations\nof NewHash, and that means people must rely on existing cryptographic\nlibraries.\n\nCryptographic libraries overwhelmingly do not support SHA-512/256.\nWhile OpenSSL does, it's only in the latest versions, and people\ngenerally cannot legally distribute both Git and OpenSSL linked\ntogether, so they must rely on system libraries for good performance.\nApple Common Crypto, for example, does not document any SHA-512/256\nimplementations.\n\nThere is also a benefit to chaining using a single algorithm for\nsignatures, which therefore necessitates using SHA-256 or one of the\nother original SHA-2 algorithms until the next version of OpenPGP is\nimplemented which supports SHA-3.\n\nBecause we decided some time ago, I've sent in a bunch of patches to our\ntestsuite to make it work with SHA-256.  Some of these patches are\ngeneral, in that they make the tests generate values which are used, or\nthey are specific to the length of the hash algorithm.  Others use\nspecific hash values, and changing the hash algorithm will require\nrecomputing all of these values.\n\nAbsent a compelling security reason to abandon SHA-256, such as a\nsignificant previously unknown cryptographic weakness, I don't plan to\nreimplement all of this work.  Updating our testsuite to work\nsuccessfully with SHA-256 has taken a huge amount of time, and this work\nhas been entirely done on my own free time because I want the Git\nproject to be successful.  That doesn't even include the contributions\nof others who have reviewed, discussed, and contributed to the current\nwork and transition plan.  While I appreciate the benefits of\nalternatives to SHA-256, I'm a bit annoyed that you're proposing to\nthrow away all of this work after we explicitly sought to build\nconsensus about an algorithm so that this stage of the work could begin.\n\nOf course, nothing prevents you from proposing a new algorithm and\nfixing the testsuite to make it work, but I don't believe that we're\nlikely to adopt a different algorithm at this point, given the previous\ndiscussion on the list.  The code is designed to be pluggable to support\narbitrary algorithms, but there are pieces which assume that the\nalgorithm can be distinguished by length (e.g., the dumb HTTP protocol)\nand therefore you'd need to devise a different way to distinguish these\nversions.\n\nIf you'd like to see what a Git binary that supports multiple hash\nalgorithms looks like at the moment, you're welcome to look at my\ntransition-stage-4 branch at https://github.com/bk2204/git.git so you\ncan get a fuller understanding of what's involved.  You can run the\ntestsuite with that code and GIT_TEST_DEFAULT_HASH=<hashname> to see\nwhat passes and fails.\n\n> SHA algorithm patches\n> =====================\n> \n> I will be sending a patch series which adds SHA Algorithms which\n> are in the sha-algorithms branch of my git tree.\n> \n> - https://github.com/michaeljclark/git.git\n> - https://github.com/michaeljclark/git/tree/sha-algorithms/sha\n> \n> This is a precursor to asking some questions about the proposed\n> implementation of multiple or compat hashs (N-hash or 2-hash?).\n> I am curious about the pack format and directory structure for\n> loose objects. It seems there needs to be a single hash chosen\n> for loose object filenames, and auxilliary hashes will need\n> hash to hash map to go from a compat hash to new hash.\n\nThat's correct.  There's documentation in the transition plan about what\nthis will look like.\n\nA stage 4 implementation (where repositories are either SHA-1 only or\nSHA-256 only) has been written and I'll send it out once the remaining\ntest fixes are merged.\n\nI should point out that we specifically chose not to support a plethora\nof algorithms because the goal is to encourage everybody to adopt a\nsingle, secure algorithm.  The network protocol will need to\ninteroperate using a single algorithm, which means the repository will\nneed to contain a mapping for that algorithm.  Since the current plan is\nto support no more than two algorithms at a time, one of which will need\nto be SHA-1, allowing users to pick and choose from a variety of\nalgorithms harms interoperability.  Seamless interoperability between\nSHA-1 and NewHash repositories was considered extremely important in the\ntransition plan.  That won't be coming immediately with the stage 4\nimplementation, but it is planned for the future.\n\nMy hope is that whatever we pick now will be secure for some time to\ncome and that when we need to adopt a newer hash, whether due to\ncryptographic advance or post-quantum cryptography, there will be no\nexisting SHA-1 repositories and transition can take place from NewHash\nto NewNewHash.\n-- \nbrian m. carlson: Houston, Texas, US\nOpenPGP: https://keybase.io/bk2204\n"},{"id":"388802","messageId":"9279D11D-2BC2-4800-8282-C2219F152269@mac.com","threadId":"52507","inReplyTo":"20191223011306.GF163225@camp.crustytoothpaste.net","subject":"Re: NewHash alternatives and SHA benchmarks","fromName":"Michael Clark","fromEmail":"michaeljclark@mac.com","sentAt":"2019-12-23T01:59:05Z","receivedAt":"2019-12-23T01:59:11Z","isPatch":false,"sender":{"key":"michaeljclark@mac.com","avatar":"https://gravatar.com/avatar/0401ef79f84c31ebb15fbd8a308f5eb0b1aac2cc8fd71cc5207a0e236acbdc53?d=mp&s=160"},"body":"\n\n> On 23/12/2019, at 2:13 PM, brian m. carlson <sandals@crustytoothpaste.net> wrote:\n> \n> On 2019-12-22 at 06:41:33, Michael Clark wrote:\n>> Recommendations\n>> ===============\n>> \n>> After performing multiple benchmarks and thinking about this for\n>> several weeks I have come to the conclusion that SHA512/256 is a\n>> very good alternative to SHA256, both from the perspective of its\n>> length extension resistance, and performance. It seems that NewHash\n>> implementation is some way off so it is not too late to change.\n>> \n>> - Consider SHA512/256 for NewHash\n> \n> This has been discussed extensively on the list.  Git is not in general\n> vulnerable to length extension attacks because it hashes the length of\n> the object as part of the object header.  This was documented as one of\n> the known aspects in the transition plan in\n> Documentation/technical/hash-function-transition.txt.\n> \n> We've considered a lot of hash algorithms, including BLAKE2b-256,\n> SHA-256, SHA-512/256, SHA-3-256, SHAKE256 with a 256-bit length, and\n> others.  This was no doubt controversial, but we discussed the pros and\n> cons of many options and this is what we decided.  I will state that\n> while our choice was not one of my more preferred options, I value that\n> we have a consensus on the way forward.\n> \n> Among the reasons we chose SHA-256 is performance on newer x86-64\n> processors with the SHA extensions, which support only SHA-1 and\n> SHA-256, and compatibility with a wide variety of cryptographic\n> libraries.  I have no desire for Git to provide assembly implementations\n> of NewHash, and that means people must rely on existing cryptographic\n> libraries.\n\nthe SHA extensions that are not generally available, which include SHA1 on the cusp of its deprecation. It seems silly not to support SHA512 when implementing SHA2 support especially considering it’s faster on 64-bit.\n\nIt’s used in PBKDF2-SHA512 for iterated password hashes. SHA512/256 is just a different IV.\n\nDon’t be discouraged by my comments. Thanks for taking the time to describe the state. The rationale of pragmatism should be in the hash migration plan.\n\nSHA256 will always take more energy than SHA512 which actually means is possibly slightly weaker, which could be used as a rationale for choosing SHA256. I don’t think the other rationale is acceptable though because the choice of purity of choice should lead what goes into hardware.\n\nI want pure hashes of the unpacked object so I will have to think about how I do that. Possibly SHA-3 too. git doesn’t really support large files that well either so I’ll have to keep that in mind... If the algorithm is not vulnerable to length extensions, then the length prefix is not required. Anyhow...\n\nI’ll have to hack up some shell scripts or something in the meantime.\n\n> Cryptographic libraries overwhelmingly do not support SHA-512/256.\n> While OpenSSL does, it's only in the latest versions, and people\n> generally cannot legally distribute both Git and OpenSSL linked\n> together, so they must rely on system libraries for good performance.\n> Apple Common Crypto, for example, does not document any SHA-512/256\n> implementations.\n> \n> There is also a benefit to chaining using a single algorithm for\n> signatures, which therefore necessitates using SHA-256 or one of the\n> other original SHA-2 algorithms until the next version of OpenPGP is\n> implemented which supports SHA-3.\n> \n> Because we decided some time ago, I've sent in a bunch of patches to our\n> testsuite to make it work with SHA-256.  Some of these patches are\n> general, in that they make the tests generate values which are used, or\n> they are specific to the length of the hash algorithm.  Others use\n> specific hash values, and changing the hash algorithm will require\n> recomputing all of these values.\n> \n> Absent a compelling security reason to abandon SHA-256, such as a\n> significant previously unknown cryptographic weakness, I don't plan to\n> reimplement all of this work.  Updating our testsuite to work\n> successfully with SHA-256 has taken a huge amount of time, and this work\n> has been entirely done on my own free time because I want the Git\n> project to be successful.  That doesn't even include the contributions\n> of others who have reviewed, discussed, and contributed to the current\n> work and transition plan.  While I appreciate the benefits of\n> alternatives to SHA-256, I'm a bit annoyed that you're proposing to\n> throw away all of this work after we explicitly sought to build\n> consensus about an algorithm so that this stage of the work could begin.\n> \n> Of course, nothing prevents you from proposing a new algorithm and\n> fixing the testsuite to make it work, but I don't believe that we're\n> likely to adopt a different algorithm at this point, given the previous\n> discussion on the list.  The code is designed to be pluggable to support\n> arbitrary algorithms, but there are pieces which assume that the\n> algorithm can be distinguished by length (e.g., the dumb HTTP protocol)\n> and therefore you'd need to devise a different way to distinguish these\n> versions.\n> \n> If you'd like to see what a Git binary that supports multiple hash\n> algorithms looks like at the moment, you're welcome to look at my\n> transition-stage-4 branch at https://github.com/bk2204/git.git so you\n> can get a fuller understanding of what's involved.  You can run the\n> testsuite with that code and GIT_TEST_DEFAULT_HASH=<hashname> to see\n> what passes and fails.\n\nThanks. I’ll check it out and try it.\n\nMy comments aren’t directed at you. I’m interested in your work. Keep it up. Well, take a break. idk. Whatever. I’ll probably be spending my holidays reading git code, or maybe libgit2 :-p\n\n>> SHA algorithm patches\n>> =====================\n>> \n>> I will be sending a patch series which adds SHA Algorithms which\n>> are in the sha-algorithms branch of my git tree.\n>> \n>> - https://github.com/michaeljclark/git.git\n>> - https://github.com/michaeljclark/git/tree/sha-algorithms/sha\n>> \n>> This is a precursor to asking some questions about the proposed\n>> implementation of multiple or compat hashs (N-hash or 2-hash?).\n>> I am curious about the pack format and directory structure for\n>> loose objects. It seems there needs to be a single hash chosen\n>> for loose object filenames, and auxilliary hashes will need\n>> hash to hash map to go from a compat hash to new hash.\n> \n> That's correct.  There's documentation in the transition plan about what\n> this will look like.\n> \n> A stage 4 implementation (where repositories are either SHA-1 only or\n> SHA-256 only) has been written and I'll send it out once the remaining\n> test fixes are merged.\n> \n> I should point out that we specifically chose not to support a plethora\n> of algorithms because the goal is to encourage everybody to adopt a\n> single, secure algorithm.  The network protocol will need to\n> interoperate using a single algorithm, which means the repository will\n> need to contain a mapping for that algorithm.  Since the current plan is\n> to support no more than two algorithms at a time, one of which will need\n> to be SHA-1, allowing users to pick and choose from a variety of\n> algorithms harms interoperability.  Seamless interoperability between\n> SHA-1 and NewHash repositories was considered extremely important in the\n> transition plan.  That won't be coming immediately with the stage 4\n> implementation, but it is planned for the future.\n> \n> My hope is that whatever we pick now will be secure for some time to\n> come and that when we need to adopt a newer hash, whether due to\n> cryptographic advance or post-quantum cryptography, there will be no\n> existing SHA-1 repositories and transition can take place from NewHash\n> to NewNewHash.\n> -- \n> brian m. carlson: Houston, Texas, US\n> OpenPGP: https://keybase.io/bk2204\n\n"},{"id":"388809","messageId":"5aff676a-c4b2-6448-f99c-ec6f54f25a1a@iee.email","threadId":"52507","inReplyTo":"9279D11D-2BC2-4800-8282-C2219F152269@mac.com","subject":"Re: NewHash alternatives and SHA benchmarks","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.email","sentAt":"2019-12-23T15:15:49Z","receivedAt":"2019-12-23T15:15:54Z","isPatch":false,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"On 23/12/2019 01:59, Michael Clark wrote:\n> git doesn’t really support large files that well either so I’ll have to keep that in mind...\nI presume you are thinking of the Git-for-Windows (GfW) implementation\nhere, where 'sizeof(long)'=32 bits, so currently the GfW is limited to\n2/4GB file sizes.\n\nThe limitation is partly due to the zlib library API which uses 'long'\nfor stream sizes, though does have 'pointer*' file sizing, and hence\nfollows the Microsoft 32->64 bit transition approach. However zlib is\nable to handle larger files when the deflation/inflation is done in\nchunks of less than 'size(long)'.\n\nOn the 'Linux' version the limit is a 64 bit address and file size, so\nprobably not a real issue on those platforms ;-)\n\nThere has been a body of work on the change to using size_t for Git file\nsizes, but such a change is extensive and may not be acceptable because\nof the size of the code churn. I (and others!) had been looking at it\nhttps://github.com/git-for-windows/git/pull/2179.\n\nHope that helps clarify the large file support limitation on Windows.\n\nPhilip\n"}]}