Key space (cryptography)
In cryptography, an algorithm's key space refers to the set of all possible keys that can be used to generate a key, and is one of the most important attributes that determines the strength of a cryptosystem.
To prevent an adversary from using a brute-force attack to find the key used to encrypt a message, the key space is usually designed to be large enough to make such a search infeasible. On average, half the key space must be searched to find the solution.
Another desirable attribute is that the key must be selected truly randomly from all possible key permutations. Should this not be the case, and the attacker is able to determine some factor that may influence how the key was selected, the search space (and hence also the search time) can be significantly reduced. Humans do not select passwords randomly, therefore attackers frequently try a dictionary attack before a brute force attack, as this approach can often produce the correct answer in far less time than a systematic brute force search of all possible character combinations.
If a key were eight bits (one byte) long, the keyspace would consist of 28 or 256 possible keys. Advanced Encryption Standard (AES) can use a symmetric key of 256 bits, resulting in a key space containing 2256 (or 1.1579 × 1077) possible keys.
In the DES block cipher, 56-bit key is used, resulting in a relatively small key space of size 256 (or 7.2058 x 1016), which was demonstrated in 1998 could be searched exhaustively in 56 hours with a desktop computer.
- "CISSP Exam Preparation". http://www.flashcardmachine.com/: Flashcard machine. Retrieved 2010-03-11. "All possible values that can be set to generate a key."
- "Q: What is a "keyspace"?". http://www.experts123.com/: experts123. Retrieved 2011-03-11. "A "keyspace" is the theoretical set of all possible permutations of a key, given a set key size."
- "Flash Card Machine". "Question: Why do the statistics measure estimate time to having 50% of the keyspace searched? Answer: Because we don't know where in the keyspace of 72,000,000,000,000,000 the right answer is. On the average, only 50% of the keyspace needs to be searched before a solution is found."
- Congressional Record. 17 144. United States Senate. October 7, 1998 to October 9, 1998. p. 25124.