I have to synchronise small sets of data between two or more systems over an insecure network. First I have to check that the other system has the same unique identification information for the data set, but without giving away the identification data if it doesn't. The unique identification strings are between 12 and 40 bytes long. I am thinking of using a one-way hash to individually hash a group of unique identifiers, send that to the remote system and have the remote system use the same hash salt to hash the same identification data from its datasets (it will have in the order of 1000 sets), compare the received hashes with its computed hashes and send back the identifiers that match (encrypted but not hashed). An obvious requirement is a very low risk of a hash collision to prevent data leakage in either direction.

What is the best hash algorithm to use for this? Is it OK to send the hash salt with the hashed data? Can I use one salt for several identifiers, or do I need to have a unique salt for each identifier?

2 Answers 2


personally I would just use SSH with public/private keys for a job like this. that employs an mechanism to not send over any identifying features (excluding hostname and possibly username, not sure on that) and is easy to setup, and easy to use.

any of the SHA algorithms would fit the bill, its 'better' to not send over the salt with the data (separated channel would be sufficient) and as for 1 or more salts, that depends on how secret much your information be kept.

  • The strings that are being compared are unique addresses to confirm that the same individual is known to both systems. It is not just the communications path that I need to protect, I need to ensure that I do not give the remote system addresses it doesn't already know. I will protect the communications path with SSH. Thanks for the recommendation on the salt.
    – Tom Foale
    Jan 6, 2015 at 10:39

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).

  • Thanks for a very detailed response. The threat model includes a compromised or untrustworthy Responder as well as a compromised Querier - your last threat, and all of the others apply as well. There can be several Queriers and several Responders - it is more of a peer-to-peer application than client-server.
    – Tom Foale
    Jan 6, 2015 at 11:13
  • SSH assumes that the server you are connecting to is entitled to whatever information (credit card data etc) you are sending once the secure connection is established, but I want to confirm that the identityholder is known to the responder first by checking that it has two specific items of information before I send any further data. A hash of the two items hopefully would allow the responder to confirm that it has the data by comparison without knowing what that data is if it has no matches. I limit the rate at which queries can be made by any one querier.
    – Tom Foale
    Jan 6, 2015 at 11:15
  • Regarding your last point, I can have a trusted third party provide a one-use common salt with good entropy to both the Enquirer and Responder on request. Both queriers and responders will have public/private key pairs for mutual authentication.
    – Tom Foale
    Jan 6, 2015 at 11:21
  • I got a feeling some people are confusing SSL (Secure Socket Library) and SSH (Secure Shell) these are NOT the same thing. SSH does use (among others things) SSL, but it use a totally DIFFRENT form of PKI than SSL (no CA for example, but server/client need to 'known' eachother)
    – LvB
    Jan 6, 2015 at 12:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .