From koontz@ariolimax.com Tue Sep 11 02:48:36 2001 Date: Wed, 25 Apr 2001 07:46:31 -0700 From: David G. Koontz Reply-To: koontz@no_spam_ariolimax.com To: cryptography@wasabisystems.com, mnemo@home.se Subject: Re: Impact and purpose of IP/FP in DES Martin Olsson wrote: > > Dear Members, > > I'm currently working on my own DES software implementation which > can handle reduced rounds etc. This is mostly a learning project, > and I do not intend to use my code for any product or such. > > > I've found that PC-1 (the first keyspace permutation, which mixes > the key bits and selects the 56 out of 64 real key-bits) and the > IP (Initial Permutation) are closely related to each other. The first > elements of the IP matrix can be calculated through adding 1 > to the first elements of the PC-1 matrix. Later on, the difference > between these two becomes two, and then three etc, > > I've searched the net and a few good books, on reasons to apply > the IP. From Bruce Schneier's excellent book; "Applied Cryptography": > > > First; I do not exactly understand what Mr.Schneier means. How can it be > easier to transfer 8-bits of data into a chip if one first rearranges the > bits? (eg; why wouldn't I just chop the 64-bits into 8 separate 8 bit chunks) > Perhaps I got it all wrong (i dont speak native english), but sevral sources > indicate similar "explainations" to this little feature. Perhaps there are > some intelligent (non-NSA) folks around who are kind enough to explain this > to me? Or atleast give me some hints/comments/thoughts on this issue. > > MY QUESTION(s)... > > ..is: If IP/FP has no effect on the security of DES. Why are PC-1 and > IP related? Wouldn't that imply that IP/PC-1 are co-functioning in some > strange way (a cooperation which logically would be cancelled if I omit > the IP from the implementation) -- or atleast that they preform a similar > function? > > One *solution* could be, "since the key aswell as the block has to go into > a chip -- its logic to apply the same kind of make-it-easier-to-transfer > algo on both". But still I do not understand why these permutations are > performed? And why are the permutations slightly different when applied > to the key versus the IP? > > Does this mean that PC-1 can be omitted too, without loosing security? > Of course one still have to select the 56-bits of real keydata. But the > actual permutation of the bits, seems to be, irrational or unnessecary? > What you are risking here is the right to refer to you software as DES. If it isn't compliant with the Digital Encryption Standard, it isn't the Digital Encryption Algorithm. The Initial and Final Permutations, as well as the Permuted Choice 1 specify how to get particular bits of data into (from for FP) particular registers (when viewed as a hardware implementation). If two implementations were to be allowed to interface data in more than one way, they couldn't interchange data. I've included a copy of a usenet posting from 1994 explaining the permutations. I received a copy of FIPS 46 from a chip designer at Fairchild in 1978 while working on crypto in the military. I probably still have my notes on plotting out the permutations into hardware. Mr. Rallapalli at Fairchild implemented the 9414 chips set which basically implemented a byte of L, a byte of R, two mask programmable S boxes, and either the C or D registers in a 40 pin bipolar IC. The implementation was especially good at showing the nature of the IP/FP permutations and PC1. These being a pattern of 8 wires. I've shown this in a VHDL model of DES I did. I'd be willing to send some one the VHDL model which illustrates the 'disappearing permutations'. In 1996 enholm@login.eunet.no (Morten Enholm) was trying to get a copy of it from Mark Riordans ripem site (ripem.msu.edu). I'd be willing to vhdl pretty print them into a pdf file so you could read the code (vhdl_des.tar.z). I'm not personally aware of any foreign copies of the VHDL code. There are three european VHDL implementations of DES in VHDL available on the Web, all three are essentially translated from C, and show the permutations. I'm including the toplevel as a pdf, which shows the translation between byte bit order (7 downto 0) and NSA or IBM order (1 to 8), and hides the IP in DIN(7 downto 0) and FP in DOUT(7 downto 0) connections to the four DSLICE's (9414 chip equivalents, sans C and D registers). I'm also including dslice.vhdl as a pdf so you can see the organization. You can find a sample C des implementation at: url (Either init_perm.c or inv_perm.c has a "| =" that should be "|=" for gcc. Some of the source files in this directory have CRLF instead of just newlines, which can give some tools problems (make in particular). This des program compiles for either big or little endian machines, although the table size is unfriendly to small cache processors. I wrote three generations of much faster code I never released publicly.) Of note are the FIPS Spec PUB 500-20 test vectors found in the file des.test. I believe one of the test vectors has a key parity bit flipped in this copy. In 1995 I figured out how to reduce the size of lookup tables for IP and FP in a C implementation. By the way, PC1 is a permuted choice instead of a permutation, because the parity bits in the key does not go into the C or D registers. -- remove "no_spam_" from Reply-to address [ Part 2, Application/PDF 12KB. ] [ Unable to print this part. ] [ Part 3, Application/PDF 6.7KB. ] [ Unable to print this part. ] [ Part 4: "Attached Text" ] Newsgroups: sci.crypt Subject: Re: DES's initial permutation Summary: Expires: References: Sender: Followup-To: Distribution: Organization: MasPar Computer Corporation Keywords: In article ssampson@icon.net (Steve Sampson) writes: >In article smb@research.att.com (Steven Bellovin) writes: >>In article , jktaber@netcom.com (John K. Taber) >writes:>> Nick Barron (nik@dreamland.tcp.co.uk) wrote: >>> : I've recently been re-reading some of the textbooks I have, and I was >>> : wondering if anyone could enlighten me on the purpose of the DES IP? I've >>> : read in one source that it has been shown to increase DES's resistance to >>> : cryptanalysis (differential IIRC), but with no further reference. >>> >>> : Can anyone shed any light on this? >>> >>> >>> >>> Somebody, I forgot who now (Lynn ???) convinced me that the purpose of >>> the IP was hardware considerations in 197x. I had always wondered about >>> this too. >>> >>> I'm sorry, I don't remember the explanation well enough to repeat it for >>> you. I found it convincing. > >>Yup. It's got to do with serial-parallel conversion -- chips in 197x >>didn't have nearly as many pins as do modern ones... > >The IP was designed to shuffle the EBCDIC bit pattern, as it has a signature. >It doesn't do anything for ASCII, and can be deleted. > 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.