Encyclopedia  |   World Factbook  |   World Flags  |   Reference Tables  |   List of Lists     
   Academic Disciplines  |   Historical Timeline  |   Themed Timelines  |   Biographies  |   How-Tos     
Sponsor by The Tattoo Collection
Weak key
Main Page | See live article | Alphabetical index

Weak key

In cryptography, a weak key is a key which when used with a specific cipher, reduces (or even in some cases, eliminates) the security expected of the cipher. That is, cryptanalysis of that message becomes either easier or trivial when such a key is used. The existence of weak keys for a particular cipher does not necessarily imply that all keys, or other keys, are also weak, nor that the cipher is therefore insecure. In the extreme, a poor cipher design is simply one with a very large number of weak keys.

Table of contents
1 Weak keys in DES
2 List of algorithms with weak keys
3 No weak keys as a design goal

Weak keys in DES

DES is probably the most famous algorithm with weak keys. In operation, the secret 56-bit key is broken up into subkeys according to the DES key schedule, and one subkey is used in each of the sixteen DES rounds. The weak keys of DES are those which produce sixteen identical subkeys. This occurs when the key bits are
all zero or
all one, or
the first half of the entire key is all ones and the second half is all zeros, or
vice versa.

Since all the subkeys are identical, and DES is a Feistel network, the encryption function is self-inverting; that is, encrypting twice produces the original plaintext.

DES also has semiweak keys. These come in pairs K1 and K2, and they have the property that:

where EK(M) is the encryption algorithm encrypting message M with key K. This means that both keys encrypt a plaintext to the same ciphertext. This is because these keys produce only two unique subkeys. There are six semiweak key pairs.

Are these weak and semiweak keys fatal flaws of DES? Not really. There are 256 (7.21 × 1016, about 72 quadrillion) possible keys for DES, of which four are weak and twelve are semiweak. This is such a tiny fraction of the possible keyspace that users do not need to worry. If they so desire, they can check for weak or semiweak keys when the keys are generated. They are very few, and easy to recognize.

List of algorithms with weak keys

This list is incomplete. You can help Wikipedia by adding to it.

No weak keys as a design goal

The goal of having a 'flat' keyspace (ie, all keys equally strong) is always a cipher design goal. As in the case of DES, sometimes a small number of weak keys is acceptable, provided that they are all identified or identifiable. An algorithm that has weak keys which are unknown does not inspire much trust.

The two main countermeasures against inadvertently using a weak key:

A large number of weak keys is a serious flaw in any cipher design, since there will then be a (perhaps too) large chance that a randomly generated one will be a weak one, compromising the security of messages encrypted under it. It will also take longer to check randomly generated keys for weakness in such cases, which will tempt shortcuts in interest of 'efficiency'.

Block ciphers
Algorithms: 3-Way | AES | Blowfish | Camellia | CAST-128 | CAST-256 | CMEA | DEAL | DES | DES-X | FEAL | G-DES | GOST | IDEA | Iraqi | KASUMI | KHAZAD | Khufu and Khafre; | LOKI89/91 | LOKI97 | Lucifer | MacGuffin | Madryga | MAGENTA | MARS | MISTY1 | MMB | NewDES | RC2 | RC5 | RC6 | Red Pike; | S-1 | SAFER | Serpent | SHARK | Skipjack | Square | TEA | Triple DES; | Twofish | XTEA
Design: Feistel network; | Key schedule; | Product cipher; | S-box | SPN   Attacks: Brute force; | Linear / Differential cryptanalysis | Mod n; | XSL   Standardisation: AES process; | CRYPTREC | NESSIE   Misc: Avalanche effect | Block size; | IV | Key size; | Modes of operation; | Piling-up lemma; | Weak key;