## RBTree.insert()

#### 카테고리: Write-up

The .Wat ness is open for testing!

http://watness.pwni.ng:7744/

When it came out in 2016, the Witness impressed with its ability to gradually teach new players the rules of the game by simply having them play it. With the .Wat ness, we take this just a small step further.

## How to solve

First of all, this write-up has a lot of guesses.

### Super easy guesses

If you’re a ‘the witness’ player, you can easily guess four symbols: (Read this with the guide) – Multicolored squares in the Witness – Suns in the Witness – Tetris blocks in the Witness – Triangles in the Witness
Wait, why the guide does not explain triangles? You need to draw a path exactly passes n edges of the block with n triangles. In The .Wat ness, it is n blue blocks.

But what are those?  We need to figure them out…

### Reversing

By reading src/constraints.ts, you can know there are total 6 constraints and Constraint5 is reversed triangles, and Constraint6 is round-edged rectangle.

By reading problem/common/src/bootstrap.ts, you can see four parameters are passed to fn_assembly/index/checkAll. (In the code, it is this.module.checkAll.) If checkAll returns an empty array, it is the answer. So, what are those four parameters?

 - mtx (parameter 1) : array_BoardMatrixElement
- parts (parameter 2) : array_PartitionListElement
- horizontalPathSegments (parameter 3) : array_i32
- verticalPathSegments (parameter 4): array_i32

The first parameter describes the symbols on the board.

If the board is partitioned by the input path, partition information is passed by the second parameter.

The third and fourth parameter have which edge is passed by the input path. So, the third one will be kinda 7×6 matrix, and the fourth one will be 6×7 matrix.

I’ve run wabt wasm2c to read the wasm file.

checkAll calls Constraint{i}_check functions. Let’s see Constraint6_check.
When reading the code, p{i} is the ith parameter, l{i} is a local variable, and i{i} is a temporal variable. Just understand l{i} as non-volatile registers, and i{i} as volatile registers.

static u32 assembly_index_Constraint6_check(u32 p0, u32 p1, u32 p2, u32 p3) {
u32 l4 = 0, l5 = 0, l6 = 0, l7 = 0, l8 = 0;
FUNC_PROLOGUE;
u32 i0, i1, i2, i3;
i0 = 0u;
i1 = 0u;
i0 = _lib_array_Array_Constraint__constructor(i0, i1);
l4 = i0;
i0 = 0u;
l5 = i0;
L1:
i0 = l5;
i1 = p0;
l6 = i1;
i1 = l6;
i1 = i32_load((&memory), (u64)(i1 + 4));
i0 = (u32)((s32)i0 < (s32)i1);
i0 = !(i0);
if (i0) {goto B0;}
i0 = 0u;
l6 = i0;
L4:
i0 = l6;
i1 = p0;
i2 = l5;
i1 = _lib_array_Array_Array_BoardMatrixElement_____get(i1, i2);
l7 = i1;
i1 = l7;
i1 = i32_load((&memory), (u64)(i1 + 4));
i0 = (u32)((s32)i0 < (s32)i1);
i0 = !(i0);
if (i0) {goto B3;}
i0 = p0;
i1 = l5;
i0 = _lib_array_Array_Array_BoardMatrixElement_____get(i0, i1);
i1 = l6;
i0 = _lib_array_Array_BoardMatrixElement____get(i0, i1);
i0 = i32_load((&memory), (u64)(i0 + 4));
i1 = 0u;
i0 = i0 != i1;
l7 = i0;
if (i0) {
i0 = p0;
i1 = l5;
i0 = _lib_array_Array_Array_BoardMatrixElement_____get(i0, i1);
i1 = l6;
i0 = _lib_array_Array_BoardMatrixElement____get(i0, i1);
i0 = i32_load((&memory), (u64)(i0 + 4));
i0 = i32_load((&memory), (u64)(i0 + 12));
i1 = 2344u;
i0 = assembly_index_streq(i0, i1);
} else {
i0 = l7;
}
if (i0) {
i0 = p0;
i1 = l5;
i0 = _lib_array_Array_Array_BoardMatrixElement_____get(i0, i1);
i1 = l6;
i0 = _lib_array_Array_BoardMatrixElement____get(i0, i1);
l7 = i0;
i0 = p2;
i1 = l5;
i0 = _lib_array_Array_Array_i32_____get(i0, i1);
i1 = l6;
i0 = _lib_array_Array_i32____get(i0, i1);
i1 = p2;
i2 = l5;
i3 = 1u;
i2 += i3;
i1 = _lib_array_Array_Array_i32_____get(i1, i2);
i2 = l6;
i1 = _lib_array_Array_i32____get(i1, i2);
i0 += i1;
i1 = p3;
i2 = l5;
i1 = _lib_array_Array_Array_i32_____get(i1, i2);
i2 = l6;
i1 = _lib_array_Array_i32____get(i1, i2);
i0 += i1;
i1 = p3;
i2 = l5;
i1 = _lib_array_Array_Array_i32_____get(i1, i2);
i2 = l6;
i3 = 1u;
i2 += i3;
i1 = _lib_array_Array_i32____get(i1, i2);
i0 += i1;
l8 = i0;
i0 = l8;
i1 = 0u;
i0 = i0 != i1;
if (i0) {
i0 = l4;
i1 = p0;
i2 = l5;
i1 = _lib_array_Array_Array_BoardMatrixElement_____get(i1, i2);
i2 = l6;
i1 = _lib_array_Array_BoardMatrixElement____get(i1, i2);
i1 = i32_load((&memory), (u64)(i1 + 4));
i0 = _lib_array_Array_Constraint__push(i0, i1);
}
}
i0 = l6;
i1 = 1u;
i0 += i1;
l6 = i0;
goto L4;
UNREACHABLE;
B3:;
i0 = l5;
i1 = 1u;
i0 += i1;
l5 = i0;
goto L1;
UNREACHABLE;
B0:;
i0 = l4;
FUNC_EPILOGUE;
return i0;
}

