---
title: "Writeup: M0leCon Teaser CTF 2021 - Left or Right?"
author:
- TorioCrema
date: 2021-05-16
categories:
- writeups
tags:
- writeups
- jeopardy
- misc
- ctf
- m0lecon
---

## Information

* *category* : misc
* *points* : 219

## Description

> nc challs.m0lecon.it 5886

## Writeup

After connecting to the challenge and solving the proof of work we receive the following message:

[Screenshot](https://i.imgur.com/QOootWQ.png)

We have to write an algorithm that can find which sequence of the given strings will result in
the leftmost point reached during the path is as near as possible to 0.

We decided, to use a greedy algorithm, since calculating all possible permutations of the strings
would require too much time and we have a limit of 1 second for each test.

To make sure that our sequence will result in the optimal solution we want to move right as much as
possible before moving to the left, so that when we do move left the strings that result in a left
movement will be countered by the fact that we have already moved right, thus minimizing the overhall
left movement of the whole sequence.

To do so we read each sequence from the output and create a list based on two values: one is the leftmost
position reached during that string, we will call this value `cost`, and the other is the position
reached at the end of the string, we will call this value `pos`.

With these values we can sort the strings and reach an optimal solution. Like we said before we first want
to move right as much as possible, then move left. To do so we sort the strings in increasing order based on
their `cost` value if their `pos` value is positive, meaning that at the end of those strings we will
end up to the right of the starting position and we will move left as little as possible; however if some
strings have a negative `pos` value we will sort those based on the differce between their `cost` and `pos`
value, meaning that the ones with a greater differce will be put first. This is because in case of a negative
`pos` value our ending position will be left of the starting position, if we used the same sorting criteria as
with the positive `pos` value strings we would end up increasing the effective `cost` value of the following strings,
thus obtaining a solution that isn't optimal.

## Exploit

```py
#!/usr/bin/env python3
from pwn import *
from hashlib import sha256

# proof-of-work
def solvepow(p, n):
s = p.recvline()
starting = s.split(b'with ')[1][:10].decode()
s1 = s.split(b'in ')[-1][:n]
i = 0
print("Solving PoW...")
while True:
if sha256((starting+str(i)).encode('ascii')).hexdigest()[-n:] == s1.decode():
print("Solved!")
p.sendline(starting + str(i))
break
i += 1

def solve(l):
v = []
for s in l:
cost = 0
pos = 0
# create list of (cost, pos)
# cost = left-most point reached during string
# pos = position reached at the end of the string
for c in s:
if c == 'L':
pos -= 1
elif c == 'R':
pos += 1
else:
assert False
cost = max(cost, -pos)
v.append((cost, pos))

# sort list based on cost if pos > 0 else based on abs(cost - pos)
v.sort(key=lambda t: (t[1] < 0, t[0] if t[1] >= 0 else -t[0]-t[1]))
print(v)

# calculate left-most point during string sequece
max_cost = 0
pos = 0
for cost, delta in v:
max_cost = max(max_cost, cost - pos)
pos += delta
return max_cost

r = remote('challs.m0lecon.it', 5886)
solvepow(r, n = 5)

r.readuntil('one second for each test.\n')
r.sendline()
for _ in range(200):
n = int(r.readline()) # read number of strings
# create list of strings
l = []
for i in range(n):
l.append(r.readline().decode().strip())

# calculate and send result
ans = solve(l)
print(ans)
r.sendline(str(ans))
print(r.readline())
r.interactive()
```