首页
社区
课程
招聘
[原创]第十二题 尊严之战 做不出来是不是就没尊严了?
发表于: 2022-6-7 23:02 13250

[原创]第十二题 尊严之战 做不出来是不是就没尊严了?

xym 活跃值
4
2022-6-7 23:02
13250


到手的英文提示很奇怪,翻译软件说是需要正确时间以获得随机数种子,或者是攻击他的hash函数。IDA打开后反编译的函数很友好,主函数确认输入为32字节后进行了两次判断,第一次就是判断是否和预期的随机数得到预期的运算结果,第二次判断输入后的hash值是否等于预期。值得一提的是这两个判断是或者的关系,也就是说只要满足一个条件即可:满足特定hash的32字节字符串肯定不止一个,这是不是意味着可以说这道题肯定是多解?
言归正传,第一次的运算在sub_140000478函数里,首先调用std::_Random_device()生成一个随机数,然后利用拓展成了长度为624的数组,然后利用sub_140000E94不断生成随机数(最后根据关键常数百度出来这是MT19937伪随机数生成算法),该函数调用的sub_14000198C很有规律,基本可以利用前624个返回值去预测后面的值,而题目给的已知值达到1024个,远大于624,但缺点是给的值都模了127,导致随机数的推导规律可能发生了变化。研究了许久之后,始终没发现最终的规律,只好换一个思路。
题目是个32位的程序,所以std::_Random_device()返回的随机数只有32bit,完全可以实现遍历,因此只要把题目中的代码提取出来编写程序实现遍历,应该可以得到所谓的随机数种子,这样参与运算的随机数也就可以确定下来,从而顺利解出答案(感觉又是一个跑废机器的题目)。但是跑的过程很不顺利,甚至可以说跑的怀疑人生。第一遍跑到一半被人拉了闸,只好从头跑,第二遍跑完没有跑出结果,于是重新检查了一遍代码开始跑第三遍,结果还没跑完,一血就已经出来了,而我最终还是没有结果。
第二天下午,二血出来后,我决定不再纠结随机数种子的事情了,继续研究下面的运算。但是这件事情导致了很严重的后遗症:随机数种子跑不出来很可能说明这个程序本身是不可信的,而我不知道不可信的究竟是随机数算法,还是给的随机数值,甚至两者都不可信,我强烈要求作者能在赛后公布这个随机数种子以安抚我这受伤的心灵。
后面的运算其实也不复杂,16的输入加上16的随机数构成一个32的向量。该向量乘上32*32的随机数矩阵后有一半的概率加上29,最后将该结果与已知结果进行比较。该操作重复两次。其中的随机数矩阵就是上文提到的1024个已知值,因此可以很快算出该矩阵的逆矩阵,然后利用该逆矩阵用计算结果计算初始值,两次得到的初始值中前16字节相同的就是答案。由于计算结果有一半的错误率,因此题目的意思可能是(加“可能”两个字是因为这个题目不可信了)需要解两个含错的32元线性方程组。
受限于可怜的数学水平,我连一个含错方程组都不会解,所以只能想其他办法。好在题目给了答案的变异md5值,因此可以遍历一个方程组中所有加29的情况,总共2的32次方种(为啥又是这个数),然后将每个解的前16字节转成字符串进行hash并与答案的hash进行比较从而判断正确解。但由于题目并没有对输入进行严格的限制,所以输入ABCDEF和123456其实是等效的。也就是计算结果如果是0xa1b2c3,那么作者设定的答案可以是“aAbBcC”,也可以是“aAbBc3”,那样hash比对不出来,只好强迫我们去解两个含错方程组。
幸好在机器吱呀吱呀半天之后,终于在跑废之前给出了7032240d5e5a1d0e021c04656d2b7c4c这样的一个结果,而且被看雪认证为正确答案,而不是期望的多解。也许精通md5值构造的大佬们能够通过这个值构造其他相同hash值的32字节字符串?


[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!

收藏
免费 3
支持
分享
最新回复 (1)
游客
登录 | 注册 方可回帖
返回
//