L1 and L2 are loop labels. Each uses l5 and l6 as an iterator.
The key part is Line 55-104. It checks whether any edge around the block is passed by the input path. If yes, it will return those blocks as array_Constraint.

The return value should be an empty array, so round-edged rectangle symbols are like blue blocks symbols with zero blue blocks. We need to avoid four edges around round-edged rectangles, regardless of its color!

Then, what are reversed triangles? Well, I don’t know.

It’s still solvable without knowing it. Just try all the possible paths around reversed triangles. One of them will be a solution.

### Solving

Just do by your hands. If it seems hard to solve, just press F5. I solved all the stages within 2 minutes.

The flag is pctf{what_if_i_made_firmament_instead}.

BTW, I solved all the puzzles in the Witness.

## Plaid Party Planning III 1

Other teammates solved this one. You can get a flag easily by just jumping to a flag printing routine. Just use GDB to change RIP, or patch the binary to jump into the routine.

The flag is PCTF{1 l1v3 1n th3 1nt3rs3ct1on of CSP and s3cur1ty and parti3s!}.

## Plaid Party Planning III 2

Basically, behaviors of binaries (III 1, III 2) are same.

The problem is here:

There are 15 people, and foods which are arranged on 5×5 board. Each food has a ‘taste’ value from 0 to 14. Also, each person has a different ‘taste’ value from 0 to 14. A person prefers a food that the difference of its taste value and the food’s taste value is large, in modular 15. It can be written in code as:

def compare_taste(user, food):
v2 = (2 * (user - food)) % 30
v4 = (2 * (food - user) + 1) % 30
return min(v2, v4)

The taste values of foods are fixed. Inputs are the taste values of people.
(When giving inputs to the binary, you need to add 1 to each inputs, because it only allows values in [1, 15].)

Next, there are total 15 functions which describes a behavior of each person while the party. Let’s say those ‘behavior functions.’

Each behavior function is a chain of three functions: grab(row), put(row), sleep(time).

grab(row) will grab a food that a person prefers most in row. If someone already grabbed the food in row, the person will wait until the food is put back.
put(row) will put back the food in its position.
sleep(time) sleeps as the given time.

In inner implementation, each food has a lock. If it’s grabbed by someone, the lock is locked. If it’s put back, the lock is unlocked.

There are two routines.

The first routine simulates the party. It just makes 15 threads for each person’s funciton, and run it. Everyone sleeps 1 second while grab and put, and also sleep time seconds when sleep is called.

The second routine checks all the possible permutations of grab, put of all the people. If there’s a deadlock so it is not possible to grab more, it will return false. If every permutation has no deadlock, it will return true.

The second routine is much stronger than the first routine, but this routine never terminates before we die. But we can now understand that the challenge wants us to get a deadlock-free inputs.

### How to solve

First, we can get every possible (A lock → B lock) pairs from the behavior functions to check possible deadlocks. If there are a behavior function with (A lock → B lock) and a behavior function with (B lock → A lock), it can cause a deadlock.

lockpairs = [
[(4, 3, []), (3, 0, []), (2, 1, []), (0, 2, []), (2, 0, [])],
[(0, 4, []), (0, 2, ), (0, 1, [2, 4]), (4, 2, ), (4, 1, [0, 2]), (2, 1, [0, 4]), (4, 3, ), (2, 3, ), (4, 1, [])],
[(2, 1, []), (1, 2, []), (1, 0, []), (1, 4, []), (1, 3, [])],
[(4, 3, []), (3, 0, []), (2, 1, []), (1, 4, [])],
[(1, 2, []), (1, 3, ), (2, 3, ), (2, 3, [])],
[(4, 3, []), (3, 0, []), (3, 2, []), (2, 1, []), (0, 2, [])],
[(0, 2, []), (2, 1, []), (3, 0, []), (3, 4, [])],
[(1, 3, []), (1, 2, ), (3, 2, )],
[(0, 2, []), (2, 1, []), (3, 4, [])],
[(3, 1, []), (3, 4, []), (0, 2, []), (2, 1, [])],
[(1, 3, []), (1, 2, ), (3, 2, ), (3, 0, [])],
[(4, 1, []), (4, 2, ), (1, 2, ), (2, 1, []), (0, 1, []), (0, 2, ), (1, 2, )],
[(0, 1, []), (1, 2, []), (1, 3, ), (2, 3, ), (1, 3, [])],
[(0, 2, []), (2, 1, []), (0, 4, [])],
[(3, 1, []), (3, 2, ), (1, 2, [])],
]

