Challenge

O(n) でソートしてください！

import secrets, os

FLAG = os.getenv("FLAG", "Alpaca{REDACTED}")

def swap(xs: list[int], i: int, j: int):
    if i == j:
        return
    xs[i] ^= xs[j]
    xs[j] ^= xs[i]
    xs[i] ^= xs[j]

def sort_challenge(xs: list[int]) -> bool:
    limit = len(xs) + 5
    for _ in range(limit):
        i = int(input("i> "))
        j = int(input("j> "))

        print(f"xs[i]: {xs[i]} -> {xs[j]}")
        print(f"xs[j]: {xs[j]} -> {xs[i]}")
        swap(xs, i, j)

        is_sorted = all(x <= y for x, y in zip(xs, xs[1:]))
        print(f"{is_sorted = }")
        if is_sorted:
            return True
    return False

for size in [10, 100, 1000, 2000]:
    print(f"{size = }")
    xs = [secrets.randbelow(2**32) for _ in range(size)]

    if not sort_challenge(xs):
        print("Challenge failed...")
        exit(0)

print("Congratulations! Here's your flag:", FLAG)

Solution

長さが10,100,1000,2000で要素が2^32内でランダムな配列が用意されます。

インデックスを2つ入力すると、その要素2つを表示し、xorを使ったswapが行われます。

swap後に昇順になっていればフラグを獲得できます。

このswap操作は配列の長さ+5回チャレンジ可能です。

単純に試そうとすると、すべての表示にn/2, 並べ替えに最悪n-1回かかってしまい、n+5だと足りなそうです。

そこで何かしらのバグを探します。

今回は入れ替えにxor swapを使っており、これは同じインデックスを指定すると、その値を0にしてしまいます。

一見 if i == j: return で弾いているように見えますが、インデックスに負数を入れることで、同じ要素を指すことができます。

なのですべての要素にこれを実行すれば、すべて0となり、昇順扱いとなって成功します。

Final Script

from pwn import *

HOST = "34.170.146.252"
PORT = 43373

sizes = [10, 100, 1000, 2000]

r = remote(HOST, PORT)

lines = []
for n in sizes:
    for k in range(n):
        lines.append(str(k))       # i
        lines.append(str(k - n))   # j  (負の添字で同一要素を指す)

payload = "\\n".join(lines) + "\\n"
r.send(payload.encode())

out = r.recvall(timeout=5)
print(out.decode(errors="replace"))

CTFで時々有用なテクニックになりますが、payloadに\\nを含めて複数入力をまとめて与えてやれば高速化できます。