> fibonacci这题本质上是属于算法优化类型的reverse题，所以对于斐波那契数列的优化过程还是需要一定的了解的。

## 算法逆向
```
# def Fibonacci_Recursion_tool(n):
#     if n <= 0:
#         return 0
#     elif n == 1:
#         return 1
#     else:
#         return Fibonacci_Recursion_tool(n - 1) + Fibonacci_Recursion_tool(n - 2)
#
#
# def Fibonacci_Recursion(n):
#     result_list = []
#     for i in range(1, n + 1): result_list.append(Fibonacci_Recursion_tool(i))
#     return result_list
#
#
# print(Fibonacci_Recursion(28))
tmp = 0
def fibonacci_encode(time, char):
    global tmp
    tmp = char
    if time == 0:
        tmp ^= 1
        return 1
    elif time == 1:
        t4 = fibonacci_encode(0,tmp)
        t3 = t4 - ((t4 & 0xffffffff) >> 1 & 0x55555555)
    else:
        t1 = fibonacci_encode(time-2,tmp)
        t2 = fibonacci_encode(time-1,tmp)
        t3 = t2+t1
        t4 = t3
        t3 = t3 - (t3 >> 1 & 0x55555555)
    t3 = (t3>>2 & 0x33333333) + (t3 & 0x33333333)
    t3 = (t3 >>4) + t3
    t3 = (t3 >>8 & 0xf0f0f) + (t3 & 0xf0f0f0f)
    tmp = tmp ^ (t3 >> 0x10) + t3 &1
    return t4

init = ['0x49', '0x7e', '0x7', '0xe2', '0x9c', '0xcc', '0xc9', '0x2b', '0xfc', '0x34', '0x4', '0x6f', '0x4e', '0x12', '0x0', '0x50', '0xa9', '0x2', '0x3a', '0xba', '0xc2', '0x8e', '0x41', '0x99', '0x98', '0xf5', '0x8d', '0x51', '0x4d', '0xa6', '0xc6', '0x43']
init_b = [73, 126, 7, 226, 156, 204, 201, 43, 252, 52, 4, 111, 78, 18, 0, 80, 169, 2, 58, 186, 194, 142, 65, 153, 152, 245, 141, 81, 77, 166, 198, 67]
def main():
    a = 0
    buf = 0x49
    for i in init_b:
        tmp = i
        for j in range(0+a,8+a):
            i = tmp
            fibonacci_encode(j, i)
            buf = buf ^ tmp << j
        print(buf)
        a = a+8

main()
```

### QDBI
QDBI 是一个动态二进制插桩工具，它的插桩级别是在单条汇编指令级别上的，在这道斐波那契题中我们可以找到关键优化点，在该点上插桩代码来加速脚本的运行。
QDBI可以使用原生的c或者c++来编写插桩脚本，另外QDBI也提供了python的api来加速插桩代码的编写，也可以配合frida来进行组合。
使用pyQDBI的方法如下：
```
LD_PRELOAD=/usr/local/lib/libpyqdbi.so PYQDBI_TOOL=./q.py ./binary
```

最终解决脚本
```
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import ctypes
import sys
import pyqbdi
import struct

""" solve by using gdb script
flag = ""
while True:
    e("si", to_string=True)
    pc = int(e("p/x $rip", to_string=True).split("=")[1].strip(), 16)
    if pc == 0x400686: # set fibo
        rdi = int(e("p/x $rdi", to_string=True).split("=")[1].strip(), 16)
        e("set $rax={:#x}".format(a[rdi]))
        e("set {{int}}$rbp={:#x}".format(sss[rdi-1]^sss[rdi-2]))
        e("set $rip=0x40069f")
    elif pc == 0x40055c: # print flag
        rdi = int(e("p/x $rdi", to_string=True).split("=")[1].strip(), 16)
        flag += chr(rdi)
        sys.stdout.write("\rflag: "+flag)
    elif pc == 0x4006ed:
        s = int(e("x/wx $rbp", to_string=True).split(":")[1].strip(), 16)
        sss.append(s)
    elif pc == 0x400570:
        break
"""

# generate fibo
fibo = []
sss = [1]
for i in range(256):
    if i == 0 or i == 1:
        fibo.append(1)
    else:
        r1 = fibo[i-1] & 0xffffffff
        r2 = fibo[i-2] & 0xffffffff
        now = (r1 + r2) & 0xffffffff
        fibo.append(ctypes.c_uint(now).value)
flag = ""

def u32(x):
    return struct.unpack('<I', x.ljust(4, '\x00'))[0]

def p32(x):
    return struct.pack('<I', x & 0xffffffff)

def cb1(vm, gpr, fpr, data):
    global sss, fibo
    rbp = pyqbdi.readMemory(gpr.rbp, 4)
    sss.append(u32(rbp))
    return pyqbdi.CONTINUE

def cb2(vm, gpr, fpr, data):
    global sss, fibo
    rdi = gpr.rdi
    gpr.rax = fibo[rdi]
    ddd = (sss[rdi-1] ^ sss[rdi-2])&0xffffffff
    pyqbdi.writeMemory(gpr.rbp, p32(ddd))
    gpr.rip = 0x40069f
    vm.setGPRState(gpr)
    return pyqbdi.BREAK_TO_VM

def cb3(vm, gpr, fpr, data):
    global flag
    rdi = gpr.rdi
    flag += chr(rdi)
    sys.stdout.write("\rflag: "+flag)
    if "}" in flag:
        print ""
        return pyqbdi.STOP
    else:
        return pyqbdi.CONTINUE

def pyqbdipreload_on_run(vm, start, stop):
    vm.addCodeAddrCB(0x4006ed, pyqbdi.PREINST, cb1, None)
    vm.addCodeAddrCB(0x400686, pyqbdi.PREINST, cb2, None)
    vm.addCodeAddrCB(0x40055c, pyqbdi.PREINST, cb3, None)
    vm.run(start, stop)
```

## unicorn
参考
```
https://bbs.pediy.com/thread-224330.htm
```

XELDAX BLOG

Pentest

Vul

Files Share

从hxp ctf fibonacci学习如何还原算法,unicorn模拟执行和QDBI插桩