At 123 bits, you're five bits short of the 128 bits I calculated with. I don't think a medium sized botnet can rise to the level of doing 8 quadrillion years of work within your lifetime.
What problem are you trying to solve? As I understand it, we're discussing enumerating the hash space, such that:
1. You are given a hashed value, such as 2b0f4e60b80da7ef1e84573d764f1bf4 .
2. The value is someone's hashed password. You need to find any string which hashes to this particular fixed value, but you don't know of any such string to start with.
You can do this by brute force, but it will take you a long, long time.
The problem is NOT:
1. You have a string which hashes to a particular value.
2. You want other strings which hash to the same value.
And it also isn't:
1. You have a string which, with an unknown prefix, hashes to a particular known value.
2. You want to identify hashes which represent the same string with other prefixes applied.
I don't see where salting is relevant to the question. It's a defense against the phenomenon that cracking one user's password automatically also cracks everyone else who uses the same password (since, without salting, they all have the same hash), but it isn't a defense against having your password cracked by a targeted attack (since, in a targeted attack, there are no other hashes to be collateral damage). Why did you bring it up? What attack are you thinking of?
I agree with your thrust that your parent poster (AstralStorm) is barking in a different forest from the tree we care about, but for salting it is also a defence against pre-computation to trade space for time.
With an unsalted hash an adversary can do as much work as they want in advance, store output and then trade that in once they have your hashes to get all or most of the same rewards as if they'd done the work after getting your hashes. Rainbow tables are the most famous example, but they're part of a family of similar attacks.
Salt lets you arbitrarily discount this advance work because the attacker must do it for all possible salt values and you get to choose how many there are - the early Unix crypt() salted pessimised password hash discounts it by a factor of 4096, modern schemes often use many orders of magnitude more salt. An attacker who has $4M to attack my password scheme probably doesn't want to spend $4M now to have a $1000 advantage once they get the hashes, and they certainly won't for a 1¢ advantage.
A rainbow table is the exact attack I'm saying is still infeasible. ("Strong passwords are still just as strong.") It only works by assuming the victim uses one of a known set of weak, easy-to-guess passwords. If they don't, their hashed password is very unlikely to be in the rainbow table at all, because there's just too much hash space. The calculation in my original comment gives the approximate number of hashes necessary to fill a complete md5 rainbow table, on the assumption that you get zero collisions in the process of filling it in. (That is, every time you hash something, you get a hash you've never seen before, allowing you to add new information to the table.) That assumption is not at all realistic. By the time you've filled in half of the space, unless you can choose them cleverly to avoid collisions, half of the strings you hash should be wasted effort.
In a single-target attack, I don't really see the concept of "pre-computation to trade space for time". That hurts you by taking a lot of space, but it doesn't gain you any time, because you spent at least the required amount of time, but almost certainly more, doing the pre-computing. If you can buy someone else's pre-computed rainbow table, then sure, that's an advantage for you. But the adversary actually doing the pre-computing is doing it in order to crack many people's passwords all at once ("this table will let you identify _everyone_ whose password is qwe123"), which is the scenario I described earlier.
(At this point I feel I should clarify that "some people use the same passwords" is a real threat and a real reason to avoid md5. I just don't think the comment I responded to, "It is a question of when not if a hash table is fully cracked", was made in good faith or informed by... anything. To fully crack md5 in that way, you'd need an easily-computed function that inverts it. No amount of hashing speed is ever going to get you there.)
> In a single-target attack, I don't really see the concept of "pre-computation to trade space for time"
In a single-target attack the reason you'd do this is because you expect your target to react in a timely fashion to discovery of some other part of your attack by changing passwords.
e.g. maybe you're sure you can break in to get hashes, but you will trigger a reactive IDS. You figure you have some period of time after that trigger before your target is alerted and changes their password.
Time-space tradeoff lets you avoid doing all the work against the clock _after_ the IDS triggers, instead you can do it all _before_ you have the hashes, and only pull the trigger and set off the alarms when you're ready to quickly break the hash, get in and do whatever your actual attack requires.
It's not a _common_ scenario, but it's important to remember it exists in designing general purpose components like password hashes.
You can assume the system uses a certain salt pattern, e.g. 4 byte prefix or 8 byte prefix or suffix.
This can reduce work from full crack to some 40 bit crack. (Guess salt then presume stupid concat scheme, use collision attack to get matches.) That one is doable on a modern PC on a GPU. It is a targetted attack. The mass variant are salted rainbow tables.
You usually do not even have to recover actual password to use credentials associated with the hash.
What problem are you trying to solve? As I understand it, we're discussing enumerating the hash space, such that:
1. You are given a hashed value, such as 2b0f4e60b80da7ef1e84573d764f1bf4 .
2. The value is someone's hashed password. You need to find any string which hashes to this particular fixed value, but you don't know of any such string to start with.
You can do this by brute force, but it will take you a long, long time.
The problem is NOT:
1. You have a string which hashes to a particular value.
2. You want other strings which hash to the same value.
And it also isn't:
1. You have a string which, with an unknown prefix, hashes to a particular known value.
2. You want to identify hashes which represent the same string with other prefixes applied.
I don't see where salting is relevant to the question. It's a defense against the phenomenon that cracking one user's password automatically also cracks everyone else who uses the same password (since, without salting, they all have the same hash), but it isn't a defense against having your password cracked by a targeted attack (since, in a targeted attack, there are no other hashes to be collateral damage). Why did you bring it up? What attack are you thinking of?