Harekaze mini CTF 2020 write-up - ぶちのブログ

はじめに

Harekaze mini CTF 2020にソロで参加し、5問を解いて141人中28位でした。
非常に面白い問題が多かったです！

運営の皆様ありがとうございました。

f:id:betit0919:20201227105452p:plain

f:id:betit0919:20201227105504p:plain

解けた問題の解法

[Misc warmup] Welcome

説明文にあるHarekazeCTF{4nch0rs_4we1gh}を提出するだけ。

[Misc medium] NM game

NimKの変形みたいな問題。競技プログラマ歓喜。
1-3個までpeddleを取れるので、相手の番のときにすべてのheapの数が4の倍数になっていれば、以下の戦略で勝てる。

相手が取ったheapから、4-(相手が取ったpeddleの個数)個のpeddleを取る。・・・①

つまり、すべてのheapを4の倍数にすることを目的にしてよい。
すべてのheapの数を4で割ったあまりを考えると、そのままNimKに帰着できる。すなわちそれらのxorが0になるように取っていけば良い。戦略は以下の通り。

全てのheapを4で割ったあまりのxorでの畳み込みが0になるようにheapとpeddleの数を選んで取る。・・・②

また、②の戦略が①の戦略を包含していることがわかる。どの山から取ればxorが0になるかは全探索すればよい。

# frozen_string_literal: true

require 'socket'

$sockin = TCPSocket.open('20.48.84.64', '20001')
$sockout = $sockin

def solve(ns)
  ns.length.times do |i|
    # i番目のheapのpeddleをj=1~3個減らしてみる
    (1..3).each do |j|
      # j個減らせない場合
      next if (ns[i] - j).negative?

      ns_copy = ns.dup
            ns_copy[i] -= j
            # 4で割った余りのxorでの畳込みが0であれば良い
      return [i, j] if ns_copy.map { |k| k % 4 }.inject(:^).zero?
    end
  end
end

loop do
  response = $sockin.gets
  puts response
  break if response.nil?
  next unless response =~ /^[0-9]/

  ns = response.split(' ').map(&:to_i)
  if ns.length == 1
    $sockout.write("#{ns[0] % 4}\n")
  else
    ans = solve(ns)
    $sockout.write("#{ans[0]}\n")
    $sockout.write("#{ans[1]}\n")
  end
end

$sockin.close

HarekazeCTF{pe6b1y_qRundY_peb6l35}

[Web warmup] What time is it now?

escapeshellcmdは対になっている'をエスケープしないので、任意のオプションをdateコマンドに渡すことができそう。
format=%27%20--help%27というパラメータを渡し、オプションを眺めると、-fオプションというのが見つかるので、それにflagへのpathを渡す。
format=%27%20-f/flag%27というパラメータを渡すとフラグが出てくる。

