题目内容为：
- 通过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
对于最后一组：
-
计算待填充长度 padding_len = 11 - len(m)
-
填充一个b"\x80"，然后填充(padding_len-1)个(padding_len-1)
-
然后同之前非最后一组的加密，得到最终state
-
取最终state的前11个字节做SHA256，并将结果与最终state的后5个字节连接作为最终MyHash函数返回值
那么哈希函数就分析完了，接下来就是找出哪里能操作一下，从而产生碰撞。
尝试1
首先想的是，最后的填充能不能进行操作。已知TARGET的最后一个分组长度为9字节，那么其填充就为：
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：
- h0的后五个字节为全0
这是因为，原初始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)，只要满足如下要求就可以实现哈希碰撞：
- 进入加的分组前的h与分组加密完成后的h完全相等
什么意思呢？比如我们在初始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：
from Crypto.Util.number import *
from pwn import *
from tqdm import *
from hashlib import sha256
from Crypto.Cipher import AES
from os import urandom
#part1 get_collision
TARGET = b"I think the hash function has no weakness!"
#state
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']
#MITM
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:]
#part2 get_flag
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()
#hash
r.recvline(b"(hex) : ")
r.sendline(msg.hex())
print(r.recvline())