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.

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?

share|improve this question
1  
How many possible IDs are there? Because I'd think it's probably just a number from, say, 0 to uint_max (~4 billion). This is trivially searchable with any hashing system, and is thus pretty useless. Even if this hashing satisfies requirements from higher up, you should think about what you really want to achieve. If you really think this increases security, you should use something that increases the cost to search, like pbkdf2 or bcrypt with decent parameters. –  Luc Nov 26 '13 at 8:52
1  
@Luc If I understand this right, he's trying to perform a lookup based on that ID, not validate it for a password. pbkdf2 (or any function that uses a salt) will not allow him to do that. The remark about the potential futility of using a non-reversible hash given the small key space of these card IDs, however, is a good one - assuming these IDs are sequential. –  Stephane Nov 26 '13 at 9:36
1  
Just use a 256 bit hash. Probability of collision is negligible for those. –  CodesInChaos Nov 26 '13 at 9:42
1  
@Stephane Yes he just needs to look it up I guess, but why hash it at all? If you're going to hash "irreversibly", at least make sure it's really non-trivial to reverse. You can just use a static salt; it's the work factor that it's about. Also, any good hashing algorithm produces good pseudorandom output regardless of whether the numbers are sequential or not. –  Luc Nov 26 '13 at 11:29
1  
This seems like a poorly-designed system. Why doesn't the smart card contain any non-secret elements you are allowed to store? Why does it send the secret element rather than doing a zero-knowledge proof that never allows the host system to see the key? This is not how smart card systems normally work. Either you are misusing the cards, or they're not actually smart cards but rather magnetic stripes (i.e. dumb cards). –  Random832 Nov 26 '13 at 15:48

4 Answers 4

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.

share|improve this answer
    
What would happen if I would actually use encoding? Encode using the public key, and throw the private key away. If I re-encode the same input later with the same key, does it give the same result? Could I use encoding as hashing? –  Konerak Nov 26 '13 at 9:47
    
That would basically amount to hashing with a static salt. And yes, adding a salt is a good idea if you were to hash at all. It's still very debatable whether it's the right approach to begin with. If the primary identifier is supposed to be kept secret from you, it's not really an identifier. Maybe you're just looking for a secondary identifier or token to be exchanged between your systems instead of the primary smart card id. –  deceze Nov 26 '13 at 9:54
    
Hmm I'll investigate if there is some other data we can pull off the smart card. Would taking two hashes even further reduce the chance on collissions? Calculating both, Hash1(A) and Hash2(A), so that if Hash1(A) = Hash1(B), the chance for Hash2(A) <> Hash2(B) is big enough? –  Konerak Nov 26 '13 at 9:57
2  
You're not going to add more entropy by hashing more. That's essentially what PBKDF2 does, it just repeats the hash many times to stretch it (to make it slower). Doesn't mean the input is going to become more unique with each hash. Yes, if you stored, say, the SHA1 and the SHA256 hash of a value it's unlikely that two different inputs would produce a collision in both hashes at the same time. But it's already unlikely for one value to produce a collision. –  deceze Nov 26 '13 at 9:58

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.

share|improve this answer

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

share|improve this answer
1  
There exist injective one-way functions. 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. –  CodesInChaos Nov 26 '13 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.

enter image description here

share|improve this answer
    
+1 I forgot where I heard it, but basically it's more likely for an extinction level event to occur in the next second (e.g. meteoroid hitting earth, in which case you won't care anymore) than a collision in a Bitcoin address to occur. ;) –  deceze Nov 26 '13 at 15:12
    
"How many are there" is misleading thank's to the birthday paradox. For example a 128 bit hash has a huge amount of possible results, still it's collision resistance of 64 bits is dubious. For non security critical hashes it's different still, as you'd estimate the collision probability as 2^b/n^2 where b is the size of the hash in bits and n the number of items. –  CodesInChaos Nov 26 '13 at 15:12
    
@deceze Collisions in bitcoin addresses are not that hard to find. Takes only about 15 times the total work of the bitcoin network so far (at least for the new address format, slightly higher for old addresses). But luckily they're irrelevant to security. They only need to be multi-target second-pre-image resistant, which they are. –  CodesInChaos Nov 26 '13 at 15:19
    
@CodesInChaos I suppose the anecdote was meant to illustrate the likelihood in practice, not as a mathematical absolute. –  deceze Nov 26 '13 at 15:28

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.