网站 › 『脱壳破解区』 › 记一次brainfuck的解密思路

高维可破 发表于 2021-5-16 22:51

记一次brainfuck的解密思路

#题目
在python3中运行下边代码，对应到第五关
```
python3 -c "exec(__import__('urllib.request',fromlist='Hacking8 ohye').urlopen('http://i.hacking8.com/static/i2.py').read().decode())"
```
不了解brainfuck也没关系，只需要分析题目中brainfuck vm的逻辑也可以得出代码的含义，再用一点数学知识就可以解决。
下边是对应的代码
```
from sys import stdin
def find_bracket(code, pos, bracket):
    cont = 0
    pair = '[' if bracket == ']' else ']'
    for a, i in zip(code, range(pos, len(code))):
      if a == bracket:
            cont = cont + 1
      if a == pair:
            if cont == 0:
                return i
            else:
                cont = cont - 1
    raise Exception


def prepare_code(code):
    def map_left_bracket(b, p):
      return (b, find_bracket(code, p + 1, b))
    def map_right_bracket(b, p):
      offset = find_bracket(list(reversed(code[:p])), 0, ']')
      return (b, p - offset)
    def map_bracket(b, p):
      if b == '[':
            return map_left_bracket(b, p)
      else:
            return map_right_bracket(b, p)
    return ') else c
            for c, i in zip(code, range(len(code)))]


def read(string):
    valid = ['>', '<', '+', '-', '.', ',', '[', ']', '%']
    return prepare_code()


def eval_step(code, data, code_pos, data_pos):
    c = code
    d = data
    step = 1
    if c == '>':
      data_pos = data_pos + 1
      if data_pos > len(data):
            data_pos = 0
    elif c == '<':
      if data_pos != 0:
            data_pos -= 1
    elif c == '+':
      data += 1
    elif c == '-':
      data -= 1
    elif c == '.':
      print(str(d))
    elif c == '%':
      if len(data) >= data_pos + 1:
            data %= data
    elif c == ',':
      data = ord(stdin.read(1))
    else:
      bracket, jmp = c
      if bracket == '[' and d == 0:
            step = 0
            code_pos = jmp
      elif bracket == ']' and d != 0:
            step = 0
            code_pos = jmp

    return (data, code_pos, data_pos, step)


def shellcode_eval(code, c_pos=0, d_pos=0):
    data =
    while c_pos < len(code):
      (n_data, n_c_pos, n_d_pos, step) = eval_step(code, data, c_pos, d_pos)
      print('eval step:',c_pos, d_pos)
      print('\t => ',n_c_pos, n_d_pos, n_data)
      data, c_pos, d_pos = n_data, n_c_pos, n_d_pos
      c_pos += step
    return str(data)

shellcode = ">>>>[-]++>[-]++++++++>>>>[-]>[-]>[-]>[-]<<<<<<[-][-]+<[->>>>[-]>[-]>[-]<<<<<[-<<[->>>>>+>+<<<<<<]>>>>>>[-<<<<<<+>>>>>>]>+<<<<<]>>>>>[-<<<<<+>>>>>]<<.<<<[-]>>>[-<<<+>>>]>>>+<<<<<<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<[-<<<<<<+>>>>>>]<<[-]>[-]>[-]>[-]<<<<<<<.>>>>[-]+++<<<<[->>>>>+>>>>>+<<<<<<<<<<]>>>>>>>>>>[-<<<<<<<<<<+>>>>>>>>>>]<[-]>[-]>[-]>[-]<<<<<<[-][-]+<[->>>>[-]>[-]>[-]<<<<<[-<<[->>>>>+>+<<<<<<]>>>>>>[-<<<<<<+>>>>>>]>+<<<<<]>>>>>[-<<<<<+>>>>>]<<.<<<[-]>>>[-<<<+>>>]>>>+<<<<<<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<[-<<<<<+>>>>>]<<[-]>[-]>[-]>[-]<<<<<<."
c = read(shellcode)
key = shellcode_eval(c)
```
题目中的 `shellcode`比较长，为了方便分析这里只截取一段，具体以题目中的代码为准

#分析
##分析brainfuck
对应到代码中的 `eval_step` 方法
`>`, `<`分别对应数据指针的自增1 和 自减1
`+`, `-`分别对应当前指针所指数据的自增1 和 自减1
`[...]`   对应于 `while` 循环块
`,` ,`.` 分别对应输入和输出
另外还增加了一个 `%` 的取余操作
嗯，很简单的几个操作，但回过头看 `shellcode` ，还是一脸懵逼...

