[💠 Platinum 4] 0의 런렝스를 감마 코드로 되감기 — DreamHack Run 풀이

file extracted/main extracted/flag.enc; ls -l extracted; readelf -h extracted/main | grep -E "Type|Entry|Machine"

readelf --dyn-syms -W extracted/main

strings -a extracted/main | wc -l; strings -a extracted/main | grep -nE "enc|flag|GoN|%"

objdump -d -M intel --no-show-raw-insn --start-address=0xda5 --stop-address=0xe24 extracted/main | sed -f annot_main.sed

objdump -d -M intel --no-show-raw-insn --start-address=0xe58 --stop-address=0xee5 extracted/main | sed -f annot_main.sed

int main(int argc, char **argv) {
    BitStream src, dst;
    if (argc != 2) exit(1);
 
    int fd = open(argv[1], O_RDONLY);
    if (fd == -1) exit(1);
    read_file(&src, fd);                       /* 파일 전체 -> src */
    close(fd);
 
    bs_init(&dst, 0x1000);                     /* 출력 버퍼 4KB 로 시작 */
    encode(&src, &dst);
 
    char *path = malloc(strlen(argv[1]) + 5);  /* ".enc" + NUL */
    if (!path) exit(1);
    sprintf(path, "%s.enc", argv[1]);
 
    fd = open(path, O_CREAT | O_WRONLY, 0600);
    if (fd == -1) exit(1);
    write(fd, &src.cap, 8);                    /* 헤더 8바이트 */
    flush(&dst, fd);                           /* 인코딩 본문 */
    close(fd);
    free(path);
    return 0;
}

typedef struct {
    char  *buf;   /* +0x00 */
    size_t pos;   /* +0x08  현재 위치 — 바이트가 아니라 비트 단위 */
    size_t cap;   /* +0x10  용량   — 역시 비트 단위 */
} BitStream;

void bs_init(BitStream *bs, size_t n) {        /* 0xb2c */
    if (n > 0x1fffffffffffffff) exit(1);
    bs->buf = malloc(n);
    bs->cap = n * 8;                           /* n 바이트 = n*8 비트 */
    bs->pos = 0;
}
 
void read_file(BitStream *bs, int fd) {        /* 0xb8f */
    size_t sz = lseek(fd, 0, SEEK_END);
    bs_init(bs, sz);
    lseek(fd, 0, SEEK_SET);
    if (read(fd, bs->buf, sz) != sz) exit(1);
}
 
void put_bit(BitStream *bs, int b) {           /* 0x97a */
    if (bs->pos >= bs->cap) {
        bs->cap *= 2;
        bs->buf = realloc(bs->buf, bs->cap);   /* 비트 수를 바이트 수로 넘긴다 */
        if (!bs->buf) exit(1);
    }
    bs->buf[bs->pos >> 3] &= ~(1 << (bs->pos & 7));
    bs->buf[bs->pos >> 3] |= (b != 0) << (bs->pos & 7);
    bs->pos++;
}
 
int get_bit(BitStream *bs) {                   /* 0xaad */
    if (bs->pos >= bs->cap) exit(1);
    return (bs->buf[bs->pos >> 3] >> (bs->pos++ & 7)) & 1;
}
 
void flush(BitStream *bs, int fd) {            /* 0xc08 */
    while (bs->pos & 7) put_bit(bs, 1);        /* 남는 자리는 1 로 채운다 */
    write(fd, bs->buf, bs->pos >> 3);
}

objdump -d -M intel --no-show-raw-insn --start-address=0xc60 --stop-address=0xcdb extracted/main | sed -f annot_encode.sed

ca9:   test   eax,eax          ; 방금 읽은 비트
cab:   je     c7f              ; 0 이면 c7f 로 -- c7f 는 count++ 하는 자리다

objdump -d -M intel --no-show-raw-insn --start-address=0xcdb --stop-address=0xd6a extracted/main | sed -f annot_encode.sed

void encode(BitStream *src, BitStream *dst) {
    while (src->pos < src->cap) {
        size_t count = 0;
        while (get_bit(src) == 0) {                    /* 0 을 센다 */
            if (src->pos >= src->cap) return;
            count++;
        }
        if (count == 0) { put_bit(dst, 0); put_bit(dst, 0); continue; }
 
        size_t nbits = 64 - __builtin_clzll(count);    /* count 의 비트길이 */
        for (int i = 0; i < nbits - 1; i++) put_bit(dst, 1);
        put_bit(dst, 0);
        for (int j = 0; j < nbits; j++) { put_bit(dst, count & 1); count >>= 1; }
    }
}

set confirm off
set pagination off
starti
python
import gdb
base = None
for line in gdb.execute("info proc mappings", to_string=True).splitlines():
    if line.rstrip().endswith("/main"):        # PIE 베이스는 가정하지 않고 매핑에서 읽는다
        base = int(line.split()[0], 16)
        break
