TUMCTF Teaser 2015: T9

This was a fun little misc. problem dealing with a T9 cipher. It didn’t require much to solve, just a quick read over the T9 Cipher and some way to parse a long text file. I probably did a little too much work by solving it with a whole python script when grep would have worked just fine, but here is my work anyway.

The challenge was given as follows:

352404707644669372663764444477927397646952284349399866786464374767564472 ?

ctf.link/assets/downloads/misc/words.txt

NOT the default flag format! Do not add hxp{ }.

The T9 Scheme

T9 wasn’t designed as a cipher, but as a predictive text mode for 9-key phones. The idea is simple, instead of making a user repeatedly press a key on a phone to select a letter, they just press the key once and then based on a dictionary the desired letter/word is predicted.

The keypad design:

(Source: Sakurambo (Created using Adobe Illustrator CS2) [Public domain], via Wikimedia Commons)

So if a user wanted to type ABC instead of typing 222222 they could just enter 222. It’s important to note that 1 and 0 can be only spaces or a symbol of punctuation.

Deciphering the Text

Recovering what the message is exclusively from the numbers pressed gets a little tricky because the longer the message the larger the keyspace. The first two words are short so lets just start with those:

3524 and 47

We can run through the possibilities for these pretty easily and get that they are flag and is respectively. If we check the provided words.txt file we can see that it starts with these two words as well:

flag
is
T9D7o534ASykDJNlwsK6MWEWLsmOfDZz6SPzsycpN795ZCYm9J2QYARPNJPszT9n LWxSXkxQoSXygw8OURnJOXi1iGkwLmLzrBsXskGJQrfy3zvRLGpuuoHEUSBKJjrd c1fKYkHt5jjj3BiLgBF7XYCU9GmXI6zSaCFjhrlGRDn0AcUMz1PRrs5kDGUc5PUP CcSQiPsIxFQSn8IUDbhujaTQ01bIjf7pzM65HqmD7KdQnQSXf15PdvKMm5cTLybh hUAvkyloeLRtr4XceO1qClCz7KZ4RolNfT5eN2poTJOVaoANIdkDnhAXxJe6nENr WKPNNFTP6ulSNwK886BeJACMEKFp35VQlw74CP5n51VFSZSHJKxUjfObIRPdHlxG HCkJGrxtelrm5upocU72ORxNsfeNVxZ0YjVteRPn4tHTVpxKUzI1AO9aDJ7AYirN 6sNI6G68sRAamc7djw1BpnbYivw72gGco8F7hB9sdxG4KLAcyVk7oOHkDhNC7LOt
…

This means that all we have left to decipher is 7644669372663764444477927397646952284349399866786464374767564472. Based on the first two words translated we can assume that the words.txt is a short-list of all possible words that our text could be. This hypothesis is supported by the fact that the remaining part of our flag is 64 characters, and each of the remaining million lines in the words.txt file is 64 chars in length.

Scripting the Solution

All that’s left to do is encode every remaining line of the words.txt file to T9 and print out the line that encodes to 7644669372663764444477927397646952284349399866786464374767564472.

Doing this in python:

def map(a):
	if a in 'abc2':
		return 2
	if a in 'def3':
		return 3
	if a in 'ghi4':
		return 4
	if a in 'jkl5':
		return 5
	if a in 'mno6':
		return 6
	if a in 'pqrs7':
		return 7
	if a in 'tuv8':
		return 8
	if a in 'wxyz9':
		return 9
	if a in '0':
		return 0
	return 1

answer = ''
with open('words.txt') as f:
	for line in f:
		for i in line[:-1]:
			answer += str(map(i.lower()))
		if answer == '7644669372663764444477927397646952284349399866786464374767564472':
			print line
			break
		answer = ''

Running this provides the flag:

7o4hoMXFRCNofPMiH4iIrpwBpfzrMgny5cBUieiWEwWUNoPVNHNherHSNsJOg4qB