Weak key
Encyclopedia
In cryptography
, a weak key is a key
, which, 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
.
The German Enigma machine is a family of about dozen different cipher machine designs, each with its own problems. The military Enigma cipher machine, in its 3 and 4 rotor implementations had the equivalent of weak keys. Certain combinations of rotor order, stepping and initial key were fundamentally weaker than others. The Enigma's reflector (when used) guaranteed that no letter could be enciphered as itself, so an A could never turn back into an A. This helped Polish and, later, British efforts to break the cipher. (See Cryptanalysis of the Enigma
and the Enigma rotor details
.)
The first stream cipher machines, that were also rotor machines had some of the same problems of weak keys as the more traditional rotor machines. The T52 was one such stream cipher machine that had weak key problems.
The British first detected T52 traffic in Summer and Autumn of 1942. One link was between Sicily
and Libya
, codenamed "Sturgeon
", and another from the Aegean
to Sicily
, codenamed "Mackerel
". Operators of both links were in the habit of enciphering several messages with the same machine settings, producing large numbers of depths.
There were several (mostly incompatible) versions of the T52: the T52a and T52b (which differed only in their electrical noise suppression), T52c, T52d and T52e. While the T52a/b and T52c were cryptologically weak, the last two were more advanced devices; the movement of the wheels was intermittent, the decision on whether or not to advance them being controlled by logic circuits which took as input data from the wheels themselves.
In addition, a number of conceptual flaws (including very subtle ones) had been eliminated. One such flaw was the ability to reset the keystream
to a fixed point, which led to key reuse by undisciplined machine operators.
DES
has a few specific keys termed "weak keys" and "semi-weak keys". These are keys that 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. DES weak keys produce sixteen identical subkeys. This occurs when the key bits are:
If an implementation does not consider the parity bits, the corresponding keys with the inverted parity bits may also work as weak keys:
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 K1 and K2, and they have the property that:
where EK(M) is the encryption algorithm encrypting message
M with key K. There are six semiweak key pairs:
There are also 48 possibly weak keys that produce only four distinct subkeys (instead of 16). They can be found in
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 cards.
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'.
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
(e.g. Davies-Meyer).
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, a weak key is a key
Key (cryptography)
In cryptography, a key is a piece of information 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 particular transformation of plaintext into ciphertext, or vice versa...
, which, used with a specific cipher
Cipher
In cryptography, a cipher is an algorithm for performing encryption or decryption — a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. In non-technical usage, a “cipher” is the same thing as a “code”; however, the concepts...
, 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
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 length 10. i.e...
.
Historical origins
Virtually all rotor based cipher machines (from 1925 onwards) have implementation flaws that lead to a substantial number of weak keys being created. Some machines have more problems with weak keys than others, as modern block and stream ciphers do.The German Enigma machine is a family of about dozen different cipher machine designs, each with its own problems. The military Enigma cipher machine, in its 3 and 4 rotor implementations had the equivalent of weak keys. Certain combinations of rotor order, stepping and initial key were fundamentally weaker than others. The Enigma's reflector (when used) guaranteed that no letter could be enciphered as itself, so an A could never turn back into an A. This helped Polish and, later, British efforts to break the cipher. (See Cryptanalysis of the Enigma
Cryptanalysis of the Enigma
Cryptanalysis of the Enigma enabled the western Allies in World War II to read substantial amounts of secret Morse-coded radio communications of the Axis powers that had been enciphered using Enigma machines. This yielded military intelligence which, along with that from other decrypted Axis radio...
and the Enigma rotor details
Enigma rotor details
This article contains technical details about the rotors of the Enigma machine.Understanding the way the machine encrypts requires taking into account the current position of each rotor, the ring setting and its internal wiring.- Physical design of rotors :...
.)
The first stream cipher machines, that were also rotor machines had some of the same problems of weak keys as the more traditional rotor machines. The T52 was one such stream cipher machine that had weak key problems.
The British first detected T52 traffic in Summer and Autumn of 1942. One link was between Sicily
Sicily
Sicily is a region of Italy, and is the largest island in the Mediterranean Sea. Along with the surrounding minor islands, it constitutes an autonomous region of Italy, the Regione Autonoma Siciliana Sicily has a rich and unique culture, especially with regard to the arts, music, literature,...
and Libya
Libya
Libya is an African country in the Maghreb region of North Africa bordered by the Mediterranean Sea to the north, Egypt to the east, Sudan to the southeast, Chad and Niger to the south, and Algeria and Tunisia to the west....
, codenamed "Sturgeon
Sturgeon
Sturgeon is the common name used for some 26 species of fish in the family Acipenseridae, including the genera Acipenser, Huso, Scaphirhynchus and Pseudoscaphirhynchus. The term includes over 20 species commonly referred to as sturgeon and several closely related species that have distinct common...
", and another from the Aegean
Aegean Sea
The Aegean Sea[p] is an elongated embayment of the Mediterranean Sea located between the southern Balkan and Anatolian peninsulas, i.e., between the mainlands of Greece and Turkey. In the north, it is connected to the Marmara Sea and Black Sea by the Dardanelles and Bosporus...
to Sicily
Sicily
Sicily is a region of Italy, and is the largest island in the Mediterranean Sea. Along with the surrounding minor islands, it constitutes an autonomous region of Italy, the Regione Autonoma Siciliana Sicily has a rich and unique culture, especially with regard to the arts, music, literature,...
, codenamed "Mackerel
Mackerel
Mackerel is a common name applied to a number of different species of fish, mostly, but not exclusively, from the family Scombridae. They may be found in all tropical and temperate seas. Most live offshore in the oceanic environment but a few, like the Spanish mackerel , enter bays and can be...
". Operators of both links were in the habit of enciphering several messages with the same machine settings, producing large numbers of depths.
There were several (mostly incompatible) versions of the T52: the T52a and T52b (which differed only in their electrical noise suppression), T52c, T52d and T52e. While the T52a/b and T52c were cryptologically weak, the last two were more advanced devices; the movement of the wheels was intermittent, the decision on whether or not to advance them being controlled by logic circuits which took as input data from the wheels themselves.
In addition, a number of conceptual flaws (including very subtle ones) had been eliminated. One such flaw was the ability to reset the keystream
Keystream
In cryptography, a keystream is a stream of random or pseudorandom characters that are combined with a plaintext message to produce an encrypted message ....
to a fixed point, which led to key reuse by undisciplined machine operators.
Weak keys in DES
The block cipherBlock cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
DES
Data Encryption Standard
The Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is...
has a few specific keys termed "weak keys" and "semi-weak keys". These are keys that 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
Key schedule
[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("...
; one subkey is used in each of the sixteen DES rounds. DES weak keys produce sixteen identical subkeys. This occurs when the key bits are:
- 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
Key schedule
[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("...
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 K1 and K2, and they have the property that:
where EK(M) is the encryption algorithm encrypting message
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
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
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 cards.
List of algorithms with weak keys
- RC4RC4In cryptography, RC4 is the most widely used software stream cipher and is used in popular protocols such as Secure Sockets Layer and WEP...
. RC4's weak initialization vectors allow an attacker to mount a known-plaintext attack and have been widely used to compromise the security of WEPWired Equivalent PrivacyWired Equivalent Privacy is a weak security algorithm for IEEE 802.11 wireless networks. Introduced as part of the original 802.11 standard ratified in September 1999, its intention was to provide data confidentiality comparable to that of a traditional wired network...
.
- 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".
- Data Encryption StandardData Encryption StandardThe Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is...
- BlowfishBlowfish (cipher)Blowfish is a keyed, symmetric block cipher, designed in 1993 by Bruce Schneier and included in a large number of cipher suites and encryption products. Blowfish provides a good encryption rate in software and no effective cryptanalysis of it has been found to date...
. 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 (i.e., 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 unknown weak keys 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
Block cipher modes of operation
In cryptography, modes of operation is the procedure of enabling the repeated and secure use of a block cipher under a single key.A block cipher by itself allows encryption only of a single data block of the cipher's block length. When targeting a variable-length message, the data must first be...
intended to construct a secure cryptographic hash function
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
(e.g. Davies-Meyer).
See also
- authentication factors
- strong authenticationStrong authenticationStrong authentication is a notion with several unofficial definitions; is not standardized in the security literature.Often, strong authentication is associated with two-factor authentication or more generally multi-factor authentication...
- Multifactor authentication