Impact and purpose of IP/FP in DES
David G. Koontz
koontz at ariolimax.com
Wed Apr 25 10:46:31 EDT 2001
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 at 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<ftp://ftp.cryptocd.com/pub/cryptocd/source/cyphers/des/c/koontz/>
(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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: des.pdf
Type: application/pdf
Size: 9484 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20010425/fe7157ed/attachment.pdf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dslice.pdf
Type: application/pdf
Size: 4921 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20010425/fe7157ed/attachment-0001.pdf>
-------------- next part --------------
Newsgroups: sci.crypt
Subject: Re: DES's initial permutation
Summary:
Expires:
References: <jktaberD9CGw3.5xF at netcom.com> <DD7CtL.3AM at ulysses.homer.att.com> <ssampson.186.000A7668 at icon.net>
Sender:
Followup-To:
Distribution:
Organization: MasPar Computer Corporation
Keywords:
In article <ssampson.186.000A7668 at icon.net> ssampson at icon.net (Steve Sampson) writes:
>In article <DD7CtL.3AM at ulysses.homer.att.com> smb at research.att.com (Steven Bellovin) writes:
>>In article <jktaberD9CGw3.5xF at netcom.com>, jktaber at netcom.com (John K. Taber)
>writes:>> Nick Barron (nik at 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.
More information about the cryptography
mailing list