Credit cards, rainbow attacks, and why it only takes one bad implementation

A ramble.

All credit cards numbers have to meet a certain check (mod-10) in order be be valid. I just wrote a little checker to make sure of this, but 10% of all randomly generated 16-digit numbers will pass a mod-10 check (funny how that works out, huh). I’ll probably find out I messed up.

Okay, so there are 16 digits in a credit card, 10 possibilities per, so 10^16 possible numbers. But if only 10% are valid, and you can know that in advance, a list of all possible, valid credit card numbers would contain 10^15. That’s a petabyte of storage, and would cost you a fair (but not astronomical) amount of money to put together. Back when I started working on credit cards and fraud stuff, it was essentially impractical for someone operating on their own to pull that off.

The actual number, though, isn’t even 10^15. It’s much, much smaller, because the first digit or two are card identifiers, then you’ve got four digits of your card identify the issuing bank and whatnot. So the first six digits aren’t actually random at all, and that dramatically contains the number space you’re working with. It’s a whole ANSI standard and everything.

So it’s actually…. 4*some limited number I could work out if I had enough time*10^10. Now we’re getting down to something you can pretty easily stash.

Anyway, there are two things I’m going to gloss over: encryption and hashing. Encryption, you use a key to take a piece of text and turn it into something you can bring back using the same key. In hashing, you put a chunk of whatever through a mathematical function and out the back end comes some crazy number. You can’t derive the original from that number, even knowing the function. (standard caveats apply)

This is used for all kinds of cool stuff, like signatures for files. If I publish an document along with the hash you can verify, and as long as I use a decent method, it’s essentially impossible for someone else to modify that document and get the same hash number to come out the end.

But let’s say you get a list of hashed passwords. You know that all passwords are eight letters long, lowercase. You can generate all 8^26 possibilities, run that same mathematical function on them, and then compare the results to what you have. Tada! You have everyone’s password.

Which is a great argument for long, complicated passwords (I’ve ranted about that before, though) — you should make your password as complicated as you can at every place that requires one.

I know you won’t. It’s okay.

Ah, so anyway, here’s the thing — what if, for whatever reason, someone uses your credit card number for verification purposes? And they store… a hash to do the compare with?

Unless they’re doing something called salting (and the attacker doesn’t figure that out), you’re toast. Same attack: the guy with the huge list of valid numbers can go through and say “for each of these potentially valid numbers, run them through a function and go see if there are any matches in this list I’ve got here.”

Whirr…. running that hash function on 10^15 (or whatever the actual number turns out to be) takes a while, but not as long as you might think, and then… tada! All the credit card numbers.

And after you’ve got those, it’s open season.

Now, this is still a pretty tough attack to make, and it’s almost certain that if an attacker can get that far, there will be more lucrative means of getting card numbers. And it’s also true that an attacker sophisticated enough to make this attack is almost certainly going to have many, many more lucrative targets that aren’t as secure.

But I kept thinking about this today: how many companies can look up your payment or account history based on your credit card number? Either they’re storing the number unencrypted to do lookups, they’re doing something clever, or… they’re using hashes. And if they’re using hashes, it might be clever, or pretty much as good as plaintext.

If you’re a customer of the companies I’ve worked at, you will be happy to know that they’ve all been clever.

If you’ve worked at a large company, where all kinds of ridiculous and bizarre decisions get made, decisions that are indefensible almost at once, how unlikely does it seem that there’s someone out there doing this?