Weak key

Encyclopedia : W : WE : WEA : Weak key

In cryptography, a weak key is a key which when used with a specific cipher, makes the cipher behave in some undesirable way. Weak keys usually represent a very small fraction of the overall keyspace, which usually means that if one generates a random key to encrypt a message weak keys are very unlikely to give rise to a security problem. Nevertheless, it is considered desirable for a cipher to have no weak keys. A cipher with no weak keys is said to have a flat keyspace.

Contents

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

Weak keys in DES

The block cipher DES has a few specific keys termed "weak keys" and "semi-weak keys". These are keys which cause the encryption mode of DES to act identically to the decryption mode of DES (albeit potentially that of a different key).

In operation, the secret 56-bit key is broken up into 16 subkeys according to the DES key schedule; 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 zeros
all ones
the first half of the entire key is all ones and the second half is all zeros
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 K₁ and K₂, and they have the property that:

[E_(E_(M))=M]

where E_K(M) is the encryption algorithm encrypting message M with key K. There are six semiweak key pairs.

Are these weak and semiweak keys fatal flaws of DES? Not really. There are 2⁵⁶ (7.21 × 10¹⁶, 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. Note, however, that DES is not recommended for general use since all keys can be brute-forced in about a day for a one-time hardware cost on the order of some new cars.

List of algorithms with weak keys

RC4. RC4's weak initialization vectors allow an attacker to mount a known-plaintext attack and have been widely used to compromise the security of WEP.
IDEA. IDEA's weak keys are identifiable in a chosen-plaintext attack. They make the relationship between the XOR sum of plaintext bits and ciphertext bits predictable. There is no list of these keys, but they can be identified by their "structure".
Blowfish. Blowfish's weak keys produce bad S-boxes, since Blowfish's S-boxes are key-dependent. There is a chosen plaintext attack against a reduced-round variant of Blowfish that is made easier by the use of weak keys. This is not a concern for full 16-round Blowfish.

This list is [Incomplete listsincomplete]; you can help by [http://encycl.opentopia.com/ expanding 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:

Checking generated keys against a list of known weak keys, or building rejection of weak keys into the key scheduling.
When the number of weak keys is known to be very small (in comparison to the size of the keyspace), generating a key uniformly at random ensures that the probability of it being weak is a (known) very small number.

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'.

However, weak keys are much more often a problem where the adversary has some control over what keys are used, such as when a block cipher is used in a mode of operation intended to construct a secure cryptographic hash function (eg Davies-Meyer).

References

[Weaknesses in the Key Scheduling Algorithm of RC4]

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.