{"thread":{"id":"29069","subject":"Re: Suggestion on hashing","startedAt":"2011-12-02T14:22:31Z","lastAt":"2011-12-07T01:44:36Z","messageCount":14,"participants":["Nguyen Thai Ngoc Duy","Jeff King","Bill Zaumen","Philip Oakley","Chris West (Faux)"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"180247","messageId":"CACsJy8CO1GtpZVo-oA2eKbQadsXYBEKVLfUH0GONR5jovuvH+Q@mail.gmail.com","threadId":"29069","inReplyTo":"1322813319.4340.109.camel@yos","subject":"Re: Suggestion on hashing","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-12-02T14:22:31Z","receivedAt":"2011-12-02T14:22:31Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"(I'm not sure why you dropped git@vger. I see nothing private here so\nI bring git@vger back)\n\nOn Fri, Dec 2, 2011 at 3:08 PM, Bill Zaumen <bill.zaumen@gmail.com> wrote:\n> At one point Nguyen said that \"What I'm thinking is whether it's\n> possible to decouple two sha-1 roles in git, as object identifier\n> and digest, separately. Each sha-1 identifies an object and an extra\n> set of digests on the \"same\" object.\"\n>\n> My code pretty much does that (it just uses a CRC instead of a real\n> digest, but I can easily change that).\n\nIt'd be easier to look at your code if you split it into a series of\nsmaller patches.\n\n> So the question is whether\n> using SHA-1 as an ID and SHA-256(?) as a digest is a better long term\n> solution than simply replacing SHA-1.\n\nI would not stick with any algorithm permanently. No one knows when\nSHA-256 might be broken.\n\n> If there is some interest in pursuing it further, I could make those\n> changes fairly easily.  Then you'd have two message digests, a SHA-1\n> and a longer one, with the longer one stored parallel to the actual\n> object. Then it becomes easy to compute a digest of all the digests\n> in a commit's tree and store that in a commit, if that is what you\n> want to do.\n\nI personally would like to see how it works out especially when\ncomputing new digests is much more expensive than SHA-1. And I hope\nthat by delaying computing new digests (stored outside actual\nobjects), we could make minimum code changes to git. Though security\nconcerns may be the killer factor and I haven't worked that out yet.\n\n> Replacing SHA-1 with something like SHA-256 sounds easier to implement,\n\nSHA-1 charateristics (like 20 byte length) are hard coded everywhere\nin git, it'd be a big audit.\n\n> but the problem is all the existing repositories.  While rewriting all\n> the objects and trees to use new hashes is similar to a rebase in most\n> cases, there is a complication - submodules.  Git stores the hash of\n> a submodule's commit in its tree because a particular revision of\n> a project 'goes' with a particular revision of a submodule. But, a\n> submodule can exist in one revision and not in the next or previous\n> revision  Furthermore A could be a submodule of B at one point in time,\n> and many commits later, B could end up being a submodule of A.\n> Fixing it up could be pretty complicated (plus having to deal with\n> network failures - to update GitHub for example, you'd have to download\n> submodules it uses, possibly from somewhere else and some submodules may\n> not be publicly accessible (e.g., a private project kept on GitHub but\n> with a critical submodule kept in house behind a corporate firewall).\n> Also, you might have to update a git repository and its submodules\n> concurrently, so that you always can find a new value when you need\n> it.\n>\n> My guess is that this could be far more complicated than what I did.\n> Excluding two files that are not used (the symbol PACKDB is not\n> defined), I added two new files, crcdb.h and objd-crcdb.c which store\n> CRCs for loose objects - 517 lines total including lots of comments in\n> the header file - full documentation for each function.  The other\n> changes include 1475 lines of new code in previously existing git files\n> and 136 deletions (most trivial).  There were also minor changes to\n> the makefile and test scripts.\n\nYou'd need to convince git maintainer this is worth doing first,\nbefore talking how big the changes are ;-)\n\n> Bill\n-- \nDuy\n"},{"id":"180262","messageId":"20111202175444.GB24093@sigill.intra.peff.net","threadId":"29069","inReplyTo":"1322813319.4340.109.camel@yos","subject":"Re: Suggestion on hashing","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-02T17:54:44Z","receivedAt":"2011-12-02T17:54:44Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 02, 2011 at 12:08:39AM -0800, Bill Zaumen wrote:\n\n> At one point Nguyen said that \"What I'm thinking is whether it's\n> possible to decouple two sha-1 roles in git, as object identifier\n> and digest, separately. Each sha-1 identifies an object and an extra\n> set of digests on the \"same\" object.\"\n> \n> My code pretty much does that (it just uses a CRC instead of a real\n> digest, but I can easily change that).   So the question is whether\n> using SHA-1 as an ID and SHA-256(?) as a digest is a better long term\n> solution than simply replacing SHA-1.\n\nI think your code is solving the wrong problem (or solving the right\nproblem in a half-way manner). The only things that make sense to me\nare:\n\n  1. Do nothing. SHA-1 is probably not broken yet, even by the NSA, and\n     even if it is, an attack is extremely expensive to mount. This may\n     change in the future, of course, but it will probably stay\n     expensive for a while.\n\n  2. Decouple the object identifier and digest roles, but insert the\n     digest into newly created objects, so it can be part of the\n     signature chain. I described such a scheme in one of my replies to\n     you. It has some complexities, but has the bonus that we can build\n     directly on older history, preserving its sha1s.\n\n  3. Replace SHA-1 with a more secure algorithm.\n\nI'm probably in favor of (1) at this point. Whether to do (2) or (3)\nwill depend on where we are when SHA-1 gets feasibly broken. It may be\nmany years away, at which point we may be considering a git 2.0 that\nbreaks repository compatibility, anyway. That would be a natural time to\nconsider changing the algorithm.\n\n> Replacing SHA-1 with something like SHA-256 sounds easier to implement,\n> but the problem is all the existing repositories.\n\nRight. I don't think anyone is denying that it would be a giant pain.\n\n-Peff\n"},{"id":"180264","messageId":"20111202180951.GC24093@sigill.intra.peff.net","threadId":"29069","inReplyTo":"CACsJy8CO1GtpZVo-oA2eKbQadsXYBEKVLfUH0GONR5jovuvH+Q@mail.gmail.com","subject":"Re: Suggestion on hashing","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-02T18:09:51Z","receivedAt":"2011-12-02T18:09:51Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 02, 2011 at 09:22:31PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> > So the question is whether\n> > using SHA-1 as an ID and SHA-256(?) as a digest is a better long term\n> > solution than simply replacing SHA-1.\n> \n> I would not stick with any algorithm permanently. No one knows when\n> SHA-256 might be broken.\n\nYeah, you could stick a few bits of algorithm parameter in the beginning\nof each identifier. It would mean unique hashes get one character or so\nlonger (and they would all start with \"1\", or whatever the identifier\nis).\n\nSHA-256 doesn't suffer from SHA-1's problems, though they are based on\nrelated constructions, so I think there is some concern that it may\neventually fail in the same way. SHA-3 is a better bet in that sense,\nbut it will also be very unproven, even once it is actually\nstandardized.\n\n> > Replacing SHA-1 with something like SHA-256 sounds easier to implement,\n> \n> SHA-1 charateristics (like 20 byte length) are hard coded everywhere\n> in git, it'd be a big audit.\n\nIn theory, you could truncate a longer hash to 160-bits. It's not the\nbit-strength of SHA-1 that is the problem, but the attacks on the\nalgorithm itself which reduce the bit-strength to something too low.\nI would think a truncated result would retain the same cryptographic\nproperties, as one of the properties of the un-truncated hash is that\nchanges in the input data are reflected throughout the hash. Some\nhashes, like Skein, explicitly have a big internal state, and then just\nlet you output as many bytes as is appropriate (i.e., being a drop-in\nreplacement for SHA-1 is an explicit goal).\n\nBut I'm not a cryptographer, so there may be some subtle issues with\ndoing that to arbitrary hash functions.\n\n-Peff\n"},{"id":"180276","messageId":"1322873323.1729.91.camel@yos","threadId":"29069","inReplyTo":"CACsJy8CO1GtpZVo-oA2eKbQadsXYBEKVLfUH0GONR5jovuvH+Q@mail.gmail.com","subject":"Re: Suggestion on hashing","fromName":"Bill Zaumen","fromEmail":"bill.zaumen@gmail.com","sentAt":"2011-12-03T00:48:43Z","receivedAt":"2011-12-03T00:48:43Z","isPatch":false,"sender":{"key":"bill.zaumen@gmail.com","avatar":null},"body":"On Fri, 2011-12-02 at 21:22 +0700, Nguyen Thai Ngoc Duy wrote:\n> (I'm not sure why you dropped git@vger. I see nothing private here so\n> I bring git@vger back)\n\nOh, I just didn't want to flood the mailing list with too much on\none topic and figured we could summarize a discussion at some point\nand post that, but if you'd rather keep it all on the list, that's \nfine with me.\n\nI can split the code into a series of smaller patches - smaller than\nthe set of three I sent, but I'm not sure if the test scripts will work\nwith all of the intermediate patches if I do that.\n\nI can also make the digest (current a CRC) pluggable.  Then you can try\ndifferent digests as an experiment and see how that affects performance.\nMy implementation uses the CRC or new digests only when\nthe object database is being modified or explicitly verified. Basically\nthe code provides memoization for an additional hash function, used\nfor whatever purpose you desire.\n\nIf you want to put a digest of message digests into a commit message,\nyou can do that fairly quickly as one level of digests has been\nprecomputed. I think Jeff's or your suggestion of putting an additional\ndigest in the commit message is a good idea.  If you want to experiment\nwith such changes, the code would provide a reasonable start on that.\n\nSo, I guess I should make those changes - pluggable digest and \nsplitting the patches further.\n\n> You'd need to convince git maintainer this is worth doing first,\n> before talking how big the changes are ;-)\n\nI'd guess there are several issues: the amount of code, how complex\nthe changes are, what the performance impacts are, whether the changes\nare backwards compatible, and what you get for the effort.\n\nAs a start on the last question, \"what you get,\" aside from some extra\nchecking to detect problems, if you modify commit messages and signed\ntags to use better digests, you can make a stronger argument regarding\nauthentication.  For example, suppose you have a project in which your\ncode is dual-licensed - GPL for free use but a separate license if the\ncode is used in a proprietary product and there is a legal dispute,\nusing a better digest than SHA-1 would have some advantages - when they\nstart calling in expert witnesses, one side will bring in a security\nexpert who will testify that SHA-1 is too weak to be used for\nauthentication, citing government publications such\nas http://csrc.nist.gov/groups/ST/hash/statement.html as evidence. The\njury is not going to consist of people who can fully understand the\ndetails, so being able to say that git's authentication matches current\nbest practices would be an additional reason to use git.\n"},{"id":"180277","messageId":"1322877021.1729.118.camel@yos","threadId":"29069","inReplyTo":"20111202175444.GB24093@sigill.intra.peff.net","subject":"Re: Suggestion on hashing","fromName":"Bill Zaumen","fromEmail":"bill.zaumen@gmail.com","sentAt":"2011-12-03T01:50:21Z","receivedAt":"2011-12-03T01:50:21Z","isPatch":false,"sender":{"key":"bill.zaumen@gmail.com","avatar":null},"body":"On Fri, 2011-12-02 at 12:54 -0500, Jeff King wrote:\n> On Fri, Dec 02, 2011 at 12:08:39AM -0800, Bill Zaumen wrote:\n\n> I think your code is solving the wrong problem (or solving the right\n> problem in a half-way manner). The only things that make sense to me\n> are:\n> \n>   1. Do nothing. SHA-1 is probably not broken yet, even by the NSA, and\n>      even if it is, an attack is extremely expensive to mount. This may\n>      change in the future, of course, but it will probably stay\n>      expensive for a while.\n> \n>   2. Decouple the object identifier and digest roles, but insert the\n>      digest into newly created objects, so it can be part of the\n>      signature chain. I described such a scheme in one of my replies to\n>      you. It has some complexities, but has the bonus that we can build\n>      directly on older history, preserving its sha1s.\n> \n>   3. Replace SHA-1 with a more secure algorithm.\n\nSuppose I make the digest pluggable, something I intended to do\neventually anyway?  Then you just use the existing SHA-1 as an\nobject identifier and the new digest in a signature chain?  What I\ndid was essentially to compute the new digest (using a CRC as the\ntrivial case) whenever an object's SHA-1 hash is computed, plus\nusing the new digest for low-cost collision checks.\n\nThen you have everything needed to experiment with your second option.\nI got the impression that Nguyen had some interest in that, but could\nbe mistaken.\n\nThe use is simple: if you have the SHA-1 hash of an object, you call\na function, currently named \"has_sha1_file_crc\" and it returns true if\na CRC is available, writing the hash into the buffer supplied as its\nsecond argument.  You can do whatever you like with it.  If you want\na digest of digests, you just traverse a commit's tree, and call\nhas_sha1_file_crc whenever you want to look up a digest.  So, the API\nis actually very simple if you just use the patch to quickly look up\nthe digest associated with a SHA-1 ID - everything else it does happens\nautomatically.\n\n \n"},{"id":"180280","messageId":"20111203150842.GA4442@sigill.intra.peff.net","threadId":"29069","inReplyTo":"1322877021.1729.118.camel@yos","subject":"Re: Suggestion on hashing","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-03T15:08:42Z","receivedAt":"2011-12-03T15:08:42Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 02, 2011 at 05:50:21PM -0800, Bill Zaumen wrote:\n\n> On Fri, 2011-12-02 at 12:54 -0500, Jeff King wrote:\n> > On Fri, Dec 02, 2011 at 12:08:39AM -0800, Bill Zaumen wrote:\n> \n> > I think your code is solving the wrong problem (or solving the right\n> > problem in a half-way manner). The only things that make sense to me\n> > are:\n> > \n> >   1. Do nothing. SHA-1 is probably not broken yet, even by the NSA, and\n> >      even if it is, an attack is extremely expensive to mount. This may\n> >      change in the future, of course, but it will probably stay\n> >      expensive for a while.\n> > \n> >   2. Decouple the object identifier and digest roles, but insert the\n> >      digest into newly created objects, so it can be part of the\n> >      signature chain. I described such a scheme in one of my replies to\n> >      you. It has some complexities, but has the bonus that we can build\n> >      directly on older history, preserving its sha1s.\n> > \n> >   3. Replace SHA-1 with a more secure algorithm.\n> \n> Suppose I make the digest pluggable, something I intended to do\n> eventually anyway?  Then you just use the existing SHA-1 as an\n> object identifier and the new digest in a signature chain?  What I\n> did was essentially to compute the new digest (using a CRC as the\n> trivial case) whenever an object's SHA-1 hash is computed, plus\n> using the new digest for low-cost collision checks.\n\nIf you make the digest stronger (or pluggable) and include it in the\nactual objects themselves, then you have a start on (2).\n\nI'd drop all of the digest-exchange bits from the protocol, as the\nactual signatures are the real, trustable verification. I don't think\nyou can drop the external storage of the digests, which is one of the\nugliest bits. You'll be asking for the digests all the time to create\nnew commit objects, so you need to have it at hand without rehashing.\n\nAnd I wouldn't get my hopes up that this will go into git any time soon.\nAt this point, we're really guessing about how broken SHA-1 will be in\nthe future, and how much we are going to want to care.\n\nJust my two cents.\n\n-Peff\n"},{"id":"180281","messageId":"68774CC59ECA4F7AB5DA410F34045F32@PhilipOakley","threadId":"29069","inReplyTo":"20111203150842.GA4442@sigill.intra.peff.net","subject":"Re: Suggestion on hashing","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.org","sentAt":null,"receivedAt":"2011-12-03T15:08:42Z","isPatch":false,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"Had you seen the recent thread by Junio with the footnote link to the paper \non reconcilliation by using multiple hashes?\nhttp://article.gmane.org/gmane.linux.kernel/1214517.\n\"What's the Difference? Efficient Set Reconciliation without Prior\nContext\" http://cseweb.ucsd.edu/~fuyeda/papers/sigcomm2011.pdfIt looks to \nhave a lot of the properties being sought, and links with other git aspects.\n\nPhilip\n\nFrom: \"Jeff King\" <peff@peff.net>: Saturday, December 03, 2011 3:08 PM\nOn Fri, Dec 02, 2011 at 05:50:21PM -0800, Bill Zaumen wrote:\n\n> On Fri, 2011-12-02 at 12:54 -0500, Jeff King wrote:\n> > On Fri, Dec 02, 2011 at 12:08:39AM -0800, Bill Zaumen wrote:\n>\n> > I think your code is solving the wrong problem (or solving the right\n> > problem in a half-way manner). The only things that make sense to me\n> > are:\n> >\n> >   1. Do nothing. SHA-1 is probably not broken yet, even by the NSA, and\n> >      even if it is, an attack is extremely expensive to mount. This may\n> >      change in the future, of course, but it will probably stay\n> >      expensive for a while.\n> >\n> >   2. Decouple the object identifier and digest roles, but insert the\n> >      digest into newly created objects, so it can be part of the\n> >      signature chain. I described such a scheme in one of my replies to\n> >      you. It has some complexities, but has the bonus that we can build\n> >      directly on older history, preserving its sha1s.\n> >\n> >   3. Replace SHA-1 with a more secure algorithm.\n>\n> Suppose I make the digest pluggable, something I intended to do\n> eventually anyway?  Then you just use the existing SHA-1 as an\n> object identifier and the new digest in a signature chain?  What I\n> did was essentially to compute the new digest (using a CRC as the\n> trivial case) whenever an object's SHA-1 hash is computed, plus\n> using the new digest for low-cost collision checks.\n\nIf you make the digest stronger (or pluggable) and include it in the\nactual objects themselves, then you have a start on (2).\n\nI'd drop all of the digest-exchange bits from the protocol, as the\nactual signatures are the real, trustable verification. I don't think\nyou can drop the external storage of the digests, which is one of the\nugliest bits. You'll be asking for the digests all the time to create\nnew commit objects, so you need to have it at hand without rehashing.\n\nAnd I wouldn't get my hopes up that this will go into git any time soon.\nAt this point, we're really guessing about how broken SHA-1 will be in\nthe future, and how much we are going to want to care.\n\nJust my two cents.\n\n-Peff\n--\nVersion: 2012.0.1873 / Virus Database: 2102/4653 - Release Date: 12/02/11\n"},{"id":"180287","messageId":"1322947314.1763.41.camel@yos","threadId":"29069","inReplyTo":"20111203150842.GA4442@sigill.intra.peff.net","subject":"Re: Suggestion on hashing","fromName":"Bill Zaumen","fromEmail":"bill.zaumen@gmail.com","sentAt":"2011-12-03T21:21:54Z","receivedAt":"2011-12-03T21:21:54Z","isPatch":false,"sender":{"key":"bill.zaumen@gmail.com","avatar":null},"body":"On Sat, 2011-12-03 at 10:08 -0500, Jeff King wrote:\n\n> > \n> > Suppose I make the digest pluggable, something I intended to do\n> > eventually anyway?  Then you just use the existing SHA-1 as an\n> > object identifier and the new digest in a signature chain?  What I\n> > did was essentially to compute the new digest (using a CRC as the\n> > trivial case) whenever an object's SHA-1 hash is computed, plus\n> > using the new digest for low-cost collision checks.\n> \n> If you make the digest stronger (or pluggable) and include it in the\n> actual objects themselves, then you have a start on (2).\n> \n> I'd drop all of the digest-exchange bits from the protocol, as the\n> actual signatures are the real, trustable verification. I don't think\n> you can drop the external storage of the digests, which is one of the\n> ugliest bits. You'll be asking for the digests all the time to create\n> new commit objects, so you need to have it at hand without rehashing.\n\nThe digest-exchange bits, including the tests and response to errors,\nis only 222 lines of new code, so its really a minor part.  The rest\ntakes care of what you referred to as \"one of the ugliest bits,\" so\nI think it is useful to have available - you can then try various ways\nof improving the authentication of commit objects without having to do\na lot of initial work.\n\nI can make those changes - probably over the next couple of weeks or\nso (have some other non-related things to take care of) and then send\na new set of patches.\n\n> \n> And I wouldn't get my hopes up that this will go into git any time soon.\n> At this point, we're really guessing about how broken SHA-1 will be in\n> the future, and how much we are going to want to care.\n> \n> Just my two cents.\n\nThanks for the discussion.  I might add that it is not just a question\nof how broken SHA-1 is.  If an IT department is considering adopting Git\nas the company's revision control system and authentication is important\nto the company, an IT manager may not accept SHA-1 for authentication\npurposes because NIST claims SHA-1 is not adequate for authentication in\ngeneral and explaining to upper management why NIST's statement is not\napplicable given the way SHA-1 is used in Git is much harder than\nsaying, \"Git follows the current best practices regarding\nauthentication.\"  That statement is a simple check-list item one can\nshow upper management in comparing alternatives.\n\nSuch issues (making technical choices for non-technical reasons) have\ncome up before - I once worked on a high-speed (for the time) networking\nproject and our manager mentioned that transferring medical records such\nas X-ray pictures was one application - they do not accept lossy data\ncompression because, even if it is completely adequate, in a malpractice\nsuit, the plaintiff's lawyer would say, \"And they purposely threw away\ndata critical to my client's health,\" which would sound pretty damning\nto a typical jury.  The legal risk outweighed the cost of the additional\nbandwidth.\n"},{"id":"180332","messageId":"alpine.DEB.2.00.1112060146121.15104@hoki.goeswhere.com","threadId":"29069","inReplyTo":"CACsJy8CO1GtpZVo-oA2eKbQadsXYBEKVLfUH0GONR5jovuvH+Q@mail.gmail.com","subject":"Re: Suggestion on hashing","fromName":"Chris West (Faux)","fromEmail":"faux@goeswhere.com","sentAt":"2011-12-06T01:56:17Z","receivedAt":"2011-12-06T01:56:17Z","isPatch":false,"sender":{"key":"faux@goeswhere.com","avatar":null},"body":"\nNguyen Thai Ngoc Duy wrote:\n> SHA-1 charateristics (like 20 byte length) are hard coded everywhere\n> in git, it'd be a big audit.\n\nI was planning to look at this anyway.  My branch[1] allows\n  init/add/commit with SHA-256, SHA-512 and all the SHA-3 candidates.\n\nlog/fsck/etc. are all broken.  Don't even dare try packs.  Fixing things\n  is painful but not impossible.  I'm not convinced the task is even\n  remotely insurmountable.\n\n(This is not a request-for-comments, just an informational notification.\n  It does not even attempt to address compatability or the like.)\n\n$ make HASH=sha512 -j6\n$ PATH=bin-wrappers:..\n$ git init && echo hi > foo && git add foo && git commit -m \"bang\"\nInitialized empty Git repository in /.../.git/\n[master (root-commit) \n8d3ae658dff0c6e398bb4a0d193974e49acfadedfcd61daca42c931ac18d5ac46f0a068e08d81c25d7b79b1c3f4951e4340eeb90f0ef39de355c9bab7e75faba] \nbang\n  1 files changed, 1 insertions(+), 0 deletions(-)\n    create mode 100644 foo\n\n\n1. (Please use the hash-v0.0.1 tag, I rebase.)\n   gitweb: http://preview.tinyurl.com/bsufh92\n   git://git.goeswhere.com/git/git.git\n   https://github.com/FauxFaux/git/tree/hash-v0.0.1\n\n---\nChris West (Faux)\nFreenode #git: FauxFaux\nhttps://ssl.goeswhere.com/key-transition-2011-10-10.txt.asc\ngpg: 408A E4F1 4EA7 33EF 1265  82C1 B195 E1C4 779B A9B2\n"},{"id":"180334","messageId":"1323143223.1745.67.camel@yos","threadId":"29069","inReplyTo":"alpine.DEB.2.00.1112060146121.15104@hoki.goeswhere.com","subject":"Re: Suggestion on hashing","fromName":"Bill Zaumen","fromEmail":"bill.zaumen@gmail.com","sentAt":"2011-12-06T03:47:03Z","receivedAt":"2011-12-06T03:47:03Z","isPatch":false,"sender":{"key":"bill.zaumen@gmail.com","avatar":null},"body":"When I went through the code, I noted that SHA-1 hashes are\ncurrently used for the following:\n\n   * object IDs\n   * authentication (something to sign using public-key encryption)\n   * data integrity (basically a really good checksum).\n\nWhile there are lot of 20-byte arrays of unsigned char, many of those\nare associated with lookups.  You might want to look at the\nnumber of places that git_SHA1_Init is called (there aren't all that\nmany of those, and that function indicates the points where SHA-1\nhashes are being created).\n\nWhile a few things I tried were complete false starts (kept those\nout of the preliminary patches I sent), I managed to store\na CRC (which you can treat as a place-holder for a real message\ndigest) for each SHA-1 hash in a pack file, but I did it by\ncreating a separate file (extension \".mds\") and that worked.\nI looked into modifying pack files, and that was too messy given\nthat you'd want older version to still work with newer remote\nrepositories.  The other factor is that the \"mds\" files are\ncomputed locally, and at the same time that you create an \"idx\" file.\nThe formats of the \"pack\" and \"idx\" files don't change.\n\nI've just started on replacing the CRC I used with real message\ndigests, making new digests easy to add. The plan is to initially\nmake it work with both a CRC and SHA-1 (the CRC so I can test it\neasily by comparing new and old versions to show that nothing\nchanged when it shouldn't have), and because Git already implements\nSHA-1.\n\nI should complete my changes.  If we are lucky, maybe the changes I'm\ntrying would solve some of the problems you mentioned with pack files.\nAt least I can store the digests in a way that doesn't break the log\nand fsck operations (it went through all the test suites, with only\nminor modifications for things like counting the number of files in\nparticular directories).\n\nIf you make changes to commit objects, fixing the test scripts is a \npain - there are a number of places where SHA-1 values are hard-\ncoded, and those have to be replaced.\n\nBill\n\nOn Tue, 2011-12-06 at 01:56 +0000, Chris West (Faux) wrote:\n> Nguyen Thai Ngoc Duy wrote:\n> > SHA-1 charateristics (like 20 byte length) are hard coded everywhere\n> > in git, it'd be a big audit.\n> \n> I was planning to look at this anyway.  My branch[1] allows\n>   init/add/commit with SHA-256, SHA-512 and all the SHA-3 candidates.\n> \n> log/fsck/etc. are all broken.  Don't even dare try packs.  Fixing things\n>   is painful but not impossible.  I'm not convinced the task is even\n>   remotely insurmountable.\n> \n> (This is not a request-for-comments, just an informational notification.\n>   It does not even attempt to address compatability or the like.)\n"},{"id":"180336","messageId":"CACsJy8CM8xqWxTx14QbY+-bT=306p3U=6gJfRaW=dDD-Swo7-w@mail.gmail.com","threadId":"29069","inReplyTo":"alpine.DEB.2.00.1112060146121.15104@hoki.goeswhere.com","subject":"Re: Suggestion on hashing","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-12-06T04:46:38Z","receivedAt":"2011-12-06T04:46:38Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Dec 6, 2011 at 8:56 AM, Chris West (Faux) <faux@goeswhere.com> wrote:\n>\n> Nguyen Thai Ngoc Duy wrote:\n>>\n>> SHA-1 charateristics (like 20 byte length) are hard coded everywhere\n>> in git, it'd be a big audit.\n>\n>\n> I was planning to look at this anyway.  My branch[1] allows\n>  init/add/commit with SHA-256, SHA-512 and all the SHA-3 candidates.\n\nGreat!\n\n> log/fsck/etc. are all broken.  Don't even dare try packs.  Fixing things\n>  is painful but not impossible.  I'm not convinced the task is even\n>  remotely insurmountable.\n\nIt would take more work, but after you're done with code changes, you\nshould have a look at updating the test suite. We have many SHA-1s\nthere. If the test suite passes, your job is (beautifully) done.\n-- \nDuy\n"},{"id":"180343","messageId":"1323151347.1745.73.camel@yos","threadId":"29069","inReplyTo":"CACsJy8CM8xqWxTx14QbY+-bT=306p3U=6gJfRaW=dDD-Swo7-w@mail.gmail.com","subject":"Re: Suggestion on hashing","fromName":"Bill Zaumen","fromEmail":"bill.zaumen@gmail.com","sentAt":"2011-12-06T06:02:27Z","receivedAt":"2011-12-06T06:02:27Z","isPatch":false,"sender":{"key":"bill.zaumen@gmail.com","avatar":null},"body":"On Tue, 2011-12-06 at 11:46 +0700, Nguyen Thai Ngoc Duy wrote:\n> On Tue, Dec 6, 2011 at 8:56 AM, Chris West (Faux) <faux@goeswhere.com> wrote:\n> >\n> > Nguyen Thai Ngoc Duy wrote:\n> >>\n> >> SHA-1 charateristics (like 20 byte length) are hard coded everywhere\n> >> in git, it'd be a big audit.\n> >\n> >\n> > I was planning to look at this anyway.  My branch[1] allows\n> >  init/add/commit with SHA-256, SHA-512 and all the SHA-3 candidates.\n> \n> Great!\n\nIf you are replacing SHA-1 as an object ID with another hash function,\ntwo things to watch are submodules and alternative object databases.\nBecause of those, it is necessary to worry about the order in which\nrepositories are converted.  In the worst case for submodules, you'd\nhave to do multiple repositories at the same time, switching between\nthem depending on what you need at each point.\n"},{"id":"180358","messageId":"CACsJy8CXkz-W3Z3pX-C-+fjLz=WahBajE2uLEG-f3gG_svEhug@mail.gmail.com","threadId":"29069","inReplyTo":"1323151347.1745.73.camel@yos","subject":"Re: Suggestion on hashing","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-12-06T06:23:00Z","receivedAt":"2011-12-06T06:23:00Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Dec 6, 2011 at 1:02 PM, Bill Zaumen <bill.zaumen@gmail.com> wrote:\n> On Tue, 2011-12-06 at 11:46 +0700, Nguyen Thai Ngoc Duy wrote:\n>> On Tue, Dec 6, 2011 at 8:56 AM, Chris West (Faux) <faux@goeswhere.com> wrote:\n>> >\n>> > Nguyen Thai Ngoc Duy wrote:\n>> >>\n>> >> SHA-1 charateristics (like 20 byte length) are hard coded everywhere\n>> >> in git, it'd be a big audit.\n>> >\n>> >\n>> > I was planning to look at this anyway.  My branch[1] allows\n>> >  init/add/commit with SHA-256, SHA-512 and all the SHA-3 candidates.\n>>\n>> Great!\n>\n> If you are replacing SHA-1 as an object ID with another hash function,\n> two things to watch are submodules and alternative object databases.\n> Because of those, it is necessary to worry about the order in which\n> repositories are converted.  In the worst case for submodules, you'd\n> have to do multiple repositories at the same time, switching between\n> them depending on what you need at each point.\n\nI know migration would be painful. But note that new repos can benefit\nstronger digest without legacy (of course until it links to an old\nrepo). For submodules, I think we should extend it to become something\nsimilar to soft-link: git link is an SHA-1 to a text file that\ncontains SHA-1 and maybe other digests of the submodule's tip.\n-- \nDuy\n"},{"id":"180436","messageId":"1323222276.1705.434.camel@yos","threadId":"29069","inReplyTo":"CACsJy8CXkz-W3Z3pX-C-+fjLz=WahBajE2uLEG-f3gG_svEhug@mail.gmail.com","subject":"Re: Suggestion on hashing","fromName":"Bill Zaumen","fromEmail":"bill.zaumen@gmail.com","sentAt":"2011-12-07T01:44:36Z","receivedAt":"2011-12-07T01:44:36Z","isPatch":false,"sender":{"key":"bill.zaumen@gmail.com","avatar":null},"body":"On Tue, 2011-12-06 at 13:23 +0700, Nguyen Thai Ngoc Duy wrote:\n> On Tue, Dec 6, 2011 at 1:02 PM, Bill Zaumen <bill.zaumen@gmail.com> wrote:\n\n> > If you are replacing SHA-1 as an object ID with another hash function,\n> > two things to watch are submodules and alternative object databases.\n> > Because of those, it is necessary to worry about the order in which\n> > repositories are converted.  In the worst case for submodules, you'd\n> > have to do multiple repositories at the same time, switching between\n> > them depending on what you need at each point.\n> \n> I know migration would be painful. But note that new repos can benefit\n> stronger digest without legacy (of course until it links to an old\n> repo). For submodules, I think we should extend it to become something\n> similar to soft-link: git link is an SHA-1 to a text file that\n> contains SHA-1 and maybe other digests of the submodule's tip.\n\nRepositories would need to store a table mapping old SHA-1 values to\nthe new ones (for commits).  There's nothing in a repository to\nreliably indicate that it is being used as a submodule, and the choice\nof submodules can vary from commit to commit, making it difficult to\ncontrol the order in which objects have their hashes updated.  In some\ncorner cases, you could have two branches in each of two repositories\nwith different choices as to which is a submodule of which, although\nI'd be surprised if anyone actually did that.\n\nAside from that, in some corporate environments, the IT departments\nwant to determine the release schedule for applications, and would\ntake a dim view of changes that could not be tested first without being\nwidely deployed.  You could end up making Git unacceptable for those\ndepartments if you do not maintain backwards compatibility with\nexisting repositories.\n"}]}