IERAE CTF 2024 Writeup - derangement

2024年9月21日〜22日に開催されたIERAE CTF 2024に参加しました。

Crypto

derangement

permutationに変な制限つけないで！の問題。

1. 問題の理解

配布されたファイルを読み、出題サーバは以下の動きをすると理解した。

1. nc経由でアクセスされたら、15文字のランダムに文字を取ってきて、文字列を作る。それをsecretとする。
2. ヒントを教えてとリクエストされたら、secretをpermutationした結果を教えてあげる。ただし、もしもsecretとpermutation結果を比べて、一文字でも同じ場所に同じ文字が来ていたら、permutationし直す。
3. ヒント（permutation結果）はいくらでも教えてあげる。
4. ncの向こう側の人が、secretをわかって入力したら、FLAGを教えてあげる。

つまり、解答者は

1. 文字列に含まれる15文字は、最初のヒントでわかる。
2. secretのk文字目は、 ヒント（permutation結果）でk文字目に来ない文字である。
   と考えて文字列を推定すればよい。

2.解く

1. ヒントを集める。
   ncで出題サーバにつなぎ1、Enterの順にキーボードを叩くと、1個ヒントを出力してくれる。ヒントをたくさんほしいので、たくさん1とEnterを叩く必要がある。
   どうしても自動化できなかったので、teeでファイルに出力しつつ、1とEnterを40回ほど叩いた。

$ nc 104.199.xx.xx 55555 |tee hoge

1. 集めてきたヒントを整形する。gauche scriptで処理する予定なので、文字列のリストにする。

$ rep hint: hoge |awk 'BEGIN{print "(define input-lst ("}{print "\""$3"\""}END{print "))"}' >input.txt

なお、リストにするためのシングルクォートはemacsで手入力した。
その結果、input.txt は次のようになっている。

input.txt

(define input-lst '(
"Uh*c}YVeA<ZNXo{"
...
"Y}{VoUeXZ*<cANh"
))

1. コードを書きながら走らせる
   以下はスクリプトとして走らせるのではなく、emacsで開いて、各行（各S式）でemacs内で走らせた（evalした）。
   推定結果（eval結果）は、emacsの*scheme* bufferに表示される。今回は、ncに手で打ち込めばよいので、単に各位置の文字の候補のリストを表示させた。

(define N 15)
(define cand (string->list (car input-lst)))
(define input
  (map
   string->list input-lst))

(define (iter cand-list it-input)
  (if (null? it-input)
      cand-list
      (iter 
       (map
        (lambda (x y) (remove (lambda (z) (eq? y z)) x))
        cand-list (car it-input))
       (cdr it-input))))
(iter (make-list N cand) input)

1. テストデータを走らせたら、一部の場所（k文字目）で候補が2文字以上残った。しかしながら、他の場所で確定した文字は別の場所には入らないため、それによって（人間の暗算で）、その場所（k文字目）の文字も確定できるのでよいことにした。
   もう一度ncで問題サーバにつないで1とEnter Keyを40回押してコードを走らせて回答を入力したら、FLAGが表示された！

3. 補足

permutationと言ったら、この小説を紹介したい。
グレッグ イーガン著『順列都市』。原題は"Permutation City"。私は大好き。
https://www.amazon.co.jp/%E9%A0%86%E5%88%97%E9%83%BD%E5%B8%82-%E4%B8%8A-%E3%83%8F%E3%83%A4%E3%82%AB%E3%83%AF%E6%96%87%E5%BA%AB-SF-2-1/dp/4150112894