카테고리: Write-up (Page 1 of 3)

Write-up을 업로드합니다.

[zer0pts CTF 2020] dirty laundry

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
        self.seed = seed & self.mask

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

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

    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: ")
    lines = f.readlines()
    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
        self.seed = seed & self.mask

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

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

    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: ")
    lines = f.readlines()
    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!!!}.

[zer0pts CTF 2020] nibelung

nc 18.179.178.246 3002
(This was all of the description)


Overview

From the organizer’s write-up(Link):

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:
    p = int(f.readline()[:-1])
    eF = eval(f.readline()[:-1])

    for i, j in iproduct(range(6), repeat=2):
        mat = eval(f.readline()[:-1])
        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}.

[zer0pts CTF 2020] diysig

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
n = 0x6d70b5a586fcc4135f0c590e470c8d6758ce47ce88263ff4d4cf49163457c71e944e9da2b20c2ccb0936360f12c07df7e7e80cd1f38f2c449aad8adaa5c6e3d51f15878f456ceee4f61547302960d9d6a5bdfad136ed0eb7691358d36ae93aeb300c260e512faefe5cc0f41c546b959082b4714f05339621b225608da849c30f
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}.

[PlaidCTF 2019] The .Wat ness

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.
Also, teammate imnotkind helped in downloading resources and reversing typescript files!

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.

Circles, a strange round-edged rectangle, and blue blocks

But what are those?

We need to figure them out…

Reversing

Download all resources via Save All Resources.

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);
        i0 = i32_load((&memory), (u64)(i0));
        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.

The flag is [c]pctf{what_if_i_made_firmament_instead}[/c].

BTW, I solved all the puzzles in the Witness.

[PlaidCTF 2019] Plaid Party Planning III

Plaid Party Planning III 1

Other teammates solved this one. You can get a flag easily by just jumping into the 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 [c]sleep[/c] 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, [4]), (0, 1, [2, 4]), (4, 2, [0]), (4, 1, [0, 2]), (2, 1, [0, 4]), (4, 3, [2]), (2, 3, [4]), (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]), (2, 3, [1]), (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]), (3, 2, [1])],
    [(0, 2, []), (2, 1, []), (3, 4, [])],
    [(3, 1, []), (3, 4, []), (0, 2, []), (2, 1, [])],
    [(1, 3, []), (1, 2, [3]), (3, 2, [1]), (3, 0, [])],
    [(4, 1, []), (4, 2, [1]), (1, 2, [4]), (2, 1, []), (0, 1, []), (0, 2, [1]), (1, 2, [0])],
    [(0, 1, []), (1, 2, []), (1, 3, [2]), (2, 3, [1]), (1, 3, [])],
    [(0, 2, []), (2, 1, []), (0, 4, [])],
    [(3, 1, []), (3, 2, [1]), (1, 2, [])],
]

Each row means each person’s lock pairs. (A, B, [C]) means the person has (Lock from A-th row → Lock from B-th row) routine in its behavior functions, with gate locks [C_1-th 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][0])
        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 `i`th person and `j`th 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] == 1:
            continue
        
        for u in range(idx + 1, 15):
            check[u][i] += 1
        for (u, v) in deadlocks[idx][i]:
            check[u][v] += 1
        
        ans.append(i)
        backtrack(idx + 1)
        ans.pop()

        for u in range(idx + 1, 15):
            check[u][i] -= 1
        for (u, v) in deadlocks[idx][i]:
            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, [4]), (0, 1, [2, 4]), (4, 2, [0]), (4, 1, [0, 2]), (2, 1, [0, 4]), (4, 3, [2]), (2, 3, [4]), (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]), (2, 3, [1]), (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]), (3, 2, [1])],
    [(0, 2, []), (2, 1, []), (3, 4, [])],
    [(3, 1, []), (3, 4, []), (0, 2, []), (2, 1, [])],
    [(1, 3, []), (1, 2, [3]), (3, 2, [1]), (3, 0, [])],
    [(4, 1, []), (4, 2, [1]), (1, 2, [4]), (2, 1, []), (0, 1, []), (0, 2, [1]), (1, 2, [0])],
    [(0, 1, []), (1, 2, []), (1, 3, [2]), (2, 3, [1]), (1, 3, [])],
    [(0, 2, []), (2, 1, []), (0, 4, [])],
    [(3, 1, []), (3, 2, [1]), (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][0])
        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)

# 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 `i`th person and `j`th 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) )

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] == 1:
            continue
        
        for u in range(idx + 1, 15):
            check[u][i] += 1
        for (u, v) in deadlocks[idx][i]:
            check[u][v] += 1
        
        ans.append(i)
        backtrack(idx + 1)
        ans.pop()

        for u in range(idx + 1, 15):
            check[u][i] -= 1
        for (u, v) in deadlocks[idx][i]:
            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 do not satisfy the second routine above, but I’m not sure :P)


« Older posts

© 2020 RBTree.insert()

Theme by Anders NorenUp ↑