Feistel Function

---

A Feistel cipher is a general cipher design principle, not a specific cipher.

• aka Feistel network or Feistel cipher
• forms the basis for many block ciphers
• invented by Horst Feistel
  • designed block ciphers for the US Air Force and IBM
• any block cipher that is based on Feistel works in essentially the same manner
  • differences occur in the round function
  • round function means a function performed with each iteration (round)
  • details of round function can vary with different implementations
  • usually simple functions to maintain efficiency
• uses S-boxes and P-boxes
  • S-boxes perform substitutions
    • notional substitution is an S-box that does a table lookup
  • P-boxes perform permutations

How It Works

Simple

• starts by splitting the block of plaintext data (often 64-bits) into two parts ( and )
  • usually split equally
• round function is applied to one of the halves
• output of each function and the remaining half of the data are run through the exclusive OR (XOR) function
  • i.e., then the result with
  • Binary Operations
• then the halves are transposed
  • i.e., positions switched
  • repeated a given number of times

Detailed

•  plaintext block is split into left and right halves ( and )
• for each round , new left and right halves are computed according to the rules:
  • • new left half is the old right half
  • • where is the subkey for round
    • subkey is derived from key according to a specified key schedule algorithm
    • new right half is the old left half XORed with a function of the old right half and the subkey
  • ciphertext block is the output of the final round
• Can decrypt regardless of the specific round function
  • with XOR we can run the process backwards
  • for , we compute:
• Final result of decryption process is plaintext
• any round function will work in a Feistel cipher, provided the output of produces the correct number of bits
  • no requirement that itself be reversible
  • but not all possible will be secure
    • the security boils down to the round function and the key schedule
      • key schedule is usually not a major issue

Drawback

• half the bits are unaffected each round
• can be viewed as a source of inefficiency
  • as a result, many recent block ciphers are not Feistel ciphers
    • e.g. AES