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 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, [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-th 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. Download

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)