Cryptography - Lecture 7 - Modern Block Ciphers

Objectives

Preliminary Reading

Lecture Content

Modern Block Ciphers

1. Modern Block Ciphers
   • will now look at modern block ciphers
   • one of the most widely used types of cryptographic algorithms
   • provide secrecy and/or authentication services

     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.

2. Private-Key Encryption Algorithms
   • also called single-key or symmetric algorithms
   • both parties share the key needed to encrypt and decrypt messages
   • hence both parties are equal
   • classical ciphers are private-key
   • modern ciphers (developed from product ciphers) include DES, Blowfish, IDEA, LOKI, RC5, Rijndael (AES) and others

     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.

3. Block Ciphers
   • in a block cipher the message is broken into blocks
   • each of which is then encrypted
   • ie like a substitution on very big characters - 64-bits or more
   • most modern ciphers we will study are of this form

   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.

Theoretical Foundations

1. Theoretical Foundations
   • ideally want one extremely large substitution
   • not practical since would need a table with 264 entries in it for a 64-bit block
   • so approximate by constructing from smaller building blocks
   • using idea of a product cipher
   • concepts developed by Shannon and Feistel
2. Shannons Theory of Secrecy Systems
   • Claude Shannon wrote some of the pivotal papers on modern cryptology theory
   • C E Shannon, "Communication Theory of Secrecy Systems", Bell System Technical Journal, Vol 28, Oct 1949, pp 656-715
   • C E Shannon, "Prediction and Entropy of printed English", Bell System Technical Journal, Vol 30, Jan 1951, pp 50-64
   • in these he developed the concepts of:
     • entropy of a message,
     • redundancy in a language,
     • theories about how much information is needed to break a cipher
     • defined the concepts of computationally secure vs unconditionally secure ciphers

     Have already seen some of the results of his 1951 paper when we discussed entropy, language redundancy and unicity distances.

3. Shannons Theory of Secrecy Systems cont
   • showed that the Vernam cipher is the only unconditionally secure cipher
   • provided the key is truly random and used once only
   • also showed that a Book cipher is not secure
     • ie. if try to encrypt English text by adding to other English text
     • not secure since English is 80% redundant
     • giving ciphertext with 60% redundancy, enough to break
   • a similar technique can also be used if the same random key stream is used twice on different messages
   • the redundancy in the messages is sufficient to break this

     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.

4. Substitution-Permutation Ciphers
   • in his 1949 paper Shannon also introduced the idea of substitution-permutation (S-P) networks
   • which form the basis of modern block ciphers
   • an S-P network is the modern form of a substitution-transposition product cipher
   • S-P networks are based on the two primitive cryptographic operations we have seen before:
     • a Substitution
     • a Permutation

     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.

5. The Substitution Operation
   • a binary word is replaced by some other binary word
   • the whole substitution function forms the key
   • if use n bit words, the key is 2ⁿ! bits, which grows rapidly as n increases
   • can also think of this as a large lookup table
   • with n address lines (hence 2ⁿ addresses)
   • each n bits wide, being the output value
   • will call them S-boxes

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

6. The Permutation Operation
   • a binary word has its bits reordered (permuted)
   • the re-ordering forms the key
   • if use n bit words, the key is n!bits
   • which grows more slowly, and hence is less secure than substitution
   • this is equivalent to a wire-crossing in practise (though is much harder to do in software)
   • will call these P-boxes

     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.

7. Substitution-Permutation Network
   • Shannon combined these two primitives
   • have sets of S-boxes linked by a P-box
   • he called these mixing transformations

     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.

8. Practical Substitution-Permutation Networks
   • in practise we need to be able to decrypt messages, as well as to encrypt them, hence either:
     • have to define inverses for each of our S & P-boxes, but this doubles the code/hardware needed, or
     • define a structure that is easy to reverse, so can use basically the same code or hardware for both encryption and decryption
9. Feistel Ciphers
   • Horst Feistel, working at IBM Thomas J Watson Research Labs devised just such a structure in early 70's, which we now call a feistel cipher
   • the idea is to partition the input block into two halves, L(i-1) and R(i-1), and use only R(i-1) in the ith round (part) of the cipher
   • the function g incorporates one stage of the S-P network, controlled by part of the key K(i)known as the ith subkey

     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.

10. Feistel Ciphers
    • can be described functionally as:

      L(i) = R(i-1)
      R(i) = L(i-1) XOR g(K(i), R(i-1))
      

    • this can easily be reversed as seen in the above diagram, working backwards through the rounds
    • in practise link a number of these stages together (typically 16 rounds) to form the full cipher

    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.

Fundamental Design Principles

