reversefreemedium

bike

b01lersc

Task: 64-bit ELF builds a Shannon-Fano-like prefix-code tree from a global frequency table, walks 32 bytes of user input bit-by-bit, and compares the decoded leaf sequence to a fixed 35-byte buffer. Solution: faithfully reconstruct the tree using float32 arithmetic (critical), encode the expected bytes via the resulting codebook, and pack the 246-bit stream MSB-first into 31 input bytes.

$ ls tags/ techniques/
elfx86_64bit_packingshannon_fanoprefix_codefloat32custom_treefull_mitigations
reverse_engineeringshannon_fano_tree_reconstructionprefix_code_encodingfloat32_precision_matchingbit_stream_packing

$ cat /etc/rate-limit

Rate limit reached (20 reads/hour per IP). Showing preview only — full content returns at the next hour roll-over.

bike — b01lersc

Description

Get your bike down from the tree!!

A 64-bit ELF binary with all modern mitigations enabled (Full RELRO, Stack canary, NX, PIE, SHSTK, IBT). The program asks for input, decodes it bit-by-bit through a tree built from a global frequency table, and compares the decoded output against a fixed 35-byte buffer. The goal is to find the input that produces the expected decoded sequence — which spells out the flag.

Analysis

Program structure

The binary contains three functions:

  • setup — disables stdout buffering.
  • build_tree(arr, lo, hi) — recursive constructor that returns a pointer to a node (leaf or internal).
  • main — reads up to 31 bytes via fgets, walks them through the tree, and compares against the global expected buffer.

The global data

At VA 0x4020 there is a freqs array of 128 entries, each laid out as:

struct entry {
    uint8_t  byte;    // +0x00
    uint8_t  pad[3];  // +0x01..+0x03
    float    freq;    // +0x04 (float32)
};   // sizeof = 8

The table covers all 128 ASCII values in a specific (non-monotonic within tied freqs) order. Frequencies are in descending order and take one of the following values:

0.18, 0.16, 0.13, 0.12, 0.11, 0.10, 0.09, 0.08, 0.07, 0.06, 0.05, 0.04, 0.03, 0.02

At VA 0x4420 there is a 35-byte expected buffer:

53 03 64 52 55 3e 4a 6b 04 66 0f 26 4c 42 3c 18
58 4a 43 53 16 63 7f 0d 0a 36 0b 16 4c 44 05 2c
74 45 43

How build_tree works

This is a classic top-down Shannon–Fano-style split on an already sorted-by-frequency array:

Node *build_tree(entry *arr, int lo, int hi) {
    if (lo == hi)
        return leaf(arr[lo].byte, arr[lo].freq);

...

$ grep --similar

Similar writeups