Capital passphrases with rainbow tables?

Question

I'm currently trying to learn how rainbow tables work for a personal project of mine, but I am a little bit confused on how passphrases can be found. Here are the steps that seem do this, from the sources I have looked up online:

1. Take words, in this case passphrases, and hash them using a hash function
2. Reduce the hash, possibly to the first 5 characters
3. Repeat that possibly 100,000 times.
4. Keep the original "passphrase" and the last hash and store it
5. Repeat that for a certain amount of words/passphrases
6. For a given hash with an unknown plaintext passphrase, check if any of the hashes stored matches, if it does, start from the stored plaintext passphrase and keep hashing until you reach the passphrase hash (the one given without a plain text passphrase) and you're done. If the given hash (the one given without a plain text passphrase) does not match with any of the stored hashes, reduce the hash to 5 characters, rehash and try again.

If I got anything wrong or mixed up, clarification would be EXTREMELY appreciated. My question is how can rainbow tables find plain text passphrases, such as Password123, with a capital letter along with lowercase letters; since from my understanding hashes would look something like cb27b615a8a4e29fdf3e7c52cb09e5ef, with either all uppercase or lowercase letters? Thanks!

Answer 1

You should first understand that hashing (and modern cryptography in general) usually works with bits and bytes, and not directly with 'characters' such as 'abc'.

Before performing a cryptographic operation such as hashing or encryption, the input (in this case, the passphrase) is converted from it's encoded format (usually unicode or ascii) to bytes.

You can experiment at this website to gain an understanding of how this works. Note that the text 'abc' maps to bytes [61, 62, 63], but 'Abc' maps to [41, 62, 63].

Try calculating the SHA-256 hash of the strings 'abc' and 'Abc' at this website. You'll notice that they're completely different.

Finally, note that the output of most cryptographic functions is also returned in raw bytes, which can then be encoded to hex (such as your example above), base64, or any other number of encodings.

Encodings are completely reversible and don't use any keys, they're just a way of representing/storing binary information. Base64 is more efficient than hex encoding, and accordingly it is case-sensitive. Hex, on the other hand, is case insensitive, so 'cb27b6' and 'CB27B6' still map to the same bytes.

To answer your question, for a rainbow table to be effective, you would need to store the hash of all possible lowercase/uppercase combinations of the passphrase. It's also common to store variations of spelling, like substituting 's' for '$', and 't' for '+'.

Regarding the truncation - rainbow tables are limited by storage. To store the full hash of the many permutations of billions of inputs is expensive. Truncating the hash (ie, chopping off everything but the first 3 or 4 bytes) saves a lot of space, and if a match is found there's a strong likelihood that the full hashes will match, and it's very fast to verify.

Note that using a slow hash and salt will render rainbow tables ineffective.