看雪2022 KCTF 秋季赛 | 第四题设计思路

WriteUp 1周前 admin
38 0 0
看雪 2022 KCTF秋季赛 于11月15日中午12点正式开赛!比赛延续上一届的模式并进行优化,对每道题设置了难度值、火力值、精致度等多类积分,用规则引导题目的难度和趣味度。大家请注意:签到题将持续开放,整个比赛期间均可提交答案,获得积分哦~

今日中午12点,第四题《治水搁浅》已截止答题,此题攻破数为0,想必还是很有难度的。接下来一起来看看本题的设计思路吧~



出题团队简介


第四题《治水搁浅》出题方 98k 战队。


战队介绍:我们是来自【中国科学院信息工程研究所】的研究生,平时爱好打CTF。


战队成员id:

队长:全盲法师(其他id:lyciumlee)

队员:rmb122

队员:roadicing

队员:GreatIchild (其他id: Ichild)

队员:c10v3r


看雪2022 KCTF 秋季赛 | 第四题设计思路

*点击可查看大图



赛题设计思路


本题主要实现了关于多项式运算和向量运算的相关考点,考察选手在逆向过程中对常见抽象代数结构/运算在二进制层面的特征识别和对基于代数构建的密码学场景的分析能力。


题目首先接收一个来自用户的长度为 78 字节的输入,取去掉前缀和后缀之后的中间的 72 字节,将其先按照 16 进制形式转换成一个 288 比特的大整数,然后对该数进行 RSA - 3840 加密,得到一个 3840 比特的加密结果,然后将该加密结果代入 check 函数检查其是否正确。


check 函数首先取 RSA 加密后的前 1920 比特,将其转化为一个 1920 比特的大数后代入某一 verify 函数中进行验证,并根据其返回结果是否为True来判定是否通过验证。


注意到这里存在对同一 verify 函数的两次调用,其中第一次调用所有传参均为硬编码,因此为一个恒成立的调用,该调用主要是为了帮助选手理解该 verify 通过的原因。


通过分析,可以看出这里主要实现了yige Schnorr 签名的验签过程,我们传入的 1920 比特的输入位于 verify 函数 API 中的私钥参数位置,因此这里的本质就是预期用户输入一个私钥,使得程序用该私钥对某一硬编码的消息进行签名,然后用一硬编码的公钥进行验签,若验签通过则返回True,因此选手的任务就是需要根据 Schnorr 签名/验签的流程和已知的硬编码数据恢复出私钥的值。


Schnorr签名的密钥生成/签名/验签过程可以参考:https://en.wikipedia.org/wiki/Schnorr_signature


根据该运算过程,可知存在表达式 (1) 成立:

看雪2022 KCTF 秋季赛 | 第四题设计思路

其中:

看雪2022 KCTF 秋季赛 | 第四题设计思路


根据题目提供的硬编码数据,可知这里我们知道 200 次签名的结果,即我们知道 200 组的看雪2022 KCTF 秋季赛 | 第四题设计思路,要求我们恢复出私钥x,注意到这里的每个ki并不是一个直接生成的随机数,而是由若干看雪2022 KCTF 秋季赛 | 第四题设计思路下的随机数累加而成的,那么这里我们可以尝试采用[子集和问题]的思想,通过格基规约的形式恢复出ki相关的信息,继而恢复出私钥x。

看雪2022 KCTF 秋季赛 | 第四题设计思路

*点击可查看大图


此时如果将表达式转移到模下的同余式:

看雪2022 KCTF 秋季赛 | 第四题设计思路


看雪2022 KCTF 秋季赛 | 第四题设计思路


