Authenticating Communications Using Digital Signatures - Implementing SSL/TLS Using Cryptography and PKI - page 185

customer service purposes. The company just asks the customer for the credit
card number again, hashes it, and searches the database on the hash column.
Unfortunately, there's a problem with this approach. Although there are a lot
of potential hash values — even for a small hash function such as MD5 — there
aren't that many credit card numbers. About 10,000 trillion. In fact, not every
16-digit number is a valid credit card number, and the LUHN consistency
check that verifi es the validity of a credit card number is a public algorithm. In
cryptography terms, this isn't actually a very big number. A motivated attacker
might try to compute the MD5 hash — or whatever hash was used — of all
10,000 trillion possible credit card numbers and store the results, keyed back
to the original credit card number. This might take months to complete on a
powerful cluster of computers, but after it's computed this database could be
used against any database that stores an MD5 hash of credit card numbers.
Fortunately, this direct attack is infeasible for a different reason. This would
require 320,000 trillion bytes of memory — about 320 petabytes. The cost of
this storage array far outweighs the value of even the largest database of credit
card numbers.
So far, so good. An attacker would have to spend months mounting a targeted
attack against the database or would have to have an astronomical amount
of storage at his disposal. Unfortunately, Martin Hellman, in his paper “A
Cryptanalytic Time — Memory Trade-Off”, came up with a way to trade stor-
age space for speed. His concept has been refi ned into what are now called
rainbow tables . The idea is to start with an input, hash it, and then arbitrarily
map that hash back to the input space. This arbitrary mapping doesn't undo
the hash — that's impossible — it just has to be repeatable. You then take the
resulting input, hash it, map it back, and so on. Do this n times, but only store
the fi rst and the last values. This way, although you have to go through every
possible input value, you can drastically reduce the amount of storage you need.
When you have a hash code you want to map back to its original input, look
for it in your table. If you don't fi nd it, apply your back-mapping function, hash
that, and look in the table again. Eventually, you fi nd a match, and when you do,
you have uncovered the original input. This approach has been successfully used
to crack passwords whose hashes were stored rather than their actual contents;
rainbow tables of common password values are available for download online;
you don't even have to compute them yourself.
The easiest way to guard against this is to include a secret in the hash; with-
out the secret, the attacker doesn't know what to hash in the fi rst place. This
is, in fact, the idea behind the HMAC. Here, both sides share a secret, which is
combined with the hash in a secure way. Only a legitimate holder of the secret
can fi gure out H ( m , s ) where H is the secure hash function, m is the message,
and s is the secret.
A weak, naïve, shared-secret MAC operation might be:
h ( m ) £ s