Notes.6 DES and conventional modern cryptosystems Pfl. Ch. 3, KPS Ch. 3. Feistel Structure First reported by Horst Feistel of IBM in 1973 Based on some number of rounds of processing, where the input plaintext is the input to the first round and the ciphertext is the last round's output, and the encryption key K is used to generate a round key k_i for each round i. On each round, the input to the round is split into 2 halves of equal length, L_i and R_i. The L_{i+1} = R_i and R_{i+1} = F(R_i,k_i) + L_i, where + is XOR and F() is some difficult to invert round function that depends on R_i and k_i. A nice feature of this structure is that each round computes a different function, as long as the k_i's are different, and any number of rounds may be employed. The beauty of this structure is that, although F is difficult to invert, it is not necessary to do so - to decrypt, L{i+1} is run through F using k_i, then the result is XORed with R_{i+1} to obtain L_i: L_i = F(R_i,k_i) + R_{i+1} = F(L_{i+1},k_i) + R_{i+1}, while R_i = L_{i+1}. The structure lends itself to use of the same hardware or software for encryption as decryption due to its nature, running it with the reverse order of round keys. Enigma Between WWI and WWII, the Germans developed the Enigma device, which allowed automated symmetric encryption using something like a teletype with lights on it - an electromechanical device. When a key was pressed, several things happened. First, an electrical connection was made that sent power through a wire corresponding to the letter on that key which then passed through a number of components that each applied a permutation to the symbol, finally lighting up a light corresponding to the permuted output symbol. Pressing the key also caused some wheels to turn, which changed the permutations used for the next symbol to be encrypted. The structure of the device allowed for some number of rotors to be inserted into the machine. Each rotor was a disk with electrical contacts on each side of it that were connected via a permutation of wires internal to the rotor. On the rim of the disk, each contact had a symbol associated with it, used to set the key (see below). The rotors moved like an odometer when the keys were pressed, so that for a given set of rotors in a given order, the permutation they made would not repeat until they all returned to their original position (with 26 symbols, that is 26^r where r is the number of rotors). In effect, if a given rotor implements a permutation P, and R(i) is the ith rotation permutation (i.e., take n to n+1 modulo N), then the rotors implemented the concatenation of r permutations, each a rotation-permutation-inverse_rotation sequence, in which the rotation and its corresponding inverse rotation changed for one or more rotors for every plaintext character entered. Once the signal travelled across the rotors in one direction, it encountered an exchange permutation reflector, a special disk that just connected pairs of contacts on the same side and did not move. (Note: an exhange permutation is one that is its own inverse, i.e., if p(x) = y, then p(y) = x). The signal was sent back out a different contact and then traversed the rotors in the reverse direction. In addition, there was a "steckerbord," a plug board similar to those used by old timey telephone operators, that allowed an arbitrary permutation to be entered before the signal traversed the rotors and reflector. The key for such a system, given a number of rotors, was the set of rotors to be used (they were interchangeable and units were sent sets of rotors in a box), the order in which the rotors were to be placed in the machine, the reflector to use, the (initial) positions of each of the rotors and the reflector, and the plugboard settings. Enigma is of importance in a number of ways: first, it was cracked by Polish, British and American codebreakers and probably decided the outcome of the war; second, it shows how carefully one must take any claims of "unbreakability" of a cryptosystem; third, electronic computers were developed in secret during WWII expressly to crack intercepted Enigma transmissions. DES DES uses 56-bit keys on 64-bit blocks with a 16-round Feistel structure. It has (useless) initial and final permutations of the bits. The round keys are generated from the 56-bit master key by splitting the master key in half, and rotating each half either one or two bits left (logical shift), then selecting 24 bits from each half. Decryption uses the same keys in reverse order, and with the left and right halves of the 64 bit block reversed. In each round, the right half is first expanded from 32 to 48 bits by considering it as 8 nybbles (4-bit quantities), and copying the 8 nybbles to the center 4 bits of 8 6-bit quantities. The leftmost and rightmost bits of the 6-bit quantities are copied from the bits that flanked the nybble in the original 32-bit input (wrapped around). E.g., the first 6-bit quantity consists of bit 31, bit 0, bit 1, bit 2, bit 3, and bit 4, while the second consists of bit 3, bit 4, bit 5, bit 6, bit 7 and bit 8. This 48-bit quantity is XORed with the round key, then put through the 8 S-boxes. Each S-box takes one of the 6-bit quantities, and using the two end bits as a two-bit selector, applies one of four substitutions to the 4 central bits. A 32-bit quantity results, which is then put through a permutation (the P-boxes) before is XORed with the left half in the Feistel structure. DES Modes ECB - Electronic Code Book - Simply break up M into 64-bit blocks and encrypt each one independently with the key, K. Subject to cut&paste attack. CBC - Cipher Block Chaining - M is again broken up into 64-bit blocks, but each plaintext block is XORed with the preceding ciphertext block before encrypting with K. The first plaintext block is XORed with an initialization vector (IV). Decryption requires that each ciphertext block be decrypted with K, then XORed with the preceding ciphertext block or IV. Transmission error will affect two blocks. Specific bits in one plaintext block may be changed at the expense of garbling the preceding block by an attacker. OFB - Output Feedback Here, DES is used as a PRNG. An IV is encrypted using K, then the leftmost k bits of the output are used as a stream key. These k bits are then shifted into the right end of the IV (tossing out the k leftmost bits of the IV), and this new quantity is encrypted to produce the next stream key. The stream keys are XORed with the plaintext symbols to produce the ciphertext. Decryption simply generates the same stream keys and XORs them with the ciphertext. Q: Why not use the rightmost k bits, so that an attacker will not have the input to DES even if some plaintext and ciphertext are known? Converts DES to a stream cipher (specifically, a Vernam cipher). Key stream can be generated ahead of time for more speedy processing. CFB - Cipher Feedback Like OFB, except that the ciphertext symbol is shifted into the previous DES input to produce the next stream key. This means that the keys cannot be computed ahead of time, but like CBC, improves diffusion greatly.