这里主要有几个难点阻碍我们理解brainfuck代码
1、没有助记符帮我们记住当前操作的数据指针是什么
2、每次增减的大小都是1，对于一个简单如 ` data = n`的赋值操作也需要用一个循环递增n次，既不利于静态分析，也不利于动态调试
3、毕竟不是我们熟悉的语言，理解起需要额外多一层"翻译",如果能直接转换成熟悉的语言 如 python， 理解起来也会直接很多。

##化简brainfuck
根据上述分析的3个问题，采用下边两个方法来解决
1、合并繁琐的增减操作，增减不再是固定的1，可以一步到位。
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;当然这样需要维护一个额外的指针映射表和数据增减映射表
2、第1步化简后还会剩下 `[]`, `+`, `%`, `.`, `.` ,
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;这些可以直接从 `eval_step` 中提取对应的处理语句，
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;直接进行翻译即可得到我们最终需要的python语言
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;只不过对while 要稍微做一点特殊的处理

说了这么多，直接撸代码吧
第1步方法
```
def shrinkBFCode(code):
    cPos2Vars = {}   #位置对应的变量
    cPos2Change = {}#位置中 + 号 增加的值
    varPos = 0
    nCode = []
    incVal = 0
    lc = None
    dataChangeOp = set(['+', '-'])
    dataShiftOp = set(['>', '<'])
    for i in range(len(code)):
      c = code
      if c not in dataChangeOp and lc in dataChangeOp:
            cPos2Change = incVal
            cPos2Vars = varPos
            nCode.append('+')
            incVal = 0
      if c == '>':
            varPos += 1
      elif c == '<':
            varPos -= 1
      else:
            if c in dataChangeOp:
                incVal += 1 if c == '+' else -1
            else:
                #if lc == '>' or lc == '<':
                #    cPos2Vars = varPos
                cPos2Vars = varPos
                nCode.append(c)
      lc = c

    return ''.join(nCode), cPos2Vars, cPos2Change
```

第2步的方法
```
def generatePyCode(shellCode, pVars, pChange):
    pyCodes = []
    bStacks = []
    whileVarCache = {}
    for i, c in enumerate(shellCode):
      d_pos = i if i not in pVars else pVars
      d_change = 1 if i not in pChange else pChange
      indentLevel = len(bStacks)
      indentStr = ' '*(4*indentLevel)
      if c == '[':
            pyCodes.append('{}while data[{}] != 0:'.format(indentStr, d_pos))
            bStacks.append((c, i))
            whileVarCache = {}
      elif c == ']':
            if bStacks[-1] != '[':
                raise Exception('miss match of {}] found between {} and {}'.format(bStacks[-1], bStacks[-1], i))
            cNum = i-bStacks[-1]   
            if cNum == 2:
                del pyCodes[-1]
                del pyCodes[-1]
                d_pos_l = i-1 if i-1 not in pVars else pVars
                pyCodes.append('{}data[{}] = 0'.format(' '*(4*(indentLevel-1)), d_pos_l))
            whileCode = shellCode+1 : i]
            if cNum>2 and '[' not in whileCode and not '%' in whileCode:# nested loop is a bit complicated, just skip
                loopCondvar = bStacks[-1]
                d_pos_l = loopCondvar if loopCondvar not in pVars else pVars
                whileVars = whileVarCache]
                cVarChange = whileVars
                # remove statement of same indent
                while len(pyCodes)>0 and pyCodes[-1].startswith(indentStr) and pyCodes[-1]!=' ':
                  pyCodes.pop()
                pyCodes.pop()
                #del pyCodes-i:]
                for vPos, vChange in whileVars.items():
                  if vPos == d_pos_l:
                        continue
                  ctimes = abs(vChange / cVarChange)
                  ctimesStr = '' if ctimes==1 else '{}*'.format(ctimes)
                  cSign = '+' if vChange > 0 else '-'
                  pyCodes.append('{}data[{}] {}= {}data[{}]'.format(' '*(4*(indentLevel-1)),
                                                                        vPos, cSign,ctimesStr, d_pos_l))
                pyCodes.append('{}data[{}] = 0'.format(' '*(4*(indentLevel-1)), d_pos_l))
            del whileVarCache]
            bStacks.pop()
      elif c == '.':
            pyCodes.append('{}print(data[{}])'.format(indentStr, d_pos))
      elif c == ',':
            pyCodes.append('{}data[{}] = ord(stdin.read(1))'.format(indentStr, d_pos))
      elif c == '+':
            opSign = '-=' if d_change < 0 else '+='
            if pyCodes and pyCodes[-1] == '{}data[{}] = 0'.format(indentStr, d_pos):
                pyCodes[-1] = '{}data[{}] = {}'.format(indentStr, d_pos, d_change)
            else:
                pyCodes.append('{}data[{}] {} {}'.format(indentStr, d_pos, opSign, abs(d_change)))
            if bStacks:
                whileVarCache].setdefault(d_pos, 0)
                whileVarCache] += d_change
      elif c == '-':
            opSign = '+=' if d_change < 0 else '-='
            if pyCodes and pyCodes[-1] == '{}data[{}] = 0'.format(indentStr, d_pos):
                pyCodes[-1] = '{}data[{}] = {}'.format(indentStr, d_pos, -d_change)
            else:
                pyCodes.append('{}data[{}] {} {}'.format(indentStr, d_pos, opSign, abs(d_change)))
            if bStacks:
                whileVarCache].setdefault(d_pos, 0)
                whileVarCache] -= d_change
      elif c == '%':
            pyCodes.append('{}data[{}] %= data[{}]'.format(indentStr, d_pos, d_pos+1))
    return '\n'.join(pyCodes)
```
具体使用
```
shrinkCode, pVars, pChange = shrinkBFCode(shellcode)
print(generatePyCode(shrinkCode, pVars, pChange))
```

