Why do we use a permutation table in the first step of DES algorithm and one at the end of the algorithm?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
The initial and final permutation have no influence on security (they are unkeyed and can be undone by anybody). The usual explanation is that they make implementation easier in some contexts, namely a hardware circuit which receives data over a 8-bit bus: it can accumulate the bits into eight shift registers, which is more efficient (in terms of circuit area) than a single 64-bit register. This process "naturally" performs the initial permutation of DES.
In more details: Suppose that you are designing a hardware circuit which should do some encryption with DES, and receives data by blocks of 8 bits. This means that there are 8 "lines", each yielding one bit at each clock. A common device for accumulating data is a shift register: the input line plugs into a one-bit register, which itself plugs into another, which plugs into a third register, and so on. At each clock, each register receives the contents from the previous, and the first register accepts the new bit. Hence, the contents are "shifted".
With an 8-bit bus, you would need 8 shift registers, each receiving 8 bits for an input block. The first register will receive bits 1, 9, 17, 25, 33, 41, 49 and 57. The second register receives bits 2, 10, 18,... and so on. After eight clocks, you have received the complete 64-bit block and it is time to proceed with the DES algorithm itself.
If there was no initial permutation, then the first step of the first round would extract the "left half" (32 bits) which, at that point, would consist of the leftest 4 bits of each of the 8 shift registers. The "right half" would also get bits from the 8 shift registers. If you think of it as wires from the shift registers to the units which use the bits, then you end up with a bunch of wires which heavily cross each other. Crossing is doable but requires some circuit area, which is the expensive resource in hardware designs.
However, if you consider that the wires must extract the input bits and permute them as per the DES specification, you will find out that there is no crossing anymore. In other words, the accumulation of bits into the shift registers inherently performs a permutation of the bits, which is exactly the initial permutation of DES. By defining that initial permutation, the DES standard says: "well, now that you have accumulated the bits in eight shift registers, just use them in that order, that's fine".
The same thing is done again at the end of the algorithm.
Remember that DES was designed at a time when 8-bit bus where the top of the technology, and one thousand transistors were an awfully expensive amount of logic.
answered Jul 12, 2011 at 18:48
-
2$\begingroup$ Excellent amount of detail! We were taught at university that it made hardware implementation easier, but not why, so thank you for your answer. $\endgroup$– ZoFreXCommented Jul 12, 2011 at 19:10
$\begingroup$
$\endgroup$
3
Our Professor, Christof Paar, sat together on lunch a few years ago with one of the main designers of DES.
He said that for getting it as specification, they had to build a piece of hardware which encrypts via DES. Shortly before finishing the project, they discovered that their wiring into the box was somewhat intermingled. Building such hardware stuff was rather expensive and time consuming in that time.
They had to decide ... changing the specification, which was cheap and had no effect on the security of the system whatsoever, or build and test a new hardware device.
-
$\begingroup$ the rest is, as we say, history ;) $\endgroup$– smartieCommented Jan 19, 2012 at 15:11
-
$\begingroup$ This is basically the same answer as the one from Thomas, but with less detail and more historical context. It's always a good thing when history is preserved :) $\endgroup$– Maarten Bodewes ♦Commented Feb 13, 2016 at 11:52
-
$\begingroup$ you mean this one? https://youtu.be/kPBJIhpcZgE XD about 40:00 ~ 50:00 min $\endgroup$– ValenCommented Aug 23, 2016 at 4:32
$\begingroup$
$\endgroup$
Something I wrote years ago to describe the IP and Inverse IP. With a copy of the FIPS Pub in hand you can see the correlation between registers and bits. Essentially the data is shifted in serially (for an interface smaller than 64 bits, in this case 8 bits wide) and used in a parallel fashion. In hardware and an 8 bit interface the IP and Inverse IP permutations (and Permuted Choice 1) are reordering of bits on the 8 bit interface. Note the reference to Port Bit order (which is big endian) and MSB7 which is little endian.
The Initial Permutation
The Initial Permuation (IP) is a description of how a byte wide interface is connected to a 64 bit block comprised of two 32 bit blocks (L and R). Consider a byte wide interface with the bits numbered 1-8. The event numbered bits go to the L Block and the odd numbered bits go to the R block. Note that the bit order is big endian, where bit 1 is most significant and bit 8 is least least significant. The input block is typically loaded as 8 successive byte loads:
Port MSB7 Input (LR) Left
Bit Bit Block (64 bits) Block (32 bits)
2------6-------58 50 42 34 26 18 10 2 1 2 3 4 5 6 7 8
4------4-------60 52 44 36 28 20 12 4 9 10 11 12 13 14 15 16
6------2-------62 54 46 38 30 22 14 6 17 18 19 20 21 22 23 24
8------0-------64 56 48 40 32 24 16 8 25 26 27 28 29 30 31 32
Right
Block (32 bits)
1------7-------57 49 41 33 25 17 9 1 1 2 3 4 5 6 7 8
3------5-------59 51 43 35 27 19 11 3 9 10 11 12 13 14 15 16
5------3-------61 53 45 37 29 21 13 5 17 18 19 20 21 22 23 24
7------1-------63 55 47 39 31 23 15 7 25 26 27 28 29 30 31 32
Input Byte 8 7 6 5 4 3 2 1
The Final Permutation
The Final Permutation (IP-1) provides the inverse, it standarizes the output of the R16L16 output block to a byte wide interface. The Output block is ordered Right then Left to allow complementary operation for subsequent decryption. Were one to perform an IP followed by IP-1 without any intervening round iteration operations, one would end up with odd and even bits swapped:
Right Output (R16L16) Standard Port
Block (32 bits) Block (64 bits) Bit Bit
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8---------6--------2
9 10 11 12 13 14 15 16 9 10 11 12 13 14 15 16---------4--------4
17 18 19 20 21 22 23 24 17 18 19 20 21 22 23 24---------2--------6
25 26 27 28 29 30 31 32 25 26 27 28 29 30 31 32---------0--------8
Left
Block (32 bits)
1 2 3 4 5 6 7 8 33 34 35 36 37 38 39 40---------7--------1
9 10 11 12 13 14 15 16 41 42 43 44 45 46 47 48---------5--------3
17 18 19 20 21 22 23 24 49 50 51 52 53 54 55 56---------3--------5
25 26 27 28 29 30 31 32 57 58 59 60 61 62 63 64---------1--------7
Output Byte 8 7 6 5 4 3 2 1
From FIPS Pub 46-2:
Final Permuation IP-1:
Output Byte
40 8 48 16 56 24 64 32 1
39 7 47 15 55 23 63 31 2
38 6 46 14 54 22 62 30 3
37 5 45 13 53 21 61 29 4
36 4 44 12 52 20 60 28 5
35 3 43 11 51 19 59 27 6
34 2 42 10 50 18 58 26 7
33 1 41 9 49 17 57 25 8
1 2 3 4 5 6 7 8 Port Bit
7 6 5 4 3 2 1 0 MSB7 Bits
In the simplest hardware implementation of DES, the Left and Right blocks are comprised in hardware of four 8 bit register each. Each 8 bit register can be serially loaded (IP), serially unloaded (IP-1), or parallel output and parallel loaded (round interation). DES is an encryption algorithm originally required to be implemented in hardware, specified in 1977 - predating 16 or 32 bit microprocessor peripherals.
Permuted Choice 1
PC1 performs a similar function loading the C and D 28 bit registers (comprised of three 8 bit bidirectional shift register and 1 4 bit bidirectional shift register, all with parallel outputs). The C and D registers can be serially loaded (shifting right), or serially shifted left or right in a closed ring for encryption or decryption.
Port MSB7
Bits Bits
Input (CD) C
Block, 64 bits Block (28 bits)
1--------7------57 49 41 33 25 17 9 1 MS 1 2 3 4 5 6 7 8
2--------6------58 50 42 34 26 18 10 2 9 10 11 12 13 14 15 16
3--------5------59 51 43 35 27 19 11 3 17 18 19 20 21 22 23 24
4--------4------60 52 44 36 ----------- (C(28)) 25 26 27 28
D
Block (28 bits)
7--------1------63 55 47 39 31 23 15 7 1 2 3 4 5 6 7 8
6--------2------62 54 46 38 30 22 14 6 9 10 11 12 13 14 15 16
5--------3------61 53 45 37 29 21 33 5 17 18 19 20 21 22 23 24
4-------(D(25)--------------28 20 12 4 25 26 27 28
8--------0------64 56 48 40 32 24 16 8 LS (parity)
Input Byte 8 7 6 5 4 3 2 1
Note that bit 4 is used as input for both C and D. This implies that C(28) output is used as the serial input to D(25). The least significant bit is used for odd parity.