CTF Overview
This time I was dealing with a 2 stars ELF binary from Hackropole called Brontosaure. It has a bunch of data to keep in mind, big math-heavy functions, a crypto algorithm and a few surprises up its sleeve that made my reversing process tough, but in the end I’m happy as I learned a lot!
Reversing the Binary
-
Getting straight to it, recon first as usual:
filesays it’s a stripped, dynamically linked binary;lddshows the libraries the binary uses, there’s nolibcrypto,libm(math), meaning if some kind of hashing happens, the functions are fully defined inside the binary:
linux-vdso.so.1 (0x00007ff898b0a000) libc.so.6 => /usr/lib/libc.so.6 (0x00007ff898800000) /lib64/ld-linux-x86-64.so.2 => /usr/lib64/ld-linux-x86-64.so.2 (0x00007ff898b0c000)stringsshow a set of functions used in the binary, from the list I can imagine what happens inside the binary:
1. `Usage: %s <name> <serial>` - a keygen challenge hint, where a program checks if a serial is valid for a given name; 2. `ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/` - base64 alphabet; 3. `?456789:;<=` and `!"#$%&'()*+,-./0123` - a couple of interesting sequences; 4. "6202CSCF" - reversed flag prefix ("FCSC2026"); 5. "processes and signals" - calls like "fork", "mmap", "mutex"-related stuff, "sigqueue", "pipe" mean I'm dealing with a multi-processes binary;nc localhost 4000gives a prompt to input a valid serial for the givenFCSC2026name, it dies after the first wrong input:
[elijah@elijah-arch brontosaure]$ nc localhost 4000 Give me a valid serial for username: FCSC2026 >>> abc Sorry, that is not a valid serial.- there was no such prompt strings in the
stringscommand output, meaning there’s a wrapper script or something that takes my input, runs the binary with it and prints based on the binary run’s result.
-
The
mainfunction starts with the input guard:
if (argc != 3) {...}
- After, six new shared and zeroed memory mappings of different sizes are created with
mmapthe following way:
g_shared = mmap(0x0,size,PROT_WRITE|PROT_READ,MAP_ANONYMOUS|MAP_SHARED,-1,0);
mutexis initialized:
pthread_mutexattr_init(mutexAttributes);
pthread_mutexattr_setpshared(mutexAttributes,PTHREAD_PROCESS_SHARED);
pthread_mutex_init(g_mutex,mutexAttributes);
The first call (pthread_mutexattr_init) initializes mutex attributes object with default values.
The pthread_mutexattr_setpshared call sets process-shared mutex attribute to PTHREAD_PROCESS_SHARED to make it usable by different processes while a normal mutex is guaranteed to work between threads of one process.
The last pthread_mutex_init call initializes the mutex object at g_mutex using those attributes. It requires 40 bytes on x86-64 machine (g_mutex = mmap(0x0,40,PROT_WRITE|PROT_READ,MAP_ANONYMOUS|MAP_SHARED,-1,0);)
-
The first function I had to work through turned out to be a
Base64 Decodingfunction. Since I was not familiar with Base64 in details, the function didn’t make much sense to me initially. I have its breakdown in the followingWhat I Learnedsection down below. In couple of words, this function makes sure that a serial I input is a valid Base64 string that decodes to at least 1 byte. -
There’s a guard after the decoding function that makes sure the output length is a multiple of 9 - that’s an interesting observation that I kept in mind.
NOTE: Before we move to the next reversing steps, here’s the data vocabulary I prepared so that you understand my namings and what they refer to
- The next function does some
SHAKE256crypto magic with the name input (FCSC2026in my case):
shake256(nameInput,g_shared5,8192,&local_1068,32);
The function derives data from the nameInput with the SHAKE256 crypto algorithm: it keeps generating 8192-byte chunks until it’s accepted, then leaves two results: the accepted 8192-byte chunk in the g_shared5 buffer, and the next 32 bytes of the stream in local_1068. You can find my process on digesting this step down in the What I Learned section.
- The next set of steps is the core of the program I’d say:
- First, every process initializes a pipe for itself to be able to read & send messages between processes via signals;
- Then, it initializes
signal handlersto be able to handle incoming signals fromsigqueue. - A per-process
g_permutationglobal is created, storing a shuffled0 .. 15array. You can read more on the permutation algorithm used here in theWhat I Learnedsection. - Lastly, global
g_sharedstate is modified. Every process, including the parent one, commits its process id and areadybit to the shared global state.
void init_process_state(void) {
__pid_t pid;
int childIndex;
pipe(&g_pipe);
initSigHandlers();
sattolo_shuffle(&g_permutation,16);
pthread_mutex_lock(g_mutex);
pid = getpid();
childIndex = g_child_index;
g_shared->pids[g_child_index] = pid;
g_shared->ready_mask = g_shared->ready_mask | 1 << (childIndex & 31);
pthread_mutex_unlock(g_mutex);
return;
}
I created a custom type for g_shared that looks like this:
struct shared_state {
long pids[16];
long ready_mask;
}
Now, every process makes sure that all others are ready with the waitForProcesses(0xffff); call:
void waitForProcesses(long param_1) {
long lVar1;
while( true ) {
pthread_mutex_lock(g_mutex);
lVar1 = g_shared->ready_mask;
pthread_mutex_unlock(g_mutex);
if (lVar1 == param_1) break;
usleep(1000);
}
return;
}
-
Once every process is ready, the parent process starts sending
tokens, 9-byte blocks from the decodedserialthat have the following structure:[1-byte k][8-byte value]. The parent process sends them all to the child process#1and themessage_loopruns. -
Let me try to simplify the
message_loopso you get the main idea behind it, excluding some values and calls:
struct msg {
int signo;
long value;
}
void message_loop() {
do {
msg message = read_message();
if (message.signo == SIGRTMIN + STOP_SIG) { // STOP_SIG = 16
break;
}
int k = message.signo - SIGRTMIN; // 0 .. 15
k = g_permutation[k];
if (message.value == MAGIC) {
g_slots[g_process_index] ^= table[get_piece_index(g_process_index, k)];
g_tokens_to_read--;
} else {
long new_value = message.value * CONSTANT;
sigqueue(g_shared->pids[(g_process_index + 1) % 16], k, new_value); // send permuted k and value to the next process
g_messages_sent++;
if (g_messages_sent > 0xffff) { // terminate if total messages limit is hit
_exit(0);
}
}
} while (g_tokens_to_read != 0); // while there're serial tokens to process
if (g_tokens_to_read == 0) {
for (int i = 0; i < 16; i++) {
sigqueue(g_shared->pids[i], STOP_SIG, some_stop_value);
}
}
if (g_process_index == 0) { // RETURN if it's the parent process
return;
}
clear_ready_mask();
_exit(0); // terminates the child process
}
The main idea of this whole tokens (remember, [1-byte k][8-byte value]) flow between the processes’ message_loop function calls is to keep permuting k (in the 0 .. 15 range) and multiplying value (value *= CONSTANT) until value == MAGIC. In this case, a certain 32-byte piece is selected from that big 8192-byte chunk that we received after SHAKE256(FCSC2026) and XORed into the landing process slot (I omitted the get_piece_index()` algorithm to save space as it’s just a math formula).
- Once all of the tokens
landed, the value and all16 32-byte slotsare stored, we got the last set of guards before the flag is captured:
- g_slots[0] ^ g_slots[1] … ^ g_slots[15] must equal
target- tokens < 256 (decoded serial can hold up to 255 tokens, so
255 * 9 = 2295bytes)- g_messages_sent > 0x7a69 (31337)
The target value in this case is the next 32 bytes after the accepted SHAKE256("FCSC2026") `8192-byte chunk.
Here’s the data flow schema I prepared to better visualise the flow:

And that’s the whole program! Now, as it’s reversed, it’s time to write a key generator program and satisfy the guards to capture the flag.
Key Generator Program Implementation
In this section, I’ll be going through the key (serial input) generation steps and include some code snippets. I decided to implement it with Rust this time.
SHAKE256("FCSC2026"), read the 2nd (8192 .. 16383) chunk ofpieces(256 pieces, 32 bytes each) as well as thetargetvalue (next 32 bytes after the pieces chunk):
fn shake256_fcsc() -> ([u8; 8192], [u8; 32]) {
let mut hasher = Shake256::default();
hasher.update(b"FCSC2026");
let mut reader = hasher.finalize_xof();
let mut buffer = [0u8; 8192];
reader.read(&mut buffer); // the 1st chunk (0 - 8192) that is declined
reader.read(&mut buffer); // the 2nd chunk (8192 - 16384) that we keep
let mut target: [u8; 32] = [0u8; 32];
reader.read(&mut target);
(buffer, target)
}
- Generate 16
g_permutationfor every process with theSattolo Shufflealgorithm, seeded bySHAKE256("FCSC#%02d"). I omitted the seeding part in the reversing section, but it’s pretty much the pseudo randomness part to select the index to swap with:
fn sattolo_permutation(reader: &mut impl XofReader) -> [u8; 16] {
// 0..16 array
let mut permutation: [u8; 16] = std::array::from_fn(|i| i as u8);
for i in (1..16).rev() {
let mut stream_byte = [0u8; 1];
reader.read(&mut stream_byte);
let num = (stream_byte[0] as usize) % i;
permutation.swap(i, num);
}
permutation
}
fn process_permutation(process_index: usize) -> [u8; 16] {
let fcsc_str = format!("FCSC#{:02}", process_index);
let mut process_hasher = Shake256::default();
process_hasher.update(fcsc_str.as_bytes());
let mut reader = process_hasher.finalize_xof();
sattolo_permutation(&mut reader)
}
I verified that my SHAKE256 function seeding for the parent process, byte by byte reads and Sattolo shuffle are implemented correctly from the reversed functions:
Rust keygen program: 16 bytes of the parent process’ permutation.
Running `target/debug/brontosaure-keygen`
Perm 0: 0402030709060e0b0c0f050001080d0a
GDB: 16 integers from the g_permutation global of the parent process with the breakpoint set on the waitForProcesses(1) call.
Breakpoint 2, 0x00005555555552e8 in ?? ()
(gdb) x/16dw 0x555555559120
0x555555559120: 4 2 3 7
0x555555559130: 9 6 14 11
0x555555559140: 12 15 5 0
0x555555559150: 1 8 13 10
- Time to quickly explain two important constants:
const C: u64 = 0x11223344556677a5;is just a constant that is used to permutevalueif it’s not equal toMAGICyet. Remember theif (value != MAGIC) { value *= C }part from the reversing section.
NOTE: Keep in mind that a wrap around happens on
value *= Cin case the result doesn’t fit into 64 bits, hencemod 2^64is applied to the result.
const MAGIC: u64 = 0x63734eebf3b7982d;is thelandingvalue. A token lands as soon as its value equalsMAGIC.
Turned out that MAGIC is the Multiplicative inverse of C mod 2^64 (C * MAGIC = 1, C is odd, hence an inverse exists). So a token lands after n hops when value * C^n = C^-1, and multiplying both sides by Cgivesvalue * C^(n+1) = 1`.
That lets us pick any number of hops n and compute a start_value that lands exactly there:
start_value = mod_pow(C_INV, n + 1) // C_INV == MAGIC
The mod_pow function computes base^exponent mod 2^64 with the square-any-multiply approach, using wrapping_mul multiplication function so the 64-bit overflow acts as the modulo:
// Square and Multiply method
fn mod_pow(base: u64, exponent: u64) -> u64 {
let mut result: u64 = 1;
let mut b = base;
let mut exp = exponent;
while exp > 0 {
// lowest bit is set
if exp & 1 == 1 {
result = result.wrapping_mul(b);
}
b = b.wrapping_mul(b);
exp >>= 1;
}
result
}
- Replay a token’s path and tell which
pieceit’d land on. Remember, apieceis selected from theSHAKE256("FCSC2026")’s 2nd chunk with apiece_index(process, k)function. But first, let’s get those final(process, k)for astart_valueand hopsn:
struct SimulationResult {
landing_process: usize,
final_k: usize,
}
fn simulate(start_k: usize, n: usize, permutations: &[[u8; 16]; 16]) -> SimulationResult {
let mut k = start_k;
let mut process = 1;
for i in 0..=n {
k = permutations[process][k] as usize;
if i == n {
break;
}
process = (process + 1) % 16;
}
SimulationResult {
landing_process: process,
final_k: k,
}
}
As in the program, we start with the process = 1 and permute k every message_loop entry.
- Knowing the
landing_processandfinal_kvalues, we can get apieceindex. The formula is simplified from thelandedbranch of themessage_loopfunction (I omitted it before):
fn piece_index(process: usize, k: usize) -> usize {
64 * (process / 4) + 63 - 16 * (process % 4) - k
}
-
We can choose pieces now, using the
Gaussian eliminationapproach over ones and zeroes (working with bits). We basically need a subset of256 pieceswhoseXORequals to the32-byte target. I might not be able to explain the approach using math language, but let me show how I implemented it the way I managed to understand it:- First, I created a few types that represent
Toolboxthat is an array of 256 slots. Every slot contains aToolwhereVectis a256-bitvalue (stored as fouru64s), and a tool sits in slotibecause its leading bit1(pivot).Comborepresents a bitmask of the original pieces it’s made of.Vectis just the way I decided to store256 bits.
type Vect = [u64; 4]; type Combo = Vect; #[derive(Default, Copy, Clone)] struct Tool { vect: Vect, combo: Combo, } type Toolbox = [Option<Tool>; 256]; // calculates a leading bit's index of a Vect fn leading_bit(vect: Vect) -> Option<usize> { for (i, word) in vect.iter().copied().enumerate().rev() { if word != 0 { let leading_bit_inside = 63 - word.leading_zeros(); return Some(i * 64 + (leading_bit_inside as usize)); } } None } // creates the first "Combo" for a Leading bit index (enables a bit) fn unit(bit_index: usize) -> Vect { let mut vect = [0u64; 4]; let word_index = bit_index / 64; vect[word_index] = 1u64 << (bit_index % 64); vect }- The goal is to fill the
ToolboxwithToolsfrom ourSHAKE256(name)chunk of data. We take a piece and see: if it’s leading bit slot is taken in theToolbox,XORit with this occupantTool(bothVectandComboto store the “recipe”) to clear theleading_bit, then store it in a free slot, or drop thepieceif it was reduced to zero:
fn insert(toolbox: &mut Toolbox, vect: Vect, combo: Combo) { let mut tool = Tool { vect, combo }; while let Some(bit) = leading_bit(tool.vect) { match toolbox[bit] { Some(occupant) => { tool.vect = xor(&tool.vect, &occupant.vect); tool.combo = xor(&tool.combo, &occupant.combo); } None => { toolbox[bit] = Some(tool); break; } } } } fn build_toolbox(chunk: &[u8; 8192]) -> Toolbox { let mut toolbox = [None; 256]; for (index, piece) in chunk.chunks_exact(32).enumerate() { let vect = to_vect(piece); let combo = unit(index); insert(&mut toolbox, vect, combo); } toolbox }- Now we can solve it: iterate over
target’s leading bits going downwards, andXORit with the correspondingTool, clearing leading bits and updatingCombo. If thetargetreaches zero, the collectedComborecipe lists thepiecesthat have toland. If there’s an empty slot at some point, it means there’s no solution:
// XOR target with a set of tools, selected by the target's leading bits fn solve(toolbox: &Toolbox, mut target: Vect) -> Option<Combo> { let mut combo = Combo::default(); while let Some(bit) = leading_bit(target) { match toolbox[bit] { Some(occupant) => { target = xor(&target, &occupant.vect); combo = xor(&combo, &occupant.combo); } None => { return None; } } } Some(combo) } // convert our "recipe" to a vector of pieces indices fn combo_to_indices(combo: &Combo) -> Vec<usize> { let mut indices = vec![]; for (i, word) in combo.iter().copied().enumerate() { if word != 0 { for j in 0..64 { let bit = (word >> j) & 1; if bit == 1 { indices.push(j + i * 64); } } } } indices } // XOR 123 pieces we calculated fn accumulate_pieces(pieces_buffer: &[u8; 8192], pieces_indices: &[usize]) -> Vect { let mut accumulator = Vect::default(); for piece_i in pieces_indices { let piece_start = piece_i * 32; let piece_end = piece_i * 32 + 32; let piece_vect = to_vect(&pieces_buffer[piece_start..piece_end]); accumulator = xor(&accumulator, &piece_vect); } accumulator }- The result I got for name
FCSC2026:rank is 256meaning all of the pieces are in the toolbox, so anytargetis reachable;123 piecesneeded to achieve ourtarget.
- First, I created a few types that represent
-
For each choosen piece:
- Reverse
piece_indexwith a256-entrylookup table for(landing_process, final_k)pairs:
fn build_lookup() -> [(usize, usize); 256] { let mut lookup = [(0usize, 0usize); 256]; for process in 0..16 { for k in 0..16 { lookup[piece_index(process, k)] = (process, k); } } lookup }- Choose a number of
nhops for tokens to land atprocess. Remember that the number of total hops should be in range31,337 < n <= 65,535, hence I selectedn >= 400hops per token. With123 tokensit’s123 + Σn = 50301messages, satisfying the guard:
const MIN_HOPS: usize = 400; fn choose_n(process: usize, mut min_n: usize) -> usize { loop { if (1 + min_n) % 16 == process { return min_n; } min_n += 1; } }- Find a
start_kvalue whose simulated journey ends withfinal_k. The simulation calculates thelanding_processandfinal_kvalues with the givenstart_kand a number of hopsn:
fn find_start_k(process: usize, final_k: usize, n: usize, permutations: &[[u8; 16]; 16]) -> usize { for start_k in 0..16 { let sim = simulate(start_k, n, permutations); if sim.landing_process == process && sim.final_k == final_k { return start_k; } } panic!( "no start_k reaches process={}, k={} in n={} hops", process, final_k, n ); } struct SimulationResult { landing_process: usize, final_k: usize, } fn simulate(start_k: usize, n: usize, permutations: &[[u8; 16]; 16]) -> SimulationResult { let mut k = start_k; let mut process = 1; for i in 0..=n { k = permutations[process][k] as usize; if i == n { break; } process = (process + 1) % 16; } SimulationResult { landing_process: process, final_k: k, } }- Build a token from the calculated
start_kand the remaining8 value bytes, so afternmultiplications by theCconstant it equalsMAGIC(C_INVconstant in my program that equalsMAGICas well):
fn make_token(start_k: usize, n: usize) -> [u8; 9] { let value_bytes = mod_pow(C_INV, (n + 1) as u64).to_le_bytes(); let mut token = [0u8; 9]; token[0] = start_k as u8; token[1..].copy_from_slice(&value_bytes); token } - Reverse
-
Time to put everything together and calculate the base64-encoded serial:
fn main() {
let (pieces_buffer, target) = shake256_fcsc();
let target_hex = target
.iter()
.map(|byte| format!("{:02x}", byte))
.collect::<String>();
println!("{}", target_hex);
let permutations: [[u8; 16]; 16] = std::array::from_fn(process_permutation);
let toolbox = build_toolbox(&pieces_buffer);
let target_vect = to_vect(&target);
let Some(combo) = solve(&toolbox, target_vect) else {
println!("No solution found");
return;
};
let pieces_indices = combo_to_indices(&combo);
let solution = accumulate_pieces(&pieces_buffer, &pieces_indices);
assert_eq!(solution, target_vect);
let lookup = build_lookup();
let mut serial = Vec::new();
let mut total_msgs = 0;
for i in pieces_indices {
let (process, final_k) = lookup[i];
let n = choose_n(process, MIN_HOPS);
let start_k = find_start_k(process, final_k, n, &permutations);
let token = make_token(start_k, n);
serial.extend(token);
total_msgs += 1 + n;
}
assert!(31337 < total_msgs && total_msgs <= 65535);
assert!(serial.len() < 0x900);
let base64_encoded_serial = BASE64_STANDARD.encode(&serial);
println!("Total msgs: {}", total_msgs);
println!("Base64 encoded serial: {}", base64_encoded_serial);
}
And here’s the output (I cut off a part of the serial to avoid posting pure solutions):
Total msgs: 50301
Base64 encoded serial: BDVd9dj/c9OsBzVd9dj/c9OsDDVd9dj/c9OsATVd9dj/c9OsCDVd9dj/c9OsBjVd9dj/c9OsDSm2lqCK7PdCASm2lqCK7PdCACm2lqCK7PdCCym2lqCK7PdCCCm2lqCK7PdCCSm2lqCK7PdCAym2lqCK7PdCBym2lqCK7PdCCW13JsFrehJIAm13JsFrehJIBG13JsFrehJICm13JsFrehJIC213JsFrehJIA213JsFrehJICG13JsFrehJIAYHCiWoXQ5EoBYHCiWoXQ5EoC4HCiWoXQ5EoCoHCiWoXQ5EoB4HCiWoXQ5EoD4HCiWoXQ5EoAIHCiWoXQ5EoBoHCiWoXQ5EoCIHCiWoXQ5EoAIXKPC/Pvu2aB4XKPC/Pvu2aC4XKPC/Pvu2aDYXKPC/Pvu2aD4XKPC/Pvu2aCYXKPC/Pvu2aBIXKPC/Pvu2aDIXKPC/Pvu2aBoXKPC/Pvu2aArlaUI5JllKTA7laUI5JllKTBblaUI5JllKTALlaUI5JllKTBLlaUI5Jll ................................ UxhJnvPKBtluUxhJnvPKCtluUxhJnvPKB9luUxhJnvPKD9luUxhJnvPKC9luUxhJnvPKBt1Qw60bEd2aAt1Qw60bEd2aA91Qw60bEd2aAd1Qw60bEd2aBd1Qw60bEd2aCt1Qw60bEd2aCd1Qw60bEd2aAN1Qw60bEd2aDXHZh2L8e4AQCXHZh2L8e4AQDHHZh2L8e4AQDnHZh2L8e4AQCnHZh2L8e4AQD3HZh2L8e4AQAnHZh2L8e4AQA3HZh2L8e4AQ
- Passing the given serial to the binary directly resulted in the
\o/sign, I thought that was it and passed the serial to the docker container, but turned out, it was just the round one. It asked for a serial for another name:
[elijah@elijah-arch brontosaure]$ nc localhost 4000
Give me a valid serial for username: FCSC2026
>>> BDVd9dj/c9OsBzVd9 ................ 4AQA3HZh2L8e4AQ
Give me a valid serial for username: VwW2htnHv8WGOvnH0804GzZZJdM
>>>
- I checked the program and figured out what parts depend on the name:
SHAKE256stream that builds the chunk table and atarget;- the chunk accepted also depends on the input name;
So I gotta reverse and implement the FUN_00101356 function from the reversed binary that decided which 8192-byte chunk is accepted. That function is quite big and math-heavy, so with the help of AI I could understand its main idea and implement a helper function to decide if a chunk is accepted or not:
- The function copies the original chunk of 256 pieces of 256 bits and runs the Gaussian elimination on them, familiar tech, right? It’s the same idea used for our Toolbox building.
- For each bit position it looks for a piece with the same bit set and XORs it out of the other pieces.
- The chunk is rejected if some bit position has no pivot.
- The chunk is accepted if all 256 positions get a pivot.
Hence, a chunk is accepted only if its 256 pieces are all independent (remember our toolbox has all 256 pieces in it?). This means that any 32-bytes target can be built by XORing some pieces, and the puzzle always has a solution.
I simply reuse the build_toolbox function to build the chunk and see if every slot is occupied by a tool:
fn chunk_is_acceptable(chunk: &[u8; 8192]) -> bool {
let toolbox = build_toolbox(chunk);
toolbox.iter().all(|slot| slot.is_some())
}
- A couple of steps left. I quickly rewrote the
shake256_fcscfunction that generates thechunkand thetargetto accept a custom name and check if the chunk is acceptable, pretty simple:
fn derive_data(name: &str) -> ([u8; 8192], [u8; 32]) {
let mut hasher = Shake256::default();
hasher.update(name.as_bytes());
let mut reader = hasher.finalize_xof();
let mut buffer = [0u8; 8192];
loop {
reader.read(&mut buffer);
if chunk_is_acceptable(&buffer) {
break;
}
}
let mut target: [u8; 32] = [0u8; 32];
reader.read(&mut target);
(buffer, target)
}
fn main() {
let input_name = std::env::args().nth(1).unwrap_or_else(|| "FCSC2026".to_string());
let (pieces_buffer, target) = derive_data(&input_name);
.....
}
Tested that the program outputs different serials properly just in case:
[elijah@elijah-arch brontosaure-keygen]$ cargo run -- FCSC2026
BDVd9dj/c9OsBzVd9 ........ 4AQA3HZh2L8e4AQ
[elijah@elijah-arch brontosaure-keygen]$ cargo run -- VwW2htnHv8WGOvnH0804GzZZJdM
DjVd9dj/c9OsDDVd9 ........ Zh2L8e4AQ
- Now, it’s the last challenge I HOPE :D
The binary keeps asking for serials for different names. I tried to manually generate and pass serials, but after 10th time I decided to automate the process as it’s likely required by design to handle this loop, so I wrote a short function that:
- connects to the challenge at
localhost:4000, creating a TCP stream; - splits the connection into a reader (
BufReaderto read output line by line) and a writer, but both use the same socket via different handlers; - reads one line (if there’re bytes to read) from the remote (server) socket and prints it to see a flag eventually;
- runs keygen (the whole flow explained above, I just moved it to a separate function) on a username if one appears in the line and is extracted;
- sends the serial + newline
\nbyte to “send” it; - repeats the process above until the server closes the connection;
- connects to the challenge at
fn run_client(permutations: &[[u8; 16]; 16]) -> std::io::Result<()> {
let stream = TcpStream::connect("localhost:4000")?;
let mut reader = BufReader::new(stream.try_clone()?);
let mut writer = stream;
let mut line = String::new();
loop {
line.clear();
if reader.read_line(&mut line)? == 0 {
break;
}
print!("{line}");
if let Some(position) = line.find("username: ") {
let name = line[position + "username: ".len()..].trim();
let serial = keygen(name, permutations);
writer.write_all(serial.as_bytes())?;
writer.write_all(b"\n")?;
}
}
Ok(())
}
And finally, after a set of request - response iterations, I got the flag:
[elijah@elijah-arch brontosaure-keygen]$ cargo run --release -- --net
Compiling brontosaure-keygen v0.1.0 (/home/elijah/Desktop/brontosaure/brontosaure-keygen)
Finished `release` profile [optimized] target(s) in 0.36s
Running `target/release/brontosaure-keygen --net`
Give me a valid serial for username: FCSC2026
>>> Give me a valid serial for username: RCg3US0O1UMsr
>>> Give me a valid serial for username: HyXdoHPwacylLYL99
>>> Give me a valid serial for username: QdWif566avqaJplzkBje
>>> Give me a valid serial for username: rZNXCOQnQfSF7gbg2dB5EIBDrAuQs6
>>> Give me a valid serial for username: YPPFNT3AumtbZdqwrTEofBXU2Jxdjto
>>> Give me a valid serial for username: CsFzr5zAZDN62qLckdt4Czb16o11tQyI
......................
>>> Give me a valid serial for username: uLfVz00crEpZnkrf8kzZ
>>> Give me a valid serial for username: rTIAM9rgmWfEM06nZLMK7Lz7b1Azj
>>> Give me a valid serial for username: ePapHyIiJq9E6Mq
>>> Give me a valid serial for username: 3rtdK5h5fnbcPSJD9STM3UIiPDK
>>> Give me a valid serial for username: hu3QzB2tRNVBGmTSpT
>>> Give me a valid serial for username: Zsv66k00rFWZLRfiGJAlqxnU
>>> Give me a valid serial for username: lNG0RH3TsML6IQkM9gjigirc1E
>>> Well done! Here is the flag: FCSC{9e076ceaf246b6003d .... f49039fe4bd}
NOTE: Hiding the full flag as usual to avoid publishing the plain answer.
What I Learned
LIBC calls decoding - mmap
I had to learn how to decode a libc function, e.g. mmap:
1. read `man 2 mmap` about the call, arguments, return values, and overall behaviour;
2. figure out the flags, protection flags arguments - in my case it was `3` for protection flags (meaning `PROT_READ | PROT_WRITE`, 1 + 2), and `0x21` for flags (meaning `MAP_SHARED | MAP_ANONYMOUS`, 0x01 + 0x20), that way I got the idea of how the new mapping is gonna be used and behave: e.g. with the `fork()` call it means that every process in this region see every change (that's why we have a process-shared mutex to avoid race conditions between processes when mutating the same memory region);
3. figure out why the remaining arguments are `-1` for `fd` and `0` for `offset` - these are required since the `MAP_ANONYMOUS` flag is set;
New types in Ghidra
I learned how to write a new type in Ghidra and use it in a rewritten function’s signature, e.g. for mmap:
-
Add a new enum type with the correct size (4 for
intin my case) and members (e.g.mmap_prothasPROT_READ = 0x1,PROT_WRITE = 0x2andPROT_EXECUTE = 0x4). The list can have only the fields that are required to correctly translate, say,0x3hex in the input toPROT_READ | PROT_WRITE. -
Rewrite the imported function’s signature to use our new argument types instead of, say, plain
int.In the end, I got this transformation that makes the code more readable:
// FROM g_shared = mmap(0x0,0x88,0x3,0x21,-1,0); // TO g_shared = mmap(0x0,0x88,PROT_WRITE|PROT_READ,MAP_ANONYMOUS|MAP_SHARED,-1,0);
A compiler’s memset pattern
After a few mmap calls I noticed loops that are pretty much the way a compiler calls memset and zeroes memory with a twist:
*pShared2 = 0;
pShared2[63] = 0;
puVar1 = pShared2 + 1 & 0xfffffffffffffff8;
for (uVar2 = (pShared2 - (pShared2 + 1 & 0xfffffffffffffff8)) + 0x200U >> 3; uVar2 != 0; uVar2 = uVar2 - 1) {
*puVar1 = 0;
puVar1 = puVar1 + bVar9 * -2 + 1;
}
Let’s figure this code out:
- It zeroes two “ends” of the region.
- Aligns a pointer to an 8-byte boundary:
puVar1 = pShared2 + 1 & 0xfffffffffffffff8;(disables 3 rightmost bits), even thoughmmapreturns page-aligned memory. - Computes how many 8-byte chunks left between that pointer and the
endof the region. - Zeroes those chunks with one
REP STOSQcommand.
Base64 Decoding function
This function looked very confusing at first, especially when I didn’t have an idea on its purpose. Here’s what I observed and learned from it:
-
It accepts 4 arguments: serial input, its length, a buffer (4096 bytes long one is passed in our case) and a number (4096 in our case):
uVar2 = FUN_00102ca8(seriaInput,serialLen,local_1048,4096); -
It has a pointer to a decoding table as I figured out later that has interesting values between repeating
0x80chunks:00103120 80 ?? 80h ........ 00103147 80 ?? 80h 00103148 80 ?? 80h 00103149 80 ?? 80h 0010314a 80 ?? 80h 0010314b 3e ?? 3Eh > 0010314c 80 ?? 80h 0010314d 80 ?? 80h 0010314e 80 ?? 80h 0010314f 3f ?? 3Fh ? 00103150 34 ?? 34h 4 00103151 35 ?? 35h 5 00103152 36 ?? 36h 6 00103153 37 ?? 37h 7 00103154 38 ?? 38h 8 00103155 39 ?? 39h 9 00103156 3a ?? 3Ah : 00103157 3b ?? 3Bh ; 00103158 3c ?? 3Ch < 00103159 3d ?? 3Dh = 0010315a 80 ?? 80h 0010315b 80 ?? 80h 0010315c 80 ?? 80h 0010315d 00 ?? 00h 0010315e 80 ?? 80h 0010315f 80 ?? 80h 00103160 80 ?? 80h 00103161 00 ?? 00h 00103162 01 ?? 01h 00103163 02 ?? 02h 00103164 03 ?? 03h 00103165 04 ?? 04h 00103166 05 ?? 05h 00103167 06 ?? 06h 00103168 07 ?? 07h 00103169 08 ?? 08h 0010316a 09 ?? 09h 0010316b 0a ?? 0Ah 0010316c 0b ?? 0Bh 0010316d 0c ?? 0Ch 0010316e 0d ?? 0Dh 0010316f 0e ?? 0Eh 00103170 0f ?? 0Fh 00103171 10 ?? 10h 00103172 11 ?? 11h 00103173 12 ?? 12h 00103174 13 ?? 13h 00103175 14 ?? 14h 00103176 15 ?? 15h 00103177 16 ?? 16h 00103178 17 ?? 17h 00103179 18 ?? 18h 0010317a 19 ?? 19h 0010317b 80 ?? 80h 0010317c 80 ?? 80h 0010317d 80 ?? 80h 0010317e 80 ?? 80h 0010317f 80 ?? 80h 00103180 80 ?? 80h 00103181 1a ?? 1Ah 00103182 1b ?? 1Bh 00103183 1c ?? 1Ch 00103184 1d ?? 1Dh 00103185 1e ?? 1Eh 00103186 1f ?? 1Fh 00103187 20 ?? 20h 00103188 21 ?? 21h ! 00103189 22 ?? 22h " 0010318a 23 ?? 23h # 0010318b 24 ?? 24h $ 0010318c 25 ?? 25h % 0010318d 26 ?? 26h & 0010318e 27 ?? 27h ' 0010318f 28 ?? 28h ( 00103190 29 ?? 29h ) 00103191 2a ?? 2Ah * 00103192 2b ?? 2Bh + 00103193 2c ?? 2Ch , 00103194 2d ?? 2Dh - 00103195 2e ?? 2Eh . 00103196 2f ?? 2Fh / 00103197 30 ?? 30h 0 00103198 31 ?? 31h 1 00103199 32 ?? 32h 2 0010319a 33 ?? 33h 3 0010319b 80 ?? 80h 0010319c 80 ?? 80h 0010319d 80 ?? 80h 0010319e 80 ?? 80h 0010319f 80 ?? 80h ........ -
At the
reconpart, in thestringsoutput we saw those table values and the alphabet, and if we take any letter from the alphabet like0x00103120 + to_ascii(letter), we’d end up with some value from the table, e.g.Ain ASCII is0x41->0x00103120 + 0x41 = 0x00103161which is value0,Bis1, and so on. That’s the decoding table! A valid Base64 character map to their position in the alphabet. -
The function performs a validation before decoding: make sure the number of valid Base64 characters is
multiple of 4(standard base64 has length that is multiple of 4) and the buffer is big enough for(count / 4) * 3size. -
4 characters are represented by 3 bytes- the biggest value in such table is0x3fthat fits in 6 bits. Hence we can see a packing algorithm toput four 6-bit values into 3 bytesby shifting bits the following way:*start = local_c[0] << 2 | local_c[1] >> 4; start[1] = local_c[1] << 4 | local_c[2] >> 2; start[2] = local_c[2] << 6 | local_c[3];Here’s how it can be visualised:
00aaaaaa 00bbbbbb 00cccccc 00dddddd PACKED INTO 3 BYTES -> aaaaaabb - bbbbcccc - ccdddddd
Bits shifted past bit 7 are dropped as you can see.
-
As Base64 text comes in groups of 4,
=pads the last group when the data doesn’t fill all 3 bytes. Hence,one =means the last group holds2 real bytes,two =->1 real byte, more=-> invalid (returns 0). -
Return value is calculated like this:
out_ptr - out_start, which is abytes writtenvalue.
Crypto Function Digestion Approach
I had to learn the correct way of digesting such functions. I managed to identify that it’s not a logic, but rather library-like code block that includes magic numbers, math operations, like a crypto function:
- it initializes
state of 25 qwords = 200 bytes = 1600 bits; - a block size of
0x88(136 bytes) is passed to the function; - a padding byte
0x1fis appended after the input (0x1f).
At this point with the given parameters I googled for it and found out that it’s the Keccak-f[1600] hashing function, it’s SHAKE256 version because of the 0x1f padding byte and 136 block size params.
NOTE: I’m not a crypto specialist and never dived into algorithms and math behind crypto functions. I believe that googling and using AI as a search engine in such cases is a great way to make decent progress while still learning and focusing on the logic of the binary. I would trust the hypothesis and verify it quickly.
To prove my finding, I computed the SHAKE256 output stream for the given name with a python script and got 32 bytes that should follow the 2nd 8192-byte chunk (offset 8192 * 2 = 16384):
[elijah@elijah-arch blog]$ python3 -c '
import hashlib
stream = hashlib.shake_256(b"FCSC2026").digest(8192 * 16)
myBytes = stream[16384:16384 + 32].hex()
print(myBytes)
'
825be322d0e97356d582ae384c999cab7ab1df356fefe6aa49fb345358064eda
Then I checked what the program actually produces. Here’s the function call so you can see the arguments:
FUN_00101494(nameInput,g_shared5,8192,&local_1068,32);
In gdb, I set a breakpoint on the call to the FUN_00101494 function, saved the address of its 4th argument (which is local_1068, passed in the RCX register), let the function finish and checked the buffer:
(gdb) b *0x555555555ca5
(gdb) r FCSC2026 MTIzNDU2Nzg5
(gdb) p/x $rcx
$1 = 0x7fffffffd070
(gdb) finish
Run till exit from #0 0x0000555555555494 in ?? ()
(gdb) x/32xb 0x7fffffffd070
0x7fffffffd070: 0x82 0x5b 0xe3 0x22 0xd0 0xe9 0x73 0x56
0x7fffffffd078: 0xd5 0x82 0xae 0x38 0x4c 0x99 0x9c 0xab
0x7fffffffd080: 0x7a 0xb1 0xdf 0x35 0x6f 0xef 0xe6 0xaa
0x7fffffffd088: 0x49 0xfb 0x34 0x53 0x58 0x06 0x4e 0xda
The bytes are identical, which confirms that it’s the real SHAKE256 hashing one!
NOTE: the program reads
8192-byte chunksfrom the stream until another inner function accepts one; forFCSC2026the first chunk is rejected and the second is keptat offset 2 × 8192 = 16384.
TOCTOU Race
Here’s an example of the race condition that might happen in this program I noticed (though, it’s harmless this time). It’s called TOCTOU - Time-of-check to time-of-use race.
pthread_mutex_lock(g_mutex);
blocks_remain = *g_remaining_blocks;
pthread_mutex_unlock(g_mutex);
if (blocks_remain == 0) {
pthread_mutex_lock(g_mutex);
*g_remaining_blocks = *g_remaining_blocks + -1;
pthread_mutex_unlock(g_mutex);
.....
sigqueue(g_shared->pids[value],signo + 16,0x4643534332303236); // "STOP" broadcast
...
In this example we have two mutex locks:
- The first mutex allows us to safely read the value of the shared global.
- The second mutex allows us to safely decrement global’s value.
But between the mutexes there’s the if (blocks_remain == 0) { guard that isn’t protected. In this case, two processes can read block_remain == 0 and both broadcast “STOP”.
In our program it’s harmless because if two STOP messages are broadcasted, then on the former msg a process is stopped, and on the latter it just ignores it pretty much as it was already stopped.
To avoid this problem, we can move the decrement part inside the same lock as the read, so only one process “wins” the 0.
Sattolo Shuffle
I got familiar with an algorithm that shuffles a set of items, an array in my case, and has an interesting side effect. Say, we have to shuffle an array of 16 indicies (0 .. 15) in the way that every spot is visited once before we return to the starting point if we jump by following the indicies.
The Sattolo Shuffle Algorithm does exactly that! It guarantees that a permutation is a single cycle of length n:
- Start at the end of of the array:
array[len - 1]. - Take a random item in the array,
excludingour current position:i = random(start, current - 1)). - Swap the current item and
i:swap(i, current). - Continue moving backwards and repeat the algorithm until everything got swapped.
The algorithm is an updated version of Fisher-Yates Shuffle, which allows an item to stay in place: i = random(start, current), when the Sattolo’s one requires and item to be swapped with an earlier one.
Conclusion
This was a big challenge to tackle, it took me a few days to capture the flag. At some point, I was frustrated with the amount of data and knowledge to digest and learn: multi-process binary reversing, signals as data channels, identifying crypto by constants and more.
The most interesting part was the keygen program implementation in Rust as I was glad to finally spend more time programming than reversing.
I’ll take a break from Hackropole challenges and decide on my next steps to become a better engineer, see you in the next blog post! :)
