Algorithm of Coding

Ссылка на задание http://f8tasks.ru/challenges#Algorithm%20of%20Coding-13

Научились писать алгоритмы сжатия данных, но в обратную сторону пока не получается… Поможешь?

Артефакты: бинарь pack, файл out.pack.

file pack out.pack
strings -n 4 pack | head -40

pack:     ELF 64-bit LSB executable, x86-64, not stripped
out.pack: data
...
MAXIK
out.pack
Enter your data:
MAXIK packed your data successfully!
collectDataInfo
encode

Ключевые наблюдения:

• pack — исполняемый ELF с сохранёнными символами (not stripped).
• out.pack — бинарный файл нестандартного формата: file возвращает только data.
• Magic-строка MAXIK в секции .rodata — маркер формата файла.
• Имена функций collectDataInfo и encode видны прямо в strings — бинарь отдаёт карту.
• Нет ни Wrong password, ни Correct. Программа не проверяет флаг — она его кодирует.

Проверка поведения на тестовом вводе:

printf 'AAAAAAAAAAAA\n' | ./pack

0.500000

Вывод: программа принимает строку, печатает вещественное число и создаёт out.pack. Задача — не «угадай пароль», а обратный ход алгоритма кодирования.

. Каждый символ сужает текущий интервал пропорционально своей вероятности в тексте.

Проверяем символы бинаря:

nm -C pack | grep -E 'collectDataInfo|encode|main|DataInfo'

main
collectDataInfo(char*)
encode(char*, DataInfo*)

collectDataInfo строит вероятностную модель строки:

1. Считает частоты $$count(c)$$ для каждого из 256 возможных байт.
2. Нормирует: $$p(c) = \dfrac{count(c)}{len(\text{text})}$$.
3. Строит накопленные суммы — каждому символу присваивается подынтервал $$[\text{low}(c),\, \text{high}(c))$% в $$[0,1)$$.

encode проходит по символам строки и последовательно сужает интервал $[L, H)$:

Финальный интервал очень мал; бинарь берёт одно число из него и записывает в out.pack.

Восстанавливаем из main через дизасм:

objdump -d -Mintel pack | grep -A 200 '<main>'

Таблица: $256 \times 3 \times 8 = 6144$ байта. Весь файл — 6161 байт.

Ключевой вывод: файл содержит всё необходимое для декодирования — без самого бинаря.

Алгоритм обратного хода — декодер воспроизводит символы один за одним:

Ручной расчёт первого шага: encoded_value ≈ 0.0181..., таблица показывает, что символ f (0x66) имеет подынтервал, который содержит это значение — первый символ флага восстановлен. Дальше — скрипт.

import struct
from pathlib import Path


def read_pack(path: str):
    blob = Path(path).read_bytes()
    magic = blob[:5]
    if magic != b"MAXIK":
        raise ValueError(f"Unexpected magic: {magic!r}")

    # encoded_value — вещественное число в формате IEEE 754 double
    value = struct.unpack("<d", blob[5:13])[0]
    # text_len — длина исходного текста в байтах
    text_len = struct.unpack("<I", blob[13:17])[0]
    # 256 записей по 24 байта: (probability, cumulative_low, cumulative_high)
    entries = [
        struct.unpack("<ddd", blob[17 + index * 24:17 + (index + 1) * 24])
        for index in range(256)
    ]
    return value, text_len, entries


def decode_arithmetic(value: float, text_len: int, entries):
    low = 0.0
    high = 1.0
    output = []

    for _ in range(text_len):
        current_range = high - low
        for byte_value, (_, cumulative_low, cumulative_high) in enumerate(entries):
            candidate_low = low + current_range * cumulative_low
            candidate_high = low + current_range * cumulative_high

            if candidate_low <= value < candidate_high:
                output.append(byte_value)
                low, high = candidate_low, candidate_high  # сузить интервал
                break
        else:
            raise ValueError("Failed to decode arithmetic-coded stream")

    return bytes(output)


def main():
    value, text_len, entries = read_pack("out.pack")
    plaintext = decode_arithmetic(value, text_len, entries)
    print(plaintext.decode())


if __name__ == "__main__":
    main()

python3 solve.py
# flag{alzha4n0}

1. Бинарь — не всегда проверка пароля. Иногда программа только создаёт артефакт. Всегда первый вопрос: «что она делает?» — а не «где сравнивает флаг».
2. Non-stripped бинарь дарит имена функций. collectDataInfo и encode сразу указали на статистику и кодирование; main раскрыл формат файла — дизасм лишь подтвердил гипотезу.
3. Ловушка задачи — поиск strcmp. Новички тратят время на Wrong/Correct, которого здесь нет. Флаг спрятан в out.pack и ждёт декодера, а не взлома.