# If the first key-bit is flipped, which DES s-boxes are affected?

Instead of the input bit being flipped... if the 1st bit of the key is being flipped, which s-boxes are affected during encryption/decryption of DES?

• If the 1st bit is an lsbit of the key, then the answer is "none of them" – poncho Sep 12 '16 at 21:25
• Sounds like homework or an alike assignment... is it? Also, what research have you done? – e-sushi Sep 12 '16 at 22:02
• It also depends on which key bits in which round. Each key bit is going to be used more than 10 times and affect 4 S Boxes. C is used for S Boxes 1 - 4 and D for 5 - 8. (keytab.c keytab -b, -b outputs key tables shown as input block bits). – user1430 Sep 13 '16 at 0:03
• As in if the 1st key bit is flipped(MSB) before the initial permutation and the rest of the operations are carried out as it is. I tried manually, but its tedious and time consuming. I was wondering if there was another logic in which this could be approached. – saahil24 Sep 13 '16 at 0:10
• Hint: follow propagation of the change thru PC2 to C/D, and from that to an S-box (take rotation into account), then at the next round a different S boxes due to further rotation of C/D and (possibly) more S-boxes thru data change propagated thru PC-1 and E. – fgrieu Sep 13 '16 at 5:00

Permuted Choice 1 determines how an input block is loaded into C and D Registers:

Permuted Choice 1 is selection permutation describing how to load C and D registers from 8 successive bytes of input key, noting the LSB is only used for parity. (The big endian bit in byte ordering is from IBM).

Permuted Choice 2 determines which C and D Register bits are used as input to f(R,K):

Permuted Choice 2 is also a selection permutation selecting two 24 bit values from each of the C and D 28 bit registers which are shifted according to the key schedule.

The DES standard also defines which selected Key bits are associated with each S Box:

This shows the E Permutation as values of R exclusive OR'd with selected key bits as input to the 8 S Boxes.

The Key Schedule causes rotations in the C and D registers bringing different key bits into play in different rounds.

The program keytab.c reproduces two tables from the Meyers Metyas book Cryptography.

Invoking keytab -b will fill an input block with input block indexes for each position convert those locations to the appropriate locations in the C and D Registers, iterate the key schedule and produce the selected Key for each round through PC2 giving a list of Ks bits referencing the input block indexes:

  Bit  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
KS
1  10 51 34 60 49 17 33 57  2  9 19 42  3 35 26 25 44 58 59  1 36 27 18 41
2   2 43 26 52 41  9 25 49 59  1 11 34 60 27 18 17 36 50 51 58 57 19 10 33
3  51 27 10 36 25 58  9 33 43 50 60 18 44 11  2  1 49 34 35 42 41  3 59 17
4  35 11 59 49  9 42 58 17 27 34 44  2 57 60 51 50 33 18 19 26 25 52 43  1
5  19 60 43 33 58 26 42  1 11 18 57 51 41 44 35 34 17  2  3 10  9 36 27 50
6   3 44 27 17 42 10 26 50 60  2 41 35 25 57 19 18  1 51 52 59 58 49 11 34
7  52 57 11  1 26 59 10 34 44 51 25 19  9 41  3  2 50 35 36 43 42 33 60 18
8  36 41 60 50 10 43 59 18 57 35  9  3 58 25 52 51 34 19 49 27 26 17 44  2
9  57 33 52 42  2 35 51 10 49 27  1 60 50 17 44 43 26 11 41 19 18  9 36 59
10  41 17 36 26 51 19 35 59 33 11 50 44 34  1 57 27 10 60 25  3  2 58 49 43
11  25  1 49 10 35  3 19 43 17 60 34 57 18 50 41 11 59 44  9 52 51 42 33 27
12   9 50 33 59 19 52  3 27  1 44 18 41  2 34 25 60 43 57 58 36 35 26 17 11
13  58 34 17 43  3 36 52 11 50 57  2 25 51 18  9 44 27 41 42 49 19 10  1 60
14  42 18  1 27 52 49 36 60 34 41 51  9 35  2 58 57 11 25 26 33  3 59 50 44
15  26  2 50 11 36 33 49 44 18 25 35 58 19 51 42 41 60  9 10 17 52 43 34 57
16  18 59 42  3 57 25 41 36 10 17 27 50 11 43 34 33 52  1  2  9 44 35 26 49