HarekazeCTF{1t\'s_7pm_1n_t0ky0}

[Crypto easy] QR

QRコードを01の行列で表したときの、任意の2*2の範囲にある和が与えられている。つまり以下の例のような変換をQRコードに対して行ったものが与えられている。

1 0 0            3 2
1 1 1      =>    3 4
0 1 1

復元する際に、特定の行と列が全てわかっていれば、そこから逆算できる。
QRコードの仕様より、7行目と7列目は確定するので、以下のようなコードを解いた

# frozen_string_literal: true

output = [
  [3, 2, 2, 2, 2, 3, 2, 1, 1, 1, 2, 2, 1, 1, 2, 3, 3, 3, 3, 2, 1, 1, 2, 3, 2, 2, 3, 2, 2, 2, 2, 3],
  [2, 1, 2, 2, 1, 2, 2, 0, 1, 2, 2, 3, 3, 1, 0, 2, 0, 0, 3, 2, 2, 1, 1, 3, 2, 2, 2, 1, 2, 2, 1, 2],
  [2, 2, 0, 0, 2, 2, 2, 1, 2, 3, 3, 3, 3, 2, 2, 2, 2, 3, 3, 2, 2, 2, 3, 0, 2, 2, 2, 2, 0, 0, 2, 2],
  [2, 2, 0, 0, 2, 2, 2, 2, 3, 3, 3, 3, 2, 2, 3, 1, 1, 3, 3, 3, 2, 2, 0, 0, 2, 2, 2, 2, 0, 0, 2, 2],
  [2, 1, 2, 2, 1, 2, 2, 2, 0, 0, 2, 2, 3, 3, 2, 1, 2, 3, 3, 3, 2, 1, 2, 3, 2, 2, 2, 1, 2, 2, 1, 2],
  [3, 2, 2, 2, 2, 3, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 2, 2, 3, 3, 2, 1, 1, 2, 2, 2, 3, 2, 2, 2, 2, 3],
  [2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 1, 1, 1, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3, 2, 1, 2, 2, 2, 2, 2, 2],
  [1, 0, 0, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 1, 2, 2, 3, 3, 2, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 0, 1],
  [2, 1, 0, 1, 2, 2, 2, 3, 3, 2, 1, 2, 3, 2, 2, 2, 3, 3, 2, 2, 1, 2, 3, 2, 3, 3, 3, 3, 2, 2, 1, 1],
  [3, 3, 2, 2, 3, 3, 1, 1, 3, 3, 1, 2, 3, 1, 2, 3, 3, 0, 2, 1, 2, 3, 0, 3, 2, 2, 3, 2, 0, 1, 1, 0],
  [2, 3, 0, 0, 0, 3, 1, 0, 2, 2, 1, 3, 2, 1, 2, 1, 2, 0, 3, 3, 0, 3, 2, 2, 2, 2, 3, 2, 0, 0, 1, 1],
  [0, 2, 3, 2, 3, 3, 2, 2, 2, 1, 2, 3, 2, 3, 3, 1, 2, 0, 0, 0, 0, 3, 2, 1, 2, 3, 2, 2, 2, 1, 2, 3],
  [0, 2, 3, 2, 3, 3, 3, 3, 2, 2, 2, 1, 1, 2, 2, 2, 3, 3, 2, 2, 3, 0, 0, 3, 2, 2, 2, 2, 2, 2, 3, 3],
  [0, 2, 0, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 2, 3, 2, 1, 1, 2, 2, 3, 0, 3, 1, 1, 1, 0, 2, 0, 2],
  [1, 3, 0, 3, 2, 2, 2, 3, 3, 1, 1, 3, 0, 0, 2, 1, 2, 2, 2, 3, 3, 1, 1, 2, 3, 2, 0, 0, 0, 1, 2, 1],
  [3, 3, 3, 0, 3, 2, 1, 2, 3, 1, 0, 1, 3, 0, 3, 2, 3, 2, 1, 2, 3, 3, 1, 0, 1, 2, 2, 2, 1, 0, 1, 1],
  [3, 2, 2, 3, 0, 3, 2, 3, 3, 2, 2, 1, 2, 3, 2, 3, 3, 2, 1, 1, 3, 0, 3, 1, 1, 3, 0, 3, 1, 1, 2, 1],
  [3, 2, 2, 2, 2, 2, 3, 0, 2, 1, 3, 2, 1, 2, 2, 3, 3, 3, 2, 2, 0, 0, 0, 2, 2, 3, 2, 2, 2, 3, 2, 0],
  [0, 2, 1, 2, 1, 1, 3, 0, 2, 0, 1, 2, 2, 3, 3, 3, 0, 3, 2, 3, 0, 3, 2, 2, 3, 2, 1, 3, 3, 2, 2, 1],
  [3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 2, 3, 2, 1, 3, 2, 1, 2, 2, 2, 1, 1, 2, 2, 3, 3, 1, 0, 2, 3],
  [3, 3, 2, 1, 2, 3, 2, 2, 2, 3, 3, 2, 1, 1, 1, 0, 2, 3, 2, 1, 1, 3, 3, 2, 1, 2, 0, 2, 1, 1, 2, 0],
  [2, 2, 1, 0, 2, 3, 3, 3, 2, 3, 0, 3, 1, 0, 1, 1, 1, 2, 2, 1, 2, 0, 0, 3, 1, 1, 2, 1, 2, 3, 3, 3],
  [0, 2, 3, 2, 2, 2, 3, 2, 0, 2, 3, 1, 0, 1, 3, 2, 1, 2, 2, 2, 3, 3, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2],
  [2, 3, 0, 3, 1, 1, 2, 2, 1, 2, 2, 1, 2, 2, 3, 3, 2, 2, 2, 2, 3, 2, 0, 1, 3, 0, 0, 0, 2, 0, 1, 2],
  [2, 2, 2, 1, 0, 1, 1, 2, 2, 2, 2, 1, 3, 2, 2, 0, 3, 1, 1, 1, 2, 3, 1, 2, 3, 2, 2, 3, 3, 2, 2, 1],
  [2, 2, 2, 2, 2, 2, 1, 2, 3, 2, 1, 0, 1, 1, 2, 3, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 2, 3, 2, 1, 0],
  [3, 2, 2, 2, 2, 3, 2, 1, 2, 1, 0, 0, 1, 2, 3, 3, 2, 2, 1, 2, 3, 1, 1, 3, 2, 1, 1, 2, 2, 0, 0, 0],
  [2, 1, 2, 2, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 3, 0, 2, 1, 3, 0, 3, 1, 2, 3, 2, 2, 3, 2, 0, 0, 1],
  [2, 2, 0, 0, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 3, 0, 3, 2, 2, 2, 2, 1, 2, 3, 3, 3, 3, 3, 2, 1, 1],
  [2, 2, 0, 0, 2, 2, 2, 0, 2, 2, 0, 1, 2, 2, 3, 0, 3, 3, 2, 1, 2, 2, 1, 1, 2, 2, 1, 2, 3, 3, 2, 0],
  [2, 1, 2, 2, 1, 2, 2, 0, 2, 2, 0, 2, 3, 2, 3, 3, 2, 3, 2, 1, 3, 0, 2, 1, 3, 3, 1, 1, 2, 2, 1, 0],
  [3, 2, 2, 2, 2, 3, 2, 1, 2, 2, 1, 1, 2, 3, 3, 2, 3, 3, 1, 0, 2, 0, 3, 3, 3, 2, 1, 1, 3, 2, 0, 1]
]

ans = 33.times.map { [nil] * 33 }
# 7行目と7列目を埋めておく
ans[6] = [1] * 7 + [0, 1] * 9 + [0] + [1] * 7
ans = ans.transpose
ans[6] = [1] * 7 + [0, 1] * 9 + [0] + [1] * 7

loop do
  32.times do |i|
    32.times do |j|
      a = ans[i][j]
      b = ans[i][j + 1]
      c = ans[i + 1][j]
      d = ans[i + 1][j + 1]
      next if [a, b, c, d].count(&:nil?) != 1

      # 2*2の範囲で1箇所だけ未知という状態ならば、その未知の値を逆算できる
      ans[i][j] = (output[i][j] - b - c - d) % 4 if a.nil?
      ans[i][j + 1] = (output[i][j] - a - c - d) % 4 if b.nil?
      ans[i + 1][j] = (output[i][j] - a - b - d) % 4 if c.nil?
      ans[i + 1][j + 1] = (output[i][j] - a - b - c) % 4 if d.nil?
    end
  end
  break if ans.all?(&:all?)
end

# 出力部分
require 'chunky_png'

png = ChunkyPNG::Image.new(33, 33)
33.times do |i|
  33.times do |j|
    png[i, j] = ChunkyPNG::Color(ans[i][j] == 1 ? 'black' : 'white')
  end
end
png.save('qr.png')

出力されたpngを読み取るとHarekazeCTF{d0_y0u_7hink_qr_ch4113ng3_i5_r3411y_in_d3m4nd}と出てくる。

[Reversing easy] Wait

まず実行するのが少し大変だった。

docker run --rm -it -v $PWD:/tmp ubuntu:18.04
apt update && apt install libssl1.0.0

とすれば実行できる。

フラグが^HarekazeCTF\{ID[A-Z]{4}X\}$という形式であることを教えてもらえるが、検証の際に1秒ほど待たされる。単純な全探索を行おうとすると、26⁴秒 ~ 5日ほどかかるので、並列化する必要がある。

シェルのバックグラウンド実行で簡単に並列化した。(実行するとlogs以下に大量のファイルが出力されるので注意)

#!/bin/sh -eux

mkdir -p logs

for a in A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
do
for b in A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
do
for c in A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
do
for d in A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
do
  (echo HarekazeCTF\{ID${a}${b}${c}${d}X\} | ./a.out > logs/${a}${b}${c}${d}) & 
done
done
done
done

出力されたlogファイルから、correctという文字列を探すと見つかる。(ちょっとエスパー)

grep correct -ril logs
logs/RACI

なので、フラグはHarekazeCTF{IDRACIX}。

感想

あまり時間がとれなかったのもあるが、個人的にはもう少し解きたかったなという感想。
一人だとどうしても勉強のモチベが保てないので、チームとかに入ってちゃんと勉強していこうか悩み中。。。