[阅读笔记]《Automatic Problem Generation for Capture-the-Flag Competitions》

  在过去一段时间里,笔者阅读了一些论文,也写了一些阅读笔记,最近想把笔记分享出来,与大家探讨,在鞭策中前行,希望能够坚持下去。原论文请戳这里

简介

  最近本人参加了国内最大型的线上CTF竞赛网鼎杯,这是本人第一次严格意义上的参加CTF竞赛,发现大佬云集,不过在队友的辅助下,本人成功解答了3道逆向题,整队分数也进入了前50名(其实是刚好第50名),当然也发现了国内CTF竞赛中共享flag是那么“流行 ”,接着就有了这篇阅读笔记。这是一篇在2015年发表于 USENIX’15(3GSE 15) 关于自动化生成CTF赛题的文章。CTF线上竞赛越来越流行,但是flag共享(py交易)也越来越多,文章主要介绍了自动化问题生成APG(automatic problem generation)技术,并且讨论了如何应用APG去检测flag共享(py交易)和该技术附带的其他好处和挑战,最后文章将APG技术应用于PicoCTF2014竞赛(一个面向高中和大学生的在线CTF竞赛,卡内基梅隆大学和世界顶级的CTF战队PPP共同举办,2014年参数人数超过10000人,一共3000+队伍),发现并捕获到多起flag共享事件,并对比赛数据进行了详细的分析。其中PicoCTF2014整个平台代码在github上开源。

中文摘要

  计算机安全游戏,尤其是夺旗赛(CTF)越来越流行。传统的CTF竞赛是指提供一组黑客挑战游戏给竞赛者,竞赛者在正确的解答题目后会得到一串文字叫做”flag”,提交给计分服务器将得到分数。在传统的CTF架构中,整个竞赛过程的题目和答案都是相同的。

  在这篇文章中,我们讨论了自动问题生成(APG),一种给定的挑战但(题目和答案)不固定,相当于有很多不同的自动生成的题目实例。APG提供给玩家独特的竞赛体验,同时能够在问题的变化中促进有目的的练习,以确保用户可以复制解决方案的想法。APG也能够赋予管理者一种能力–检测用户是否提交了一个从其他队里py交易来的flag(a copied flag)到服务器。在2014年我们举办了一场大型的CTF竞赛叫做PicoCTF,在比赛中我们统计了flag共享的流行程度。我们的结果表明,提交AGP生成题目的flags,大约0.8%是py交易来的,同时14%的队伍至少提交了一个py交易来的flag。在flag共享事件中,68%的队伍最终自己也解决了题目(笔者注:先提交了py来的flag,然后又提交了自己的flag)。

介绍

  这一节详细介绍了CTF、APG、PicoCTF等概念,并且说明是如何应用APG技术到PicoCTF赛事中,最后说明了文章的贡献(其中结论比较有意思):

  1. 文章详细描述了APG如何运用到PicoCTF赛事中,细节包括表现性能、可拓展性、题目难度的平衡、APG的选择等。
  2. 文章对PicoCTF2014共享flag的事件进行了统计分析,得出一些有意思的结论:不止低分段会py,高分段也存在py交易,并且共享flag的队伍很有可能来自同一学校。
  3. PicoCTF平台在github上开源。

