yoggy's diary

◆ CODEGATE2010 CTF Level 3の解き方

Level 3はサーバに接続すると暗号化されたデータが送られてきて、 そのデータの中から答となるキーの文字列を取り出す問題でした。 問題は以下のような感じです。

credentials: ctf3.codegate.org port 20909

Julianor doesn't understand why block ciphers exist, too complex.. just use his super secure message service.

指定されたサーバに接続すると、16進数の文字列を送り返してきます。

 $ nc ctf3.codegate.org 20909
 Message To:?
 a <-適当に文字を入力
 e5 2f 79 9d 01 e6 6e a4
 4a df b9 b9 4b d7 b1 d0
 d9 98 4a 40 55 d2 e9 93
 ea 1c 2b 5d 8f 0c 94 e1
 72 91 3a 9b 41 a0 a2 2a
 bf 22 ce c1 fc 49 da 5b
 2d 62 b0 9d bf 63 0b 95
 df 37 0f 7b 95 8d b2 aa
 75 a5 e6 2c 01 df 96 84
 8e 54 2b 8f 29 fc f0

もう少し長いデータを送ると、それに応じてデータが長くなります。

 $ nc ctf3.codegate.org 20909
 Message To:?
 aa <-適当に文字を入力
 e5 2f 79 9d 6a e6 20 85
 4e cc eb da 5c c5 d7 a0
 e5 95 52 5c 42 8c cf c0
 dc 06 2c 0f c9 06 99 e7
 35 d8 20 d2 5b c2 8c 29
 b3 2a fa dd d6 50 c2 56
 3a 63 fe ee a2 71 15 89
 f3 36 12 78 8c 96 a1 bf
 68 a3 e7 48 01 f8 96 a3
 c8 55 4c 8f 31 e0 d4 21

いろいろ試行錯誤した結果、次の仮定を考えて問題に取り組みました。

(1) 暗号化される前のデータはFig.1のようなフォーマットであると仮定

• Fig.1

(2) 単純にXORを使って暗号化している

encryption_data = (header + input_text + secret_text) xor key

(3) XORに使用している鍵は、毎回同じ

(4) XORに使用している鍵は、かなり長い

暗号化に使用している鍵が毎回同じということと、XORの演算は片方が0だと、

 0 xor 0 -> 0
 0 xor 1 -> 1

と、もう片方の値がそのまま出力されることを利用して、 Fig.2のように十分に長い\x00が続くデータを入力すると、 encryption_dataのinput_textに対応する部分にそのまま暗号化に使用した 鍵が出力されると考えました。

• Fig.2

試してみると、\x00だとサーバ側の読み込みが先頭で終わってしまうようだったので、 実際には\xffが続くデータを入力して、出力結果の0/1を反転させることで、 暗号化に使用している鍵を得ることができました。

問題を解くコード(Ruby)

#!/usr/bin/ruby
require 'socket'
require 'pp'

def dump(buf)
  puts "========"
  buf.each_with_index {|b, i|
    puts if i % 8 == 0 && i != 0
    #print "#{b.to_s(16)} "
    print sprintf("%02x ", b)
  }
  puts
  $stdout.flush
end

def get(str)
  s = TCPSocket.new("ctf3.codegate.org", 20909)
  s.gets
  sleep 0.2
  s.print "#{str}\n"
  sleep 0.2

  buf = []
  loop do
    l = s.gets
    break if l == nil
    buf += l.chomp.split(" ").map{|h| h.hex}
  end

  buf
end

# 0x00を送ると、サーバ側でreadが終わってしまうので、
# 0xffを突っ込んであとから戻す作戦
null = "\xff"

# get key data
# 0xffを突っ込んで、5～79バイトの部分の鍵を取り出す。
key = get(null * 100)
key = key[4, key.size-1]
key = key.map {|b| b ^0xff} # 0xffで鍵を取り出しているので、もとに戻す
dump key

# get encryption data
# 1文字だけ文字を入力。かえってくるデータの5～79バイト目が暗号化されたデータ
src = get(null * 1)
src = src[4, src.size-1]
dump src

# decode (XOR)
i = 0
dst = src.map{|s|
  d = s ^ key[i]
  i += 1
  d
}

# print decode data
pp dst.map{|c| c.chr}.join

実行結果

$ ./prob3.rb
========
0b ec 2a c1 2b ad 99 fa
1f 91 91 80 b5 f9 33 25
27 fe e3 ca 85 69 59 7d
e9 60 f5 86 52 f8 49 a1
61 e2 ce 45 dc 49 91 82
95 39 b2 3e 5f 11 8d d3
ec 22 54 d6 b0 59 7c 0b
fc ff d3 de 1c ca 88 26
0b f2 bb 8e c2 19 01 a5
1b d2 fa 2b b2 38 c7 be
66 91 82 97 22 5b 4e 37
d4 cb 7a 2f 6c 20 74 96
33 2d 92 86 58 2e d9 9b
d5 5b c8 3e ff 18 6f ac
db 59 89 ef 03 ed a1 d5
57 be fe e9 71 40 ba 83
de 3c a4 31 bf 0f 2e c2
8a 3a 63 83 b0 da d3 15
88 b2 6e bf e1 a8 93 fc
8a 59 4d 8a 4b 4a 5e 2b
fb a7 04 24 d4 82 e3 87
a3 5b 69 b7 f2 b0
========
01 e6 6e a4 4a df b9 b9
4b d7 b1 d0 d9 98 4a 40
55 d2 e9 93 ea 1c 2b 5d
8f 0c 94 e1 72 91 3a 9b
41 a0 a2 2a bf 22 ce c1
fc 49 da 5b 2d 62 b0 9d
bf 63 0b 95 df 37 0f 7b
95 8d b2 aa 75 a5 e6 2c
01 df 96 84 8e 54 2b 8f
29 fc f0
"\n\nDear CTF Player,\nYour flag is: Block_Ciphers=NSA_Conspiration\n\n--\nLM**2.\n"

最後に出力される"Block_Ciphers=NSA_Conspiration"が問題の答えとなるキーです。