1. Fundamental Design Principles
   • Shannons mixing transformations a special form of product ciphers
   • the components work together, so that overall:

     S-Boxes

     providing confusion of input bits

     P-Boxes

     providing diffusion across S-box inputs

   • these were further codified by Webster & Tavares as Avalanche and Completeness

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

2. Avalanche effect
   • where changing one input bit results in changes of approx half the output bits
   • more formally, a function f has a good avalanche effect if:
     • for each bit i,0<=i<m, if the 2^m plaintext vectors are divided into 2^m-1 pairs X and X_i with each pair differing only in bit i and if the 2^(m-1) exclusive-or sums, termed avalanche vectors, V_i = f(X) XOR f(X_i) are compared, then about half of these sums should be found to be 1.

     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.

3. Completeness effect
   • where each output bit is a complex function of all the input bits
   • more formally, a function f has a good completeness effect if:
     • for each bit j,0<=j<m, in the ciphertext output vector, there is at least one pair of plaintext vectors X and X_i which differ only in bit i, and for which f(X) and f(X_i) differ in bit j

     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.

4. Block Cipher Design
   • these principles are critical in the design of good block ciphers
   • avalanche ensures that small changes to input make large changes to output
   • which means even if an attacker guesses close, the result is nowhere near what is wanted
   • completeness ensures that every output bit depends on all the input bits
   • so an attacker is unable to "divide and conquer" in attacking the cipher
   • as we've seen, classical ciphers don't have these properties
5. Feistel Cipher Design
   • the following design parameters are usually considered in the cipher design:

     block size

     increasing size improves security, but slows cipher

     key size

     increasing size improves security, makes exhaustive key searching harder, but may slow cipher

     number of rounds

     increasing number improves security, but slows cipher

     subkey generation

     greater complexity can make analysis harder, but slows cipher

     round function

     greater complexity can make analysis harder, but slows cipher

   • all a matter of tradeoffs
   • not hard to design a "secure" block cipher, just use a very large number of rounds, but will be very slow
   • getting a fast, secure, cipher is much harder

     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.

6. Some General Words on Cipher Design
   • Good Cipher Design has avalanche, completeness, unpredictability
   • Bad Cipher Design has (lack of) randomness, too much predictability
   • many ciphers have been broken (incl. commercial products like Wordperfect, pkzip, all current mobile phone ciphers)
   • even the experts get it wrong
   • best to use tested, proven ciphers designed from experience

     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

1. Lucifer
   • the first known practical example of a substitution-permutation cipher
   • developed by Horst Feistel at IBM labs
   • best known public reference is his paper: Horst Feistel, "Cryptography and Computer Privacy", Scientific American, Vol 228(5), May 1973, pp 15-23.
   • provides an overview of his work, but actual details of Lucifer are very sketchy
   • the best detailed reference is: Arthur Sorkin, "Lucifer, A Cryptographic Algorithm", Cryptologia, Vol 8(1), Jan 1984, pp 22-41, with addenda in Vol 8(3) pp260-261
   • contains a detailed description of the algorithm, plus a Fortran implementation

     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.

2. Lucifer Overview
   • original descriptions are not the clearest, see Sorkin Fig 1 p24
   • redrawn in modern form, Lucifer has the following form:

     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.

3. Lucifer Key Schedule
   • Lucifer is a Feistel cipher with 128-bit data blocks and 128-bit keys
   • the subkeys used in each round are taken from the left part of the key
   • key is then rotated left 56-bits, so all key bits are used

     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.

4. Lucifer Data Computation
   • the data computation had 16 rounds using the subkey and RH side as inputs to the round function
   • and XORing the output witht he LH side before exchanging them
   • the S-P function for Lucifer has the following structure:
     • substitution using 8 identical pairs of 4-bit S-boxes (S0 & S1)
     • these were used in alternate order (S0|S1) or (S1|S0) depending on the key
     • then the subkey is added modulo 2 to their outputs
     • and the result is permuted through a combination of small 8-bit permutations and a large 128-bit simple permutation (convolution)
   • for details see Sorkin

     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.

5. Lucifer Security
   • Lucifer has not been extensively analysed
   • is now known to be theoretically broken by differential cryptanalysis
   • not in current use
   • main claim is is predecessor the DES

Summary

1. Summary
   • have discussed:
   • concept of block ciphers and their theoretical foundations
   • concept of feistel ciphers, giving avalanche and completeness
   • Lucifer structure in brief

Exercises

1. Exercises
   1. A Shannon style Substitution Box (S-box) grows in size as the number of input bits increases. For inputs of 4, 6, 8, 10, and 12 bits, list how many entries would be required. How large would each of these entries be, and why? What are the implications for the growth of this number on implementing such S-boxes in hardware, software (on a smartcard, PC)? Now consider a Permutation box (P-box). Much larger P-boxes can be used than S-boxes, why? How would you implement a P-box in hardware, software?

Additional References