Cryptology Part II. Bitblock Ciphers

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Contents

1. Composition of ciphers
2. Bitblock ciphers, Feistel, and SP networks
3. Modes of operation of block ciphers
4. DES
5. Cryptanalysis of bitblock ciphers
6. AES

1. Finite fields [PDF]
2. Polynomials and polynomial functions [PDF]
3. Boolean functions, Boolean maps, and Boolean circuits [PDF] (a gentle introduction for beginners with SageMath code)
4. Fourier analysis of Boolean maps
5. The hypergeometric distribution [PDF]

The complete Part II as PDF file.

Overview

For the encryption of computer data we need algorithms that operate on bitblocks, are fast—and thereby suited for large data sets and high transfer speeds—, and optimally resist sophisticated cryptanalysts. Therefore as subjects of Part II of these cryptology lecture notes we treat:

• Construction principles for bitblock ciphers
  • product ciphers, SP networks, Feistel networks, nonlinearity
• Example ciphers of special relevance
  • Lucifer, DES, AES
• The most important cryptanalytic approaches
  • algebraic, linear, and differential cryptanalysis

The mathematical appendix C gives a gentle introduction to Boolean functions and Boolean maps for beginners that might not feel comfortable with the algebraic treatment of Boolean algebra.

The mathematical appendix D under the title »Fourier Analysis of Boolean Maps« focusses on nonlinearity: How to recognize, measure, and prevent unwanted linearity in encryption functions or in their building blocks.

Our goals are:

1. Describe the general mathematical framework for defining encryption functions on bitblocks, that is on vectors in a vector space F₂^l over the two element field F₂.
2. Develop some criteria that help in assessing the strength of encryption functions.
3. Show that bitblock ciphers have interesting mathematical aspects, contrary to the belief that these ciphers only involve boring fiddling with bits—a belief that is quite common among mathematicians.

Introduction

In classical cryptography the weakness of simple monoalphabetic substitutions is remedied in two different ways: first by polygraphic substitutions that encrypt groups of letters at once, second by polyalphabetic substitutions that change the substitution alphabet depending on the position in the plaintext.

If we consider bits instead of letters, monoalphabetic substitutions are cryptographically useless since we have only two choices: either leave all bits unchanged or invert all bits. Thus the plaintext either remains unchanged, or changes in a trivial way. However the two principles of hardening monoalphabetic substitutions yield two classes of useful encryption methods for binary encoded informations:

• Bitblock ciphers split bitstrings into blocks of a fixed length and encrypt one complete block per step.
• Bitstream ciphers encrypt bit by bit, each one by another substitution (so each single bit is unchanged or flipped by a position-dependent rule).

No mathematically complete proof exists for the security of any bitblock or bitstream cipher. Thus the situation is even worse than for asymmetric ciphers where the proof of security often reduces to a well-studied, if not solved, mathematical problem. The best we can do is to consider a symmetric cipher secure if none of the known attacks is significantly faster than a complete exhaustion of the key space (also known as »brute force attack«).