8 ms·
SHA-1 Collision Detection on GitHub.com
- yuhong 10y agoI wonder how many chosen prefix (not identical prefix) attacks this detects. There are many ways to do it ranging from 2^77 to 2^80 time. Of course, this is still much more expensive than identical prefix, and git would probably not the best target for such attacks.
- koolba 10y agoThe article links to this repo that actually does the work of finding possible collisions: https://github.com/cr-marcstevens/sha1collisiondetection https://github.com/cr-marcstevens/sha1collisiondetection My understanding of it is that it runs a SHA-1 and examines the internal state of the of the digest along the way to see if it matches up with known vectors that could be manipulated to cause a collision.
- unholiness 10y agoInteresting that it's hosted on GitHub. Everyone in this thread is wondering about the 2^-90 chance that a random commit will fail, but I wonder how these guys prevented their repo with test files from being rejected.
- koolba 10y agoThe files don't trigger a collision because git adds a header prior to hashing. The hash is the sha1 of the total bytes.
- theoh 10y agoOn that note, in the case of this kind of system, the possibility of a false positive (so a commit fails, but shouldn't) there's always the option of adding a salt or a NOP of some kind to the file being committed so as to alter its hash. Filesystems like Venti could conceivably, on the one hand, check for collisions, but on the other, compare the stored block with the newly committed block. If there's a collision, but the blocks differ, just perturb the new block with a NOP, a nonce header of some kind...
- collinmanderson 10y agoYou could also just zip the files and unzip when testing
- indolering 10y ago> Everyone in this thread is wondering about the 2^-90 chance that a random commit will fail Considering that the Bitcoin network burns through ~2^90 hashes in a year ... I'm not worried : )
- click170 10y ago> The recent attack uses special techniques to exploit weaknesses in the SHA-1 algorithm that find a collision in much less time. These techniques leave a pattern in the bytes which can be detected when computing the SHA-1 of either half of a colliding pair. > GitHub.com now performs this detection for each SHA-1 it computes, and aborts the operation if there is evidence that the object is half of a colliding pair. Isn't it possible for a valid non-colliding object or commit to contain that pattern as well? It sounds like eventually, though possibly in the far distant future, someone will be unable to push a commit to Github because it matches the pattern but doesn't contain colliding objects. Does anyone know what the pattern is they're looking for? I'm curious now.
- rspeer 10y agoThey say that the chance of a false positive is less than 2^-90.
- orblivion 10y agoPer commit, or over the expected lifetime of Git's utilization of sha-1? If it's the former it's not very useful unless we have an idea how many commits are made.
- AnimalMuppet 10y agoWell, I'd lay a fair amount of money that the number of commits is less than 10^20...
- semi-extrinsic 10y agoThere are ~3.1e9 seconds in a century, and ~7.5e9 people on Earth. So if every human makes a git commit every second for a century, the odds of a single false positive is ~5.3e-7 (i.e. less than one in a million).
- sillysaurus3 10y agoif every human makes a git commit every second for a century Will someone please write a dystopian novel around this premise? It almost writes itself. GitHub turns evil, forcing the world population into subservience from birth; using Git is all anyone is ever allowed to do, and is how people conceptualize the universe and access entertainment; various cults form with the belief that randomness can be influenced via the right ceremony... You can source inspiration from https://twitter.com/DystopianYA https://twitter.com/DystopianYA
- BrailleHunting 10y agoForcing committers to GPG sign their commits and authorizing only verified commits from certain key ids would be a stronger, end-to-end chain-of-custody process. Right now, GPG verification badges on tags and commits is nice but it doesn't have "teeth." This is a nice step, but GH needs to keep going and add stronger, mandatory defense-in-depth (optional security doesn't get used).
- homakov 10y agoIt's not them it's GPG that's too ugly to be used even by programmers. If they enforce it, too many people will struggle
- mstade 10y agoI set up GPG for my account a couple of months ago, and found it surprisingly simple. The setup has even survived a recent machine change with no issues what so ever. Curious to know what makes this "too ugly" if you don't mind elaborating!
- FungalRaincloud 10y agoI see this line of thought pretty frequently. I don't really understand why we collectively believe that GPG is so tough. I started using it as a teen, barely even understanding the software, let alone how the actual encryption worked. I've come to understand it, but even when I didn't, it didn't seem difficult at all to get passable security out of it. Cyphar has the right answer for why this would be problematic, though - GPG would just prove that the initial commit was from a trusted committer. It would be trivial to use the same signature with the fake commit. That's not an unsolvable problem, but switching to a different hashing algorithm seems to me like the more reasonable solution.
- cyphar 10y agoBut commit signatures are actually just signing the SHA1 hash. So you still have the problem that you could just reuse the signature for the valid commit with the malicious one.
- a13n 10y ago> Two objects colliding accidentally is exceedingly unlikely. If you had five million programmers each generating one commit per second, your chances of generating a single accidental collision before the Sun turns into a red giant and engulfs the Earth is about 50%. What happens when machines are writing commits and there are far more than 5 million and 1 per second? Is this a "640K ought to be enough for anybody" quote of our time?
- markcerqueira 10y agoI guess the pertinent question now is how close are we to 5 million and 1 commits per second!
- AnimalMuppet 10y agoOne of two things will happen. Either the machines will be generating random commits, and nobody will care if they collide... ... or the machines will be able to generate real, useful code that fast, in which case it will be the machines' problem to solve.
- charles-salvia 10y agoAnd in the latter case, most human programmers will be unemployed, and thus unconcerned with hash collisions.
- nojvek 10y agoIf you were generating hashes on the gpu for collisions, according to https://hashcat.net/forum/thread-4314.html https://hashcat.net/forum/thread-4314.html A single titanX does 2^9 hashes per second. Suppose you had a 10,000 Gpus (expensive but not impossible) you can do 2e13 hashes per second. In 100 years there are ~3e9 seconds, so 6e22 hashes. Still magnitudes below 90. Sha1 isn't still crackable by brute force in a meaningful time.
- graton 10y ago> Is this a "640K ought to be enough for anybody" quote of our time? No. 1) That quote wasn't actually said by Bill Gates 2) Very few people will quote that 15-20 years from now.
- TorKlingberg 10y agoIf I understand right they detect files that contain the specific collision that Google released. It will work fine until somebody else does the same work Google did to generate an other collision pair.
- peff 10y agoNo, it's better than that. It detects evidence of the cryptanalytic tricks that were used to generate that collision. So it will find any collision generated using their attack technique (which is ~2^63 operations, as opposed to 2^80 for brute force). There may be new disturbance vectors discovered as the attack matures, but they can be added to the detector.
- gruez 10y agoWhy use that specific method to detect sha1 collisions rather than doing a direct comparison or hashing using a more secure algorithm?
- chrisseaton 10y ago> rather than doing a direct comparison A direct comparison between what two things? In the attack they are worried about, they only see one half of the attack. > hashing using a more secure algorithm They don't control how Git works.
- homakov 10y agoConsider detecting this too https://gist.github.com/homakov/c11f1e3b8b35300ffa07abf95a64fb69 https://gist.github.com/homakov/c11f1e3b8b35300ffa07abf95a64...
- uwu 10y agowhat is it?
- fny 10y agoLooks like a bug with Cyrillic character highlighting. I'm guessing this is probably an issue with Rogue/Pygments[0][1] since I doubt Github is rolling their own syntax highlighter. [0]: https://github.com/jneen/rouge https://github.com/jneen/rouge [1]: http://rouge.jneen.net/pastes/6nDQ http://rouge.jneen.net/pastes/6nDQ
- antons_ghost 10y ago>>> "params[:sandboх] = true".decode('ascii') Traceback (most recent call last): File "<stdin>", line 1, in <module> UnicodeDecodeError: 'ascii' codec can't decode byte 0xd1 in position 14: ordinal not in range(128)
- tkremer 10y agoWhy not just store a second hash with a different algorithm, and check both hashes match?
- Buge 10y agoThat's a good idea, but only provides full protection if all git clients do it. The official git client itself doesn't support that, so people would still be vulnerable if they got a malicious half from github, or a signature on a non-malicious half from github and a malicious half somewhere else. This protection github is implementing uses a heuristic to try to find collision attempts by just looking at a single file. So it prevents github from hosting any collision attempts.
- Achshar 10y agoI don't think github is in a place to change how git itself works. That's Linus and the team's job.
- deleted 10y ago[deleted]
- IncRnd 10y agoThe SHAttered attack was made public shortly after browsers deprecated SHA-1 or started flagging SHA-1 in certs as insecure. This specific practical attack may have existed for a while before it was made public. In fact it may have been made public only when it no longer provided practical benefits. Just some food for thought.
- simias 10y agoThat doesn't make a lot of sense to me, if anything this type of attack only gets more practical as the cost to compute a collision dwindles. It's not like a 0-day vulnerability. I'm also not aware of any significant recent attempt at mitigating SHA-1 collisions that would've suddenly made the attack impractical. And in general these collisions are pretty difficult to exploit since you can't control the collision exactly.
- yeukhon 10y agoMaybe. But SHA-1 is still widely used today, perhaps no long for signing certificates, but a lot of developers and systems today continue to use SHA1 to produce checksum.
- taejo 10y agoThe team that found it is at least partly academic; they published a paper on a free-start collision at CRYPTO 2015, and made a prediction there about how long it would take them and how much it would cost to find a full collision, which was more or less accurate. They are hash function researchers, not spies or hackers. There's no reason to believe they were hiding anything.
- rmc 10y agoWe don't know what tools the NSA have in their arsenal.
- runholm 10y agoWeaknesses with theoretical attacks have been known for over 10 years, and most major companies started phasing it out of use years ago. The recent news that someone was able to find two colliding inputs is just yet another red flag against continuous use, but there is no more need to panic now than a year ago. Remember that finding a collision for a spesific input is much harder than finding two inputs which collide.
- xg15 10y agoOne thing I'm wondering about that I haven't seen discussed yet is the possibility to make circular git histories: When a git commit hash is calculated, one of the data that is used are the pointers to parent commits. That results in two properties for commits: 1) A child commit's hash cannot be predicted without knowing the parent commits 2) Once a commit is created, its parent pointers are practically immutable. The only way to change them is to create a new commit with a different hash - which cannot carry over the old commit's children. Those properties meant that it's impossible to construct a commit with a parent pointer that points to its own children. Therefore it was safe to assume that a git history is always a DAG. I think with deliberate SHA1 collisions now possible, someone could actually violate property (2) and introduce a cycle. As the DAG assumption is pretty fundamental, I'd imagine such a cycle could break a lot of tools. Has this ever been tested?
- laumars 10y agoInteresting idea. Continuing your theory, if a git utility then got locked in an infinite cycle trying to import the commit due to the recursive parent-child relationship, then such an attack might be exploitable for DOSing cloud-based git repositories.
- rmc 10y agoA circular directory would be much worse. As soon as you check it out, your disk fills up.
- maweki 10y agobut git doesn't store directory information. it is implicit with the file information. So symlink-shenanigans shouldn't be possible using just the git objects.
- rbehrends 10y agoGit doesn't store directory information per se, but the directory structure is still reflected in tree objects.
- 10y ago
- everlost 10y agoNaive question - why can't GitHub use a SHA2 function for commit hashes?
- detaro 10y agoBecause Git only supports SHA-1 as of now, and files in Git, distributed to users, is what they worry about here. If it were some internal system, then they could switch to a different hash easier.