7 ms·
This 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 s
by dijit 5y ago
This 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?
- hunter2_ 5y agoWhenever you say how long something takes, you need to specify how much computing power is used to achieve it in that duration (FLOPS or whatever appropriate unit). Then you see what it costs to manufacturer and operate the device that operates at that speed. Then you spend double to have 2 such devices and parallelize the job, completing it in half the time. Repeat that last part until the time is reasonable (TFA is all about this). It doesn't break down until you exceed the available natural resources and our ability to put them to work.
- SAI_Peregrinus 5y agoTypically we calculate assuming the total energy needed at the Landauer limit at 3K. It's usually going to be multiples of the entire sun's energy output for billions of years, more if not using a quantum computer. Money isn't the relevant metric at the scales of modern cryptography.
- amluto 5y agoBut the Landauer limit, even at 300K, for a first preimage of even a completely secure hash is essentially zero. Define: f(s, n, h) = 1 if there exists an n-bit preimage of h that starts with s, else 0 Computing f by brute force costs one bit erasure to prepare room for the answer. (And takes 2^(n - len(s)) operations, but we’re imagining a civilization that can build Dyson spheres and has quantum, and hence at least somewhat reversible, computers. We’re talking about the Landauer limit in particular.) Now choose an appropriate n (slightly greater than the length of the hash) and compute f for s=[0] and s=[1]. After at most two tries, you’ll get a match, assuming a preimage exists. Call the first match s_1. Now repeat for s_1||0 and s_1||1. Call the first match s_2. Repeat this up to s_n. Now s_n is the lexicographically first n-bit preimage! This costs O(n) energy at the Landauer limit. All crypto is broken! Never mind that the actual computation involved exceeds 2^n.
- SAI_Peregrinus 5y agoWith reversible computing, yes. I strongly suspect that'll never be practically realized, or in the event that they are that the slowdown will be large enough that other fundamental limits on the speed (rather than the energy) of computing will instead dominate.
- adrian_b 5y agoSecurity is measured in both time and money. With little money you need a long time, with a lot of money a shorter time is enough. The security is good enough when the attackers need either more money than they have to break the cryptographic scheme in a useful time, or when using the amount of money that they afford results in breaking the cryptographic scheme after a time that is too long to be useful. For cryptographic problems which are ideally parallelizable, the product of money by time is constant. For most real problems the amount of required money increases much faster than the solving time is reduced (except that there are some thresholds where slightly more money can produce a large decrease in the solving time, e.g. when you can afford to design and make a dedicated ASIC for the problem; however after such a threshold and the corresponding step in the required time, the quantity of money still increases faster than the time decreases).
- sigmoid10 5y agoThe thing is, collisions should correlate with hash length. If hashes were uniformly distributed, you should need about 2^160 hashes to find a SHA-1 collision. But researchers got that number down to 2^61. That's the difference between completely impossible, even with a state actor's level of resources, and almost possible with consumer grade hardware.
- naniwaduni 5y agoBrute-force collisions is a birthday attack, so you expect to find a collision in 2^80 hashes, not 2^160.
- usr1106 5y agoBirthday if you want to access any account. Not if you want to access a targeted account. Whether the math is right if it were birthday I don't remember at the moment.
- naniwaduni 5y agoCollisions don't help you access accounts.
- eyelidlessness 5y ago> This was fun, but my gut reaction to the title was “it doesn’t have to be easy, just possible” and that holds. It really depends why you’re hashing and what the consequences of a collision are. Using a hashing algorithm to protect sensitive data (should I hash passwords with SHA-1?) should weight the value of this answer significantly differently than using it as a convenient lookup optimization (should I use SHA-1 to identify git references?). And there’s a spectrum between those, where that convenience might be an attack surface (can I impersonate someone’s git commit?) or might be worth the risk (does it matter if I can easily find a collision?). Unless I’ve missed some new proof, it should be assumed the answer to “is it possible?” will likely always be yes. The question then becomes “has the known wisdom on the following questions changed since I last asked?”, followed in no specific order by, “how plausible is the collision? how much do I care if it happens? how motivated are people to find it? are there other plausible mitigations in place? is the known wisdom on these questions likely to change in a way meaningful to me? how soon?”
- l33t2328 5y agoIt is always possible to generate a collision for any hash function since they are not injective by definition.
- eyelidlessness 5y agoMy point wasn’t to address whether any hashing technique might be collision-free, but that assessing that fact is not a good metric for the fitness of a given hashing technique.
- naniwaduni 5y ago> Using a hashing algorithm to protect sensitive data (should I hash passwords with SHA-1?) You're almost certainly fine! A collision oracle doesn't actually make it any easier to conduct a preimage attack. We normally recommend against using hashing algorithms with known collision attacks for password hashing because (a) these hashes aren't well-suited to password hashing in the first place (b) because having a collision attack implies structural weakness and you don't really want to be caught relying on that hash if a preimage attack does turn up (c) as a fashion statement. > using it as a convenient lookup optimization (should I use SHA-1 to identify git references?) Now this is a bad idea, because having collisions in the wild means that someone can swap out one for the other without the hash catching it, so now you need to build in extra complexity to mitigate that. (Of course, collisions always exist in theory, so you want to design around the possibility. The difference having collisions in the wild makes is that as long as they're only theoretical, you can get away with e.g. screaming loudly about running into an impossible situation and guarantee that you don't do something actively dangerous, or falling back to something horrendously slow but always correct; once collisions exist in the wild, that's a denial-of-service.)
- wlesieutre 5y agoThey're underestimating GPU costs substantially by looking at the MSRP, even for AMD cards, versus AWS pricing which is based in part on Amazon having to actually buy hardware. For the 6800 XT, $900 is more realistic than $650 right now, so it'd be fair to add another 50% hardware price by about 40%.
- dotnet00 5y agoPrices have been coming down quickly over the past month or so though. Lately I've even seen brand new 3090s and 3080ti-s available at MSRP or even slightly below it on Amazon for hours. Although the pricing for AMD's lineup does seem to be in a weird spot right now, 6800XT for $950 but 6900XT for MSRP@$999.
- cmeacham98 5y agoIf you're buying in bulk you can get GPUs for close to or even at MSRP (AMD at least, and I assume it's similar for Nvidia).
- wlesieutre 5y agoThat's true, I'm looking at retail prices here. Can you really get MSRP on a $20,000 order though? That's small enough that people could coordinate group buys instead of going through retailers if it were easily doable.
- cmeacham98 5y agoProbably not at MSRP, especially given the card they're talking about is the 6800XT which is very in demand. Based on personal experience of being involved with orders of similar magnitude (~$30k-$40k), I'd guess you could get within 25% of MSRP rather easily, and within 10%-15% if you got lucky (and are good at negotiating). > That's small enough that people could coordinate group buys instead of going through retailers if it were easily doable. You'd have to trust somebody with several hundred dollars to a grand of your money. There's very few people I would do that for and I don't think I could easily put together a group big enough. Also there's other ways to get near/at-MSRP GPUs as an individual (ex: weekly AMD.com drop).
- danamit 5y agoI wonder how much buying hashing power from elsewhere would cost.
- PragmaticPulp 5y ago> 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. The real benefit of the AWS solution is that you could rent a large number of AWS nodes and run the calculations to completion right now if you wanted to. As in, literally tonight. And you wouldn’t have to source the hardware, assemble machines, install software, power it all, cool it, figure out all of the power complexities and so on.
- systemvoltage 5y agoI expect some "Is this Bitcoin mining?" flags to go off at AWS. So realistically, I would say, 2-3 business days to get things going properly.
- losteric 5y agoDoes AWS ban Bitcoin mining? Why would they care as long as the bills get paid
- nemothekid 5y ago>Why would they care as long as the bills get paid I imagine it's the cause of several support tickets along the lines of "I got hacked and racked up a $50,000 bill because of bitcoin mining"
- nerdbaggy 5y agoThey don’t ban it, but new accounts or even semi old accounts will have hard time getting access to more than a few instances. Most of the GPU machines are behind lock and key that go toward AWS bigger clients and clients with a proven track record. They don’t want to be stuck with an unpaid ec2 bill for a multi thousand dollar a month vm.
- rkagerer 5y agoEasy fix, give the new, reputationless customers the chance to pay in advance.
- eek2121 5y agoAgreed to the first sentence. Let's say you have a table full of SHA-1 salted + hashed passwords, is even remotely worth the effort to spend even 1k per user/per password? Especially when many (though obviously not all) may be using unique passwords (such as myself)? Even if they use the same passwords for all sites, that is an incredibly large hill to climb... Oh uh, to be clear, you should NOT be using SHA-1 right now. If you are reading this in order to justify not moving to a stronger hashing algorithm, none of us give you permission to do this, and if you get caught, any of us involved will vote for hanging you...with a noose...in a good old western style hanging...or something. Seriously. Don't use SHA-1. Move on. If you are a manager and a developer tells you that you can't move on, please reach out. I've (regretfully) moved many from SHA1 -> SHA-XXX and I've provided migration paths. Migration paths with accessibility mind you...though that apparently doesn't matter to many of you cough Citibank cough.
- tptacek 5y agoSHA-XXX is also not an acceptable password hash.
- CamperBob2 5y agoWhy not?
- throwaway787544 5y agoBecause a password hash should be based on a KDF and SHA hash algorithms aren't. https://en.m.wikipedia.org/wiki/Key_derivation_function https://en.m.wikipedia.org/wiki/Key_derivation_function
- rocqua 5y agoBecause it is fast. Password hashing is better a slow function to compute. Delaying login by e.g. 0.001s (say 1000 times slower than normal) is unnoticeable, and login is rare enough that the total compute impact is quite low. But for a brute force attack a 1000 times slowdown is horrible. Even if specialized hardware makes it only 10 times slower it might still be effective. KDFs try to be slow, and they try to be hard to speed up with specialized hardware, all to prevent brute forcing. There is ab interesting parallel with PoW systems. Many cryptos have switched PoW algorithm to remove the advantage of specialized hardware. This is supposed to prevent decentralization.
- Salgat 5y agoReminds me of multithreading. If a race condition is possible, you have to assume it will happen, especially because you can never predict what weird edge cases will trigger it to happen more than you'd expect.