Is a randomly generated long password more secure than a higher number of rounds in a PBKDF?

Question

Usually the requirements for passwords are that they should be salted and use a high number of rounds.

My understanding is:

1. Salting a password is only used to prevent rainbow attacks
2. Using a high number of rounds is only used to prevent brute-forcing short passwords

But if a password is computer generated and only used in an automated way between 2 remote systems, is it safe to salt it, but not hash it with multiple rounds? Would using an extra long randomly generated password (like a 256 bit password) be enough to avoid needing the multiple rounds? Would just salting be enough?

Answer 1

TL;DR Yes, a password with a strength of 256 bit would be much more secure than a password of around 40-60 bits (the strength of reasonably secure passwords) + a number of iterations. Even about 270 million iterations would only add 28 bits of security ($2^{28} \approxeq 270 \text M$).

Salting a password is only used to prevent rainbow attacks

That's not entirely correct; for one you could easily distinguish identical passwords if there is no salt (or other data) used to distinguish between use cases or indeed users.

Using a high number of rounds is only used to prevent brute-forcing short passwords

Well, yes. A normal hash is already one-way, and you need the salt for the aforementioned purposes. So the only reason to use the iteration count or work factor is to have the attacker perform many rounds of the underlying primitive as well.

Of course, if the salt is missing, the iteration count would also make it harder to build a rainbow table.

But if a password is computer generated and only used in an automated way between 2 remote systems, is it safe to salt it, but not hash it with multiple rounds?

That's not a password, that's a secret. If you'd use it correctly you might not even need a salt, although you will have to keep in mind that the secret remains the same in the protocol that you use it for (e.g. for encryption you'd need an IV or nonce to make sure the outcome is not deterministic).

Would using an extra long randomly generated password (like a 256 bit password) be enough to avoid needing the multiple rounds?

There is no such thing as a 256 bit password. Passwords consist of text, not binary. 256 random bits are common for keys such as AES-256 keys or keys used for HMAC-256.

A password could have 256 bits of entropy, spread over many characters. But such a password could not be remembered by a human for normal operations. For instance, if you'd use ASCII with all possible special characters (without space) then you'd need a fully random 39 character password ($\log_{92}(2^{256})$ in case you want to verify this).

And yes, for a secret key you would not need the iteration count or the PBKDF in the first place. If you need a salt or not depends on how you are going to use it. You would not need it for one-time usage. If you need a KDF then you could use a Key Based KDF such as HKDF.

Answer 2

Salting predated rainbow tables by a significant margin. In fact it may have come before the more general time memory tradeoff for inverting hash functions(Would have to look up but and pick exact dates to attribute the developments, but late 70s early 80s is when these stuff were happening).

Rainbow tables I was around to remember the paper "A faster cryptanalytic time-memory tradeoff" came out late 2003 IIRC. And though we commonly use rainbow tables as a synonym for time memory tradeoff they only give a factor of 2 compared to previous multiple tables with distinguishing points. They simply were the best option as these attacks became viable for many hash functions.

Back to to Salting. Salting prevents attacking multiple hashes together. If I get a leaked file with hashed passwords and no salt is used we can brute force all of the passwords together. The runtime to break at least one password drops linearly with the number of password.

Iteration count is great for slowing down the attacker, but it slows down the legitimate user as well. And though we try to combat with memory hard functions, we should assume the attacker still has a scale advantage. E.g with GPUs or custom hardware. And of course there could be cryptanalytic improvements. More entropy in the source ia more robust and won't slow down the legitimate user.