lect1  Lecture 8

"Iterative (product) ciphers. Feistel construction. Lucifer and DES."

 0. We have finished information theoretic part of Shannon's paper by
studying conditional entropy (equivocation) of the key or message as a
function of the length of intercepted cryptogram. While, as Shannon has
shown, information theoretic approach falls short  for real life ciphers, it
provides an important basis and motivation for practical secrecy (complexity
theoretic) approach,  which will be the topic of our study in the rest of this
course. [this material will appear in about two weeks in the lecture notes].

 1.We will study applications of Shannon's ideas on mixing transformations,
confusion and diffusion elements. Substitution-Permutation Networks (SPN).
[we have seen a slide with avalanche of differences taken from Feistel's paper]

If you want an example of a measure preserving mixing transformation
consider the following:
(x,y) -> (2x,1/2y) mod 1 (if 0<x<1/2),
(x,y) -> (2x,1/2(y+1)) mod 1 (if 1/2<x<1),
where x,y are from the unit interval [0,1].
This is a famous baker's transform (roll, cut, fold). The operations do not
commute and thus good mixing is provided. You can check this by picking
a random point  x and plotting say 10000 iterations of T(x). The trajectory
will be dense in the unit square. Another example is to pour a milk in
a cup of coffee. Doing several mixing operations with a spoon you hope to
receive a homogeneous liquid, i.e. every small volume of the cup should
have the amount of milk proportional to its size.

Warning: natural mixing transforms (chaotic maps, etc.) which have good asymptotic
mixing behavior are usually not good for cryptographic purposes. Strong ciphers
should provide good mixing in a small number of iterations (8, 16, 32).

One of the AES candidates: Serpent is an example of a SPN (to be more exact it is a
Substitution-LinearTransformation Network). Iterations of the same function
are used to achieve better mixing and are called "rounds".

2. Description of Lucifer -- an example of early SPN (early 1970-s, IBM).
(30.04.2000)

64, 128 - bit block size.
128-256 bit key size.
8-16-32 rounds (iterations).
S-boxes 4x4 bits (small due to hardware constraints).
 

Here is a more detailed description of one variant of this cipher from IBM TR (1970) (Horst Feistel),
S-boxes and P-permutation are not specified:

a. 128-bit block is divided into two 64-bit halves in a Feistel structure (see below).
b. 256-bit key is stored in 16, 16-bit shift registers
c. 4x4 bit S-boxes S1 and S0 (16 boxes in each round).  The key bit is used to make a
choice between the two S-boxes (so for each round 16 key bits are used for the S-box control
pattern).  This block provides  "confusion".
d. Fixed permutation of 64-bits -- a "diffuser"
e. After performing substitutions and a permutation the result is XORed with 64-bits of the
key. Thus each round subkey has 16+64 key bits which are taken from the key shift-registers.
The only requirement is that S-box control bits for each pair of boxes are taken from different
shift registers.
f. There are 16 rounds, so that after the encryption the key is in a position ready for the encryption of the next block.  The choice of the number 16 is said to be a "reasonable guess", while possibility of 8 and 32 rounds
depending on the further analysis is mentioned.
g. Mangler (optional) -- there is a possibility to  make Feistel's swap conditional. For each pair of bits
a key bit decides if the bits are to be swapped or to remain in their places.

Note that the only unknown element is the secret key (satisfying Kerkhoff's cipher design rules).
Brief assessment: With more than 16 rounds, careful choice of S-boxes, permutations and key-schedule
this cipher looks quite strong even by modern criteria. Attacks on smaller variants of this cipher are
given in [5] and [6]. The idea of a mangler does not look very useful.
 
 

3. Feistel ciphers. (read Feistel's popular paper in Scientific American.)
The idea is to construct a cipher (as a product of involutions) in such a way
that encryption and decryption can be performed by the same function with
a small adjustment of the secret keys.

Advantages:
a. Two times larger block can be handled.
b. The cipher is always uniquely decipherable.
c. Designer can concentrate on the internal properties of the round functions.

Some old IBM patents on block-ciphers:
US3798360  3 /1974  Feistel   (IBM)   STEP CODE CIPHERING SYSTEM
US3798359  3 /1974  Feistel   (IBM)   BLOCK CIPHER CRYPTOGRAPHIC SYSTEM
US3798605  3 /1974  Feistel   (IBM)   CENTRALIZED VERIFICATION SYSTEM
US3796830  3 /1974  Smith    (IBM)   RECIRCULATING BLOCK CIPHER CRYPTOGRAPHIC SYSTEM
US3962539  6 /1976  Ehrsam (IBM)   Product block cipher system for data security
US3958081  5 /1976  Ehrsam (IBM)   Block cipher system for data security
US4078152  3 /1978  Tuckerman, III  Block-cipher cryptographic system with chaining
US4195200  3 /1980  Feistel   (IBM)   Key controlled block-cipher cryptographic system employing a multidirectional shift matrix
US4316055  2 /1982  Feistel   (IBM)   Stream/block cipher crytographic system

4. Description and basic design principles of DES. The rest of the design
principles for this cipher will be covered when we come to "differential
cryptanalysis". DES algorithm is a standard and is used in a large variety
of applications. Each time you type your PIN number when using your
credit card, the ATM performs a DES encryption for you. Here are the
details on this process.
[we have seen complementation property of DES]

Reading

1. Claude Shannon, "Communication Theory of Secrecy Systems", Bell. Sys.
Tech. J., 1950.

2. FIPS PUB: The Data Encryption Standard.

3. Horst Feistel, "Cryptography and Computer Privacy", Scientific American,
Vol. 228, No.5 , 1973.

4. H.Feistel, W.A.Notz, J.L. Smith, "Cryptographic Techniques for Machine to
Machine Data Communications", RC 3663 (#16560), December 27, 1971,
Communications, IBM T.J.Watson RC.

5. E. Biham, A.Shamir, "Differential cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer",
   Technical report CS91-18, Weizmann Institute of Science CRYPTO'91, or in the book:

   Eli Biham, Adi Shamir,
   Differential Cryptanalysis of the Data Encryption Standard,
   Springer Verlag, 1993. ISBN: 0-387-97930-1, 3-540-97930-1.

6. Ishai Ben-Aroya, Eli Biham,
   Differential Cryptanalysis of Lucifer ,
   CS 782, October 1993,   Proceedings of Crypto'93, LNCS 773
   Journal of Cryptology, Vol. 9, No. 1, pp. 21-34, 1996.

In the next lectures we will cover: attacks on modified or round-reduced
variants of DES, generic attacks on one-way functions by Hellman.