• S-boxes: lookup tables that map n bits to m bits (where n and m often are equal).
  
  There are several ways of constructing good S-boxes for ciphers, as well as several ways of measuring them. Some designers use a rigorous mathematical approach by using bent functions (or related) to create S-boxes which can be proven to be resistant against some particular attacks. Other designers use heuristic approaches, which may lead to S-boxes that are more difficult to handle in mathematical proofs, but can have additional benefits (such as several different implementation options).
  
  The S-box may even be the only non-linear part of the cipher. This is the case in the block cipher DES, and thus may be regarded as the single most important part of the algorithm. In fact, many consider DES's S-boxes so good that they use them in their own designs (for example, Serpent).
  
  
  
• Feistel networks: a Feistel network is a general device of constructing block ciphers from simple functions. The original idea was used in the block cipher Lucifer, invented by Horst Feistel. Several variations have been devised from the original version.
  
  Put simply, the standard Feistel network takes a function from n bits to n bits and produces an invertible function from 2n bits to 2n bits. The basic function upon which the structure is based is often called the round function. The essential property of Feistel networks that makes them so useful in cipher design is that the round function need not be invertible, but the resulting function always is.
  
  If the round function depends on, say, k bits of a key, then the Feistel cipher requires rk bits of the key where r is the number of rounds used.
  
  The security of the Feistel structure is not obvious, but analysis of DES has shown that it is a good way to construct ciphers. It is compulsory that a Feistel cipher has enough rounds, but just adding more rounds does not always guarantee security.
  
  
• The operation of taking the user key and expanding it into rk bits for the Feistel rounds is called key scheduling. This is often a non-linear operation, so that finding out any of the rk bits of the round keys does not directly provide any information about the actual user key. There are many ciphers that have this basic structure; Lucifer, DES, and Twofish, just to name a few.
  
  
• Expansion, Permutation: these are common tools in mixing bits in a round function. They are linear operations, and thus not sufficient to guarantee security. However, when used with good non-linear S-boxes (as in DES) they are vital for the security because they propagate the non-linearity uniformly over all bits.
  
  
• bit slice operations (bitwise logic operations XOR, AND, OR, NOT and bit permutations): The idea of bitslice implementations of block ciphers is due to Eli Biham. It is common practice in vector machines to achieve parallel operation. However, Biham applied it on serial machines by using large registers as available in modern computers. The term "bitslice" is due to Matthew Kwan.
  
  Basically all block ciphers can be written in bitslice manner, but operations such as addition and multiplication may become very slow. On the other hand, permutations are almost free as they just require naming of the registers again and this can be done one the coding level. Thus, for example, in DES exhaustive key search using bitslice techniques, one can increment the current key in a fraction of the time than is usually needed for key scheduling.
  
  The AES finalist Serpent is designed to be implemented using bitslice operations only. This makes it particularly efficient on modern architectures with many registers.
  
  

• The AES,
  Rijndael, the design of two Belgian cryptographers, Joan Daemen and Vincent Rijmen.
  
  Rijndael follows the tradition of square ciphers (it is based on ideas similar to the Square cipher). NIST gave as its reasons for selecting Rijndael that it performs very well in hardware and software across a wide range of environments in all possible modes. It has excellent key setup time and has low memory requirements, in addition its operations are easy to defend against power and timing attacks.
  
  NIST stated that all five finalists had adequate security and that there was nothing wrong with the other four ciphers. After all analysis and received comments were considered, NIST considered Rijndael the best choice for the AES. The other four finalists are mentioned below.
  
  
• MARS by Zunic et. al., IBM.
  
  This is an interesting new design (using a special type of a Feistel network), which depends heavily on the instruction sets available on modern 32-bit processors. This has the benefit that on these target machines it is efficient, but it may lead to implementation difficulties in cheaper architectures like smart cards.
  
  
• RC6 by Rivest, Robshaw and Yin, RSA Laboratories.
  
  RC6 follows the ideas of RC5 - but with many improvements. For example, it attempts to avoid some of the differential attacks against RC5's data dependent rotations. However, there are some attacks that get quite far, and it is unclear whether RC6 is well enough analyzed yet.
  
  
  
• Serpent by Anderson, Biham and Knudsen.
  
  Serpent has a basically conservative but in many ways innovative design. It may be implemented by bitslice (or vector) gate logic throughout. This makes it rather complicated to implement from scratch, and writing it in a non-bitslice way involves an efficiency penalty.
  
  The 32 rounds lead to probably the highest security margin on all AES candidates, while it is still fast enough for all purposes.
  
  
  
• Twofish by Schneier et. al., Counterpane Security.
  
  Twofish is a new block cipher designed by Counterpane (whose CEO is Bruce Schneier). The design is highly delicate, with many alternative ways of implementation. It is cryptanalysed in much detail, by the very authoritative "extended Twofish team". It is basically a Feistel cipher, but utilizes many different ideas.
  
  This cipher has key dependent S-boxes like Blowfish (another cipher by Bruce Schneier).
  
  

