task2.out

Platform: spbctf | Category: Reversing | Type: Challenge | Difficulty: Easy | OS: Windows | Author: XESXOR | Date: 2020-01-01 | Status: Solved Techniques: static_analysis, affine_cipher_bruteforce, modular_arithmetic, python_reimplementation

Summary

Task: 32-bit ELF binary accepts two letters as arguments, applies affine cipher transformation to encoded string. Solution: Brute force 29x29 key combinations to find k1=7 ('h'), k2=13 ('n') that decodes to flag.

task2.out — spbctf (rev-kids20)

Description

Download binary: task2.out (ELF) / task2.exe (Windows PE). The app accepts two letters as command line arguments. If you give it correct letters, it will print the flag.

English summary: A 32-bit ELF binary takes two single-letter command line arguments and uses them as keys to decode an encoded string. The goal is to find the correct two letters.

Analysis

Binary reconnaissance

 bash read-only • copy allowed Copy
$ file task2.out
task2.out: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, 
           interpreter /lib/ld-linux.so.2, for GNU/Linux 2.6.32, not stripped
‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

$ strings task2.out | grep -E "abcdef|Wrong"
abcdefghijklmnopqrstuvwxyz{}_
Wrong input
WHAAAAAT?
Sorry, bro

The binary is not stripped, revealing useful symbols:

• main - entry point
• get_idx - converts character to index in custom alphabet
• transform - applies the cipher transformation

Key data structures

1. Custom alphabet (29 characters): abcdefghijklmnopqrstuvwxyz{}_
2. Encoded string: dix_gyhiiz}xdduah}puvyhn}u}pxa}tnbfh}ozbc

Algorithm identification

The binary implements an affine cipher — a classical substitution cipher with the formula: ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

new_char = alphabet[(idx * k1 + k2) % 29]

Where:

• idx = index of input character in the alphabet
• k1, k2 = keys derived from the two command line arguments
• 29 = alphabet length (modulus)

Function analysis

1. get_idx(char) — converts a character to its index in the custom alphabet (0-28)
2. transform(encoded_string, k1, k2) — applies affine transformation to each character
3. main — parses two single-letter arguments, converts to indices via get_idx, calls transform ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

Solution

Since the binary accepts only two letters from a 29-character alphabet, there are at most 29×29 = 841 combinations — easily brute-forceable.

Python brute force script

 python read-only • copy allowed Copy
#!/usr/bin/env python3

encoded = "dix_gyhiiz}xdduah}puvyhn}u}pxa}tnbfh}ozbc"
alphabet = "abcdefghijklmnopqrstuvwxyz{}_"

def get_idx(c):
    return alphabet.index(c)

def transform(c, key1, key2):
    idx = get_idx(c)
    new_idx = (idx * key1 + key2) % 29
    return alphabet[new_idx]

def decode(s, key1, key2):
    return "".join(transform(c, key1, key2) for c in s)
‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

# Brute force all 29*29 = 841 combinations
for k1 in range(29):
    for k2 in range(29):
        decoded = decode(encoded, k1, k2)
        if '{' in decoded and '}' in decoded:
            brace_pos = decoded.index('{')
            if brace_pos > 0 and decoded.endswith('}'):
                prefix = decoded[:brace_pos]
                if prefix.isalpha():
                    print(f"k1={k1} ({alphabet[k1]}), k2={k2} ({alphabet[k2]}): {decoded}")

Result

k1=7 (h), k2=13 (n): flag{REDACTED}

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

Verification

 bash read-only • copy allowed Copy
$ ./task2.out h n
flag{REDACTED}

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