# Writeup for Crypto Problems in SCTF 2019

## warmup

### Analysis

  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  #!/usr/bin/python # -*- coding: utf-8 -*- from Crypto.Cipher import AES from Crypto.Util.strxor import strxor from Crypto.Random import get_random_bytes from FLAG import flag class MAC: def __init__(self): self.key = get_random_bytes(16) self.iv = get_random_bytes(16) def pad(self, msg): pad_length = 16 - len(msg) % 16 return msg + chr(pad_length) * pad_length def unpad(self, msg): return msg[:-ord(msg[-1])] def code(self, msg): res = chr(0)*16 for i in range(len(msg)/16): res = strxor(msg[i*16:(i+1)*16], res) aes = AES.new(self.key, AES.MODE_CBC, self.iv) return aes.encrypt(res).encode('hex') def identity(self, msg, code): if self.code(msg) == code: msg = self.unpad(msg) if msg == 'please send me your flag': print 'remote: ok, here is your flag:%s' % flag else: print 'remote: I got it' else: print 'remote: hacker!' if __name__ == '__main__': mac = MAC() message = 'see you at three o\'clock tomorrow' print 'you seem to have intercepted something:{%s:%s}' %(mac.pad(message).encode('hex'), mac.code(mac.pad(message))) print 'so send your message:' msg = raw_input() print 'and your code:' code = raw_input() mac.identity(msg.decode('hex'), code) exit() 

1. AES_CBC模式加密

2. 已知的1个明-密文对：pad('see you at three o\'clock tomorrow') - 从服务器收到的密文
3. 明文长度48=16*3，AES加密的是strxor后的明文

4. 输入msg和code，其中msg要满足unpad(msg)后是'please send me your flag'，而且用同样的key和IV加密这个msg后得到的内容是自己输入的code

### AES attack

message每次都是固定的，都是‘see you at three o’clock tomorrow’，pad后就是'see you at three o'clock tomorrow\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f'，然后再对这个pad后的结果进行strxor操作，也就是分成3组，每组对应位置的字符异或，然后得到一个16bytes长的res，每次pad后的结果也都是一样的，所以第一次加密的res也都是一样的，可以先算出来，是res = '$\x05ML\x1a\x0f\x19DN\x0f@\x16\x08\x0f\x18\x05'，所以每次AES都是对这个加密。 这里，我们可以构造一个msg，使得： 1. unpad(msg) = 'please send me your flag' 2. strxor(pad(msg)) = res = '$\x05ML\x1a\x0f\x19DN\x0f@\x16\x08\x0f\x18\x05'

unpad时，是按照末尾字节的值来截断尾部的。

len('please send me your flag') = 24，所以截断后的长度必须为24，且msg[:24]='please send me your flag'

### 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  from pwn import * from Crypto.Util.strxor import strxor def fuck(): pad_message = 'see you at three o\'clock tomorrow' + 15 * chr(15) res = chr(0) * 16 for i in range(len(pad_message) / 16): res = strxor(pad_message[i*16:(i+1)*16], res) # res = '\$\x05ML\x1a\x0f\x19DN\x0f@\x16\x08\x0f\x18\x05' msg = 'please send me your flagdeadbee' msg += chr(ord(msg[15])^ord(res[15])^(16*3-24)) payload3 = '' for i in range(15): payload3 += chr(ord(msg[i]) ^ ord(msg[i + 16]) ^ ord(res[i])) payload3 += chr(16*3 - 24) return msg + payload3 # 'please send me your flagdeadbeed;\x1cZ\r\x0f\x06XPO\x04ER\x07\x0f]\x18' r = remote('47.240.41.112', 12345) context.log_level = 'debug' code = r.recvline()[-34:-2] r.recvuntil('message:\n') r.sendline(fuck().encode('hex')) r.recvuntil('code:\n') r.sendline(code) r.interactive() # remote: ok, here is your flag:sctf{y0u_4r3_7h3_4p3x_ch4mp10n} 

## babygame

