# The most boring

by dp1
April 30, 2018

*******************************************************************************
| hi all, welcome to the most Boring task, but I think its interesting for all|
| Think about a rotating drum, each of the segments is of one of three types, |
| such that any k consecutive segments uniquely determine the position of the |
| drum, example: for k = 3, the circular sequence 111220120210110200100022212 |
| has desired property. In each stage, send us three distinct sequences with  |
| given k, and get the valuable flag :))                                      |
*******************************************************************************


Easy, right? Probably the hardest part was understanding the question. While it doesn’t say it explicitly, the sequences needed to contain all possible subsequences of length k. This means that they had to be de Bruijn sequences. Luckily the Wikipedia page also contains python code to generate those sequences, so by just writing a small wrapper around it I got to the flag. The only missing part was how to generate three different sequences, but it was enough to swap che characters around for them to be different (e.g. 001122 -> 110022)

import itertools, hashlib, sys
from pwn import *

def bruijn(k, n):
alphabet = list(map(str, range(k)))

a = [0] * k * n
sequence = []

def db(t, p):
if t > n:
if n % p == 0:
sequence.extend(a[1:p + 1])
else:
a[t] = a[t - p]
db(t + 1, p)
for j in range(a[t - p] + 1, k):
a[t] = j
db(t + 1, t)
db(1, 1)
return "".join(alphabet[i] for i in sequence)

target = target.strip().split(' ')[-1]
print '[+] Solving captcha for', target
alpha = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'
for a,b,c,d,e in itertools.product(alpha, repeat=5):
if hashlib.sha256(a+b+c+d+e).hexdigest()[-6:] == target:
return a+b+c+d+e
quit()

def solve(line, r):
k = int(line.strip().split(' ')[-1])
print '[+] Solving for k =', k
sol = bruijn(3, k)
r.recvuntil('first sequence:')
r.sendline(sol)
r.recvuntil('second sequence:')
sol = sol.replace('0', 'a').replace('1', '0').replace('a', '1')
r.sendline(sol)
r.recvuntil('third sequence:')
sol = sol.replace('0', 'a').replace('2', '0').replace('a', '2')
r.sendline(sol)

r = remote('37.139.22.174', 56653)

while not s.startswith('Submit'):

while True:
solve(s, r)
while len(s.strip()) == 0:
if 'ASIS' in s:
print s
break


(pwn) dario@PC:~/desktop/ctf/asisquals2018/boring\$ python t.py
[+] Opening connection to 37.139.22.174 on port 56653: Done