GitS 2013 RTFM

GitS_2013_RTFM.md

I reverse engineered the binary to find the encoding function, converted it to Python, and verified correctness. I then wasted a bunch of time making an iterative bruteforcer, until I realized that the encoding function is basically equivalent to:

bits('RTFM') + tab[buf[0]] + '00' + tab[buf[1]] + '00' + ... + tab[buf[n]]

where tab is a mapping from ascii characters to variable-length bitstrings, with the important property that they start and end with 1s, and contain no 00s. (match /^1.*1$/ but not /00/)

After that, decoding is simple.

rtfm.py

# extracted from rtfm binary
tab = [683, 731, 749, 887, 747, 863, 751, 765, 767, 239, 29,
879, 733, 31, 885, 939, 759, 757, 941, 943, 859, 875, 877, 855,
891, 893, 951, 853, 861, 955, 763, 895, 1, 511, 351, 501, 475,
725, 699, 383, 251, 247, 367, 479, 117, 53, 87, 431, 183, 189,
237, 255, 375, 347, 363, 429, 427, 439, 245, 445, 493, 85, 471,
687, 701, 125, 235, 173, 181, 119, 219, 253, 341, 127, 509, 381,
215, 187, 221, 171, 213, 477, 175, 111, 109, 343, 437, 349, 373,
379, 685, 503, 495, 507, 703, 365, 735, 11, 95, 47, 45, 3, 61, 91,
43, 13, 491, 191, 27, 59, 15, 7, 63, 447, 21, 23, 5, 55, 123, 107,
223, 93, 469, 695, 443, 693, 727, 949]

def decode(buf):
    bufbits = ''.join('{:08b}'.format(ord(c)) for c in buf[4:])

    char = {'{:b}'.format(c): chr(n) for n, c in enumerate(conv0)}
    char[''] = ''

    out = ''.join(char[bits] for bits in bufbits.split('00'))

    return out

print decode(open("rtfm-e24f03bb1204f8e3d40fae8ac135187a11b0ba5c").read())

rtm_encode.py

import random
import subprocess
import os

# table extracted from rtfm binary
conv0 = [683, 731, 749, 887, 747, 863, 751, 765, 767, 239, 29,
879, 733, 31, 885, 939, 759, 757, 941, 943, 859, 875, 877, 855,
891, 893, 951, 853, 861, 955, 763, 895, 1, 511, 351, 501, 475,
725, 699, 383, 251, 247, 367, 479, 117, 53, 87, 431, 183, 189,
237, 255, 375, 347, 363, 429, 427, 439, 245, 445, 493, 85, 471,
687, 701, 125, 235, 173, 181, 119, 219, 253, 341, 127, 509, 381,
215, 187, 221, 171, 213, 477, 175, 111, 109, 343, 437, 349, 373,
379, 685, 503, 495, 507, 703, 365, 735, 11, 95, 47, 45, 3, 61, 91,
43, 13, 491, 191, 27, 59, 15, 7, 63, 447, 21, 23, 5, 55, 123, 107,
223, 93, 469, 695, 443, 693, 727, 949]

conv1 = [10, 10, 10, 10, 10, 10, 10, 10, 10, 8, 5, 10, 10, 5, 10,
10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
10, 1, 9, 9, 9, 9, 10, 10, 9, 8, 8, 9, 9, 7, 6, 7, 9, 8, 8, 8,
8, 9, 9, 9, 9, 9, 9, 8, 9, 9, 7, 9, 10, 10, 7, 8, 8, 8, 7, 8,
8, 9, 7, 9, 9, 8, 8, 8, 8, 8, 9, 8, 7, 7, 9, 9, 9, 9, 9, 10,
9, 9, 9, 10, 9, 10, 4, 7, 6, 6, 2, 6, 7, 6, 4, 9, 8, 5, 6,
4, 3, 6, 9, 5, 5, 3, 6, 7, 7, 8, 7, 9, 10, 9, 10, 10, 10
]

def rtfm(text):
    output = [0] * 0x200
    output[0] = ord('R')
    output[1] = ord('T')
    output[2] = ord('F')
    output[3] = ord('M')

    length = 4
    bit = 0
    for c in text:
        val = ord(c)
        v9 = conv0[val]
        v8 = conv1[val]
        mask = (v9 << ((16 - v8) & 0xFF)) & 0xFFFFFFFF
        for _ in xrange(0, v8 + 2):
            output[length] = (output[length] * 2) & 0xFF
            output[length] |= (mask & 0xFF00) >> 15
            mask *= 2
            bit += 1
            if bit > 7:
                bit = 0
                length += 1
        if length + 10 > len(output):
            output.extend([0] * len(output))

    return output[:length+1]

def hexlify(r):
    if isinstance(r, str):
        r = map(ord, r)
    return ''.join("%02x " % c for c in r)


def rnd_string(n):
    return ''.join(chr(random.randint(1, 127)) for _ in range(n))

def check():
    for n in range(100):
        print n
        s = rnd_string(800)
        f = open("check_in", "wb")
        f.write(s)
        f.flush()
        f.close()

        subprocess.check_output(['./rtfm-67cc5dcb69df4244bcf2d573481e6d6a06b861a3', 'check_in'])

        rtfm_good = open('check_in.rtfm', 'rb').read()
        os.unlink('check_in.rtfm')

        rtfm_mine = ''.join(map(chr, rtfm(s)))

        assert rtfm_good[:-1] == rtfm_mine[:-1]

check()