Impact and purpose of IP/FP in DES

[Martin Olsson]

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.

Yesterday, I got past the boring framework stuff and started coding
the real cryptography parts. I've read quite alot about DES lately,
and I'm aware of the fact that IP/FP (Initial/Final Permutations)
are sometimes left out of DES software implementations because they
are messy to code and does not increase the algoritms security.

I've choosen to make the IP/FP optional, so last night I went ahead
and typed in the IP/FP matrices and wrote a quick little PermuteBits()
routine. While I was entering the IP I made a "strange" discovery,
or more likely its not strange at all -- I just dont know enough
about DES to explain it. 

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":

<quote>

"The initial permutation and the corresponding final permutation do not
affect the security of DES. (As near as anyone can tell, its primary
purpose is to make it easier to load plaintext and ciphertext data into a
DES chip in byte sized pieces. Remember that DES predates 16-bit or 32-bit
microprocessor busses.) ... many software implementations of DES leave out
both the initial and the final permutations. ... While the new algorithm is
no less secure than DES, it does not follow the DES standard and should not
be called DES."

</quote>

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?

Included below, are the two matices IP and PC-1. The FP matrix is of
course the the IP matrix performed backwards so to speak. These tables
should be read as:

PrePC1Bits = the bits that is to be permuted
PostPC1Bits = the resulting bits, once PC-1 has been applied
Permutation algorithm is:
"the 1 bit of PostPC1Bits is the 57 bit of PrePC1Bits"
"the 2 bit of PostPC1Bits is the 49 bit of PrePC1Bits"
"the 3 bit of PostPC1Bits is the 41 bit of PrePC1Bits"
"the 4 bit of PostPC1Bits is the 33 bit of PrePC1Bits"
etc etc etc

RELEVANT TABLES:

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);

IP:     (58, 50, 42, 34, 26, 18, 10,  2,
         60, 52, 44, 36, 28, 20, 12,  4,
         62, 54, 46, 38, 30, 22, 14,  6,
         64, 56, 48, 40, 32, 24, 16,  8,
         57, 49, 41, 33, 25, 17,  9,  1,
         59, 51, 43, 35, 27, 19, 11,  3,
         61, 53, 45, 37, 29, 21, 13,  5,
         63, 55, 47, 39, 31, 23, 15,  7);


All comments, references to info (offline/online),
and explainations are greatly appreciated! Thanks.


Regards,
/m
-
__,,,^..^,,,_________________________________________________
  mnemo$11a.nu  www.mnemo.nu  www.delphi-jedi.org  www.11a.nu
  member of the eleventh alliance development & security team




---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com