The DES Key Schedule
Chapter Twenty-One
Syllabus topic Module 1, "Classical Encryption Techniques: The Data Encryption Standard"
Pages 110 to 115 of 678
In one line
Throw away the parity bits, split what is left in two, and rotate each half a little more before every round, taking 48 of the 56 bits each time. That is how one 56-bit key becomes sixteen different 48-bit subkeys.
In the wording a student can write in an examination: the DES key schedule takes the 64-bit key and applies permuted choice one, PC-1, which discards the eight parity bits and permutes the remaining 56. The 56 bits are split into two 28-bit halves, C and D. For each of the sixteen rounds, both halves are circularly left shifted by one or two bits according to a fixed schedule, and then permuted choice two, PC-2, selects 48 of the 56 shifted bits to form that round's subkey.
Why the schedule is shaped like this
The parity bits go first. In a 64-bit DES key every eighth bit carries odd parity over the preceding seven, so that a key damaged in transmission can be detected. PC-1's table has 56 entries and none of them is 8, 16, 24, 32, 40, 48, 56 or 64: the parity bits are simply not selected. That is where the 56 in "56-bit key" comes from.
The rotation makes the subkeys different. If every round used the same 48 bits the cipher would be much weaker, and one of the attacks in the next chapter would become far easier. Rotating both halves before each round means each subkey is a different selection from the key.
The shift schedule is one, one, two, two, two, two, two, two, one, two, two, two, two, two, two, one. Rounds 1, 2, 9 and 16 shift by one and the other twelve shift by two. Add them up and the total is 28, which is exactly the length of each half. So after sixteen rounds each half has been rotated all the way round and is back where it started. That is why a hardware implementation can run the schedule forwards for encryption and backwards for decryption from the same starting registers, and it is the tidiest fact in DES.
PC-2 discards eight of the 56 bits each round. So each subkey uses 48 of the 56 available bits, and which eight are left out changes from round to round because the halves have rotated.
The schedule, computed
# The DES key schedule, from Tables 6, 7 and 8 of FIPS 46-3.
PC1 = [57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18,
10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36,
63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,
14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4]
PC2 = [14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,
23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2,
41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32]
SHIFTS = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]
def bits_of(hexstr):
n = len(hexstr) * 4
v = int(hexstr, 16)
return [(v >> (n - 1 - i)) & 1 for i in range(n)]
def hexof(bl):
v = 0
for b in bl:
v = (v << 1) | b
return "%0*X" % ((len(bl) + 3) // 4, v)
def permute(bl, table):
return [bl[i - 1] for i in table]
key = "133457799BBCDFF1"
kb = bits_of(key)
print("the 64-bit key :", key)
print("every 8th bit is a parity bit, so 56 bits of key material remain")
print("parity of each byte :", end=" ")
for i in range(8):
byte = kb[i * 8:i * 8 + 8]
print("%d" % (sum(byte) % 2), end=" ")
print(" (odd parity on every byte, as the standard requires)")
print()
k56 = permute(kb, PC1)
c, d = k56[:28], k56[28:]
print("after PC-1, the 56 bits split into two halves of 28:")
print(" C0 :", "".join(str(b) for b in c))
print(" D0 :", "".join(str(b) for b in d))
print()
print("round shift subkey (48 bits, as hex)")
for r in range(16):
n = SHIFTS[r]
c = c[n:] + c[:n]
d = d[n:] + d[:n]
k = permute(c + d, PC2)
print(" %2d %d %s" % (r + 1, n, hexof(k)))
print()
print("total left shifts over the sixteen rounds:", sum(SHIFTS))
print("so C16 and D16 are back where C0 and D0 started:", sum(SHIFTS) == 28)
print()
def schedule(keyhex):
b = bits_of(keyhex)
k = permute(b, PC1)
cc, dd = k[:28], k[28:]
out = []
for r in range(16):
n = SHIFTS[r]
cc = cc[n:] + cc[:n]
dd = dd[n:] + dd[:n]
out.append(hexof(permute(cc + dd, PC2)))
return out
print("the four weak keys: every one of their sixteen subkeys is the same,")
print("so encrypting twice returns the plaintext.")
for wk in ("0101010101010101", "FEFEFEFEFEFEFEFE",
"E0E0E0E0F1F1F1F1", "1F1F1F1F0E0E0E0E"):
subs = schedule(wk)
print(" %s all 16 subkeys equal: %-5s (K1 = %s)"
% (wk, len(set(subs)) == 1, subs[0]))The DES Key Schedule
the 64-bit key : 133457799BBCDFF1
every 8th bit is a parity bit, so 56 bits of key material remain
parity of each byte : 1 1 1 1 1 1 1 1 (odd parity on every byte, as the standard requires)
after PC-1, the 56 bits split into two halves of 28:
C0 : 1111000011001100101010101111
D0 : 0101010101100110011110001111
round shift subkey (48 bits, as hex)
1 1 1B02EFFC7072
2 1 79AED9DBC9E5
3 2 55FC8A42CF99
4 2 72ADD6DB351D
5 2 7CEC07EB53A8
6 2 63A53E507B2F
7 2 EC84B7F618BC
8 2 F78A3AC13BFB
9 1 E0DBEBEDE781
10 2 B1F347BA464F
11 2 215FD3DED386
12 2 7571F59467E9
13 2 97C5D1FABA41
14 2 5F43B7F2E73A
15 2 BF918D3D3F0A
16 1 CB3D8B0E17F5
total left shifts over the sixteen rounds: 28
so C16 and D16 are back where C0 and D0 started: True
the four weak keys: every one of their sixteen subkeys is the same,
so encrypting twice returns the plaintext.
0101010101010101 all 16 subkeys equal: True (K1 = 000000000000)
FEFEFEFEFEFEFEFE all 16 subkeys equal: True (K1 = FFFFFFFFFFFF)
E0E0E0E0F1F1F1F1 all 16 subkeys equal: True (K1 = FFFFFF000000)
1F1F1F1F0E0E0E0E all 16 subkeys equal: True (K1 = 000000FFFFFF)The DES Key Schedule
Read five things out of the run.
Every byte of the key has odd parity, printed as eight 1s. That is what makes 133457799BBCDFF1 a well-formed DES key. A key whose parity is wrong is not rejected by the algorithm, which ignores those bits entirely, but it would be rejected by equipment that checks.
C0 and D0 are 1111000011001100101010101111 and 0101010101100110011110001111. These are the values every published walk-through gives, so this chapter is checkable against an independent source.
K1 is 1B02EFFC7072. This is the subkey the previous chapter used, and the round function it produced there came out 234AA9BB, which agrees with the published value. The two chapters therefore check each other.
The sixteen subkeys are all different, and they have to be. Two identical subkeys in a Feistel cipher create a symmetry an attacker can exploit, and the weak keys below are the extreme case of exactly that.
The shifts total 28. The program checked it and printed True. Each half is 28 bits, so sixteen rounds of shifting brings both halves round to their starting position.
The weak keys, and why they are weak
The last block of the run is the whole answer to a question that is set often.
A weak key is one for which all sixteen subkeys are identical. The run found that for all four of the classical weak keys, 0101010101010101, FEFEFEFEFEFEFEFE, E0E0E0E0F1F1F1F1 and 1F1F1F1F0E0E0E0E, the set of sixteen subkeys has exactly one member.
Why does that matter? Because DES decryption is the same algorithm with the subkeys reversed. If all sixteen subkeys are the same, then the reversed schedule is the same as the forward schedule, so decryption is identical to encryption. The consequences follow at once.
- Encrypting a block twice with a weak key returns the original block. The key is its own inverse.
- An attacker who suspects a weak key can test all four in four operations.
- In some protocols, a self-inverse cipher destroys a security property the protocol was relying on.
The DES Key Schedule
The reason those four keys behave this way is visible in their structure. 0101010101010101 is all zero bits apart from parity, so C0 and D0 are all zeros and rotating a block of zeros changes nothing. FEFEFEFEFEFEFEFE is all ones apart from parity, and the same applies. The other two give one half of all zeros and one half of all ones.
There are also semi-weak key pairs, sixteen keys forming six pairs, for which encryption under one key is decryption under the other, because their subkey schedules are each other's reverse. And a larger set of possibly weak keys produce only four distinct subkeys rather than sixteen.
How much does this cost DES? Almost nothing: there are 4 weak keys, 12 semi-weak, and 48 possibly weak, out of 2 to the power 56. The chance of choosing one at random is negligible. It is examinable because it is a clean illustration of what a key schedule is for, not because it is a practical threat.
A worked example: the first shift, by hand
The setting. Key 133457799BBCDFF1. After PC-1, from the run, C0 is 1111000011001100101010101111 and D0 is 0101010101100110011110001111.
Step 1: round 1 shifts by one. Rotate each half one place left, moving the leftmost bit round to the right-hand end.
C1 is 1110000110011001010101011111 and D1 is 1010101011001100111100011110.
Check C1 against C0: C0 began 1111 0000 and C1 begins 1110 0001, which is C0 with its first bit moved to the end. And C0 ended 1111 while C1 ends 1111 1, having gained the 1 that came round. That is the check to make, because a rotation done wrong is the commonest arithmetic slip in this topic.
Step 2: apply PC-2. Concatenate C1 and D1 into 56 bits, then take the 48 bits PC-2 names, in the order it names them. PC-2 begins 14, 17, 11, 24, 1, 5, so the subkey's first six bits are bits 14, 17, 11, 24, 1 and 5 of that 56-bit string.
Step 3: read the answer. The result is 1B02EFFC7072, as the run printed for round 1.
Step 4: note what PC-2 leaves out. PC-2 has 48 entries out of 56, so eight positions are never named. Check the table and they are 9, 18, 22, 25, 35, 38, 43 and 54. Those eight bits of C1 D1 are simply not used in round 1, and because the halves rotate, a different eight are unused in round 2.
Distinctions that carry marks
| PC-1 | PC-2 | |
|---|---|---|
| Input | 64 bits, the whole key | 56 bits, the shifted halves |
| Output | 56 bits | 48 bits |
| Discards | the 8 parity bits | 8 of the 56, a different 8 each round |
| Applied | once | once per round, sixteen times |
The DES Key Schedule
| Weak key | Semi-weak key pair | Possibly weak key | |
|---|---|---|---|
| Subkeys | all 16 identical | the two schedules are each other's reverse | only 4 distinct |
| Consequence | encryption is decryption; the key is its own inverse | encrypting with one decrypts the other | a reduced schedule |
| How many | 4 | 12, in 6 pairs | 48 |
| The 64-bit key | The 56-bit key material | |
|---|---|---|
| Contains | 56 key bits and 8 parity bits | the bits PC-1 selects |
| Keyspace | not 2 to the power 64 | 2 to the power 56 |
| Parity | odd, per byte | not applicable |
What beginners get wrong here
Saying the keyspace is 2 to the power 64. PC-1 discards the parity bits, so it is 2 to the power 56.
Rotating the two halves together. C and D are rotated separately, each within its own 28 bits.
Rotating right, or shifting instead of rotating. It is a circular left shift: the bit that leaves the left end comes back at the right.
Getting the shift schedule wrong. Rounds 1, 2, 9 and 16 shift by one; all the others by two. A useful check is that the total must be 28.
Listing the weak keys without saying why they are weak. The reason is that all sixteen subkeys are identical, so decryption is the same as encryption and the key is its own inverse.
Quick revision
- PC-1: 64 bits to 56, discarding the eight parity bits. That is where 56 comes from.
- Split into C and D, 28 bits each, rotated separately and circularly left before every round.
- Shift schedule: 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1. Rounds 1, 2, 9 and 16 shift by one.
- The shifts total 28, so after sixteen rounds both halves are back where they started.
- PC-2: 56 bits to 48, leaving out eight, and a different eight each round because the halves have rotated.
- For key
133457799BBCDFF1:C0 = 1111000011001100101010101111,D0 = 0101010101100110011110001111,K1 = 1B02EFFC7072. - A weak key has all sixteen subkeys identical, so encryption equals decryption and the key is its own inverse. There are 4 of them, plus 12 semi-weak in 6 pairs and 48 possibly weak.
- The keyspace is 2 to the power 56, never 2 to the power 64.
Test yourself
1. Describe the DES key schedule. PC-1 takes the 64-bit key to 56 bits, discarding the eight parity bits. The 56 bits split into two 28-bit halves C and D. Before each of the sixteen rounds both halves are circularly left shifted, by one bit in rounds 1, 2, 9 and 16 and by two bits otherwise, and PC-2 then selects 48 of the 56 shifted bits as that round's subkey.
The DES Key Schedule
2. Why is the DES key 56 bits when it is presented as 64? Because every eighth bit is a parity bit, carrying odd parity over the preceding seven so that a corrupted key can be detected. PC-1 does not select any of those eight positions, so they contribute nothing to the subkeys and the keyspace is 2 to the power 56.
3. State the shift schedule and give the check on it. One, one, two, two, two, two, two, two, one, two, two, two, two, two, two, one: rounds 1, 2, 9 and 16 shift by one and the remaining twelve by two. The check is that the shifts total 28, the length of each half, so after sixteen rounds C and D have been rotated exactly once round and are back at their starting positions.
4. What is a weak key, and why is it weak? A key for which all sixteen subkeys come out identical. Since DES decryption is the same algorithm with the subkeys reversed, an identical schedule means decryption is the same as encryption, so the key is its own inverse and encrypting a block twice returns it. There are four such keys.
5. Name the four weak keys. 0101010101010101, FEFEFEFEFEFEFEFE, E0E0E0E0F1F1F1F1 and 1F1F1F1F0E0E0E0E.
6. Distinguish a weak key from a semi-weak key pair. A weak key has all sixteen subkeys the same, so encryption and decryption coincide under that one key. A semi-weak pair consists of two keys whose subkey schedules are each other's reverse, so encrypting with one key is the same as decrypting with the other. There are four weak keys and twelve semi-weak keys forming six pairs.
7. How many bits does PC-2 discard, and why is that acceptable? Eight of the 56, so each subkey uses 48 bits. It is acceptable because the halves rotate between rounds, so a different eight bits are omitted in each round and every bit of the key material is used in most rounds.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.