# Page 2 of 5

Do you wanna air my dirty laundry?

## How to solve

### Recovering PRNG

The challenge uses 256-bit LFSR PRNG, of which seed is the lower 256-bit of 1024-bit prime number.

Let’s see pailler_enc unction.

def paillier_enc(m, p, noise):
p = next_prime(p + noise)
q = getStrongPrime(512)
n = p * q
g = (1 + prng.rand() * n) % n**2
c = pow(g, m, n**2) * pow(prng.rand(), n, n**2) % n**2
return n, g, c

The value p is 1024-bit, so n should be 1536-bit. This means that g = (1 + prng.rand() * n) % n**2 is just same as g = 1 + prng.rand() * n, beacuse prng.rand() is only 256-bit.

So, you can get some prng.rand() values from gs, and then recover the PRNG by reversing the PRNG steps.

class PRNG256(object):
def __init__(self, seed):
self.mask = (1 << 256) - 1

def _pick(self):
b = ((self.seed>>0)^(self.seed>>2)^(self.seed>>5)^(self.seed>>10)^1)&1
return b

def _rev(self):
b = ((self.seed>>255)^(self.seed>>1)^(self.seed>>4)^(self.seed>>9)^1)&1

def rev(self):
for i in range(256):
self._rev()

def rand(self):
x = 0
for i in range(256):
x = (x << 1) | self._pick()
return x

with open('output.txt', 'r') as f:
ln = len("[+] pubkey: ")
pubkeys = eval(lines[1][ln:])
shares = eval(lines[2][ln:])

g1 = (pubkeys[0][1] - 1) // pubkeys[0][0]
g1_rev = int(format(g1, '0256b')[::-1], 2)

prng2 = PRNG256(g1_rev)

prng2.rev()
prng2.rev()

### Recovering msg from ciphertexts

Now we know every prng.rand() values. Then, how can we recover m from c = pow(g, m, n**2) * pow(prng.rand(), n, n**2) % n**2?

First, we know pow(prng.rand(), n, n**2), so we can get pow(g, m, n**2).

About pow(g, m, n**2), let’s use the lemma:

(1+n)^x \equiv 1+nx (\textrm{mod}\ n^2)

and L function from the Paillier cryptosystem. (Check out Background section of the wikipedia article.)

Let’s name the prng.rand() of g = 1 + prng.rand() * n as noise. Then,

g \equiv 1 + n \cdot noise \equiv (1 + n)^{noise} (\textrm{mod}\ n^2)

g^m \equiv (1 + n)^{noise \cdot m} \equiv 1 + n \cdot noise \cdot m (\textrm{mod}\ n^2)

Therefore, if the value of pow(g, m, n**2) is x, we can get m by

L(x) \cdot noise^{-1}\ \textrm{mod}\ n.

# ...
noises = [ [ prng2.rand() for j in range(3) ] for i in range(5) ]

