ぺんぎんさんのおうち

日記です。たまに日記じゃないこともあります。

CSAW CTF Qualification Round 2017 [Another Xor]

時間内に解けなかったので供養のために..

Ph03nix Team: [CSAW_Qualification_2017] Another Xor

参考にさせていただきました。

日本語訳して僕の解釈を入れただけになりますがご容赦ください。

まず問題は、

2つの引数(key, flag)を取り、flag + keyを結合したものに更にmd5(flag + key)を結合したものを keyをn回繰り返したもの(文字数は調整されている)とXORとるようになってました。

文章だとわかりにくいので数式っぽく書くと

enc = 
flag + key + md5( flag + key)
xor
key + key + key + ...

ここでFLAGの最初の5文字は flag{ になることがわかってるので、enc[:5] xor 'flag{' すると
A qua が得られました。

次に、keyが何回繰り返されているかを確かめるためにmd5ハッシュ化されたenc[-32:]を見てやる必要があります。大会中の僕は、どうせxorとったところでflagもkeyもわからないし意味ないだろうと思ってました。

def check_md5(enc):
    for i, ch in enumerate(enc):
      print(i+105),
      for j in xrange(33, 127):
        if chr(j ^ ord(ch)) in '1234567890abcdef': # char(s) used by md5
          print(chr(j)),
      print

総当たりで見ていって、A qa が順に現れる部分を探します。するとenc[134]だけに A がいました。 135, 136にもそれぞれq があるので、 KEY を key の繰り返しとすると

KEY == key * n + 'A q'

になります。

次は flag と key の文字数と key の繰り返し回数 n を決定します。
key は 1 回以上の繰り返し回数nを持ち、len(key*n) が 137からA qを引いた134文字より多くなってはいけないので、現在わかっているflagの5文字を合わせると

5 < len(key) < 134
1 < n < 26 ( floor( 134 / 5 ) )
len(key * n) == 134

の条件が成り立つようにそれぞれ求めればいいことになります。 これを満たす n は 2 なので、key は 67[文字]、 flag は 105-67 で 38[文字]となります。

ということは、

flag + key = "flag{" + "_"*33 + "A qua" + "_"*62
KEY = "A qua" + "_"*62 + "A qua" + "_"*62 + "A q"

これでKEYを復元しつつ、flagを得ることができます。

solverです

plain='flag{' + '_'*(38-5) + 'A qua' + '_'*(67-5)
key='A qua' + '_'*(67-5) + 'A qua' + '_'*(67-5) + 'A q'

cipher = open("encrypted").read()
cipher = cipher.decode("hex")

prev = ''
while prev != plain:
  prev = plain
  plain=list(plain)
  key=list(key)

  for i in xrange(len(plain)):
    if plain[i] == '_' and key[i] != '_':
      plain[i] = chr(ord(cipher[i]) ^ ord(key[i]))
    if plain[i] != '_' and key[i] == '_':
      key[i] = chr(ord(cipher[i]) ^ ord(plain[i]))

  plain = ''.join(plain)
  key = ''.join(key)

  print(plain)
  key = plain[38:]*2 + 'A q'

print(plain[:38])

FLAG : flag{sti11_us3_da_x0r_for_my_s3cratz}

ただただなるほどな〜といった感じ。
確か解答してるチーム結構いたので、そこまで難しくなかったようです….