時間内に解けなかったので供養のために..
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}
ただただなるほどな〜といった感じ。
確か解答してるチーム結構いたので、そこまで難しくなかったようです….