gdb.execute("set $base = %#x" % base)
print("PIE base            = %#x" % base)
end
break *($base + 0xc60)
break *($base + 0xcdb)
continue
printf "encode(src=%p, dst=%p)\n", $rdi, $rsi
printf "  src->buf          = %p\n", *(long *)$rdi
printf "  src->pos          = %ld\n", *(long *)($rdi + 8)
printf "  src->cap          = %ld bits = %ld B\n", *(long *)($rdi + 16), *(long *)($rdi + 16) / 8
printf "  src->buf[0..3]    = %02x %02x %02x %02x\n", *(unsigned char *)(*(long *)$rdi), *(unsigned char *)(*(long *)$rdi + 1), *(unsigned char *)(*(long *)$rdi + 2), *(unsigned char *)(*(long *)$rdi + 3)
continue
printf "count != 0 인 첫 코드워드 (0xcdb)\n"
printf "  count             = %ld\n", *(long *)($rbp - 0x10)
printf "  src->pos          = %ld  (소비한 원본 비트)\n", *(long *)(*(long *)($rbp - 0x28) + 8)
printf "  dst->pos          = %ld  (뱉은 출력 비트)\n", *(long *)(*(long *)($rbp - 0x30) + 8)
kill

gdb -q -batch -x cmds.gdb --args extracted/main flag.png

#!/usr/bin/env python3
"""flag.enc 앞 8바이트(= 인코더가 써 넣은 src->cap)를 읽어 원본 크기를 역산한다."""
import sys
 
blob = open(sys.argv[1], 'rb').read()
n_bits = int.from_bytes(blob[:8], 'little')
print(f'파일 전체      : {len(blob)} B')
print(f'헤더 8바이트   : {blob[:8].hex(" ")}')
print(f'-> src->cap    : {n_bits} bits = {n_bits // 8} B  (원본 파일 크기)')
print(f'인코딩 본문    : {len(blob) - 8} B')
print(f'비율           : {(len(blob) - 8) / (n_bits // 8):.3f} 배  (늘어난 게 아니라 줄었다)')
print(f'본문 첫 4바이트: {blob[8:12].hex(" ")}')
bits = ''.join(f'{blob[8 + i]:08b}'[::-1] for i in range(3))   # 바이트 안에서 LSB-first
print(f'-> 비트열(LSB-first) : {bits}')

python3 read_header.py extracted/flag.enc

#!/usr/bin/env python3
"""main 바이너리(0-런렝스 + Elias-gamma 인코더)의 역함수.
 
파일 포맷 : [8바이트 LE = 원본 비트수 N] + [인코딩 비트스트림, 바이트 안에서 LSB-first]
코드워드  : (nbits-1)개의 1 → 0 → count 의 nbits 비트(LSB-first)
복원      : count 개의 0 비트 + 1 비트 하나  를 이어 붙여 N 비트를 채운다
            (encode 0xc60 의 `test eax,eax; je` 가 '0 을 세는' 루프라는 점이 핵심)
"""
import sys
 
 
class BitReader:
    def __init__(self, data):
        self.d = data
        self.n = len(data) * 8
        self.p = 0
 
    def bit(self):
        i = self.p
        if i >= self.n:
            raise EOFError
        self.p = i + 1
        return (self.d[i >> 3] >> (i & 7)) & 1
 
 