assert all([ noises[i][1] == (pubkeys[i][1] - 1) // pubkeys[i][0] for i in range(5) ])

from Crypto.Util.number import inverse
msgs = []
for i in range(5):
n = pubkeys[i][0]
gm = shares[i][1] * pow(inverse(noises[i][2], n**2), n, n**2) % (n**2)
assert (gm - 1) % n == 0
m = ((gm - 1) // n) * inverse(noises[i][1], n) % n
# Actually the input m of paillier_enc is f(x) + noise.
# Removing noise here
m -= noises[i][0]
msgs.append(m)

### Recovering PRIME and flag

Let’s see the make_shares funciton.

def make_shares(secret, k, shares, prime=PRIME):
PR, x = PolynomialRing(GF(prime), name='x').objgen()
f = PR([secret] + [ZZ.random_element(prime) for _ in range(k-1)])
xy = []
pubkey = []
for x in range(1, shares+1):
noise = prng.rand()
n, g, y = paillier_enc(f(x) + noise, prime, noise)
pubkey.append([n, g])
xy.append([x, y])
return pubkey, xy

We can write f = PR([secret] + [ZZ.random_element(prime) for _ in range(k-1)]) as ax^2 + bx + secret with unknown a, b.

We know the values f(1), f(2), f(3), f(4), f(5), but we still don’t know PRIME value.

To recover PRIME, follow these steps:

f(1) = a + b + secret (\textrm{mod}\ PRIME)
f(2) = 4a + 2b + secret (\textrm{mod}\ PRIME)
f(3) = 9a + 3b + secret (\textrm{mod}\ PRIME)
f(4) = 16a + 4b + secret (\textrm{mod}\ PRIME)
f(5) = 25a + 5b + secret (\textrm{mod}\ PRIME)

f(2) - f(1) = 3a + b (\textrm{mod}\ PRIME)
f(3) - f(2) = 5a + b (\textrm{mod}\ PRIME)
f(4) - f(3) = 7a + b (\textrm{mod}\ PRIME)
f(5) - f(4) = 9a + b (\textrm{mod}\ PRIME)

f(3) - 2f(2) + f(1) = 2a (\textrm{mod}\ PRIME)
f(4) - 2f(3) + f(2) = 2a (\textrm{mod}\ PRIME)
f(5) - 2f(4) + f(3) = 2a (\textrm{mod}\ PRIME)

Those three values should be same in mod PRIME. Let’s see the values.

# ...
diff1 = [msgs[i + 1] - msgs[i] for i in range(4)]
diff2 = [diff1[i + 1] - diff1[i] for i in range(3)]

print(diff2)
[15811421083594511222443737739252635264048880525922585588301936609228995378847100219077025996330637679748201495232713488175501419093889756582141854326794585932757033416010075789093873549925885865427721464977303837867972880212881542442858600772700056257381545416159374874599314719160184896130245018676138377339, 15811421083594511222443737739252635264048880525922585588301936609228995378847100219077025996330637679748201495232713488175501419093889756582141854326794585932757033416010075789093873549925885865427721464977303837867972880212881542442858600772700056257381545416159374874599314719160184896130245018676138377339, -124774146038784351164660695638844469856057176985103369924500484527626445042767085680881218533371013137755309524956122804303169360720687143840617652657883917066736244248204558778941905728536041360624781514852127873619283658133441911094549580928196987208500641692108582717297358074519511405222407995323945125710]

The third value is different from the others. It means the difference between the third and the others is the multiple of PRIME, because it should be same in mod PRIME.

The difference is:

140585567122378862387104433378097105120106057511025955512802421136855440421614185899958244529701650817503511020188836292478670779814576900422759506984678502999493277664214634568035779278461927226052502979829431711487256538346323453537408181700897043465882187108267957591896672793679696301352653014000083503049

and it’s actually a prime number. Therefore, it must be PRIME.

Now we know the value of PRIME, we can decrypt the flag.

Here is the full solver.

from Crypto.Util.number import long_to_bytes, inverse

class PRNG256(object):
def __init__(self, seed):
self.mask = (1 << 256) - 1

def _pick(self):
b = ((self.seed>>0)^(self.seed>>2)^(self.seed>>5)^(self.seed>>10)^1)&1
return b

def _rev(self):
b = ((self.seed>>255)^(self.seed>>1)^(self.seed>>4)^(self.seed>>9)^1)&1

def rev(self):
for i in range(256):
self._rev()

def rand(self):
x = 0
for i in range(256):
x = (x << 1) | self._pick()
return x

with open('output.txt', 'r') as f:
ln = len("[+] pubkey: ")
pubkeys = eval(lines[1][ln:])
shares = eval(lines[2][ln:])

g1 = (pubkeys[0][1] - 1) // pubkeys[0][0]
g1_rev = int(format(g1, '0256b')[::-1], 2)

prng2 = PRNG256(g1_rev)

prng2.rev()
prng2.rev()

noises = [ [ prng2.rand() for j in range(3) ] for i in range(5) ]

assert all([ noises[i][1] == (pubkeys[i][1] - 1) // pubkeys[i][0] for i in range(5) ])

msgs = []
for i in range(5):
n = pubkeys[i][0]
gm = shares[i][1] * pow(inverse(noises[i][2], n**2), n, n**2) % (n**2)
assert (gm - 1) % n == 0
m = ((gm - 1) // n) * inverse(noises[i][1], n) % n
m -= noises[i][0]
msgs.append(m)

diff1 = [msgs[i + 1] - msgs[i] for i in range(4)]
diff2 = [diff1[i + 1] - diff1[i] for i in range(3)]

p = diff2[1] - diff2[2] # It is prime!

a = diff2[0] * inverse(2, p) % p
b = (diff1[0] - 3 * a) % p
secret = (msgs[0] - a - b) % p
print(long_to_bytes(secret))

The flag is zer0pts{excellent_w0rk!y0u_are_a_master_0f_crypt0!!!}.

nc 18.179.178.246 3002
(This was all of the description)

## Overview

FiniteGeneralLinearGroup is just a matrix class over a finite field.
We can encrypt and decrypt arbitrary messages.
Encryption is defined as: Y = UXU^{-1}.
Decryption is defined as: X = U^{-1}YU.
The size of matrix (from the server) is 6×6.

## How to solve

You cannot decrypt the flag directly, because it only accepts the matrix with values in the range 0~255.

Let’s think about (i, j)-th entry of the UXU^{-1}.

(UXU^{-1})_{i, j} = \sum_{i' = 1}^6 \sum_{j'=1}^6 U_{i, i'} X_{i', j'} U^{-1}_{j', j}

If you send the matrix X which has 1 in the (i, j)-th entry and 0 in the others, you can get U_{k, i} U^{-1}_{j, l} values for every (k, l).

Notice that (UXU^{-1})_{i, j} is a linear combination of X_{i', j'} and U_{i, i'} U^{-1}_{j', j}. Because we now know U_{i, i'} U^{-1}_{j', j} values, we can construct the linear system with 36 variables and 36 equations. We can solve the system with sage.

Here’s the extractor code for getting U_{i, i'} U^{-1}_{j', j} values.

from pwn import *
import base64

f = open('data', 'w')

r = remote('13.231.224.102', 3002)
r.recvuntil('Encrypted Flag:\n')

eF = r.recvuntil('p = ')[:-5]
p = r.recvuntil('=')[:-1]

eF = eF.replace('\n', ',') + '\n'
f.write(p + eF)

for i in range(36):
target = b'\x00' * i + b'\x01' + b'\x00' * (35 - i)
target = base64.b64encode(target)
r.sendline('1')
r.sendline(target)
r.recvuntil('Encrypted:\n')
v = r.recvuntil('=')[:-2]
v = v.replace('\n', ',') + '\n'
f.write(v)

f.close()

Here’s the sage solver for the linear system.

from itertools import product as iproduct

# [i][j][i_][j_] = U[i][j] * U**-1[i_][j_]
UUm1_coef = [ [ [ [None for i in range(6)] for j in range(6) ] for k in range(6) ] for l in range(6) ]

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

for i, j in iproduct(range(6), repeat=2):
for i_, j_ in iproduct(range(6), repeat=2):
UUm1_coef[i_][i][j][j_] = mat[i_][j_]

mat = [ [0 for i in range(36)] for j in range(36) ]
vec = [ eF[i // 6][i % 6] for i in range(36) ]

for i, j, i_, j_ in iproduct(range(6), repeat=4):
mat[i * 6 + j][i_ * 6 + j_] += UUm1_coef[i][i_][j_][j]
mat[i * 6 + j][i_ * 6 + j_] %= p

R = IntegerModRing(p)
M = Matrix(R, mat)
b = vector(R, vec)
ans = M.solve_right(b)

flag = ''
for i in range(36):
flag += chr(ans[i])
print(flag)

The flag is zer0pts{r1ng_h0m0m0rph1sm_1s_c00l}.

I made a cipher-signature system by myself.

nc 18.179.178.246 3001

## How to Solve

In the challenge, you can (1) encrypt and sign, (2) verify encrypted message, and (3) get public key. The public key of the server is always fixed.

If you see the verify function of server.py, you can find out that it will let you know the hash of the decrypted message.

        if h == H:
sock.send(b"Signature OK!\n")
else:
sock.send(s2b("Invalid Signature: {:08x} != {:08x}\n".format(h, H)))

Next, let’s see the _hash function of diysig.py.

    def _hash(self, m):
""" DIY Hash Function """
H = 0xcafebabe
M = m
# Stage 1
while M > 0:
H = (((H << 5) + H) + (M & 0xFFFFFFFF)) & 0xFFFFFFFF
M >>= 32
# Stage 2
M = H
while M > 0:
H = ((M & 0xFF) + (H << 6) + (H << 16) - H) & 0xFFFFFFFF
M >>= 8
# Stage 3
H = H | 1 if m & 1 else H & 0xfffffffe
return H

As you can see, Stage 3 leaks LSB of the message. This means you can apply the RSA LSB oracle attack in this challenge.

The solver is here.

from pwn import *
from Crypto.Util.number import inverse

# From the server
enc = 0x3cfa0e6ea76e899f86f9a8b50fd6e76731ca5528d59f074491ef7a6271513b2f202f4777f48a349944746e97b9e8a4521a52c86ef20e9ea354c0261ed7d73fc4ce5002c45e7b0481bb8cbe6ce1f9ef8228351dd7daa13ccc1e3febd11e8df1a99303fd2a2f789772f64cbdb847d6544393e53eee20f3076d6cdb484094ceb5c1
e = 0x10001

div = pow(inverse(2, n), e, n)

flag = ''
m, sur = 0, 0
for i in range(1024):
r = remote('18.179.178.246', 3001)
r.recvuntil('> ')
r.sendline('2')
r.recvuntil('ENC : ')
r.sendline(hex(enc)[2:])
r.recvuntil('SIG : ')
r.sendline('00000000')
r.recvuntil('!= ')
sig = r.recv(8)
r.close()

sig = int(sig, 16) % 2
if sig % 2 == 0:
m |= (sur % 2) << (i % 8)
sur = (sur + (sur % 2)) // 2
else:
m |= (1 - sur % 2) << (i % 8)
sur = (sur + (1 - sur % 2) + n) // 2
enc = enc * div % n

if i % 8 == 7:
if m == 0:
break
flag += chr(m)
m = 0

print(flag[::-1])

The flag is zer0pts{n3v3r_r3v34l_7h3_LSB}.

오늘 부산의 중국비자서비스센터에 다녀왔습니다. 안타깝게도 중국을 다녀오려면 비자가 꼭 필요하더라고요. 0CTF/TCTF 측에서 그래서 초청장을 보내왔습니다.

## 초청장을 갖고 가기 전에…

하나투어 비자센터를 통해서 이 초청장이 괜찮은지 물어봤습니다. 돌다리도 두드려보고 건너라고, 혹시 모르는 마음에 문의를 했습니다. 실제로 비자센터를 통해 비자를 신청할 것은 아니였지만… 미안해요 하나투어!

대사관에 문의를 해봤는데, 초청장 매 페이지마다 도장이 필요하세요.

하나투어 비자센터

초청장이 두 페이지로 이루어져 있는데 마지막 페이지에만 도장이 있었습니다. 주최 측에 문의를 해서 첫 페이지에도 도장을 받았습니다.

이제 부산으로 가기만 하면 될 것만 같습니다.

## 부산에서 비자 신청하기

초청장이 있는 경우 관광 비자로 신청하는 것이 어렵습니다. 저와 LeaveCat-PLUS 팀원은 무역 단기 비자로 신청을 했습니다.

문제는 초청장을 들고 갔더니 직원 분께서 하시는 말씀이,

이 초청장으로는 안 되세요.

부산 중국비자서비스센터 직원

아니, 이게 무슨 청천벽력과 같은 말이람!

중국에 급하게 국제 전화도 걸어보고, (oto 라는 어플리케이션을 사용했습니다. 중국 국제전화가 무료라고 하네요. 하지만 불안해서 사용하고 지웠습니다.) 메일로 고쳐야 할 사항을 보내서 수정을 받아서 무사히 제출에 성공했습니다.

고쳐야 하는 사항은 다음과 같았습니다.

• 초청장의 발급 일자
• 도장 뿐만 아니라, 담당자의 사인

초청장에 필요했던 내용을 요약해보자면 다음과 같겠습니다.

• 초청 받는 사람이 누구인지, 여권 정보 등을 포함해 서술
• 이 사람이 언제 출국하고 언제 돌아오는지
• 초청장을 작성한 일자
• 페이지가 여러 개일 경우, 각 페이지마다 도장 (왜 하필 도장인지 모르겠지만 직원의 말에 따르자면)
• 담당자가 누구인지, 그리고 담당자의 사인
• 중국에서의 경비를 누가 지원하는지
• 등등 …

자비로 갔다오는 거라면 자비로 갔다온다고, 초청한 회사가 담당하면 초청한 회사가 지원한다고 써있어야 한다고 하더군요.

또한 비자 신청서에 회사의 주소와 연락처를 기재해야하는데, 우리가 받은 초청장의 경우 영어 초청장의 주소와 중국 초청장의 주소가 달라 중국 초청장의 주소로 다시 바꿔 적는 일이 있었습니다.
중국어를 적는게 귀찮다면 프린트할 때 미리 쓰거나 종이에 프린트한 것을 오려 붙여도 된다고 하니 참고하세요.

그리고 이 해프닝은 모두 부산에서 있었던 것으로, 서울에서 비자를 신청할 때와 다름에 주의하시기 바랍니다.

혹시 비슷한 일로 초청장을 받아서 갔다온다면 참고가 되었으면 좋겠습니다.

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 [js]src/constraints.ts[/js], you can know there are total 6 constraints and [js]Constraint5[/js] is reversed triangles, and [js]Constraint6[/js] is round-edged rectangle.

By reading [js]problem/common/src/bootstrap.ts[/js], you can see four parameters are passed to [js]fn_assembly/index/checkAll[/js]. (In the code, it is [js]this.module.checkAll[/js].) If [js]checkAll[/js] 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.

[c]checkAll[/c] calls [c]Constraint{i}_check[/c] functions. Let’s see [c]Constraint6_check[/c].
When reading the code, [c]p{i}[/c] is the ith parameter, [c]l{i}[/c] is a local variable, and [c]l{i}[/c] is a temporal variable. Just understand [c]l{i}[/jscas non-volatile registers, and [c]i{i}[/c] 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;
}

[c]L1[/c] and [c]L2[/c] are loop labels. Each uses [c]l5[/c] and [c]l6[/c] 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 [c]array_Constraint[/c].

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.