Modern block ciphers are widely used to provide encryption of quantities of information, and/or a cryptographic checksum to ensure the contents have not ben altered. We continue to use block ciphers because they are comparatively fast, and because we know a fair amount about how to design them.
Private key / Single Key / Symmetric - all refer to characteristics of these ciphers. They have only one key, which must be kept secret, and which is used both to encrypt messages, and decrypt messages. Since either person knowing the key could have encrypted any message, they are equivalent, ie symmetric. The design of block ciphers has evolved from the concept of product ciphers.
Block ciphers work a on block / word at a time, which is some number of bits. All of these bits have to be available before the block can be processed. cf stream ciphers which work on a bit or byte at a time.
2^{64}
entries in it for a 64-bit
block
Have already seen some of the results of his 1951 paper when we discussed entropy, language redundancy and unicity distances.
Have discussed this previously when discussing autokey classical ciphers - where English text say is used as the source of a substitution key (either the message itself with a keyword prepended, or thru reference to a book). The issue is still that some letters occur more frequently than others, and this gives information to the analyst. Its critical that a cryptographic key be unpredictable, ie random.
Its his 1949 paper which has the key ideas that led to the development of modern block ciphers. Critically, it was the technique of layering groups of S-boxes separated by a larger P-box to form the S-P network, a complex form of a product cipher.
To implement an S-box, essentially need either to decode every possible binary value of the input word, and map to the appropriate output word, or need a memory with as many entries are there are possible input values. Back in the 70's, limitations of silicon chip hardware meant S-boxes could only be 4-bit (16 entries) to 6-bit (64 entries) in size. More recent block ciphers can use larger boxes (8 to 12 bits for example).
Compared to an S-box, a P-box only needs to exchange as many wires/bits as there are in a word. ie a 32-bit word needs 32 wire crossings or bit shufflings. Hence these can be much larger.
Remember that can only have small S-boxes, but can have a P-box as large as the block we are using. So group a set of S-boxes together, and then link them using a single large P-box which distributes the outputs from the S-boxes, across many/all the S-boxes in the next stage.
One of Feistel's main contributions was the invention of a suitable structure which adapted Shannon's S-P network in an easily inverted structure. Essentially the same h/w or s/w is used for both encryption and decryption, with just a slight change in how the keys are used. One layer of S-boxes and the following P-box are used to form the function g.
L(i) = R(i-1) R(i) = L(i-1) XOR g(K(i), R(i-1))
At the end of the round, have all the information necessary to undo it. The old RH side has become the new LH side. Hence use that value to recompute the value of function g. When add the value (output) of g back to the new RH side, since an XOR is its own inverse, XOR'ing witht eh same value twice egts us back to the original value, the old LH side. Note - if unsure of the basic logical operators: AND OR NOT XOR, you should go and revise them.
A F Webster & S E Tavares "On the Design of S-boxes", in Advances in Cryptology - Crypto 85, Lecture Notes in Computer Science, No 218, Springer-Verlag, 1985, pp 523-534
The key aim with modern block ciphers is to destroy, as far as possible, any of the statistical charcteristics that exist in the original message, and which make classical ciphers vulnerable to attack. The idea of diffusion is to spread/smear the statistics over a range of bits, or put another way, to have each part of the plaintext affect a large part of the ciphertext, thus making the statistical relationship between the ciphertext and plaintext as difficult as possible. This is achieved by the P-boxes spreading the outputs of the S-boxes as widely as possible (nb. that P-boxes alone don't give diffusion). The idea of confusion is to make the statistical relationship between the ciphertext and key as difficult as possible. This is primarily achieved by using a complex, non-linear, substitution operation (S-box).
To "measure" avalanche, its necessary to look at each input bit in turn, and then for every possible value of the other bits, compare outputs created when the input bit under consideration is a 0 and a 1. The number of output bits which differ between these should, on average, be about half of them (ie with DES which uses 64 bit blocks, as you change just 1 bit, roughly 32 output bits should change). Note: the formal description uses an XOR, which has the characteristic of setting a 1 wherever the input bits differ.
To "measure" completeness, its necessary to look at each output bit in turn, and then for every input bit, find a pair of inputs, differing only in the input bit being looked at, which result in the output bit changing. This means that every input bit influences the result of every output bit.
Much of the debate over the selection of the new Advanced Encryption Standard cipher Rijndael revolved around the tradeoffs between speed, complexity and security; the result had to be a compromise.
Very common for people with a little cryptographic knowledge to design a cipher, only to miss the obvious flaws. Not even the experts get it right, cf. the case of Magenta in the AES. Hence the importance of relying on publically tried, tested and proven ciphers that have a history of standing up to the best efforts of the cryptographic research community. The AES process has been exemplary in this respect.
Lucifer was the practical realisation of Feistel's work on cipher structures. It was proposed for use in some IBM equipment in the early 70's. The Scientific American paper first made known this new approach, but was very sketchy on details (reflecting the sensitivity with which governments viewed all things related to crpytography). It was quite some time later before the detailed design became known.
The original diagrams in Sorkin, based on the research reports on the cipher, reflect to a fair degree the hardware implementation of the cipher (focusing on the shift registers and wiring). The form I've redrawn it as is closer to how we mostly consider modern ciphers.
The Lucifer key schedule is very simple, this is one of the deficiencies in the design as we know now. It simply took the left 64 bits and used them in the round, and then rotated the key bits left by 56 bits. Thus over the 16 rounds, all bits were used a number of times, but in different places.
The number of rounds at 16 is typical. The structure is classic Feistel. The S-box size of 4-bits reflects the limitations of the h/w at the time.