Does it make any difference when salting database passwords with Random vs SecureRandom? I want to salt database passwords and then compute the hash but I wonder if I should use Random or SecureRandom? From an attacker perspective would it be easy to break if Random is used or SecureRandom is used or does it make no difference? if yes why? if not, why not?
I am telepathically inferring you're talking about Java here, in which:


Random is a linear congruential generator with a 48-bit seed and no security properties whatsoever, and
SecureRandom is some cryptographic algorithm whose documentation (archived 2019-03-23) is unclear about its security properties, with broken links and archaic references, but of which one might reasonably expect the following two standard properties:


indistinguishability from uniform random (or prediction resistance, next bit test): to anyone who does not know the seed, the output is indistinguishable from a uniform random string of bits; i.e., prior outputs do not help to predict subsequent outputs
key erasure (or backtracking resistance, or forward secrecy): even if the state is compromised, it does not help to recover past outputs


[edit: I just looked closer (archived 2019-02-22) and discovered that the one algorithm supported by SecureRandom does not, in fact, do key erasure at all—it just uses SHA-1 in ‘CTR mode’.  Nice, Java.]




In general, you should use SecureRandom by default unless you have measured an overwhelming performance concern arising from it.  In general, you might get in cryptographic trouble just from the use of Random.  In general, you will never get in as much cryptographic trouble just from the use of SecureRandom, unless loads of other people are in much deeper trouble already.  If you find yourself spending time wondering which one to use, but you haven't measured a performance impact, you are wasting time wondering and you should just use SecureRandom.



OK, you measured a performance impact?  If not, stop reading and go back to the previous paragraph.

What are the security requirements for salts in password hashes?

The purpose of the salt is to thwart multi-target attacks like rainbow tables that save effort by attacking many instances of the same hash simultaneously—that is, the same unsalted hash.  For example, if an adversary is trying to find one password $p_i$ given $\operatorname{MD5}(p_1), \operatorname{MD5}(p_2), \dots, \operatorname{MD5}(p_n)$, they can use a multi-target attack which costs only $2^{128}/n$ and which can run in time $2^{128}/n^3$ if parallelized $n^2$ ways, even though as a 128-bit hash function you might naively expect the cost of an attack to be about $2^{128}$ in the best case that the $p_i$ were chosen by processes with 128 bits of min-entropy themselves.

Using an independent function for each password, as in $(s_i, \operatorname{MD5}(s_i \mathbin\| p_i))$ where each $s_i$ is a distinct salt, thwarts this attack.*  Of course, it thwarts the attack only if everyone on the planet is using an independent function for every password; in other words, if anyone else uses the same salt, then a multi-target attack can still save costs for an adversary.

According to the documentation (archived 2019-04-01), Random is a linear congruential generator with a 48-bit seed.  This seed is so small that even if it were chosen uniformly at random, collisions would be expected after a few million choices, leading to identical salts produced for every output.  It is unclear how the seeds are chosen; it would not be surprising if it were chosen from the time of day and/or the process id, in which case similar applications run at similar times might choose the same seed.

There are cryptosystems where public values like initialization vectors absolutely must be unpredictable in advance, like AES-CBC.  Is it the end of the world to use Random for password hash salts?  No, but it would suggest that you're a too-cool-for-crypto hipster with reckless disregard for user security and/or your auditors' time, but with ample free time of your own to spend dying on hills on the internet.  You're not that hipster, are you?

N.B.:  You should not use MD5 for anything.  For password hashes, you should use argon2, which has exactly the same considerations for salts, but unlike MD5 can use your available resources—time before user expects a response, available RAM, and additional CPU cores—to raise the attacker's costs.



* Using a secret function like $\operatorname{HMAC-MD5}_k$ for a secret key $k$ instead of $\operatorname{MD5}$ can also help—here we sometimes affectionately call $k$ a pepper—but only if there is a meaningful security boundary between the password hash storage and the password hash verification; that's a story for another day.