<em>The password is automatically salted with the domain and username</em>
...which is exactly as secure as Gawker.com themselves doing a salt+hash.
Let's for a minute assume what you're proposing is what's being done. Gawker has been attacked. The hacker has the columns "password" and "username". Hacker knows the domain name. You're exactly where you left off!
Even if the password has been again hashed and salted on the server - that's just an extra round of cracking (or, more realistically, rainbow-table matching).
What you _should_ be doing is using a single, trusted and very much secure password provider (a la OpenID). Hacker attacks your site, gains nothing. And if you must do the authentication yourself, or the nature of your userbase prevents you from outsourcing the authentication (perhaps <em>you</em> are the OpenID provider we're talking about earlier), you need to be using something more complex than a silly MDx or even SHAx to do the hash - these are made for boiling down huge amounts of data into a small field of not more than ~256-4096 bytes - which is NOT what you want. Look at bcrypt - it's DESIGNED for this. It's a solution waiting for more and more attacks like Gawker.com so lazy and incompetent developers worldwide will use this existing, plug-and-play, simple, direct, and safe alternative to what they're currently doing.
EDIT
Regarding rainbow tables - I'm predicting that with todays resources and cloud super-computing, etc. (just look at the new EC2 GPU instances!) we're going to see a new type of rainbow tables that actually precompute the hashes for different salts as well. It's an order of magnitude larger data and more computation than last generations rainbow tables, but todays tech is more than an order of magnitude more available.
I think that's not true - you'd have to generate new rainbow tables for each user for gawker. So this method would indeed make rainbow tables impractical.
edit: but I think the rest of what you said is fine.
In addition to tptacek's comment off yours, rainbow tables aren't remotely necessary to check the most common passwords, gaining thousands of them in seconds. The salt's there. Just hash "password1" against all the salts in the database - you're nigh-guaranteed to get a bunch, associated with their username. Viola, you've likely got their email account.
Similarly, any sufficiently-complex-and-long (at best: random) password in those hashes is effectively secure. Rainbow tables typically only handle up to a dozen-ish characters long, and specific common passwords, frequently only alphanumeric values to limit the problem space. You're stuck brute-forcing each one effectively separately because you don't have enough storage on the planet to rainbow-table my 30-character random-ascii password. For instance, freerainbowtables.com recently cracked "racsivrv" and their table is 232GB. [1]
And even if you do find a match, it's simply a hash-collision. There are an infinite number of those. You might have my password, you might just have a random string that behaves like it with that salt. If it's random, you can't tell until you try it on other sites that I use the same password on. If it's a word, there's probably just the one (of reasonable length).
Rough sizes and overall idea (though I don't tend to link to codinghorror for accurate details, it's a pretty readable overview): http://www.codinghorror.com/blog/2007/09/rainbow-hash-cracki... Very specifically from that link, "You'll also note that that passphrases, which I am a big fan of, are immune to this technique due to their length."
The reports I've seen have been that the password hashes were crypt(3) hashed; I've literally seen reports of people checking their hashes with crypt(3) to verify that they lost their real password.
That being the case, it feels reasonable to respond to your argument about "no evidence of brute-force cracked passwords" by saying that the tool that brute forces these passwords has been open sourced since NINETEEN NINETY. I was in 8th grade when the tool that breaks these passwords was published. "Love Will Never Do Without You" by Janet Jackson was a hit single.
I think --- it's hard to prove, since you'd have to get into a long involved conversation about how easy things are to parallelize in CUDA or FPGAs --- that the scheme you've provided is actually faster than that: like, De La Soul or Run-DMC easy instead of Janet easy.
>To compare this to the incredible magnitude of computation required to do that for a truly distinct per-row large entropy salt is extraordinary.
But the salt is based off a static, known set of data per user: username and domain. The salt is known, even though it isn't stored.
So run `shasum (salt + "password")`, or however they mangle it. It's precisely the same thing. There can't be a more-complex salt, because all browsers have to replicate it, or you could only use your login info from a single browser - lose that, and you lose your account.
<em>The password is automatically salted with the domain and username</em>
...which is exactly as secure as Gawker.com themselves doing a salt+hash.
Let's for a minute assume what you're proposing is what's being done. Gawker has been attacked. The hacker has the columns "password" and "username". Hacker knows the domain name. You're exactly where you left off!
Even if the password has been again hashed and salted on the server - that's just an extra round of cracking (or, more realistically, rainbow-table matching).
What you _should_ be doing is using a single, trusted and very much secure password provider (a la OpenID). Hacker attacks your site, gains nothing. And if you must do the authentication yourself, or the nature of your userbase prevents you from outsourcing the authentication (perhaps <em>you</em> are the OpenID provider we're talking about earlier), you need to be using something more complex than a silly MDx or even SHAx to do the hash - these are made for boiling down huge amounts of data into a small field of not more than ~256-4096 bytes - which is NOT what you want. Look at bcrypt - it's DESIGNED for this. It's a solution waiting for more and more attacks like Gawker.com so lazy and incompetent developers worldwide will use this existing, plug-and-play, simple, direct, and safe alternative to what they're currently doing.
EDIT
Regarding rainbow tables - I'm predicting that with todays resources and cloud super-computing, etc. (just look at the new EC2 GPU instances!) we're going to see a new type of rainbow tables that actually precompute the hashes for different salts as well. It's an order of magnitude larger data and more computation than last generations rainbow tables, but todays tech is more than an order of magnitude more available.