Tags: brute-force
Rating:
# Task
Being normal is hard these days because of Corona virus pandemic!
We have source code and a file called output.txt.
The source code is the following:
```
import random
from flag import FLAG
p = 8443
def transpose(x):
result = [[x[j][i] for j in range(len(x))] for i in range(len(x[0]))]
return result
def vsum(u, v):
assert len(u) == len(v)
l, w = len(u), []
for i in range(l):
w += [(u[i] + v[i]) % p]
return w
def sprod(a, u):
w = []
for i in range(len(u)):
w += [a*u[i] % p]
return w
def encrypt(msg):
l = len(msg)
hyper = [ord(m)*(i+1) for (m, i) in zip(list(msg), range(l))]
V, W = [], []
for i in range(l):
v = [0]*i + [hyper[i]] + [0]*(l - i - 1)
V.append(v)
random.shuffle(V)
for _ in range(l):
R, v = [random.randint(0, 126) for _ in range(l)], [0]*l
for j in range(l):
v = vsum(v, sprod(R[j], V[j]))
W.append(v)
random.shuffle(transpose(W))
return W
enc = encrypt(FLAG)
print(enc)
```
output.txt contains the "encrypted" flag.
# Analysis
There are some computations made on the plaintext.
The first one: multiply the ASCII value of each character with its index in the plaintext increased by one, to obtain the list called "hyper".
Then, a diagonal matrix "V" is built from hyper: the values on the diagonal are the values from hyper, in the same order.
The rows of the matrix are then shuffled.
At this point, it starts the building of the matrix "W".
To summarize, each row of W is the list "hyper", with each element modified in the following way:
```
W[i][j] = (hyper[i] * random.randint(0, 126)) % p;
where p = 8443, "i" and "j" in range(l), where "l" is the length of the message to encrypt.
```
The previous shuffle was thwarted.
Finally, there is a misleading statement: ```random.shuffle(transpose(W))```; the random shuffle could make the challenge much harder... if only it were happened.
In fact, "transpose" function doesn't operate in place, returning the same object, but creates a new object.
Therefore, the statement has no effects.
The matrix "W" is then returned as "encrypted" output.
# Solution
The generic column of "W", let's denote it as ```W[:][j]``` is of the following form:
```
W[:][j] = [(ord(m) * (j + 1) * r[0][j]) % p, (ord(m) * (j + 1) * r[1][j]) % p, ... , (ord(m) * (j + 1) * r[l-1][j]) % p]
```
If it wasn't for the modulo operations, we could easily get ```ord(m) * (j + 1)``` by computing the GCD over column j, then obtain the character m in position j for each j, and finally join all characters to obtain the plaintext.
We can try to find a way to compute GCD in finite fields, but since the range of random values is not very large, we can compute a full mapping.
I mean: for each index i in the range of the length of the plaintext, for each possible character m in the plaintext's alphabet, for each possible random value r, compute the out value: ```((i + 1) * ord(m) * r) % p```, and remember it in a dict which maps out values to corresponding pairs (index, ASCII value of character); note that we don't need to memorize the random value.
Now, we know that for each column, we are going to find the same pair ```(i + 1, ord(m))```.
So, starting from the first element of a column and looking at its out value, we have a set of possible ```(i + 1, ord(m))``` pairs which could have generated that value.
If we look at the second element, it will have, in general, a different value and so a different set; but at least one pair must be in common with the first set, because one pair will be the good one for all the elements in the column.
Therefore we compute the intersection between the first set and the second set, and remember the result in "s".
As you may expect, now the game is simple: we loop over the column, obtain for each element the set of possible pairs, compute the intersection between this set and the set "s" and assign the result to "s".
We do this for all columns, obtaining an ordered list of sets of possible ```(i + 1, ord(m))``` pairs.
At this point, we have to choose the pairs, and now the statement "the random shuffle could make the challenge much harder" written before makes sense.
It's easy to choose the pairs if we suppose that for each set the indexes are unique, and this is easy to have because of the intersections between columns' sets.
In fact, from the set in position "i" in the ordered list, we just choose the pair which has index equal to "i + 1", and discard all the other pairs.
Now we have a list of pairs, that easily become a list of ASCII values, and we obtain the flag from this last list.
Here is the script:
```
import string
# redacted here for readability
output = [ [...], ..., [...] ]
def main():
p = 8443
mapping = {}
alphabet = string.digits + string.ascii_letters + '!-.?_{}'
for i in range(len(output)):
for m in alphabet:
for r in range(127):
_key = ((i + 1) * ord(m) * r) % p
_value = (i + 1, ord(m))
if mapping.get(_key):
mapping[_key].add(_value)
else:
mapping[_key] = set([_value])
values = []
for i in range(len(output)):
col = [output[j][i] for j in range(len(output))]
s = mapping[col[0]]
for j in range(1, len(col)):
s = s.intersection(mapping[col[j]])
values.append(s)
for i in range(len(values)):
val = values[i]
inOrder = False
delSet = set()
for t in val:
if t[0] == i + 1:
inOrder = True
else:
delSet.add(t)
if inOrder:
values[i] = values[i] - delSet
# sanity check :)
assert all(map(lambda _set: len(_set) == 1, values))
m = [0] * len(values)
for i in range(len(values)):
ind, flag_char = list(values[i])[0]
m[ind - 1] = flag_char
print("".join([chr(i) for i in m]))
if __name__ == "__main__":
main()
```
CCTF{H0w_f1Nd_th3_4lL_3I9EnV4Lu35_iN_FiN173_Fi3lD5!???}