Each row means each person’s lock pairs. (A, B, [C]) means the person has (Lock from A row → Lock from B row) routine in its behavior functions, with gate locks [C_1 row, C_2 row, …].

Second, we can calculate each person’s food choices on each row when its taste value is 0 ~ 14.

foods = [
[0, 3, 6, 9, 12],
[1, 6, 11, -1, -1],
[1, 4, 8, 14, -1],
[2, 8, -1, -1, -1],
[1, 5, 9, 10, 13],
]

def compare_taste(user, food):
v2 = (2 * (user - food)) % 30
v4 = (2 * (food - user) + 1) % 30
return min(v2, v4)

choices = []

# Choice for each likelihood
for v in range(15):
choice = []
for i in range(5):
ansidx, ans = 0, compare_taste(v, foods[i])
for j in range(1, 5):
if foods[i][j] == -1:
break
t = compare_taste(v, foods[i][j])
if ans > t:
ansidx, ans = j, t

choice.append(ansidx)
choices.append(choice)

Third, check all possible deadlocks between person i and person j, when person i‘s taste value is v1 and person j‘s taste value is v2.

# Possible deadlock pairs
pos_dl_pairs = []

for i in range(15):
for j in range(i + 1, 15):

for (p1, q1, r1) in lockpairs[i]:
for (p2, q2, r2) in lockpairs[j]:
if p2 == q1 and p1 == q2:

gatelocks = list(set(r1) & set(r2))
# If ith person and jth person picks a same food
# in row p1 and p2, it will cause a deadlock.
pos_dl_pairs.append( (i, j, p1, p2, gatelocks) )

deadlocks = [ [ [] for i in range(15) ] for j in range(15) ]

for (u1, u2, i1, i2, gatelocks) in pos_dl_pairs:
for v1 in range(15):
for v2 in range(15):
if v1 == v2: continue
if choices[v1][i1] == choices[v2][i1] and choices[v1][i2] == choices[v2][i2]:
# Check if there's a gate lock.
# If yes, it could not cause a deadlock.
flag = True
for g in gatelocks:
if choices[v1][g] == choices[v2][g]:
flag = False
break

if flag:
deadlocks[u1][v1].append( (u2, v2) )

Finally, do backtracking with those deadlock constraints and get possible deadlock-free inputs.

ans = []
check = [ [ 0 for i in range(15) ] for j in range(15) ]

def backtrack(idx):
if idx == 15:
with open("ans.txt", "a") as f:
f.write(str(ans) + "\n")
print(ans)
return
for i in range(15):
if check[idx][i] > 0:
continue
if idx == 6 and choices[i] == 1:
continue

for u in range(idx + 1, 15):
check[u][i] += 1
check[u][v] += 1

ans.append(i)
backtrack(idx + 1)
ans.pop()

for u in range(idx + 1, 15):
check[u][i] -= 1
check[u][v] -= 1

backtrack(0)

The full solver is here:

lockpairs = [
[(4, 3, []), (3, 0, []), (2, 1, []), (0, 2, []), (2, 0, [])],
[(0, 4, []), (0, 2, ), (0, 1, [2, 4]), (4, 2, ), (4, 1, [0, 2]), (2, 1, [0, 4]), (4, 3, ), (2, 3, ), (4, 1, [])],
[(2, 1, []), (1, 2, []), (1, 0, []), (1, 4, []), (1, 3, [])],
[(4, 3, []), (3, 0, []), (2, 1, []), (1, 4, [])],
[(1, 2, []), (1, 3, ), (2, 3, ), (2, 3, [])],
[(4, 3, []), (3, 0, []), (3, 2, []), (2, 1, []), (0, 2, [])],
[(0, 2, []), (2, 1, []), (3, 0, []), (3, 4, [])],
[(1, 3, []), (1, 2, ), (3, 2, )],
[(0, 2, []), (2, 1, []), (3, 4, [])],
[(3, 1, []), (3, 4, []), (0, 2, []), (2, 1, [])],
[(1, 3, []), (1, 2, ), (3, 2, ), (3, 0, [])],
[(4, 1, []), (4, 2, ), (1, 2, ), (2, 1, []), (0, 1, []), (0, 2, ), (1, 2, )],
[(0, 1, []), (1, 2, []), (1, 3, ), (2, 3, ), (1, 3, [])],
[(0, 2, []), (2, 1, []), (0, 4, [])],
[(3, 1, []), (3, 2, ), (1, 2, [])],
]

foods = [
[0, 3, 6, 9, 12],
[1, 6, 11, -1, -1],
[1, 4, 8, 14, -1],
[2, 8, -1, -1, -1],
[1, 5, 9, 10, 13],
]

def compare_taste(user, food):
v2 = (2 * (user - food)) % 30
v4 = (2 * (food - user) + 1) % 30
return min(v2, v4)

choices = []

