corCTF 2023 - Superbox (crypto)
Here we have a block-cipher in ternary: operating on trits in $GF(3)$ grouped into 135-trit branches treated as elements of $GF(3^{135})$. The structure is a short 6-round Feistel Network with squaring as the Feistel function:
left, right = SuperEncrypt.f(block), SuperEncrypt.f(message_hash)
for k in self.keys: # 6 rounds
right += (k + left) ^ 2
left, right = right, left
The goal is to recover the master key. This can be done by recovering the 6 round subkeys, and then using the key schedule to recover the master key from them, which is the more involved part.
# setup
x = var("x")
sys.path.append("2023-07-CorCTF-Superbox")
load("2023-07-CorCTF-Superbox/main.sage")
Recovering subkeys
Since the round function is very algebraic in nature and has low degree in both directions, we can directly solve the polynomial system involving the round keys in a few given encryptions. Furthermore, since the decryption direction is as simple as encryption, we can reduce the degrees of equations by building the system using the meet-in-the-middle approach.
rawpt = open("2023-07-CorCTF-Superbox/DDT.py", "rb").read()[:6000]
rawct = open("2023-07-CorCTF-Superbox/DDT.py.enc", "rb").read()
message_hash = pad(bytes_to_trits(sha512(rawpt).digest()[:25]), 135)
pt = [rawpt[i:i+25] for i in range(0, len(rawpt), 25)]
ct = [rawct[i:i+54] for i in range(0, len(rawct), 54)]
k0,k1,k2,k3,k4,k5 = SuperEncrypt.F["k0,k1,k2,k3,k4,k5"].gens()
eqs = []
for i in range(10):
message = pt[i]
chunk = pad(bytes_to_trits(message + b"\xff"), 135)
trin = chunk + message_hash
l, r = SuperEncrypt.f(trin[:135]), SuperEncrypt.F(trin[135:])
ciph = pad(bytes_to_trits(ct[i]), 270)
L, R = SuperEncrypt.f(ciph[:135]), SuperEncrypt.f(ciph[135:])
# Forward
r += (k0 + l)**2
l, r = r, l
r += (k1 + l)**2
l, r = r, l
r += (k2 + l)**2
l, r = r, l
# Backward
L, R = R, L
R -= (k5 + L)**2
L, R = R, L
R -= (k4 + L)**2
L, R = R, L
R -= (k3 + L)**2
eqs.append(l-L)
eqs.append(r-R)
ksol = Ideal(eqs).variety()
ksol
[{k5: 2*a^89 + a^88 + a^87 + a^85 + a^82 + 2*a^79 + a^78 + 2*a^77 + 2*a^76 + a^75 + a^74 + a^73 + a^72 + 2*a^70 + 2*a^69 + 2*a^66 + a^65 + 2*a^63 + a^62 + a^61 + 2*a^60 + a^59 + 2*a^57 + 2*a^52 + a^51 + a^50 + 2*a^47 + a^45 + a^44 + 2*a^43 + a^42 + 2*a^41 + a^40 + a^39 + 2*a^38 + a^36 + 2*a^34 + 2*a^31 + 2*a^30 + a^29 + a^28 + a^26 + a^25 + a^24 + a^23 + 2*a^20 + a^18 + a^17 + 2*a^16 + 2*a^15 + 2*a^14 + 2*a^12 + 2*a^11 + 2*a^9 + 2*a^7 + a^6 + a^2 + 2,
k4: a^134 + 2*a^133 + 2*a^132 + 2*a^131 + a^130 + 2*a^127 + a^126 + a^123 + a^121 + a^120 + 2*a^118 + a^117 + 2*a^115 + 2*a^114 + 2*a^113 + a^112 + a^110 + a^109 + a^108 + a^107 + a^106 + 2*a^105 + 2*a^104 + a^103 + 2*a^99 + 2*a^98 + a^95 + a^94 + 2*a^93 + a^92 + a^90 + a^88 + 2*a^87 + a^86 + 2*a^85 + 2*a^84 + 2*a^83 + a^82 + a^81 + a^80 + a^79 + 2*a^78 + a^77 + a^75 + a^74 + 2*a^72 + 2*a^71 + 2*a^69 + a^68 + 2*a^67 + a^64 + 2*a^63 + a^61 + a^60 + 2*a^57 + a^56 + a^55 + 2*a^54 + 2*a^53 + a^51 + 2*a^49 + 2*a^48 + 2*a^47 + a^45 + 2*a^44 + a^42 + 2*a^39 + 2*a^37 + 2*a^35 + a^33 + a^32 + 2*a^31 + a^30 + a^28 + a^27 + a^26 + 2*a^23 + 2*a^22 + 2*a^21 + 2*a^20 + 2*a^16 + a^15 + 2*a^13 + 2*a^12 + 2*a^11 + 2*a^10 + a^8 + a^7 + 2*a^6 + a^5 + a^4 + a^3 + a^2 + 2,
k3: 2*a^134 + a^133 + a^132 + a^131 + 2*a^130 + 2*a^129 + 2*a^127 + a^126 + 2*a^122 + a^121 + a^120 + a^118 + 2*a^117 + 2*a^116 + 2*a^115 + a^114 + 2*a^113 + a^112 + a^111 + a^109 + 2*a^108 + a^107 + 2*a^105 + a^104 + 2*a^103 + 2*a^102 + 2*a^101 + 2*a^100 + 2*a^98 + 2*a^91 + a^90 + a^89 + a^88 + a^87 + a^86 + 2*a^84 + a^83 + a^82 + a^81 + a^79 + a^78 + a^76 + 2*a^75 + a^74 + a^72 + a^70 + 2*a^68 + a^66 + a^63 + 2*a^62 + a^61 + a^60 + 2*a^57 + a^56 + 2*a^54 + a^53 + 2*a^52 + 2*a^51 + 2*a^50 + 2*a^47 + 2*a^45 + 2*a^43 + 2*a^41 + 2*a^40 + 2*a^37 + 2*a^34 + 2*a^32 + a^31 + 2*a^30 + a^29 + 2*a^28 + a^27 + 2*a^26 + 2*a^24 + a^23 + a^22 + 2*a^21 + 2*a^20 + a^19 + a^18 + 2*a^17 + a^16 + a^14 + a^13 + a^12 + 2*a^9 + 2*a^6 + a^5 + a^3 + a^2 + 2*a + 1,
k2: a^134 + a^132 + a^131 + a^130 + 2*a^127 + a^126 + 2*a^125 + a^124 + a^123 + 2*a^122 + 2*a^119 + a^118 + a^117 + a^116 + 2*a^115 + a^113 + a^111 + 2*a^110 + a^109 + a^107 + a^106 + a^105 + 2*a^104 + 2*a^103 + a^102 + 2*a^100 + a^97 + 2*a^96 + a^95 + a^94 + a^92 + a^91 + 2*a^88 + 2*a^87 + a^86 + 2*a^85 + 2*a^84 + a^82 + 2*a^81 + 2*a^80 + a^79 + 2*a^78 + 2*a^75 + a^73 + 2*a^72 + 2*a^71 + 2*a^70 + a^67 + 2*a^66 + a^65 + a^64 + 2*a^62 + a^61 + a^59 + a^58 + a^57 + 2*a^56 + a^54 + 2*a^53 + a^52 + 2*a^50 + 2*a^49 + 2*a^48 + 2*a^47 + a^45 + a^44 + 2*a^41 + 2*a^36 + a^35 + a^34 + 2*a^33 + a^32 + a^31 + 2*a^26 + a^25 + 2*a^24 + 2*a^21 + a^20 + a^18 + 2*a^16 + a^15 + 2*a^14 + a^12 + a^11 + 2*a^10 + 2*a^7 + a^5 + a^4 + a^3 + 2*a^2,
k1: a^134 + 2*a^133 + 2*a^130 + 2*a^129 + a^128 + 2*a^127 + 2*a^122 + 2*a^121 + 2*a^120 + 2*a^119 + a^115 + 2*a^114 + 2*a^113 + a^112 + a^110 + a^107 + 2*a^106 + 2*a^104 + a^103 + 2*a^102 + a^100 + a^99 + 2*a^98 + 2*a^97 + 2*a^96 + 2*a^94 + 2*a^93 + a^92 + 2*a^91 + a^90 + a^89 + 2*a^85 + 2*a^84 + 2*a^83 + 2*a^82 + 2*a^80 + 2*a^79 + 2*a^76 + 2*a^75 + a^73 + a^72 + 2*a^70 + 2*a^68 + a^67 + a^66 + 2*a^65 + a^63 + a^61 + a^59 + 2*a^58 + 2*a^56 + a^55 + 2*a^54 + a^53 + 2*a^52 + 2*a^50 + 2*a^49 + 2*a^48 + 2*a^47 + a^45 + 2*a^43 + 2*a^42 + 2*a^40 + a^39 + a^37 + 2*a^35 + 2*a^32 + a^31 + 2*a^30 + a^29 + 2*a^28 + a^27 + a^26 + 2*a^25 + 2*a^24 + a^23 + a^22 + a^21 + 2*a^20 + 2*a^19 + 2*a^18 + 2*a^17 + 2*a^14 + a^13 + a^12 + 2*a^11 + a^9 + a^8 + 2*a^6 + 2*a^5 + 2*a^4 + 2*a^3 + a + 1,
k0: 2*a^134 + 2*a^133 + a^132 + a^131 + 2*a^130 + a^129 + 2*a^128 + a^127 + 2*a^126 + a^124 + a^122 + a^121 + 2*a^120 + 2*a^119 + a^118 + 2*a^117 + 2*a^116 + a^115 + 2*a^114 + 2*a^111 + 2*a^110 + 2*a^107 + a^105 + a^104 + a^103 + a^101 + a^100 + a^99 + 2*a^98 + a^97 + 2*a^96 + a^95 + a^94 + 2*a^93 + a^92 + a^91 + 2*a^90 + 2*a^89 + a^87 + a^85 + 2*a^80 + a^79 + 2*a^78 + 2*a^77 + a^75 + a^74 + a^72 + a^70 + 2*a^69 + 2*a^68 + a^66 + a^65 + 2*a^64 + 2*a^63 + 2*a^62 + a^60 + a^59 + a^58 + a^57 + 2*a^56 + a^55 + a^54 + 2*a^53 + a^51 + a^49 + 2*a^47 + 2*a^45 + a^44 + a^43 + 2*a^42 + 2*a^41 + a^39 + a^38 + a^35 + 2*a^34 + 2*a^33 + 2*a^32 + a^30 + a^29 + a^27 + 2*a^26 + 2*a^24 + a^23 + 2*a^22 + 2*a^17 + 2*a^15 + 2*a^12 + a^10 + 2*a^9 + 2*a^8 + a^6 + a^3 + a^2 + 2*a + 1}]
globals().update({str(k): v for k, v in ksol[0].items()})
We get the subkeys in less than a minute!
The missing ... S-box
The key schedule employs an S-box operating on 5 trits, that is, mapping $GF(3)^5$ to itself (the set contains 243 elements). However, we are not given the S-box: only its ... DDT!
Recall that $DDT[a][b]$ tells us the number of $x$ such that $S(x+a)-S(x)=b$. In other words, how many solutions are there for the differential transition $a \to b$. In fact, we will only care about which transitions are possible (nonzero entry) and which are not (zero entries).
F.<a> = GF(3 ^ 5, 'a', modulus = x^5 + x^3 + x + 1)
def ddt(sbox):
ordered = [F.from_integer(i) for i in range(len(sbox))]
sbox2 = [F.from_integer(i) for i in sbox]
table = []
for delta_in in ordered:
row = [0] * 3^5
for element in ordered:
delta_out = (sbox2[(element + delta_in).to_integer()] - sbox2[(element).to_integer()]).to_integer()
row[delta_out] += 1
table.append(row)
return tuple(tuple(row) for row in table)
We are also given a few hints that could help:
try:
assert set(SUPERBOX) == set(range(3 ^ 5))
assert sha512(str(list(SUPERBOX)).encode()).hexdigest() == "ec7c27e69f323ae28e9321b50b99ecdcebc208c2d1d5ad48e53ae1416b3e38ddb9d6cb1977bd88b75e8d464baae398a8c6f5ce4fba3ae716bd523474126031a1"
assert SUPERBOX[13] == 37 # Patented identification method
except:
print("INVALID SUPERBOX SUPPLIED.")
print("CONTACT YOUR SUPERVISOR FOR A NEW COPY.")
exit()
Can we recover the S-box from its DDT? There are a few research papers on this problem. A more recent one ("Reconstructing an S-box from its Difference Distribution Table " uses a link between DDT and LAT (Linear Approximation Table / Walsh transform) of a function. This approach may be difficult to adapt to the ternary case. Another paper with more theory and direct approach is "Two Notions of Differential Equivalence on Sboxes". You can also see presentation slides for this paper by Valentin Suder. We will adapt the approach from this work.
Observe that DDT is invariant under adding a constant to the input and/or to the output of the S-box, since these only permute the solutions corresponding to each transition $a \to b$, and do not change their number. Therefore we can at least assume $S(0)=0$ and after finding a candidate matching the DDT consider $S+c$ for all $c \in GF(3)^5$. Conveniently, we can use the given hash digest of the S-box to check candidates.
Note: here we ignore the hint $S(13)=37$ since I forgot about it during the ctf. Using it could simplify the search a bit.
Now, the main search idea is as follows. Consider the first row $DDT[1][*]$. Using the assumption $S(0)=0$, we can now filter candidates for $S(1)$: $S(0+1)-S(0)=b$ must have $DDT[1][b] > 0$. Since each row of the DDT has about 1/3 nonzero entries, we can expect 1/3 of the candidates to survive. Note that we can repeat this for all rows of the DDT, not just $DDT[1]$.
All of this required no guesses (other than $S(0)=0$ which does not change solvability). After we compute all the filters as described above, we have to make a guess. We can choose an entry $x$ such that $S(x)$ has the smallest number of candidates. After guessing $S(x)$, we can again go through all rows $DDT[a]$ and filter candidates for $S(a+x)$.
After repeating this guess-filter procedure recursively, we can explore all possible solutions.
Note: In fact, because we have two degrees of freedom in choosing constants (as in $S(x+c_1)+c_2$), we can fix $S(1)$ arbitrarily among available candidates. And then enumerate all possible $c_1,c_2$ for resulting candidate S-boxes. Bur for this time, we will ignore this optimization.
# precompute tables for faster operations
ADD = [
[
(Expansion.F.from_integer(a) + Expansion.F.from_integer(b)).to_integer()
for b in range(243)
]
for a in range(243)
]
SUB = [
[
(Expansion.F.from_integer(a) - Expansion.F.from_integer(b)).to_integer()
for b in range(243)
]
for a in range(243)
]
from DDT import DDT
# initial candidates
cands = [set(range(1, 243)) for _ in range(243)]
cands[0] = {0}
for dx in range(1, 243):
for dy in range(1, 243):
if DDT[dx][dy] == 0:
cands[dx].remove(dy)
if dx < 10:
print("S(%d)" % dx, ":", len(cands[dx]), "candidates")
print("...")
S(1) : 93 candidates S(2) : 93 candidates S(3) : 91 candidates S(4) : 93 candidates S(5) : 90 candidates S(6) : 91 candidates S(7) : 90 candidates S(8) : 93 candidates S(9) : 89 candidates ...
SOLS = []
def recurse(n, knownx, knowny, cands):
if len(knownx) >= 243:
sol = []
for st in cands:
assert len(st) == 1
for a in st:
sol.append(a)
SOLS.append(sol)
return
ln, x = min(
(len(xs), x) for x, xs in enumerate(cands) if x not in knownx
)
for sx in cands[x]:
if sx in knowny:
continue
cands2 = [st.copy() for st in cands]
for dx in range(1, 243):
#s(x + dx) - s(x) =? dy
#s(x + dx) =? dy + sx
xdx = ADD[x][dx]
for sxdx in cands[xdx]:
dy = SUB[sxdx][sx]
if DDT[dx][dy] == 0:
cands2[xdx].remove(ADD[dy][sx])
if not cands2[xdx]:
break
else:
knownx.add(x)
knowny.add(sx)
recurse(n+1, knownx, knowny, cands2)
knownx.remove(x)
knowny.remove(sx)
recurse(n=0, knownx={0}, knowny={0}, cands=cands)
len(SOLS)
243
In less than a minute we recovered 243 candidates. Note that this matches the basic constant addition equivalence lower-bound: essentially we fixed one degree of freedom, but one was left, so that in total we have $243^2$ candidates and no surprises. By the way, there exist (binary) S-boxes with the same DDT but which are not related by input/output constant additions (see paper "Two Notions of Differential Equivalence on Sboxes").
Now we can go through the candidates, and all possible output constants, and compare to the hash from the hint.
for sol in SOLS:
# instead of guessing off we could
# compute it from the hing S(13) = 37
# but it's fast anyway
for off in range(243):
sbox = [ADD[off][a] for a in sol]
if sha512(str(list(sbox)).encode()).hexdigest() == "ec7c27e69f323ae28e9321b50b99ecdcebc208c2d1d5ad48e53ae1416b3e38ddb9d6cb1977bd88b75e8d464baae398a8c6f5ce4fba3ae716bd523474126031a1":
print("Found S-box:")
print(sbox)
SUPERBOX = sbox
break
Found S-box: [20, 208, 153, 26, 44, 92, 23, 164, 59, 189, 39, 104, 218, 37, 60, 235, 120, 115, 145, 188, 61, 126, 228, 223, 119, 40, 54, 166, 62, 88, 1, 72, 29, 17, 8, 192, 179, 97, 136, 125, 43, 91, 103, 213, 206, 112, 194, 87, 190, 106, 159, 78, 167, 227, 96, 174, 41, 5, 151, 14, 9, 65, 46, 231, 175, 152, 49, 110, 98, 144, 211, 183, 86, 198, 165, 186, 140, 157, 221, 162, 57, 105, 83, 200, 30, 109, 131, 161, 205, 64, 102, 214, 191, 47, 216, 123, 19, 215, 178, 128, 11, 229, 69, 130, 148, 38, 67, 210, 219, 89, 141, 207, 25, 7, 68, 233, 150, 201, 77, 182, 111, 100, 3, 34, 71, 129, 15, 73, 230, 121, 63, 51, 48, 6, 239, 226, 143, 85, 135, 196, 149, 127, 238, 107, 80, 171, 117, 42, 52, 122, 0, 139, 209, 169, 133, 24, 170, 36, 163, 181, 172, 94, 184, 137, 173, 212, 27, 138, 70, 242, 225, 236, 114, 2, 56, 160, 33, 31, 195, 240, 187, 146, 156, 18, 84, 158, 74, 220, 118, 108, 177, 203, 234, 185, 132, 199, 197, 147, 93, 22, 237, 99, 168, 81, 95, 90, 55, 50, 217, 82, 10, 155, 204, 58, 224, 75, 124, 202, 176, 35, 193, 113, 154, 12, 21, 4, 116, 45, 79, 134, 13, 222, 76, 28, 142, 101, 53, 66, 241, 32, 232, 16, 180]
Recovering the master key
Now we can finally look at the key schedule function. Essentially, the 6 round subkeys, each of size 135 trits, are generated in blocks of 45 trits. Furthermore, for some reason, only the first 17 blocks are meaningfull and the last one is filled with zeroes (as we could see from missing coefficients of $k_5$). Each generation takes the 45-trit block index and the master key and produces the output 45-trit subkey part.
@staticmethod
def mix(x):
x2 = sum(j * Expansion.c ^ i for i, j in enumerate(x))
result = x2 * Expansion.CONSTANT
return [result[i] for i in range(3)]
def generate(self, n):
new_key = [Expansion.F.from_integer(n)] * 9
new_key = [i + j for i, j in zip(new_key, self.primary_key)]
for _ in range(2):
new_key = [new_key[i] for i in Expansion.PBOX]
new_key = sum((Expansion.mix(new_key[i:i + 3]) for i in range(0, 9, 3)), [])
# Patented diffusion technology
tmp = [Expansion.F.from_integer(SUPERBOX[i.to_integer()]) for i in new_key]
new_key = [i * (j^2 + Expansion.a^2) * j for i, j in zip(tmp, new_key)]
new_key = [i + j for i, j in zip(new_key, self.primary_key)]
output = []
for n in new_key:
output.extend([n[i] for i in range(5)])
return output
The generation essentially consists of a two-round SPN with operating on 5-trit S-boxes arranged in a 3x3 state. What is strange, is that the S-box $S$ is actually applied as $$ x \mapsto x \cdot S(x) \cdot (x + a)$$ for some constant $a$. As could be expected, it results in a non-invertible mapping:
image = set()
for xi in range(243):
x = Expansion.F.from_integer(xi)
sx = Expansion.F.from_integer(SUPERBOX[x.to_integer()])
new_key = sx * (x**2 + Expansion.a**2) * x
image.add(new_key.to_integer())
len(image)
152
Meaning that we would have a tricky time inverting the function... Or maybe we can exploit this non-bijectivity for our purposes?
The last operation for each 45-trit block is addition of the raw master key! Therefore, because of the reduced number of possible values before the addition, we can directly discard master key's 5-trit candidates. After repeating this for the 17 available subkey blocks, we get:
keystream = []
for k in (k0, k1, k2, k3, k4, k5):
k_trits = [k[i] for i in range(135)]
print(k_trits)
keystream.extend(k_trits)
keystream = keystream[:-45]
[1, 2, 1, 1, 0, 0, 1, 0, 2, 2, 1, 0, 2, 0, 0, 2, 0, 2, 0, 0, 0, 0, 2, 1, 2, 0, 2, 1, 0, 1, 1, 0, 2, 2, 2, 1, 0, 0, 1, 1, 0, 2, 2, 1, 1, 2, 0, 2, 0, 1, 0, 1, 0, 2, 1, 1, 2, 1, 1, 1, 1, 0, 2, 2, 2, 1, 1, 0, 2, 2, 1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 2, 0, 0, 0, 0, 1, 0, 1, 0, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 0, 1, 1, 1, 0, 2, 0, 0, 2, 2, 0, 0, 2, 1, 2, 2, 1, 2, 2, 1, 1, 0, 1, 0, 2, 1, 2, 1, 2, 1, 1, 2, 2] [1, 1, 0, 2, 2, 2, 2, 0, 1, 1, 0, 2, 1, 1, 2, 0, 0, 2, 2, 2, 2, 1, 1, 1, 2, 2, 1, 1, 2, 1, 2, 1, 2, 0, 0, 2, 0, 1, 0, 1, 2, 0, 2, 2, 0, 1, 0, 2, 2, 2, 2, 0, 2, 1, 2, 1, 2, 0, 2, 1, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 2, 0, 1, 1, 0, 2, 2, 0, 0, 2, 2, 0, 2, 2, 2, 2, 0, 0, 0, 1, 1, 2, 1, 2, 2, 0, 2, 2, 2, 1, 1, 0, 2, 1, 2, 0, 2, 1, 0, 0, 1, 0, 1, 2, 2, 1, 0, 0, 0, 2, 2, 2, 2, 0, 0, 0, 0, 2, 1, 2, 2, 0, 0, 2, 1] [0, 0, 2, 1, 1, 1, 0, 2, 0, 0, 2, 1, 1, 0, 2, 1, 2, 0, 1, 0, 1, 2, 0, 0, 2, 1, 2, 0, 0, 0, 0, 1, 1, 2, 1, 1, 2, 0, 0, 0, 0, 2, 0, 0, 1, 1, 0, 2, 2, 2, 2, 0, 1, 2, 1, 0, 2, 1, 1, 1, 0, 1, 2, 0, 1, 1, 2, 1, 0, 0, 2, 2, 2, 1, 0, 2, 0, 0, 2, 1, 2, 2, 1, 0, 2, 2, 1, 2, 2, 0, 0, 1, 1, 0, 1, 1, 2, 1, 0, 0, 2, 0, 1, 2, 2, 1, 1, 1, 0, 1, 2, 1, 0, 1, 0, 2, 1, 1, 1, 2, 0, 0, 2, 1, 1, 2, 1, 2, 0, 0, 1, 1, 1, 0, 1] [1, 2, 1, 1, 0, 1, 2, 0, 0, 2, 0, 0, 1, 1, 1, 0, 1, 2, 1, 1, 2, 2, 1, 1, 2, 0, 2, 1, 2, 1, 2, 1, 2, 0, 2, 0, 0, 2, 0, 0, 2, 2, 0, 2, 0, 2, 0, 2, 0, 0, 2, 2, 2, 1, 2, 0, 1, 2, 0, 0, 1, 1, 2, 1, 0, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 2, 1, 0, 1, 1, 0, 1, 1, 1, 2, 0, 1, 1, 1, 1, 1, 2, 0, 0, 0, 0, 0, 0, 2, 0, 2, 2, 2, 2, 1, 2, 0, 1, 2, 1, 0, 1, 1, 2, 1, 2, 2, 2, 1, 0, 1, 1, 2, 0, 0, 0, 1, 2, 0, 2, 2, 1, 1, 1, 2] [2, 0, 1, 1, 1, 1, 2, 1, 1, 0, 2, 2, 2, 2, 0, 1, 2, 0, 0, 0, 2, 2, 2, 2, 0, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 2, 0, 2, 0, 2, 0, 0, 1, 0, 2, 1, 0, 2, 2, 2, 0, 1, 0, 2, 2, 1, 1, 2, 0, 0, 1, 1, 0, 2, 1, 0, 0, 2, 1, 2, 0, 2, 2, 0, 1, 1, 0, 1, 2, 1, 1, 1, 1, 2, 2, 2, 1, 2, 1, 0, 1, 0, 1, 2, 1, 1, 0, 0, 2, 2, 0, 0, 0, 1, 2, 2, 1, 1, 1, 1, 1, 0, 1, 2, 2, 2, 0, 1, 2, 0, 1, 1, 0, 1, 0, 0, 1, 2, 0, 0, 1, 2, 2, 2, 1] [2, 0, 1, 0, 0, 0, 1, 2, 0, 2, 0, 2, 2, 0, 2, 2, 2, 1, 1, 0, 2, 0, 0, 1, 1, 1, 1, 0, 1, 1, 2, 2, 0, 0, 2, 0, 1, 0, 2, 1, 1, 2, 1, 2, 1, 1, 0, 2, 0, 0, 1, 1, 2, 0, 0, 0, 0, 2, 0, 1, 2, 1, 1, 2, 0, 1, 2, 0, 0, 2, 2, 0, 1, 1, 1, 1, 2, 2, 1, 2, 0, 0, 1, 0, 0, 1, 0, 1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
cands = [set(range(243)) for _ in range(9)]
outs = [keystream[i:i+45] for i in range(0, len(keystream), 45)]
sets = [set() for _ in range(9)]
for out in outs:
slices = [out[i:i + 5] for i in range(0, 45, 5)]
out = [int(ZZ(i, 3)) for i in slices]
for i in range(9):
cands[i] = {c for c in cands[i] if SUB[out[i]][c] in image}
cands
[{115}, {185}, {41}, {209}, {4}, {14}, {79}, {146}, {191}]
Unique candidates! Phew, that was a convoluted challenge:
from hashlib import sha512
hidden_flag = b'^h\xde\t\xc9\x8e#N\x96K\xce\xd8-\xdc\xc16R{\x02Y\n_c\xf5\x9b\xbbhE\x0e=\xd5\xb7:\xd4'
output = []
key = [Expansion.F.from_integer(list(cs)[0]) for cs in cands]
for k in cands:
k, = list(k)
n = Expansion.F.from_integer(k)
output.extend([n[i] for i in range(5)])
print("Master key:")
print(output)
flag = bytes(i ^ j for i, j in zip(hidden_flag, sha512(str(list(output)).encode()).digest()))
print(flag)
Master key:
[1, 2, 0, 1, 1, 2, 1, 2, 0, 2, 2, 1, 1, 1, 0, 2, 0, 2, 1, 2, 1, 1, 0, 0, 0, 2, 1, 1, 0, 0, 1, 2, 2, 2, 0, 2, 0, 1, 2, 1, 2, 0, 0, 1, 2]
b'corctf{5uP3r_Id0L_d3_x1ao_r0Ng...}'