First, I must give an obligatory bump:
Know your threat model. You cannot possibly secure your system unless you have a threat model describing the threats you are preventing. A script-kiddie scanning you is very different from the US gov't scanning you, which is also very different from a government actually trying to get your data. Without a threat model, secure algorithms are almost pointless.
I second Lawri's suggestion to use SSL. It drastically decreases how much you have to think when proving you can defend against your threat model. It also provides the encryption you need for the next step.
However, I'll assume that for some reason SSH is not accessible. Perhaps its a performance thing.
What does your threat model contain? Here's my guess
- Defining two parties: the Querier which initiates the query/response pattern, and the Responder which answers.
- Replay attacks: both a snooper replaying the transmission and a secure node pretending it still has the identifier on its side by retaining the hashcode for that identifier.
- Brute force attacks: failing to observe any useful information, the attacker blindly sends requests
- Malicious Responder: if you ask someone for data, you may reveal that you probably have it.
- Attacks on the underlying network: Consider xauth, which has a known troublesome attack where an attacker creates fraudulent TCP packets to fake authentication.
- Attackers have no physical access to the machines, nor can they get remote access with sufficient privileges to read the identifiers right out of your files.
The last one I'll have to skip in this answer, because I don't know enough about your underlying network. However, because you chose to implement your own security rather than using a standard tool like SSL, you WILL have to pay attention to it.
The replay attacks show how you have to handle the salt. If the Querier can generate their own salt, then there is no way for the Responder to tell the difference between a valid request and a replay. At a minimum, the Querier should start the session, and the Responder should pick the salt. It should be a big salt (I'd just use a 64-bit random number, myself). This way, a replay attack is impossible because each Responder will have a different salt.
Now we can see that the salt can be sent in plaintext, because we can see that the salt has no use except for salting requests in this session. No replay potential, and no information has been sent regarding the identifiers. When the hashed identifiers are sent to the Responder, in theory the one way function protects them...
... but by choosing to not use a standard software suite, you have now put yourself at risk. You have to choose a hash, and you don't have a massive base of security experts warning you when the hash algorithm is breaking like SSL does. Make sure you pick a good one
Now, as for the number of salts, one salt is sufficient. We can use the threat model to prove that the only reason we are salting is to prevent replays. Without the threat model, this is not clear. The threat model also makes it clear that even a defecting Responder can't figure out what a Querier requested, because all they have to work with is a salt and a hash or does it?. A malicious Responder could always offer the same salt, and have a rainbow table of salted identifiers to work with.
Without a threat model, this issue would have slipped past. Now we see that the salt needs to have input from both Querier and Responder, not just the Responder. The Querier needs to send half of the hash, and the Responder provides the second half. Perhaps they both send a 64-bit random number. Now, with our threat model, we can see that this does not compromise the salt any more than it already was, but prevents a malicious Responder from getting information with a rainbow table.
For a final test: how random are your identifiers? No matter what system you devise, it will be possible to attempt to brute force these identifiers if they don't have enough bits of entropy. If they don't have enough bits of entropy to them, no system can protect them if an attacker brute force queries...
... which leads right back to SSL. SSL has a certificate based system which you can use to reject brute force attacks from any node which does not have a valid trusted certificate. It is trivial to guarantee these have enough bits of entropy (if you generate them with standard SSL tools, they will be more than secure enough).