Generating a token that I can prove I generated

Question

I need to generate random tokens so that when I see them later I can determine absolutely that they were actually generated by me, i.e. it should be near impossible for anyone else to generate fake tokens. It's kind of like serial number generation except I don't need uniqueness. Actually, its a lot like a digital signature except I am the only one that needs to verify the "signature".

My solution is as follows:

1. have a secret string S (this is the only data not in the open)
2. for each token, generate a random string K
3. token = K + MD5(K + S)

to validate the token is one I generated:

1. split incoming token into K + H
2. calculate MD5(K + S), ensure equal to H

It seems to me that it should be impossible for anybody to reliably generate H, given K without S. Is this solution too simplistic?

Answer 1

That's not too simplistic, that's certainly a valid way to implement a simple digital signature.

Of course, you can't prove to anybody else that you generated the signature without revealing your secret key S, but for that purpose you would want to use a more sophisticated protocol like PKI.

Answer 2

Just to nitpick a bit you would prove only that whomever has access to S could have generated the token. Another little detail: use a better hash, like SHA256. Because if Mallory is able to generate a collision, she doesn't even need to know S.

Answer 3

Check out HMAC.

Answer 4

The solution you presented is on the right track. You're essentially performing challenge-response authentication with yourself. Each token can consist of a non-secret challenge string C, and HMAC(C, K) where K is your server's secret key.

To verify a token, simply recompute the HMAC with the supplied value of C and see if it matches the supplied HMAC value.

Also, as Vinko mentioned, you should not use MD5; SHA-256 is a good choice.