ARMssembly 4 picoCTF 2021 Solution

Description

1. Step 1Map the call graph: func1 picks one of two branches
   main calls func1(atoi(argv[1])). func1 splits on whether the input is <=100 or >100. The other small functions (func3, func4, func5, func7, func8) are all leaves; func6 is dead code (never called from this path).
   bash

   grep -nE '^func[0-9]+:|cmp|bls|bhi|bl ' chall_4.S

   Copied!
   Learn more

   Branching summary, after walking each function:

   func7(x) = (x > 100) ? x : 7
   func8(x) = x + 2
   func5(x) = func8(x)            ; = x + 2
   func4(x) = call func1(17), discard, return x   ; identity
   func3(x) = func7(x)            ; = (x > 100) ? x : 7
   
   func2(x):
       if (unsigned) x > 499:  return func5(x + 13)   ; = x + 15
       else:                   return func4(x - 86)   ; = x - 86
   
   func1(x):
       if (unsigned) x <= 100: return func3(x)        ; = 7
       else:                   return func2(x + 100)

   Note the unsigned compares. The branches use bls (branch if lower-or-same, unsigned) and bhi (branch if higher, unsigned), so a Python translation must compare with the input masked to 32 bits, not as a signed int. Inputs above 2³¹ are still positive in this world.

2. Step 2Collapse the call graph into three cases
   Once func4 is identity and func5 is +2, every path through func1 reduces to a piecewise linear formula on the input.
   python

   python3 - <<'EOF'
   def chall4(x):
       x &= 0xFFFFFFFF
       if x <= 100:
           return 7
       elif (x + 100) <= 499:    # 100 < x <= 399
           return (x + 100 - 86) & 0xFFFFFFFF   # = x + 14
       else:                     # x > 399 (after +100 overflow check, none here)
           return (x + 100 + 15) & 0xFFFFFFFF   # = x + 115
   
   for arg in [50, 200, 600, 3251107833]:
       r = chall4(arg)
       print(f"arg={arg:<12} -> {r} (hex {r:#010x})")
   EOF

   Copied!
   Learn more

   Worked output:

   arg=50           -> 7          (hex 0x00000007)
   arg=200          -> 214        (hex 0x000000d6)
   arg=600          -> 715        (hex 0x000002cb)
   arg=3251107833   -> 3251107948 (hex 0xc1c7f86c)

   For arg=3251107833 the answer is 3251107948. Convert that to lowercase 8-hex-digit form (no 0x prefix) and wrap with picoCTF{...} for submission.

   Sanity check via QEMU if you doubt the trace: aarch64-linux-gnu-gcc -static -o chall_4 chall_4.S && qemu-aarch64 ./chall_4 3251107833 should print Result: 3251107948.

   See Python for CTF for the simulation idiom and Ghidra reverse engineering if you want a graphical view of the dispatch tree.

Flag

func1 collapses to a piecewise formula on the input: 7 when input<=100, input+14 when 100<input<=399, input+115 otherwise. Different picoCTF instances seed different inputs; plug yours into the Python solver and submit the lowercase 8-hex-digit form.