nullcon HackIM Write-up
はじめに
2020/02/01 ~ 2019/02/03に開催されたHackTM CTFにチーム(NekochanNano!)で参加しました．
成績
チームとしては3問解いて160位でした (1208チーム中)．
今回は自分が解いた1問のWrite-upを書きます．
Crypto
RockPaperScissors
To get the flag you have to beat us in rock paper scissors but to make it fair we used a commitment based scheme.
nc crypto1.ctf.nullcon.net 5000
rps.py
#!/usr/bin/env python3 from Crypto import Random from Crypto.Random import random from Crypto.Util.number import * from secret import flag sbox = [221, 229, 120, 8, 119, 143, 33, 79, 22, 93, 239, 118, 130, 12, 63, 207, 90, 240, 199, 20, 181, 4, 139, 98, 78, 32, 94, 108, 100, 223, 1, 173, 220, 238, 217, 152, 62, 121, 117, 132, 2, 55, 125, 6, 34, 201, 254, 0, 228, 48, 250, 193, 147, 248, 89, 127, 174, 210, 57, 38, 216, 225, 43, 15, 142, 66, 70, 177, 237, 169, 67, 192, 30, 236, 131, 158, 136, 159, 9, 148, 103, 179, 141, 11, 46, 234, 36, 18, 191, 52, 231, 23, 88, 145, 101, 17, 74, 44, 122, 75, 235, 175, 54, 40, 27, 109, 73, 202, 129, 215, 83, 186, 7, 163, 29, 115, 243, 13, 105, 184, 68, 124, 189, 39, 140, 138, 165, 219, 161, 150, 59, 233, 208, 226, 176, 144, 113, 146, 19, 224, 111, 126, 222, 178, 47, 252, 99, 87, 134, 249, 69, 198, 164, 203, 194, 170, 26, 137, 204, 157, 180, 168, 162, 56, 81, 253, 213, 45, 21, 58, 24, 171, 37, 82, 53, 50, 84, 196, 232, 242, 244, 64, 80, 10, 114, 212, 187, 205, 28, 51, 182, 16, 107, 245, 211, 85, 92, 195, 5, 197, 200, 31, 183, 61, 123, 86, 167, 154, 41, 151, 35, 247, 246, 153, 95, 206, 149, 76, 112, 71, 230, 106, 188, 172, 241, 72, 156, 49, 14, 214, 155, 110, 102, 116, 128, 160, 135, 104, 77, 91, 190, 60, 42, 185, 96, 97, 251, 218, 133, 209, 65, 227, 3, 166, 255, 25] p = [5, 9, 1, 8, 3, 11, 0, 12, 7, 4, 14, 13, 10, 15, 6, 2] round = 16 def pad(data, size = 16): pad_byte = (size - len(data) % size) % size data = data + bytearray([pad_byte]) * pad_byte return data def repeated_xor(p, k): return bytearray([p[i] ^ k[i % len(k)] for i in range(len(p))]) def bytes_to_int(xbytes): return bytes_to_long(xbytes) def int_to_bytes(x): return long_to_bytes(x, 16) def group(input, size = 16): return [input[i * size: (i + 1) * size] for i in range(len(input) // size)] def hash(data): state = bytearray([208, 151, 71, 15, 101, 206, 50, 225, 223, 14, 14, 106, 22, 40, 20, 2]) data = pad(data, 16) data = group(data) for roundkey in data: for _ in range(round): state = repeated_xor(state, roundkey) for i in range(len(state)): state[i] = sbox[state[i]] temp = bytearray(16) for i in range(len(state)): temp[p[i]] = state[i] state = temp return hex(bytes_to_int(state))[2:] def gen_commitments(): secret = bytearray(Random.get_random_bytes(16)) rc = hash(secret + b"r") pc = hash(secret + b"p") sc = hash(secret + b"s") secret = hex(bytes_to_int(secret))[2:] rps = [("r", rc), ("p", pc), ("s", sc)] random.shuffle(rps) return secret, rps def check_win(a, b): if a == "r": if b == "p": return True else: return False elif a == "s": if b == "r": return True else: return False elif a == "p": if b == "s": return True else: return False return False def main(): print("Beat me in Rock Paper Scissors 20 consecutive times to get the flag") for i in range(20): secret, rps = gen_commitments() move = rps[0][0] print("Here are the possible commitments, the first one is my move:", " ".join(map(lambda s: s[1], rps))) inp = input("Your move:") res = check_win(move, inp) print("My move was:", move, "Secret was:", secret) if not res: print("You lose!") exit(0) print("You win") print("Your reward is", flag) exit(0) if __name__ == '__main__': main()
> nc crypto1.ctf.nullcon.net 5000 Beat me in Rock Paper Scissors 20 consecutive times to get the flag Here are the possible commitments, the first one is my move: fce244bcbc04700b41826ca483c023f9 d81237fe4e8bed3cf9e7a92291675454 5cb149b74cb5c739082c3775a885fac4 Your move:r My move was: s Secret was: 28351b948c17fb2b1604602c0423c693 Here are the possible commitments, the first one is my move: d33f53586f3061727da1ba5153d069be 3aabc6c958fa1ff562d6fe5ef57e6493 cd42da2f16c1173e39d196f8edf8becf Your move:r My move was: p Secret was: 101e48d532eec3d49f3df1386a52d14a You lose!
アプローチ：hash()の逆関数を書いてstateを求める
rps.pyの処理を簡単にまとめると以下のようになります．
- 16byteの
secretを生成 secret + r,secret + p,secret + sそれぞれのハッシュ値を生成stateの初期化- 入力データを16の倍数にpadding
- padding済みデータを16byteに分割
roundkey(16byteに分割されたpadding済みデータ) ごとにstateに対するxor, 置換, 転置を16round繰り返すroundkeyとstateのxorを計算sbox(substitution box) によってstateを置換pによってstateを転置
- 最後に
stateをハッシュ値としてreturn
hash(secret + r),hash(secret + p),hash(secret + s)をシャッフル- シャッフル結果を出力
- シャッフル結果の先頭に勝てる
moveを入力 (r,pors) - 20連勝するとflag
以上のことから，この問題では出力されたハッシュ値からmoveを特定する必要があることが分かります．
そのためには，hash()の逆関数を作成し，roundkeyをsecretとしたときのstateを求める必要があります．
roundkeyをsecretとしたときのstateは，2つめのroundkey (入力データの17byteから32byte)がpad(), group()によって[move]\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0fになることを利用して求めることができます．
つまり，全てのハッシュ値に対してroundkeyをr\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f, p\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f, s\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0fとしたときのstateを求め，
全てのハッシュ値に共通するstateを見つけることで，そのハッシュ値がどのmoveから生成されたものなのかを特定できます．
以下ソルバになります（汚い）
from Crypto import Random from Crypto.Random import random from Crypto.Util.number import * from socket import * rev_sbox = [47, 30, 40, 252, 21, 198, 43, 112, 3, 78, 183, 83, 13, 117, 228, 63, 191, 95, 87, 138, 19, 168, 8, 91, 170, 255, 156, 104, 188, 114, 72, 201, 25, 6, 44, 210, 86, 172, 59, 123, 103, 208, 242, 62, 97, 167, 84, 144, 49, 227, 175, 189, 89, 174, 102, 41, 163, 58, 169, 130, 241, 203, 36, 14, 181, 250, 65, 70, 120, 150, 66, 219, 225, 106, 96, 99, 217, 238, 24, 7, 182, 164, 173, 110, 176, 195, 205, 147, 92, 54, 16, 239, 196, 9, 26, 214, 244, 245, 23, 146, 28, 94, 232, 80, 237, 118, 221, 192, 27, 105, 231, 140, 218, 136, 184, 115, 233, 38, 11, 4, 2, 37, 98, 204, 121, 42, 141, 55, 234, 108, 12, 74, 39, 248, 148, 236, 76, 157, 125, 22, 124, 82, 64, 5, 135, 93, 137, 52, 79, 216, 129, 209, 35, 213, 207, 230, 226, 159, 75, 77, 235, 128, 162, 113, 152, 126, 253, 206, 161, 69, 155, 171, 223, 31, 56, 101, 134, 67, 143, 81, 160, 20, 190, 202, 119, 243, 111, 186, 222, 122, 240, 88, 71, 51, 154, 197, 177, 199, 151, 18, 200, 45, 107, 153, 158, 187, 215, 15, 132, 249, 57, 194, 185, 166, 229, 109, 60, 34, 247, 127, 32, 0, 142, 29, 139, 61, 133, 251, 48, 1, 220, 90, 178, 131, 85, 100, 73, 68, 33, 10, 17, 224, 179, 116, 180, 193, 212, 211, 53, 149, 50, 246, 145, 165, 46, 254] rev_p = [6, 2, 15, 4, 9, 0, 14, 8, 3, 1, 12, 5, 7, 11, 10, 13] round = 16 def pad(data, size = 16): pad_byte = (size - len(data) % size) % size data = data + bytearray([pad_byte]) * pad_byte return data def group(input, size = 16): return [input[i * size: (i + 1) * size] for i in range(len(input) // size)] def repeated_xor(p, k): return bytearray([p[i] ^ k[i % len(k)] for i in range(len(p))]) def rev_hash(rps_hash): while len(rps_hash) < 32: rps_hash = '0' + rps_hash r = b'r\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f' p = b'p\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f' s = b's\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f' roundkeys = [r, p, s] states = [] for roundkey in roundkeys: state = bytearray([int(rps_hash[i:i+2],16) for i in range(0,len(rps_hash),2)]) for _ in range(round): temp = bytearray(16) for i in range(len(state)): temp[rev_p[i]] = state[i] state = temp for i in range(len(state)): state[i] = rev_sbox[state[i]] state = repeated_xor(state,roundkey) # print(state) states.append(state) return states sock = socket(AF_INET, SOCK_STREAM) sock.connect(('crypto1.ctf.nullcon.net', 5000)) for _ in range(21): rec = sock.recv(1024).decode('utf-8') print(rec) commitments = rec.split('\n')[1].split(': ')[1].split(' ') rev_hash_result = [] for commitment in commitments: rev_hash_result.append(rev_hash(commitment)) ans = [1 if x in rev_hash_result[1] and x in rev_hash_result[2] else 0 for x in rev_hash_result[0]] if ans == [1, 0, 0]: sock.send(b'p\n') elif ans == [0, 1, 0]: sock.send(b's\n') else: sock.send(b'r\n')
hackim20{b4d_pr1mitiv3_beats_all!1!_7f65}
まとめ
- 何もわからなかった
- ayyMessage(Crypto), SecureLinearFunctionEvaluation(Crypto), returminator(Rev)解きたかった…