# Choice for each likelihood
for v in range(15):
choice = []
for i in range(5):
ansidx, ans = 0, compare_taste(v, foods[i])
for j in range(1, 5):
if foods[i][j] == -1:
break
t = compare_taste(v, foods[i][j])
if ans > t:
ansidx, ans = j, t

choice.append(ansidx)
choices.append(choice)

pos_dl_pairs = []

for i in range(15):
for j in range(i + 1, 15):

for (p1, q1, r1) in lockpairs[i]:
for (p2, q2, r2) in lockpairs[j]:
if p2 == q1 and p1 == q2:

gatelocks = list(set(r1) & set(r2))
# If ith person and jth person picks a same food
# in row p1 and p2, it will cause a deadlock.
pos_dl_pairs.append( (i, j, p1, p2, gatelocks) )

deadlocks = [ [ [] for i in range(15) ] for j in range(15) ]

for (u1, u2, i1, i2, gatelocks) in pos_dl_pairs:
for v1 in range(15):
for v2 in range(15):
if v1 == v2: continue
if choices[v1][i1] == choices[v2][i1] and choices[v1][i2] == choices[v2][i2]:
# Check if there's a gate lock.
# If yes, it could not cause a deadlock.
flag = True
for g in gatelocks:
if choices[v1][g] == choices[v2][g]:
flag = False
break

if flag:

ans = []
check = [ [ 0 for i in range(15) ] for j in range(15) ]

def backtrack(idx):
if idx == 15:
with open("ans.txt", "a") as f:
f.write(str(ans) + "\n")
print(ans)
return
for i in range(15):
if check[idx][i] > 0:
continue
if idx == 6 and choices[i] == 1:
continue

for u in range(idx + 1, 15):
check[u][i] += 1
check[u][v] += 1

ans.append(i)
backtrack(idx + 1)
ans.pop()

for u in range(idx + 1, 15):
check[u][i] -= 1
check[u][v] -= 1

backtrack(0)

There are total 5574 possible inputs:

Just run all of them. You can efficiently run them by patching, or running multiple processes.

The answer is [11, 13, 3, 7, 4, 10, 9, 1, 0, 8, 2, 12, 5, 14, 6]. You can run this by ./pppiii 1 12 14 4 8 5 11 10 2 1 9 3 13 6 15 7.

The flag is PCTF{J ljv3 Jn th3 1nt3rs3ctJon of CSP and s3curjty and partj3s!}.

(It seems these inputs does not satisfy the second routine above, but I’m not sure :P)

Guys, guys, don’t fight. I’m sure we’ll be able to come up with something roughly equal.

source

eulernt.pwni.ng:5555

NOTE: We originally uploaded the wrong version. It is still available here if you really want it: wrong version.

## How to solve

We need to get a divisor of $333!$ that is close to $(333!)^{1/2}$.

Just factorize with factorDB. There are some $p^k$s of which $k$ is odd. Let’s define a product of those $p$s as $v := \prod p$.

So, we can easily get $(333! / v) ^ {1/2}$. The next step is to calculate a value which is similar to $v ^ {1/2}$.

Let’s just guess we can make the value with primes {2, 3, 5, 7, 11, 13, 17, 19, 23}. Then try all possible values nearby $v ^ {1/2}$. If you can get from this set, just add more primes.

import gmpy2

primes = [3, 5, 7, 19, 29, 37, 43, 47,
59, 61, 89, 97, 101, 103, 107,
109, 167, 173, 179, 181, 191,
193, 197, 199, 211, 223, 227,
229, 233, 239, 241, 251, 257,
263, 269, 271, 277, 281, 283,
293, 307, 311, 313, 317, 331]

v = 1
for p in primes:
v *= p

N = 1
for i in range(2, 333):
N *= i

