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.
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"
Legally, even money you have in your account now might not stay there, if there was fraud involved. But the mined coins will be gone (and the compute time, too).
I didn't do the math, just my feeling.
People also overestimate how much effort it is to manage hardware, especially for raw compute (ie 99% SLA fine) operations.
The cooling and power is handled by your datacentre. You don't need to deal with that.
I've built a 200 GPU mining operation in one workweek, pay me $170k?
And that is just raw uptime, as an end-user you also have to live with you jobs waiting for the scheduler to fit them into the queue. A day or two waiting time is pretty common on larger jobs.
> There is no runtime available right now. Please change the compute type or try again later.
recently, that's not always true.
It's always funny to me when you run into a wall of "no more instances" in AWS. It doesn't happen often unless you're at a massive scale, but it does happen surprisingly often with the GPU types
It's pretty sad how Google/Amazon can't at least temporarily move their own workloads to free up resources for their public clouds while they install new hardware.
That's likely not the reason. It's more likely caused by inherent spike-y ness of the traffic, given that most GPU instances are probably used for batch numerical computations (like training neural networks). The pricing incentivizes using a lot of nodes for a shorter amount of time, much like in the SHA example.
If their own public services slowed down in high demand times, it wouldn't look good. The sales channels could try to spin it as “giving you priority over us” but who would genuinely believe them.
They could reduce resources available to low priority internal stuff during spikes of other activity, but that would not have a large effect considering the combined size of activity on the public cloud resources.
I dig the cloud for production, but for R&D I like my people to have fixed costs and close to zero marginal costs.
But you are right that the marginal costs will be mostly made up of opportunity costs.
Unless you have only one researcher, it doesn't matter for an individual researcher whether their marginal costs are opportunity costs of their co-workers or AWS bills.
(And if you don't have any mechanism for your individual researchers to feel the opportunity costs of their co-workers; that is the same thing as saying that one researcher can hog up all the compute time.
Social pressure is also a way to make them feel opportunity costs.)
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?”
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.)
Somebody better tell Linus? I kid. But yeah the answer is you use it as part of your lookup and then mitigate collisions with more expensive comparisons.
They are working on it since 2017. https://github.com/bk2204/git/commits/transition-stage-4/Doc...
Not that it's particularly urgent...
Anyway, practically you're going to write a collision fallback anyway, the difference is that as long as collisions aren't likely, you can be pretty sure that collision handling is a very cold code path that's never going to have more than a handful of items in a bucket.
The point I'm trying to make, though, is that while practical collision attacks do have practical implications, they aren't relevant to password hashing. People routinely assume that collision attacks make a hash unsuitable for password hashing. They're not exactly wrong, but it's kind of a non sequitur. I felt that this was a point that had to be made because the framing of parent ("what the consequences of a collision are") implied that the expected answers were exactly the opposite.
It is possible that this a bad idea because of collisions. However, if you have for example a federated system you don't have a central instance issuing identifiers for objects. So you create a hash. In reality it doesn't matter if you used SHA1, MD5 or even a random identifier. As long as you have enough bits, a collision becomes unlikely. However again, if you have many objects consider the birthday paradox.
The interesting thing here is that this is an issue in any case: Even if you have an extremely secure hash algorithm, in the end you have less bits than the original data, so collisions must occur, even if they are immensely improbable.
If you then decide that you ignore collisions because after considering the birthday paradox collisions won't occur practically it can be worth thinking about what would happen if such a collision does occur.
Let's say your application executes a database update and has a hash collision. Then another object would be overwritten.
This is a use case of not mixing object creation and object update. If you program carefully such that you never overwrite another object if you update your object you'll get an internal error if you have a hash collision. That's better than losing unrelated data.
However this is difficult to test. And I am sure that other bugs are a lot more probable.
But this thinking shows me that it is useful to program defensively.
If you have assumptions, encode them in assertions. So even if you don't have tests for this rare problem, your chance of being lucky is higher.
But it <i>does</i> matter. Usually it's only a big problem in edge cases, but sometimes those edge cases are <i>extremely</i> important. TLS certificates use a hash as their identifier in a distributed/federated model like you describe. By generating collisions, one can submit a normal signing request to a trusted public CA, but then use the resulting signature with a second certificate that has malicious properties (being for a domain name belonging to someone else, having additional properties like it being trusted to sign other certificates, etc.).[1] This is why you can't get new MD5 or SHA1 certificates signed by public authorities anymore.
As you say, there is always going to be at least an infinitesimally small chance that two realistic inputs to the same hashing function will produce the same output, but IMO virtually any system that uses hashes as identifiers will have its security degraded in some way if it's practical to generate a collision.
<i> If you program carefully such that you never overwrite another object if you update your object you'll get an internal error if you have a hash collision.</i>
It sounds challenging to handle this gracefully in a distributed system without some fairly complex logic. Alice uploads a PDF of sensitive data that hashes to value A on node 1. Node 1 grants Alice full access to the file with that hash. Bob uploads some meeting notes that also hash to value A, but on node 2. Node 2 grants Bob full access to the file with that hash. When the nodes are synchronized an hour later, the system detects a collision. What does it do?
First, for a password hash function to matter, the hashed password must be compromised. If you don't have the hash it doesn't really matter all that much. Yes, hashed passwords do get compromised but many don't.
Second, I can't think of many bigger security threats than intentionally creating an SHA1 collision for a git repository. Poisoning a Linux git repo could be truly disastrous. Remember too that if you can poison a git repo, you can also make the binary output have the same size and hash too. I mean that's much more difficult but not impossible and it wouldn't surprise me if state actors have dedicated a lot of computing power to this.
And "is it possible?" is by definition always "yes".
I do? I should have been more clear that I think this is another case which very much depends on the other considerations I addressed and probably many more.
> And "is it possible?" is by definition always "yes".
You’re not the only person to say so, and… I know. I left the possibility open in my response mainly because I wanted to focus on the other considerations without dismissing the parent comment. Even if the answer was less definitive I believe considering level and degree of risk should be a bigger factor in these conversations than what’s theoretically possible.
As the link suggests, it is nowhere near impossible, and well funded attackers can produce collisions extremely quickly.
Git also uses sha1 for signing commits, which is another area where it relies on it for security.
That collisions theoretically exist is not a problem, only being able to compute them reasonably. (Reasonably being the sum of a human lifetime)
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.
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?
f(s, n, h) = 1 if there exists an n-bit preimage of h that starts with s, else 0
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.
https://security.stackexchange.com/questions/6141/amount-of-...
(Admitting the possibility of an incorrect current understanding of the mathematics is, like, a major reason to go with the enormous overkill on key sizes we do.)
If you can make the cost to break effectively "infinite" ,that's great as its really easy to analyze.
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).
Whether the math is right if it were birthday I don't remember at the moment.
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.
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.
Unfortunately, this tends to just prolong the development of ASIC's, and often keeps the first working versions hidden from the public with the sole purpose of being able to mine with vastly increased efficiency compared to others.
Monero's RandomX also seems succesful, but that has a higher bar (wanting to be CPU only) and a smaller footprint so ASICs might be easier to hide.
As a bonus for KDFs, there is much less economic pressure to 'break' them. So trying to develop ASICs / FPGAs / GPU implementation is pure cost, rather than an investment.
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%.
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.
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).
Hmm if you know enough video game players at the office you could coordinate this through work. Might try it for the next generation.
Worst case if someone backs out you have to sell the extra, which isn't going to be very hard right now.
I don't know for sure. If I had to guess, it has good performance per watt for mining, and miners generally care more about that than performance per dollar.
> And is it worth selling mine to buy a 6900XT or an nvidia?
If you're able to sell yours and buy a 6900XT (or Nvidia GPU better than the 6800XT, basically 3080 and up), then I don't see why not.
If you can sell yours and upgrade for a small cost - how much is the performance worth to you? You're probably only getting 10%-20% more performance (depending on GPU), is that worth $50, $100, etc?
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.