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.
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:
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:
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:
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: