0
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please correct me if i'm wrong, but it is my understanding that once you found a hash that matches the original hash, start truncating and hashing from the beginning plaintext for that table until you find the original hash with a plaintext. If I wanted to find a passphrase like Password123, doesn't that exact combination of characters and numbers need to be part of the first 11 truncated characters of a hash? $\endgroup$ – DecanalGossypine27 Aug 16 '18 at 21:11
  • $\begingroup$ Rainbow tables are for looking up hashes (and the plaintext the hash maps to). So you wouldn't be searching for 'Password123' directly. The most likely scenario would be that a password has been stored as a hash in some database, and you want to know which password that hash represents. So you take the hash (from the compromised database), truncate it, and look for the truncation in your rainbow table. For each match, hash the plaintext (stored along with the truncated hash) and compare it to the hash you're searching for. If it's they match, then you've found the password. $\endgroup$ – hunter Aug 17 '18 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.