How do substution-permutation networks work? I understand what's going on in higher level. But i don't understand what's really going on in page 3 and 4 of this slide. 

Specifically,


How S0 and S1 is used? What goes in what goes out?
How exactly  key bits determine
which s-box is to be
used at each position? Position refers to what?
is the function "f" in page 4 exactly the same SP network in page 3? 
why split plain text into left L and right R?
why XOR L with R after applying "f"? 
why rotate after  applying last "f"?
why XOR is used? why not some other bitwise operation?


preceding slides for reference
1) and 2) Either S0, or S1 is used for each 4-bit long part of block depending on key bits. 16 S-boxes are used in each round (because you split 64-bit-long block into 16 parts of length 4) of the Lucifer cipher, so each round needs a 2 byte long subkey.

Example:

16 starting bits of the key (the first subkey):

0 0 1 0 1 1 1 1 0 0 1 0 1 0 0 1 (2 bytes together)

S-boxes used in the first round:

S0 S0 S1 S0 S1 S1 S1 S1 S0 S0 S1 S0 S1 S0 S0 S1 (4 bit input/output each, 64 bits together)

3) No, not necessarily. Feistel's scheme is a general solution based on any S-box and any permutation P. The Lucifer SP is just one example of a possible SP. Feistel's scheme can be used with non-invertible function F, too. You don't need to use SP, although it is the most common choice.

4) and 5) Because this is how Feistel designed his scheme... He wanted to develop a hard-wired device he could safely use for both encryption and decryption and which would have all the great features provided by SP network (avalanche effect, non-linearity,...). You cannot use the same device for both encryption and decryption with basic SP network decribed on page 3 of your slides.

Why did he decide to rotate L and R after each round? If there is no rotation, R stays untouched - not very good for an encryption scheme, right?

6) Your slides are a little bit confusing, I think this picture illustrates Feistel's scheme better:



As you can see, if you place all XORs on the left and uses the right part always as an input of F, you rotate L and R after each round except the final one. Why not? Because the final rotation does not depend on key, so it would provide no extra security.

7) Because it is fast to compute XOR by our hardware and because the result depends equally on both input bits. If you used AND and the result was 1, you would know the input was 1 independently on the key, which is not what you really want, right? The same problem with OR and 0 result.



Linear cryptanalysis (based on comments):

Let's have a block cipher, output of which can be represented as a system of linear equations:

C1 = a11P1 XOR a12P2 XOR ... XOR a1nPn XOR b11K1 XOR ... XOR b1kKk

C2 = a21P1 XOR a22P2 XOR ... XOR a2nPn XOR b21K1 XOR ... XOR b2kKk

...

Cn = an1P1 XOR an2P2 XOR ... XOR annPn XOR bn1K1 XOR ... XOR bnkKk

where Ci stands for the i-th bit of the ciphertext, Pj is the j-th bit of plaintext, Kp is the p-th bit of the secret key and coefficients aij and bij are some wellknown 0/1 constants defined by the design of the cipher.

If you had enough plaintext-ciphertext pairs known for the same key, you could solve the equation system and find the key value. That would be a problem, right? That is why modern ciphers are never linear - you cannot write their output as a system of linear equations of input bits and key bits as above.

S-boxes in SP networks are always chosen not to be linear and even more, it must be difficult to approximate them by linear equations, otherwise the whole SP network would be vulnerable to linear cryptanalysis.

If you chose S-boxes of your SP network wisely, the whole network will be non-linear (therefore safe against linear cryptanalysis) and so will be Feistel's scheme based on this SP network.

However, this is just a basic intro. The linear cryptanalysis is very interesting and very complex topic and you should find some more detailed source of information in case you are interested.



Feel free to ask.