What are recommended, general strategies to start block-cipher design and/or analysis?

Question

I (and many others for that matter) have always been fascinated by the inner workings of the modern building block of cryptography: block ciphers.

Now, the resources on the "black art" of design and analysis of these ciphers are sparse; especially for the entry level. Available information like the Schneier guide seems to be somewhat outdated (due to its age).

What's the general consensus of the “best” (read: recommended) strategy to start designing and/or analyzing modern cryptographical block ciphers?

---

_{Nota bene: Think of this as a general, wiki-alike question – for learning purposes only. (Besides that, this Q&A would represent a place we can point people to when alike algorithm design questions arise.)}

Answer 1

In order to design and analyze a cipher, we have to establish what a cipher is supposed to accomplish. Put simply, we would like to be able to transform information in such a way that only those who are authorized may perform or invert the transformation. We can refer to this transformation as "encryption". Unauthorized parties may exist that should not be able to obtain any information protected by the encryption method, despite the fact that they can/will try to do so, if given the opportunity. This applies even if the work that would be involved is a large, nontrivial amount. We can refer to unauthorized parties as adversaries.

Ideally, we would like the mutual information required by the authorized parties to be minimal, and for it to be obtainable with some level of convenience. If it were not for these two extremely practical aspects, the One Time Pad would be literally unbeatable, with information-theoretic security, implementation simplicity, and maximum efficiency (just a single addition per character!). A OTP is not a block cipher, but it makes for a good reference point to measure against.

Unfortunately, one time pads require the key material be as long as the information to be enciphered, and prepared ahead of time by the authorized parties. This violates our two practical desires listed above, so we must design other algorithms that can re-use a much smaller key.

One temptation is to keep the encryption algorithm itself secret. Unfortunately, keeping an algorithm secret implies that all users of the algorithm know the secret to encrypting/decrypting. As the number of users that know the secret increases, so does the likelihood that the secret will become compromised by adversaries. This would fail the original design goal, and only does marginally better then the OTP in terms of practicality and the size of the secret to be protected.

This leads to the third, most successful option: Using a publicly known algorithm that concentrates the required secrecy into a key that is used by the algorithm.

Whatever method is used to encrypt, the information may be subject to attack by adversaries. The job of encryption is to resist this attack, and keep the information protected. This means a few things:

• Since modern ciphers use a key to authorize parties to perform the transformation, the goal of an adversary is to obtain the key

  • Obtaining the key implies the ability to encrypt plaintexts and decrypt ciphertexts, violating the original design goal of the cipher

    • Similar to how a lock on a door uses a key
    • You just have to protect the key, not prevent anyone from knowing there is a lock
    • The key is reusable, and has a very long lifespan.
    • The key should be relatively small - 128 to 256 bits is common

  • The key must remain secure even if the adversary:

    • Possesses vast amounts of ciphertext
    • Knows the plaintext contents of a message, and the corresponding ciphertexts for each message
    • Can trick an authorized party into encrypting/decrypting messages for the adversary
      • Choose messages to encrypt or decrypt at will.
      • Can adapt or modify future encryption/decryption queries in response to past queries.

Most of the complexity of a modern cipher comes from the attempt at protecting the key, and by extension, the plaintext. Designing a cipher with a reusable key will require an understanding of the ways that the cipher and key can be attacked. In order to design a cipher, you must learn to think like the adversary, and study how ciphers are broken.

Standard attacks

There are a handful of generic attack methods that any new cipher must protect against: brute force search, differential cryptanalysis, and linear cryptanalysis.

• Brute force search means that the adversary simply guesses all possible combinations of key values, until the correct key is found

  • Has a worst case time complexity of $2^N$, where $N$ is the width of the key in bits
    • time complexity is only accurate if the key is uniformly random
    • 64 bits is considered too low for modern computers
    • 128 bits is considered secure for now
    • 256 bits is considered secure forever, even in the face of futuristic quantum computers

• Differential cryptanalysis exploits the probability that a particular difference ($\Delta_1$) between inputs ($t_1$ and $t_1'$) will be propagate to a particular output difference ($\Delta_2$)

  • By testing all the possible input differences, it is possible to return probabilities to have some output differences. A couple of specific differences $\Delta_1$ and $\Delta_2$ is called a differential and noted ($\Delta_1 \Rightarrow \Delta_2$).
  • The more likely that a given differential ($\Delta \Rightarrow \Delta'$) holds, the more effectively this behavior can be exploited against the cipher
  • A relatively simple tutorial with code can be found here
  • The original paper by Biham and Shamir can be found here

• Linear cryptanalysis exploits the probability of a subsection of bits from a given input is correlated with a subsection of bits in the output of a function

  • A subsection of bits is selected via bitwise masking
  • The exploitable relationship is if the parity of the hamming weight of the subsection of input and output bits is the same
  • The more regularly this relationship occurs, the more effective linear cryptanalysis will be
  • A relatively simple tutorial with code can be found here
  • The original paper by Matsui can be found here

Linear and differential cryptanalysis can provide hints as to what the internal state of the cipher may be, up to a certain point. This can reduce the number of possible values for a part of the key that an adversary will have to guess. These are considered to be two of the most powerful tools in regards to cryptanalysis of a modern cipher.

Block Cipher constructions

There are two main classes of cipher constructions: The Feistel network , and the substitution-permutation network.

The basic design of the Feistel network is to split the message block into two halves, a left and a right. A keyed function with good diffusion and confusion is applied to right half, and the output of this is added to the left half. The halves are then swapped, and the process repeated. Decryption is more or less the same operation performed with the reverse keys, and so this construction is relatively lightweight in terms of implementation complexity. DES is an example of a Feistel network. There are differential and linear attacks against DES.

The design of a substitution permutation network is typically finer grain then a left and right half of a Feistel network. For example, in the Rijndael cipher, also known as Advanced Encryption Standard (AES), the message is operated upon as 16 x 1 byte state, arranged as 4 rows and 4 columns. It consists of 4 main steps: a byte substitution, a row transposition, a mixColumns step, and the addition of key material via XOR.

Many, if not all modern block ciphers, are made of repeatedly iterating the same core function(s), often times with multiple different keys between each application. Often times, these keys are derived from the master key that is actually supplied to the cipher by the user. We refer to keys generated this way as the round keys, and the process of generating them the key schedule.

The way round keys are derived can influence both the security and efficiency of the cipher. Ideally, recovery of any round key information should reveal as little as possible about other rounds keys or the master key. This is one of the strengths of the OTP: recovery of a byte of key material (i.e. via known plaintext attack) provides no assistance in the recovery of any other bytes of the key. It is also generally considered beneficial for the generation of round key material to be quick, as a cipher with a slow key schedule may have greater latency and/or lower throughput.

Designing a round function

In order to know what to operations to use, we need to know what we need to accomplish:

• Diffusion

  • Flipping one input bit anywhere should flip (about) half the output bits on average
  • Bytewise shifts, rotations, and transpositions can help spread the influence of a given subsection of bits
  • Bitwise transpositions can be used too, but can be relatively slow in software (but potentially fast in hardware)

• Confusion/Non-linearity

  • The relationship between the key and ciphertext should be complex
  • A linear cipher can be broken by gaussian elimination
  • Mixing arithmetic in different fields can provide non-linearity (i.e. xor and addition modulo 256)
  • Boolean functions can provide non-linearity

• Invertible only with the correct key

  • The cipher will only provide confidentiality if secret (key) material is introduced at some point.
    • Applying a key on the input before applying any rounds and after applying all rounds is called key whitening and is common
    • Additionally, a key is added every N rounds, where N is often 1 (i.e. after every round)
    • Key addition is often times done via xor and addition modulo (2**wordsize_in_bits), or both
  • There should be no "weak keys"

So our goals are to combine the message with a key, and flip lots of bits in a diffusing and non-linear fashion. Ideally, we would like the composition of our operations to produce output similar to that of a random permutation.

Some available instructions are:

• Xor

  • Useful for combining two inputs (i.e. message and key)
  • Is its own inverse (an involution)
    • No subtraction instruction required to invert
  • Bit sliced
  • Needs addition/boolean function/s-box lookup for non-linearity

• Addition

  • Useful for combining two inputs
  • Requires separate subtraction instruction to invert
  • Tends to flip low order bits more then high order bits

• Lookup tables

  • Useful for good differential/linear properties
  • Effectively equivalent to the cached inputs/outputs of a non-linear function
  • Can be vulnerable to timing attacks on machines that utilize a cache

• Boolean functions

  • Useful for non-linearity
  • Some examples are the Choice and Majority functions
    • Choice
      • Logically, If C then B, else A
      • c ^ (a & (b ^ c)) (for mathematicans: $c\oplus(a\wedge(b\oplus c))$ )
      • Bit sliced operation
    • Majority
      • (a & b) | (a & c) | (b & c) (for mathematicans: $(a\wedge b)\vee(a\wedge c)\vee(b\wedge c)$ )

• Rotations/Shifts

  • Useful for diffusion and carrying/spreading differences through a word
  • Generally done by fixed amounts, but not necessarily

• Transposition

  • Shuffling the order of state words can help provide diffusion
  • Transposing bytes according to secret data can be vulnerable to timing attacks (secret dependent memory access is the concern)
  • Includes rotations

• Composed bitwise and bytewise transposition:

  • Acts like a shuffle (permutation) of the input bits
  • Only modifies a given bits position, not its value (Does not modify hamming weight)
  • Is a linear transformation
  • Example: The Keccak permutation, specifically the Rho and Pi steps
  • Can provide "weak alignment"

• Pseudo-Hadamard transform:

  • Provides diffusion
  • Used by SAFER and Twofish

Some example combinations of the above operations:

• Rijndael consists of addRoundKey, mixColumns, shiftRows, subBytes on the message:
  • subBytes is a lookup table (good differential/linear properties)
  • shiftRows is a bytewise transposition
  • mixColumns is a linear transformation that, in conjunction with shiftRows, provides diffusion
  • addRoundKey xors the key with the state
• DES round function consists of an expansion permutation, key mixing, s-box application, and bit permutation
  • Expansion compensates the S-boxes going from 6 to 4 bits.
  • Keys are applied every round via xor
  • S-boxes provide resistance against differential cryptanalysis
  • Bit permutation provides diffusion
• Serpent round function consists of key-mixing XOR, a 4×4 S-box, and a linear transformation
  • Keys are applied every round via xor
  • S-boxes are applied in parallel (bit sliced design)
  • Linear mixing provides diffusion
• TEA uses only addition, shift, and XOR:
  • xor/addition create nonlinearity and apply key material
  • shifts/additions provide diffusion

As we can see from some examples, there appear to be at least two different approaches:

• S-box based designs

  • Can offer very good linear/differential properties with good performance
  • Can be hard to find good large s-boxes because of the huge search space
  • Tend to be used in conjunction with a linear mixing layer for diffusion
  • Rijndael strategy:
    • Use an s-box with the optimal worst case differential/linear properties
    • Use a mixing layer that aims at increase the lower bound of the rate of diffusion
    • Notice how it's designed around the worst case scenario
  • Can provide clear proofs of resistance to differential/linear attack

• ARX based designs (addition, rotation, xor)

  • Are inherently less conducive to timing based side channel attacks then s-box based constructions
    • Addition, XOR and rotation by fixed amount are often times implemented in constant time
  • Fast performance on PCs (especially if you can avoid memory accesses/stick to the registers)
  • Compact/simple implementation (does not require the space that lookup tables need)
  • Not as straightforward to analyze security to differential/linear attack compared to s-box based design

Many ciphers use a set of constants. Every round, a new constant is introduced to the state via addition/xor. This can help against slide attacks by making successive rounds different.

Breaking a round function

Before you resort to applying linear and/or differential cryptanalysis to any new design, considering running some statistical tests. Statistical tests can tell you very quickly whether your latest design is totally broken. Note that statistical tests cannot confirm whether a design is cryptographically secure, it can only confirm that a design is insecure.

Some example tests might be:

• Avalanche test
  • Generate blocks of random data with a given key (i.e. encrypt an incrementing counter) and measure the hamming distance between successive outputs (measures diffusion of data)
  • Encrypt the same series of successive values with a different key, and measure the hamming distance between the previous set of random data and the new set (measures diffusion of key)
• Randomness test
  • Generate a sizeable (>1MB) amount of psuedorandom data with the cipher (i.e. by encrypting an incrementing counter)
  • Pass the data to a tool such as ent, dieharder, or the NIST test suite

Run the mentioned tests on both your design and on os.urandom: ideally the two results should be indistinguishable.

When devising an attack, try attacking a reduced (single?) round version of the cipher first. Look for the weakest points in the design. Try practising against FEAL, it has a major weak point and is useful for learning differential/linear cryptanalysis, and slide attacks. Some of the attacks against DES would probably be helpful ways to learn about linear cryptanalysis and brute force search

Once you've got a handle on those, there are actually many different attacks besides generic linear/differential cryptanalysis You may find some software related to cryptanalysis here

Math and visualization

If you find visualizations and diagrams helpful, this page may be interesting to you. If you do not know math well, try learning some of the notation. Much of the information you want to understand will be in scientific research papers and written in the language of math.

Some of the subjects that will prove useful when reading papers and in cryptanalysis/cipher design are:

• Basic Set theory
• Basic Probability theory
• Basic linear algebra
• Boolean logic
• Finite fields

Answer 2

There is no such thing as a clearly defined, unambiguous, optimal learning path. However, drawing from my own experience, I would suggest tackling the following in due sequence:

• Linear cryptanalysis: start with Matsui's article, implement your own DES, and try it out on a reduced version (e.g. 8 rounds instead of the full 16). You might also want to have a look at this report from Pascal Junod.

• Differential cryptanalysis: it is explained at length in this book (made freely available in PDF form by Biham). Actually this is also a good source on the DES algorithm itself, so you will want to use it for making your implementation of linear cryptanalysis as well. There again, implement differential cryptanalysis on a reduced DES.

• Read up on Boomerang attacks and related attacks (amplified boomerang, rectangle...). These can be viewed as extended variants upon differential attacks, whose main pedagogical benefit is to illustrate many ways in which attackers "cheat".

• Also make some investigations on Vaudenay's decorrelation theory to get a feeling of how attacks can be theorised up in a formal context.

• Then it is time to tackle with the AES competition. All the previous steps were really meant to give you enough background information on terminology, and, perhaps more importantly, train you into reading research articles, so that you could read all the contributions that showed up during that competition.

In general, I have a "hands on" approach, meaning that I try things out by implementing them. I find that, in my case, this helps a lot for understanding. But ultimately, the key to analysing block ciphers is to have an extensive knowledge of all kinds of designs and attacks that have been accumulated over the years, and this comes only through reading a lot of research articles.

Having implementation experience is also a requirement for handling the currently hot topic in block ciphers, which is side-channel attacks. In particular, timing attacks based on cache behaviour have been demonstrated (in lab conditions, not "in the wild") for many classical AES implementations, and there has been a lot of efforts at designing implementation techniques that prevent such attacks.

Answer 3

This is a complementary answer to the others, focusing on theory as well:

Step 1

The Heys' "Tutorial on linear and differential cryptanalysis" available here which uses 4 rounds of an SPN network with 16 bit block length and four 4x4 Sboxes is a very nice introduction to cryptanalysis where it is possible to simulate attacks in say, maple, magma, Mathematica with minimal computational effort.

This comes with some interesting twists:

1. Since the cipher would be ridiculously weak with a key scheduling algorithm, it is loaded with randomly generated keys, including a whitening key, resulting in 60 key bits. Still, it can be broken in a reasonable time by the approach described in the tutorial via either linear or differential cryptanalysis. One is able to demonstrate that the subkey patterns with the highest bias (linear cryptanalysis) or highest probability (differential cryptanalysis) turn out to be the correct subkey values when enough plaintext/ciphertext pairs are tested.

2. The cipher also has a small blocklength and could be used to demonstrate brute force attacks such as (a) building a codebook or (b) brute force key search; which would be a second way of double checking the results of the cryptanalysis from 1. Note that the second case is easier to perform since it takes constant memory. Both cases take time of the order $2^{16}=2^b=2^k$ since blocklength $b$ and keylength $k$ are both equal to 16.

Step 2:

You can now move on to more algebraic approaches to Sbox design via Boolean functions and properties such as nonlinearity, correlation immunity, resilience and their vectorial boolean counterparts. There are a few books/documents that do a good job of treating this subject, including:

1. Carlet's chapter on boolean functions
2. Carlet's chapter on vectorial boolean functions
3. Cusick and Stanica's book on boolean functions and applications to cryptography (Chapters 1-3 and 7 are particularly relevant to this question)