shell(de)coding

Platform: hxp_39c3 | Category: Misc | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2025-12-28 | Status: Solved Techniques: compact_arithmetic, probabilistic_decoding, register_reuse

Summary

Task: Write x86-64 shellcode under 42 bytes to decode Base64. Solution: Probabilistic approach ignoring +/- characters (~25% success rate), compact assembly with register reuse and stosd trick for 3-byte writes.

shell(de)coding — hxp 39C3

Description

The task was to write x86-64 shellcode less than 42 bytes long that decodes a random 32-byte secret encoded in Base64 (44 characters). The shellcode runs in the Unicorn emulator.

Analysis

The standard Base64 decoding process converts 4 characters (6 bits each) into 3 bytes (24 bits total). Key constraints:

• Shellcode length: < 42 bytes.
• Input data: RDI = output buffer, RSI = input buffer (Base64), RDX = input length (44).
• Environment: Unicorn emulator. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Due to the extremely tight size limit (41 bytes), implementing a full Base64 decoder handling all 64 alphabet characters (A-Z, a-z, 0-9, +, /) is extremely difficult.

Solution

Probabilistic Approach

The key idea for size optimization is ignoring the + and / characters. Since the secret is randomly generated, the probability that none of the 44 Base64 characters contain + or / is: $$(62/64)^{44} \approx 0.247 \text{ (about 24.7%)}$$

This allows significantly simplifying the character mapping logic by simply skipping the check for special characters. If + or / appear, the decoding will be incorrect, but we can just restart the solution until we get a "clean" string. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Assembly Optimization

1. Accumulator: Using EBX as a 24-bit accumulator.
2. Input/Output: lodsb for reading and a combination of stosd + dec edi for writing 3 bytes (write 4, shift pointer back by 1).
3. Character mapping:
   • sub al, 65 converts A-Z to 0-25.
   • If the result is negative (character is a digit), add offsets to get the correct value.
   • For lowercase letters a-z, subtract an additional constant.

Shellcode (41 bytes)

 hex read-only • copy allowed Copy
6a045931dbc1e306ac2c417304044504063c1a72022c0608c3e2ea930fc8c1e808abffcf83ea0475d7

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Source Code (ASM)

 asm read-only • copy allowed Copy
BITS 64
main:
    push 4
    pop rcx             ; Inner counter (4 characters)
    xor ebx, ebx        ; Clear accumulator
.inner:
    shl ebx, 6          ; Shift accumulator by 6 bits
    lodsb               ; Load next Base64 character
    sub al, 65          ; Map A-Z (65-90 -> 0-25)
    jnc .L1             ; If >= 0, it's a letter (or digit/special char above)
    add al, 69          ; Map digits (part 1)
    add al, 6           ; Map digits (part 2)
.L1:
    cmp al, 26          ; Check if character is uppercase
    jb .L2
    sub al, 6           ; Map lowercase letters (a-z)
.L2:
    or bl, al           ; Add 6 bits to accumulator
    loop .inner
    xchg eax, ebx       ; Prepare for output
    bswap eax           ; Fix byte order (endianness)
    shr eax, 8          ; Align 24 bits
    stosd               ; Write 4 bytes to RDI
    dec edi             ; Adjust pointer (-1, net +3 bytes)
    sub edx, 4          ; Outer counter (44 / 4 = 11 iterations)
    jnz main

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