二叉树

0x4000ad:       nop
0x4000ae:       je      0x4000bd
0x4000b0:       lea     rbx, [rdi + 0x40]
0x4000b4:       nop
0x4000b5:       add     r9, 0x49
0x4000b9:       jmp     0x400080
0x4000bb:       nop
0x4000bc:       nop
0x4000bd:       lea     rbx, [rdi + 0x20]
0x4000c1:       nop
0x4000c2:       nop
0x4000c3:       nop
0x4000c4:       add     r9, 0x11
0x4000c8:       nop
0x4000c9:       nop
0x4000ca:       nop
0x4000cb:       jmp     0x400080

0x4000ad:       mov     rax, 1
0x4000b4:       mov     rdi, 1
0x4000bb:       mov     rdx, 5
0x4000c2:       cmp     r9, 0x49da
0x4000c9:       jg      0x4000d2
0x4000cb:       mov     rsi, r10
0x4000ce:       Syscall
0x4000d0:       jmp     0x4000d7
0x4000d2:       mov     rsi, r11
0x4000d5:       syscall
0x4000d7:       mov     rax, 0x3c
0x4000de:       xor     rdi, rdi
0x4000e1:       syscall

从 顶点 进口 *


loopFunc  =  0x400080 
loopFuncLen  =  0x4000e1 - loopFunc

bigdataArray  =  0x400176 
bigdataArrayLen  =  0x4c7556 - bigdataArray

MAGIC_VALUE  =  0x49da


md  =  Cs ( CS_ARCH_X86 , CS_MODE_64 )
 binaryFile  =  oPEn ( "main.elf" , "rb" )
 data  =  binaryFile。读()

loopFuncMem  = 数据[ 0x80 : 0x80 + loopFuncLen ]
 bigArrayMem  = 数据[ 0x176 : 0x176 + bigdataArrayLen ]

loopFuncMem  = [ b  for  b  in  loopFuncMem ]
 bigArrayMem  = [ b  for  b  in  bigArrayMem ]

二进制文件。关闭()


# 实际最小路径计算

最短路径 = {}

DEF  registerPath（路径，附加）：
     revAdd  =  0
    如果 路径[ - 1 ]在 最短路径：
         revAdd  = 最短路径[路径[ - 1 ]]
    否则：
         revAdd  = 添加[ - 1 ]

    为 [R 在 范围（1，len个（路径）+ 1）：
        如果 - [R  >  1：revAdd  =  revAdd  + 附加[ - [R ]
        如果 路径[ - [R ]在 最短路径：
            最短路径[路径[ - [R ]] = 分钟（最短路径[路径[ - r]，revAdd）
        否则：
            最短路径[路径[ - [R ]] =  revAdd

def  parsebranch ( mem , rbx , val , depth = 0 , path = [], add = []):

   
    如果 RBX 在 最短路径：
         registerPath（路径，附加）
        如果 最短路径[ RBX ] + VAL  >  MAGIC_VALUE：
            返回
    
    if  depth  ==  100 * 8 : 
         registerPath ( path , add )
        返回

    ＃应用自修改XOR
    用于 我 在 范围（8 * 4）：
         MEM [我] ^ = bigArrayMem [ RBX +我]

    currentAdd  =  0 
    nextPointer  =  0 
    existingJumps  = []
    
    因为 我 在 md。disasm ( bytes ( mem ), 0x2d ):
         op  =  i。助记符
        if  op  ==  "nop" : 
             continue 
        if  op  ==  "je" :
             continue 
        if  op  ==  "jmp" :
             existingJumps。追加（（nextPointer，currentAdd））
            继续
        ，如果 运算 ==  “添加”：
             currentAdd  =  INT（我。op_str。分裂（“”）[ 1 ]。条（），16）
            继续
        ，如果 运算 ==  “LEA” ：
             nextPointer  =  INT（我。op_str。分裂（“+”）[ 1 ] .split ( "]" )[ 0 ] .strip (), 16 )
            继续
        PRint ( "0x%x: t %s t %s"  % ( i . address , i . mnemonic , i . op_str )) # 如果发生意外，则打印
    
    对于（nextPointer，currentAdd）  在 existingJumps：
         parseBranch（MEM + []，nextPointer，VAL + currentAdd，深度+ 1，路径+ [ nextPointer ]，添加+ [ currentAdd ]）
    
# 计算最短路径
parseBranch ( loopFuncMem [ 0x2d :], 0 , 0 )

        ＃这防止不必要的计算
        ，如果 最短路径[ RBX ] + VAL  >  14000 和 深度 <  400：
            返回
            
        如果 最短路径[ RBX ] + VAL  >  12000 和 深度 <  200：
            返回

def  verboseCalc ( mem , rbx , val , depth = 0 , bits = []):

    如果 深度 ==  100 * 8 : 
         barray  =  ''。加入（'0'  ，如果 b  ==  0 否则 '1' 为 b 中 位）
         ＃打印标记
        打印（'' 。加入（[ Chr（INT（barray [我* 8 :(我+ 1）* 8 ] [： : - 1 ], 2 ))对于 我 在 范围内( len ( barray ) // 8 )]))
        返回
        
    ＃应用自修改XOR
    用于 我 在 范围（8 * 4）：
         MEM [我] ^ = bigArrayMem [ RBX +我]

    当前添加 =  0 下一个
    指针 =  0
    
    
    现有跳跃 = []
    
    因为 我 在 md。disasm ( bytes ( mem ), 0x2d ):
         op  =  i。助记符
        if  op  ==  "jmp" :
             existingJumps。追加（（nextPointer，currentAdd））
        如果 运算 ==  “添加”：
             currentAdd  =  INT（我。op_str。分裂（“”）[ 1 ]。strip (), 16 )
         if  op  ==  "lea" :
             nextPointer  =  int ( i . op_str . split ( "+" )[ 1 ]. split ( "]" )[ 0 ]. strip (), 16 )
    
    jo  =  shortestPath [ existingJumps [ 0 ][ 0 ]]
     jz  =  shortestPath [ existingJumps [ 1 ][ 0 ]]

    if  jo + val  ==  MAGIC_VALUE :
         verboseCalc ( mem + [], existingJumps [ 0 ][ 0 ], val + existingJumps [ 0 ][ 1 ], depth + 1 , bits + [ 1 ])
     if  jz + val  ==  MAGIC_VALUE :
         verboseCalc ( mem + [], existingJumps [ 1 ][0 ], val + existingJumps [ 1 ][ 1 ],深度+ 1 ,位+ [ 0 ])

# 使用最短路径映射并遍历它
verboseCalc ( loopFuncMem [ 0x2d :], 0 , 0 )

>python solve.py
pbctf{!!finding_the_shortest_path_in_self-modifying_code!!_e74c30e30bb22a478ac513c9017F1b2608abfee7}

https://rainbowpigeon.me/posts/pbctf-2021/#cosmo