4

I was reading a book called Introduction to network security theory and practice, and I found the following paragraph:

Rainbow Tables

A rainbow table is a table of two columns constructed as follows: let be a function that maps an encrypted hash of a password to a string in the domain of possible passwords. This function is referred to as a reduction function, for the length of a password is typically shorter than the length of its encrypted hash value.

I noticed the word typically, but I was just wondering:

Does encrypted_hash < password mean that it will be easier to find a way of de-crypting the hash ?

Why is that? Why not?

Lighty
  • 2,368
  • 1
  • 23
  • 36
Dex
  • 143
  • 5

4 Answers4

7

First things first: this is NOT encryption. This is hashing. If your book talks of "encrypted hash" then that book is confused, and thus confusing. Notably, hashed passwords are never "decrypted", since they are not encrypted in the first place.

A cryptographic hash function offers a fixed output size. In the case of passwords, one needs to do something specific called "password-hashing", which has its own theory (see this answer for details). However, the main principle is still there: when verifying an incoming password, the password is hashed into a value x, and that x is compared to the value that was stored. If the password is the right one, then the same x is obtained. However, if a wrong password was entered, another value x' is obtained, which is distinct from x with high probability.

This is the important point here: an attacker could still get (very) lucky and instead of sending the right password, he could theoretically stumble on another, distinct password that, by pure chance, would yield the same hash value.

Of course, we do not want such a thing to happen, and the best way to make that event utterly improbable is to make these values x (i.e. output of the hash function) large enough for bad luck not to occur in practice. Existing hash functions have an output size which is typically 16 bytes (128 bits) or more. This also applies to password hashing functions; e.g. bcrypt outputs 192 bytes.

(Compounding the effect is that hash outputs are binary, but often encoded in Base64 before storage in database, which increases the size; also, password hashing functions need some extra parameters, e.g. a salt, which, in some functions, are also encoded in the output, further expanding the output.)

User-chosen passwords rarely exceed a dozen characters in length, so, generally speaking, the hash output will be larger. However, hash functions can use large inputs, so there is no intrinsic reason why hash outputs should always be larger than passwords. It just happens that we need, to thwart the "lucky attacker" described above, an output size which is "large enough", and that "large enough" is larger than the average size of passwords chosen by human users.

Community
  • 1
Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
3

Rainbow tables are an element of TMTO (Time-Memory-Trade-Off) by which password hashes are precomputed, but not stored as the hash itself. To store a password in such form, you need a starting point T0. On T you apply the password hash function and get H. Now the reduction function is applied to get a new T1. This procedure is repeated a defined time and only T0 and Tn (the last node) are stored in the table. In an attack, you get the password hash from the password DB, apply the reduction function and check if it equals a known Tn. If so, you start that line and compute the password hash of T0. After each hash you check if the result equals the hash you want to know from the database. If that is not the case, you apply the reduction function and continue computing through like in the initial generation.

Why is the length of a password typically shorter than the length of a hash? Well that's because humans are really bad at memorizing passwords. Even when you let them chose a password with no complexity, a lot chose 'welcome' or 'password' which are 49, respectively 56 bits long. But even with MD5 your password hash would be 128 bits and with SHA2 most likely 256 or even 512 bits long. So it's safe to say a password is typically longer than a password hash.

Zonk
  • 458
  • 2
  • 6
1

This has more to do with the nature of humans, which often choose short passwords which can be remembered. A lot of effort is made to store such short (weak) passwords in a safe way, key-stretching is one of the measures to handle short passwords, it wouldn't be necessary for long and strong passwords.

The output of a hash must allow for enough combinations, so an attacker cannot build a lookup-table with all possible outcomings, and to avoid a lot of collisions, this requires a minimum length. So the length of the password is typically shorter than the length of its hash.

martinstoeckli
  • 5,149
  • 2
  • 27
  • 32
1

When a password has a higher entropy than the hash, then it becomes weaker by hashing it. The reason is that when a brute-force attack is performed, it becomes more likely to find a random collision than to find the original password, and a random collision would be accepted just like the password would.

However, most hash functions commonly used for hashing passwords have an entropy which is many orders of magnitude higher than any password a normal human being can remember (except for a few extraordinary people).

Philipp
  • 48,867
  • 8
  • 127
  • 157