Skip to content

Instantly share code, notes, and snippets.

@rmmh
Last active December 13, 2015 22:18
Show Gist options
  • Save rmmh/4982924 to your computer and use it in GitHub Desktop.
Save rmmh/4982924 to your computer and use it in GitHub Desktop.
GitS 2013 RTFM

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.

# 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())
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment