该文章主要记录一些哈希函数相关的趣题
babyhash 题目来源：ISG 2023
题目：
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 143 144 145 146 147 148 import signalimport socketserverfrom Crypto.Cipher import AESfrom Crypto.Util.Padding import padfrom hashlib import sha256from os import urandomimport base64import randomimport stringfrom ecdsa import SigningKeyimport osimport jsonfrom secret import flagclass Hash (): def __init__ (self, data ): self.data = data def digest (self ): data = bytes (self.data) data = pad(data, 16 ) text = b"\x00" * 16 hash_result = b"" for i in range (0 , len (data), 16 ): key = data[i:i+16 ] text = AES.new(key, AES.MODE_ECB).encrypt(text) hash_result += text return hash_result class Task (socketserver.BaseRequestHandler): def __init__ (self, *args, **kargs ): super ().__init__(*args, **kargs) def timeout_handler (self, signum, frame ): raise TimeoutError def proof_of_work (self ): random.seed(urandom(8 )) proof = "" .join( [random.choice(string.ascii_letters + string.digits) for _ in range (20 )] ) digest = sha256(proof.encode()).hexdigest() self.dosend("sha256(XXXX + {}) == {}" .format (proof[4 :], digest)) self.dosend("Give me XXXX:" ) x = self.request.recv(10 ) x = (x.strip()).decode() if len (x) != 4 or sha256((x + proof[4 :]).encode()).hexdigest() != digest: return False return True def dosend (self, msg ): try : self.request.sendall(msg.encode("latin-1" ) + b"\n" ) except : pass def sign (self, sk, msg ): return sk.sign(msg, hashfunc=Hash) def verify (self, vk, msg, signature ): try : vk.verify(signature, msg, hashfunc=Hash) except : return {"status" : "error" , "msg" : "Invalid signature" } msg = json.loads(msg.decode()) if not msg.get("admin" , False ): return {"status" : "error" , "msg" : "You are not admin" } else : return {"status" : "success" , "msg" : "You are admin" , "flag" : flag} def challenge (self, sk, vk ): while True : self.dosend("Input your choice:\n[1] Sign in\n [2] Verify\n [3] Exit" ) choice = self.request.recv(2 ).strip() choice = int (choice.decode()) if choice == 1 : self.dosend("Input your username:" ) buf = b"" while len (buf) < 1000 : buf += self.request.recv(1 ) if buf[-1 :] == b"\n" : break name = "" .join( chr (x) for x in buf if chr (x).isalnum()) msg_to_sign = {"admin" : False , "username" : name} msg_to_sign = json.dumps(msg_to_sign).encode() sig = self.sign(sk, msg_to_sign).hex () info = {"sig" : sig} self.dosend("Your signature: {}" .format (json.dumps(info))) if choice == 2 : self.dosend("Input your msg and sigature in JSON form:" ) buf = b"" while len (buf) < 1000 : buf += self.request.recv(1 ) if buf[-1 :] == b"\n" : break buf = buf.decode() print ('buf' , buf) try : info = json.loads(buf) except : self.dosend("Invalid JSON" ) continue msg = info['msg' ].encode() sig = bytes .fromhex(info['sig' ]) send_info = self.verify(vk, msg, sig) self.dosend(json.dumps(send_info)) if choice == 3 : self.request.close() return def handle (self ): try : signal.signal(signal.SIGALRM, self.timeout_handler) signal.alarm(60 ) if not self.proof_of_work(): self.dosend("You must solve proof of work" ) return signal.alarm(60 ) sk = SigningKey.generate() vk = sk.get_verifying_key() self.challenge(sk, vk) except TimeoutError: self.dosend("Timeout" ) return except Exception as e: print (e) self.dosend("WTF?" ) self.request.close() class ThreadedServer (socketserver.ForkingMixIn, socketserver.TCPServer): pass if __name__ == "__main__" : HOST, PORT = "0.0.0.0" , 10500 server = ThreadedServer((HOST, PORT), Task) server.allow_reuse_address = True server.serve_forever()
梳理一下题目任务：
通过proof
用现有库ecdsa生成一个签名对象sk，同时生成对应的验签对象vk后，进入challenge
在challenge中，输入1，可以输入一个username，对 {"admin": False, "username": name}形式的msg进行签名，靶机返回签名值；输入2，可以输入一个JSON形式的数据对象如：{'msg': '{"admin": false, "username": name}', 'sig': sig}，靶机将对输入的数据对象进行验签。
如果验签通过，且”admin”值不为false，则得到flag。
而在本题的签名流程中，哈希函数是自定义的，如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Hash (): def __init__ (self, data ): self.data = data def digest (self ): data = bytes (self.data) data = pad(data, 16 ) text = b"\x00" * 16 hash_result = b"" for i in range (0 , len (data), 16 ): key = data[i:i+16 ] text = AES.new(key, AES.MODE_ECB).encrypt(text) hash_result += text return hash_result
也就是把msg的内容分为长度为16的若干组，并分别当作AES的key并对b”\x00” * 16进行AES加密，得到的结果拼接起来就是哈希值。
也就是说，我们的任务就是构造一个msg，使得其自定义哈希值与{"admin": false, "username": name}相同，同时满足”admin”的值不为false。
首先有一点就很奇怪：这个哈希函数长度会随着data的长度变化而变化。也就是说，如果给一个足够长的data，就会产生一个足够大的哈希值，现有的ecdsa库是否会对这种情况进行处理？
结果发现真的会处理，如下图中所示，allow_truncate在sign函数中是默认为true的，而baselen经测验是24，也就是说，如果哈希超长，他只会取前24个作为摘要值：
这也就是说，题目中自定义的哈希函数不管产生多长的字节流，由于哈希摘要只取24个，因此只有前两个分组的data会对最终被使用到签名里的哈希值产生影响,也就是说我们传入的JSON对象的第三十二个以后的字符都不会影响验签。而观察verify函数，他其实是先把传入的msg当作字节串进行验签，再把其当作JSON对象检验是否”admin”为false：
1 2 3 4 5 6 7 8 9 10 def verify (self, vk, msg, signature ): try : vk.verify(signature, msg, hashfunc=Hash) except : return {"status" : "error" , "msg" : "Invalid signature" } msg = json.loads(msg.decode()) if not msg.get("admin" , False ): return {"status" : "error" , "msg" : "You are not admin" } else : return {"status" : "success" , "msg" : "You are admin" , "flag" : flag}
但是JSON对象是可以覆盖前面的”admin”的值的，也就是说，我们将msg的值设置成下面这种形式，再传给靶机：
1 {"admin" : false, "username" : name, "admin" : name}
那么对于服务器来说，其验签是用的上面这个字符串 的自定义哈希的前32位来进行验签，因此当然能验签通过。而在验签通过后，他把这个字符串通过loads转成JSON对象，”admin”的值就被覆盖成为了name，因此就能得到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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 from Crypto.Util.number import *from pwn import *from tqdm import tqdmfrom hashlib import sha256import jsondef proof_of_work (): table = string.digits + string.ascii_letters temp = r.recvuntil(b"sha256(XXXX + " ) temp = r.recvline() suffix = temp[:16 ].decode() hex1 = temp[20 :].strip().decode() for i in tqdm(table): for j in table: for k in table: for m in table: temp1 = i+j+k+m if (sha256((temp1+suffix).encode()).hexdigest() == hex1): r.sendline(temp1.encode()) return r = remote("node4.anna.nssctf.cn" ,28234 ) proof_of_work() r.recvuntil(b"[3] Exit" ) r.sendline(b"1" ) r.recvuntil(b"Input your username:" ) r.sendline(b"Tiffany" ) r.recvuntil(b"signature: " ) sig = r.recvline().strip().decode()[9 :-2 ] r.recvuntil(b"[3] Exit" ) r.sendline(b"2" ) r.recvuntil(b"JSON form:" ) msg = '{"admin": false, "username": "Tiffany", "admin": "Tiffany"}' msg_to_sign = {"msg" : msg, "sig" : sig} print (msg_to_sign)msg_to_sign = json.dumps(msg_to_sign).encode() r.sendline(msg_to_sign) r.recvline() print (r.recvline())r.close()
Ezhash 题目来源：强网拟态 2021
题目：
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 import os, random, hashlib, stringfrom signal import alarmfrom Crypto.Cipher import AESfrom binascii import unhexlifyfrom secret import flagclass MyHash : def __init__ (self ): self.cipher = AES.new(b"a" *32 ,AES.MODE_ECB) self.state = b"\x00" *16 def enc (self,m ): return self.cipher.encrypt(m) def upadteState (self,m ): m += b"\x00" * 5 state = bytes ([(a+b+2 )%256 for a,b in zip (self.state,m)]) self.state = self.enc(state) def finalUpdateState (self,m ): padding_len = 11 - len (m) % 11 m += bytes ([0x80 ] + [padding_len - 1 ] * (padding_len - 1 )) self.upadteState(m) def genResult (self ): result = hashlib.sha256(self.state[:11 ]).digest() + self.state[11 :] return result def hash (self,msg ): self.state = b"\x00" * 16 length = len (msg) // 11 for i in range (length): subMsg = msg[11 *i:11 *(i+1 )] self.upadteState(subMsg) finalMsg = msg[length*11 :] self.finalUpdateState(finalMsg) return self.genResult() def proof_of_work (): random.seed(os.urandom(8 )) proof = '' .join([random.choice(string.ascii_letters+string.digits) for _ in range (20 )]) digest = hashlib.sha256(proof.encode()).hexdigest() print ("sha256(XXXX+%s) == %s" % (proof[4 :],digest)) print ("Give me XXXX:" ) x = input () if len (x) != 4 or hashlib.sha256((x + proof[4 :]).encode()).hexdigest() != digest: return False return True def main (): alarm(60 ) if not proof_of_work(): return alarm(10 ) TARGET = b"I think the hash function has no weakness!" try : h = MyHash() h1 = h.hash (TARGET) anotherHash = unhexlify(input ("Please your hash (hex) : " )) if anotherHash != TARGET: h2 = h.hash (anotherHash) if h1 == h2: print (f"Success! Here is your flag : {flag} " ) else : print ("Try again!" ) else : print ("Can't input TARGET!" ) except : print ("Error!" ) if __name__ == "__main__" : main()
题目内容为：
通过proof
输入一个字节串的十六进制编码，该字节串不能等于TARGET
若该字节串的MyHash()值与TARGET相等，则得到flag
也就是说我们要找到一个满足要求的自定义哈希函数的碰撞，那么就要分析一下这个哈希函数。简单来说，该哈希函数首先完成下列准备工作：
把输入的字节串按长度为11分为若干组，最后一组不足11的单独列出
设置固定密钥为b”a”*32的AES
设置初始状态state，为b”\x00”*16
准备工作完成后，每一轮做如下加密：
对于非最后一组：
依次取分组中的每个长度为11的字节串，在后面填5个b”\x00”使得长度为16
将该分组与当前state逐字节相加后再加2(模256加法)
用AES对上述值加密，作为新的state
对于最后一组：
那么哈希函数就分析完了，接下来就是找出哪里能操作一下，从而产生碰撞。
尝试1 首先想的是，最后的填充能不能进行操作。已知TARGET的最后一个分组长度为9字节，那么其填充就为：
1 b"weakness!" + b"\x80" + b"\x01"
那么就发现长度方面没什么操作的办法，因为一改变长度，最后一字节就不一样了，那么就肯定不能期望AES后还能得到相同结果。
尝试2 那么就只能从非最后一组的加密入手，画一下对于TARGET的加密流程图：
其中，m1、m2、m3、m4是TARGET的分组，h1、h2、h3、h4是每个state，这些都是可以求出的。
而看图容易看出，我们只要让任何一次加密开始前的state与给定的h1、h2、h3或h4相等，那么在之后的加密过程中就会保持完全一致。而h1、h2、h3、h4是AES得到的，没有办法直接操作，那么要使其相等，就只能让AES加密前的t1、t2、t3或t4相等。
所以第一个朴素的想法就是：有没有办法通过改变m1，使得改变后得到的t1’仍然与t1相等？显然这完全不可能，因为要让t1=t1’，就必须有m1=m1’(mod 256)，而要有m1=m1’(mod 256)其实就必须有m1=m1’，所以m1一点都不能动。
然后就想到，既然只要让t1’与t1相等即可，我们完全可以在第一组之前添加分组，而h1之后分组的我们已经完全不需要关心了。比如我们添加m0，使得：
有没有机会同时改变m0和m1，使得这样得到的t1’与原t1相等呢？那么要确认以下两点：
h0是不可控的，因为经过了AES加密
t1是已知的
那么要得到h0，我们其实只能采取随机生成m0的方式来得到不同的h0，但是我们可以通过改变m1，来取到不同的t1’，期望其最终与原t1相同。那么其实很明显，只有生成的h0满足下面的性质，我们才能取得符合要求的t1：
这是因为，原初始state为16字节全0，而m1本身长度只有11，后五个字节也为填充的0。也就是说，前面11个字节我们可以通过得到的h0，去对应改变m1得到，但是后面五个字节是我们控制不了的，我们只能通过随机产生的方式，去爆破出一组AES加密后后五个字节均为0的h0.如果把AES加密得到的串视为随机生成的字节的话，那么随机生成，得到的串满足要求的概率也就是五个字节为0的概率，也就是1/2^40。而以生日攻击的理论，我们要产生2^40个随机串m0，才有大于50的概率获得满足要求的h0，这个范围显然过大了。
同理，如果想要生成t2’、t3’之类，使其与原t2或t3相等，要求也是一样的：生成的前一组h’的最后五个字节需要与计算得到的完全相同，概率都是1/2^40。
这个方法虽然看上去可行，但由于复杂度过大而不可接受的，因此还要想其他办法。
尝试3 把问题再具体化一点，我们其实可以在初始的TARGET中加任意个分组(每组长度为11)，只要满足如下要求就可以实现哈希碰撞：
什么意思呢？比如我们在初始TARGET的加密流程中，往箭头处加入几个新的明文分组：
可以看到，对于新加入的几个明文分组，其输入的state值是h1，而我们只要保证这几个明文分组的最终输出也是h1，后续的加密state就完全一样了，因此能够得到哈希碰撞。
而如果复现过前几天的CBCTF的CB_cipher一题的话，就容易反应过来这也可以用中间相遇攻击来缩小复杂度。具体来说，刚才我们想要通过新加入两组m，并控制这两组m的值，来得到一个相同的t，从而保证后续哈希相等。而现在我们完全可以在箭头处加入三组m，然后用第一组m和第三组m进行中间相遇攻击，从而计算出中间的满足要求的第二组m，这样一来，本身需要2^40次才有大于50的概率找到一组符合要求的m，现在可以用2*2^20次就可以达到这个概率。
具体来说，我们用如下方式控制三组生成的m(分别叫做m1、m2、m3，请注意与本身TARGET的分组做区别)，则输入这个分组的state为h1，需要输出的state也为h1：
随机生成2^20个m1，并加密其得到2^20个不同的temp1，并建立字典
随机生成2^20个m3，并AES解密h1后，减去m3再减去2；对这个值再进行AES解密，得到2^20个不同的temp2
如果第二步得到的某个值temp2与第一步的字典中的某个值temp1的后五个字节满足：temp2 = temp1 + 2，那么我们就可以由这一组值计算出符合要求的m2。这是因为，m2长度为11字节，进行加密时后五个字节需要填充全0，因此只要后五个字节满足temp2 = temp1 + 2就是合法的m2
如此一来我们就可以用能够接受的复杂度找出一组哈希碰撞了。需要注意的是，通过proof后只有10s的时间提交哈希碰撞，但是由于TARGET是定死的，所以我们完全可以先找好碰撞，再连接提交。
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 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 from Crypto.Util.number import *from pwn import *from tqdm import *from hashlib import sha256from Crypto.Cipher import AESfrom os import urandomTARGET = b"I think the hash function has no weakness!" h1,h2,h3,h4 = [b'\x82R>?XAY>\xf4\x98\xdd\x1f(\x81{\x15' ,b'o0(;Xf\xea\xe4s\xbf\xab\xd7S\x1b\x02\xca' ,b'\x8a\xb5z\xf9\xca9u<\x82\x81\xe4<\x11\tJ\xbd' ,b'\x8f\xe3\xd9\xbf3\xc2\x11b\xa3\x19\xbeA\xec\xad`J' ] msg = b"" cipher = AES.new(b"a" *32 ,AES.MODE_ECB) def enc (state,m ): m = m + b"\x00" *5 state = bytes ([(a+b+2 )%256 for a,b in zip (state,m)]) return cipher.encrypt(state) def dec (state,m ): temp = cipher.decrypt(state) state = bytes ([(a-b-2 )%256 for a,b in zip (temp,m)]) return state dic = {} for i in trange(2 **20 ): m1_ = urandom(11 ) + b"\x00" *5 dic[enc(h1,m1_)[-5 :]] = m1_ for j in trange(2 **20 ): m3_ = urandom(11 ) + b"\x00" *5 temp = dec(h1,m3_) temp = cipher.decrypt(temp) temp = bytes ([(a-2 )%256 for a in temp]) if (temp[-5 :] in dic.keys()): m1_ = dic[temp[-5 :]] h2_ = enc(h1,m1_) m2_ = bytes ([(a-b)%256 for a,b in zip (temp,h2_)]) msg = m1_[:-5 ] + m2_[:-5 ] + m3_[:-5 ] break msg = TARGET[:11 ] + msg + TARGET[11 :] def proof_of_work (): table = string.digits + string.ascii_letters temp = r.recvuntil(b"sha256(XXXX+" ) temp = r.recvline() suffix = temp[:16 ].decode() hex1 = temp[20 :].strip().decode() for i in tqdm(table): for j in table: for k in table: for m in table: temp1 = i+j+k+m if (sha256((temp1+suffix).encode()).hexdigest() == hex1): r.sendline(temp1.encode()) return r = remote("node4.anna.nssctf.cn" , 28947 ) proof_of_work() r.recvline(b"(hex) : " ) r.sendline(msg.hex ()) print (r.recvline())
MEF 题目来源：TCTF/0CTF 2020 Finals
题目：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 flag = '[REDACTED]' flagnum = int (flag.encode('hex' ),16 ) h = [1 ] p = 374144419156711147060143317175368453031918731002211 m = 16077898348258654514826613220527141251832530996721392570130087971041029999399 assert flagnum < mdef listhash (l ): fmt = "{} " *len (l) s = fmt.format (*l) return reduce(lambda x,y:x*y,map (hash ,s.split(' ' ))) num = 0x142857142857142857 for i in range (num): x = h[i]*p%m x += h[listhash(h)%len (h)] x %= m h.append(x) encflag = h[num] ^ flagnum print encflag
代码很短，几句话就可以讲清楚题目内容：
设置h数组初值为1
循环num次，每次会给h数组append一个新值
h的递推过程为：
1 h[i] = (h[i-1 ]*p + h[listhash(h)%len (h)]) % m
1 2 3 4 def listhash (l ): fmt = "{} " *len (l) s = fmt.format (*l) return reduce(lambda x,y:x*y,map (hash ,s.split(' ' )))
然后，将h的最后一个值与flag异或，给出密文。也就是说我们如果能得到h的最后一个值，就可以将密文异或回去得到flag
那么重点就放在了分析listhash函数上，而listhash的功能就是：把h当前的所有数字以空格分割，并分别计算它们对应的python内置的hash()函数值，并相乘得到最终值后返回。
但是仔细看看就会发现不对劲，比如如果h是：
那么s就是：
注意到最后还有一个空格，因此split后会产生一个长度为4的列表，最后一个元素是空串””。然后hash一下空串果然发现得到的值是0，也就是说，list哈希连乘过后，返回的结果恒为0。因此h的递推过程可以写成：
1 h[i] = (h[i-1 ]*p + 1 ) % m
因此可以知道h[i]其实就是：
这是一个等比数列求和，因此可以用求和公式算出结果是：
所以就能直接算出h[num]，然后异或即得到flag。
exp：
1 2 3 4 5 6 7 8 9 10 11 12 from Crypto.Util.number import *p = 374144419156711147060143317175368453031918731002211 m = 16077898348258654514826613220527141251832530996721392570130087971041029999399 c = 11804007143439251849628349629375460277798651136608332038133488180610375813979 num = 0x142857142857142857 x = ((1 -pow (p, num+1 , m))*inverse(1 -p,m) % m) flag = c ^ x print (long_to_bytes(flag))