Bit 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
KS
1  22 28 39 54 37  4 47 30  5 53 23 29 61 21 38 63 15 20 45 14 13 62 55 31
2  14 20 31 46 29 63 39 22 28 45 15 21 53 13 30 55  7 12 37  6  5 54 47 23
3  61  4 15 30 13 47 23  6 12 29 62  5 37 28 14 39 54 63 21 53 20 38 31  7
4  45 55 62 14 28 31  7 53 63 13 46 20 21 12 61 23 38 47  5 37  4 22 15 54
5  29 39 46 61 12 15 54 37 47 28 30  4  5 63 45  7 22 31 20 21 55  6 62 38
6  13 23 30 45 63 62 38 21 31 12 14 55 20 47 29 54  6 15  4  5 39 53 46 22
7  28  7 14 29 47 46 22  5 15 63 61 39  4 31 13 38 53 62 55 20 23 37 30  6
8  12 54 61 13 31 30  6 20 62 47 45 23 55 15 28 22 37 46 39  4  7 21 14 53
9   4 46 53  5 23 22 61 12 54 39 37 15 47  7 20 14 29 38 31 63 62 13  6 45
10  55 30 37 20  7  6 45 63 38 23 21 62 31 54  4 61 13 22 15 47 46 28 53 29
11  39 14 21  4 54 53 29 47 22  7  5 46 15 38 55 45 28  6 62 31 30 12 37 13
12  23 61  5 55 38 37 13 31  6 54 20 30 62 22 39 29 12 53 46 15 14 63 21 28
13   7 45 20 39 22 21 28 15 53 38  4 14 46  6 23 13 63 37 30 62 61 47  5 12
14  54 29  4 23  6  5 12 62 37 22 55 61 30 53  7 28 47 21 14 46 45 31 20 63
15  38 13 55  7 53 20 63 46 21  6 39 45 14 37 54 12 31  5 61 30 29 15  4 47
16  30  5 47 62 45 12 55 38 13 61 31 37  6 29 46  4 23 28 53 22 21  7 63 39


These represent Table 3-10 First Set of 24 key Bits in K(i), the Key used at Round( i) and Table 3-11 Second Set of 24 Key Bits in K(i), the Key Used at Round(i) found in Chapter 3. The Data Encryption standard the section Description of the Data Encryption Standard and subsection Generation of Key Vectors Used for Each Round of DES, of Cryptography A new Dimension in Computer Data Security subtitled A Guide for the Design and Implementation of Secure Systems, by Carl H. Meyer and Stephen M. Matyas published in 1982.

The tables demonstrate the Permuted Choice 2 selected C and D register contents given in input block indexes for the 16 rounds of DES.

The KS bits tell us which S Boxes each input block key bit is used on in each round.

Note that for input block bit 1 (the most significant bit of the first byte of key) is used as input to S Boxes 1 through 4 in 14 rounds.

Taking in to account e-suishi's comment the answer is achievable through research either reading or applied practice. You could also note the process undertaken by the keytab program matches that described by fgrieu's comment.

In this case keytab generates the schedule key for each of the 16 rounds by providing an integer value representing the input block index instead of a 1 or 0 representing a binary value.

The idea comes from the original BSD libcrypt implementation of DES (des0.tar.gz, file crypt.c) which used integers to represent individual bits.

Doing or can imply validating what you read.

Your question may be a trick question. If you are looking for "direct changes", user1430's answer is the answer.

But if you flip k1 in S4/Round1, you also modify at least 2 bits out of S4 and then, with P and E between 2 rounds, you modify 2 to 6 bits of Round2 48 bit input. etc.