CTF
首页 > 安全文摘 > CTF> 正文

2016 HCTF Crypto 出题总结

今年犯懒了所以只出了3题RSA的密码学题目, 出题思路来源于协会上一届的学长 @Mystery Of Panda 关于RSA后门的毕业设计.

作者:kong来源:paper.seebug.org|2016-11-30 12:34:37

今年犯懒了所以只出了3题RSA的密码学题目, 出题思路来源于协会上一届的学长 @Mystery Of Panda 关于RSA后门的毕业设计.

Crypto So Interesting

题目: https://github.com/Hcamael/ctf-library/tree/master/RSA1

payload: https://github.com/Hcamael/ctf-library/blob/master/RSA1/rsa1_payload.py

出题时预测的分数在300分左右, 不过看完选手的wp后发现这题出现了重大失误, 现在来看, 这题只值150分左右, 但是实际情况只有23个队解出了该题.

本题思路来源: 基于隐藏指数的RSA-HSDβ算法, 全称为隐藏小私有指数δ的RSA后门密钥生成算法.

该算法依赖于wiener小指数攻击方法

后门生成流程:

其中β是在2^(k-1) ± 2^(k/2)范围内的素数, 转置函数的作用是在β非常大的情况下, 返回值可以认为是PRP(Pseudo-Random Permutation). 转置函数可以有好几种形式, 我选取的是一种比较简单的转置函数.

从上面的流程可以看出这题非常的简单, 要逆向也是很容易的, 所以该题为本届HCTF密码学的签到题

逆向思路:

从上图可以看出本题只涉及到了wiener算法, 难度差不多是150左右

出题时本来是准备考两种算法的, 一种是wiener算法, 一种是Riemann's hypothesis and tests for primality, payload中的divide_pq函数, 已知e, d, n质因数分解p和q(http://www.di-mgt.com.au/rsa_factorize_n.html)

原本设计着算出(ϵ, δ)后, 根据(ϵ, δ, n)分解出q和p, 但是出题失误, 导致只需要wiener算法就能getflag

PS1: 不过还是出现了非预期, ROIS的dalao利用wiener算法分解出p和q, https://github.com/Hcamael/ctf-library/blob/master/RSA1/rsa_s.py

PS2: 基于隐藏指数的RSA后门生成算法除了本题涉及的还有RSA-HSPEβ和RSA-HSEβ

Crypto So Cool

题目: https://github.com/Hcamael/ctf-library/tree/master/RSA2 payload:

https://github.com/Hcamael/ctf-library/blob/master/RSA2/rsa2_payload.py
https://github.com/Hcamael/ctf-library/blob/master/RSA2/rsa2_payload.sage
出题时预测的分数在400分左右, 实际情况只有7个队解出了该题. 和预测差不多, 最后放了一波hint, 要不然可能会更少.

本题思路来源: 基于隐藏素数因子的RSA-HPβ算法

该后门算法依赖于Coppersmith partial information attack算法, sage实现该算法

后门生成流程: 

该算法的核心在于把p的前半部分比特隐写到n中

τ的长度为k/16比特

μ的长度为5k/16比特

λ的长度为5k/8比特

所以n的长度为k比特

p * (q xor random(k/8比特长度))的前3k/8比特的值是不变的

所以可以成功把τ, μ隐写到n中

逆向思路:

该题的难点主要在于Coppersmith partial information attack算法, 能在放hint前做出的队伍都是在github上找到了该算法的脚本 https://github.com/Gao-Chuan/RSA-and-LLL-attacks

Crypto So Amazing

题目: https://github.com/Hcamael/ctf-library/tree/master/RSA3

payload:

https://github.com/Hcamael/ctf-library/blob/master/RSA3/rsa3_payload.py
https://github.com/Hcamael/ctf-library/blob/master/RSA3/rsa3.sage
出题时预测的分数在450分左右, 不过却没有能做出来, 我知道的几个队都是被上一题的脚本给坑了

本题思路来源: 基于有限域F(2^m)上椭圆曲线的RSA后门生成算法

流程图懒得画了, 上一题的后门算法看懂了, 这题去看代码也不难, 主要是通过Diffie–Hellman key exchange算法生成私钥作为种子生成伪随机数, 私钥很好求, 本题的难点跟上题一样同样在于Coppersmith partial information attack算法

上一题我故意改简单了, 已知p的前640比特, 所以可以很容易通过https://github.com/Gao-Chuan/RSA-and-LLL-attacks这个脚本恢复出完整的p

但是这题已知p的前576bit, github上的那个脚本就跑不出来了

这部分是出题时无意间挖出的坑, 因为我并不知道github上的这个脚本, 在我预想中能做出rsa2的基本都是能做出rsa3的

这题还有一个坑点

sage和python 用相同的seed生成的随机数不一样, 所以在payload中我使用了python生成随机数

总结

本届HCTF的Crypto计划的考点是Coppersmith partial information attack算法和Riemann's hypothesis and tests for primality算法, 不过无奈由于出题失误第二个算法没考成

【责任编辑:kong 】

分享:

安全快讯+更多

多少次,她说是在工作,但是诡异的第六感告诉我们,她在撒谎...
安识科技,是一家专注于账号安全、企业风险评估的技术型企业。旗下拥有基于云+端的自研产品多因素令牌、基于多重检测引擎的伏特漏洞扫描云平台等!
近日,国家信息安全漏洞共享平台(CNVD)收录了CNVD白帽子(ID:ayound)报送的Jackson框架enableDefaultTyping方法反序列化漏洞(CNVD-2017-04483)。
又公开了一波NSA黑客工具,可供下载;Word曝0day漏洞,打开文档就自动安装恶意程序;iOS 10.3.1高危WiFi芯片漏洞.
由上海GRCC公司主办,美国AutoHarvest协会、上海市信息服务业行业协会协办,由美国新思科技(Synopsys, Inc)、Green Hills Software, Inc.等联合赞助的2017 第二届中国汽车网络信息安全峰会于2月23日-24日在上海浦东顺利召开。