Liminal - Reverse Engineering

Points: 645 (Hard) | Flag: 0xfun{0x4c8e40be1e97f544} | Solved by: Smothy @ 0xN1umb

what we got

A stripped ELF 64-bit binary called liminal. The description is super cryptic talking about "spaces between", "shadows left in silicon", "operations that both happen and don't". Classic speculative execution vibes ngl.

The goal: find an input that produces 0x4C494D494E414C21 (which is "LIMINAL!" in ASCII lmao).

first look

$ file liminal
ELF 64-bit LSB executable, x86-64, dynamically linked, stripped

$ strings liminal | grep -i spec
This binary requires speculative execution side-channels.

bruh. it literally tells you it needs Spectre. running it:

so we can't just run it and brute force. gotta reverse the whole thing statically. cool cool cool.

the solve

understanding the architecture

threw it in objdump and started tracing from main. the binary:

1. parses hex input via strtoull(argv[1], &endptr, 16)
2. calibrates (checks if your CPU supports Flush+Reload timing)
3. calls compute function 50 times, takes majority vote
4. prints compute(input) = output

the compute function at 0x405b37 is where the magic happens. after staring at it for a while... it's an SPN cipher (Substitution-Permutation Network). 8 rounds. beautiful.

the cipher structure

the spectre sauce

here's where it gets wild. each S-box byte lookup is done through speculative execution side channels. for real.

each bit of each S-box output is computed by a separate function that:

1. flushes two probe cache lines (clflush)
2. calls a training function that manipulates the return stack buffer
3. speculatively accesses base + table[input_byte] where table[input_byte] is either 0x100 or 0x340
4. times access to both probes via rdtscp
5. if probe 1 is faster than probe 0 → returns 1, else → returns 0

the training function at 0x401440 is lowkey genius:

lea  0x239(%rip), %rax    ; load addr of a `ret` gadget
push %rax                  ; push it on stack
clflush (%rsp)            ; flush from cache (slow fetch on ret)
mfence
xor %rax, %rax
ret                        ; returns to the ret gadget → back to caller

this causes return address misprediction which triggers speculative execution of the table lookup. the speculative access brings a cache line into L1/L2, and the Flush+Reload timing detects which one. classic Spectre v1.

the calibration function

the calibration at 0x406298 confirmed the bit interpretation for me:

• it randomly accesses probe 0 or probe 1
• then checks if timing correctly identifies which was accessed
• needs 70/100 success rate

from this i confirmed: table_value = 0x100 maps to bit 0, table_value = 0x340 maps to bit 1.

extracting the cipher components

8 round keys at 0x42f2c0:

keys = [
    0xeff230922b8f2f34, 0xb7acc594df2767b4,
    0x15194c24bd0f9e09, 0x2420afeac6c5e1ec,
    0x8a818effc7402e80, 0x81997bb21d2231bb,
    0x1abd026bbf95ef64, 0xbfc90d85da8f9378
]

64-bit permutation table at 0x42f280:

perm = [19, 61, 28, 7, 45, 56, 51, 53, 35, 2, 5, 57, 14, 32, 21, 16,
        47, 4, 50, 10, 43, 60, 46, 23, 20, 44, 11, 26, 38, 48, 40, 24,
        22, 18, 17, 55, 62, 42, 0, 12, 52, 1, 30, 59, 58, 6, 36, 39,
        63, 3, 29, 54, 31, 9, 37, 13, 49, 34, 27, 25, 8, 33, 15, 41]

8 S-boxes extracted from 64 lookup tables starting at 0x40f280 with 0x800 stride. each table has 256 qword entries (0x100 or 0x340). 8 tables per S-box (one per output bit), 8 S-boxes total = 64 tables. all verified as bijections.

inverting the cipher

standard SPN inversion - undo operations in reverse order:

def decrypt(ciphertext):
    state = inv_sub(ciphertext)      # undo final SubBytes
    state ^= keys[7]                  # undo final key XOR
    for r in range(6, -1, -1):
        state = inv_perm(state)       # undo permutation
        state = inv_sub(state)        # undo SubBytes
        state ^= keys[r]             # undo key XOR
    return state

getting the flag

>>> target = 0x4C494D494E414C21  # "LIMINAL!"
>>> answer = decrypt(target)
>>> hex(answer)
'0x4c8e40be1e97f544'
>>> hex(encrypt(answer))
'0x4c494d494e414c21'  # verified!

ez. well... "ez" after understanding speculative execution side channels at 3am lmao

flag

0xfun{0x4c8e40be1e97f544}

key takeaways

• the binary is literally a Spectre PoC wrapped in an SPN cipher. you don't need to RUN it - just reverse the S-box tables from the data section
• the "speculative execution" is the side channel mechanism for S-box lookup, but the underlying math is a standard block cipher
• calibration function was clutch for confirming bit interpretation (0x100 → 0, 0x340 → 1)
• challenge name "Liminal" = existing in the space between. like speculative execution - computations that both happen and don't. clever fr

smothy out ✌️