该问题可以通过 Nguyen-Stern 算法求解,即通过构造两次垂直格的形式进行 [LLL 格基规约],如图 1 所示,详细分析过程可参考[该文献](https://eprint.iacr.org/2020/461.pdf)。


看雪2022 KCTF 秋季赛 | 第四题设计思路

然而该表达式同本题中的场景存在一定差异(本题中还引入了独立的加法运算),注意到上述论文中还提到了关于隐式子集和问题的一个变种场景的讨论,即引入了加法运算后的仿射隐式子集和问题(affine hidden subset sum problem


如表达式 (4) 所示,论文中在对该问题的讨论中引入了关于 Schnorr 签名场景的 case study,该场景和我们本题中的场景是一致的,根据论文中的分析思路,该问题同样可以通过构造两次垂直格按照 Nguyen-Stern算法的思路求解,如图 2 所示,详细分析过程可参考该文献(https://eprint.iacr.org/2020/461.pdf)

看雪2022 KCTF 秋季赛 | 第四题设计思路

对于通过该方法求出的矩阵C,满足:
看雪2022 KCTF 秋季赛 | 第四题设计思路

看雪2022 KCTF 秋季赛 | 第四题设计思路

我们将看a成未知向量,解方程即可得到a的值,此时将代回 (4) 式,即可求出私钥x的值。这里需要注意的是,若求出的x的比特数小于 1920 比特,则是由于 check 函数中取的前 1920 比特转化为整数后的值大于p。

因此要恢复出真正的前 1920 比特的值,实际为求出的x的值加上i倍的q,鉴于这里的i值很小(本题中1=3),因此我们可以对i进行穷举来恢复真正的前 1920 比特,关于上述过程的代码实现详见solver.sage 文件。

回到 check 函数,check 函数接下来取 RSA  加密后的后 1920 比特,并最终检查表达式 (6) 是否成立:
看雪2022 KCTF 秋季赛 | 第四题设计思路
其中:
看雪2022 KCTF 秋季赛 | 第四题设计思路
看雪2022 KCTF 秋季赛 | 第四题设计思路

看雪2022 KCTF 秋季赛 | 第四题设计思路

看雪2022 KCTF 秋季赛 | 第四题设计思路

看雪2022 KCTF 秋季赛 | 第四题设计思路

看雪2022 KCTF 秋季赛 | 第四题设计思路

其中:
看雪2022 KCTF 秋季赛 | 第四题设计思路

看雪2022 KCTF 秋季赛 | 第四题设计思路

看雪2022 KCTF 秋季赛 | 第四题设计思路

看雪2022 KCTF 秋季赛 | 第四题设计思路

看雪2022 KCTF 秋季赛 | 第四题设计思路
*点击可查看大图

前后 1920 比特各恢复完成之后,我们将其按二进制流拼接成一个 3840 比特的数,该数即为用户输入经过 RSA-3840 加密后的密文,由于 RSA 的私钥已知,因此我们对该密文解密,即可得到真正的用户输入,将该用户输入按序列号格式转化为序列号提交即可。

序列号:KCTF{B97E6ACEAC32A162F421D64410BB0853CD58561582244F594A95BCC262A5B4F7517D9DB1}

看雪2022 KCTF 秋季赛 | 第四题设计思路


看雪2022 KCTF 秋季赛 | 第四题设计思路

第五题《灾荒蔓延》比赛正在进行

https://ctf.pediy.com/game-season_fight-220.htm
欢迎参与和围观看雪2022 KCTF 秋季赛 | 第四题设计思路


看雪2022 KCTF 秋季赛 | 第四题设计思路
- End -


看雪2022 KCTF 秋季赛 | 第四题设计思路


看雪2022 KCTF 秋季赛 | 第四题设计思路

球分享

看雪2022 KCTF 秋季赛 | 第四题设计思路

球点赞

看雪2022 KCTF 秋季赛 | 第四题设计思路

球在看



看雪2022 KCTF 秋季赛 | 第四题设计思路
“阅读原文查看详情!

原文始发于微信公众号(看雪学苑):看雪2022 KCTF 秋季赛 | 第四题设计思路

版权声明:admin 发表于 2022年11月25日 下午6:02。
转载请注明:看雪2022 KCTF 秋季赛 | 第四题设计思路 | CTF导航

相关文章

暂无评论

暂无评论...