Algorithm for assigning a unique series of bits for each user?

Question

The problem seems simple at first: just assign an id and represent that in binary.

The issue arises because the user is capable of changing as many 0 bits to a 1 bit. To clarify, the hash could go from 0011 to 0111 or 1111 but never 1010. Each bit has an equal chance of being changed and is independent of other changes.

What would you have to store in order to go from hash -> user assuming a low percentage of bit tampering by the user? I also assume failure in some cases so the correct solution should have an acceptable error rate.

I would an estimate the maximum number of bits tampered with would be about 30% of the total set.

I guess the acceptable error rate would depend on the number of hashes needed and the number of bits being set per hash.

I'm worried with enough manipulation the id can not be reconstructed from the hash. The question I am asking I guess is what safe guards or unique positioning systems can I use to ensure this happens.

Answer 1

So you're trying to assign a "unique id" that will still remain a unique id even if it's changed to something else?

If the only "tampering" is changing 0's to 1's (but not vice-versa) (which seems fairly contrived), then you could get an effective 'ID' by assigning each user a particular bit position, set that bit to zero in that user's id, and to one in every other user's id.

Thus any fiddling by the user will result in corrupting their own id, but not allow impersonation of anyone else.

Answer 2

Your question isn't entirely clear to me.

Are you saying that you want to validate a user based on a hash of the user ID, but are concerned that the user might change some of the bits in the hash?

If that is the question, then as long as you are using a proven hash algorithm (such as MD5), there is very low risk of a user manipulating the bits of their hash to get another user's ID.

If that's not what you are after, could you clarify your question?

EDIT

After reading your clarification, it looks like you might be after Forward Error Correction, a family of algorithms that allow you to reconstruct altered data.

Essentially with FEC, you encode each bit as a series of 3 bits and apply the "majority wins" principal when decoding again. When encoding you represent "1" as "111" and "0" as "000". When decoding, if most of the encoded 3 bits are zero, you decode that to mean zero. If most of the encoded 3 bits are 1, you decode that to mean 1.

Answer 3

Assign each user an ID with the same number of bits set.

This way you can detect immediately if any tampering has occurred. If you additionally make the Hamming distance between any two IDs at least 2n, then you'll be able to reconstruct the original ID in cases where less than n bits have been set.