Even if you assume weak passwords, there's no comparison in effort when you involve stretching.

No salt means you can precompute the hash for the 1,000,000 most common passwords. That'll take maybe an hour or two with aggressive stretching. Then you check it against the million or so records in the database for any matches.

Salt means FOR EACH RECORD in the database, you have to compute those 1,000,000 passwords. That means you're talking about decades of computation time. That's a heck of a lot more expensive. And importantly, you have to start that computation AFTER the breach, because that's when you gain access to the salts.

Salts are not unimportant.

> Salt means FOR EACH RECORD in the database, you have to compute those 1,000,000 passwords. That means you're talking about decades of computation time.

SHA256 of the million most common passwords (with a 128 bit salt) takes 2 seconds /total/ on my laptop. That's only 42 days required to crack a database of one million hashes.

  var stopwatch = Stopwatch.StartNew();
  var salt = "0123456789012345";

  int crackCount = 0;

  foreach (var password in File.ReadLines(@"c:\temp\10_million_password_list_top_1000000.txt"))
  {
    System.Security.Cryptography.SHA256.Create().ComputeHash(Encoding.UTF8.GetBytes(password + salt));
    ++crackCount;
  }

  stopwatch.Elapsed.Dump();
  crackCount.Dump();

=>

  00:00:02.0981333
  999999

Salt is indeed important, but the only real way to protect is to iterate - PBKDF2/scrypt/bcrypt.

Are you ignoring the part where I said "when you involve stretching?"

The claim was that salting is irrelevant compared to stretching. It is not. It is still unbelievably important even when doing stretching.

I think in the real world there are two scenarios, someone is using one of PBKDF2/Bcrypt/Scrypt - in which case all of this is moot, set an appropriate work factor/#of iterations, and you are secure with even a moderate sanity check against the password. Interesting note - said sanity check, ironically, could be a simple as a lookup - the top 4 billion passwords can be stored in a packed 24 gigabyte lookup table on disk which can be searched in < 100 milliseconds).

The other scenario is when you doing a single pass of a hash, in which case the salt is irrelevant for the security of that password.

Everyone here understands that you need to salt when your dictionary takes a long time to build (Say, more than 1 millisecond/password, which equals 2.5 billion passwords/month) - not everyone appreciates that salting a fast password (more than 2.5 billion passwords/second) - adds no security to that particular password.

The scenario where there is moderate "stretching" (by which I presume you mean running multiple iterations of a hash), with no randomized salt, is a bit of a straw man - who would bother to go the effort of "stretching" and not stick a randomized salt in while they are at it?

Sorry yes I obviously missed that bit.

So - I think we basically agree with each other, that for a straightforward single round of a hash like SHA256, that a salt is now irrelevant (reason - a GPU cluster can check 10s of billions of passwords/second)

I think the point I was trying, and perhaps failing to make, is that the three PBKDFs - PBKDF2/BCRYPT/SCRYPT - all come with a salt anyways - so you don't really need to call them out.

What I guess I should have made explicit, (and I didn't) is that if all you are doing is a single round of a SHA - then adding a salt at the beginning isn't going to make that password any more secure. If it could fall to a Rainbow Table Lookup, then it will fall in pretty much the same amount of time to a password-cracker - on the order of milliseconds.

Now this is something which i don't understand. Is this really the best we got?

If you somehow get into a server with those hashed passwords, you'll probably try to mirror it and everything on the server, to figure out the hashing mechanism. So lets say, time is not an issue, also regarding long lasting APT's.

So what will you do with it? Why should you try brute force a million passwords, each one taking 2 hours to decrypt? No, you're smarter than that: Why not create a rainbow table of possible admin account, vips, state actor, etc. How many are those? 100? 1000?

Nice, you just reduced the search space by a factor of 1000.

That whole circus about hashing... I know, randomly salted hashing makes sense, but true secure password storage is a myth.