Mastering Algorithms With C - Kyle Loudon [195]
Q: With DES, we encipher and decipher data by performing a series of permutations and substitutions. Exactly how these permutations and substitutions affect the data is essentially a function of 16 subkeys, derived from an initial key that we provide. In general, the security of DES is greatest when most of the subkeys differ from one another. Unfortunately, certain initial keys lead to situations in which all subkeys are identical. These initial keys are called weak keys. DES has four weak keys. What are they?
A: To generate subkeys in DES, we first transform the key from 64 bits to 56 bits. Once the key has been transformed, we divide it into two 28-bit blocks and perform a number of other operations that are repeated during each round. If either of the two 28-bit blocks contains bits that are all the same, these operations have no effect. Thus, we end up with subkeys that are identical for every round, and the initial key is considered weak. The four weak keys of DES and what they become are shown in Table 15.9.
Table 15.9. Weak Keys in DES Before and After the Key Transformation
Key
Becomes
0101 0101 0101 0101
0000000 0000000
1F1F 1F1F 1F1F 1F1F
0000000 FFFFFFF
E0E0 E0E0 F1F1 F1F1
FFFFFFF 0000000
FEFE FEFE FEFE FEFE
FFFFFFF FFFFFFF
Q: Avoiding weak keys is one security issue in DES. Another issue is avoiding semiweak keys. Semiweak keys come in pairs. Two keys form a semiweak key pair if the subkeys they produce are in the opposite order. This means that if we use one key from the pair to re-encipher the ciphertext generated using the other key, we effectively get the same result as deciphering the ciphertext with the original key. DES has six semiweak key pairs. What are they? Why are semiweak keys a problem?
A: The problem with semiweak key pairs in DES is that by re-enciphering the ciphertext with one key in the pair we essentially end up performing the same operation as deciphering the ciphertext with the other key. Thus, effectively we have two keys that can decipher the data, which makes semiweak keys undesirable. The six semiweak key pairs of DES are shown in Table 15.10.
Table 15.10. Semiweak Key Pairs in DES
Key 1
Key 2
01FE 01FE 01FE 01FE
FE01 FE01 FE01 FE01
1FE0 1FE0 0EF1 0EF1
E01F E01F F10E F10E
01E0 01E0 01F1 01F1
E001 E001 F101 F101
1EFE 1EFE 0EFE 0EFE
FE1F FE1F FE0E FE0E
011F 011F 010E 010E
1F01 1F01 0E01 0E01
E0FE E0FE F1FE F1FE
FEE0 FEE0 FEF1 FEF1
Q: Some applications of DES use keys that are generated randomly. In applications like this, what precautions might we take against the use of weak and semiweak keys, if any?
A: Considering the number of keys listed in Tables Table 15.9 and Table 15.10 combined, it's evident that out of 256 possible keys in DES, weak and semiweak keys are rare. Nevertheless, applications that use randomly generated keys often check to make sure a candidate key is not weak or semiweak before using it. On the other hand, since checking every key is somewhat wasteful considering how infrequent weak and semiweak keys are, many applications simply don't worry about them.
Q: RSA is a block cipher, which means that it processes data one block at a time. Whereas DES always uses a block size of 64 bits, the block size of RSA varies depending on the value of n, where n = pq. What happens if we mistakenly choose the block size so that some blocks of plaintext contain values greater than or equal to n?
A: The problem with a block of plaintext containing a value greater than or equal to n is that when we encipher and decipher blocks, the modular exponentiation operation is modulo n. This means that all blocks generated as either ciphertext or plaintext contain values less than n.