Modes Of Operation

• CBC (cipher block chaining): a ciphertext block is obtained by first XORing the plaintext block with the previous ciphertext block, and encrypting the resulting value. This way leading blocks influence all trailing blocks, which increases the number of plaintext bits one ciphertext bit depends on, but also leads to synchronization problems if one block is lost.
  
  
• CFB (cipher feedback): the kth ciphertext block is obtained by encrypting the (k-1)th ciphertext block and XORing the result onto the plaintext. Interestingly, an CFB feedback loop can also be used as a pseudo-random number generator if one simply feeds one block of true random data with trailing blocks of zeroes into the encryption routine (although the expected period of this PRNG would be only about 2^n/2 where n is the block size of the cipher).
  
  

• Stream ciphers. A stream cipher consists of a state machine that outputs at each state transition one bit of information. This stream of output bits is commonly called the running key. The encryption can be implemented by just exclusively-oring the running key to the plaintext message.
  
  The state machine is nothing more than a pseudo-random number generator. For example, we can build one from a block cipher by encrypting repeatedly its own output. Typically, more elaborate constructions are used for stream ciphers to obtain high-speed.
  
  Some of the more well-known stream ciphers are RC4 and SEAL. Several stream ciphers are based on linear-feedback shift registers (LFSR), such as A5/1 used in GSM. These have the benefit of being very fast (several times faster than usual block ciphers).
  
  
• SSSC (self-synchronizing stream ciphers): The class of self-synchronizing stream ciphers has the convenient property that it corrects the output stream after bit flips or even dropped bits after a short time (say, a few hundred bits).
  
  SSSC's can be constructed using block ciphers in a CFB-related way. Assume that we have already encrypted n bits of the message and know that much of the ciphertext (where n denotes the block length of the cipher). Then we produce a new running key (see above) bit by encrypting the n ciphertext bits. Take one bit of the output of the cipher to be the new running key bit. Now moving one bit further we can iterate this procedure for the whole length of the message.
  
  It is easy to see that a one bit error in a ciphertext cannot affect the decrypted plaintext after n bits. This makes the cipher self-synchronizing.
  
  The block cipher used should have sufficiently large block size to avoid substitution attacks, for example.
  
  

Cryptography before the 1970's

• Fish was used by the German army in WWII to encipher high-command communications. It was produced by a stream cipher called the Lorentz machine. Fish was the name given to it by British cryptanalysts. It was important because it caused difficulties for British analysts, who finally developed a machine called Colossus, which was arguably the first, or one of the first, digital computers.
  
  The Colossus machine may have been an important factor in the planning and success of the Allied attack on Normandy. Given the intelligence produced by cryptanalysis of Fish, Allied forces knew the positions of pretty much every German division.
  
  
  
• Enigma was another cipher used by the Germans in World War II. The machine used several rotors and looked like a typing machine. However, first Polish and then later British mathematicians were able to keep up with the development of the machine. Most communication using the basic version of Enigma was deciphered by British analysts at Bletchley Park within few hours of the interception. One of the strongest Enigma's were used in submarine communication, but British analysts managed to break them with great implications for the battle on the Atlantic.
  
  There are several good books about Enigma and Bletchley Park. In addition, the work of the major figure of British cryptanalysis, Alan Turing, has been explained in many articles and books. Recently his original notes about cryptanalysis from that time has been released for the public.
  
  This cipher, or a variant of it, is used by the unix crypt(1) program. It is unlikely that any variant of Enigma could be considered very secure by todays standards.
  
  
• Vernam cipher is described in detail above.
  
  
• Substitution cipher. This is one of the basic pencil-and-paper methods. Make a table by first listing your alphabet in order on the first row, and then making a random permutation of the alphabet on the second row. You can then encrypt any character of the alphabet by first looking it up on the first row, and the writing down the random character on the second row. The key of this method is the permutation of the alphabet on the second row. Decryption works in reverse.
  
  This method is suspectible to frequency analysis, as long as the alphabet size is small. Modern block ciphers can be seen as a variant of this idea, in the sense that they try hide the message under a very large alphabet that depends on the key. In the block cipher case the permutation is generated by the secret key and the key space might not cover all the possible permutations.
  
  
• Vigenere. This cipher uses clock arithmetic to add together the key and the message. The difference between OTP and Vigenere is that in Vigenere we explicitly reuse the short key several times for one message.
  
  Methods for attacking Vigenere ciphers are the Kasiski test, index of coincidence etc. These lead to effective methods which break even very short message (relative to the key size of course).
  
  
• Hill cipher. The Hill cipher uses matrices in clock arithmetic, and is highly suspectible to known plaintext attacks.