Weak key

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", or "linear", key space.

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: [FIPS, "GUIDELINES FOR IMPLEMENTING AND USING THE NBS DATA ENCRYPTION STANDARD", FIPS-PUB 74, http://www.itl.nist.gov/fipspubs/fip74.htm ]
* Alternating ones + zeros (0x0101010101010101)
* Alternating 'F' + 'E' (0xFEFEFEFEFEFEFEFE)
* '0xE0E0E0E0F1F1F1F1'
* '0x1F1F1F1F0E0E0E0E'

If an implementation does not consider the parity bits, the corresponding keys with the inverted parity bits may also work as weak keys:
* all zeros (0x0000000000000000)
* all ones (0xFFFFFFFFFFFFFFFF)
* '0xE1E1E1E1F0F0F0F0'
* '0x1E1E1E1E0F0F0F0F'Using weak keys, the outcome of the Permuted Choice 1 (PC1) in the DES key schedule leads to round keys being either all zeros, all ones or alternating zero-one patterns.

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 "semi-weak keys", which only produce two different subkeys, each used eight times in the algorithm: This means they come in pairs "K"1 and "K"2, and they have the property that:

:E_{K_1}(E_{K_2}(M))=M

where E"K"(M) is the encryption algorithm encrypting message "M "with key "K". There are six semiweak key pairs:
* 0x011F011F010E010E and 0x1F011F010E010E01
* 0x01E001E001F101F1 and 0xE001E001F101F101
* 0x01FE01FE01FE01FE and 0xFE01FE01FE01FE01
* 0x1FE01FE00EF10EF1 and 0xE01FE01FF10EF10E
* 0x1FFE1FFE0EFE0EFE and 0xFE1FFE1FFE0EFE0E
* 0xE0FEE0FEF1FEF1FE and 0xFEE0FEE0FEF1FEF1

There are also 48 possibly weak keys that produce only four distinct subkeys (instead of 16). They can be found in [NIST, "Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher," Special Publication 800-67, page 14]

These weak and semiweak keys are not considered "fatal flaws" of DES. 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. 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. [FLUHRER, S., MANTIN, I., AND SHAMIR, A. Weaknesses in the key scheduling algorithm of RC4. Eighth Annual Workshop on Selected Areas in Cryptography (August 2001), http://citeseer.ist.psu.edu/fluhrer01weaknesses.html]

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

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

ee also

* weak authentication
* authentication factors
* cf. strong authentication
* Multifactor authentication

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Key strengthening — In cryptography, key strengthening or key stretching refer to techniques used to make a possibly weak key, typically a password or passphrase, more secure against a brute force attack by increasing the time it takes to test each possible key.… …   Wikipedia

  • Key (cryptography) — In cryptography, a key is a piece of information (a parameter) that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the… …   Wikipedia

  • Key space — In cryptography, an algorithm s key space refers to the set of all possible keys that can be used to initialize it. For example, if an algorithm works using a key that is a string of 10 bits, then its key space is the set of all binary strings of …   Wikipedia

  • Key Biscayne — is an island located in Miami Dade County, Florida, United States, between the Atlantic Ocean and Biscayne Bay. It is the southernmost of the barrier islands along the Atlantic coast of Florida, and lies south of Miami Beach and southeast of… …   Wikipedia

  • Weak entity — In a relational database, a Weak Entity is an entity that cannot be uniquely identified by its attributes alone; therefore, it must use a foreign key in conjunction with its attributes to create a primary key. The foreign key is typically a… …   Wikipedia

  • Weak solution — In mathematics, a weak solution (also called a generalized solution) to an ordinary or partial differential equation is a function for which the derivatives appearing in the equation may not all exist but which is nonetheless deemed to satisfy… …   Wikipedia

  • Key derivation function — KDF redirects here. For the Nazi organization, see Kraft durch Freude In cryptography, a key derivation function (or KDF) is a function which derives one or more secret keys from a secret value and/or other known information such as a password or …   Wikipedia

  • Related-key attack — In cryptography, a related key attack is any form of cryptanalysis where the attacker can observe the operation of a cipher under several different keys whose values are initially unknown, but where some mathematical relationship connecting the… …   Wikipedia

  • Diffie–Hellman key exchange — (D–H)[nb 1] is a specific method of exchanging keys. It is one of the earliest practical examples of key exchange implemented within the field of cryptography. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge …   Wikipedia

  • Password-authenticated key agreement — In cryptography, a password authenticated key agreement method is an interactive method for two or more parties to establish cryptographic keys based on one or more party s knowledge of a password. Contents 1 Types 2 Brief history 3 See also …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”