### Analysis

  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  #!/usr/bin/python # -*- coding: utf-8 -*- from Crypto.Util.number import * from Crypto.Cipher import AES from Crypto.Random import get_random_bytes from binascii import * from FLAG import flag from MESSAGE import message class telecom: def __init__(self, name): self.name = name self.key = get_random_bytes(16) self.iv = get_random_bytes(16) self.e = 3 p = getPrime(512) q = getPrime(512) self.fn = (p-1)*(q-1) while True: if GCD(self.e, self.fn) != 1: p = getPrime(512) q = getPrime(512) self.fn = (p - 1) * (q - 1) else: break self.d = inverse(self.e, self.fn) self.n = p * q def RSA_encrypt(self, plaintext): assert bytes_to_long(plaintext).bit_length() < 512 a = getPrime(512) b = getPrime(512) m = bytes_to_long(plaintext) c = pow(a * m + b, self.e, self.n) message = 'admin:'+self.name+ ', your ciphertext is: c=' +hex(c)+ '\nwith some parameters:a=' +hex(a)+ ', b=' +hex(b)+'\n' return message def RSA_decrypt(self): pass def broadcast(self): message = self.name+':'+'my pub-key is: '+'e='+str(self.e)+','+'n='+hex(self.n)+'\n' return message def pad(self, msg): pad_length = 16 - len(msg) % 16 return msg + chr(pad_length) * pad_length def unpad(self, msg): return msg[:-ord(msg[-1])] def AES_encrypt(self, message): message = self.pad(message) aes = AES.new(self.key, AES.MODE_OFB, self.iv) return aes.encrypt(message) def AES_decrypt(self, message): aes = AES.new(self.key, AES.MODE_OFB, self.iv) return self.unpad(aes.decrypt(message)) def proof_of_work(): p = getPrime(512) q = getPrime(512) n = p*q e = 65537 fn = (p-1)*(q-1) d = inverse(e, fn) print "pubkey:{e, n}={65537, %s}\n" %hex(n) print 'Give me something you want to encrypt:' sys.stdout.flush() m = int(raw_input()) c = pow(m, e, n) if m == pow(c, d, n): return False return True if __name__ == '__main__': if not proof_of_work(): exit() while True: print 'You have the following options to do:\n[1]monitor\n[2]forge the message' choice = raw_input() if int(choice) == 1: Alpha = telecom('Alpha') Bravo = telecom('Bravo') Charlie = telecom('Charlie') print Alpha.broadcast() print Bravo.broadcast() print Charlie.broadcast() print Alpha.RSA_encrypt(message) print Bravo.RSA_encrypt(message) print Charlie.RSA_encrypt(message) print 'Alpha:David, make sure you\'ve read this:' + hexlify(Alpha.AES_encrypt(message))+'\n' elif int(choice) == 2: print 'you can send message to David now:' input_cipher = raw_input() if Alpha.AES_decrypt(unhexlify(input_cipher)) == message.replace('afternoon', 'morning'): print 'you made it, this reward is prepared for you:' + flag exit() else: print 'you failed' exit() else: exit() 

• 注意到e=3，低加密指数。
• 需要伪造对message AES_OFB模式加密后的密文，使得解密后的明文中的afternoon被篡改为morning

### RSA attack

1. 计算所有n的乘积(n1×n2×n3)
2. 用CRT（中国剩余定理）计算每一个满足条件的T
3. 建立在模N下的多项式环
4. 计算每一个g=(a*x+b)^3-c，这里x就是我们想要的message
5. 计算Ti*gi的和（多项式）并赋值给g
6. 将多项式的最高次项系数化简为1
7. 寻找g的根，多半就是message了

sage代码如下：

  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  n=[82032188601940227752297417081294226543597575504416918007449661834299359067950465277706498580089107996755263427091915970632797292872337319081745842487600650365878082117843668748166556806508008992831799872668452888180728669229746719472110704095075270054792936797172777444638714087380138926023368608670981217091L, 144790109105696916737182878418639456117731330157011040204957460047368669964683349809310287923136309839414697358993776555550819796186587083349149593331591983649252876768081158685346872502328624435541992264407180812711658502822714431271074073131726414451778163016485973268562068628815869252990930579057754896173L, 75291463839461164667469229834843531305640509692662939401339536264435630748347655598022583030492163266505500249672170695051585801149706658572170917049940314913097219983077566373502443956836685905331660776209201294705162873672584599713463731511599324513575176660760395849807244914156996168333606402035878533381L] c=[67497575318327879887596391364750753705169316916381036313287449919879742983169383559661964321852173414328395486815887056253402772840945029491705527313929081200464807407660414760161256035556293097461881324625478369607471130614351104463500599958969159169050874869751290896066581553838854811211907890750382746511L, 61417831208102453560914910052558296402381558961421547405790778254948342894828953024945127165546949565456233519419089997499796829911888055718138539158703076265672618023467204457469261580970191667410598385021272475612274977806376487258894705386083011345682311011008867926893257606509774484971214854873119396523L, 59139963329969277014867029295568306182785272886586884034466445222852652054855577647906813408336405743993989682438127549115465873135913639429070056018223773094951946677500375796734667908820959638217714514827653064127798201054131814345268242102046781245681177963062451193062599946629137832003277003715562783676L] a=[10690284821425810281664680252419661592694244929597744471278947260947912212068164535406286136913239607137611205694268949515679703337156206775167860560960531L, 7084608813044653312908744751862853435370315673659572445175422987292025037024211691353987001505135183178528203370140920842675898979940113026011801133323387L, 7109556811500607022678698446990028501935112258837085372401389025171854709554488399418026529159439666193759252114352506000602595045828924640827082875525761L] b=[8978952666402441172502571446625322184642731589908616056188753886315351207063560919714949439324395532521646399347732857483571187621924964620683026077931937L, 7161265246275328861792856065576124793212521627707981245532742473215873826957088742546550304939190194348241371526295386537134008106992791660625241828335409L, 10713585141780358045259127130466271189717723982908989041527459583656559664545085864785815191726519183276131221864053677348130406321637993310732667315632693L] from functools import reduce import gmpy2 def modinv(a, m): return int(gmpy2.invert(gmpy2.mpz(a), gmpy2.mpz(m))) def chinese_remainder(n, a): sum = 0 prod = reduce(lambda a, b: a * b, n) # 并行运算 for n_i, a_i in zip(n, a): p = prod // n_i sum += a_i * modinv(p, n_i) * p return int(sum % prod) T = [] T.append(chinese_remainder([n[0],n[1],n[2]],[1,0,0])) T.append(chinese_remainder([n[1],n[0],n[2]],[1,0,0])) T.append(chinese_remainder([n[2],n[1],n[0]],[1,0,0])) N = n[0]*n[1]*n[2] P. = PolynomialRing(Zmod(N)) g=0 for i in range(3): g+=((a[i]*x + b[i])^3 - c[i])*T[i] g = g.monic() print g.small_roots() # [670865060925536167183341633904872636604138549784041874166444071991777516769578599095298315216573752629227374] 

long_to_bytes转出来得到message:I will send you the ticket tomorrow afternoon

### AES attack

key_stream = AES_cipher ^ pad(message)

  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  from pwn import * from Crypto.Util.number import * from Crypto.Util.strxor import strxor from binascii import * r = remote('47.240.41.112', 54321) # context.log_level = 'debug' r.recvuntil("encrypt:\n") r.sendline("1"*1000) r.recvuntil("[2]forge the message") r.sendline("1") # n, c, a, b = [],[],[],[] # r.recvuntil("n=") # n.append(int(r.recvline()[:-2],16)) # r.recvuntil("n=") # n.append(int(r.recvline()[:-2],16)) # r.recvuntil("n=") # n.append(int(r.recvline()[:-2],16)) # for i in range(3): # r.recvuntil("c=") # c.append(int(r.recvline()[:-2],16)) # r.recvuntil("a=") # a.append(int(r.recvuntil(",")[:-2],16)) # r.recvuntil("b=") # b.append(int(r.recvline()[:-2],16)) r.recvuntil("this:") AES_cipher = r.recvline()[:-1] # pad_message = "I will send you the ticket tomorrow afternoon\x03\x03\x03" # forge_message = "I will send you the ticket tomorrow morning\x05\x05\x05\x05\x05" cipher = unhexlify(AES_cipher) k_stream = strxor(cipher, 'I will send you the ticket tomorrow afternoon\x03\x03\x03') forge_cipher = strxor(k_stream, "I will send you the ticket tomorrow morning\x05\x05\x05\x05\x05") payload = hexlify(forge_cipher) r.recvuntil("[2]forge the message") r.sendline("2") r.recvuntil("now:") r.sendline(payload) r.interactive() # you made it, this reward is prepared for you:sctf{7h15_ch4ll3n63_15_n07_h4rd_f0r_y0u_r16h7?}