Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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!

enter image description here

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!

share|improve this question
3  
Hmmm, I think you might be missing something in your explanation above, why do you need to receive the hash at all? Otherwise they could send you 50 bytes from /dev/random. is it for future communication? is it to prove that they have installed the software? –  Andrew Russell Jul 19 '11 at 9:53
    
Yep good question. The string is actually an identifier of a customer, so the server app needs to log/aggregate all interactions with that customer. So yep future use. But the string identifier needs to be obfuscated before i receive it, and the server app musn't be able to decrypt it back to the original identifier. –  SR01 Jul 19 '11 at 12:12
1  
If the clients are fully trusted then what are you protecting? What is the use for the hash value? Why can't they just send you the string without transformation? –  this.josh Jul 19 '11 at 16:39
    
@SR01, I still don't understand. Why can't the client pick a random 128-bit string and use it as his own unique identifier, and send that identifier in all future interactions? –  D.W. Jul 19 '11 at 20:27
1  
(log2(10^10) ≈ 33.2, so you have a little over 33 bits input entropy assuming uniform distribution of IDs.) You need a function that, given this input, gives you some sort of output, and for each input, the output must always be the same. This output is to be stored on the server. Having access to the output must not make it possible (at least not without considerable difficulty) to discover the original input. Is this a correct understanding of your problem? –  Michael Kjörling Jul 21 '11 at 12:12
show 8 more comments

4 Answers

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.

share|improve this answer
add comment

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 1010 × 1,000,000 = 1016 ≈ 253 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 1016 hash operations per customer ID he wants to recover. To recover all N customer IDs, an attacker has to do 1016 × N hash operations; compare to solution #1, where only 1016 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).

share|improve this answer
add comment

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

share|improve this answer
    
Thanks Andrew! My understanding of regular SSL is that if i sign the client certificates, then i will be able to decrypt any encrypted message the client sends me; i don't want this. I want to be potentially be able to 'sign' the client certificates, but then only be able to tell whether any two or more encrypted/hashed messages from different clients were created from the same plain text (and never be able to decrypt the message on the server). Are you saying this is trivial? If so great i would really appreciate a link! :) –  SR01 Jul 19 '11 at 14:11
    
Hi @sr01, just use the client's key signature, don't worry about the hashed secret string. –  Andrew Russell Jul 19 '11 at 21:32
    
Ok cheers will look in to it! –  SR01 Jul 20 '11 at 1:11
add comment

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.

share|improve this answer
    
Yeah i have read through a lot of the wikipedia stuff. My understanding of most of the public/private key algorithms is that they allow the cipher text to be decrypted at the other end (which i can't have). And regular hashing functions are fallible in the scenario that i have. But yeah surely in the same way public and private keys have mathematical relationships, a hash could be generated that has a mathematical relationship to another hash that i could then detect on the server... –  SR01 Jul 19 '11 at 12:14
    
@Michael, I don't know why you think this helps. Your solution is flawed. It is still vulnerable to dictionary-search attacks by the server (exactly to the same degree as the simple scheme without encryption mentioned in the question). –  D.W. Jul 19 '11 at 20:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.