Differential Cryptanalysis of a Multi-Round SPN
Part three of the differential cryptanalysis series
May 11, 2023
The design of block ciphers is usually seen as a specialist topic. Consequently, knowledge is mostly preserved in academic papers and there are only few introductory tutorials. We aim to fill this gap between the IT security practitioner and the block cipher designer. In this blog series we introduce differential cryptanalysis with a hands-on approach. Our target group are IT security practitioners and programmers without a deep knowledge of math.
The following list shows the topics of all scheduled blog posts. It will be updated with the corresponding links once new posts are being released.
- Part1:DesignofModernSymmetricCiphers
- Part2:DifferentialCryptanalysisofaSingle-RoundSPN
- Part3:DifferentialCryptanalysisofaMulti-RoundSPN
Introduction
In the lastpostofthisseries we discussed a single round SPN and how to perform differential attacks on it. In this post, we introduce a multi-round SPN toy cipher and extend the differential cryptanalysis to recover the key in such a multi-round setting. Again, Python code is provided so the reader can follow along.
Our Toy Cipher
This section introduces our novel toy block cipher.
The block sizes of the plaintext and ciphertext are 9 bits. We will group the bits in triplets in our notation. The size of the S-box is 3 bits. There is only one S-box, and this S-box is used multiple times.
The length of the key is 27 bits. The round keys are simply the different parts of the key. I.e., the key consists of three round keys with 9 bits each. In a more modern design, a separate complex key schedule would be used. But this is not the main focus of our work, and thus we omitted it in our design.
The full design is shown in the schematic below.
Our toy design follows a classical SPN, where as usual the last permutation is omitted, as it does not increase security.
In the following code the S-box is defined. The values of the S-box have been chosen randomly. Additionally, we define the inverse of the S-box, as it is needed for decryption.
import random
s = [3, 6, 4, 5, 1, 7, 2, 0]
s_rev = [s.index(0),
s.index(1),
s.index(2),
s.index(3),
s.index(4),
s.index(5),
s.index(6),
s.index(7)]
# not the bit length of the sbox, but its range of possible input values
SBOX_RANGE = len(s)
def sbox(x):
return s[x]
def inv_sbox(x):
return s_rev[x]Next, the permutation used in our design is defined. In this code we select a single bit of the input using the and operation with a shifted one bit. Then the input bit is shifted according to the permutation table. Finally, the shifted bits are collected in the output value.
p = [0, 3, 6, 1, 4, 7, 2, 5, 8]
def pbox(x):
y = 0
for i in range(len(p)):
if (x & (1 << i)) != 0:
y = y ^ (1 << p[i])
return yAs our design uses three S-boxes in parallel, functions are needed to demultiplex the 9 bit blocks into three blocks of 3 bits each. Additionally, multiplexing is necessary to reverse the demultiplexing.
def demux(x):
"""
Takes 9 Bit value to three 3 Bit values.
demux(1) = [1,0,0]
demux(8) = [0,1,0]
"""
y = []
for i in range(3):
y.append((x >> (i * 3)) & 0x7)
return y
def mux(x):
"""
Takes three 3 Bit values to a 9 Bit value.
The inverse of demux.
mux(demux(13)) = 13
"""
y = 0
for i in range(3):
y = y ^ (x[i] << (i * 3))
return yNext, the key schedule is programmed. The main key is simply split into three round keys of same size. This is very similar to the demultiplexing from above, but with different sizes.
def round_keys(key):
"""
Derives the list of round keys from the main key.
Note: rounds are enumerated starting with zero.
"""
y = []
for i in range(3):
y.append((key >> (i * 9)) & 0x1ff)
return yHaving all the ingredients together, the full algorithms for encryption and decryption can be programmed.
def round_function(input, round_key):
return mux([sbox(k ^ p) for k, p in zip(demux(round_key), demux(input))])
def encrypt(input, key):
if key > 2**27-1:
raise Exception("Key too long")
if input > 511:
raise Exception("Plaintext block too long")
roundkeys = round_keys(key)
output = round_function(input, roundkeys[0])
output = pbox(output)
output = round_function(output, roundkeys[1])
output = mux([(k ^ p) for k, p in zip(demux(roundkeys[2]), demux(output))])
# the last line is similar to
# output = output ^ roundkeys[2]
# but we avoid endianness errors
return output
def decrypt(input, key):
if key > 2**27-1:
raise Exception("Key too long")
if input > 511:
raise Exception("Plaintext block too long")
roundkeys = round_keys(key)
output = mux([(k ^ p) for k, p in zip(demux(roundkeys[2]), demux(input))])
output = mux([inv_sbox(x) for x in demux(output)])
output = mux([(k ^ p) for k, p in zip(demux(roundkeys[1]), demux(output))])
output = pbox(output) # in our case pbox = inv_pbox
output = mux([inv_sbox(x) for x in demux(output)])
output = mux([(k ^ p) for k, p in zip(demux(roundkeys[0]), demux(output))])
return outputDifferential Attack
As with differential attacks on a single round cipher, a first step in attacking ciphers with multiple rounds is to compute the difference distribution table of the S-box. This table shows the number of output differences given a fixed input difference. The necessary procedure is exactly the same as for the previouspostinthisseries .
def get_difference_distribution_table():
print("[*] Computing difference distribution table.")
diff_dist_table = [[0 for x in range(SBOX_RANGE)]
for y in range(SBOX_RANGE)]
for in_diff in range(SBOX_RANGE):
for input0 in range(SBOX_RANGE):
input1 = input0 ^ in_diff
out_diff = sbox(input0) ^ sbox(input1)
diff_dist_table[in_diff][out_diff] = diff_dist_table[in_diff][out_diff] + 1
return diff_dist_table
def matrix_pretty_print(matrix):
# https://stackoverflow.com/questions/13214809/pretty-print-2d-python-list
s = [[str(e) for e in row] for row in matrix]
lens = [max(map(len, col)) for col in zip(*s)]
fmt = ' '.join('{{:{}}}'.format(x) for x in lens)
table = [fmt.format(*row) for row in s]
print('\n'.join(table))
diff_dist_table = get_difference_distribution_table()
matrix_pretty_print(diff_dist_table)For a single S-box the difference distribution table is as follows.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 2 | 2 | 0 | 0 | 2 | 2 | 0 |
| 0 | 0 | 0 | 4 | 0 | 0 | 0 | 4 |
| 0 | 2 | 2 | 0 | 0 | 2 | 2 | 0 |
| 0 | 2 | 2 | 0 | 0 | 2 | 2 | 0 |
| 0 | 0 | 0 | 0 | 4 | 0 | 0 | 4 |
| 0 | 2 | 2 | 0 | 0 | 2 | 2 | 0 |
| 0 | 0 | 0 | 4 | 4 | 0 | 0 | 0 |
As always, an input difference of zero leads to an output difference of zero for 8 out of 8 of the possible inputs. The interesting differentials are again those of high probability. Each entry of 4 in the table corresponds to a probability of 1/2 of that specific output difference.
Thus, the differentials of high probability are as follows.
- An input difference of 2 (010) leads to an output difference of 3 (011) or 7 (111) with probability 1/2.
- An input difference of 5 (101) leads to an output difference of 4 (100) or 7 (111) with probability 1/2.
- An input difference of 7 (111) leads to an output difference of 3 (011) or 4 (100) with probability 1/2.
These differential characteristics only hold for a single S-box, but not for the whole cipher. In order to get a differential characteristic for the whole cipher, the characteristics for the S-boxes need to be stitched together. Up to here, our analysis was analogous to that of attackingasingleroundSPN , but now we need to extend that analysis.
The schematic below traces a possible difference throughout the cipher, up to the next but last round. Thick lines stand for a value of 1.
As we can see, the input difference of 16 (000 010 000) is distributed over three S-boxes. Adding the key to the data using xor does not affect the differences. Thus, in the first round, the input differences to the S-boxes are 000, 010, and 000 respectively. An input difference of 000 always leads to an output difference of 000. So, the interesting part is the S-box in the middle. Here, we know that the output difference is 111 with a probability of 1/2, due to our difference distribution table. Applying the permutation, it can be seen that the resulting difference is 010 010 010 with probability 1/2. In summary, if two plaintexts with a difference of 000 010 000 are encrypted with one round, the output difference is 010 010 010 with probability 1/2.
We could trace the differences for the next round. This is not shown in the schematic, as it is not necessary, but for illustration purposes, let us talk it through. We have the inputs 010 for each S-box, which are mapped to 111 with probability 1/2. Thus there is a combined probability of (1/2)^3 = 1/8 = 12.5% for the output 111 111 111 for all S-boxes in the last round. Consequently, for the whole cipher, an input difference of 000 010 000 leads to an output difference of 111 111 111 with 6.25% probability (50% for the first round and 12.5% for the last round). This analysis of probabilities is based on the wrong assumption, that the probabilities are independent and thus can be multiplied over multiple rounds. Even though this assumption is wrong, it is standard in differential cryptanalysis and experiments have shown that in practice it makes no difference.
As mentioned above, for our analysis it suffices to trace the differences only up to the last but one round. So, it should be kept in mind that an input difference of 000 010 000 leads to an output difference in the last but one round of 010 010 010 with 50% probability.
Key Recovery through Differential Cryptanalysis
Up to now, a differential characteristic through the whole cipher was found. These are sometimes also called differential trails. In this section, we show how to achieve key recovery using the differential trail.
As usual, the chosen-plaintext version of the differential attack is used. Thus, plaintext pairs with a fixed input difference are generated. The input difference of these pairs is chosen according to our differential characteristic for the cipher.
def gen_plain_cipher_pairs(input_diff, num):
# Generate num plaintext, ciphertext pairs with fixed input difference.
# Remember, this is a chosen plaintext attack
# random key which we want to recover
key = random.randint(0, 2**27-1)
print(f"[*] Real key: {key}")
print(f"[*] Corresponding round keys: {round_keys(key)}")
pairs = []
for input0 in random.sample(range(2**9-1), num):
input1 = input0 ^ input_diff
output0 = encrypt(input0, key)
output1 = encrypt(input1, key)
pairs.append(((input0, input1), (output0, output1)))
return pairs
plain_cipher_pairs = gen_plain_cipher_pairs(16, 500)In the code, 500 plaintext pairs with difference 000 010 000 are used. Additionally, their ciphertexts are known. There should be some good pairs among these pairs. As in the previous post, a good pair is a pair that satisfies our chosen characteristic.
Now, remember that for a plaintext difference of 000 010 000, the difference before the last S-box is 010 010 010 with 50% probability. Consequently, all 2^9 values for the last round key k2 can be tested as follows. A ciphertext-pair is chosen and decrypted up to before the S-box. There, the difference should be 010 010 010 with high probability if k2 is correct. Otherwise, the guess of k2 was wrong, or it is a false positive, as the plaintext pair used for validating the guess was not a good pair.
In our tests, there were around 64 probable keys k2 for the last round with the same probability. This is due to the fact, that there is a second characteristic for an S-box that maps 110 to 010 with 50% probability. Consequently, tracing the differences backwards through the cipher can lead to other trails with a similar probability of occurrence.
def recover_probable_last_roundkey():
print("[*] Brute-Forcing key of last round.")
# count for each key, how often we had the correct difference
count = [0 for i in range(2**9)]
for k3 in range(2**9): # bruteforce nine bits.
for _, outputs in plain_cipher_pairs:
out1 = outputs[0]
out2 = outputs[1]
mid1 = mux([inv_sbox(k ^ o)
for k, o in zip(demux(k3), demux(out1))])
mid2 = mux([inv_sbox(k ^ o)
for k, o in zip(demux(k3), demux(out2))])
if mid1 ^ mid2 == int('010010010', 2):
count[k3] += 1
# Multiple keys are printed. in my test i had 64 keys
# which occur 250 times.
most_probable_keys = [key for key in range(2**9)
if count[key] == max(count)]
print(f"[*] Most probable keys in last round: {most_probable_keys}")
print(f"[*] How often these keys yielded the correct difference: {max(count)}")
return most_probable_keys
last_round_keys = recover_probable_last_roundkey()How much effort is needed to brute-force the remaining round keys k0 and k1? Naively, this takes 2^18 steps. However, we can get away with only 2^9 steps, similar as in the last post of this series. If k2 is known, then k1 can be guessed. With these two round keys, k0 can be computed (not guessed). Thus, only all 2^9 values of k1 have to be guessed instead of all 2^18 values for k0 and k1.
As there are 64 probable round keys for k2 determined using 2^9 guesses, the overall effort of
recovering the key is 2^9*(number of plaintext pairs) * 2^9*64.
This is an effort of around 33.280 = 2^15 instead of
2^27 = 134.217.728 which are needed for a brute force attack on the
whole key space.
def validate_key(guessed_key):
"""Checks a key against the known plaintext-ciphertext pair and returns True if the key is correct."""
for ((input0, input1), (output0, output1)) in plain_cipher_pairs:
if encrypt(input0, guessed_key) != output0:
return False
if encrypt(input1, guessed_key) != output1:
return False
return True
def bruteforce_remaining_keyspace(last_round_keys):
print("[*] Brute-Forcing remaining key space.")
# Note that we need to check with multiple plaintext-ciphertext
# pairs. Checking with only one pair yields false positives for
# the key.
# Additionally, note that we do not need to bruteforce k1 and
# k2. If we know k2, we can compute k1 by using a plaintext
# ciphertext pair. Thereby, the effort of
# bruteforcing the remaining keyspace is 2**9 instead of 2**18.
((input0, input1), (output0, output1)) = plain_cipher_pairs[0]
for last_round_key in last_round_keys:
print(f"Trying last round key of {last_round_key}")
for k2 in range(2**9):
# Compute k1
key = (last_round_key << 18) | (k2 << 9) | 0
k1 = decrypt(output0, key) ^ input0
# Verify the key with other plaintext-ciphertext pairs
key = (last_round_key << 18) | (k2 << 9) | k1
if validate_key(key):
print(f"Recovered key --> {key}")
bruteforce_remaining_keyspace(last_round_keys)Current Research Trends
Even though differential cryptanalysis is considered a basic attack for modern symmetric encryption, there is still ongoing research. In this section, some of the modern research trends regarding differential encryption are highlighted.
Variations of Differential Cryptanalysis
There are many variations of standard differential cryptanalysis. For example, one can analyze the differences which can never occur. These are the zeroes in the difference distribution table. Their analysis leads to impossible differentials. Another variation is to analyze differences of differences. The study of these so-called higher order differentials can be exploited in higher order differential attacks. In truncated differential cryptanalysis only partially determined differences instead of the full differences are considered.
Finding Differentials for the Whole Cipher
One line of work considers the search for differentials for a complete cipher, given differential characteristics for the S-boxes. In our examples, we stitched the differential characteristics together manually, in order to receive a differential for the whole encryption algorithm. In general, this is not feasible as there may be too many rounds involved. Consequently, algorithms are needed that provide differential trails of high probability.
Security Proofs against Differential Attacks
Of course, there is also research on the defensive side. For a modern cipher there is usually a proof of its security against differential attacks. AES, for example, follows the wide trail design strategy. In this design strategy, when a difference different from zero is fed into the cipher, the number of S-boxes whose differential input is different from zero is large. This allows to bound the probability of differentials for the whole cipher.
Key schedule
In our toy design, the used key schedule was very simple. Usually that is not the case. AES, for example, uses 10, 12 or 14 rounds with a round key of 128 bits each. Simply concatenating the round keys to yield the main key would lead to a very large key. Consequently, the idea is to use the main secret key as seed for a random number generator. The outputs of the number generator are then used as round keys. Using a fully fledged cryptographically secure random number generator to derive the round keys may be safe, but this constitutes a very slow way. Hence, the security properties of the key schedule need to be evaluated, also in regards to the susceptibility to differential cryptanalysis. This is still an ongoing research topic.
References
- The main reference we used for this blog post is the fantastic tutorial into linear and differential cryptanalysis by Howard Heys available at http://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf
- Another notable reference is the seminal paper that introduced differential cryptanalysis by Biham and Shamir available at https://dl.acm.org/doi/10.5555/646755.705229
- Regarding the graphics, we are grateful for TikzforCryptographers which saved us a lot of time.
- TheDesignofRijndael is a good book to understand the intricacies in the design of AES and explains some design decisions.
- The title image is due to Pexels .
Full Code
The full code is shown below, and can also be downloaded here: multi_round_differential_crypto.py
# Differential Cryptanalysis Toy Implementation
# This code contains the differential cryptanalysis of a two round SPN.
# "First, we want to establish the idea that a computer language is
# not just a way of getting a computer to perform operations but
# rather that it is a novel formal medium for expressing ideas about
# methodology. Thus, programs must be written for people to read, and
# only incidentally for machines to execute."
# - Harold Abelson, Structure and Interpretation of Computer Programs
# Two Round SPN
# block size = 9 bit, sbox size = 3 bits, keylength = 27 bits
# see 02_differential.jpg for the specification
# xor k0
# sbox, sbox, sbox
# permutation: 0, 3, 6, 1, 4, 7, 2, 5, 8
# xor k1
# sbox, sbox, sbox
# xor k2
import random
s = [3, 6, 4, 5, 1, 7, 2, 0] # chosen by fair dice roll
s_rev = [s.index(0),
s.index(1),
s.index(2),
s.index(3),
s.index(4),
s.index(5),
s.index(6),
s.index(7)]
# not the bit length of the sbox, but its range of possible input values
SBOX_RANGE = len(s)
def sbox(x):
return s[x]
def inv_sbox(x):
return s_rev[x]
p = [0, 3, 6, 1, 4, 7, 2, 5, 8]
def pbox(x):
y = 0
for i in range(len(p)):
if (x & (1 << i)) != 0:
y = y ^ (1 << p[i])
return y
def demux(x):
"""
Takes 9 Bit value to three 3 Bit values.
demux(1) = [1,0,0]
demux(8) = [0,1,0]
"""
y = []
for i in range(3):
y.append((x >> (i * 3)) & 0x7)
return y
def mux(x):
"""
Takes three 3 Bit values to a 9 Bit value.
The inverse of demux.
mux(demux(13)) = 13
"""
y = 0
for i in range(3):
y = y ^ (x[i] << (i * 3))
return y
def round_function(input, round_key):
return mux([sbox(k ^ p) for k, p in zip(demux(round_key), demux(input))])
def round_keys(key):
"""
Derives the list of round keys from the main key.
Note: rounds are enumerated starting with zero.
"""
y = []
for i in range(3):
y.append((key >> (i * 9)) & 0x1ff)
return y
def encrypt(input, key):
if key > 2**27-1:
raise Exception("Key too long")
if input > 511:
raise Exception("Plaintext block too long")
roundkeys = round_keys(key)
output = round_function(input, roundkeys[0])
output = pbox(output)
output = round_function(output, roundkeys[1])
output = mux([(k ^ p) for k, p in zip(demux(roundkeys[2]), demux(output))])
# the last line is similar to
# output = output ^ roundkeys[2]
# but we avoid endianness errors
return output
def decrypt(input, key):
if key > 2**27-1:
raise Exception("Key too long")
if input > 511:
raise Exception("Plaintext block too long")
roundkeys = round_keys(key)
output = mux([(k ^ p) for k, p in zip(demux(roundkeys[2]), demux(input))])
output = mux([inv_sbox(x) for x in demux(output)])
output = mux([(k ^ p) for k, p in zip(demux(roundkeys[1]), demux(output))])
output = pbox(output) # in our case pbox = inv_pbox
output = mux([inv_sbox(x) for x in demux(output)])
output = mux([(k ^ p) for k, p in zip(demux(roundkeys[0]), demux(output))])
return output
def get_difference_distribution_table():
print("[*] Computing difference distribution table.")
diff_dist_table = [[0 for x in range(SBOX_RANGE)]
for y in range(SBOX_RANGE)]
for in_diff in range(SBOX_RANGE):
for input0 in range(SBOX_RANGE):
input1 = input0 ^ in_diff
out_diff = sbox(input0) ^ sbox(input1)
diff_dist_table[in_diff][out_diff] = diff_dist_table[in_diff][out_diff] + 1
return diff_dist_table
def matrix_pretty_print(matrix):
# https://stackoverflow.com/questions/13214809/pretty-print-2d-python-list
s = [[str(e) for e in row] for row in matrix]
lens = [max(map(len, col)) for col in zip(*s)]
fmt = ' '.join('{{:{}}}'.format(x) for x in lens)
table = [fmt.format(*row) for row in s]
print('\n'.join(table))
diff_dist_table = get_difference_distribution_table()
matrix_pretty_print(diff_dist_table)
# 8 0 0 0 0 0 0 0
# 0 2 2 0 0 2 2 0
# 0 0 0 4 0 0 0 4
# 0 2 2 0 0 2 2 0
# 0 2 2 0 0 2 2 0
# 0 0 0 0 4 0 0 4
# 0 2 2 0 0 2 2 0
# 0 0 0 4 4 0 0 0
# So, the nice differentials per round are as follows:
# input diff of 2 (010) leads to output diff of 3 (011) or 7 (111) with 50% probability (4/8)
# input diff of 5 (101) leads to output diff of 4 (100) or 7 (111) with 50% probability (4/8)
# input diff of 7 (111) leads to output diff of 3 (011) or 4 (100) with 50% probability (4/8)
# We stitch the differentials together as in 02_differential_char.jpg
# and get a differential for all rounds.
# An input difference of 16 (000 010 000) leads to an output difference
# of 511 (111 111 111) with probability of 6,25% (first round 50%,
# second round 12,5%)
# This is under the (wrong) assumption that the probabilities are
# independent. Even though this assumption is wrong it is standard in
# differential cryptanalysis.
# We only need to go to the second-but-last round, and have
# 000 010 000 -> 010 010 010 with 50% probability.
def gen_plain_cipher_pairs(input_diff, num):
# Generate num plaintext, ciphertext pairs with fixed input difference.
# Remember, this is a chosen plaintext attack
# random key which we want to recover
key = random.randint(0, 2**27-1)
print(f"[*] Real key: {key}")
print(f"[*] Corresponding round keys: {round_keys(key)}")
pairs = []
for input0 in random.sample(range(2**9-1), num):
input1 = input0 ^ input_diff
output0 = encrypt(input0, key)
output1 = encrypt(input1, key)
pairs.append(((input0, input1), (output0, output1)))
return pairs
plain_cipher_pairs = gen_plain_cipher_pairs(16, 500)
# We use the characteristic for the whole cipher.
# Thus the input difference is 16.
# As the characteristic 16 -> 511 holds with a probability of 6.25%
# we take 500 plain_cipher_pairs. There should be some good pairs in them.
# I found out, that it works without specially selecting good pairs.
# This may be due to the fact that the last round again lowers the
# probabilities of the characteristic holding.
# We know that for a plaintext difference of 000 010 000, the
# difference before the last sbox is 010 010 010 with 50%
# probability. That means we can now try all 2**9 values for the
# last roundkey and check if the difference before the last sbox is
# 010 010 010. If it is, it is probably the correct round key.
# In my tests i had around 64 keys for the last round which had the same
# probability. Why is this the case? There is also a differential
# characteristic for a single sbox 5 -> 7 or 110 -> 010 with 50% probability.
# The effort for key-recover is thus
# 2**9 * number of pairs for recovery of 64 possible values for k3
# + 2**9 * 64 for bruteforcing the remaining key space.
# Why is bruteforcing the remaining keyspace only 2**9 and not 2**18?
# Well, if we have a k3 and guess a k2, then we can compute (not
# guess!) a k1. Thus, we only have to try all 2**9 values of k2,
# instead of all 2**18 values for k2 and k1.
# This is an effort of around 33.280 = 2**15 instead of
# 2**27 = 134.217.728 for a complete bruteforce.
def recover_probable_last_roundkey():
print("[*] Brute-Forcing key of last round.")
# count for each key, how often we had the correct difference
count = [0 for i in range(2**9)]
for k3 in range(2**9): # bruteforce nine bits.
for _, outputs in plain_cipher_pairs:
out1 = outputs[0]
out2 = outputs[1]
mid1 = mux([inv_sbox(k ^ o)
for k, o in zip(demux(k3), demux(out1))])
mid2 = mux([inv_sbox(k ^ o)
for k, o in zip(demux(k3), demux(out2))])
if mid1 ^ mid2 == int('010010010', 2):
count[k3] += 1
# Multiple keys are printed. in my test i had 64
# keys which occur 250 times.
most_probable_keys = [key for key in range(2**9)
if count[key] == max(count)]
print(f"[*] Most probable keys in last round: {most_probable_keys}")
print(f"[*] How often these keys yielded the correct difference: {max(count)}")
return most_probable_keys
last_round_keys = recover_probable_last_roundkey()
# After we have the key(s) of the last round, we can brute-force the remainder of the key.
def validate_key(guessed_key):
"""Checks a key against the known plaintext-ciphertext pair and returns True if the key is correct."""
for ((input0, input1), (output0, output1)) in plain_cipher_pairs:
if encrypt(input0, guessed_key) != output0:
return False
if encrypt(input1, guessed_key) != output1:
return False
return True
def bruteforce_remaining_keyspace(last_round_keys):
print("[*] Brute-Forcing remaining key space.")
# Note that we need to check with multiple plaintext-ciphertext
# pairs. Checking with only one pair yields false positives for
# the key.
# Additionally, note that we do not need to bruteforce k1 and
# k2. If we know k2, we can compute k1 by using a plaintext
# ciphertext pair. Thereby, the effort of
# bruteforcing the remaining keyspace is 2**9 instead of 2**18.
((input0, input1), (output0, output1)) = plain_cipher_pairs[0]
for last_round_key in last_round_keys:
print(f"Trying last round key of {last_round_key}")
for k2 in range(2**9):
# Compute k1
key = (last_round_key << 18) | (k2 << 9) | 0
k1 = decrypt(output0, key) ^ input0
# Verify the key with other plaintext-ciphertext pairs
key = (last_round_key << 18) | (k2 << 9) | k1
if validate_key(key):
print(f"Recovered key --> {key}")
# Code for a full bruteforce of k1 and k2 for comparison purposes
# for k1 in range(2**9):
# for k2 in range(2**9):
# key = (last_round_key << 18) | (k2 << 9) | k1
# if validate_key(key):
# print(f"Recovered key --> {key}")
bruteforce_remaining_keyspace(last_round_keys)