Finding trails

Previously, we went over what a differential trail is, and how they're made. Now we will go over how to find and exploit them. This is going to be a more coding-heavy section, and mostly involves automating the tiresome process of before. There's no harm in skipping this section, though it can be quite useful to know.

Matsui's algorithm

For a while, Matsui's branch-and-bound trail search algorithm was favored and continuously refined by the cryptographic community. At present, the method has been largely supplanted by more powerful ones, so we include this section out of historical interest. However, it's still a fundamental and is simple enough to offer insight into how to find good trails quick.

The idea is rooted in what we discussed earlier regarding differential uniformity and branch numbers. Suppose we have a differential that holds with probability $p$ over $r$ rounds and we're interested in finding a better one. For simplicity, we'll assume a fixed starting difference as well. What we can do is as follows:

• We branch. For every active S-Box, we iterate over possible output differences based on our input difference. We then propagate these differences via the linear layer.
• We bound. The differences are assumed to propagate ideally through the rest of the cipher (based on our differential uniformity and branch number). This is then compared to our current best result. If it's worse, we prune this difference.
• If a trail reaches the end without being pruned, it's saved as a good trail

What's interesting is that Matsui's algorithm can be considered exhaustive, making it great for smaller ciphers. It can also be used to e.g. estimate a branch number for a larger number of consecutive rounds.

Task Using Matsui's algorithm, find the best differential trail for 3-round PRESENT.

Task Using a modified version of Matsui's algorithm, find the branch number for three consecutive rounds of PRESENT.

Automated searching

As mentioned prior, Matsui's algorithm is no longer the state-of-the-art. More processing power and algorithmic improvements have made more generic optimisational problem-solvers the future.

MILP (Mixed Integer Linear Programming) is a powerful method that can be used for automating the search for differential trails in block ciphers. Instead of manually exploring the trail space (as in Matsui’s branch-and-bound algorithm), MILP models the cipher's behavior as a set of linear constraints and uses an optimisational solver to find trails of maximised probability.

For this section, we use PuLP, a Python library that abstracts MILP modeling. It supports many popular MILP solvers like CBC, Gurobi, and CPLEX.

S-Box modelling

As mentioned, MILP solves optimisational problems expressed as linear systems. In our case, we want to maximally increase the probability that a differential holds, which means maximising the weight of a differential trail. Because we're dealing with only linear systems, we do have to get clever with how we model these things.

There is an assumed familiarity with Mixed Integer Programming here. In case this is new to you, head over to the optional section Intro to MILP where we first go over a simpler example and explain the basics of how MILP works.

That out of the way, let's start with just one round. For ease, we'll represent the input and output as 64 binary variables.

import pulp

model = pulp.LpProblem("PRESENT", pulp.LpMaximize)
x = [pulp.LpVariable(f"x{i}", cat='Binary') for i in range(64)]
y = [pulp.LpVariable(f"y{i}", cat='Binary') for i in range(64)]

Now we model the S-Boxes. We will need to reuse the values from our DDT from earlier so that we can account for the differentials.

selectors_per_sbox = []
for sbox in range(16):
	selectors = []
	for in_diff in range(16):
		for out_diff in range(16):
			weight = DDT[in_diff][out_diff]
			if weight == 0: # Ignore impossible differentials
				continue
			sel = pulp.LpVariable(f"sel{sbox}_{in_diff}_{out_diff}", cat='Binary')
			selectors.append((sel, in_diff, out_diff, weight))
	selectors_per_sbox.append(selectors)

The selectors are binary values just as well. A one indicates that the differential is active. We don't necessarily want to minimise the amount of active bits or differentials, but we do want there to be at least one (and, if counting the trivial differential, exactly one for each S-Box). We also don't want our differentials to be invalid — a differential should only be considered if the input bits permit it. So we now fix that.

total_weight = []

def nibble_extr(bits):
    return sum(bits[i] * (1 << (3-i)) for i in range(4))

for sbox in range(16):
	selectors = selectors_per_sbox[sbox]
	in_bits = x[sbox*4:(sbox+1)*4]
    out_bits = y[sbox*4:(sbox+1)*4]
    dx = nibble_extr(in_bits)
    dy = nibble_extr(out_bits)
	
	# Exactly one differential per S-Box
	model += pulp.lpSum(sel for sel, _, _, _ in selectors) == 1
	# The input bits the differential wants must match the actual input bits  
	model += dx == pulp.lpSum(sel * diff_in for sel, diff_in, _, _ in selectors)
	# Likewise for the output bits
	model += dy == pulp.lpSum(sel * diff_out for sel, _, diff_out, _ in selectors)
	# We keep a track of our active weights, i.e. probabilities
	total_weight += [sel * w for sel, _, _, w in selectors]

All that's left now is to model the permutation, add our function, and see where our best differentials ended up.

y_perm = [pulp.LpVariable(f"y{i}_perm", cat="Binary") for i in range(64)]
for i in range(64):
    model += y_perm[PBOX[i]] == y[i]

model += pulp.lpSum(total_weight)
model.solve()

We've got a single round of PRESENT modelled now. This is actually quite useful on its own. Were we to ever get "stuck" with a differential, we could extend it by one round by just fixing some of the input variables. Expanding the above to work for more rounds isn't as hard, though it will involve more variables. As the number of variables, and inherently the number of equalities, increase, so does the complexity of solving.

Task The above code can be said to "work", but only by technicality: it outputs the trivial differential as the best one. Add a constraint such that the trivial differential isn't always the best one. This can also be done by excluding it as a selectable differential, but then you'll have to change the constraint forcing every S-Box to be active.

More rounds

Now it's on you. One round is good, but we can do better than that. This is done best by adding more variables, and mapping old ones to new ones after each round.

Task Expand the above code to analyse four rounds of PRESENT.