Hash/Digest of string; multiple clients and reverse lookup must be impossible

Question

Ok so i need a technique (could be a system or just an algorithm) to generate a hash/digest of a string on a client app without me (admin of a server app) being able to determine what the original string was. The twist is that i know the format of the string so it would be quite easy to generate a lookup table of SHA, MD5 etc values and determine the plain text.

The other twist is that each client app is maintained by a separate company, so any key (or salting) based methods obvious to me would need a third party to co-ordinate the keys/salt values without them ever getting back to me.

I'm thinking some sort of setup where each client has/generates a key which will encrypt the string, and i have a key that can tell if the encrypted string would have come from the same plain text value - even though each digest is different - but my key will not actually be able to decrypt the digest.

Now i have a feeling that there is a solution perhaps in the vein of public/private key sort of setup but im a rank rookie when it comes to cryptography so any help in potential solutions or even terminology to search for or help describe this type of problem would help me greatly. I would like to avoid having to have a third party supply and maintain keys also. Cheers :)

(I have a workflow diagram if that will help which i will try and link to clarify the scenario if need be)

---

Edit: So i think i can post pics now, here's a diagram which illustrates the scenario i need to solve!

The client apps are numerous. There is no need to authenticate them with the server app; they are fully trusted. The clients have about a second to hash the string with say standard desktop specs. All the server needs is to receive the hash from the client app and store it in a table with a timestamp so i can determine when the same visitor id logs in across any of the client apps.

Thanks for help so far!

Answer 1

You can't know the ID but you MUST uniquely identify him? Then why not just setup another system to provide a secure identity(pubkey pair) for a given ID? That system will be the lookup-DB in case of tampering but also the weak point in the privacy of your system. If you don't need that recovery mechanism, just don't create that lookup-DB in the first place..

Or, if you don't really care which customer uses your service but only that it is SOME valid customer, take a look at anonymous authentication using zero-knowledge proofs. A simple solution might also be to use blind signatures upside down: The server distributes valid signatures to the customer during enrollment and the customer randomizes them before authentication. In that approach the customer can create new aliases by randomizing a signature you gave him, but you can always assure that the signature is one you generated at some point.

Answer 2

Problem statement. Here is my understanding of the problem you want to solve. Each customer has a 10-digit customer ID, which is privacy-sensitive and which you don't want stored or transmitted to the server: but you do want to be able to uniquely identify the customer. Got it.

Solution #1. Here is a fairly simple solution. Generate a cloaked identifier by iteratively hashing the 10-digit customer ID many times, say one million times. The number of times you iteratively hash it is a parameter that you can choose. I suggest you choose the parameter so that the entire iterative hashing process takes about one second or so. We are trying to make it expensive to recover the original 10-digit customer ID from the cloaked identifier.

When you enroll a new customer, you generate their cloaked identifier and store the cloaked identifier in the server app's database. When a customer installs a client app, the client app gets access to the 10-digit customer ID and iteratively hashes a million times to construct the cloaked identifier. This process takes about a second, but the client app never needs to do it again: it can store the cloaked identifier permanently.

When the client app wants to talk to your server app, it should connect to your server app over SSL/TLS and transmit the cloaked identifier over the SSL/TLS connection. The server can verify the validity of the cloaked identifier and use it to identify the customer. Your server app should use a standard SSL/TLS certificate, and the client app should verify this certificate.

Security analysis of solution #1. Solution #1 is a bit more secure than storing the 10-digit customer identifiers on the server, though please understand that it is not perfect. Let's say you have N customers and hence N cloaked identifiers stored on the server. An attacker who steals a copy of the server's database can recover all of the original customer IDs by building a mapping between 10-digit numbers and their million-fold hashes. It will take the attacker 10¹⁰ × 1,000,000 = 10¹⁶ ≈ 2⁵³ hash operations to build the entire mapping. This computation is feasible, but not trivial: it is not something you can do over the weekend on your home machine (it is more like hundreds of CPU-years of computation, so it is achievable with a large cluster, and probably achievable for thousands or tens of thousands of dollars, but not super-easy). Once the attacker builds the mapping, he can easily recover all N customer IDs.

This might be good enough for your purposes. If it is not, here is one slight improvement:

Solution #2. Don't store the cloaked identifier on the server; instead, store a salted hash of the cloaked identifier. The cloaked identifier is defined as before. But now, when you enroll a new customer, you generate the cloaked identifier, you generate a random salt for the customer, and you store (salt, Hash(salt, cloakedid)) on the server. You don't store a copy of the cloaked identifier. When the user installs a client app, the client app gets the 10-digit customer ID, computes the cloaked identifier, and sends the server a special request saying "I am new; here is my cloaked identifier, can you please send me my salt?" over a SSL/TLS connection to the server. The server takes the cloaked identifier I from the client, and for each pair (salt, h) in its database, it checks whether Hash(salt, I)=h. If yes, then it has found the matching entry for that customer and sends the customer's salt back to the client app. (The server does not retain the cloaked identifier.) The client app now stores the salt and the value Hash(salt, cloakedid). When the client app connects to the server in the future, instead of sending the cloaked identifier, it sends the value Hash(salt, cloakedid). This is sufficient to identify the customer.

Security analysis of solution #2. This is more secure than solution #1. An attacker who gets his hands on a copy of the server's database has to do 10¹⁶ hash operations per customer ID he wants to recover. To recover all N customer IDs, an attacker has to do 10¹⁶ × N hash operations; compare to solution #1, where only 10¹⁶ hash operations are needed.

On the other hand, solution #2 is more complicated and thus may be trickier to implement and deploy. Also, the server has to do a bit more work each time a new customer installs a new client app (the server has to do N hash operations each time a customer installs a new client app).

Answer 3

OK a bit of guesswork is required here, mapping your goals to what crypto can do.

Goal: To have an untrusted client app prove that they have a valid string.

Probably not possible without the "secret string" loaded onto the server, or an embedded key in the string. Effectively the string becomes a "public key", and the server side uses the "private key" to decrypt any message sent.

Goal: To have an untrusted client app provide a string that can be determined to be distinct from other apps talking to you.

Easier to do as long as there is enough randomness in the key string, just use a secure password hashing algorithm with a lot of repetitions (see the libraries).

Thus the client app will have to do a lot of work in order to hash the string, so that you as the server admin cannot brute force all the possible input strings feasibly.

Goal: To increase your server side security by not requiring the "secret strings" as part of the server infrastructure.

You can use the feature above with password hashing, and when necessary investigations can match the secret string with the hash offline for the few cases that need it.

Goal: Do you need the separate companies below to be validated for use on your systems.

The other twist is that each client app is maintained by a separate company, so any key (or salting) based methods obvious to me would need a third party to co-ordinate the keys/salt values without them ever getting back to me.

Standard https security (more generically called SSL or TLS) can be configured to solve this problem. Each of the companies create their own certificates, send them to you for signing, then you send them back. Then both your https server and their client software are configured to require those signed certificates only. Note that this preserves secrets well because the private keys of all systems involved need never be disclosed to other parties (this is the key to the magic in the system).

Answer 4

Some implementation of public key cryptography sounds like the way to go. Each client has access to "your" public (encryption) key, whereas only you have access to the corresponding private (decryption) key. Encrypt to the public key, and (assuming adequate key length and no mistakes in the implementation) only using the private key can the string be decrypted. No third parties involved, and very little coordination required.

You can either encrypt a hash, or (probably more practical in this case, unless the strings are long which doesn't seem to be the case) the whole string.

If this is for a public API, you can publish your public key along with the API specs. Again, as long as you use sufficiently long keys and the implementation itself is sound, the security risk of exposing your public key will be negligible.

http://en.wikipedia.org/wiki/Public-key_cryptography is probably a good place to start for learning about all this.