Search Key Space

Search key space is all possible keys for a password. The size of the search key space is important for estimating the time required to guess a password using a Brute Force attack.

The size of the key space is the number of possible characters for each position in the key raised to the power of the key length, or total number of characters.

Possibilities count ^ Key length

Imagine a combination lock with three wheels that rotate to choose different numbers. Each wheel has the numbers 0 through 9, for a total of 10 possible choices per wheel. Since there are three wheels, there are 10 x 10 x 10 combinations, or a key space size of 1,000.

A larger key space means more time is required to test every possible combination. Measuring the size of the key space provides a metric for measuring the relative strength of a password.

Larger character sets increase key space

Allowing more characters in each "position" of a password increases the key space, and makes Brute Force attacks take longer.

For example, using only 5 characters:

  • Lowercase letters: 26^5 = 11 million combinations
  • Upper and lowercase letters: 52^5 = 380 million combinations
  • Upper/lower + digits + 10 symbols: 72^5 = 2 billion combinations

Longer key lengths increase key space

Having longer key lengths (more characters) increases the key space, and makes Brute Force attacks take longer.

For example, using 26 possible characters:

  • 3 characters long: 26^3 = 17,576 combinations
  • 5 characters long: 26^5 = 11 million combinations
  • 8 characters long: 26^5 = 208 billion combinations

Key length has greater effect than character set size

It is far more important to have longer keys than it is to allow more characters. Key length provides exponential increases.

Compare these two password schemes. The first uses significantly more characters. The second uses only a slightly longer key.

  • 72 possibilities, 3 characters: 72^3 = 373,248
  • 26 possibilities, 5 characters: 26^5 = 11,881,376
Fork me on GitHub