Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.
Sign up to join this community
We are looking to allow users to log on with a smart card. The smart card reader can read the smart card ID and send it to us.
We are, however, not allowed to store the smart card ID. Not in plaintext, not in a reversible encoding. An irreversible hashing is allowed.
Then again, we need to make sure that each ID hashes to a unique result, as to avoid collisions.
How can we satisfy both unique and irreversible properties?
For a hash to be collision free, each unique input would need to map to a unique output. If each output is unique, that means it can be reverse-mapped to a unique input. That would not be hashing, that would just be an encoding. Collision-free and non-reversibility are mutually exclusive by definition.
The important point is how likely a collision is, and the answer for modern hashes is negligibly unlikely. If the output key space is larger than the input key space, you're extremely unlikely to ever find a collision, and even if it's not it's still so unlikely as to not be worth considering in the real world.
I would guess though that those smart card ids aren't very complex, likely decimal numbers all of the same length (e.g. 1234567890). That means there aren't that many possible inputs and it's probably possible to calculate the hashes of all possible ids in a feasible amount of time, creating a lookup table to reverse the hashes. If that's the case, you'll want to be using a slow hash like bcrypt, scrypt, PBKDF2 etc. to make this infeasible.
The more I think about it the less the requirement makes sense. The secret here should be between the card and the reader, and the trust needs to be between the reader and the system it's connected to. Why is it a security problem if the id of a card is known? What can somebody do with this id if he obtains it? If the answer is that the id is a secret and somebody can do whatever he wants if he knows the id number, that's poor security. The security here should come from the fact that one needs to have physical possession of the card, which means the secrets are all between the card and the reader. Beyond that there's only an authenticated user with an id, which is a simple necessity to make the system work.
Use 512-bit hash function like SHA-2-512 and when adding a "smart" card to the database, check if the hash already exists. In an EXTREMELY UNLIKELY case that it does, don't use the card. Even with trillions of unique IDs, you are unlikely to have a single collision.
As @deceze said, a cryptographic hash function cannot also be a perfect hash function for your key space.
So, instead of requiring all results to be unique, you should concentrate on dealing with collision properly.
There are many options for this (lookup the wikipedia article on hash tables, it is pretty well written) but they all depends on what you didn't tell us: what you want to do with that ID.
If you want to use it to identify a user using that ID and you have no other element, then there is, in theory, no way to prevent a collision to occure while still relaining the non-reversibility property of the hash. All you can do is reduce the chances of collision if you deem them too high (but, as @Matrix noted, the chances of a collision is really low and should be checked before assigning a card).
If you have any other property provided, for instance a hash password, then you could use the result of the hash to identify all potentially valid rows and then use a more expensive lookup (for instance, checking the password provided against each of these rows) to identify the correct one.
In practice, however, I wouldn't worry too much about collision unless you're going to issue truly high numbers of cards (millions).
y = g^x mod p with large p is a simple example. In practice there is little reason to choose them over a normal hash.
Nov 26, 2013 at 9:46
Consider this graphic before worrying about the chances of a collision. Bitcoin addresses are the hashed output of a key, which in your case would be the smartcard ID. As you can see, the range of addresses is rather large and therefore a collision quite unlikely.
In fact, it is considered so unlikely that addresses are generated without fear that anyone else might have generated the same address, even though this could cause significant financial loss for a user this happened to.
Therefore you need to (theoretically) pick one, unique or irreversible. However, consider it's extremely unlikely you have to worry about unique being an issue, so simply pick a sensible hash algorithm such as SHA-512 which has a very large pool.