def decode(blob):
    n_bits = int.from_bytes(blob[:8], 'little')      # src->cap = 원본 바이트수 * 8
    br = BitReader(blob[8:])
    out = bytearray((n_bits + 7) // 8)               # 0 으로 시작 → 0 비트는 그냥 건너뛴다
    pos = 0
    while pos < n_bits:
        try:
            k = 0                                    # 0 이 나올 때까지 1 을 센다 → nbits = k+1
            while br.bit():
                k += 1
            count = 0
            for j in range(k + 1):                   # count 의 비트를 LSB-first 로
                count |= br.bit() << j
        except EOFError:
            break
        pos += count                                 # 0 이 count 개
        if pos < n_bits:                             # 런을 끝내는 1
            out[pos >> 3] |= 1 << (pos & 7)
            pos += 1
    return bytes(out[:n_bits // 8]), pos, n_bits
 
 
if __name__ == '__main__':
    src, dst = sys.argv[1], sys.argv[2]
    blob = open(src, 'rb').read()
    res, pos, n_bits = decode(blob)
    open(dst, 'wb').write(res)
    print(f'{src} ({len(blob)}B) -> {dst} ({len(res)}B), 복원 비트 {pos}/{n_bits}')

#!/usr/bin/env python3
"""Run (DreamHack Platinum 4) — flag.enc 한 방 복원.
 
1) flag.enc 를 역RLE-gamma 로 풀어 원본 PNG 를 되살린다  (decode.py)
2) 되살린 10000x10000 PNG 에서 잉크가 있는 영역을 찾고, 오른쪽 러너 아이콘을
   가장 넓은 빈 열 구간에서 잘라내 글자 줄만 남긴다
3) 그 조각을 tesseract 로 읽어 flag 문자열을 뽑는다
"""
import re
import subprocess
import sys
 
from PIL import Image, ImageOps
 
from decode import decode
 
Image.MAX_IMAGE_PIXELS = None          # 우리가 방금 만든 파일이라 폭탄 경고는 무의미하다
 
SRC = sys.argv[1] if len(sys.argv) > 1 else 'extracted/flag.enc'
PNG = sys.argv[2] if len(sys.argv) > 2 else 'flag.png'
CROP = 'flag_crop.png'
 
 
def split_off_icon(ink):
    """열 단위 잉크 합에서 가장 긴 빈 구간을 찾아 그 왼쪽(=글자 줄)만 돌려준다."""
    w, h = ink.size
    col = [0] * w
    px = ink.load()
    for x in range(w):
        s = 0
        for y in range(0, h, 4):       # 4행마다 훑어도 빈 열 판정에는 충분하다
            s += px[x, y]
        col[x] = s
    best_len, best_end, run = 0, 0, 0
    for x in range(w):
        if col[x] == 0:
            run += 1
            if run > best_len:
                best_len, best_end = run, x
        else:
            run = 0
    if best_len < 40:                  # 뚜렷한 공백이 없으면 통째로 쓴다
        return ink.getbbox()
    cut = best_end - best_len + 1
    return ink.crop((0, 0, cut, h)).getbbox()
 
 
def main():
    blob = open(SRC, 'rb').read()
    png, pos, n_bits = decode(blob)
    open(PNG, 'wb').write(png)
    print(f'[1] {SRC} ({len(blob)}B) -> {PNG} ({len(png)}B), 복원 비트 {pos}/{n_bits}')
    print(f'[1] magic = {png[:8].hex(" ")}')
 
    im = Image.open(PNG)
    print(f'[2] 복원된 이미지: {im.size[0]}x{im.size[1]} {im.mode}')
 
    gray = im.convert('L')                       # 알파를 버리고 밝기만 본다
    ink = gray.point(lambda p: 255 if p > 40 else 0)
    box = ink.getbbox()
    print(f'[2] 잉크 전체 영역 = {box}')
 
    sub = ink.crop(box)
    tb = split_off_icon(sub)
    text_box = (box[0] + tb[0], box[1] + tb[1], box[0] + tb[2], box[1] + tb[3])
    print(f'[2] 아이콘을 뗀 글자 영역 = {text_box}')
 
    crop = gray.crop(text_box)
    ImageOps.expand(ImageOps.invert(crop), border=60, fill=255).save(CROP)
    print(f'[2] {CROP} 저장 ({crop.size[0]}x{crop.size[1]})')
 
    raw = subprocess.run(['tesseract', CROP, '-', '--psm', '13'],
                         capture_output=True, text=True).stdout.strip()
    print(f'[3] tesseract 원문 = {raw!r}')
    m = re.search(r'GoN\{[^}]*\}', raw)
    print(f'[3] FLAG = {m.group(0) if m else "(못 찾음)"}')
    return 0 if m else 1
 
 
if __name__ == '__main__':
    sys.exit(main())

python3 solve.py

#!/usr/bin/env python3
"""복원한 flag.png 로 글에 넣을 그림 두 장을 만든다.
 
  12_preview.png : 10000x10000 원본을 1000x1000 으로 줄인 전체 미리보기
  13_flag.png    : 글자 줄만 잘라낸 원본 색(검정 배경 흰 글자) 조각
"""
from PIL import Image
 
Image.MAX_IMAGE_PIXELS = None
OUT = '/home/jinho/homepage/public/images/blog/dreamhack-run-writeup'
 
im = Image.open('flag.png').convert('RGB')
im.resize((1000, 1000), Image.LANCZOS).save(f'{OUT}/12_preview.png')
print(f'12_preview.png  <- {im.size[0]}x{im.size[1]} 를 1000x1000 으로')
 
box = (3900, 9140, 8120, 9540)          # solve.py 가 찍어 준 글자 영역에 여백을 더한 값
im.crop(box).save(f'{OUT}/13_flag.png')
print(f'13_flag.png     <- crop{box} = {box[2] - box[0]}x{box[3] - box[1]}')

python3 make_figs.py

#!/usr/bin/env bash
# 복원한 flag.png 를 문제 바이너리에 그대로 재투입해 배포본 flag.enc 와 대조한다.
set -eu
cd "$(dirname "$(readlink -f "$0")")"
mkdir -p roundtrip && cp flag.png roundtrip/flag.png
( cd roundtrip && ../extracted/main flag.png )
sha256sum roundtrip/flag.png.enc extracted/flag.enc
if cmp -s roundtrip/flag.png.enc extracted/flag.enc; then
  echo "MATCH: 재인코딩 결과가 배포본과 바이트 단위로 같다"
else
  echo "DIFF: 모델이 틀렸다"; exit 1
fi

./roundtrip.sh