Automatic Problem Generation

  陈述陈述,然后举了一个凯撒密码的例子:服务器首先生成唯一的flag,然后附加到原始明文”the secret pass phrase is”后,接着服务器选取n(26个可能)做为密钥对明文进行加密得到密文,将结果派发给需要挑战的队伍(不同队伍会生成不会的flag和密钥)。这个例子是属于模板自动生成问题( templated autogen problem),也就是一个模子里出来的题目(但是题目不完全相同,答案也不同),能够解决flag共享的作弊问题,但是不能解决解题思路共享的作弊问题,比如该例子虽然各队的flag不一样,但是解题思路都是凯撒密码。模板自动生成问题有2个作用:1)阻止和检测flag coping, 2)找出泄露flag的源。(这里应该很好理解,就是同一道题目,每个队伍的答案都是不一样的flag,这样当提交的是别队解答出来的flag当然就可以检测和阻止啦。泄露溯源的话就是如果同一时间大量的队伍提交同一flag,那么就可以找出这个flag对应的队伍,进而找出flag泄露的原因。文章在下一节举了个例子,当比赛进行到第5天时,突然有一个flag被大量提交,然后举办方发现原来是该flag所属的队伍在YouTube上把flag泄露了,如下图,橙色是不正确的提交,蓝色是正确的提交:)

  接着,文章提出了合成自动生成问题( synthesized autogen problem),是指输入一系列约束条件的组合,然后自动生成题目。能够解决上面的2种作弊问题(共享flag和共享思路),但是生成的题目很难平衡难易,有失公平性。文章制定了一个通用的逆向工程挑战原型(用户必须提供满足不同复杂性约束的输入)、ROP攻击(不同的队伍需利用不同的gadgets和function)、以及隐藏在各种类型图像中的隐写问题。由于这些问题比较复杂,因此很难确保生成的不同实例具有相似的难度。出于这个原因,这些生成的题目没有在PicoCTF2014中使用。不过在未来中,这些题目可能有助于参赛者的练习,帮助其提高安全技能。

  之后,文章讨论了CTF赛事中使用APG题目的一些挑战:

  1. 保持一致的难度。主要是说,自动生成的题目实例可能难度不一样,比如PicoCTF2014的一道XOR异或题,由于自动生成的题目是从0-255中取一个字节与明文进行异或加密,那么对于收到异或字节0题目的队伍,他们拿到的密文就是明文(就不用解密操作了,直接提取flag),造成各题难度不一致。
  2. Bug的预防。APG可能产生非预期的bug,这会给比赛带来一些问题。举例了使用python函数strip()会造成非预期的错误,strip函数是取参数的每个单字节,并去除字符串头尾存在的相同字节。比如 strip(““)的本意是去除html标签,但是其实如果头尾存在t、d字符也会被去掉,而每个队伍拿到的flag都是随机生成并且唯一的,那么可能有些队伍的flag头尾存在t、d字符,被去掉后造成服务器判断flag无效。
  3. 可扩展性和部署。可扩展性是说可能有很多新的特性,平台需要比较容易扩展。部署是另一个新的挑战,因为每道题每个队伍的flag不同,那么flag的生成可能需要绑定队伍的token。

  最后,文章介绍了APG应用于PicoCTF中,并介绍了部分代码的架构,比如一道APG题目,需要一个 generator和一个 grader,generator主要负责生成题目,grader主要负责判断队伍提交的答案是否正确。

Flag Sharing in PicoCTF 2014:

  接下来,作者统计了PicoCTF2014比赛中,flag sharing事件,并进一步对其详细的分析,还对flag泄露事件进行了溯源分析:

  文章表示,有71%的flag共享事件都是出现在同一个学校之间,并且不止低分段有flag共享,高分段也会出现flag共享事件。

讨论:

  作者发现,很多关于flag共享的因素都是PicoCTF唯一的,如:

  1. PicoCTF比赛持续了12天,使得flag不被泄露更具有挑战。
  2. 很多参赛队伍都是来自同一个学校,使得flag共享变动更加容易。
  3. 更多的参赛人员是新手玩家,相比有经验的人,可能更不清楚flag共享的严重性。

  所以,作者认为造成PicoCTF中flag共享频繁出现并且覆盖面广的原因具有唯一性,其他类似的比赛可能很少出现,有也是集中于个别队伍。(本人不这么认为,你懂得)

结束语

  纵观国内的CTF比赛,好像还没有出现一个类似的防作弊技术运用于CTF中,基本都是同一道题同一flag。据我所知,这次网鼎杯比赛中使用了其他手段:1)通过检测pwn题目的流量,来检测是否有队伍进行了作弊,或者答案的泄露;2)同时使用了赛后复查wp的机制来防作弊(不过最后好像没有时间检查wp)。但是这2个方法都具有局限性,比如通过流量只能检测部分pwn的作弊,修改解题的脚本流量就能绕过检测;通过审核wp虽然可以一定程度防止作弊,但是需要大量的人力。攻防是一个持续不断的过程,如何更有效的防止线上CTF的作弊也是值得思考的事情。

坚持原创技术分享,您的支持将鼓励我继续创作!