13 ms·
How easy is it in 2022 to find a SHA1 collision?
- cerved 5y agosadly, Microsoft didn't get the memo https://stackoverflow.com/a/70434510 https://stackoverflow.com/a/70434510
- userbinator 5y agoI wonder how easy it is to use a collision in that context (SSH)?
- xiaodai 5y agoWhat should be used instead
- colordrops 5y agoSHA256 is an option. It's secure enough for Bitcoin.
- acchow 5y agoProving cryptographic security by financial incentive seems to be the most useful aspect of blockchains.
- quickthrower2 5y agoSomeone that can crack cryptocurrency needs to figure out how to extract value without spooking the entire market into collapsing. That is why I think they’ll put more effort into exploiting badly written smart contracts than the underlying blockchain. Ethereum projects get hacked every day, hackers make millions, but no one loses faith. More of a gravy train. Really you need someone with a mission to crack bitcoin, not someone looking just to make money.
- paulpauper 5y agojust break into a dormant wallet or multiple old wallets . you only need just a few thousand btc to be set for life and for it to be undetected. depends on what you mean by crack.
- Vladimof 5y agobut if bitcoin/sha256 gets cracked, it isn't a big deal, because miners will probably agree to move to something better and revert bad transactions...
- quickthrower2 5y agoBitcoin is a brand not a fixed protocol (see the Bitcoin Cash fork, for example…)
- Vladimof 5y agoPretty much... Bitcoin is whatever the majority (of miners) agrees it to be... and it could change at any time.
- postalrat 5y agoSure. But how about all the addresses out there that won't move the coins to an updated address? They would stay vulnerable.
- quickthrower2 5y agoYes this relies on some foresight, to move well in time of the zero-day.
- unobatbayar 5y agoPeople seem to overestimate the security of SHA256 as compared to SHA1. Although it is definitely better than SHA1, the improvement is ever so slightly: SHA1 : ec1623b7a94ed3d8feaffaf7580df3eca4f5f5ca SHA256 : e2b0c44298fc0c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
- michaelscott 5y agoA "mere" 2^96 improvement; the security between the two is a universe apart.
- charcircuit 5y agoblake3 if you do not have to worry about compatibility with older things that do not support it
- bombcar 5y agoDoes using and verifying multiple hash functions help? If something verifies with SHA1 and MD5 is it better than just one? Of course you’d add SHA256 and BLAKE3 or whatever. I think I’ve seen Gentoo’s portage use multiple.
- charcircuit 5y ago>Does using and verifying multiple hash functions help? Technically yes, but it takes extra time to hash something twice and it will take extra storage to store 2 hashes. This trade off is not really worth it compared to just using a good hash function alone.
- ReactiveJelly 5y agoProbably whatever the libsodium team recommends. For password hashes, looks like Argon2 https://doc.libsodium.org/password_hashing https://doc.libsodium.org/password_hashing For generic data, they're still using BLAKE2b as the default, not BLAKE3. Not sure why. Too new? https://doc.libsodium.org/hashing/generic_hashing https://doc.libsodium.org/hashing/generic_hashing SHA256 and SHA512 alone are not awful, but they're slower than BLAKE3 and vulnerable to length extension. You can add extra tricks to protect them from length extension, like a length prefix or like doing SHA512/256, but it's better not to add tricks to your crypto.
- omegalulw 5y agoWhat about bcrypt?
- duskwuff 5y agoDifferent tool for a different job. bcrypt is a password hash. It's optimized to defend against brute-force attacks on a short secret string -- which means it's slow (tens to hundreds of milliseconds), and it doesn't support inputs longer than 72 bytes at all. SHA256 and the BLAKE family are designed for hashing larger bodies of data. They're fast (~5 CPU cycles per byte) and can handle an arbitrarily long input.
- shp0ngle 5y agopassword hash is not a general hash. general hashes are to be used in other crypto constructions. Or, if you really need just a quick hash (but really think if you really need it.) Password hashes are for passwords.
- charcircuit 5y ago>but they're slower than BLAKE3 It's important to know that this currently isn't true for small inputs for SHA256 when using a cpu with dedicated instructions for it.
- trinovantes 5y ago> vulnerable to length extension I think this is only relevant if you're using a hash as a MAC, in which case you should be using HMAC-SHA256 instead which is not vulnerable to length extension attacks
- tptacek 5y agoSHA2 or Blake2; they're both fine, with an edge to Blake2 on a safer interface and better software performance.
- quaffapint 5y agoPick your poison. Here's the latest results from SMhasher listing various hashing options many even much faster than Blake3. Find one that works for you and has a stable library for your language/platform. https://rurban.github.io/smhasher/doc/ryzen3.html https://rurban.github.io/smhasher/doc/ryzen3.html
- tptacek 5y agoUnsurprisingly, the really fast ones tend to be exploiting hardware intrinsics.
- oconnor663 5y agoI don't know how that benchmark figure was measured, and I think these are more informative: https://bench.cr.yp.to/results-hash.html https://bench.cr.yp.to/results-hash.html. The specific CPU and the input length both matter a lot.
- dylan604 5y agoHow long is a string? That question is just as easy to answer as the one you posed. Your question is best answered by asking more questions. What are you doing with the hash is probably the first question. Depending on the answer will go a long way to helping pick an algo that provides the most appropriate when considering security vs expense/time to hash
- Zamicol 5y agoSHA2 and SHA3.
- dijit 5y agoThis was fun, but my gut reaction to the title was “it doesn’t have to be easy, just possible” and that holds. Unless, I guess, you want to collide a sha1 for some reason. I found the AWS vs GPU cost comparison to be fun. 10x the cost of the hardware to run the collisions in the same time window. Crazy.
- rco8786 5y agoCollisions are possible in any hashing algo. You’re taking infinite inputs and mapping them to finite number of outputs. There are literal infinite collisions in any hashing function.
- dijit 5y agoMaybe I was unclear. That sha1 collisions can be manufactured is a problem. That collisions theoretically exist is not a problem, only being able to compute them reasonably. (Reasonably being the sum of a human lifetime)
- ReactiveJelly 5y agoSecurity isn't measured in time, it's measured in money. If my secret is worth $10 and it costs $500 to crack, nobody will bother. If my secret is worth $1 million and it costs $900,000 to crack.... I have a serious problem.
- ClumsyPilot 5y agoTechnically true but hard to calculate and you have to re-calculate regularly as technology changes
- TacticalCoder 5y ago> Security isn't measured in time, it's measured in money. That's not how cryptography works though: many schemes (for sufficiently large keys) are, in our current understanding of mathematics, totally unbreakable over a period of time that stretches from now until the heath death of the universe. That's measured in time and no amount of money is going to change anything about it right?
- userbinator 5y agoIt's still not as easy as MD5, which can be done in a few seconds on a 10-year-old CPU.
- khnov 5y agoare you saying you need few seconds to crack an md5 hash using an old cpu ?
- MiguelX413 5y agoI'm pretty sure that's what they said.
- TheDong 5y agoThat's not the case. They're saying you can find a collision easily (i.e. I can easily give you two files that have the same md5sum). However, "crack an md5 hash" isn't what that means. First, you can't really "crack" a hash (there are infinitely many inputs that have the same hash), but even just going from a hash to any input with that hash is much harder. That's a preimage attack, and a preimage attack for md5, according to wikipedia, remains theoretical https://en.wikipedia.org/wiki/MD5#Preimage_vulnerability https://en.wikipedia.org/wiki/MD5#Preimage_vulnerability. I welcome anyone to give a counter example by giving me something that has an md5 hash of 08fc873f2aac5acce46ed751613472fe
- TillE 5y agoYeah, this is an important point. The known published attacks on MD5 are pretty narrow, so there are many circumstances where you can rely on MD5 hashes if you have to.
- quickthrower2 5y agoCareful, you are open to a $5 wrench attack
- maccard 5y agoThat's also true if you use a more secure hash.
- rdtwo 5y agoIf you run it Against a database of thousands or millions of passwords you can trickle out a steady flow though. So each gpu can crank out a few cracked accounts a day.
- nokcha 5y agoQuestion is a bit ambiguous whether it refers to a 'second-preimage attack' or a 'collision attack'. 'Second-preimage attack': You are given a message, and your goal is find another message that hashes to the value as the given message. 'Collision attack': Your goal is to construct two messages (of your choosing) that hash to the same value.
- forgotmypw17 5y agoA question for the experts: Does it add any additional security to multi-layer multiple hash algorithms and/or multiple runs of the same algo? For example, sha1(md5(sha1(foo)))
- alexlur 5y agoIt will decrease the security.
- dannyw 5y agoIn this case yes as md5 has a lower bit size and both algos are broken. When done correctly, it increases the security. It's like encrypting a file with AES and then encrypting it with Twofish and then Serpent. The security is actually the strongest link; not the weakest. That's why bitcoin addresses use SHA256(RIPEMD160(X)) for output into a 160 bit hash.
- atq2119 5y agoThe "when done correctly" is a huge caveat, given that what you're replying to does it incorrectly. If X and Y collide, so that SHA-1(X) = SHA-1(Y), then f(SHA-1(X)) = f(SHA-1(Y)) no matter what f is -- so you get a collision. Concatenating the outputs of the hash functions fixes that particular issue. But concatenating makes preimage attacks easier.
- drdrey 5y agoPlease explain
- forgotmypw17 5y agoCan you please clarify why this is? I don't understand why it would decrease security.
- mrspuratic 5y agoI can't generalise for f(g(h(foo))), but as referred to in sibling comment (dannyw), the specific example sha1(md5(sha1(foo))) decreases security because the output of MD5 is 128 bits, compared with 160 bits for SHA-1. The arbitrarily long input foo is reduced to an input of 128 bits at the final step, and you only need to find that input for a collision (independently of any MD5-specific weakness you may also have added to the mix).
- TedShiller 5y agoHow easy? Depends on how much money you have. With sufficient money it’s easy. Otherwise, hard.
- yalogin 5y agoSorry for the tangential post here but the cost difference between hosting the GPUs and using AWS is jarring to me. The whole value proposition is to do things cheaper. Now I can’t understand how this can be correct anymore. Basit ever been the case at all?
- nknealk 5y agoIf I recall correctly Nvidia does not allow you to put consumer cards into data centers. They force you to buy a different line of cards which are like 10x more expensive. That may be a driver of the AWS price. Update — I do recall correctly. Source: https://www.digitaltrends.com/computing/nvidia-bans-consumer-gpus-in-data-centers/ https://www.digitaltrends.com/computing/nvidia-bans-consumer...
- kube-system 5y agoOne of the reasons the cost looks so radically different is also because it is not comparing the same things. AWS is not just GPU + electricity. It's GPU + a server + a rack + electricity + network + a physical data center + real estate + labor + reserve capacity + automation, etc...
- dotnet00 5y agoAWS GPUs (or ones offered by any of the big cloud providers for that matter) are not really all that cost effective. They also have to use datacenter GPUs, which are a lot more expensive than consumer ones. For cost effectiveness, one route (mostly in the ML community) is to rent people's machines via services like vast.ai, who can get around NVIDIA preventing use of consumer cards in data centers by making it so they're only selling/buying time on people's computers. These end up being a lot more affordable (IIRC ~$20/day for a 2x 3090 system) but in exchange have the unreliability that comes with renting time on someone else's computer, like tasks randomly getting killed (which is pretty frustrating to wake up to, as you get charged for time rather than usage), some people having poor upload/download speeds or other gpu performance issues.
- Sohcahtoa82 5y ago> The whole value proposition is to do things cheaper. I don't think this was ever the case, at least, not in the short term or at smaller scales. I always thought the value proposition for AWS was the fact that you could scale up and down nearly instantly and that you didn't have to run your own data center, which was a monster of an expense. AWS made it so a single person could be a startup. With just a couple clicks, you've got a server running, and you only pay for the time you use. Now, maybe you're asking about GPUs specifically...in that case, yeah, I don't know why people would use AWS unless they really only need a couple hours of GPU time per month or something. GPU instances are so expensive that the ROI for buying them yourself hits pretty quickly. You have to REALLY need the rest of the AWS infrastructure to be directly connected to your GPU to make it worthwhile.
- l33t2328 5y agoThis is relevant: http://shattered.io/ http://shattered.io/
- sidcool 5y agoTheoretically, how much money and time to break SHA 128? Can ML and pattern recognition expedite the calculations?
- teknopaul 5y agoWhat does this mean for lxcoin (a sha1 based coin) ? There is a few 100,000 in that coin is that value at risk
- feintruled 5y agoCan someone ELI5 why collisions are so serious? As far as I understand what a collision is, it means you have two source files that produce the same hash output, but why is this so bad? How do you have any control over what the contents of those two files are?
- iforgotpassword 5y agoIf you use the hash (that we assume you aquired overa secure channel) to verify the download of eg an installer for some sensitive software, and someone manages to give you a backdoored installer instead with the same hash, that would be rather bad.
- iso1210 5y agoI think the question is that how is it useful if you happen to have two hashes that match - it's very unlikely that they will be Where the problem comes is when you can generate a matching 128 bit hash with your own content without having to do 2^128 different hashes (or strike ridiculously (lottery winner being struck by lightning) lucky and only need to do 2^100 hashes)
- walls 5y agoLets say you have an anti-malware service that sees file1, analyzes it, and decides the file is benign. The service then updates a database saying 'hash xyz has been analyzed and is benign'. Then you send file2 which is actually malicious, and the service decides it has already analyzed this file and lets it go. This would work on a lot of big AV appliances and software. A surprising amount of these are still using md5 for de-duplication.
- pornel 5y agoThis specific attack is not possible against SHA-1 (yet). The known collision weakness only allows generating two colliding pieces ahead of time with a hash value that you don't control. It does not give you ability to collide with a pre-existing file/pre-existing hash, so you can't attack any existing SHA-1-verified file. You can only attack files that you've specifically crafted/tricked to contain your colliding block.
- Mason69 5y ago[dead]