14. September 2012: Lecture #3: Symmetric ciphers (2/2): Block ciphers

Reading this week

• Trappe chapter 4 and 5
  
• Menezes chapter 7
  

---

A block cipher transforms a plain text message by dividing it into blocks, typically a fixed size of 64 or 128 bit, and transforming it to another reversible block. There is no memory outside the block. Block ciphers are often used as a building block to generate stream ciphers, for message authentication codes (MAC), hash functions or in a signature scheme. The key is typically short (128-256 bit)

From lecture 1 we learned about the transposition ciphers. This cipher is actually a block cipher with the swap (permutation) as the key, and generally one could say block ciphers are complex permutations.

A block cipher is a vectorial Boolean function and the function has to be bijection meaning it has a one-to-one mapping in the domain and codomain. This guarantees there is a reverse function for decipherment. Practical requirements would be that the function is quick to compute, but at the same time be resistant to analysis of the key even in a "known plain text" and "chosen plain text" setting.

Number of possible block ciphers given an n-bit block grows much faster than the number of possible keys for a k-bit key. The number of keys will limit "how many of the block ciphers" are available for usage in that particular cipher.
The reason for faculty growth is that every combination of the possible values for the block can be combined with all the other possible values as long as it is reversible.

Notation used for representing a permutation given the selected key. Note subtraction of one since we count binary from zero

Perfect (provable) security requires a new random not repeated key for every (key-length divided by block length) block, but this is impractical. The normal case would that the number of blocks with the same keys are much greater than this.

Important principles

Confusion Every bit in the key should affect/impact as many bits as possible of the output in order to reduce the possibilities of finding what the key is given the cipher text. Make the relationship between key and output at complicated as possible. It requires none linear operations (logic AND) and is often seen as (substitution) S-boxes applied used in many rounds. (Topic for cryptology2)

Diffusion Is a counter measure against redundancy in the plain text (remember the rate of the language). Changing a few plain text bits causes many cipher text bits to change. This is achieved my using linear transformations (permutations) using XOR logic

Key schedule The key is used in many round and each round requires a different key. An algorithm is used to derive the round keys based on the preshared key. The concept of sub-units (rounds) is a trade off between security and implementation complexity (speed)

Examples of ciphers

There are two main types of block ciphers: Feistel and Substitution-Permutation Networks. The SPN's are newer and are easier to analyze with our current technology.

• Feistel (1950s)
  1. DES (used in cash dispensers using 2TDES)
     
  2. LUCIFER (Author Horst Feistel)
     
  3. KASUMI (3G smartphones)
     
  4. MISTYI
     
  5. CAMELLIA
     
  6. FEAL
     
  7. Blowfish
     
  8. Twofish
     

• Substitution-Permutation Networks
  1. Rijndael (AES)
     
  2. IDEA
     
  3. SHARK
     
  4. SQUARE
     
  5. 3-way SAFER
     

Feistel

The main principle of a feistel cipher is that the plain text is divided in two halves. One half is transformed by a permutation function. This result is XOR'ed with the first half. The second half is also directly copied and swapped for each round:

Two feistel ciphers are used for example in this course: DES and KASUMI since they are commonly used.

DES uses a 56 bit key (actually it receives 64 bit but 8 of them are fixed) and is applied on 64 bit blocks during 16 rounds. The block is divided in half (32 bits each), applied a function and XOR'ed with the other half as any other feistel cipher. The function and the key schedule is what differentiates it. DES also has a fixed initial and final permutation before and after the 16 rounds (bits are reordered), and the interchange is omitted the 16th round.

56bit is not enough, and the solution was to triple it with different keys (TDES). There are two modes. {encipher encipher encipher} EEE or {encipher decipher encipher} EDE. The key is not actually efficiently 3x56-bit but closer to 112bit with TDES. With double DES it has the strength of 57 bit because of the "meet in the middle attack". ATM machines uses first and 3rd key equal and has about 80 bit of strength.

KASUMI is the core confidentiality and integrity functionality of the UMTS system. It has a 128 bit key, operates on 64 bit block, has 8 rounds. The difference from DES is a more complicated function. A "feistel inside feistel" design using AND, XOR and OR logic. The first feistel stage of 8 rounds has a FL and FO function. The FO has tree stages of a FI function inside of it. One known problem with this one is that the key schedule is linear. MISTY1 is almost the same but has a none-linear key schedule.

Substitution-Permutation Networks

Rijndael can use block sizes of 128-256 bit (in 32 bit increments), but the AES (Advances Encryption Standard - 2001 - replacing DES) chose the 128 bit block size version (key can still be 128, 192 and 256 bit using 10, 12 and 14 rounds respectively). One interesting thing with this cipher is that the first round key IS the actual key, which is unusual.

Rijndael polynomial

Rijndael/AES has 4 separate steps: ByteSub, ShiftRows, MixColumn and AddRoundKey (with their inverse steps for encipherment)

• ByteSub is a none linear s-box for avoiding differential analyzing (add confusion)
  
• Shift rows is a linear mixing/diffusion in GF(2) (field mod polynomial)
  
• MixColumn is shifting rows
  
• AddRoundKey is XOR with round key
  

Check out cs.bc.edu for å great presentation on how it it works

One problem with AES is that the S-box chosen is the simplest one possible to generate. Possible weakens? Different encipher from decipher makes weak keys attack more unlikely, but decipher is slower and encipher.

How to use a block cipher?

Or more precisely, how to use a block cipher when message is longer than the block. One could divide the plain text in blocks, encrypt each block separately and send the concatenated cipher blocks, aka the Electronic Code Book (ECB-mode). This however is a bad idea. Look at this illustration of an image encrypted using this approach:

(source wikipedia)

Other methods

Initial vector A "message key" or a nonce, used to kick start some modes of operation. Does not need to be kept secret, but are sometimes unnecessary for synchronization. Must be random

• Cipher Block Chaining (CBC): Output used as IV for next block. Must send IV. Require padding if size mod block length is not 0. IV register is parallel.
  
• Cipher Feedback mode (CFB - stream cipher): Cipher text in the feedback. Self synchronized (content of shift register (IV) is completely changed), require only encipher implementation, works on smaller sections of the block (1 to block size, 8 is typical).
  
• Output Feedback mode (OFB - stream cipher): Output of cipher is the feedback. Not self synchronizing. Enciphering block size each time.
  
• Counter mode (CTR - stream cipher): No feedback. A counter is used as input for the block cipher and is incremented for each new block. A stream of bits is generated and XOR'ed with the plain text. It can be run in parallel with different numbers of the count. The IV is the initial value of the counter.
  

The security of block ciphers

"Design according to widely accepted rules, have it attacked and improve rules if any attack is successful"

Kinds of security:

• Perfect security (One time pad)
  
• Security against polynomial attacks (Provable security - attacker runs in polynomial time, we need exponential complexity to be secure - P or NP problem)
  
• Practical "security" (known attacks, how long will it take it break it?)
  
• Historical security (no one has found a way to attack it...yet)