Nv_root = gmpy2.isqrt(N // v)
v_root = gmpy2.isqrt(v)

# Rough upper limit
lim = v_root + v_root // 10000
primes = [3, 5, 7, 11, 13, 17, 19, 23]

def backtrack(idx, val):
if idx == len(primes):
lg = int(math.log(v_root, 2) - math.log(val, 2))
final = val * (2 ** lg) * Nv_root
fstr = str(final)
if len(fstr) == 349 and fstr[:8] == '32147263':
print(final)
final *= 2
fstr = str(final)
if len(fstr) == 349 and fstr[:8] == '32147263':
print(final)
return

while True:
val *= primes[idx]
if val > lim:
return
backtrack(idx + 1, val)

backtrack(0, 1)

From this, I was able to get a value:

3214726365718308699390009351051926320347863432801378170603206865184662872923685805900796110576640315841185356341136473888821110903341917546848786593096487214784202625564775154918631601168022399388653631105727651790627380050049166043926298612848761901579219048962836676642657563673663196096066312251333672960000000000000000000000000000000000000000000

The flag is PCTF{R3fr3sh1ngly_Sm00th}.

## How to solve

Permutations can be handled as matrices.

For given key $k$ and plaintext $(x, y)$, the result of one-round encryption is: $(x_1, y_1) = (y, xk^{-1}yk)$

Let’s do this for three rounds! $(x_2, y_2) = (xk^{-1}yk, yk^{-1}xk^{-1}yk^2)$ $(x_3, y_3) = (y_2, xk^{-1}ykk^{-1}y_2k) = (y_2, xk^{-1}yy_2k)$

If we define $t = yy_2$, we can say that $(yx_3, y_3) = (t, xk^{-1}tk)$

So, the three-round encryption is not different from the one-round one!

From this, just run backtracking for $x^{-1}y_3 = k^{-1}tk$ to get proper $k$ that satisfies the both sets.

import random
from hashlib import sha1
from horst import Permutation

with open('data.txt', 'r') as f:

(x1, y1), (t1, u1) = data
(x2, y2), (t2, u2) = data

# Left-hand side: l
l1, l2 = x1.inv() * u1, x2.inv() * u2
# Right-hand side: k^{-1} r k
r1, r2 = y1 * t1, y2 * t2

k = [-1 for _ in range(64)]
kinv = [-1 for _ in range(64)]
called = []

def backtrack(idx):
if idx in called:
st = set(range(64)) - set(called)
if len(st) == 0:
k_str = str(Permutation(k)).encode('ascii')
print("PCTF{%s}" % sha1(k_str).hexdigest())
exit(0)
backtrack(min(st))
return

called.append(idx)
p, q = l1[idx], l2[idx]

# Running backtracking for: l = k^{-1} r k
# If l[idx] = p, then k[r[kinv[idx]]] = p
# Let's say kinv[idx] = a, r[a] = b, k[b] = p.
# Just do possible all the (a, b) pairs for backtracking.

# Possible a values
if kinv[idx] != -1:
arange = [kinv[idx]]
else:
# Values which are not used
arange = list(set(range(64)) - set(kinv))

for a in arange:

# If k[a] is assigned, flag_ka is True.
flag_ka = False
if kinv[idx] == -1:
flag_ka = True
kinv[idx] = a
k[a] = idx

b = r1[a]
c = r2[a]

if ((k[b] != -1 and k[b] != p) or (kinv[p] != -1 and kinv[p] != b)
or (k[c] != -1 and k[c] != q) or (kinv[q] != -1 and kinv[q] != c)):
# Set back
if flag_ka:
kinv[idx] = -1
k[a] = -1
continue

# If k[b] is assigned, flag_kb is True, and so on.
flag_kb, flag_kc = False, False
if k[b] == -1:
flag_kb = True
k[b] = p
kinv[p] = b
if k[c] == -1:
flag_kc = True
k[c] = q
kinv[q] = c

backtrack(p)

# Set back
if flag_kc:
k[c] = -1
kinv[q] = -1
if flag_kb:
k[b] = -1
kinv[p] = -1
if flag_ka:
kinv[idx] = -1
k[a] = -1

called.pop()

backtrack(0)

The flag is PCTF{69f4153d282560cdaab05e14c9f1b7e0a5cc74d1}.

I heard bulldozer is on this channel, be careful!
nc crypto.chal.ctf.westerns.tokyo 5643

To decrypt the flag, we need two things: the AES key and the IV when the flag is generated.

#### IV

IV is generated by random.getrandbits(). Python random uses Mersenne Twister, and it is able to recover the state of the Python random generator with 624 32-bit integers. See this link for detail.

You can check that MT::untemper works normally with this code.

from pwn import *

r = remote('crypto.chal.ctf.westerns.tokyo', 5643)
menu_str = '4: get encrypted key'

rand_values = []
def encrypt(t):
r.sendline('1')
r.sendline(t)

# Store random values to restore MT
iv = int(l.split('AES: ')[:32], 16)
for i in range(4):
rand_values.append( (iv >> (32 * i)) & ((1 << 32) - 1) )

rsa = int(l.split('RSA:').split('AES:'), 16)
return rsa

for i in xrange(256):
encrypt('\x00')

from mt import untemper
mt_state = tuple(map(untemper, rand_values[:624]) + )
random.setstate((3, mt_state, None))

for i in xrange(1024):
rnd = random.getrandbits(128)
assert rnd == rand_values[i], "Failed"

#### AES Key

• This part is unintended.

We can get $aeskey^e (mod\ N)$ by the option 4, and we can decrypt $x^e (mod\ N)$ with the option 2, but it only gives the length and the last one byte of the plain message.

The problem is that they give the length. AES key is 16byte, and the RSA is 1024bit. It is possible to get $(aeskey \times t)^e (mod\ N)$ for any $t$. So we can recover the AES key one bit by one bit, from the MSB to the LSB, by multiplying a value $t$ that makes a difference in the length of the decrypted message.

from pwn import *
# Using encrypt() defined above

# Calculate N of RSA
N = None
for i in range(2, 8): # 2 ~ 7, total
enc = encrypt( chr(i) )
if N is None:
N = pow(i, 0x10001) - enc
else:
N = GCD(N, pow(i, 0x10001) - enc)

# Get encrypted AES key
r.sendline('4')
aeskey_enc = l.split('here is encrypted key :)\n')[:256]
aeskey_enc = int(aeskey_enc, 16)

# Check whether the length is 128 bytes, or not.
def decrypt(t):
r.sendline('2')
r.sendline(t)
lsb = l.split('RSA: ').split('\n')
return lsb

recovered = 0
two_1016 = 2 ** 1016
for i in xrange(127, -1, -1):
threshold = recovered + 2 ** i
tmp = (two_1016 + threshold - 1) // threshold
assert tmp * (threshold - 1) < two_1016, "Failed"

val = aeskey_enc * pow(tmp, 0x10001, N) % N
res = decrypt( long_to_bytes(val).encode('hex') )
if len(res) // 2 == 128:
recovered += 2 ** i

aeskey = recovered
print('aeskey', aeskey)

#### Full exploit

from pwn import *
from Crypto.Util.number import long_to_bytes, GCD
from Crypto.Cipher import AES
import random

r = remote('crypto.chal.ctf.westerns.tokyo', 5643)
menu_str = '4: get encrypted key'

# === Stage 1: Recover Python MT ===

rand_values = []
def encrypt(t):
r.sendline('1')
r.sendline(t)

# Store random values to restore MT
iv = int(l.split('AES: ')[:32], 16)
for i in range(4):
rand_values.append( (iv >> (32 * i)) & ((1 << 32) - 1) )

rsa = int(l.split('RSA:').split('AES:'), 16)
return rsa

# Calculate N of RSA
N = None
for i in range(2, 8): # 2 ~ 7, total
enc = encrypt( chr(i) )
if N is None:
N = pow(i, 0x10001) - enc
else:
N = GCD(N, pow(i, 0x10001) - enc)

for i in xrange(156 - 6):
encrypt('\x00')

# From http://mslc.ctf.su/wp/confidence-ctf-2015-rsa2-crypto-500/
from mt import untemper
mt_state = tuple(map(untemper, rand_values[:624]) + )
random.setstate((3, mt_state, None))

for i in xrange(156):
rnd = random.getrandbits(128)

iv = random.getrandbits(128)
print('next iv', iv)

r.sendline('3')
flag = l.split('coming!\n').split('\n')[32:]
print('flag', flag)

# === Stage 2: Recover AES key ===

def decrypt(t):
r.sendline('2')
r.sendline(t)
lsb = l.split('RSA: ').split('\n')
return lsb

r.sendline('4')
aeskey_enc = l.split('here is encrypted key :)\n')[:256]
aeskey_enc = int(aeskey_enc, 16)

# Check whether the length is 128 bytes, or not.
recovered = 0
two_1016 = 2 ** 1016
for i in xrange(127, -1, -1):
threshold = recovered + 2 ** i
tmp = (two_1016 + threshold - 1) // threshold
assert tmp * (threshold - 1) < two_1016, "Failed"

val = aeskey_enc * pow(tmp, 0x10001, N) % N
res = decrypt( long_to_bytes(val).encode('hex') )
if len(res) // 2 == 128:
recovered += 2 ** i

aeskey = recovered
print('aeskey', aeskey)

r.close()

# === Stage 3: Decrypt ===

flag = flag.decode('hex')
aeskey = long_to_bytes(aeskey, 16)
iv = long_to_bytes(iv, 16)

n = ord(s[-1])
return s[:-n]

aes = AES.new(aeskey, AES.MODE_CBC, iv)
print(unpad(aes.decrypt(flag)))

The flag is TWCTF{L#B_de#r#pti#n_ora#le_c9630b129769330c9498858830f306d9}.
I need to study the LSB decryption oracle. 🙁

Define Function M: $M(x_0,\ldots,x_{n-1}) = \sum\limits_{i=0}^{n-1} \sum\limits_{j=i}^{n-1} q_{i, j}x_i x_j + \sum\limits_{i=0}^{n-1} u_ix_i + c$. ( $q$ is for quad, $u$ is for uni. Notice that $q_{i,j}=q_{j,i}$)

The code gives $M(input)$ and $M(input + flag)$. Let’s think about $F(x, y)=M(x + y) - M(x)$. $F(x, y)=M(x + y) - M(x) = \sum\limits_{i=0}^{n-1} \sum\limits_{j=i}^{n-1} q_{i, j} (x_i y_j + y_i x_j + y_i y_j) + \sum\limits_{i=0}^{n-1} u_i y_i$

For some integer $k$ that $0 \leq k \leq n-1$, define $x'$: $x'_i = \begin{cases}x_i + 1 (i = k),\\x_i (i \neq k)\end{cases}$

Then, $F(x', y)-F(x, y)=\sum\limits_{i=0}^{k} q_{i, k} y_i + \sum\limits_{j=k}^{n-1} q_{k, j} y_j = q_{k,k} y_k+\sum\limits_{i=0}^{n-1}q_{i, k}y_i (\because q_{i,j}=q_{j,i})$

Note that $q_{k,k}$ appears twice.

Therefore, we can get $n$ linear equations of $flag$ by getting a value of $F(x', flag)-F(x, flag)$ for each $k$, and it’s clear that they are solvable.

So, do the row reduction and get the flag. The code is here:

from pwn import *

r = remote('mq.eatpwnnosleep.com', 12345)

mq_str = r.recvuntil('\n')
mq_var_str = mq_str.replace(' ', '').split('+')

quad = [ [ 0 for _ in range(32) ] for _ in range(32) ]
uni = [ 0 for _ in range(32) ]
c = 0
p = 131

# Parse MQpoly
for var in mq_var_str:
tmp = var.split('x')
if len(tmp) == 1:
c = int(tmp)
elif len(tmp) == 2:
uni[ int(tmp)-1 ] = int(tmp)
else:
x, y, z = int(tmp), int(tmp), int(tmp)

# Get values
def get_value(s):
r.send(s)
tmp = r.recv()
print(tmp[:4])
return (int(tmp[2:4], 16) - int(tmp[:2], 16)) % p

base_input = [ 'a' for _ in range(32) ]
base_value = get_value( ''.join(base_input) )
value = [ 0 for _ in range(32) ]

for i in range(32):
base_input[i] = 'b'
value[i] = get_value( ''.join(base_input) )
value[i] = (value[i] - base_value) % p
base_input[i] = 'a'

print("value:", value)

# Solve (Gauss Elimination)
def xgcd(b, a):
x0, x1, y0, y1 = 1, 0, 0, 1
while a != 0:
q, b, a = b // a, a, b % a
x0, x1 = x1, x0 - q * x1
y0, y1 = y1, y0 - q * y1
return  b, x0, y0

def mulinv(b, n):
g, x, _ = xgcd(b, n)
if g == 1:
return x % n

def swap(i, j):
for k in range(32):

def mult(i, m):
for k in range(32):

value[i] *= m
value[i] %= p

def reduc(i, j, m):
for k in range(32):

value[j] -= value[i] * m
value[j] %= p

for i in range(32):

for i in range(32):
for j in range(i, 32):
break
if i != j:
swap(i, j)

mult(i, pivot_inv)

for j in range(i+1, 32):

for i in range(31, -1, -1):
for j in range(i-1, -1, -1):

print(value)

flag = ''.join([ chr(v) for v in value ])
print(flag)

The flag is SCTF{Try_MQ_be_happy!}.

It is quite simple PRNG with the equation (t = 0xdeadbeef): $x_i = (k_1 - t) x_{i-1} + k_1 t x_{i-2} + k_2 (mod\ k_3)$

We can define $y_i$ as $y_i = x_i + t x_{i-1}$, then $y_i = k_1 y_{i-1} + k_2 (mod\ k_3)$. So, it’s just same as the normal LCG.

I used the method to break LCG described in this link, and the solver is here.

from pwn import *

def xgcd(b, a):
x0, x1, y0, y1 = 1, 0, 0, 1
while a != 0:
q, b, a = b // a, a, b % a
x0, x1 = x1, x0 - q * x1
y0, y1 = y1, y0 - q * y1
return  b, x0, y0

def mulinv(b, n):
g, x, _ = xgcd(b, n)
if g == 1:
return x % n

r = remote('lcg.eatpwnnosleep.com', 12345)
inputs = []

for i in range(16):
r.sendline('1')
inputs.append( int(r.recvuntil('\n')) )

print(inputs)

arr = []

for i in range(15):
arr.append(inputs[i+1] + k*inputs[i])

# http://sandeepmore.com/blog/2012/03/23/breaking-linear-congruential-generator/
def d(i, j):
t1 = arr[i] - arr
t2 = arr[i+1] - arr
t3 = arr[j] - arr
t4 = arr[j+1] - arr

return t1 * t4 - t2 * t3

t = d(2, 3)
for i in range(3, 13):
t, _, _ = xgcd( t, d(i, i+1) )

k3 = t if t > 0 else -t

print("k3: ", k3)

g0_inv = mulinv( (arr - arr) % k3, k3)
k1 = ((arr - arr) * g0_inv) % k3
k2 = (inputs - (k1 - k) * inputs - k1 * k * inputs) % k3

print("k1: ", k1)
print("k2: ", k2)

s0, s1 = inputs[-2], inputs[-1]

for i in range(16):
s0, s1 = s1, ( (k1 - k) * s1 + k1 * k * s0 + k2 ) % k3
r.sendline( str(s1) )

r.interactive()

The flag is SCTF{LCG_is_too_simple_to_be_a_good_CSPRNG}.

At first, let’s define final_state(), which returns the last state of transduce(B, s) for input B.

def transduce(b, s=0):
if len(b) == 0:
return b
d, t = T[s]
b0, bp = b, b[1:]
return [b0 ^ t] + transduce(bp, s=d[b0])

def final_state(b, s=0):
if len(b) == 0:
return s
d, _ = T[s]
b0, bp = b, b[1:]
return transduce_state(bp, s=d[b0])

The problem of breaking the cipher is that there’s swapping action of left 32bit & right 32bit in each stage.

def swap(b):
l = BLOCK_SIZE // 2
m = (1 << l) - 1 return (b >> l) | ((b & m) << l)

class Transducipher:
def __init__(self, k):
self.k = [k]
for i in range(1, len(T)):
k = swap(transduceblock(k))
self.k.append(k)

def encrypt(self, b):
for i in range(len(T)):
b ^= self.k[i]
b = transduceblock(b)
b = swap(b)
return b

Let’s say self.k[i] as Key_i, and block of the each stage as Data_i. (Data_0 is the input of the encrypt() function. The output of the encrypt() function will be Data_6.)
Next, let’s say the left 32bit of block B_i as B_i,0, and the right 32bit as B_i,1.

From Key_i, we can write Key_i+1,0 and Key_i+1,1 like these:

Key_i+1,1 = transduce(Key_i,0, 0)
Key_i+1,0 = transduce(Key_i,1, final_state(Key_i,0, 0) )

From these, we can write out some relations of the Key_i,j blocks which affected by Key_0,0, with some unknown states.

Key_1,1 = transduce(Key_0,0, 0)
Key_2,0 = transduce(Key_1,1, final_state(Key_1,0, 0) )
Key_3,1 = transduce(Key_2,0, 0)
Key_4,0 = transduce(Key_3,1, final_state(Key_3,0, 0) )
Key_5,1 = transduce(Key_4,0, 0)

Also, we can write out relations from Data_0,0.

Data_1,1 = transduce(Data_0,0 ^ Key_0,0, 0)
Data_2,0 = transduce(Data_1,1 ^ Key_1,1, final_state(Data_1,0 ^ Key_1,0, 0) )
Data_3,1 = transduce(Data_2,0Key_2,0, 0)
Data_4,0 = transduce(Data_3,1 ^ Key_3,1, final_state(Data_3,0 ^ Key_3,0, 0) )
Data_5,1 = transduce(Data_4,0Key_4,0, 0)
Data_6,0 = transduce(Data_5,1 ^ Key_5,1, final_state(Data_5,0 ^ Key_5,0, 0) )

The key idea is that, if we just assume the unknown values from  final_state() in these relations, we can get Data_6,0 from Key_0,0 & Data_0,0 immediately. There are five unknown states, so we can assume those states and get 6**5 settings for them.
From this, we can write a backtracking function for finding Key_0,0, from 0th bit to 31st bit.

def transduce_withstate(b, s=0): # Also returns the final state
if len(b) == 0:
return b, s
d, t = T[s]
b0, bp = b, b[1:]

rb, fs = transduce_withstate(bp, s=d[b0])

return [b0 ^ t] + rb, fs

# Backtracking function for first 32 bit of the first key
def backtrack_first32bit(idx, data_in, data_out, key_cand, states, data_num):
a, b, c, d, e = states

# First 32bits are filled
if idx == 32:
key_copy = [k for k in key_cand]
data_copy = data_in[:32]
next_states = []

istates = [ (0, 0), (a, b), (0, 0), (c, d), (0, 0) ]

# Get states for calculating last 32bits of the key
for i in range(5):
i1, i2 = istates[i]
for j in range(32):
data_copy[j] ^= key_copy[j]
key_copy, kstate = transduce_withstate(key_copy, i1)
data_copy, dstate = transduce_withstate(data_copy, i2)

if i%2 == 0:
next_states.append(kstate)
next_states.append(dstate)

# Backtrack for remaining
backtrack_last32bit(0, data_in, data_out, key_cand, next_states, states, data_num)

return

for b0 in range(2): # Test the idx th bit as b0

key_copy = [k for k in key_cand]
key_copy.append(b0)
data_copy = data_in[:idx+1]

# Run the encryption
istates = [ (0, 0), (a, b), (0, 0), (c, d), (0, 0), (0, e) ]

for i1, i2 in istates:
for j in range(idx+1):
data_copy[j] ^= key_copy[j]
key_copy = transduce(key_copy, i1)
data_copy = transduce(data_copy, i2)

# Compare
if data_copy[idx] != data_out[idx]:
continue # Failed

key_copy = [k for k in key_cand]
key_copy.append(b0)
backtrack_first32bit(idx+1, data_in, data_out, key_copy, states, data_num)

# Data of the problem
data = [[13079742441184578626, 15822063786926281121],
...
[10970386673164693022, 12683515533170128309]]

if __name__ == "__main__":
# Change data to binary vector form
for i in range(len(data)):
data[i], data[i] = block2bin(data[i]), block2bin(data[i])

# Test for each datum (total 16 data)
for data_num in range(len(data)):

# Assume five states
for i in range(6**5):
states = [(i // (6**j)) % 6 for j in range (5)]
backtrack_first32bit(0, data[data_num], data[data_num], [], states, data_num)

if i % 100 == 0:
print(data_num, i)

print(data_num, "end")

if data_num > 0:
pos_key.intersection_update(pos_key[data_num])

print(len(pos_key))
if len(pos_key) < 5:
print(pos_key)

After finding candidates of Key_0,0, we can also get candidates of Key_0,1  from Key_0,0. backtrack_last32bit() will do this.
Furthermore, we can re-calculate the five states, which are assumed at first, from Key_0,1. We can compare the value between the assumed ones and the re-calculated ones, and find out whether the assumed setting is right or not.

The key(Key_0) is 11424187353095200769, and the flag is PCTF{9e8adddea4bfe001}.