这样我们就可以把 `shellcode` 转化成如下的python代码
```
data = 2
data = 8
data = 0
data = 0
data = 0
data = 0
data = 0
data = 1
while data != 0:
    data -= 1
    data = 0
    data = 0
    data = 0
    while data != 0:
      data -= 1
      data += data
      data += data
      data = 0
      data += data
      data = 0
      data += 1
    data += data
    data = 0
    print(data)
    data = 0
    data += data
    data = 0
    data += 1
data += data
data = 0
data += data
data = 0
data = 0
data = 0
data = 0
data = 0
print(data)
data = 3
data += data
data += data
data = 0
data += data
data = 0
data = 0
data = 0
data = 0
data = 0
data = 0
data = 1
while data != 0:
    data -= 1
    data = 0
    data = 0
    data = 0
    while data != 0:
      data -= 1
      data += data
      data += data
      data = 0
      data += data
      data = 0
      data += 1
    data += data
    data = 0
    print(data)
    data = 0
    data += data
    data = 0
    data += 1
data += data
data = 0
data += data
data = 0
data = 0
data = 0
data = 0
data = 0
print(data)
```
至此 我们得出来比较容易读懂的代码了，虽然看起来还是有些绕，但结合动态调试已经足够分析代码的行为了。
这段代码的含义大致是：
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;先计算 2^8 = 256,
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;再计算 3^256 = 139008452377144732764939786789661303114218850808529137991604824430036072629766435941001769154109609521811665540548899435521

题目中完整的shellcode还有一些更”夸张“的数学操作，但依然可以通过上述方法比较快速的分析出含义，这里就不详述了，有兴趣的可以自己试一试。

#后记
上述的代码转化其实还可以做一些优化，以便得出更容易理解的代码。
包括消除冗余的代码，缓存中间结果减少多层嵌套循环 等
当然这些会涉及到编译原理方面的知识，只能后续抽空补一补，再做优化了

以上只是解题的一种思路，有别的思路或者优化方案也欢迎各位大佬提出，先谢过了

xixicoco 发表于 2021-5-17 03:52

大佬写的东西就是看不懂啦

Li1y 发表于 2021-5-17 09:48

用github上的bfc把brainfuck编译成elf，然后丢IDA分析

高维可破 发表于 2021-5-17 10:01

Li1y 发表于 2021-5-17 09:48
用github上的bfc把brainfuck编译成elf，然后丢IDA分析

多谢大佬提醒。
不过这个bfc可以支持添加自定义操作符吗，还有是否支持大数操作？
我对c的不是很熟，回头试试

高维可破 发表于 2021-5-17 10:09

xixicoco 发表于 2021-5-17 03:52
大佬写的东西就是看不懂啦

大佬，可能是我第一次写的缘故。。。
有不懂的地方可以指出来，我可以再写得更详细易懂点。
先谢过了。

Li1y 发表于 2021-5-17 10:16

高维可破 发表于 2021-5-17 10:01
多谢大佬提醒。
不过这个bfc可以支持添加自定义操作符吗，还有是否支持大数操作？
我对c的不是很熟，回 ...

貌似只支持brainfuck标准格式的编译

刘样andholiday 发表于 2021-5-17 14:23

丢DIA分析是可以的

LoneLySCeR 发表于 2021-5-17 14:56

专业水平

余粮永盈盎 发表于 2021-5-17 16:01

认真学习

jim2g 发表于 2021-7-11 18:26

大佬第四关怎么过的啊

查看完整版本: 记一次brainfuck的解密思路