Without a salt one can pre-compute all the KDF (input, output) pairs and store them in a dictionary (essentially). This single dictionary now acts as a kind of master key.
By including a random per-user salt, even assuming the attacker has access to the salt, the output of the KDF now varies on both a per-user and per-password basis.
Two users with the same password have different keys under this design, so pre-computing something that works for all users becomes infeasible.
If the KDF is weak in other ways, e.g., it is so fast that one doesn't need to pre-compute anything, that's a separate issue.
1. You have a whole bunch of encrypted files from different users.
2. The KDF is slow compared to checking if decryption with a given output of the KDF is successful.
With a salt this will take time nm(T + Q) where n is the number of files, m is the number of different passwords and T is the time it takes to execute the KDF and Q is the time it takes to try to decrypt with a derived key. Without a salt you can amortize the KDF executions for a total time of mT + nmQ.
In particular it doesn't help you decrypt one specific file, and the total time is still on the order of n*m, so unless Q is very cheap compared to T this won't help much (obviously still a good idea to do the salting though).
I think you're confusing encryption and KDFs. Encryption is meant to be reversible, KDFs are not.
In this context, a KDF is used for verifying that a message is valid. I have a derived key, you give me a key, and I verify that key by running it through the KDF. If KDF(your_key) == derived_key then we have "proven" that your_key is valid.
Another way of thinking about it is that the image of a KDF should map low-entropy input to high-entropy output. Depending on what we're using the KDF for, we might also want it to have other properties, e.g., intentionally slow, intentionally memory intensive, etc.
This is different than you encrypting something, sending me the encrypted message, and me decrypting it using a shared secret.
I don't think I said anything that disagrees with this? In this case the output of the KDF is used as a key to decrypt a further key, with is in turn used to decrypt your file. So an attacker can't just do a simple check to see that he guessed the right password, he actually needs to decrypt the file and see if garbage comes out or an actual decrypted file.
By including a random per-user salt, even assuming the attacker has access to the salt, the output of the KDF now varies on both a per-user and per-password basis.
Two users with the same password have different keys under this design, so pre-computing something that works for all users becomes infeasible.
If the KDF is weak in other ways, e.g., it is so fast that one doesn't need to pre-compute anything, that's a separate issue.