{"thread":{"id":"47","subject":"SHA1 hash safety","startedAt":"2005-04-16T12:24:24Z","lastAt":"2005-04-20T18:56:53Z","messageCount":30,"participants":["David Lang","Ingo Molnar","Brian O'Mahoney","C. Scott Ananian","Petr Baudis","ross@lug.udel.edu","Paul Jackson","Martin Mares","Tkil","David A. Wheeler","Horst von Brand","Theodore Ts'o","Andy Isaacson","David Meybohm"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"295","messageId":"Pine.LNX.4.62.0504160519330.21837@qynat.qvtvafvgr.pbz","threadId":"47","inReplyTo":null,"subject":"SHA1 hash safety","fromName":"David Lang","fromEmail":"david.lang@digitalinsight.com","sentAt":"2005-04-16T12:24:24Z","receivedAt":"2005-04-16T12:24:24Z","isPatch":false,"sender":{"key":"david.lang@digitalinsight.com","avatar":null},"body":"this issue was raised a few days ago in the context of someone tampering \nwith the files and it was decided that the extra checks were good enough \nto prevent this (at least for now), but what about accidental collisions?\n\nif I am understanding things right the objects get saved in the filesystem \nin filenames that are the SHA1 hash. of two legitimate files have the same \nhash I don't see any way for both of them to exist.\n\nyes the risk of any two files having the same has is low, but in the \nearlier thread someone chimed in and said that they had two files on their \nsystem that had the same hash..\n\nDavid Lang\n\n-- \nThere are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.\n -- C.A.R. Hoare\n"},{"id":"297","messageId":"20050416123155.GA19908@elte.hu","threadId":"47","inReplyTo":"Pine.LNX.4.62.0504160519330.21837@qynat.qvtvafvgr.pbz","subject":"Re: SHA1 hash safety","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2005-04-16T12:31:55Z","receivedAt":"2005-04-16T12:31:55Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* David Lang wrote:\n\n> this issue was raised a few days ago in the context of someone \n> tampering with the files and it was decided that the extra checks were \n> good enough to prevent this (at least for now), but what about \n> accidental collisions?\n> \n> if I am understanding things right the objects get saved in the \n> filesystem in filenames that are the SHA1 hash. of two legitimate \n> files have the same hash I don't see any way for both of them to \n> exist.\n> \n> yes the risk of any two files having the same has is low, but in the \n> earlier thread someone chimed in and said that they had two files on \n> their system that had the same hash..\n\nyou can add -DCOLLISION_CHECK to Makefile:CFLAGS to turn on collision \nchecking (disabled currently). If there indeed exist two files that have \ndifferent content but the same hash, could someone send those two files?\n\n\tIngo\n"},{"id":"298","messageId":"Pine.LNX.4.62.0504160542190.21837@qynat.qvtvafvgr.pbz","threadId":"47","inReplyTo":"20050416123155.GA19908@elte.hu","subject":"Re: SHA1 hash safety","fromName":"David Lang","fromEmail":"david.lang@digitalinsight.com","sentAt":"2005-04-16T12:48:32Z","receivedAt":"2005-04-16T12:48:32Z","isPatch":false,"sender":{"key":"david.lang@digitalinsight.com","avatar":null},"body":"On Sat, 16 Apr 2005, Ingo Molnar wrote:\n\n> * David Lang wrote:\n>\n>> this issue was raised a few days ago in the context of someone\n>> tampering with the files and it was decided that the extra checks were\n>> good enough to prevent this (at least for now), but what about\n>> accidental collisions?\n>>\n>> if I am understanding things right the objects get saved in the\n>> filesystem in filenames that are the SHA1 hash. of two legitimate\n>> files have the same hash I don't see any way for both of them to\n>> exist.\n>>\n>> yes the risk of any two files having the same has is low, but in the\n>> earlier thread someone chimed in and said that they had two files on\n>> their system that had the same hash..\n>\n> you can add -DCOLLISION_CHECK to Makefile:CFLAGS to turn on collision\n> checking (disabled currently). If there indeed exist two files that have\n> different content but the same hash, could someone send those two files?\n\nremember that the flap over SHA1 being 'broken' a couple weeks ago was not \nfrom researchers finding multiple files with the same hash, but finding \nthat it was more likly then expected that files would have the same hash.\n\nthere was qa discussion on LKML within the last year about useing MD5 \nhashes for identifying unique filesystem blocks (with the idea of being \nable to merge identical blocks) and in that discussion it was pointed out \nthat collisions are a known real-life issue.\n\nso if collision detection is turned on in git, does that make it error out \nif it runs into a second file with the same hash, or does it do something \nelse?\n\nDavid Lang\n\n-- \nThere are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.\n -- C.A.R. Hoare\n"},{"id":"301","messageId":"4261132A.3090907@khandalf.com","threadId":"47","inReplyTo":"Pine.LNX.4.62.0504160542190.21837@qynat.qvtvafvgr.pbz","subject":"Re: SHA1 hash safety","fromName":"Brian O'Mahoney","fromEmail":"omb@khandalf.com","sentAt":"2005-04-16T13:29:14Z","receivedAt":"2005-04-16T13:29:14Z","isPatch":false,"sender":{"key":"omb@khandalf.com","avatar":null},"body":"Three points:\n(1) I _have_ seen real-life collisions with MD5, in the context of\n Document management systems containing ~10^6 ms-WORD documents.\n(2) The HMAC (ethernet-harware-address) of any interface _should_\n help to make a unique Id.\n(3) While I havn't looked at the details of the plumbing, this is\n the time to make sure we can, easily, drop in SHA-160, SHA-256\n (or whatever comes from NIST) when needed.\n\n\nDavid Lang wrote:\n> On Sat, 16 Apr 2005, Ingo Molnar wrote:\n> \n>> * David Lang wrote:\n>>\n>>> this issue was raised a few days ago in the context of someone\n>>> tampering with the files and it was decided that the extra checks were\n>>> good enough to prevent this (at least for now), but what about\n>>> accidental collisions?\n>>>\n>>> if I am understanding things right the objects get saved in the\n>>> filesystem in filenames that are the SHA1 hash. of two legitimate\n>>> files have the same hash I don't see any way for both of them to\n>>> exist.\n>>>\n>>> yes the risk of any two files having the same has is low, but in the\n>>> earlier thread someone chimed in and said that they had two files on\n>>> their system that had the same hash..\n>>\n>>\n>> you can add -DCOLLISION_CHECK to Makefile:CFLAGS to turn on collision\n>> checking (disabled currently). If there indeed exist two files that have\n>> different content but the same hash, could someone send those two files?\n> \n> \n> remember that the flap over SHA1 being 'broken' a couple weeks ago was\n> not from researchers finding multiple files with the same hash, but\n> finding that it was more likly then expected that files would have the\n> same hash.\n> \n> there was qa discussion on LKML within the last year about useing MD5\n> hashes for identifying unique filesystem blocks (with the idea of being\n> able to merge identical blocks) and in that discussion it was pointed\n> out that collisions are a known real-life issue.\n> \n> so if collision detection is turned on in git, does that make it error\n> out if it runs into a second file with the same hash, or does it do\n> something else?\n> \n> David Lang\n> \n\n-- \nBrian\n"},{"id":"311","messageId":"Pine.LNX.4.61.0504161040310.29343@cag.csail.mit.edu","threadId":"47","inReplyTo":"4261132A.3090907@khandalf.com","subject":"Re: SHA1 hash safety","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-16T14:58:15Z","receivedAt":"2005-04-16T14:58:15Z","isPatch":false,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Sat, 16 Apr 2005, Brian O'Mahoney wrote:\n\n> (1) I _have_ seen real-life collisions with MD5, in the context of\n> Document management systems containing ~10^6 ms-WORD documents.\n\nDude! You could have been *famous*! Why the \naitch-ee-double-hockey-sticks didn't you publish this when you found it?\nSeriously, man.\n\nEven given the known weaknesses in MD5, it would take much more than a \nmillion documents to find MD5 collisions. I can only conclude that the \nhash was being used incorrectly; most likely truncated (my wild-ass guess \nwould be to 32 bits; a collision is likely with > 50% probability in a \nmillion document store for a hash of less than 40 bits).\n\nI know the current state of the art here. It's going to take more than \njust hearsay to convince me that full 128-bit MD5 collisions are likely. \nI believe there are only two or so known to exist so far, and those were \nfound by a research team in China (which, yes, is fairly famous among the \ncryptographic community now after publishing a paper consisting of little \napart from the two collisions themselves).\n\nPlease, let's talk about hash collisions responsibly. I posted earlier \nabout the *actual computed probability* of finding two files with an SHA-1 \ncollision before the sun goes supernova. It's 10^28 to 1 against.\nThe recent cryptographic works has shown that there are certain situations \nwhere a decent amount of computer work (2^69 operations) can produce two \nsequences with the same hash, but these sequences are not freely chosen; \nthey've got very specific structure. This attack does not apply to \n(effectively) random files sitting in a SCM.\n http://www.schneier.com/blog/archives/2005/02/sha1_broken.html\n\nThat said, Linux's widespread use means that it may not be unimaginable \nfor an attacker to devote this amount of resources to an attack, which \nwould probably involve first committing some specially structured file to \nthe SCM (but would Linus accept it?) and then silently corrupting said \nfile via a SHA1 collision to toggle some bits (which would presumably Do \nEvil). Thus hashes other than SHA1 really ought to be considered...\n\n...but the cryptographic community has not yet come to a conclusion on \nwhat the replacement ought to be. These attacks are so new that we don't \nreally understand what it is about the structure of SHA1 which makes them \npossible, which makes it hard to determine which other hashes are \nsimilarly vulnerable. It will take time.\n\nI believe Linus has already stated on this list that his plan is to \neventually provide a tool for bulk migration of an existing SHA1 git \nrepository to a new hash type. Basically munging through the repository \nin bulk, replacing all the hashes. This seems a perfectly adequate \nstrategy at the moment.\n --scott\n\nWASHTUB Panama Minister Moscow explosives KUGOWN hack Marxist LPMEDLEY \ngenetic immediate radar SCRANTON COBRA JANE KGB Shoal Bay atomic Bejing\n ( http://cscott.net/ )\n"},{"id":"314","messageId":"20050416151116.GC19099@pasky.ji.cz","threadId":"47","inReplyTo":"Pine.LNX.4.61.0504161040310.29343@cag.csail.mit.edu","subject":"Re: Re: SHA1 hash safety","fromName":"Petr Baudis","fromEmail":"pasky@ucw.cz","sentAt":"2005-04-16T15:11:17Z","receivedAt":"2005-04-16T15:11:17Z","isPatch":false,"sender":{"key":"pasky@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/18439?v=4"},"body":"Dear diary, on Sat, Apr 16, 2005 at 04:58:15PM CEST, I got a letter\nwhere \"C. Scott Ananian\" told me that...\n> On Sat, 16 Apr 2005, Brian O'Mahoney wrote:\n> \n> >(1) I _have_ seen real-life collisions with MD5, in the context of\n> > Document management systems containing ~10^6 ms-WORD documents.\n> \n> Dude! You could have been *famous*! Why the \n> aitch-ee-double-hockey-sticks didn't you publish this when you found it?\n> Seriously, man.\n> \n> Even given the known weaknesses in MD5, it would take much more than a \n> million documents to find MD5 collisions. I can only conclude that the \n> hash was being used incorrectly; most likely truncated (my wild-ass guess \n> would be to 32 bits; a collision is likely with > 50% probability in a \n> million document store for a hash of less than 40 bits).\n> \n> I know the current state of the art here. It's going to take more than \n> just hearsay to convince me that full 128-bit MD5 collisions are likely. \n> I believe there are only two or so known to exist so far, and those were \n> found by a research team in China (which, yes, is fairly famous among the \n> cryptographic community now after publishing a paper consisting of little \n> apart from the two collisions themselves).\n\nhttp://cryptography.hyperlink.cz/MD5_collisions.html\n\n-- \n\t\t\t\tPetr \"Pasky\" Baudis\nStuff: http://pasky.or.cz/\nC++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor\n"},{"id":"318","messageId":"Pine.LNX.4.61.0504161114530.29343@cag.csail.mit.edu","threadId":"47","inReplyTo":"20050416151116.GC19099@pasky.ji.cz","subject":"Re: Re: SHA1 hash safety","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-16T15:36:28Z","receivedAt":"2005-04-16T15:36:28Z","isPatch":false,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Sat, 16 Apr 2005, Petr Baudis wrote:\n\n>> I know the current state of the art here. It's going to take more than\n>> just hearsay to convince me that full 128-bit MD5 collisions are likely.\n>\n> http://cryptography.hyperlink.cz/MD5_collisions.html\n\nOK, OK, I spoke too sloppily. Let me rephrase:\n It's going to take more than just hearsay to convince me that full\n 128-bit MD5 collisions *IN ARBITRARILY CHOSEN DOCUMENTS* are likely.\n\nI could add, \"WITHOUT SPECIAL EFFORT BY AN ATTACKER\".\n\nBut you're right, I was too busy thrashing around with the basic \nprobability cluestick to carefully distinguish MD5 (in which *collisions* \ncan be found fairly easily now by an attacker, although not *preimages*) \nand SHA1 (which is what git is actually using, and still requires 2^69 \nhash computations to collide).\n\nAnd note again that these are not preimage attacks. Even with MD5, an \nattacker can't arbitrarily change existing code in the Linux kernel by \ncreating a malicious file with the same MD5 hash.\n\nBut extreme caution is necessary, because both of these hash mechanisms \nhave been shown to be weak, and algorithms grow weaker with time, not \nstronger.\n\nI think the only conclusion that can be made is that \"one should not rely \non the hash for security\". And I don't believe that we are. We should be\ncareful to continue saying \"branch 46f *in Linus' tree*\" instead \nof just \"branch 46f\" and assuming that that is unique. The \nsecurity is provided by Linus' control over his repository, not by the \nhash.\n --scott\n\n[The 'MD5 collisions in 15 minutes on a laptop' paper did surprise me. I \nvaguely remember hearing about this before, but I'd forgotten just how \nbroken MD5 is. It's still a fine *hash* function; just not a terribly \ngood *cryptographically secure* hash function.]\n\nIsrael PBSUCCESS $400 million in gold bullion President Nader jihad \nRNC LPMEDLEY agent HTKEEPER Cheney SEQUIN SARANAC Clinton biowarfare\n ( http://cscott.net/ )\n"},{"id":"319","messageId":"20050416154951.GB13373@jose.lug.udel.edu","threadId":"47","inReplyTo":"Pine.LNX.4.61.0504161040310.29343@cag.csail.mit.edu","subject":"Re: SHA1 hash safety","fromName":"","fromEmail":"ross@lug.udel.edu","sentAt":"2005-04-16T15:49:51Z","receivedAt":"2005-04-16T15:49:51Z","isPatch":false,"sender":{"key":"ross@lug.udel.edu","avatar":null},"body":"On Sat, Apr 16, 2005 at 10:58:15AM -0400, C. Scott Ananian wrote:\n> Even given the known weaknesses in MD5, it would take much more than a \n> million documents to find MD5 collisions. I can only conclude that the \n> hash was being used incorrectly; most likely truncated (my wild-ass guess \n> would be to 32 bits; a collision is likely with > 50% probability in a \n> million document store for a hash of less than 40 bits).\n\nI've also seen non thread-safe GUID generation, using MD5m hit collisions:\nbut of course that was due to the fact that the code had thread safety\nissues, not because anyone actually ever hit a MD5 collision...\n\nOf course there are constructed cases of MD5 collision, but those are\npretty disinteresting. Give me two files that have useful content and\nthe same hash, and then I'll be impressed.\n\nLinus has already weighed in that he doesn't give a crap. All the\ncrypto-babble about collision whitepapers is uninteresting without a\nrepo that has real collisions. git is far too cool as is - prove I\nshould be concerned.\n\n-- \nRoss Vandegrift\nross@lug.udel.edu\n\n\"The good Christian should beware of mathematicians, and all those who\nmake empty prophecies. The danger already exists that the mathematicians\nhave made a covenant with the devil to darken the spirit and to confine\nman in the bonds of Hell.\"\n\t--St. Augustine, De Genesi ad Litteram, Book II, xviii, 37\n"},{"id":"344","messageId":"20050416121652.1b1a8645.pj@sgi.com","threadId":"47","inReplyTo":"Pine.LNX.4.61.0504161040310.29343@cag.csail.mit.edu","subject":"Re: SHA1 hash safety","fromName":"Paul Jackson","fromEmail":"pj@sgi.com","sentAt":"2005-04-16T19:16:52Z","receivedAt":"2005-04-16T19:16:52Z","isPatch":false,"sender":{"key":"pj@sgi.com","avatar":null},"body":"Scott wrote:\n> Please, let's talk about hash collisions responsibly.\n\nAgreed.\n\nChasing down links from the one Petr provided:\n\n http://cryptography.hyperlink.cz/MD5_collisions.html\n\nthe best read I found was:\n\n MD5 To Be Considered Harmful Someday\n http://eprint.iacr.org/2004/357.pdf\n\nAs the author, Dan Kaminsky, states:\n\n> it is far too easy to overestimate the risks described in this paper.\n\nThis paper does a good job of explaining the vulnerabilities\nthat MD5 has, currently (and yes, git uses SHA1 ...).\n\nWe have far greater vulnerabilities from intentional or accidental\ncoding errors, inadequately audited code, root exploits of user\n(non-kernel) code, compilation and build tools, unreliable hardware\n(how many of us use non-ECC memory - I do), poorly administered\nsystems, ...\n\n-- \n I won't rest till it's the best ...\n Programmer, Linux Scalability\n Paul Jackson 1.650.933.1373, 1.925.600.0401\n"},{"id":"356","messageId":"4261852B.6090507@khandalf.com","threadId":"47","inReplyTo":"Pine.LNX.4.61.0504161040310.29343@cag.csail.mit.edu","subject":"Re: SHA1 hash safety","fromName":"Brian O'Mahoney","fromEmail":"omb@khandalf.com","sentAt":"2005-04-16T21:35:39Z","receivedAt":"2005-04-16T21:35:39Z","isPatch":false,"sender":{"key":"omb@khandalf.com","avatar":null},"body":"Please see below:\n\nC. Scott Ananian wrote:\n> On Sat, 16 Apr 2005, Brian O'Mahoney wrote:\n> \n>> (1) I _have_ seen real-life collisions with MD5, in the context of\n>> Document management systems containing ~10^6 ms-WORD documents.\n> \n> \n> Dude! You could have been *famous*! Why the\n> aitch-ee-double-hockey-sticks didn't you publish this when you found it?\n> Seriously, man.\n\nThe MD5 has was fine, or at least the code (a) produced the correct\nresults on the published test cases, and, (b) was properly applied to\nall bytes of the file(s). I was surprised when it happened, which is why\nI bothered to post to this list at this time, so I make two more points\n\n(1) These hashes were designed, to assist in the construction of digital\nsignatures, ie so it is hard to produce a document to hash to a known\nhash value, and that with a defined document format so they are designed\n(i) hash similar documents far apart, and (ii) be hard to reverse;\n\nit says nothing about naturally ocurring collisions, ie where the\ndocument is not constrained to be similar,\n\n> \n> Even given the known weaknesses in MD5, it would take much more than a\n> million documents to find MD5 collisions. I can only conclude that the\n> hash was being used incorrectly; most likely truncated (my wild-ass\n> guess would be to 32 bits; a collision is likely with > 50% probability\n> in a million document store for a hash of less than 40 bits).\n> \n> I know the current state of the art here. It's going to take more than\n> just hearsay to convince me that full 128-bit MD5 collisions are likely.\n> I believe there are only two or so known to exist so far, and those were\n> found by a research team in China (which, yes, is fairly famous among\n> the cryptographic community now after publishing a paper consisting of\n> little apart from the two collisions themselves).\n\n(2) I am not concerned with cryptography here, merely sound engineering\ntradeoffs and the avoidance of _pain_in_the_ass_ when we do see a\nrandom collision, [NB the 2^69 is to 'cause a collision in SHA1' not the\nodds against such a collision] ... (below)\n\n> \n> Please, let's talk about hash collisions responsibly. I posted earlier\n> about the *actual computed probability* of finding two files with an\n> SHA-1 collision before the sun goes supernova. It's 10^28 to 1 against.\n> The recent cryptographic works has shown that there are certain\n> situations where a decent amount of computer work (2^69 operations) can\n> produce two sequences with the same hash, but these sequences are not\n> freely chosen; they've got very specific structure. This attack does\n> not apply to (effectively) random files sitting in a SCM.\n> http://www.schneier.com/blog/archives/2005/02/sha1_broken.html\n> \n> That said, Linux's widespread use means that it may not be unimaginable\n> for an attacker to devote this amount of resources to an attack, which\n> would probably involve first committing some specially structured file\n> to the SCM (but would Linus accept it?) and then silently corrupting\n> said file via a SHA1 collision to toggle some bits (which would\n> presumably Do Evil). Thus hashes other than SHA1 really ought to be\n> considered...\n>\n> ..but the cryptographic community has not yet come to a conclusion on\n> what the replacement ought to be. These attacks are so new that we\n> don't really understand what it is about the structure of SHA1 which\n> makes them possible, which makes it hard to determine which other hashes\n> are similarly vulnerable. It will take time.\n> \n> I believe Linus has already stated on this list that his plan is to\n> eventually provide a tool for bulk migration of an existing SHA1 git\n> repository to a new hash type. Basically munging through the\n> repository in bulk, replacing all the hashes. This seems a perfectly\n> adequate strategy at the moment.\n\n... [I say again, the problem here is NOT forgery of hashes, though SCO\nlike paranoia ...] ... but the hashes are a tiny part of the total\nspace, even for trivial patches, so that, providing _NOW_ for a longer\nhash (and then why not use, say, SHA-256 for now as well) is prudent.\n\nWe do not want to revisit the plumbing, in the next 3-10 years, for 16\nbytes per hash.\n\nFinally I can do no more than quote Schneier:\n\n\"SHA-1 has been broken. Not a reduced-round version. Not a simplified\nversion. The real thing. ...\n\nIt's time for us all to migrate away from SHA-1.\n\nLuckily, there are alternatives. The National Institute of Standards and\nTechnology already has standards for longer -- and harder to break --\nhash functions: SHA-224, SHA-256, SHA-384, and SHA-512. They're already\ngovernment standards, and can already be used.\" and there are FOSS\nimplementations.\n\nOr, put more simply by Jon Callas, PGP's CTO: \"It's time to walk, but\nnot run, to the fire exits. You don't see smoke, but the fire alarms\nhave gone off.\" That's basically what he said last August [2004].\n\n> --scott\n> \n> WASHTUB Panama Minister Moscow explosives KUGOWN hack Marxist LPMEDLEY\n> genetic immediate radar SCRANTON COBRA JANE KGB Shoal Bay atomic Bejing\n> ( http://cscott.net/ )\n> -\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n> \n> \n> \n\n-- \nmit freundlichen Grüßen, Brian.\n\nDr. Brian O'Mahoney\nMobile +41 (0)79 334 8035 Email: omb@bluewin.ch\nBleicherstrasse 25, CH-8953 Dietikon, Switzerland\nPGP Key fingerprint = 33 41 A2 DE 35 7C CE 5D F5 14 39 C9 6D 38 56 D5\n"},{"id":"362","messageId":"Pine.LNX.4.62.0504161531370.22652@qynat.qvtvafvgr.pbz","threadId":"47","inReplyTo":"4261132A.3090907@khandalf.com","subject":"Re: SHA1 hash safety","fromName":"David Lang","fromEmail":"david.lang@digitalinsight.com","sentAt":"2005-04-16T22:33:06Z","receivedAt":"2005-04-16T22:33:06Z","isPatch":false,"sender":{"key":"david.lang@digitalinsight.com","avatar":null},"body":"On Sat, 16 Apr 2005, Brian O'Mahoney wrote:\n\n> Three points:\n> (1) I _have_ seen real-life collisions with MD5, in the context of\n> Document management systems containing ~10^6 ms-WORD documents.\n> (2) The HMAC (ethernet-harware-address) of any interface _should_\n> help to make a unique Id.\n\nyou want a unique ID that can be computed directly from the file contents.\n\nwhat file integrety programa (ala tripwire) do is to use multiple \nidentification routines (aide uses MD4+MD5+filesize IIRC)\n\n>\n> David Lang wrote:\n>> On Sat, 16 Apr 2005, Ingo Molnar wrote:\n>>\n>>> * David Lang wrote:\n>>>\n>>>> this issue was raised a few days ago in the context of someone\n>>>> tampering with the files and it was decided that the extra checks were\n>>>> good enough to prevent this (at least for now), but what about\n>>>> accidental collisions?\n>>>>\n>>>> if I am understanding things right the objects get saved in the\n>>>> filesystem in filenames that are the SHA1 hash. of two legitimate\n>>>> files have the same hash I don't see any way for both of them to\n>>>> exist.\n>>>>\n>>>> yes the risk of any two files having the same has is low, but in the\n>>>> earlier thread someone chimed in and said that they had two files on\n>>>> their system that had the same hash..\n>>>\n>>>\n>>> you can add -DCOLLISION_CHECK to Makefile:CFLAGS to turn on collision\n>>> checking (disabled currently). If there indeed exist two files that have\n>>> different content but the same hash, could someone send those two files?\n>>\n>>\n>> remember that the flap over SHA1 being 'broken' a couple weeks ago was\n>> not from researchers finding multiple files with the same hash, but\n>> finding that it was more likly then expected that files would have the\n>> same hash.\n>>\n>> there was qa discussion on LKML within the last year about useing MD5\n>> hashes for identifying unique filesystem blocks (with the idea of being\n>> able to merge identical blocks) and in that discussion it was pointed\n>> out that collisions are a known real-life issue.\n>>\n>> so if collision detection is turned on in git, does that make it error\n>> out if it runs into a second file with the same hash, or does it do\n>> something else?\n>>\n>> David Lang\n>>\n>\n> -- \n> Brian\n>\n\n-- \nThere are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.\n -- C.A.R. Hoare\n"},{"id":"368","messageId":"Pine.LNX.4.62.0504161543150.22652@qynat.qvtvafvgr.pbz","threadId":"47","inReplyTo":"Pine.LNX.4.61.0504161040310.29343@cag.csail.mit.edu","subject":"Re: SHA1 hash safety","fromName":"David Lang","fromEmail":"david.lang@digitalinsight.com","sentAt":"2005-04-16T22:46:13Z","receivedAt":"2005-04-16T22:46:13Z","isPatch":false,"sender":{"key":"david.lang@digitalinsight.com","avatar":null},"body":"that's the difference between CS researchers and sysadmins.\n\nsysadmins realize that there are an infinante number of files that map to \nthe same hash value and plan accordingly (becouse we KNOW we will run \nacross them eventually), and don't see it as a big deal when we finally \ndo.\n\nCS researches quote statistics that show how hard it is to intentiallly \ncreate two files with the same hash and insist it just doesn't happen \nuntil presented by the proof, at which point it is a big deal.\n\na difference in viewpoints.\n\nDavid Lang\n\n\n On Sat, 16 Apr 2005, C. Scott Ananian wrote:\n\n> Date: Sat, 16 Apr 2005 10:58:15 -0400 (EDT)\n> From: C. Scott Ananian \n> To: omb@bluewin.ch\n> Cc: David Lang , Ingo Molnar ,\n> git@vger.kernel.org\n> Subject: Re: SHA1 hash safety\n> \n> On Sat, 16 Apr 2005, Brian O'Mahoney wrote:\n>\n>> (1) I _have_ seen real-life collisions with MD5, in the context of\n>> Document management systems containing ~10^6 ms-WORD documents.\n>\n> Dude! You could have been *famous*! Why the aitch-ee-double-hockey-sticks \n> didn't you publish this when you found it?\n> Seriously, man.\n>\n> Even given the known weaknesses in MD5, it would take much more than a \n> million documents to find MD5 collisions. I can only conclude that the hash \n> was being used incorrectly; most likely truncated (my wild-ass guess would be \n> to 32 bits; a collision is likely with > 50% probability in a million \n> document store for a hash of less than 40 bits).\n>\n> I know the current state of the art here. It's going to take more than just \n> hearsay to convince me that full 128-bit MD5 collisions are likely. I believe \n> there are only two or so known to exist so far, and those were found by a \n> research team in China (which, yes, is fairly famous among the cryptographic \n> community now after publishing a paper consisting of little apart from the \n> two collisions themselves).\n>\n> Please, let's talk about hash collisions responsibly. I posted earlier about \n> the *actual computed probability* of finding two files with an SHA-1 \n> collision before the sun goes supernova. It's 10^28 to 1 against.\n> The recent cryptographic works has shown that there are certain situations \n> where a decent amount of computer work (2^69 operations) can produce two \n> sequences with the same hash, but these sequences are not freely chosen; \n> they've got very specific structure. This attack does not apply to \n> (effectively) random files sitting in a SCM.\n> http://www.schneier.com/blog/archives/2005/02/sha1_broken.html\n>\n> That said, Linux's widespread use means that it may not be unimaginable for \n> an attacker to devote this amount of resources to an attack, which would \n> probably involve first committing some specially structured file to the SCM \n> (but would Linus accept it?) and then silently corrupting said file via a \n> SHA1 collision to toggle some bits (which would presumably Do Evil). Thus \n> hashes other than SHA1 really ought to be considered...\n>\n> ...but the cryptographic community has not yet come to a conclusion on what \n> the replacement ought to be. These attacks are so new that we don't really \n> understand what it is about the structure of SHA1 which makes them possible, \n> which makes it hard to determine which other hashes are similarly vulnerable. \n> It will take time.\n>\n> I believe Linus has already stated on this list that his plan is to \n> eventually provide a tool for bulk migration of an existing SHA1 git \n> repository to a new hash type. Basically munging through the repository in \n> bulk, replacing all the hashes. This seems a perfectly adequate strategy at \n> the moment.\n> --scott\n>\n> WASHTUB Panama Minister Moscow explosives KUGOWN hack Marxist LPMEDLEY \n> genetic immediate radar SCRANTON COBRA JANE KGB Shoal Bay atomic Bejing\n> ( http://cscott.net/ )\n>\n\n-- \nThere are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.\n -- C.A.R. Hoare\n"},{"id":"372","messageId":"Pine.LNX.4.62.0504161549410.22652@qynat.qvtvafvgr.pbz","threadId":"47","inReplyTo":"Pine.LNX.4.61.0504161114530.29343@cag.csail.mit.edu","subject":"Re: Re: SHA1 hash safety","fromName":"David Lang","fromEmail":"dlang@digitalinsight.com","sentAt":"2005-04-16T22:56:20Z","receivedAt":"2005-04-16T22:56:20Z","isPatch":false,"sender":{"key":"dlang@digitalinsight.com","avatar":null},"body":"On Sat, 16 Apr 2005, C. Scott Ananian wrote:\n\n> Date: Sat, 16 Apr 2005 11:36:28 -0400 (EDT)\n> From: C. Scott Ananian \n> To: Petr Baudis \n> Cc: omb@bluewin.ch, David Lang ,\n> Ingo Molnar , git@vger.kernel.org\n> Subject: Re: Re: SHA1 hash safety\n> \n> On Sat, 16 Apr 2005, Petr Baudis wrote:\n>\n>>> I know the current state of the art here. It's going to take more than\n>>> just hearsay to convince me that full 128-bit MD5 collisions are likely.\n>> \n>> http://cryptography.hyperlink.cz/MD5_collisions.html\n>\n> OK, OK, I spoke too sloppily. Let me rephrase:\n> It's going to take more than just hearsay to convince me that full\n> 128-bit MD5 collisions *IN ARBITRARILY CHOSEN DOCUMENTS* are likely.\n>\n> I could add, \"WITHOUT SPECIAL EFFORT BY AN ATTACKER\".\n\nyou are missing the point.\n\nI'm not talking about takeing one document (sched.c) and finding a \nreplacement that can drop in without being noticed.\n\nwhat I'm talking about is the chance that somewhere, sometime there will \nbe two different documents that end up with the same hash\n\nwhat git is doing (in very crude sysadminish terms) is to take all the \nfiles you care about, move them into a new directory where they are named \nby their hash with a symlink that replaces the origional file (and then a \nbunch of stuff to manage multiple versions of those symlinks)\n\nif you are taking every file that you ever care about and loosing all \nrefrence to it except by it's hash then when you get a second file that \nhas the same hash you loose the contents of one of the two files (race \ncondition over which file gets written into the storage directory last)\n\nanywhere else that hashing algorithms are used people realize that there \nwill be hash collisions and plan accordingly, however people tend to put \nblinders on when you say SHA1 or MD5 and decide that somehow the same \nthing cannot happen with these types of hashes.\n\nthey can, and eventually they will so you need to plan accordingly.\n\nDavid Lang\n\n-- \nThere are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.\n -- C.A.R. Hoare\n"},{"id":"379","messageId":"20050416161153.534b47d5.pj@sgi.com","threadId":"47","inReplyTo":"Pine.LNX.4.62.0504161549410.22652@qynat.qvtvafvgr.pbz","subject":"Re: SHA1 hash safety","fromName":"Paul Jackson","fromEmail":"pj@sgi.com","sentAt":"2005-04-16T23:11:53Z","receivedAt":"2005-04-16T23:11:53Z","isPatch":false,"sender":{"key":"pj@sgi.com","avatar":null},"body":"> what I'm talking about is the chance that somewhere, sometime there will \n> be two different documents that end up with the same hash\n\nI have vastly greater chance of a file colliding due to hardware or\nsoftware glitch than a random message digest collision of two legitimate\ndocuments.\n\nI've lost quite a few files in 25 years of computing to just\nsuch glitches, sometimes without knowing it until months or years\nlater.\n\nWe've already computed the chances of a random pure hash collision\nwith SHA1 - it's something like an average of 1 collision every\n10 billion years if we have 10,000 coders generating 1 new file\nversion every minute, non-stop, 24 hours a day, 365 days a year.\n\nGet real. There are _many_ sources of random error in our\ntools. When some sources are billions of billions times\nmore likely to occur, it makes sense to worry about them first.\n\nReminds me of the drunk looking under the lamp post for the\nhouse keys he dropped - because that's where the light is.\n\n-- \n I won't rest till it's the best ...\n Programmer, Linux Scalability\n Paul Jackson 1.650.933.1373, 1.925.600.0401\n"},{"id":"380","messageId":"20050416161404.718e87e5.pj@sgi.com","threadId":"47","inReplyTo":"Pine.LNX.4.62.0504161543150.22652@qynat.qvtvafvgr.pbz","subject":"Re: SHA1 hash safety","fromName":"Paul Jackson","fromEmail":"pj@sgi.com","sentAt":"2005-04-16T23:14:04Z","receivedAt":"2005-04-16T23:14:04Z","isPatch":false,"sender":{"key":"pj@sgi.com","avatar":null},"body":"> sysadmins realize that there are an infinante number of files that map to \n\nSysadmins know that there are an infinite ways for their\nsystems to crap out, and try to cover for the ones that\nthere is a snow balls chance in Hades of them seeing in\ntheir lifetime.\n\n-- \n I won't rest till it's the best ...\n Programmer, Linux Scalability\n Paul Jackson 1.650.933.1373, 1.925.600.0401\n"},{"id":"382","messageId":"20050416231832.GA11444@ucw.cz","threadId":"47","inReplyTo":"20050416161153.534b47d5.pj@sgi.com","subject":"Re: SHA1 hash safety","fromName":"Martin Mares","fromEmail":"mj@ucw.cz","sentAt":"2005-04-16T23:18:32Z","receivedAt":"2005-04-16T23:18:32Z","isPatch":false,"sender":{"key":"mj@ucw.cz","avatar":null},"body":"Hi!\n\n> We've already computed the chances of a random pure hash collision\n> with SHA1 - it's something like an average of 1 collision every\n> 10 billion years if we have 10,000 coders generating 1 new file\n> version every minute, non-stop, 24 hours a day, 365 days a year.\n\nGIT is safe even for the millions of monkeys writing Shakespeare :-)\n\n\t\t\t\tHave a nice fortnight\n-- \nMartin `MJ' Mares http://atrey.karlin.mff.cuni.cz/~mj/\nFaculty of Math and Physics, Charles University, Prague, Czech Rep., Earth\nHomo homini lupus, frater fratri lupior, bohemus bohemo lupissimus.\n"},{"id":"423","messageId":"ghdi684sm.fsf@brand.scrye.com","threadId":"47","inReplyTo":"4261132A.3090907@khandalf.com","subject":"Re: SHA1 hash safety","fromName":"Tkil","fromEmail":"tkil@scrye.com","sentAt":"2005-04-17T03:23:37Z","receivedAt":"2005-04-17T03:23:37Z","isPatch":false,"sender":{"key":"tkil@scrye.com","avatar":null},"body":">>>>> \"Brian\" == Brian O'Mahoney writes:\n\nBrian> (1) I _have_ seen real-life collisions with MD5, in the context\nBrian> of Document management systems containing ~10^6 ms-WORD\nBrian> documents.\n\nWas this whole-document based, or was it blocked or otherwise chunked?\n\nI'm wondering, because (SFAIK) the MS word on-disk format is some\nserialized version of one or more containers, possibly nested. If\nyou're blocks are sized so that the first block is the same across\nmultiple files, this could cause collisions -- but they're the good\nkind, that allow us to save disk space, so they're not a problem.\n\nAre you saying that, within 1e7 documents, that you found two\ndocuments with the same MD5 hash yet different contents?\n\nThat's not an accusation, btw; I'm just trying to get clarity on the\nterminology. I'm fascinated by the idea of using this sort of\ncontent-addressable filesystem, but the chance of any collision at all\nwigs me out. I look at the probabilities, but still.\n\nThanks,\nt.\n"},{"id":"429","messageId":"20050416210934.11a27387.pj@sgi.com","threadId":"47","inReplyTo":"ghdi684sm.fsf@brand.scrye.com","subject":"Re: SHA1 hash safety","fromName":"Paul Jackson","fromEmail":"pj@sgi.com","sentAt":"2005-04-17T04:09:34Z","receivedAt":"2005-04-17T04:09:34Z","isPatch":false,"sender":{"key":"pj@sgi.com","avatar":null},"body":"> but the chance of any collision at all wigs me out.\n\nGuess you're just going to get wigged out then.\n\n-- \n I won't rest till it's the best ...\n Programmer, Linux Scalability\n Paul Jackson 1.650.933.1373, 1.925.600.0401\n"},{"id":"432","messageId":"4261E84D.6040208@dwheeler.com","threadId":"47","inReplyTo":"20050416161153.534b47d5.pj@sgi.com","subject":"Re: SHA1 hash safety","fromName":"David A. Wheeler","fromEmail":"dwheeler@dwheeler.com","sentAt":"2005-04-17T04:38:37Z","receivedAt":"2005-04-17T04:38:37Z","isPatch":false,"sender":{"key":"dwheeler@dwheeler.com","avatar":"https://avatars.githubusercontent.com/u/813150?v=4"},"body":"Paul Jackson wrote:\n>>what I'm talking about is the chance that somewhere, sometime there will \n>>be two different documents that end up with the same hash\n> \n> I have vastly greater chance of a file colliding due to hardware or\n> software glitch than a random message digest collision of two legitimate\n> documents.\n\nThe probability of an accidental overlap for SHA-1 for two\ndifferent files is absurdly remote; it's just not worth worrying about.\n\nHowever, the possibility of an INTENTIONAL overlap is a completely\ndifferent matter. I think the hash algorithm should change in the\nfuture; I have a proposal below.\n\nSomeone has ALREADY broken into a server to modify the Linux kernel\ncode already, so the idea of an attack on kernel code\nis not an idle fantasy. MD5 is dead, and SHA-1's work factor has\nalready been sufficiently broken that people have already been told\n\"walk to the exits\" (i.e., DO NOT USE SHA-1 for new programs like git).\n\nThe fact that blobs are compressed first, with a length header\nin front, _may_ make it harder to attack. But maybe not.\nI haven't checked for this case, but most decompression algorithms\nI know of have a \"don't change\" mode that essentially just copies the\ndata behind it. If the one used in git has such a mode\n(I bet it does!), an attacker could use that mode to\nmake it MUCH easier to create an attack vector than it would\nappear at first. Now the attacker just needs to create a collision\n(hmmm, where was that paper?). Remember, you don't need to\nrun a hash algorithm over an entire file; you can precompute\nto near the end, and then try your iterations from there.\nA little hardware (inc. FPGAs) would speed the attack.\n\nOf course, that assumes you actually\ncheck everything to make sure that an attacker can't slip\nin something different. After each rsync, are all new files'\nhash values checked? Do they uncompress to right length?\nDo they have excess data after the decompression?\nI'm hoping that sort of input-checking (since the data\nmight be from an attacker, if indirectly!) is already going on,\nthough I haven't reviewed the git source code.\n\nWhile the jury's still out, the current belief by most folks\nI talk to is that SHA-1 variants with more bits, such as SHA-256,\nare the way to go now. The SHA-1 attack simply reduces\nthe work factor (it's not a COMPLETE break), so adding\nmore bits is believed to increase the work factor\nenough to counter it.\n\nAdding more information to the hash can make attacking even harder.\nHere's one idea: whenever that hash algorithm\nswitch occurs, create a new \"hash\" value as this:\n SHA-256 \"+\" uncompressed-length\nWhere SHA-256 is computed just like SHA-1 is now, e.g.,\nSHA-256(file) where file = typecode + length + compressed data.\nLeave the internal format as-is (with the length embedded as well).\nThis means that an attacker has to come up with an attack\nthat creates the same length uncompressed, yet has the same hash\nof the compressed result. That's harder to do.\nLength is also really, really cheap to compute :-).\nThat also might help the convince the \"what happens if there's\nan accidental collision\" crowd: now, if the file lengths\nare different, you're GUARANTEED that the hash values are different,\nthough that's not the best reason to do that.\n\nOne reason to think about switching sooner rather than later\nis that it'd be really nice if the object store also included\nsignatures, so that in one fell swoop you could check who signed what\n(and thus you could later on CONFIRM with much more certainty who\nREALLY submitted a given change... say if it was clearly malicious).\nIf you switch hash algorithms, the signatures might not work,\ndepending on how you do it.\n\n--- David A. Wheeler\n"},{"id":"433","messageId":"gacny8135.fsf@brand.scrye.com","threadId":"47","inReplyTo":"20050416210934.11a27387.pj@sgi.com","subject":"Re: SHA1 hash safety","fromName":"Tkil","fromEmail":"tkil@scrye.com","sentAt":"2005-04-17T04:43:42Z","receivedAt":"2005-04-17T04:43:42Z","isPatch":false,"sender":{"key":"tkil@scrye.com","avatar":null},"body":"\n>>>>> \"Tkil\" == Tkil writes:\n\nTkil> but the chance of any collision at all wigs me out.\n\n>>>>> \"Paul\" == Paul Jackson writes:\n\nPaul> Guess you're just going to get wigged out then.\n\nWig wig. :)\n\nI didn't mean \"wigs me out to the point I won't use it\" but more of\n\"wigs me out so that I'm curious whether there are backup schemes\nworth considering\".\n\nIn particular, the comparisons between hash collisions and hardware\nfailure seem contrived -- if I have bad RAM, or a bad block on my HD,\nI can recover it from known good sources. But if the actual known\ngood source is structured in such a way that a particular set of data\ncannot be represented, that bothers me.\n\nIn this case, the fact that it has to be the same length, same SHA-1,\ncorrect C, and functionally similar C at that, makes for a comforting\ncushion. Further, git wouldn't be the only representation; there\nwould be periodic tarballs, different trees, etc.\n\nOn the other paw, if \"effectively random\" MS Word docs gave true MD5\ncollisions (when we have a proper MD5 hash computed over the entire\ndocument) in a \"mere\" 1e7 space, that is interesting/scary.\n\n(I was also trying to add a few factoids to the MSW comment, as their\nstructure could lead to collisions if (say) only the first 512 bytes\nwere considered -- it's possible that nothing but size and date might\nchange in that, and /those/ I can see colliding in 1e7 documents.)\n\nFinally, I apologize for taking your time. I'm just watching this\nfrom the sidelines, and the questions above are just intellectual\ncuriosity. :-/\n\n(The only other thread I'm really following is people trying to chunk\nfiles in a way that would increase storage efficiency; reading the\nVenti paper, I was wondering how efficient it would be if a one-byte\naddition at the top of the file would generate all-new blocks, while\nthe rsync-ish protocol seems to offer substantial relief. But if the\n\"interesting history\" fits in 10USD worth of HD, that might be enough.\nBabble.)\n\nThanks,\nt.\n\n"},{"id":"438","messageId":"20050416220931.1eec8f1e.pj@sgi.com","threadId":"47","inReplyTo":"gacny8135.fsf@brand.scrye.com","subject":"Re: SHA1 hash safety","fromName":"Paul Jackson","fromEmail":"pj@sgi.com","sentAt":"2005-04-17T05:09:31Z","receivedAt":"2005-04-17T05:09:31Z","isPatch":false,"sender":{"key":"pj@sgi.com","avatar":null},"body":"I have nothing further to contribute to this subtopic.\nGood luck with it.\n\n-- \n I won't rest till it's the best ...\n Programmer, Linux Scalability\n Paul Jackson 1.650.933.1373, 1.925.600.0401\n"},{"id":"590","messageId":"200504170635.j3H6Z0Ga005661@laptop11.inf.utfsm.cl","threadId":"47","inReplyTo":"20050416154951.GB13373@jose.lug.udel.edu","subject":"Re: SHA1 hash safety","fromName":"Horst von Brand","fromEmail":"vonbrand@inf.utfsm.cl","sentAt":"2005-04-17T06:35:00Z","receivedAt":"2005-04-17T06:35:00Z","isPatch":false,"sender":{"key":"vonbrand@inf.utfsm.cl","avatar":"https://avatars.githubusercontent.com/u/211384?v=4"},"body":"ross@jose.lug.udel.edu said:\n\n[...]\n\n> Linus has already weighed in that he doesn't give a crap. All the\n> crypto-babble about collision whitepapers is uninteresting without a\n> repo that has real collisions. git is far too cool as is - prove I\n> should be concerned.\n\nJust copy over a file (might be the first step in splitting it, or a\nheader file that is duplicated for convenience, ...)\n-- \nDr. Horst H. von Brand User #22616 counter.li.org\nDepartamento de Informatica Fono: +56 32 654431\nUniversidad Tecnica Federico Santa Maria +56 32 654239\nCasilla 110-V, Valparaiso, Chile Fax: +56 32 797513\n"},{"id":"612","messageId":"20050418000946.GA7172@thunk.org","threadId":"47","inReplyTo":"4261E84D.6040208@dwheeler.com","subject":"Re: SHA1 hash safety","fromName":"Theodore Ts'o","fromEmail":"tytso@mit.edu","sentAt":"2005-04-18T00:09:48Z","receivedAt":"2005-04-18T00:09:48Z","isPatch":false,"sender":{"key":"tytso@mit.edu","avatar":"https://avatars.githubusercontent.com/u/51416?v=4"},"body":"On Sun, Apr 17, 2005 at 12:38:37AM -0400, David A. Wheeler wrote:\n> The probability of an accidental overlap for SHA-1 for two\n> different files is absurdly remote; it's just not worth worrying about.\n> \n> However, the possibility of an INTENTIONAL overlap is a completely\n> different matter. I think the hash algorithm should change in the\n> future; I have a proposal below.\n> \n> Someone has ALREADY broken into a server to modify the Linux kernel\n> code already, so the idea of an attack on kernel code\n> is not an idle fantasy. MD5 is dead, and SHA-1's work factor has\n> already been sufficiently broken that people have already been told\n> \"walk to the exits\" (i.e., DO NOT USE SHA-1 for new programs like git).\n\nWe're very clearly going to need a FAQ for git.\n\nSHA-1's work factor has been decreased to 2**69 from 2**80 for\ngenerating two messages that have the same hash value, WHERE THE HASH\nVALUE AND THE MESSAGES ARE NOT UNDER THE ATTACKER'S CONTROL. This is\nnot the same as a pre-image attack, where given a message M1 which\nhashes to value H, the attacker can find another message M2 which also\nhashes to value H. In even if the attacker can do this, the result\nhas to have valid git metadata format, and also be valid C code.\n\nSo the the recent result which has weakened (but not broken) SHA-1's\nuse in digital signatures, and which has resulted in the advice to\n\"walk not run\" for the exits, do not apply to git.\n\nCan we guarantee that there won't be further innovations that may\nbreak SHA-1? Of course not. But an attacker who wants to introduced\na trojan into the Linux kernel would have a much easier time doing a\n\"black bag job\" --- i.e., breaking into Linus's house in Portland, and\nthen inserting a buggered patch into his master source tree.\n\nIf you're going to be a professional paranoid, it's best to worry\nabout the realistic attacks before stressing out over the unrealistic\nones.\n\n\t\t\t\t\t\t- Ted\n"},{"id":"603","messageId":"42631664.1050403@khandalf.com","threadId":"47","inReplyTo":"200504170635.j3H6Z0Ga005661@laptop11.inf.utfsm.cl","subject":"Re: SHA1 hash safety","fromName":"Brian O'Mahoney","fromEmail":"omb@khandalf.com","sentAt":"2005-04-18T02:07:32Z","receivedAt":"2005-04-18T02:07:32Z","isPatch":false,"sender":{"key":"omb@khandalf.com","avatar":null},"body":"Linus wants to drive ahead, and ignore the collision issue for now,\nand has been dismissive of the risks, he wants a result not heart\nsearching, and the list comments exhibit a confusion with the\nengineering problem of avoiding accidental collisions v deliberate sabotage.\n\nSince this is not a show-stopper, and getting the BK replacement in place\nis time critical, and if you look at the code it is easy to extend the\ncontent key, LET US just leave this issue for now.\n\nHorst von Brand wrote:\n> ross@jose.lug.udel.edu said:\n> \n> [...]\n> \n> \n>>Linus has already weighed in that he doesn't give a crap. All the\n>>crypto-babble about collision whitepapers is uninteresting without a\n>>repo that has real collisions. git is far too cool as is - prove I\n>>should be concerned.\n> \n> \n> Just copy over a file (might be the first step in splitting it, or a\n> header file that is duplicated for convenience, ...)\n\n-- \nmit freundlichen Grüßen, Brian.\n\nDr. Brian O'Mahoney\nMobile +41 (0)79 334 8035 Email: omb@bluewin.ch\nBleicherstrasse 25, CH-8953 Dietikon, Switzerland\nPGP Key fingerprint = 33 41 A2 DE 35 7C CE 5D F5 14 39 C9 6D 38 56 D5\n"},{"id":"634","messageId":"20050418074323.GA29765@hexapodia.org","threadId":"47","inReplyTo":"4261852B.6090507@khandalf.com","subject":"Re: SHA1 hash safety","fromName":"Andy Isaacson","fromEmail":"adi@hexapodia.org","sentAt":"2005-04-18T07:43:23Z","receivedAt":"2005-04-18T07:43:23Z","isPatch":false,"sender":{"key":"adi@hexapodia.org","avatar":null},"body":"[trimmed cc list, nobody wants to read this noise]\n\nOn Sat, Apr 16, 2005 at 11:35:39PM +0200, Brian O'Mahoney wrote:\n> >> (1) I _have_ seen real-life collisions with MD5, in the context of\n> >> Document management systems containing ~10^6 ms-WORD documents.\n> > \n> > Dude! You could have been *famous*! Why the\n> > aitch-ee-double-hockey-sticks didn't you publish this when you found it?\n> > Seriously, man.\n> \n> The MD5 has was fine, or at least the code (a) produced the correct\n> results on the published test cases, and, (b) was properly applied to\n> all bytes of the file(s). I was surprised when it happened, which is why\n> I bothered to post to this list at this time, so I make two more points\n\nOK, I guess it's time for some remedial math.\n\nThere are 2^128 = 340282366920938463463374607431768211456 different MD5\nhashes.\n\nYou are suggesting that you found a collision using ~1e6 = ~1,000,000\nplaintexts.\n\nLet's suppose there were actually 100,000,000 = 1e8 plaintexts, just in\ncase you underestimated the number.\n\nApplying the birthday paradox, we have a 50% probability that you'd find\none collision if there were ~7,213,475,309,916,173 possible hash values.\nIf you extend the birthday argument (\"what is the probability of a\ncollision if you take N samples from a set of size M?\") you get the\nfollowing results, with N = 1e8:\n\n50% (1 in 2) probability of collision in 7,213,475,309,916,173.\n1% (1 in 100) probability of collision in 497,496,027,172,833,194.\n.05% (1 in 1845) probability of collision in 9,223,372,036,854,775,806.\n\nThat's where my quick-and-dirty solver craps out, but we're still a\nreally long ways from\n\n 340,282,366,920,938,463,463,374,607,431,768,211,456.\n\nA simple linear extrapolation (certainly wrong, but not by more than a\nfew dozen orders of magnitude) says that the odds would be\n1 in 68,056,473,384,187,692,692 for the full MD5 hash (I'm not even\ngoing to dignify that with a percentage).\n\nI'm not going to do the sums, but I would hazard a guess that it's more\nlikely your PC suffered a cosmic-ray-induced memory fault - EACH OF THE\nFOUR TIMES YOU TESTED IT - causing it to report the same MD5, than that\nyou actually discovered a collision with a measly million (or even\nhundred million) plaintexts.\n\n(Of course, I don't know how many tests of the hash you actually did.\nBut the point stands.)\n\nHell, if you're *that* lucky, what are you doing in IT? You could be\nmaking a killing at the roulette table.\n\nOr, even more likely, there was some other factor in the system (most\nlikely that it was only using a few bits, probably 32, of the hash\nwhen looking for collisions) that resulted in a false alarm.\n\nIf you had actual evidence of a collision, I'd love to see it - even if\nit's just the equivalent of\n% md5 foo\nd3b07384d113edec49eaa6238ad5ff00 foo\n% md5 bar\nd3b07384d113edec49eaa6238ad5ff00 bar\n% cmp foo bar\nfoo bar differ: byte 25, line 1\n%\n\nBut in the absence of actual evidence, we have to assume (just based on\nthe probabilities) that there was some error in your testing.\n\n-andy\n"},{"id":"669","messageId":"Pine.LNX.4.61.0504181250200.1039@cag.csail.mit.edu","threadId":"47","inReplyTo":"200504170635.j3H6Z0Ga005661@laptop11.inf.utfsm.cl","subject":"Re: SHA1 hash safety","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-18T16:50:57Z","receivedAt":"2005-04-18T16:50:57Z","isPatch":false,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Sun, 17 Apr 2005, Horst von Brand wrote:\n\n>> crypto-babble about collision whitepapers is uninteresting without a\n>> repo that has real collisions. git is far too cool as is - prove I\n> Just copy over a file (might be the first step in splitting it, or a\n> header file that is duplicated for convenience, ...)\n\nThis is not a collision. This is a *feature*.\n --scott\n\npayment UKUSA ODOATH AVBLIMP ESSENCE JUBILIST ASW AK-47 CABOUNCE Ortega \nPBPRIME North Korea anthrax Milosevic bomb Soviet QKFLOWAGE Yeltsin\n ( http://cscott.net/ )\n"},{"id":"672","messageId":"Pine.LNX.4.61.0504181252590.1039@cag.csail.mit.edu","threadId":"47","inReplyTo":"20050418074323.GA29765@hexapodia.org","subject":"Re: SHA1 hash safety","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-18T17:04:44Z","receivedAt":"2005-04-18T17:04:44Z","isPatch":false,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Mon, 18 Apr 2005, Andy Isaacson wrote:\n\n> If you had actual evidence of a collision, I'd love to see it - even if\n> it's just the equivalent of\n> % md5 foo\n> d3b07384d113edec49eaa6238ad5ff00 foo\n> % md5 bar\n> d3b07384d113edec49eaa6238ad5ff00 bar\n> % cmp foo bar\n> foo bar differ: byte 25, line 1\n> %\n>\n> But in the absence of actual evidence, we have to assume (just based on\n> the probabilities) that there was some error in your testing.\n\nI've already had a long correspondence with this poster. He claims that \n\"this happened 7 years ago\", involved a \"commercial contract covered by \nSwiss Banking Law\" (with caps!) and that, of course, he \"certainly doesn't \nretain [his] client's documents\", and even if he *did*, he wouldn't show \nthem to *me*.\n\nAnd then he was unable to comprehend that I couldn't accept his word alone \nas prima facie evidence that the laws of probability did not apply to him or \nhis clients.\n\nI've been a coder far too long to attribute to \"The Mysterious Hand Of \nGod\" what can adequately be described by subtle programmer error.\n\nThe most reasonable explanation, given the (lack of) evidence, is that \nthe programmer involved quickly took refuge in a (wildly improbable, but \nhis clients'll never know) \"MD5 collision\" instead of buckling down and \nfinding the bug in his code.\n --scott\n\nODOATH Ortega FBI SGUAT AEBARMAN India Peking ODACID operation RYBAT \n[Hello to all my fans in domestic surveillance] for Dummies KUCLUB\n ( http://cscott.net/ )\n"},{"id":"879","messageId":"20050419223027.GA26100@localhost","threadId":"47","inReplyTo":"20050418074323.GA29765@hexapodia.org","subject":"Re: SHA1 hash safety","fromName":"David Meybohm","fromEmail":"dmeybohmlkml@bellsouth.net","sentAt":"2005-04-19T22:30:27Z","receivedAt":"2005-04-19T22:30:27Z","isPatch":false,"sender":{"key":"dmeybohmlkml@bellsouth.net","avatar":null},"body":"On Mon, Apr 18, 2005 at 12:43:23AM -0700, Andy Isaacson wrote:\n> \n> I'm not going to do the sums, but I would hazard a guess that it's more\n> likely your PC suffered a cosmic-ray-induced memory fault - EACH OF THE\n> FOUR TIMES YOU TESTED IT - causing it to report the same MD5, than that\n> you actually discovered a collision with a measly million (or even\n> hundred million) plaintexts.\n\nBut doesn't this require assuming the distribution of MD5 is uniform,\nand don't the papers finding collisions in less show it's not? So, your\nbirthday-argument for calculating the probability wouldn't apply, because\nit rests on the assumption MD5 is uniform, and it isn't.\n\nFor example, say most people are married in June, get pregnant, and\nthere are more births around March, 9 months later, than in other\nmonths. Then if you are born in March you have a higher chance of seeing\na collision of your birthday with someone else's. The same is true for\nsomeone else born in March too, and this makes the chances of seeing a\ncollision for the whole function higher.\n\n"},{"id":"890","messageId":"Pine.LNX.4.61.0504191848300.29929@cag.csail.mit.edu","threadId":"47","inReplyTo":"20050419223027.GA26100@localhost","subject":"Re: SHA1 hash safety","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-19T22:48:57Z","receivedAt":"2005-04-19T22:48:57Z","isPatch":false,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Tue, 19 Apr 2005, David Meybohm wrote:\n\n> But doesn't this require assuming the distribution of MD5 is uniform,\n> and don't the papers finding collisions in less show it's not? So, your\n> birthday-argument for calculating the probability wouldn't apply, because\n> it rests on the assumption MD5 is uniform, and it isn't.\n\nNo, the collision papers don't show this at all.\n --scott\natomic strategic HBDRILL SARANAC COBRA JUDY Ft. Meade assassination politics \nMossad HOPEFUL ZPSEMANTIC DTFROGS HTKEEPER LITEMPO LIONIZER operation\n ( http://cscott.net/ )\n"},{"id":"1016","messageId":"20050420185653.GA3076@localhost","threadId":"47","inReplyTo":"Pine.LNX.4.61.0504191848300.29929@cag.csail.mit.edu","subject":"Re: SHA1 hash safety","fromName":"David Meybohm","fromEmail":"dmeybohmlkml@bellsouth.net","sentAt":"2005-04-20T18:56:53Z","receivedAt":"2005-04-20T18:56:53Z","isPatch":false,"sender":{"key":"dmeybohmlkml@bellsouth.net","avatar":null},"body":"On Tue, Apr 19, 2005 at 06:48:57PM -0400, C. Scott Ananian wrote:\n> On Tue, 19 Apr 2005, David Meybohm wrote:\n> \n> >But doesn't this require assuming the distribution of MD5 is uniform,\n> >and don't the papers finding collisions in less show it's not? So, your\n> >birthday-argument for calculating the probability wouldn't apply, because\n> >it rests on the assumption MD5 is uniform, and it isn't.\n> \n> No, the collision papers don't show this at all.\n\nI didn't mean they showed it directly. I meant by finding collisions in\nMD5 quickly, MD5 would have to have some non-uniformity. But that's\nnevertheless wrong because uniformness and collision finding ability\naren't related. Sorry to have wasted everyone's time.\n\nDave\n"}]}