この大会は2021/1/24 2:00(JST)～2021/1/31 2:00(JST)に開催されました。
今回もチームで参戦。結果は 5755点で286チーム中64位でした。
自分で解けた問題をWriteupとして書いておきます。
sanity check (blockchain)
https://remix.ethereum.org/を利用する。GoogleChromeの拡張プラグイン「MetaMask」を使用して、Rinkebyを設定する。chall.solの内容をそのまま貼り付け、コンパイルする。
「Deploy & run transactions」タブに移動し、以下を実行すると、フラグが表示された。
・[At Address]の箇所に「0x5CDd53b4dFe8AE92d73F40894C67c1a6da82032d」を入力し、[At Address]をクリックする。 ・[welcome]ボタンをクリックする。
flag{1t_1s_jus7_th3_st@rt}
optimizer (misc)
$ nc 207.180.200.166 9660 you will be given a number of problems give me the least number of moves to solve them level 1: tower of hanoi [54, 11, 58, 10, 30, 44, 6, 13, 27, 3, 34, 12, 49, 50, 28, 6, 55, 54, 39, 5, 18, 17, 31, 58, 43, 49, 53, 11, 57, 50, 48, 47, 23, 21, 58, 29, 10, 33, 45, 57, 30, 8, 25, 35, 8, 3, 44, 16, 6, 31, 43, 29, 9, 61, 41, 26, 6, 20, 46] > 1 wrong, the answer is 576460752303423487 $ nc 207.180.200.166 9660 you will be given a number of problems give me the least number of moves to solve them level 1: tower of hanoi [47, 47, 2, 53, 9, 3, 52, 13, 56, 45, 45, 54, 57, 39, 47, 52, 5, 63, 32, 53, 40, 49] > 1 wrong, the answer is 4194303
tower of hanoiについて調べる。https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94を見ると、最小回数は2**n-1であることがわかる。
level 2 : merge sort, give me the count of inversions [33, 23, 5, 24, 49, 36, 5, 16, 5, 57, 18, 32, 48, 15, 2, 43, 60, 37, 56, 7, 46, 48, 61, 58, 22, 9, 28, 25, 34, 40, 24, 14, 2, 3, 39, 43, 52, 42, 63, 42, 34, 23, 6, 20, 63, 61, 53, 55, 28, 38, 1, 36, 44, 1, 46, 25, 56, 2, 39, 21, 41, 4, 56, 30, 52, 7, 12, 14, 29, 3, 41, 25, 12, 60, 27, 20, 9, 4, 29, 9, 23, 45, 22, 52] > 1 wrong, the answer is 1797 level 2 : merge sort, give me the count of inversions [33, 13, 41, 45, 49, 16, 10, 52, 42, 9, 62, 9, 4, 9, 30, 33, 16, 34, 23, 37, 36, 57, 44, 34, 12, 42, 33, 55, 6, 25] > 1 wrong, the answer is 207
https://www.geeksforgeeks.org/counting-inversions/を参考に、マージソートのinversion回数を答えていくスクリプトを組む。
import socket def recvuntil(s, tail): data = '' while True: if tail in data: return data data += s.recv(1) def get_inv_count(arr, n): inv_count = 0 for i in range(n): for j in range(i + 1, n): if (arr[i] > arr[j]): inv_count += 1 return inv_count s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('45.134.3.200', 9660)) data = recvuntil(s, '\n').rstrip() print data #### level 1 #### data = recvuntil(s, '\n').rstrip() print data for i in range(25): print 'Round %d' % (i + 1) data = recvuntil(s, '\n').rstrip() print data n = len(eval(data)) ans = str(2**n - 1) data = recvuntil(s, '> ') print data + ans s.sendall(ans + '\n') #### level 2 #### data = recvuntil(s, '\n').rstrip() print data for i in range(25): print 'Round %d' % (i + 1) data = recvuntil(s, '\n').rstrip() print data arr = eval(data) ans = str(get_inv_count(arr, len(arr))) data = recvuntil(s, '> ') print data + ans s.sendall(ans + '\n') data = recvuntil(s, '\n').rstrip() print data
実行結果は以下の通り。
you will be given a number of problems give me the least number of moves to solve them
level 1: tower of hanoi
Round 1
[22, 44, 3, 11, 16, 42, 40, 41, 54, 45, 4, 21, 45, 45, 34, 56, 3, 44, 45, 22, 58, 17, 6, 22, 21, 8, 32, 50, 30, 28, 59, 6, 38, 39, 28, 60, 20, 2, 21, 31, 5, 10, 40, 55, 6, 48, 11, 50, 61, 43, 15, 2, 35, 47, 35, 48, 29, 60, 34, 12]
> 1152921504606846975
Round 2
[28, 8, 13, 55, 19, 36, 50, 40, 35, 45, 36, 59, 31, 24, 22, 44]
> 65535
Round 3
[15, 35, 32, 14, 41, 42, 58, 20, 29, 22, 20, 17, 58, 43, 25, 15, 14, 58, 10, 21, 54, 44, 25, 52, 15, 11, 43, 47, 45, 14]
> 1073741823
Round 4
[51, 35, 36, 8, 5, 36, 38, 43, 23, 35, 42, 64, 31, 48, 61, 17, 13, 14, 52, 25, 2, 23, 42, 32, 24, 49, 48, 10, 40, 59, 42, 37, 23, 49, 35, 21, 45, 21, 1, 5, 63, 57, 32, 29, 9, 3, 16, 64, 47, 49]
> 1125899906842623
Round 5
[35, 39, 28, 9, 42, 17, 32, 41, 55, 49, 27, 36, 56, 57, 17, 41, 21, 2, 6, 15, 48, 38, 18, 27, 53, 35, 42, 61, 26, 26, 12, 6, 44, 57, 33, 23, 32, 39, 16, 41, 31, 3, 21, 42, 43, 31, 44, 30, 16, 46, 4, 53, 18, 8, 29, 29]
> 72057594037927935
Round 6
[43, 48, 29, 52, 61, 12, 12, 46, 14, 15, 14, 33, 49, 7, 16, 63, 19, 58, 35, 3, 48, 58, 4, 18, 38, 57]
> 67108863
Round 7
[22, 61, 58, 48, 23, 36, 57, 26, 6, 17, 25, 38, 41, 61]
> 16383
Round 8
[31, 61, 17, 55, 27, 56, 22, 11, 27, 38, 50, 19, 42, 46, 24, 23, 64, 6, 20, 9, 50, 48, 33, 31, 41, 30, 51, 40, 61, 38, 20, 19, 50, 63, 28, 6, 57, 13, 4, 46, 4, 51, 61, 27, 49, 30, 10, 20, 4, 24, 12, 50, 39, 57, 24, 14, 55, 54]
> 288230376151711743
Round 9
[46, 1, 10, 43, 38, 23, 7, 9, 5, 35, 44]
> 2047
Round 10
[56, 36, 19, 47, 57, 57, 43, 52, 37, 21, 42, 47, 34, 47, 46, 49]
> 65535
Round 11
[63, 57, 1, 49, 50, 61, 1, 14, 60, 23, 20, 50, 23, 63, 31, 55, 9, 12, 40, 16, 52, 39, 42, 43, 56, 30, 44, 44, 41, 41, 15, 25, 10, 6, 26, 33, 55, 47, 58, 33]
> 1099511627775
Round 12
[3, 33, 33, 28, 41, 32, 51, 12, 27, 18, 57, 48, 58, 6, 57, 23, 13, 45, 3, 31, 41, 18, 38, 55, 13, 12, 49, 6, 11, 57, 16, 64, 9, 64, 23, 60, 14, 51, 8, 28, 50, 6, 8, 61, 13, 49, 42, 51, 23, 48, 51, 62, 60, 12, 9, 30, 54, 42, 49, 57, 23, 14]
> 4611686018427387903
Round 13
[23, 27, 19, 53, 37, 27, 14, 28, 28, 6, 56, 58, 64, 41, 32, 22]
> 65535
Round 14
[36, 48, 55, 61, 35, 33, 2, 24, 3, 13, 54, 26, 59, 12, 20, 35]
> 65535
Round 15
[38, 56, 64, 28, 27, 10, 9, 46, 9, 21, 48, 62, 5, 9, 43, 59, 15, 10, 25, 48, 50, 41, 46, 57, 61, 17, 17, 28, 46, 32, 35, 50, 27, 17, 28, 7, 27, 20, 21, 64, 37, 23, 48, 44, 8, 64, 60, 16]
> 281474976710655
Round 16
[42, 22, 49, 26, 40, 12, 58, 49, 30, 40, 47, 33, 2, 52, 13, 23, 58, 33, 46, 30, 41, 29, 19, 22, 53, 22, 37, 12, 51, 33, 46, 3, 14, 30, 52, 63, 25]
> 137438953471
Round 17
[25, 20, 21, 23, 24, 56, 8, 11, 24, 35, 36, 37, 46, 19, 48, 15, 17, 41, 53, 34, 63, 32, 3, 19, 8, 11, 12, 7, 53, 50, 17, 31, 4, 60, 23, 5, 62, 25, 22, 12, 48, 43, 12, 51, 15, 30, 34, 14, 49, 60, 18, 19, 59, 17, 55, 39, 58]
> 144115188075855871
Round 18
[54, 52, 15, 48, 24, 37, 43, 52, 8, 23, 51, 41, 37, 15, 63, 24, 52, 6, 64, 32, 31, 53, 2, 9, 37, 60, 11, 11, 23, 5, 16, 26, 43, 25, 26, 29, 31, 14, 33, 8, 51, 4, 14, 20, 45]
> 35184372088831
Round 19
[37, 2, 50, 44, 17]
> 31
Round 20
[31, 21, 55, 51, 46, 7, 60, 22, 46, 32, 55, 58, 15, 1, 7, 16, 48, 44, 13, 57]
> 1048575
Round 21
[32, 54, 43, 3, 11, 6, 22, 17, 11, 8, 16, 37, 46, 42, 10, 1, 9, 33, 8, 56, 35, 12, 22, 17, 28, 32, 15, 17, 20, 54, 62, 29, 36, 50, 24, 44, 19, 51]
> 274877906943
Round 22
[64, 23, 42, 28, 18, 63, 22, 22, 12, 25, 54, 6, 32, 24, 53, 1, 36, 38, 12, 5, 50, 19, 19, 29, 15, 56, 26, 22, 62, 56]
> 1073741823
Round 23
[3, 25, 57, 3, 39, 58, 25, 59, 15, 23, 35, 52, 26, 53, 7, 38, 4, 50, 54, 6, 52, 53, 8, 54, 4, 34, 53, 31, 49, 12, 4, 6, 8, 12, 5, 7, 4, 61, 32, 51, 46, 19, 50, 25, 44]
> 35184372088831
Round 24
[48, 61, 7, 48, 57, 26, 59, 57, 56, 3, 21, 7, 39, 21, 27, 52, 14, 9, 9, 14, 54, 14, 24, 13, 59, 47, 27, 23, 32, 54, 57, 37, 23, 42, 39, 39, 25]
> 137438953471
Round 25
[22, 37, 38, 24, 2, 11, 46, 54, 10, 27, 54, 23, 38, 12, 19, 27, 49, 23, 55, 59, 41, 19, 7, 16, 55, 39, 43, 54, 13, 34, 14, 8, 60, 36, 27, 37, 61, 33, 29, 13, 18, 8, 18, 35, 57, 52, 15, 45]
> 281474976710655
level 2 : merge sort, give me the count of inversions
Round 1
[55, 55, 31, 4, 39, 12, 63, 44, 60, 23, 18, 4, 3, 51, 34, 37, 38, 13, 3, 36, 11, 61, 43, 17, 36, 53, 63, 4, 34, 27, 1, 64, 35, 3, 10, 41, 35, 20, 35, 11, 29, 8, 37, 28, 34, 43, 17, 13, 34, 39, 28, 17, 57, 47, 7, 33, 63, 35, 25, 2, 26, 39, 3, 60, 22, 36, 35, 16, 34, 44, 33, 3, 1, 39, 28, 37, 44, 10, 56, 36, 8, 49, 24, 44, 33, 11, 15, 35, 60, 15, 31, 50, 39, 1, 27, 33, 61, 46, 18, 18, 31, 34, 48, 10, 64, 33, 47, 36, 39, 51, 43, 59, 17, 13, 12, 36, 35, 40, 6, 28, 7, 20, 46, 10, 8, 55, 32, 36, 20, 14, 11, 40, 61, 54, 28, 61, 20, 25, 52, 17, 39, 50, 15, 4, 2, 58, 60, 5, 33, 15, 54, 36, 26, 27, 9, 34, 61, 60]
> 5960
Round 2
[10, 41, 56, 64, 39, 28, 33, 14, 58, 54, 56, 44, 31, 63, 39, 58, 20, 22, 9, 38, 64, 64, 7, 61, 15, 33, 30, 62, 38, 45, 34, 43, 13, 31, 46, 25, 54, 45, 32, 60, 58, 49, 17, 14, 2, 7, 64, 54, 20, 27, 59, 28, 50, 53, 6, 14, 6, 52, 24, 56, 8, 6, 58, 41, 49, 48, 44, 42, 15, 49, 28, 25, 43, 24, 61, 54, 16, 43, 4, 7, 32, 8, 54, 35, 8, 47, 32, 31, 42, 48, 45, 19, 28, 2, 64, 22, 9, 44, 16, 25, 55, 43, 46, 28, 39, 17, 28, 11, 58, 7, 8, 13, 19, 3, 22, 59, 36, 37, 2, 44, 1, 53, 11, 18, 39, 45, 1, 44, 10, 41, 62, 62, 2, 45, 8, 56, 56, 28, 54, 31, 33, 10, 19, 27, 10, 3, 55, 52, 15, 58, 6, 28, 34, 56, 17, 39, 19, 50, 4, 10, 41, 2, 35, 33, 15, 9]
> 7708
Round 3
[60, 39, 47, 61, 3, 54, 47, 29, 31, 38, 30, 17, 15, 34, 52, 46, 50, 31, 24, 31, 2, 63, 40, 7, 44, 25, 37, 4, 32, 38]
> 258
Round 4
[64, 23, 40, 10, 28, 16, 47, 18, 57, 52, 11, 1, 14, 14, 31, 17, 8, 24, 4, 51, 9, 13, 21, 24, 52, 10, 29, 27, 48, 18, 39, 29, 20, 41, 64, 34, 13, 41, 7, 28, 61, 11, 11, 37, 11, 25, 32, 26, 35, 14, 3, 25, 31, 11, 22, 46, 56, 60]
> 765
Round 5
[1, 16, 53, 46, 46, 49, 45, 35, 58, 36, 64, 31, 13, 50, 47, 60, 11, 26, 6, 5, 27, 7, 16, 15, 11, 35, 31, 10, 42, 46, 18, 13, 10, 64, 48, 25, 58, 53, 4, 26, 11, 19, 56, 47, 2, 5, 53, 46, 23, 40, 54, 16, 55, 3, 5, 54, 32, 9, 11, 35, 28, 38, 50, 57, 38, 9, 6, 29, 2, 8, 54, 29, 18, 47, 11, 9, 11, 53, 9, 11, 55, 60, 61, 10, 40, 47, 49, 42, 57, 31, 3, 17, 3, 64, 2, 18, 53, 44, 7, 64, 6, 1, 38, 53, 58, 36, 36, 17, 17, 52, 54, 61, 2, 26, 50, 2, 57, 63, 35, 55, 47, 11, 17, 21, 46, 15, 38, 1, 17, 31, 55, 7, 42, 50, 24, 4, 61, 31, 26, 57, 21, 3, 11, 39, 13, 11, 24, 23, 19, 14]
> 5620
Round 6
[57, 46, 63, 34, 1, 60, 53, 55, 23, 3, 26, 31, 61, 53, 19, 47, 26, 11, 39, 57, 13, 28, 43, 51, 51, 12, 40, 27, 21, 18, 47, 57, 3, 39, 21, 63, 60, 63, 43, 50, 3, 28, 41, 47, 4]
> 517
Round 7
[30, 8, 40, 2, 43, 42, 60, 30, 56, 25, 46, 19, 19, 7, 10, 39, 42, 9, 14, 34, 4, 4, 29, 41, 53, 7, 7, 10, 6, 3, 6, 31, 38, 57, 51, 62, 26, 1, 24, 25, 48, 44, 41, 41, 57, 63, 36, 29, 34, 31, 19, 60, 18, 49, 27, 20, 49, 2, 48, 12, 33, 4, 15, 36, 44, 35, 27, 5, 60, 4, 33, 49, 63, 56, 20, 54, 5, 31, 18, 42, 38, 49, 62, 10, 52, 11, 27, 56, 19, 52, 38, 38, 55, 36, 63, 38, 36, 43, 43, 8, 29, 31, 60, 45, 43, 6, 9, 31, 53, 52, 8, 35, 18, 6, 14, 23, 64, 51, 25, 52, 33, 9, 42, 7, 55, 40, 58, 21, 12, 45, 50, 23, 58, 50, 38, 49, 14, 61, 9, 26, 57, 45, 50, 6, 48, 50, 59, 40, 9, 32, 56, 39, 3, 37, 48, 16, 31, 49, 63, 44, 34]
> 5578
Round 8
[56, 26, 9, 42, 36, 35, 4, 13, 49, 44, 20, 16, 17, 36, 38, 32, 2, 14, 5, 21, 23, 56, 30, 55, 35]
> 148
Round 9
[13, 35, 12, 3, 27, 51, 37, 56, 49, 31, 36, 38, 30, 25, 10, 19, 11, 39, 43, 23, 15, 16, 5, 24, 49, 20, 13, 54, 58, 38, 44, 22, 32, 32, 63, 14, 27, 12, 24, 39, 39, 56, 15, 24, 47, 6, 47, 17, 33, 36, 21, 41, 3, 42, 27, 63, 44, 64, 38, 56, 1, 59, 39, 38, 19, 14, 8, 24, 28, 45, 2, 15, 63, 41, 6, 52, 36, 45, 62, 55, 46, 9, 22, 23, 32, 63, 35, 57, 51, 26, 43, 24, 40, 13, 21, 50, 5, 18, 51, 37, 57, 23, 37, 16, 4, 13, 11, 19, 60, 37, 21, 11, 56, 36, 28, 57, 5, 24, 35, 26, 2, 18, 21, 61, 64, 44, 18, 49, 20, 36, 17, 6, 1, 29, 17, 61]
> 4558
Round 10
[14, 11, 30, 54, 20, 28, 27, 56, 33, 12, 32, 62, 8, 50, 53, 10, 52, 57, 1, 20, 57, 22, 6, 23, 10, 54, 54, 23, 56, 18, 19, 5, 49, 15, 10, 6, 24, 15, 36, 61, 57, 6, 3, 9, 22, 6, 22, 1, 5, 44, 14, 7, 62, 64, 22, 6, 16, 55, 52, 22, 27, 46, 35, 6, 22, 51, 18, 53, 13, 35, 4, 15, 33, 45, 51, 64, 55, 36, 62, 13, 10, 42, 35, 35, 53, 32, 4, 61, 27, 44, 45, 38, 34, 46, 25, 10, 15, 44, 20, 21, 43, 48, 9, 59, 24, 55, 21, 55, 3, 7, 29, 43, 49, 35, 1, 26, 18, 18, 37, 44, 20, 18, 40, 30, 23, 61, 30, 42, 25, 46, 31, 64, 13, 13, 9, 39, 45, 10, 34, 38, 18, 34, 3, 35, 43, 32, 39, 32, 45, 30, 62, 62, 35, 53, 26, 63, 15, 44, 43, 23, 21, 61, 51, 48, 1, 56, 8, 34, 55, 27, 39, 36, 25, 49, 31, 24, 3, 31, 51, 22]
> 7321
Round 11
[53, 40, 61, 1, 64, 1, 46, 4, 2, 26, 63, 34, 39, 42, 43, 47, 25, 10, 10, 60, 8, 33, 46, 41, 61, 32, 18, 21, 40, 25, 59, 63, 57, 64, 64, 2, 40, 58, 55, 46, 14, 36, 31, 53, 8, 12, 42, 4, 57, 45, 32, 26, 38, 18, 25, 50, 46, 21, 45, 11, 43, 48, 57]
> 945
Round 12
[29, 17, 64, 26, 7, 7, 34, 58, 10, 2, 43, 17, 45, 29, 1, 25, 34, 49, 25, 14, 45, 45, 41, 48, 56, 15, 45, 63, 64, 51, 10, 24, 21, 19, 17, 11, 33, 56, 24, 17, 38, 9, 39, 29, 17, 35]
> 491
Round 13
[8, 33, 9, 36, 28, 44, 42, 5, 54, 50, 24, 64, 62, 7, 27, 24, 25, 26, 5, 18, 36, 63, 5, 8, 56, 56, 19, 58, 2, 15, 49, 30, 16, 58, 24, 3, 53, 6, 9, 6, 16, 5, 29, 61, 3, 28, 17, 31, 25, 45, 17, 29, 14, 33, 57, 21, 44, 38, 32, 41, 52, 7, 14, 55, 54, 4, 26, 50, 63, 3, 40, 45, 41, 25, 20, 49]
> 1341
Round 14
[52, 8, 19, 19, 51, 4, 29, 14, 43, 51, 30, 34, 10, 59, 57, 19, 42, 57, 27, 52, 27, 24, 28, 52, 25, 15, 25, 43, 10, 7, 30, 42, 22, 39, 59, 25, 37, 1, 33, 10, 30, 62, 61, 50, 48, 42, 1, 34, 22, 25, 18]
> 625
Round 15
[12, 34, 11, 16, 64, 62, 23, 41, 29, 48, 50, 40, 49, 13, 62, 41, 57, 4, 11, 28, 61, 31, 9, 63, 50, 12, 50, 7, 54, 20, 34, 4, 24, 34, 4, 14, 15, 1, 45, 52, 23, 49, 33, 34, 31, 7, 47, 20, 30, 44, 20, 38, 40, 5, 7, 13, 60, 56, 24, 41, 23, 34, 36, 43, 44, 62, 5, 50, 19, 60, 43, 50, 3, 1, 37, 54, 52, 49, 56, 47, 12, 10, 60, 38, 34, 23, 2, 21, 4, 59, 20, 13, 64, 23, 46, 10, 9, 36, 16, 7, 35, 23, 3, 60, 46, 60, 41, 59, 36, 18, 14, 25, 1, 38, 19, 28, 45, 22, 25, 39, 26, 2, 25, 40, 11, 55, 47, 29, 5, 62, 24, 52, 36, 41, 25, 5, 2, 57, 40, 1, 50, 12, 55, 48, 61, 64, 9, 57, 16, 63, 61, 11, 50, 27, 36, 35, 33, 23, 41, 10, 34, 23, 20, 19, 11, 22, 39, 9, 50, 43, 36, 14, 24, 52, 12, 20, 17, 30, 50, 27, 15, 39, 21, 63, 59, 31, 17, 3, 47, 57, 7, 24, 28, 23, 12, 1, 8, 56, 39]
> 10013
Round 16
[29, 30, 41, 55, 30, 55, 37, 59, 30, 10, 50, 4, 21, 45, 41, 45, 27, 39, 62, 5, 44, 62, 30, 17, 62, 59, 49, 33, 26, 37, 9, 10, 36, 45, 5, 30, 30, 40, 41, 5, 1, 6, 58, 3, 53, 62, 61, 49, 5, 13, 37, 64, 8, 27, 39, 24, 22, 7, 28, 1, 28, 52, 55, 3, 30, 20, 7, 40, 51, 32, 4, 50, 54, 25, 10, 55, 61, 12, 21, 39, 64, 35, 3, 38, 4, 40, 36]
> 1977
Round 17
[49, 7, 6, 18, 11, 28, 37, 10, 52, 20, 44, 56, 64, 34, 9, 2, 53, 55, 54, 42, 37, 53, 16, 27, 43, 39, 50, 59, 19, 34, 41, 35, 52, 3, 25, 49, 29, 63, 18, 60, 17, 31, 34, 23, 9, 38, 10, 45, 15, 59, 63, 3, 20, 10, 31, 60, 37, 54, 28, 47, 45, 5, 57, 8, 41, 52, 29, 29, 54, 1]
> 1175
Round 18
[17, 2, 46, 54, 31, 22, 33, 61, 15, 58, 37, 39, 26, 12, 64, 31, 61, 2, 35, 24, 45, 40, 62, 63, 60, 44, 44, 41, 48, 14, 53, 11, 18, 22, 62, 40, 30, 13, 2, 53, 41, 54, 10, 24, 62, 21, 12, 31, 31, 6, 55, 44, 37, 62, 38, 27, 20, 12, 63, 19, 42, 20, 42, 57, 64, 55, 56, 12, 23, 63, 20, 56, 15, 50, 36, 52, 29, 43, 61, 37, 16, 5, 25, 21, 11, 48, 58, 28, 40, 54, 32, 34, 36, 33, 6, 63, 24, 37, 13, 8, 35, 57, 13, 2, 53, 42, 18, 41, 39, 45, 28, 32, 39, 27, 8, 33, 12, 12, 41, 2, 40, 17, 20, 28, 60, 43, 48, 6, 45, 56, 38, 51, 59, 56, 13, 47, 34, 60, 45, 21, 1, 1, 40, 24]
> 5313
Round 19
[53, 33, 20, 50, 38, 29, 27, 51, 52, 62, 64, 25, 59, 23, 64, 50, 44, 52, 44, 19, 63, 47, 41, 33, 59, 48, 45, 39, 57, 21, 27, 62, 26, 19, 46, 28, 61, 12, 53, 11, 19, 62, 36, 32, 6, 11, 29, 7, 49, 29, 8, 11, 21, 15, 29, 19, 16, 16, 54, 2, 22, 28, 23, 29, 21, 29, 36, 48, 53, 49, 27, 3, 53, 8, 50, 42, 4, 50, 46, 8, 26, 51, 5, 12, 49, 18, 31, 52, 9, 5, 58, 24, 53, 16, 28, 18, 51, 44, 20, 56, 48, 24, 59, 20, 57, 17, 64, 49, 19, 60, 19, 4, 50, 30, 18, 33, 3, 44, 36, 22, 56, 8, 3, 64, 54, 33, 36, 2, 38, 34, 37, 45, 4, 1, 15, 11, 24, 29, 48, 49, 57, 50, 57, 31, 28, 41, 31, 33, 8, 48]
> 5972
Round 20
[62, 1, 14, 31, 33, 64, 34, 38, 43, 64, 39, 16, 64, 32, 59, 46, 49, 23, 22, 6, 11, 56, 59, 52, 19, 8, 53, 32, 48, 27, 11, 21, 1, 37, 47, 26, 9, 15, 32, 49, 5, 23, 45, 27, 48, 22, 9, 58, 37, 3, 23]
> 729
Round 21
[63, 33, 60, 10, 35, 46, 62, 3, 3, 61, 49, 27, 56, 33, 36, 50, 50, 47, 44, 41, 15, 48, 54, 2, 2, 27, 13, 25, 18, 51, 49, 61, 42, 43, 22, 35, 11, 4, 23, 5, 62, 9, 37, 10, 41, 52, 33, 5, 24, 32, 3, 17, 2, 51, 14, 52, 19, 40, 55, 44, 42, 6, 38, 36, 51, 37, 12, 32, 43, 41, 59, 31, 27, 40, 46, 31, 58, 5, 64, 8, 42, 57, 8, 55, 44, 7, 19, 38, 22, 49, 62, 56, 19, 39, 6, 6, 36, 63, 42, 28, 49, 62, 61, 39, 28, 50, 44, 36, 56, 8, 31, 40, 44, 40, 41, 16, 21, 34, 47, 36, 43, 26, 40, 29, 29, 12, 33, 59, 8, 13, 37, 48, 29, 45, 28, 35, 28, 5, 27, 40, 49, 32, 53, 17, 53, 1, 21, 54, 45, 13, 51, 62, 35, 10, 57, 59, 12, 22, 26, 53, 11, 19, 17, 60, 11, 61, 33, 5, 8, 30, 52, 56, 59, 60, 55, 15, 51, 12, 36, 6, 2, 59, 17, 55, 30, 30, 50, 19, 52, 2]
> 8955
Round 22
[13, 24, 31, 59, 34, 28, 8, 22, 21, 47, 20, 18, 45, 56, 39, 48, 37, 52, 48, 45, 20, 26, 61, 30, 52, 38, 52]
> 124
Round 23
[58, 39, 7, 6, 49, 14, 57, 27, 27, 12, 28, 59, 58, 34, 54, 28, 2, 18, 51, 48, 37, 47, 22, 19, 37, 58, 22, 61, 24, 39, 7, 39, 25, 7, 27, 27, 51, 61, 12, 20, 58, 1, 8, 53, 44, 37, 52, 9, 32, 46, 12, 21, 42]
> 699
Round 24
[46, 3, 36, 3, 17, 40, 63, 56, 38, 63, 8, 64, 57, 49, 54, 2, 43, 59, 22, 37, 12, 55, 18, 20, 19, 44, 36, 55, 34, 1, 52, 41, 46, 32, 21, 48, 28, 26, 50, 30, 36, 4, 26, 39, 6, 12, 50, 11, 42, 10, 62, 13, 34, 4, 51, 30, 8, 37, 43, 50, 22, 37, 23, 63, 61, 63, 25, 19, 22, 21, 27, 49, 2, 9, 13, 52, 54, 61, 18, 35]
> 1650
Round 25
[34, 9, 54, 48, 49, 63, 34, 26, 9, 13, 4, 61, 33, 9, 9, 15, 48, 51, 17, 37, 56, 16, 64, 41, 61, 31, 40, 5, 28, 28, 48, 40, 33, 27, 52, 2, 46, 37, 15, 15, 60, 42, 26, 30, 55, 16, 46, 11, 21, 42, 20, 7, 38, 41, 9, 31, 60, 6, 4, 45, 29, 36, 44, 48, 59, 26, 37, 29, 4, 15, 21, 10, 40, 37, 56, 33, 12, 15, 1, 36, 33, 45, 2, 12, 11, 8, 17]
> 2102
you won here's your flag flag{g077a_0pt1m1ze_3m_@ll}
flag{g077a_0pt1m1ze_3m_@ll}
0x414141 (misc)
offshiftのオープンソースを調べると、以下のページが見つかる。
https://github.com/offshift-protocol
その中にリポジトリはpromoだけがある。script.cpython-38.pycが削除されているようだが、直接見れないので、クローンして確認してみる。
$ git clone https://github.com/offshift-protocol/promo Cloning into 'promo'... remote: Enumerating objects: 8, done. remote: Counting objects: 100% (8/8), done. remote: Compressing objects: 100% (7/7), done. remote: Total 8 (delta 0), reused 0 (delta 0), pack-reused 0 Unpacking objects: 100% (8/8), done. $ cd promo/.git $ cat refs/heads/main f2112c46cafb86e3225901b011e4ea71858901a3 $ python -c 'import zlib; print zlib.decompress(open("objects/f2/112c46cafb86e3225901b011e4ea71858901a3").read())' commit 733tree c67bf4194644f2ebb9acb63f795d5f34e7ed8e9e parent dc43c1ac33f767a7d30dbeab123a1c87566e885d author Offshift <49762107+offshift-dev@users.noreply.github.com> 1611505905 -0100 committer GitHub <noreply@github.com> 1611505905 -0100 gpgsig -----BEGIN PGP SIGNATURE----- wsBcBAABCAAQBQJgDaDxCRBK7hj4Ov3rIwAAdHIIAFoiwz+xsAxxsXGcO6vgSw7e 9GtbWf30+mWoiPkt4b+0yyHxndjnapHX+RQ0FZKPR+8e0niX3GRPGBaMQrhJvysX gnOHTxPPHQhppePqYA2eIVVde92DY8uy4XoJfLYM6WtxRDMv3peqOSxe6G6Nq5UI k75p5ut+CCiCBXaQ0YGwBZB0HhTYjZ7aum++686RoN2QqpygVpk8l7n5j6kH7LMY HYzE6AfTpEzdCTQsTkXYLFiGNlrJBopXLVk6UlK6FEJjtugme7IyUA8+C2mQuDf3 stpfClixh8DoSlne7lxYWBEPZ0/Cz2M/YJdI/YIK42bo9ciA25p1VU/ywNKMnaY= =rzCh -----END PGP SIGNATURE----- Delete __pycache__ directory $ python -c 'import zlib; print zlib.decompress(open("objects/c6/7bf4194644f2ebb9acb63f795d5f34e7ed8e9e").read())' | xxd -g 1 00000000: 74 72 65 65 20 37 35 00 31 30 30 36 34 34 20 69 tree 75.100644 i 00000010: 6e 64 65 78 2e 68 74 6d 6c 00 86 b9 11 1f 9a 08 ndex.html....... 00000020: 7a ce d6 ca 90 ef 5a 76 d6 7e 78 5e af 3c 31 30 z.....Zv.~x^.<10 00000030: 30 36 34 34 20 73 74 79 6c 65 2e 63 73 73 00 56 0644 style.css.V 00000040: d6 18 f0 c4 32 d3 34 19 2a 5a 16 41 07 fe f5 21 ....2.4.*Z.A...! 00000050: 90 fd fd 0a .... $ python -c 'import zlib; print zlib.decompress(open("objects/dc/43c1ac33f767a7d30dbeab123a1c87566e885d").read())' commit 677tree f2770ee6c94e8f0e1c0605a435b6b7d998081d01 author Offshift <49762107+offshift-dev@users.noreply.github.com> 1611505821 -0100 committer GitHub <noreply@github.com> 1611505821 -0100 gpgsig -----BEGIN PGP SIGNATURE----- wsBcBAABCAAQBQJgDaCdCRBK7hj4Ov3rIwAAdHIIAGQlUPSihalxcnAvZAhKWA0u K0e+kdVSfNve2nuIniWDD0bYKrKoqaj0XifFg6k6JWmgJ6QmanEsWqTl7IMlOlNL 5eeChcSl/OZRV0ZOa0g/PpuZnQYrHaVQBm2bsvkbYUmMTSb7Cui7/bBHjceEke56 Imt82NnoFIDUVP+9iS8WKGSQIc4eWZTD4bJE6SdOyHxFpcc4+aUahqibixGx5tYU N64LG1OHYkwa9wx0zHFOj7zfJbkzhfC4ypuX3Xc5vE4vvSQJU4BPqTcWzr/qY358 gw3CLVK04PE3kE7tjzbO44Nw7tQUxjM1PlD+BSA7M8FM5vQgr+b36Nyq3aelHGk= =F0e5 -----END PGP SIGNATURE----- Add files via upload $ python -c 'import zlib; print zlib.decompress(open("objects/f2/770ee6c94e8f0e1c0605a435b6b7d998081d01").read())' | xxd -g 1 00000000: 74 72 65 65 20 31 31 33 00 34 30 30 30 30 20 5f tree 113.40000 _ 00000010: 5f 70 79 63 61 63 68 65 5f 5f 00 0f 14 56 62 28 _pycache__...Vb( 00000020: c7 f9 3e 3f 37 7a de 90 43 3b 8c 92 13 e5 ad 31 ..>?7z..C;.....1 00000030: 30 30 36 34 34 20 69 6e 64 65 78 2e 68 74 6d 6c 00644 index.html 00000040: 00 86 b9 11 1f 9a 08 7a ce d6 ca 90 ef 5a 76 d6 .......z.....Zv. 00000050: 7e 78 5e af 3c 31 30 30 36 34 34 20 73 74 79 6c ~x^.<100644 styl 00000060: 65 2e 63 73 73 00 56 d6 18 f0 c4 32 d3 34 19 2a e.css.V....2.4.* 00000070: 5a 16 41 07 fe f5 21 90 fd fd 0a Z.A...!.... $ python -c 'import zlib; print zlib.decompress(open("objects/0f/14566228c7f93e3f377ade90433b8c9213e5ad").read())' | xxd -g 1 00000000: 74 72 65 65 20 34 39 00 31 30 30 36 34 34 20 73 tree 49.100644 s 00000010: 63 72 69 70 74 2e 63 70 79 74 68 6f 6e 2d 33 38 cript.cpython-38 00000020: 2e 70 79 63 00 08 08 80 d2 16 84 d4 d0 19 c0 e7 .pyc............ 00000030: 66 01 2b 69 07 8c 44 b1 c4 0a f.+i..D... $ python -c 'import zlib; print zlib.decompress(open("objects/08/0880d21684d4d019c0e766012b69078c44b1c4").read())' | xxd -g 1 00000000: 62 6c 6f 62 20 35 36 39 00 55 0d 0d 0a 00 00 00 blob 569.U...... 00000010: 00 cd c2 d4 5f e1 01 00 00 e3 00 00 00 00 00 00 ...._........... 00000020: 00 00 00 00 00 00 00 00 00 00 18 00 00 00 40 00 ..............@. 00000030: 00 00 73 52 00 00 00 64 00 64 01 6c 00 5a 00 64 ..sR...d.d.l.Z.d 00000040: 02 5a 01 64 03 64 04 64 04 64 05 64 06 64 07 64 .Z.d.d.d.d.d.d.d 00000050: 08 64 08 64 09 64 0a 64 0b 64 03 64 0c 64 0d 64 .d.d.d.d.d.d.d.d 00000060: 0e 64 0f 64 0c 64 06 64 08 64 10 64 11 64 12 64 .d.d.d.d.d.d.d.d 00000070: 13 64 14 67 18 5a 02 64 15 64 16 84 00 65 01 44 .d.g.Z.d.d...e.D 00000080: 00 83 01 5a 03 64 01 53 00 29 17 e9 00 00 00 00 ...Z.d.S.)...... 00000090: 4e 7a 12 68 74 74 70 73 3a 2f 2f 67 6f 6f 67 6c Nz.https://googl 000000a0: 65 2e 63 6f 6d 73 04 00 00 00 4e 44 45 3d 73 04 e.coms....NDE=s. 000000b0: 00 00 00 4e 54 4d 3d 73 04 00 00 00 4e 44 6b 3d ...NTM=s....NDk= 000000c0: 73 04 00 00 00 4e 54 41 3d 73 04 00 00 00 4d 54 s....NTA=s....MT 000000d0: 49 7a 73 04 00 00 00 4d 54 45 77 73 04 00 00 00 Izs....MTEws.... 000000e0: 4d 7a 49 3d 73 04 00 00 00 4e 54 45 3d 73 04 00 MzI=s....NTE=s.. 000000f0: 00 00 4d 7a 51 3d 73 04 00 00 00 4e 44 41 3d 73 ..MzQ=s....NDA=s 00000100: 04 00 00 00 4e 54 55 3d 73 04 00 00 00 4d 7a 59 ....NTU=s....MzY 00000110: 3d 73 04 00 00 00 4d 54 45 78 73 04 00 00 00 4e =s....MTExs....N 00000120: 44 59 3d 73 04 00 00 00 4d 54 49 3d 73 04 00 00 DY=s....MTI=s... 00000130: 00 4e 44 55 3d 73 04 00 00 00 4d 54 45 32 73 04 .NDU=s....MTE2s. 00000140: 00 00 00 4d 54 49 77 63 01 00 00 00 00 00 00 00 ...MTIwc........ 00000150: 00 00 00 00 02 00 00 00 07 00 00 00 43 00 00 00 ............C... 00000160: 73 26 00 00 00 67 00 7c 00 5d 1e 7d 01 74 00 a0 s&...g.|.].}.t.. 00000170: 01 74 02 74 03 7c 01 83 01 64 00 41 00 83 01 a0 .t.t.|...d.A.... 00000180: 04 a1 00 a1 01 91 02 71 04 53 00 29 01 e9 41 00 .......q.S.)..A. 00000190: 00 00 29 05 da 06 62 61 73 65 36 34 5a 09 62 36 ..)...base64Z.b6 000001a0: 34 65 6e 63 6f 64 65 da 03 73 74 72 da 03 6f 72 4encode..str..or 000001b0: 64 da 06 65 6e 63 6f 64 65 29 02 da 02 2e 30 da d..encode)....0. 000001c0: 01 69 a9 00 72 09 00 00 00 fa 0b 2e 2f 73 63 72 .i..r......./scr 000001d0: 69 70 74 2e 70 79 da 0a 3c 6c 69 73 74 63 6f 6d ipt.py..<listcom 000001e0: 70 3e 05 00 00 00 73 04 00 00 00 06 00 02 00 72 p>....s........r 000001f0: 0b 00 00 00 29 04 72 03 00 00 00 5a 06 73 65 63 ....).r....Z.sec 00000200: 72 65 74 5a 07 63 69 70 68 65 72 32 5a 07 63 69 retZ.cipher2Z.ci 00000210: 70 68 65 72 31 72 09 00 00 00 72 09 00 00 00 72 pher1r....r....r 00000220: 09 00 00 00 72 0a 00 00 00 da 08 3c 6d 6f 64 75 ....r......<modu 00000230: 6c 65 3e 01 00 00 00 73 06 00 00 00 08 02 04 01 le>....s........ 00000240: 34 01 0a 4..
script.cpython-38.pycのデータを見つけたので、取り出し、デコンパイルする。
$ python -c 'import zlib; a = zlib.decompress(open("objects/08/0880d21684d4d019c0e766012b69078c44b1c4").read())[9:]; open("script.cpython-38.pyc", "wb").write(a)' $ uncompyle6 script.cpython-38.pyc # uncompyle6 version 3.7.4 # Python bytecode 3.8 (3413) # Decompiled from: Python 2.7.17 (default, Sep 30 2020, 13:38:04) # [GCC 7.5.0] # Warning: this version of Python has problems handling the Python 3 "byte" type in constants properly. # Embedded file name: ./script.py # Compiled at: 2020-12-12 22:17:01 # Size of source mod 2**32: 481 bytes import base64 secret = 'https://google.com' cipher2 = ['NDE=', 'NTM=', 'NTM=', 'NDk=', 'NTA=', 'MTIz', 'MTEw', 'MTEw', 'MzI=', 'NTE=', 'MzQ=', 'NDE=', 'NDA=', 'NTU=', 'MzY=', 'MTEx', 'NDA=', 'NTA=', 'MTEw', 'NDY=', 'MTI=', 'NDU=', 'MTE2', 'MTIw'] cipher1 = [base64.b64encode(str(ord(i) ^ 65).encode()) for i in secret] # okay decompiling script.cpython-38.pyc
cipher1はsecretを元に、secret2のような暗号になる。cipher2が同様に暗号化されていると推測し、復号する。
import base64 secret = 'https://google.com' cipher2 = ['NDE=', 'NTM=', 'NTM=', 'NDk=', 'NTA=', 'MTIz', 'MTEw', 'MTEw', 'MzI=', 'NTE=', 'MzQ=', 'NDE=', 'NDA=', 'NTU=', 'MzY=', 'MTEx', 'NDA=', 'NTA=', 'MTEw', 'NDY=', 'MTI=', 'NDU=', 'MTE2', 'MTIw'] cipher1 = [base64.b64encode(str(ord(i) ^ 65).encode()) for i in secret] print '[+] cipher1 =', cipher1 secret2 = ''.join([chr(int(base64.b64decode(i)) ^ 65) for i in cipher2]) print secret2
実行結果は以下の通り。
[+] cipher1 = ['NDE=', 'NTM=', 'NTM=', 'NDk=', 'NTA=', 'MTIz', 'MTEw', 'MTEw', 'Mzg=', 'NDY=', 'NDY=', 'Mzg=', 'NDU=', 'MzY=', 'MTEx', 'MzQ=', 'NDY=', 'NDQ='] https://archive.is/oMl59
復号したURLのhttps://archive.is/oMl59にアクセスすると、メッセージの中に以下が書いてある。
super secret random file https://mega.nz/file/AAdDyIoB#gpj5s9N9-VnbNhSdkJ24Yyq3BWSYimoxanP-p03gQWs
このストレージからsmashing.pdfをダウンロードしたが、PDFの形式にはなっていない。XORされていないかヘッダ部だけ確認すると、鍵長1バイトのXORになっているようなので、復号してみる。
with open('smashing.pdf', 'rb') as f: ct = f.read() key = ord(ct[0]) ^ ord('%') pt = '' for c in ct: pt += chr(ord(c) ^ key) with open('smashing_decrypt.pdf', 'wb') as f: f.write(pt)
復号したPDFの末尾の後ろに、ZIPが付いているので、切り取る。ZIPはパスワード付きZIPになっているので、クラックして、そのパスワードで解凍、展開する。
$ fcrackzip -u -D -p dict/rockyou.txt flag.zip PASSWORD FOUND!!!!: pw == passwd $ unzip -P passwd flag.zip Archive: flag.zip extracting: flag.txt $ cat flag.txt oh ma gawd you got it flag{1t_b33n_A_l0ng_w@y8742}
flag{1t_b33n_A_l0ng_w@y8742}
file reader (misc)
指定したファイルを読み込み表示してくれるが、以下の文字列が含まれているとエラーになる。
/etc/passwd", "/flag.txt", "/proc/"
それを避けて、指定してみる。
$ nc 207.180.200.166 2324 give me a file to read > /*flag.txt flag{oof_1t_g0t_expanded_93929}
flag{oof_1t_g0t_expanded_93929}
Ware (reversing)
$ upx -d skidw4re Ultimate Packer for eXecutables Copyright (C) 1996 - 2017 UPX 3.94 Markus Oberhumer, Laszlo Molnar & John Reiser May 12th 2017 File size Ratio Format Name -------------------- ------ ----------- ----------- 2046392 <- 706824 34.54% linux/i386 skidw4re Unpacked 1 file. $ file skidw4re skidw4re: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), statically linked, with debug_info, not stripped
Ghidraでデコンパイルする。
void main.Encryptfinal(void) { uint *puVar1; undefined4 *puVar2; undefined4 uVar3; int *in_GS_OFFSET; undefined4 in_stack_ffffff88; undefined4 in_stack_ffffff8c; undefined4 local_70; undefined4 local_6c; undefined local_68 [32]; char *local_48; undefined4 local_44; char *local_40; undefined4 local_3c; undefined4 local_28; undefined4 local_24; undefined local_20 [8]; undefined4 *local_18; undefined4 local_14; undefined4 local_10; undefined4 local_4; puVar1 = (uint *)(*(int *)(*in_GS_OFFSET + -4) + 8); if ((undefined4 *)*puVar1 <= &local_4 && &local_4 != (undefined4 *)*puVar1) { local_48 = "321174068998067 98980909";★ local_44 = 0x18; local_40 = "thisis32bitlongpassphraseimusing"; local_3c = 0x20; runtime.stringtoslicebyte(local_68,"thisis32bitlongpassphraseimusing",0x20); main.EncryptAES(in_stack_ffffff88,in_stack_ffffff8c,local_70,local_48,local_44); uVar3 = runtime.concatstring2(0,"This is the only message--------> ",0x22); local_28 = 0; local_24 = 0; local_18 = &local_28; if (local_18 == (undefined4 *)0x0) { local_28 = uVar3; } local_14 = 1; local_10 = 1; runtime.convT2E(&DAT_080f1f00,local_20,0); puVar2 = local_18; *local_18 = local_70; if (runtime.writeBarrier.enabled == false) { puVar2[1] = local_6c; } else { runtime.writebarrierptr(puVar2 + 1,local_6c); } fmt.Println(local_18,local_14,local_10); return; } local_4 = 0x8049510; runtime.morestack_noctxt(); main.Encryptfinal(); return; }
元のデータは "321174068998067 98980909"。
flag{32117406899806798980909}
factorize (crypto)
nの平方根を取って、上位512ビットがbaseの上位512ビットになる。
p = base + x q = base + y n = p * q = base ** 2 + (x + y) * base + x*y x + y = (n - base**2) // base x * y = (n - base**2) % base
和と積がわかるので、方程式にしてp, qを求める。あとはそのまま復号する。
import gmpy2 from sympy import * from Crypto.Util.number import * n = 23135514747783882716888676812295359006102435689848260501709475114767217528965364658403027664227615593085036290166289063788272776788638764660757735264077730982726873368488789034079040049824603517615442321955626164064763328102556475952363475005967968681746619179641519183612638784244197749344305359692751832455587854243160406582696594311842565272623730709252650625846680194953309748453515876633303858147298846454105907265186127420148343526253775550105897136275826705375222242565865228645214598819541187583028360400160631947584202826991980657718853446368090891391744347723951620641492388205471242788631833531394634945663 e = 0x10001 c = 17830167351685057470426148820703481112309475954806278304600862043185650439097181747043204885329525211579732614665322698426329449125482709124139851522121862053345527979419420678255168453521857375994190985370640433256068675028575470040533677286141917358212661540266638008376296359267047685745805295747215450691069703625474047825597597912415099008745060616375313170031232301933185011013735135370715444443319033139774851324477224585336813629117088332254309481591751292335835747491446904471032096338134760865724230819823010046719914443703839473237372520085899409816981311851296947867647723573368447922606495085341947385255 x = gmpy2.isqrt(n) base = (x >> 512) << 512 remain = n - pow(base, 2) plus = remain // base prod = remain % base p = symbols('p') ans = solve(p**2 - plus * p + prod, p) p = base + int(ans[0]) q = base + int(ans[1]) assert p * q == n phi = (p - 1) * (q - 1) d = inverse(e, phi) m = pow(c, d, n) flag = long_to_bytes(m) print flag
flag{just_g0tta_f@ct0rize_1t4536}
staple AES (crypto)
暗号化の処理概要は以下の通り。
・flagの長さは16の倍数+1 ・flagに\x0f*15をパディング ・16バイト1ブロックで、flagをブロック単位でシャッフル ・暗号化 iv --(AES暗号化)--> c0、pt0 ^ c0 -> ct0 c0 --(AES暗号化)--> c1、pt1 ^ c1 -> ct1 c1 --(AES暗号化)--> c2、pt2 ^ c2 -> ct2
iv, keyは固定のため、c0, c1, c2は固定。ブロックごとのXORで考えるしかない。
$ nc 161.97.176.150 3167 1c4d2577fb9d46230e3338145be071174b83ab64f8dfe67b94db150948638f6463305d63ac7c5657ec3ad64a021548e5 $ nc 161.97.176.150 3167 1c4d2577fb9d46230e3338145be071175ebdd73480b1dc2bdb8b6935241eb31f760e2133d4126c07a36aaa766e68749e $ nc 161.97.176.150 3167 072e4b1f8fdb161b690c427c3c9b212f45deb95cf4f78c13bcb4135d4365e327760e2133d4126c07a36aaa766e68749e $ nc 161.97.176.150 3167 072e4b1f8fdb161b690c427c3c9b212f4b83ab64f8dfe67b94db150948638f647853330bd83a066f8b05ac22656e18dd $ nc 161.97.176.150 3167 1210374ff7b52c4b265c3e4050e61d545ebdd73480b1dc2bdb8b6935241eb31f7853330bd83a066f8b05ac22656e18dd
ブロックに分割して考える。
1c4d2577fb9d46230e3338145be07117 4b83ab64f8dfe67b94db150948638f64 63305d63ac7c5657ec3ad64a021548e5 1c4d2577fb9d46230e3338145be07117 5ebdd73480b1dc2bdb8b6935241eb31f 760e2133d4126c07a36aaa766e68749e 072e4b1f8fdb161b690c427c3c9b212f 45deb95cf4f78c13bcb4135d4365e327 760e2133d4126c07a36aaa766e68749e 072e4b1f8fdb161b690c427c3c9b212f 4b83ab64f8dfe67b94db150948638f64 7853330bd83a066f8b05ac22656e18dd 1210374ff7b52c4b265c3e4050e61d54 5ebdd73480b1dc2bdb8b6935241eb31f 7853330bd83a066f8b05ac22656e18dd
平文の各ブロックをpt0, pt1, pt2（順序は考えない）とする。
pt0 ^ c0 = 1c4d2577fb9d46230e3338145be07117 pt1 ^ c0 = 072e4b1f8fdb161b690c427c3c9b212f pt2 ^ c0 = 1210374ff7b52c4b265c3e4050e61d54 pt0 ^ c0 ^ pt1 ^ c0 = pt0 ^ pt1 = 1c4d2577fb9d46230e3338145be07117 ^ 072e4b1f8fdb161b690c427c3c9b212f pt1 ^ c0 ^ pt2 ^ c0 = pt1 ^ pt2 = 072e4b1f8fdb161b690c427c3c9b212f ^ 1210374ff7b52c4b265c3e4050e61d54 pt2 ^ c0 ^ pt0 ^ c0 = pt2 ^ pt0 = 1210374ff7b52c4b265c3e4050e61d54 ^ 1c4d2577fb9d46230e3338145be07117
c1, c2も同様のことが言える。あるブロックは"}" + \x0f * 15と推測できるので、そのことからXORで復号する。
from Crypto.Util.strxor import strxor from Crypto.Util.Padding import pad, unpad def is_printable(s): for c in s: if ord(c) < 32 or ord(c) > 126: return False return True enc_bl = ['1c4d2577fb9d46230e3338145be07117', '072e4b1f8fdb161b690c427c3c9b212f', '1210374ff7b52c4b265c3e4050e61d54'] enc = [] enc.append(strxor(enc_bl[0].decode('hex'), enc_bl[1].decode('hex'))) enc.append(strxor(enc_bl[1].decode('hex'), enc_bl[2].decode('hex'))) enc.append(strxor(enc_bl[2].decode('hex'), enc_bl[0].decode('hex'))) flag = ['', '', pad('}', 16)] for i in range(len(enc)): pt = strxor(enc[i], flag[2]) if is_printable(pt): if pt.startswith('flag'): flag[0] = pt else: flag[1] = pt flag = unpad(''.join(flag), 16) print flag
flag{I_7h0ught_7h1s_wa5_@_s3cr3t}
Delegate wallet (crypto)
(X0 * m + c) % n = X1 (X1 * m + c) % n = X2 (X2 * m + c) % n = X3 (X3 * m + c) % n = X4 (X4 * m + c) % n = X5 X3 - X2 = (X2 - X1) * m mod n ☆ X4 - X3 = (X3 - X2) * m mod n (X4 - X3) * (X2 - X1) = (X3 - X2)**2 mod n (X5 - X4) * (X3 - X2) = (X4 - X3)**2 mod n ：
この差分を数回とりGCDを取ることにより、nを割り出す。nがわかったら、☆よりmを逆算することができる。
m = ((X3 - X2) * inverse(X2 - X1, n)) % n
さらにcを割り出すことができる。
c = (X2 - X1 * m) % n
これで次の数値を算出することができる。
import socket from Crypto.Util.number import * def recvuntil(s, tail): data = '' while True: if tail in data: return data data += s.recv(1) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('185.172.165.118', 4008)) X = [] for i in range(8): data = recvuntil(s, '> ') print data + '1' s.sendall('1\n') data = recvuntil(s, '\n').rstrip() print data X.append(int(data)) cs = [] for i in range(5): c1 = (X[i+3] - X[i+2]) * (X[i+1] - X[i]) c2 = (X[i+2] - X[i+1]) ** 2 if c1 > c2: c = c1 - c2 else: c = c2 - c1 cs.append(c) n = cs[0] for i in range(len(cs) - 1): n = GCD(n, cs[i+1]) print '[+] n =', n m = ((X[2] - X[1]) * inverse(X[1] - X[0], n)) % n print '[+] m =', m c = (X[1] - X[0] * m) % n print '[+] c =', c guess = str((X[-1] * m + c) % n) data = recvuntil(s, '> ') print data + '2' s.sendall('2\n') data = recvuntil(s, '> ') print data + guess s.sendall(guess + '\n') data = recvuntil(s, '\n').rstrip() print data
実行結果は以下の通り。
1) Generate a new wallet seed
2) Guess the next wallet seed
> 1
205600799772289345656512115659624517173423800218105916576855944964024707684982707049187844954815550689957803676097281265539470743425287448789530864268326774563770430525474927883798497
1) Generate a new wallet seed
2) Guess the next wallet seed
> 1
365402502563786390912694580625513327177671275957027745363041240794904568609294881386278887735508394002717059240681298778080319176614031100269976887735509557512605024192285847511360008
1) Generate a new wallet seed
2) Guess the next wallet seed
> 1
224952501214046660313388573492898855297979963381006208621080383394450867200772782692706594814414972934845107530728067025982235477477246922233794534968971537569083313176481093110610470
1) Generate a new wallet seed
2) Guess the next wallet seed
> 1
255629899258689969607411017134617172668891621228611039213363410066821292733391067565803328832827405007928032778240899140690881521111030682570720863959711903335338383074908764462486915
1) Generate a new wallet seed
2) Guess the next wallet seed
> 1
526312918494968483669375640504048805057846889243799429701232646722770399985161665823720014326544326067034763717051415645539746215686827666560301831218027325001987765492353269627214413
1) Generate a new wallet seed
2) Guess the next wallet seed
> 1
422552249409833253028548293932580803895739819461070273646354784614206434529479253017594640261551604706380327305026312297852576910173803555344389738950779065022553085562282303371641834
1) Generate a new wallet seed
2) Guess the next wallet seed
> 1
515110659716453319891151765914548925738616838730021309075034719498838685311757325301035950754518014190758484224415690910264682862177981734748022367448587444156538130977024690853024848
1) Generate a new wallet seed
2) Guess the next wallet seed
> 1
225998749999180002969566138425595586077586075562521796149851455642147342432534074176913034285817273720808983757680617619241153213876792422830411915160339129726425098219888457472488252
[+] n = 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127
[+] m = 432045342985714330674242123070043799018829857700900194542840199591914840441337375115148738539281976063524715443463466245003104040011222208861631442359541686468524830712577484868037198
[+] c = 434849646037905231096241985310755214291867091225405542034606208361331903733563815873822563397209031172076187422331726176546737742157598367697464952702583239039307921821381265224221563
1) Generate a new wallet seed
2) Guess the next wallet seed
> 2
> 474070570516616676100123299202704282849672197449795712238709182294115800920288242009929131538191411050046211537015884490243096415276655956899049602248910287856692836430228654160784220
flag{NBD_7H3Y_U53D_0ffsh1ft4532}
flag{NBD_7H3Y_U53D_0ffsh1ft4532}
eazy RSA (crypto)
eが2の4乗。p % 4 = 3, q % 4 = 3なので、Rabin暗号の復号を4回行う。
from Crypto.Util.number import * def egcd(a, b): if a == 0: return b, 0, 1 else: gcd, y, x = egcd(b % a, a) return gcd, x - (b // a) * y, y c = 3708354049649318175189820619077599798890688075815858391284996256924308912935262733471980964003143534200740113874286537588889431819703343015872364443921848 e = 16 p = 75000325607193724293694446403116223058337764961074929316352803137087536131383 q = 69376057129404174647351914434400429820318738947745593069596264646867332546443 n = p * q assert p % 4 == 3 assert q % 4 == 3 cs = [c] for i in range(4): ps = [] for c2 in cs: r = pow(c2, long((p + 1) / 4), long(p)) s = pow(c2, long((q + 1) / 4), long(q)) gcd, x0, x1 = egcd(p, q) x = (r * x1 * q + s * x0 * p) % n y = (r * x1 * q - s * x0 * p) % n ps += [x, n - x, y, n - y] cs = ps for m in ps: flag = long_to_bytes(m) if flag.startswith('flag'): print flag break
flag{d0nt_h4v3_4n_3v3n_3_175_34sy!!!}
Encrypt0r (crypto)
$ nc 185.172.165.118 4449 Heres the flag! 248460643464675800653780615843208617730874812788255456931910 Enter a value for me to encrypt > 0 0 Enter a value for me to encrypt > 1 1 Enter a value for me to encrypt > 2 15316765420522776956567713808649930958674151786266484041867 Enter a value for me to encrypt > 3 22858393062144231457977434767158918520515356317653059923134 Enter a value for me to encrypt > 4 721065027681193958622905905170978238298829337296513362101428 Enter a value for me to encrypt >
この結果からRSA暗号と推測する。2, 4, 16の暗号からnを割り出す。それからeを割り出すと、通常の65537で計算は合う。あとはfactordbで素因数分解して、p, qを求め復号する。
import socket from Crypto.Util.number import * def recvuntil(s, tail): data = '' while True: if tail in data: return data data += s.recv(1) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('185.172.165.118', 4449)) data = recvuntil(s, '\n').rstrip() print data data = recvuntil(s, '\n').rstrip() print data c = int(data) #### calculate n #### try_rsa_enc = [] for m in [2, 4, 16]: data = recvuntil(s, '> ') print data + str(m) s.sendall(str(m) + '\n') data = recvuntil(s, '\n') print data try_rsa_enc.append(int(data)) diff1 = (try_rsa_enc[0]) ** 2 - try_rsa_enc[1] diff2 = (try_rsa_enc[1]) ** 2 - try_rsa_enc[2] n = GCD(diff1, diff2) for i in range(128, 1, -1): if n % i == 0: n /= i print '[+] n =', n e = 65537 assert pow(2, e, n) == try_rsa_enc[0] assert pow(4, e, n) == try_rsa_enc[1] assert pow(16, e, n) == try_rsa_enc[2] # n = 722316164267119792405604455117204641944448497312096064056839 # = 730573343524370733896529924509 * 988697672409703112206678896371 #### decrypt #### p = 730573343524370733896529924509 q = 988697672409703112206678896371 phi = (p - 1) * (q - 1) d = inverse(e, phi) m = pow(c, d, n) flag = long_to_bytes(m) print '[*] flag:', flag
実行結果は以下の通り。
Heres the flag! 248460643464675800653780615843208617730874812788255456931910 Enter a value for me to encrypt > 2 15316765420522776956567713808649930958674151786266484041867 Enter a value for me to encrypt > 4 721065027681193958622905905170978238298829337296513362101428 Enter a value for me to encrypt > 16 437047056914634815063585116191009236869948090365526468427683 [+] n = 722316164267119792405604455117204641944448497312096064056839 [*] flag: y0u_d0nt_n33d_4nyth1ng
flag{y0u_d0nt_n33d_4nyth1ng}
