09
Jan
2012

GitS teaser 2012 – TeL aViv+

We have a file and the assignment to “get the password”. Ok, let’s see what kind of file it is:

$ file 7139a4ea239dcac655f7c38ca6a77b61.bin 
7139a4ea239dcac655f7c38ca6a77b61.bin: tcpdump capture file (little-endian) - version 2.4 (Ethernet, capture length 65535)

Looks like a packet forensics challenge!

It’s not a very big file, so let’s just take quick look at what it contains using tcpdump.

$ tcpdump -r 7139a4ea239dcac655f7c38ca6a77b61.bin
reading from file 7139a4ea239dcac655f7c38ca6a77b61.bin, link-type EN10MB (Ethernet)
21:58:15.174774 IP localhost.41699 > localhost.2011: Flags [S], seq 1869455239, win 32792, options [mss 16396,sackOK,TS val 515426 ecr 0,nop,wscale 7], length 0
21:58:15.174794 IP localhost.2011 > localhost.41699: Flags [S.], seq 1868102644, ack 1869455240, win 32768, options [mss 16396,sackOK,TS val 515426 ecr 515426,nop,wscale 7], length 0
21:58:15.174810 IP localhost.41699 > localhost.2011: Flags [.], ack 1, win 257, options [nop,nop,TS val 515426 ecr 515426], length 0
21:58:15.175125 IP localhost.2011 > localhost.41699: Flags [P.], seq 1:37, ack 1, win 256, options [nop,nop,TS val 515426 ecr 515426], length 36
21:58:15.175155 IP localhost.41699 > localhost.2011: Flags [.], ack 37, win 257, options [nop,nop,TS val 515426 ecr 515426], length 0
21:58:15.176542 IP localhost.41699 > localhost.2011: Flags [P.], seq 1:246, ack 37, win 257, options [nop,nop,TS val 515426 ecr 515426], length 245
21:58:15.176550 IP localhost.2011 > localhost.41699: Flags [.], ack 246, win 265, options [nop,nop,TS val 515426 ecr 515426], length 0
21:58:15.176576 IP localhost.41699 > localhost.2011: Flags [F.], seq 246, ack 37, win 257, options [nop,nop,TS val 515426 ecr 515426], length 0
21:58:15.176840 IP localhost.2011 > localhost.41699: Flags [P.], seq 37:95, ack 247, win 265, options [nop,nop,TS val 515426 ecr 515426], length 58
21:58:15.176855 IP localhost.41699 > localhost.2011: Flags [R], seq 1869455486, win 0, length 0

Note the length fields for the packets: there’s only three packets which actually contain any data.

Let’s dump the packet contents using ‘tcpdump -A -r 7139a4ea239dcac655f7c38ca6a77b61.bin’ to see if it’s a text-based protocol:

