{"thread":{"id":"31826","subject":"When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)","startedAt":"2012-10-15T16:42:29Z","lastAt":"2012-10-17T08:05:30Z","messageCount":14,"participants":["Elia Pinto","Ævar Arnfjörð Bjarmason","Jeff King","René Scharfe","Theodore Ts'o","david@lang.hm","Junio C Hamano","Peter Todd"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"201268","messageId":"CA+EOSBncr=4a4d8n9xS4FNehyebpmX8JiUwCsXD47EQDE+DiUQ@mail.gmail.com","threadId":"31826","inReplyTo":null,"subject":"When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)","fromName":"Elia Pinto","fromEmail":"gitter.spiros@gmail.com","sentAt":"2012-10-15T16:42:29Z","receivedAt":"2012-10-15T16:42:29Z","isPatch":false,"sender":{"key":"gitter.spiros@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158490?v=4"},"body":"Very clear analysis. Well written. Perhaps is it the time to update\nhttp://git-scm.com/book/ch6-1.html (A SHORT NOTE ABOUT SHA-1) ?\n\nHope useful\n\nhttp://www.schneier.com/crypto-gram-1210.html\n\nBest Regards\n"},{"id":"201275","messageId":"CACBZZX65Kbp8N9X9UtBfJca7U1T0m-VtKZeKM5q9mhyCR7dwGg@mail.gmail.com","threadId":"31826","inReplyTo":"CA+EOSBncr=4a4d8n9xS4FNehyebpmX8JiUwCsXD47EQDE+DiUQ@mail.gmail.com","subject":"Re: When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2012-10-15T17:47:09Z","receivedAt":"2012-10-15T17:47:09Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Mon, Oct 15, 2012 at 6:42 PM, Elia Pinto wrote:\n> Very clear analysis. Well written. Perhaps is it the time to update\n> http://git-scm.com/book/ch6-1.html (A SHORT NOTE ABOUT SHA-1) ?\n>\n> Hope useful\n>\n> http://www.schneier.com/crypto-gram-1210.html\n\nThis would be concerning if the Git security model would break down if\nsomeone found a SHA1 collision, but it really wouldn't.\n\nIt's one thing to find *a* collision, it's quite another to:\n\n 1. Find a collision for the sha1 of harmless.c which I know you use,\n and replace it with evil.c.\n\n 2. Somehow make evil.c compile so that it actually does something\n useful and nefarious, and doesn't just make the C compiler puke.\n\n If finding one arbitrary collision costs $43K in 2021 dollars\n getting past this point is going to take quite a large multiple of\n $43K.\n\n 3. Somehow inject the new evil object into your repository, or\n convince you to re-clone it / clone it from somewhere you usually\n wouldn't.\n\nAt some point in the early days of Git Linus went on a rant to this\neffect either on this list or on the LKML.\n\nMaybe it would be useful to include some of that instead?\n\nIt would be very interesting to see an analysis that deals with some\nactual Git-related security scenarios, instead of something that just\nassumes that if someone finds *any* SHA1 collision the sky is going to\nfall.\n"},{"id":"201278","messageId":"CA+EOSBnUxHW2c6r4C6cTn0P_NMAoyJL9jvaG9Du1O8BT-8EVPA@mail.gmail.com","threadId":"31826","inReplyTo":"CACBZZX65Kbp8N9X9UtBfJca7U1T0m-VtKZeKM5q9mhyCR7dwGg@mail.gmail.com","subject":"Re: When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)","fromName":"Elia Pinto","fromEmail":"gitter.spiros@gmail.com","sentAt":"2012-10-15T18:09:12Z","receivedAt":"2012-10-15T18:09:12Z","isPatch":false,"sender":{"key":"gitter.spiros@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158490?v=4"},"body":"2012/10/15 Ævar Arnfjörð Bjarmason :\n> On Mon, Oct 15, 2012 at 6:42 PM, Elia Pinto wrote:\n>> Very clear analysis. Well written. Perhaps is it the time to update\n>> http://git-scm.com/book/ch6-1.html (A SHORT NOTE ABOUT SHA-1) ?\n>>\n>> Hope useful\n>>\n>> http://www.schneier.com/crypto-gram-1210.html\n>\n> This would be concerning if the Git security model would break down if\n> someone found a SHA1 collision, but it really wouldn't.\nI know perfectly.\n>\n> It's one thing to find *a* collision, it's quite another to:\n>\n> 1. Find a collision for the sha1 of harmless.c which I know you use,\n> and replace it with evil.c.\n>\n> 2. Somehow make evil.c compile so that it actually does something\n> useful and nefarious, and doesn't just make the C compiler puke.\n>\n> If finding one arbitrary collision costs $43K in 2021 dollars\n> getting past this point is going to take quite a large multiple of\n> $43K.\n>\n> 3. Somehow inject the new evil object into your repository, or\n> convince you to re-clone it / clone it from somewhere you usually\n> wouldn't.\n>\n> At some point in the early days of Git Linus went on a rant to this\n> effect either on this list or on the LKML.\n>\n> Maybe it would be useful to include some of that instead?\n>\nWhat you wrote is a risk analysis. I appreciate, i am also a security\nprofessionals..\n> It would be very interesting to see an analysis that deals with some\n> actual Git-related security scenarios, instead of something that just\n> assumes that if someone finds *any* SHA1 collision the sky is going to\n> fall.\nWhat you wrote is a risk analysis. I appreciate, as security professionals, too.\n\nI agree, of course. However, it is totally different from saying that\nbecause exists the birthday paradox git will be immune to collision,\nsure, if caused by a cryptographic attack. But clearly the risk for a\nproject that uses a cryptographic hash function as a hash function, as\ngit, is zero in the absence of a real use case. In computer security\nthe use of encryption is hardly the point of attack, today, as you\nhave clearly said. But it is the most invisible to highlight.\n\nIt seemed interesting to quote here the Bruce article because the\ntopic has already been discussed in the past here. That's it. No more,\nno less.\n\nThanks\n\nBest Regards\nBest Regard\n"},{"id":"201280","messageId":"20121015183438.GB31658@sigill.intra.peff.net","threadId":"31826","inReplyTo":"CACBZZX65Kbp8N9X9UtBfJca7U1T0m-VtKZeKM5q9mhyCR7dwGg@mail.gmail.com","subject":"Re: When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-15T18:34:38Z","receivedAt":"2012-10-15T18:34:38Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Oct 15, 2012 at 07:47:09PM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> On Mon, Oct 15, 2012 at 6:42 PM, Elia Pinto wrote:\n> > Very clear analysis. Well written. Perhaps is it the time to update\n> > http://git-scm.com/book/ch6-1.html (A SHORT NOTE ABOUT SHA-1) ?\n> >\n> > Hope useful\n> >\n> > http://www.schneier.com/crypto-gram-1210.html\n> \n> This would be concerning if the Git security model would break down if\n> someone found a SHA1 collision, but it really wouldn't.\n> \n> It's one thing to find *a* collision, it's quite another to:\n> \n> 1. Find a collision for the sha1 of harmless.c which I know you use,\n> and replace it with evil.c.\n> \n> 2. Somehow make evil.c compile so that it actually does something\n> useful and nefarious, and doesn't just make the C compiler puke.\n> \n> If finding one arbitrary collision costs $43K in 2021 dollars\n> getting past this point is going to take quite a large multiple of\n> $43K.\n\nThere are easier attacks than that if you can hide arbitrary bytes\ninside a file. It's hard with C source code. The common one in hash\ncollision detection circles is to put invisible cruft into binary\ndocument formats like PDF or Postscript. Git blobs themselves do not\nhave such an invisible place to put it, but you might be storing a\nformat that does.\n\nBut worse, git _commits_ have such an invisible portion. We calculate\nthe sha1 over the full commit, but we tend to show only the portion up\nto the first NUL byte. I used that horrible trick in my \"choose your own\nsha1 prefix\" patch. However, we could mitigate that by checking for\nembedded NULs in git-fsck.\n\n> 3. Somehow inject the new evil object into your repository, or\n> convince you to re-clone it / clone it from somewhere you usually\n> wouldn't.\n\nYeah, this part is the kicker. With the commit NUL trick, you would make\na useful commit and then ask somebody to pull it, and then later replace\nit with a commit pointing to an arbitrary tree. But if we assume we can\ndetect that easily (which I think we can), we are left with replacing\nbinary blobs that have hidden bits. And most projects do not take many\nsuch blobs, and the result is that you could only replace the contents\nof that particular blob, not an arbitrary part of the tree.\n\n> It would be very interesting to see an analysis that deals with some\n> actual Git-related security scenarios, instead of something that just\n> assumes that if someone finds *any* SHA1 collision the sky is going to\n> fall.\n\nI agree that most of the analysis is overblown. Having read the analysis\nSchneier pointed to, it actually is not that bad. We have 5-10 years to\nget to a point where it's really expensive and extremely complex to\nmount a single attack.\n\nThat doesn't seem like an emergency to me. It sounds like something we\nshould be thinking about (and we are). The simplest thing would be to\nwait for a moment when it makes sense to break compatibility (e.g., we\ndecide that \"git 2.0\" is here, and everybody will have to rewrite to\ntake advantage of new features, so we can jump to sha-2). We can also\nstart building sha-2 history that references sha-1 history. That would\nmean everybody needs to upgrade their git, but that is not a problem\nthat requires 5-10 years of foresight and planning.\n\n-Peff\n"},{"id":"201283","messageId":"CA+EOSBki6-PWu=mwxr3PU0XC15cBhqr7L5Ay7-e9on+jGumsxw@mail.gmail.com","threadId":"31826","inReplyTo":"20121015183438.GB31658@sigill.intra.peff.net","subject":"Re: When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)","fromName":"Elia Pinto","fromEmail":"gitter.spiros@gmail.com","sentAt":"2012-10-15T19:09:44Z","receivedAt":"2012-10-15T19:09:44Z","isPatch":false,"sender":{"key":"gitter.spiros@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158490?v=4"},"body":"Hem , sha-3 i suppose, keccak, no ? But really is not so urgent as you\nhave already told .\n\nBest\n\n2012/10/15, Jeff King :\n> On Mon, Oct 15, 2012 at 07:47:09PM +0200, Ævar Arnfjörð Bjarmason wrote:\n>\n>> On Mon, Oct 15, 2012 at 6:42 PM, Elia Pinto \n>> wrote:\n>> > Very clear analysis. Well written. Perhaps is it the time to update\n>> > http://git-scm.com/book/ch6-1.html (A SHORT NOTE ABOUT SHA-1) ?\n>> >\n>> > Hope useful\n>> >\n>> > http://www.schneier.com/crypto-gram-1210.html\n>>\n>> This would be concerning if the Git security model would break down if\n>> someone found a SHA1 collision, but it really wouldn't.\n>>\n>> It's one thing to find *a* collision, it's quite another to:\n>>\n>> 1. Find a collision for the sha1 of harmless.c which I know you use,\n>> and replace it with evil.c.\n>>\n>> 2. Somehow make evil.c compile so that it actually does something\n>> useful and nefarious, and doesn't just make the C compiler puke.\n>>\n>> If finding one arbitrary collision costs $43K in 2021 dollars\n>> getting past this point is going to take quite a large multiple of\n>> $43K.\n>\n> There are easier attacks than that if you can hide arbitrary bytes\n> inside a file. It's hard with C source code. The common one in hash\n> collision detection circles is to put invisible cruft into binary\n> document formats like PDF or Postscript. Git blobs themselves do not\n> have such an invisible place to put it, but you might be storing a\n> format that does.\n>\n> But worse, git _commits_ have such an invisible portion. We calculate\n> the sha1 over the full commit, but we tend to show only the portion up\n> to the first NUL byte. I used that horrible trick in my \"choose your own\n> sha1 prefix\" patch. However, we could mitigate that by checking for\n> embedded NULs in git-fsck.\n>\n>> 3. Somehow inject the new evil object into your repository, or\n>> convince you to re-clone it / clone it from somewhere you usually\n>> wouldn't.\n>\n> Yeah, this part is the kicker. With the commit NUL trick, you would make\n> a useful commit and then ask somebody to pull it, and then later replace\n> it with a commit pointing to an arbitrary tree. But if we assume we can\n> detect that easily (which I think we can), we are left with replacing\n> binary blobs that have hidden bits. And most projects do not take many\n> such blobs, and the result is that you could only replace the contents\n> of that particular blob, not an arbitrary part of the tree.\n>\n>> It would be very interesting to see an analysis that deals with some\n>> actual Git-related security scenarios, instead of something that just\n>> assumes that if someone finds *any* SHA1 collision the sky is going to\n>> fall.\n>\n> I agree that most of the analysis is overblown. Having read the analysis\n> Schneier pointed to, it actually is not that bad. We have 5-10 years to\n> get to a point where it's really expensive and extremely complex to\n> mount a single attack.\n>\n> That doesn't seem like an emergency to me. It sounds like something we\n> should be thinking about (and we are). The simplest thing would be to\n> wait for a moment when it makes sense to break compatibility (e.g., we\n> decide that \"git 2.0\" is here, and everybody will have to rewrite to\n> take advantage of new features, so we can jump to sha-2). We can also\n> start building sha-2 history that references sha-1 history. That would\n> mean everybody needs to upgrade their git, but that is not a problem\n> that requires 5-10 years of foresight and planning.\n>\n> -Peff\n>\n\n-- \nInviato dal mio dispositivo mobile\n"},{"id":"201284","messageId":"20121015191414.GA6779@sigill.intra.peff.net","threadId":"31826","inReplyTo":"CA+EOSBki6-PWu=mwxr3PU0XC15cBhqr7L5Ay7-e9on+jGumsxw@mail.gmail.com","subject":"Re: When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-15T19:14:14Z","receivedAt":"2012-10-15T19:14:14Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Oct 15, 2012 at 09:09:44PM +0200, Elia Pinto wrote:\n\n> Hem , sha-3 i suppose, keccak, no ? But really is not so urgent as you\n> have already told .\n\nIt depends. Read what Schneier wrote right before they announced the\nSHA-3 winner:\n\n https://www.schneier.com/crypto-gram-1210.html#2\n\nThere's really no security reason not to use SHA-2, and in fact it's\nprobably better, as it has been more widely studied at this point. But\nthat part is easy; it's the compatibility switch-over that's hard (we\ncould also even parameterize the hash, but that has some annoyances,\ntoo).\n\n-Peff\n"},{"id":"201323","messageId":"507D4651.6080207@lsrfire.ath.cx","threadId":"31826","inReplyTo":"20121015183438.GB31658@sigill.intra.peff.net","subject":"Re: When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2012-10-16T11:34:41Z","receivedAt":"2012-10-16T11:34:41Z","isPatch":false,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 15.10.2012 20:34, schrieb Jeff King:\n> On Mon, Oct 15, 2012 at 07:47:09PM +0200, Ævar Arnfjörð Bjarmason wrote:\n> \n>> On Mon, Oct 15, 2012 at 6:42 PM, Elia Pinto wrote:\n>>> Very clear analysis. Well written. Perhaps is it the time to update\n>>> http://git-scm.com/book/ch6-1.html (A SHORT NOTE ABOUT SHA-1) ?\n>>>\n>>> Hope useful\n>>>\n>>> http://www.schneier.com/crypto-gram-1210.html\n>>\n>> This would be concerning if the Git security model would break down if\n>> someone found a SHA1 collision, but it really wouldn't.\n>>\n>> It's one thing to find *a* collision, it's quite another to:\n>>\n>> 1. Find a collision for the sha1 of harmless.c which I know you use,\n>> and replace it with evil.c.\n>>\n>> 2. Somehow make evil.c compile so that it actually does something\n>> useful and nefarious, and doesn't just make the C compiler puke.\n>>\n>> If finding one arbitrary collision costs $43K in 2021 dollars\n>> getting past this point is going to take quite a large multiple of\n>> $43K.\n> \n> There are easier attacks than that if you can hide arbitrary bytes\n> inside a file. It's hard with C source code. The common one in hash\n> collision detection circles is to put invisible cruft into binary\n> document formats like PDF or Postscript. Git blobs themselves do not\n> have such an invisible place to put it, but you might be storing a\n> format that does.\n> \n> But worse, git _commits_ have such an invisible portion. We calculate\n> the sha1 over the full commit, but we tend to show only the portion up\n> to the first NUL byte. I used that horrible trick in my \"choose your own\n> sha1 prefix\" patch. However, we could mitigate that by checking for\n> embedded NULs in git-fsck.\n\nFWIW, I couldn't measure a performance difference for git log with and\nwithout the following patch, which catches commits created with your\nhash collision trick, but might be too strict:\n\ndiff --git a/commit.c b/commit.c\nindex 213bc98..4cd1e83 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -262,6 +262,12 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s\n \tif (item->object.parsed)\n \t\treturn 0;\n \titem->object.parsed = 1;\n+\n+\tif (memchr(buffer, '\\0', size)) {\n+\t\treturn error(\"bogus commit contains a NUL character: %s\",\n+\t\t\t sha1_to_hex(item->object.sha1));\n+\t}\n+\n \ttail += size;\n \tif (tail <= bufptr + 46 || memcmp(bufptr, \"tree \", 5) || bufptr[45] != '\\n')\n \t\treturn error(\"bogus commit object %s\", sha1_to_hex(item->object.sha1));\n"},{"id":"201372","messageId":"20121016173254.GD27243@sigill.intra.peff.net","threadId":"31826","inReplyTo":"507D4651.6080207@lsrfire.ath.cx","subject":"Re: When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-16T17:32:54Z","receivedAt":"2012-10-16T17:32:54Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Oct 16, 2012 at 01:34:41PM +0200, René Scharfe wrote:\n\n> FWIW, I couldn't measure a performance difference for git log with and\n> without the following patch, which catches commits created with your\n> hash collision trick, but might be too strict:\n> \n> diff --git a/commit.c b/commit.c\n> index 213bc98..4cd1e83 100644\n> --- a/commit.c\n> +++ b/commit.c\n> @@ -262,6 +262,12 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s\n> \tif (item->object.parsed)\n> \t\treturn 0;\n> \titem->object.parsed = 1;\n> +\n> +\tif (memchr(buffer, '\\0', size)) {\n> +\t\treturn error(\"bogus commit contains a NUL character: %s\",\n> +\t\t\t sha1_to_hex(item->object.sha1));\n> +\t}\n> +\n\nHmm. Yeah, that should be relatively inexpensive, since we are about to\nread through most of the bytes anyway (we probably have just zlib\ninflated them all, so they would even be in cache). It might make more\nof a difference for a raw traversal that is not even going to look at\nbelow the header, like rev-list or merge-base. But I couldn't measure a\ndifference doing \"git rev-list HEAD >/dev/null\" in either git.git or\nlinux-2.6.git.\n\nSo maybe it is worth doing preemptively. Even without security concerns,\nwe would be truncating the commit message, so it is probably better to\nlet the user know (a warning is probably more appropriate, though, just\nin case somebody does have embedded NULs for historical reason).\n\n-Peff\n"},{"id":"201374","messageId":"20121016175806.GB26650@thunk.org","threadId":"31826","inReplyTo":"20121016173254.GD27243@sigill.intra.peff.net","subject":"Re: When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)","fromName":"Theodore Ts'o","fromEmail":"tytso@mit.edu","sentAt":"2012-10-16T17:58:06Z","receivedAt":"2012-10-16T17:58:06Z","isPatch":false,"sender":{"key":"tytso@mit.edu","avatar":"https://avatars.githubusercontent.com/u/51416?v=4"},"body":"I seem to recall that there was at least some discussion at one point\nabout adding some extra fields to the commit object in a backwards\ncompatible way by adding it after the trailing NUL. We didn't end up\ndoing it, but I could see it being a useful thing nonetheless (for\nexample, we could potentially put the backup SHA-2/SHA-3 pointer there).\n\nWhat if we explicitly allow a length plus SHA-2/3 hash of the commit\nplus the fields after the SHA-2/3 hash as an extension? This would\nallow a secure way of adding an extension, including perhaps adding\nbackup SHA-2/3 parent pointers, which is something that would be\nuseful to do from a security perspective if we really are worried\nabout a catastrophic hash failure.\n\nThe one reason why we *might* want to use SHA-3, BTW, is that it is a\nradically different design from SHA-1 and SHA-2. And if there is a\ncrypto hash failure which is bad enough that the security of git would\nbe affected, there's a chance that the same attack could significantly\naffect SHA-2 as well. The fact that SHA-3 is fundamentally different\nfrom a cryptographic design perspective means that an attack that\nimpacts SHA-1/SHA-2 will not likely impact SHA-3, and vice versa.\n\n\t\t \t \t \t - Ted\n"},{"id":"201375","messageId":"20121016182751.GA30010@sigill.intra.peff.net","threadId":"31826","inReplyTo":"20121016175806.GB26650@thunk.org","subject":"Re: When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-16T18:27:51Z","receivedAt":"2012-10-16T18:27:51Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Oct 16, 2012 at 01:58:06PM -0400, Theodore Ts'o wrote:\n\n> I seem to recall that there was at least some discussion at one point\n> about adding some extra fields to the commit object in a backwards\n> compatible way by adding it after the trailing NUL. We didn't end up\n> doing it, but I could see it being a useful thing nonetheless (for\n> example, we could potentially put the backup SHA-2/SHA-3 pointer there).\n\nI don't see much point in it. If we want to add new backup pointers to\ncommit objects, it is very easy to do so by adding new header fields.\n\nA much bigger problem is the other places we reference sha1s. The\nobvious place is trees, which have no room for backup pointers (either\nin headers, or with a NUL trick). But it also means that any time you\nhave a sha1 that you arrive at in some other way than traversal from a\nsignature, you are vulnerable to attack. E.g., if I record a sha1 in an\nexternal system, today I can be sure that when I fetch the object for\nthat sha1, it is valid (or I can check that it is valid by hashing it).\nWith sha1 collisions, I am vulnerable to attack.\n\n> What if we explicitly allow a length plus SHA-2/3 hash of the commit\n> plus the fields after the SHA-2/3 hash as an extension? This would\n> allow a secure way of adding an extension, including perhaps adding\n> backup SHA-2/3 parent pointers, which is something that would be\n> useful to do from a security perspective if we really are worried\n> about a catastrophic hash failure.\n\nI'm not sure exactly what you mean. Extended parent pointers make sense,\nbut I don't see what you mean in your first sentence. It sounds like we\nare SHA-2/3 hashing something internal to the object, but that doesn't\nhelp. If the pointers are sha1, then I can always replace the whole\nobject with a colliding one, even if that object is internally\nconsistent with respect to sha-2.\n\n> The one reason why we *might* want to use SHA-3, BTW, is that it is a\n> radically different design from SHA-1 and SHA-2. And if there is a\n> crypto hash failure which is bad enough that the security of git would\n> be affected, there's a chance that the same attack could significantly\n> affect SHA-2 as well. The fact that SHA-3 is fundamentally different\n> from a cryptographic design perspective means that an attack that\n> impacts SHA-1/SHA-2 will not likely impact SHA-3, and vice versa.\n\nRight. The point of having the SHA-3 contest was that we thought SHA-1's\nbreakage meant that SHA-2 was going to fall next. But Schneier's\ncomments before the winners were announced were basically \"it turns out\nthat SHA-2 is not broken like we thought, so there's no reason to ditch\nit, and the fact that it is well-studied and well-deployed may mean it's\na good choice\".\n\nSo I could go either way. This is not a decision we should make today,\nthough, so we can wait and see which direction the world goes before\npicking an algorithm.\n\n-Peff\n"},{"id":"201378","messageId":"alpine.DEB.2.02.1210161131100.13407@asgard.lang.hm","threadId":"31826","inReplyTo":"20121016182751.GA30010@sigill.intra.peff.net","subject":"Re: When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)","fromName":"","fromEmail":"david@lang.hm","sentAt":"2012-10-16T18:32:38Z","receivedAt":"2012-10-16T18:32:38Z","isPatch":false,"sender":{"key":"david@lang.hm","avatar":null},"body":"On Tue, 16 Oct 2012, Jeff King wrote:\n\n> On Tue, Oct 16, 2012 at 01:58:06PM -0400, Theodore Ts'o wrote:\n>\n>> I seem to recall that there was at least some discussion at one point\n>> about adding some extra fields to the commit object in a backwards\n>> compatible way by adding it after the trailing NUL. We didn't end up\n>> doing it, but I could see it being a useful thing nonetheless (for\n>> example, we could potentially put the backup SHA-2/SHA-3 pointer there).\n>\n> I don't see much point in it. If we want to add new backup pointers to\n> commit objects, it is very easy to do so by adding new header fields.\n>\n> A much bigger problem is the other places we reference sha1s. The\n> obvious place is trees, which have no room for backup pointers (either\n> in headers, or with a NUL trick). But it also means that any time you\n> have a sha1 that you arrive at in some other way than traversal from a\n> signature, you are vulnerable to attack. E.g., if I record a sha1 in an\n> external system, today I can be sure that when I fetch the object for\n> that sha1, it is valid (or I can check that it is valid by hashing it).\n> With sha1 collisions, I am vulnerable to attack.\n\nIf you have two hashes of the same contents (SHA1 and SHA3) and they both \nagree that the file has not been tampered with, you should still be in \ngood shape just using the SHA1 as a reference.\n\nDavid Lang\n"},{"id":"201379","messageId":"20121016185430.GF27243@sigill.intra.peff.net","threadId":"31826","inReplyTo":"alpine.DEB.2.02.1210161131100.13407@asgard.lang.hm","subject":"Re: When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-16T18:54:30Z","receivedAt":"2012-10-16T18:54:30Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Oct 16, 2012 at 11:32:38AM -0700, david@lang.hm wrote:\n\n> >I don't see much point in it. If we want to add new backup pointers to\n> >commit objects, it is very easy to do so by adding new header fields.\n> >\n> >A much bigger problem is the other places we reference sha1s. The\n> >obvious place is trees, which have no room for backup pointers (either\n> >in headers, or with a NUL trick). But it also means that any time you\n> >have a sha1 that you arrive at in some other way than traversal from a\n> >signature, you are vulnerable to attack. E.g., if I record a sha1 in an\n> >external system, today I can be sure that when I fetch the object for\n> >that sha1, it is valid (or I can check that it is valid by hashing it).\n> >With sha1 collisions, I am vulnerable to attack.\n> \n> If you have two hashes of the same contents (SHA1 and SHA3) and they\n> both agree that the file has not been tampered with, you should still\n> be in good shape just using the SHA1 as a reference.\n\nBut tampering is only part of it. We care about a chain of authenticity\nfrom some known point (either a gpg signature, or a sha1 that you know\nto be good because you recorded it from a trusted source). The\nreferences between objects are the links in that chain.\n\nWhether an internal hash would help you would depend on the exact\ndetails of the collision attack. Let's imagine you have a signed tag\nthat points to commit sha1 X. The pointed-to commit contains a trailer\nthat says \"btw, my sha-3 is Y\". An attacker doing a brute-force birthday\nattack would do:\n\n 1. Generate some potential contents for the object (generally, take a good\n and malicious version of the object, and add some random bits at\n the end).\n\n 2. Generate the sha-3 trailer for each object and tack it on.\n\n 3. Generate the sha1 for object+trailer.\n\n 4. Remember the sha1 and contents of each object. If the sha1 matches\n something we generated before, we have a collision. Otherwise, goto\n step 1.\n\nSo each object, good or malicious, remains consistent with respect to\nthe sha-3 hash. We know it has not been tampered with since its\ngeneration, but do we not know if it is the same object that the tagger\noriginally referenced. We had to compute the sha-3 as part of\ngenerating the object, but it was not actually part of the collision\nattack; it just makes it a little more expensive to compute each\niteration. We still have to do only 2^80 iterations.\n\nBut nobody is worried about this 2^80 brute force attack. The problem\nwith sha-1 (as I understand it) is that there are tricks you can do when\nmaking the modifications in step 1 that will make the sha1 from step 3\nmore likely to find a collision with something you've already generated.\nThe modifications you make in step 1 will affect the sha-3 hash in step\n2, which ultimately impacts the sha1 hash in step 3. Whether and how\nthat affects your attack would depend on the exact details of the\ntricks.\n\nI don't keep up on the state of the art in sha-1 cracking, so maybe the\ntechniques happen in such a way that the extra hash would be a\nsignificant impediment. Even if it is sufficient to stop current (or\nwhatever is \"current\" when sha1 is broken enough to worry about)\nattacks, it is a weak point for future attacks.\n\n-Peff\n"},{"id":"201387","messageId":"7v391erxgc.fsf@alter.siamese.dyndns.org","threadId":"31826","inReplyTo":"20121016182751.GA30010@sigill.intra.peff.net","subject":"Re: When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-10-16T20:09:07Z","receivedAt":"2012-10-16T20:09:07Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> A much bigger problem is the other places we reference sha1s. The\n> obvious place is trees, which have no room for backup pointers (either\n> in headers, or with a NUL trick).\n\nThis is a tangent (as I do not have anything particularly worth\nadding on top of what have already been said around the exact\nSHA-[123] topic), but we probably would want to start thinking about\nthe tree object format \"v2\" at some point.\n\nSome random thoughts:\n\n - It is OK if existing versions of Git barfed when asked to read a\n tree object in the \"v2\" format. The repository format version\n may need to be bumped up when writing such an object, and\n transfer protocols need to pay attention to it, to avoid\n transferring history with objects in newer representation to\n repositories with older repository format version.\n\n - We do not need a new \"tree v2\" object type. Existing versions of\n Git will barf upon seeing such an object, but that won't be the\n only way to prevent existing versions of Git from misinterpreting\n a tree object recorded in the \"v2\" format as if it were in the\n current format (e.g. a non-octal in the mode field of the first\n entry causes tree-walk.c::get_mode() to barf).\n\n - We do not mind two tree objects that encodes the same tree in the\n current and the enhanced formats to have different object names.\n In fact, we care more about the object names derived purely from\n the content of the object as an uninterpreted bytestream, so it\n is expected that they have different object names.\n\n This will make the path-limited traversal and diff to open more\n trees unnecessarily at the \"version bump\" boundary in the\n history, but that is normal (think of a project that used to\n record its text files with CRLF and one day decides to convert\n everything to LF; the trees before and after the conversion will\n record logically the same contents \"git show\" should give an\n emptyness, but the diff machinery needs to go into contents at\n the flag day boundary).\n\n As long as we do not let random \"extension of the day\" into the\n new format willy-nilly, the resulting history will still be\n useful and usable. From that point of view, no parts of the\n additional information we would record in the updated format that\n is not present in the current format should be optional (iow,\n once you decide to use the \"v2\" format to record a certain tree,\n you will produce an identical and reproducible representation in\n \"v2\", regardless of your implementation).\n\nAll of the above are issues for Git 3.0 and beyond, though ;-).\n"},{"id":"201413","messageId":"20121017080530.GA6676@savin","threadId":"31826","inReplyTo":"20121016182751.GA30010@sigill.intra.peff.net","subject":"Re: When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)","fromName":"Peter Todd","fromEmail":"pete@petertodd.org","sentAt":"2012-10-17T08:05:30Z","receivedAt":"2012-10-17T08:05:30Z","isPatch":false,"sender":{"key":"pete@petertodd.org","avatar":null},"body":"On Tue, Oct 16, 2012 at 02:27:51PM -0400, Jeff King wrote:\n> > The one reason why we *might* want to use SHA-3, BTW, is that it is a\n> > radically different design from SHA-1 and SHA-2. And if there is a\n> > crypto hash failure which is bad enough that the security of git would\n> > be affected, there's a chance that the same attack could significantly\n> > affect SHA-2 as well. The fact that SHA-3 is fundamentally different\n> > from a cryptographic design perspective means that an attack that\n> > impacts SHA-1/SHA-2 will not likely impact SHA-3, and vice versa.\n> \n> Right. The point of having the SHA-3 contest was that we thought SHA-1's\n> breakage meant that SHA-2 was going to fall next. But Schneier's\n> comments before the winners were announced were basically \"it turns out\n> that SHA-2 is not broken like we thought, so there's no reason to ditch\n> it, and the fact that it is well-studied and well-deployed may mean it's\n> a good choice\".\n> \n> So I could go either way. This is not a decision we should make today,\n> though, so we can wait and see which direction the world goes before\n> picking an algorithm.\n\nDo you really need to pick an algorithm and go through a full-on flag\nday ten years down the road all over again? People don't really care\nthat a git revision is actually the hex-encoded SHA1 hash of a tree.\nThey just know it's this long string of \"stuff\" that uniquely identifies\na revison globally somehow. They know if they copy and paste the first\nfew characters of the string there is a small chance two revisions will\nhave the same first few characters, and if they copy and paste the whole\nstring the chance drops to \"you're whole dev team will be eaten by\nwolves in tragic unrelated incidences\" unlikely.\n\nSo why bake in a single algorithm? We'll have to extend the length of a\nwhole revision string anyway - the alternatives start at 256bits - and\npeople are going to want to be able to specify the whole revision string\nat least sometimes. Once you've gone through that pain, why have to\nrepeat it again in ten years?\n\n\nLet's make revisions be a long but variable length string. A revision by\nitself is meaningless of course. However if if you know of a repo that\ncontains that revision, you can convert it into something useful, like a\ncommit and associated tree. If you don't know, well, you'd be stuck\nanyway right now. \n\nNow when you push and pull from a remote repo what'll happen is the repo\nwill figure out what type(s) of hash algorithm your client supports. A\nGit 3000 user with a repo using SHA3072 can talk to a v0.1 client just\nfine: they send the v0.1 client revisions calculated with an algorithm\nthey support, and when they pull revisions from that repo they calculate\nnew revisions with their preferred algorithm. If they want to do this a\nlot, they maintain the two sets of digest tables next to each other,\nwith the SHA3072 table marked as preferred, and the rest kept only so\npushes and pulls can be fast. In most cases a project will convert to\none hash algorithm, but by having multi-hash support that conversion\ndoesn't have to be a flag day, and at the same time it's still easy to\nlookup old revisions by their old digests. Meanwhile the crypto-wonks\nget to have their fun PGP signing and timestamping long, secure digests.\n\nNote that we don't even have to shut out non-upgraded users from\nparticipating. Machine-to-machine communication is not a problem as\noutlined above, but even with stuff like mailing lists we can start\npassing around concatenated revisions like the following: \n\nda39a3ee5e6b4b0d3255bfef95601890afd80709.e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855\n\nOld users just use the first bit. (the period isn't even required\nreally) If you think that's too long, there's a simple solution that\nkeeps -bit security, albeit one whose implications\nlead you right to Linus's lines of thinking:\n\nda39a3ee5e6b4b0d3255bfef95601890afd80709\n\nThat's just a SHA1 again. Of course, if you actually care about this\nstuff you already have cryptographic infrastructure, and that\ninfrastructure can simply store *trusted* metadata in you're repos\nsaying that the string 'foo' happens to be a valid alias for the actual\ndigest that *the user* can specify instead of that digest. It may even\nbe that for your security needs just timestamping those aliases is\nenough. Either way while something needs to be calculating secure\nhashes, and preferably Git mainline so push and pull works without\nhaving to examine every last line of code, you can get away without\nchanging the UI very much.\n\n\nAnyway, in the short term the people who care can write parallel digest\ncalculators; I personally have a use-case for one right now. Better code\nto handle the cases where individual blobs have colliding hashes is\nrequired as well in the medium term. Finally those who require it could\nvery well write parallel git's to effectively do the pulling and pushing\nof their parallel calculated revision hashes if they really wanted too.\n\nBut if this problem gets to the point where git-core has to change the\nreality is organizations are not going to be happy if it has to be a big\nflag day. Git v2/v3 interoperability *will* be implemented. Once we're\nat that point, let's make sure Git 5.0's big feature isn't SHA5000. \n\n-- \n'peter'[:-1]@petertodd.org\n"}]}