What is the best way to determine duplicate credit card numbers without storing them?

Question

I run a website where we mark certain accounts as scammers, and "flag" their account and all credit cards used as being bad. We don't store actual credit card values, but are storing a checksum/MD5 algorithm of it instead.

We are hitting collisions all the time now. What is the best way to store these values - non reversible, but able to do comparisons on future values.

I thought MD5 would be the best, but we've got a debate going on here...

Answer 1

A cryptographically secure hash would work. (SHA512 or SHA256 would be OK)

However, I would use a fairly secret salt that is not stored along with the cards (to prevent any sort of rainbow table attack).

PS:
Rainbow table attacks against credit cards could be particularlly effective, since the total size of the plain-text-space is quite small due to the limited character set, the fixed size, and the check digits.

PPS:
You can't use a random salt for each entry, because you would never be able to feasibly check duplicates. Salts are used to prevent collisions, whereas we are specifically looking for a collision in this instance.