$ tcpdump -A -r 7139a4ea239dcac655f7c38ca6a77b61.bin
reading from file 7139a4ea239dcac655f7c38ca6a77b61.bin, link-type EN10MB (Ethernet)
21:58:15.174774 IP localhost.41699 > localhost.2011: Flags [S], seq 1869455239, win 32792, options [mss 16396,sackOK,TS val 515426 ecr 0,nop,wscale 7], length 0
E..<B.@.@...............om...........0....@....
...b........
21:58:15.174794 IP localhost.2011 > localhost.41699: Flags [S.], seq 1868102644, ack 1869455240, win 32768, options [mss 16396,sackOK,TS val 515426 ecr 515426,nop,wscale 7], length 0
E..<..@.@.<.............oX..om.......0....@....
...b...b....
21:58:15.174810 IP localhost.41699 > localhost.2011: Flags [.], ack 1, win 257, options [nop,nop,TS val 515426 ecr 515426], length 0
E..4B.@.@...............om..oX.......(.....
...b...b
21:58:15.175125 IP localhost.2011 > localhost.41699: Flags [P.], seq 1:37, ack 1, win 256, options [nop,nop,TS val 515426 ecr 515426], length 36
E..X&.@.@...............oX..om.......L.....
...b...bWelcome to the Gibson, please login!
21:58:15.175155 IP localhost.41699 > localhost.2011: Flags [.], ack 37, win 257, options [nop,nop,TS val 515426 ecr 515426], length 0
E..4B.@.@...............om..oX.......(.....
...b...b
21:58:15.176542 IP localhost.41699 > localhost.2011: Flags [P.], seq 1:246, ack 37, win 257, options [nop,nop,TS val 515426 ecr 515426], length 245
E..)B.@.@...............om..oX.............
...b...bGitS.Plague..+........W!W.....M]..
h..P-. ...'......... ....:.....;4.7....!x%...K.....!....%....\.....]I3........)..:...9.S
.....9....-......8....../...    ..................L	C.
21:58:15.176550 IP localhost.2011 > localhost.41699: Flags [.], ack 246, win 265, options [nop,nop,TS val 515426 ecr 515426], length 0
E..4&.@.@..*............oX..om.}...	.(.....
...b...b
21:58:15.176576 IP localhost.41699 > localhost.2011: Flags [F.], seq 246, ack 37, win 257, options [nop,nop,TS val 515426 ecr 515426], length 0
E..4B.@.@...............om.}oX.......(.....
...b...b
21:58:15.176840 IP localhost.2011 > localhost.41699: Flags [P.], seq 37:95, ack 247, win 265, options [nop,nop,TS val 515426 ecr 515426], length 58
E..n&.@.@...............oX..om.~...	.b.....
...b...bPassword accepted, welcome back Plague!
root@TheGibSon:~# 
21:58:15.176855 IP localhost.41699 > localhost.2011: Flags [R], seq 1869455486, win 0, length 0
E..(..@.@.<.............om.~....P....3..

So the first packet is a login prompt, and the last packet is a “valid login” message. The second packet is the interesting one, it appears to contain two strings (“GitS” and “Plague”) and some binary data.

Since it’s just a single packet we just use ‘tcpdump -x -r 7139a4ea239dcac655f7c38ca6a77b61.bin’ to dump the packet contents as hex and then paste it into python. If it was anything more complicated we’d have extracted the data using the excellent scapy module for manipulating pcap files.

We now have a string which looks like this:

>>> s
'GitS\x00Plague\x00\x08+.\x01\x17\x10\x01\x05\x01\x07W!W\x01\x01\x12\x01\x06M]\x1d\x08\r\x02\x05\x1b\n\x18\x02\x01\x04Z\x04F\x10\x05\x84\'\x16\x12\x03\x05\x9d"\x05\x01\x01\x04\xb8\t\x04\x01\x053]8\x05\x01\x04^\rh\x1f\x07P-\x1a \x02\t\x02\x06\x90\x0c \x10\x0f\x01\x04:\x04\x01\x01\x08\x17;4\x187\x0f\x01\x01\x04!x%\x08\x05\x1dK\x08\x03\x01\x04\x1a!\x02\x03\x05\x19%\x04\x01\x01\x05\\\x17\x12\x02\x01\x08]I3\x04\x03\x02\x01\x01\x04\x96\x1a)\x05\x03:\x05\x01\x069\x04S\n\x01\x01\x07y\x02\x07\x1b\x017\x01\x04\x03\x0e\x18\x17\x05n\x11\t\x03\x01\t\xb4\x06\x01\x03\x04\x03\x1e\x02\x01\x07\x02\xa7\x10\x10\x12\x13\x02\x07L\tC\x07\r\x04*\x04\rx_\x02\x04+\x07\r\x01\x05t\r\x0e\t\x02\x06-\xa6\r\x0b\x01\x06\x04\x9d9\x05\x01\x02\xd5\t\x068\x06\x02\x02\x01\x01\x04/\x05\x0b\x01'

Neither “GitS” nor “Plague” is the solution, so let’s ignore those for now and look at the rest of the data. It seems to be somehow regular, but let’s try to pin this down a bit more. Start by counting how often each byte occurs:

>>> s = s[12:]
>>> len(s)
233
>>> from collections import Counter
>>> h = Counter(s)
>>> len(h)
74
>>> h
Counter({'\x01': 36, '\x04': 20, '\x02': 16, '\x05': 16, '\x03': 9, '\x07': 8, '\x06': 8, '\t': 7, '\r': 7, '\x08': 6, '\x10': 5, '\x12': 4, '\x17': 4, '\x18': 3, '\x1a': 3, '!': 3, ']': 3, '\x0b': 2, '\n': 2, '\x0f': 2, '\x0e': 2, '\x1b': 2, '\x1d': 2, ' ': 2, '%': 2, '\x9d': 2, '+': 2, '-': 2, '3': 2, '7': 2, '9': 2, ':': 2, 'W': 2, '8': 2, 'x': 2, '\x0c': 1, '\x11': 1, '\x13': 1, '\x16': 1, '\x19': 1, '\x1f': 1, '\x84': 1, '"': 1, "'": 1, '\xa6': 1, ')': 1, '*': 1, '/': 1, '.': 1, '4': 1, '\xb8': 1, ';': 1, '\xb4': 1, '\x1e': 1, 'C': 1, '\x96': 1, 'F': 1, 'I': 1, 'K': 1, 'M': 1, 'L': 1, 'P': 1, 'S': 1, '\xd5': 1, 'Z': 1, '\\': 1, '_': 1, '^': 1, '\xa7': 1, '\x90': 1, 'h': 1, 'n': 1, 't': 1, 'y': 1})

So there’s only 74 unique values in this string of 233 bytes. That’s too few for random data or proper encryption, but probably too many for a naive substitution cipher or a single-char xor cipher. Although it *could* still be a substitution cipher, if they used all 26*2 upper/lowercase letters, all digits, and a bunch of symbols and punctuation. Let’s try that first. In this case, ‘\x01’ occurs most often so it is probably the space character.

>>> Counter(map(len, s.split("\x01")))
Counter({0: 9, 5: 6, 1: 3, 3: 3, 4: 3, 7: 2, 8: 2, 10: 2, 2: 1, 9: 1, 11: 1, 12: 1, 15: 1, 19: 1, 25: 1})

This is a histogram of word lengths if ‘\x01’ is indeed the space character. That doesn’t look right, there’s a bunch of 0-length words and too many very long ones.

Next we tried some tools for bruteforcing xor and substitution ciphers, and trying anything related to GitS, Plague and TelAviv as the key. Nothing worked, of course πŸ™‚

Finally someone noticed a pattern! The first byte is ‘\x08’. If you skip 8 bytes after that, you get byte value ‘7’. Skip 7 bytes after that, and you get a byte with value ‘6’. This pattern continues until you reach ‘4’, then it starts to bounce back and forth but always staying below 9. Also, if you do this you end up exactly at the end of the data, so there are no ‘leftover’ bytes.

This was too nice to be a coincidence. Supposing that this was some sort of packet-based format where each block is prefixed by a byte specifying the length of the block, we wrote a quick parser:

i = 0
while i < len(s):
	l = ord(s[i])
	i += 1
	t = s[i:i+l]
	i += l
	print ' '.join("%02x" % ord(c) for c in t)

This gives the following output:

2b 2e 01 17 10 01 05 01
57 21 57 01 01 12 01
4d 5d 1d 08 0d 02
1b 0a 18 02 01
5a 04 46 10
84 27 16 12 03
9d 22 05 01 01
b8 09 04 01
33 5d 38 05 01
5e 0d 68 1f
50 2d 1a 20 02 09 02
90 0c 20 10 0f 01
3a 04 01 01
17 3b 34 18 37 0f 01 01
21 78 25 08
1d 4b 08 03 01
1a 21 02 03
19 25 04 01 01
5c 17 12 02 01
5d 49 33 04 03 02 01 01
96 1a 29 05
3a 05 01
39 04 53 0a 01 01
79 02 07 1b 01 37 01
03 0e 18 17
6e 11 09 03 01
b4 06 01 03 04 03 1e 02 01
02 a7 10 10 12 13 02
4c 09 43 07 0d 04 2a
0d 78 5f 02
2b 07 0d 01
74 0d 0e 09 02
2d a6 0d 0b 01 06
9d 39 05 01
d5 09
38 06 02 02 01 01
2f 05 0b 01

This looks very interesting, and we can already see some new patterns here. To start with, the first bytes of these packets are usually pretty high, and the last bytes are often ‘\x01’ or even ‘\x01\x01’. Still, there’s no obvious way to split these packets up futher or decode them.

Playing around with these for a while yielded the second breakthrough. When you print the sums of the bytes in each packet, you get this:

i = 0
while i < len(s):
	l = ord(s[i])
	i += 1
	t = s[i:i+l]
	i += l
	print sum(map(ord, t))
136
228
222
64
180
214
198
198
206
242
196
220
64
230
198
116
64
68
136
228
222
64
156
214
64
140
230
240
218
230
64
154
242
220
222
68
64

First of all, there are a lot of identical values. Also, all values are in the range 64-242. Maybe this is some kind of substitution cipher?

But wait, all values appear to be even! And 64 is exactly 2 times 32, which is the ascii value for space. Maybe we just need to divide everything by 2?

i = 0
tmp = ''
while i < len(s):
	l = ord(s[i])
	i += 1
	t = s[i:i+l]
	i += l
	tmp += chr(sum(map(ord, t)) >> 1)
print tmp

This gives the output ‘Dro Zkccgybn sc: “Dro Nk Fsxms Myno” ‘. Looking good! At a glance, ‘Dro Zkccgybn sc: “…”‘ is probably some sort of simple encrytion of ‘The Password is: “…”‘.

Looks like it is shifted by 16 characters. Now we have the solution:

s = '4769745300506c6167756500082b2e0117100105010757215701011201064d5d1d080d02051b0a180201045a044610058427161203059d2205010104b809040105335d380501045e0d681f07502d1a2002090206900c20100f01043a04010108173b3418370f01010421782508051d4b080301041a210203051925040101055c17120201085d4933040302010104961a2905033a0501063904530a0101077902071b01370104030e1817056e1109030109b406010304031e02010702a71010121302074c0943070d042a040d785f02042b070d0105740d0e0902062da60d0b0106049d39050102d50906380602020101042f050b01'
s = b.decode('hex')
s = b[12:]

i = 0
tmp = ""
while i < len(d):
	l = ord(d[i])
	i += 1
	t = d[i:i+l]
	i += l
	#print ' '.join("%02x" % ord(c) for c in t)
	tmp += chr(sum(map(ord,t)) >> 1)
	

abc = "abcdefghijklmnopqrstuvwxyz"
ABC = abc.upper()

t = ""
for c in tmp:
	if c in abc:
		c = abc[(abc.index(c) + 16) % 26]
	elif c in ABC:
		c = ABC[(ABC.index(c) + 16) % 26]
	t += c

print t

‘The Password is: “The Da Vinci Code”‘

But what does the challenge name mean? After reading some other writeups it turns out TLV is an acronym for “Type Length Value”, which is a hint about the encoding. And of course ‘+’ refers to the summing of the packet bytes. Guess we should have googled a bit harder!

Comments are closed.