Accessible Sesamum Indicum | IrisCTF2024

#IrisCTF2024

#!/usr/bin/env python3

import random

MAX_DIGITS = 65536

def vault() -> bool:

    pin = "".join([random.choice("0123456789abcdef") for _ in range(4)])
    digits = ["z", "z", "z", "z"]
    counter = 0

    print("What is the 4-digit PIN?")

    while True:

        attempt = list(input("Attempt> "))

        for _ in range(len(attempt)):

            digits.insert(0, attempt.pop())
            digits.pop()

            if "".join(digits) == pin:
                return True

            counter += 1
            if counter > MAX_DIGITS:
                return False

    return False

def main():

    print("You're burgling a safehouse one night (as you often do) when you run into a")
    print("vault. The vault is protected by a 16-digit pad for a 4-digit PIN. The")
    print("safehouse is guarded by an alarm system and if you're not careful, it'll go")
    print("off, which is no good for you. After this, there are 15 more vaults.\n")

    for n in range(16):

        print(f"You've made it to vault #{n+1}.\n")

        print("|---|---|---|---|")
        print("| 0 | 1 | 2 | 3 |")
        print("|---|---|---|---|")
        print("|---|---|---|---|")
        print("| 4 | 5 | 6 | 7 |")
        print("|---|---|---|---|")
        print("|---|---|---|---|")
        print("| 8 | 9 | a | b |")
        print("|---|---|---|---|")
        print("|---|---|---|---|")
        print("| c | d | e | f |")
        print("|---|---|---|---|\n")

        if not vault():
            print("The alarm goes off and you're forced to flee. Maybe next time!")
            return
        print("You've defeated this vault.")

    print("You unlock the vault and find the flag.\n")
    with open("flag.txt", "r") as f:
        print(f.read(), end="")

if __name__ == "__main__":
    main()

4桁の pin を当てるのを16回できたらOK

attemptは左からところてん式に値を詰めていく感じで、65536回マッチが走る間に当てる必要がある
要するに、 0-f までの値を65530個横に並べたとき、連続する4個の並びが $15^4$ 通りの組み合わせをすべて含んでいればよい
人間には難しいのでChatGPTに解いてもらいたい

De Bruijn Sequence がそれらしい

> pythonで0-9とa-fの15個の文字を扱っています。これらの文字から4種類を選んで並べたときの組み合わせがすべて登場するような文字列を生成できますか

15文字（0-9とa-f）から4種類を選び、それらを並べてすべての組み合わせが登場するような文字列を生成する問題は、デ・ブラウィン列（De Bruijn sequence）の生成問題として知られています。デ・ブラウィン列は、与えられたアルファベットの集合に対して、そのアルファベットのすべての可能な部分列を、その列の中でちょうど一度ずつ含むような環状の文字列です。

この場合、アルファベットは {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f} の16文字で、部分列の長さは4です。デ・ブラウィン列を生成するアルゴリズムは複数存在しますが、一般的には効率的なアルゴリズムの一つはリンカーン算法（Lyndon word algorithm）です。

このアルゴリズムを使って、求められる文字列を生成してみましょう。

生成された文字列は、15個の文字（0-9とa-f）から4つを選んで並べたすべての組み合わせを含む65,536文字の長さです。この文字列は、すべての可能な4文字の部分列を一度だけ含んでいます。これはデ・ブラウィン列の一例であり、この特定の問題に対する解決策を提供します。

De Bruijn Sequenceを生成するコードはCopilotに書いてもらった
```python from ptrlib import Socket

def de_bruijn(alphabet, n): """ de_bruijn(alphabet, n) """ k = len(alphabet) 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)

seq = de_bruijn("0123456789abcdef", 4)

sock = Socket("nc accessible-sesasum-indicum.chal.irisc.tf 10104")

for _ in range(16): sock.sendlineafter("Attempt> ", seq) sock.interactive()

```