BinaryStudio

HackTheVote 2016: Vermatrix Supreme Writeup

I picked this challenge to work on first since it was the lowest point crypto challenge, which also just happened to be written in Python. The challenge had the following flavor text:

Working in IT for a campaign is rough; especially when your candidate uses his password as the IV for
your campaign's proprietary encryption scheme, then subsequently forgets it. See if you can get it 
back for him. The only hard part is, he changes it whenever he feels like it.

nc vermatrix.pwn.democrat 4201

handout

author's irc nick: negasora

The handout link provided the source to a python2 program, which presumably was the source of the challenge running on the remote server:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

import sys, random, time

flag = "flag{1_sw34r_1F_p30Pl3_4cTu4lLy_TrY_Th1s}"

def printmat(matrix):
    for row in matrix:
        for value in row:
            print value,
        print ""
    print ""


def pad(s):
    if len(s)%9 == 0:
        return s
    for i in xrange((9-(len(s)%9))):
        s.append(0)
    return s

def genBlockMatrix(s):
    outm = [[[7 for x in xrange(3)] for x in xrange(3)] for x in xrange(len(s)/9)]
    for matnum in xrange(0,len(s)/9):
        for y in xrange(0,3):
            for x in xrange(0,3):
                outm[matnum][y][x] = s[(matnum*9)+x+(y*3)]
    return outm


def fixmatrix(matrixa, matrixb):
    out = [[0 for x in xrange(3)] for x in xrange(3)]   
    for rn in xrange(3):
        for cn in xrange(3):
            out[cn][rn] = (int(matrixa[rn][cn])|int(matrixb[cn][rn]))\
            &~(int(matrixa[rn][cn])&int(matrixb[cn][rn]))
    return out


def chall():
    IV = [c for c in '?????????']
    seed = "??????????????????"


    blocks = genBlockMatrix(pad(IV + [ord(c) for c in seed]))

    res = [[0 for i in xrange(3)] for i in xrange(3)]
    for i in xrange(len(blocks)):
        res = fixmatrix(res, blocks[i])


    print "SEED: " + str(seed)
    printmat(res)

    data = raw_input("")

    data = data.replace(' ', '').strip().split(',')

    if len(data) != 9:
        return False

    for i in xrange(len(IV)):
        if str(IV[i]) != str(data[i]):
            return False

    return True


if chall():
    print flag

Looking over the source, it appeared the flag was stored in the first variable flag, and would only display if the chall() function returned true. Since the script didn't import socket I could only assume all I/O would be handled via STDIN and STDOUT, probably through netcat.

At this point, I wanted to know what the output looked like, so ran ncat vermatrix.pwn.democrat 4201, which gave the output:

SEED: %bIdKOc'I
997 678 527
827 773 1161
1025 836 562

Connecting a second time gave the output:

SEED: (v=]UPNh?
1339 617 777
1055 770 465
677 1021 609

And running the program locally with python2 handout.4838bbdb8619b3a581352c628c6b0b86475b94c9519347a520c90cf1822351ae.py gave the error:

Traceback (most recent call last):
  File "handout.4838bbdb8619b3a581352c628c6b0b86475b94c9519347a520c90cf1822351ae.py", line 66, in <module>
    if chall():
  File "handout.4838bbdb8619b3a581352c628c6b0b86475b94c9519347a520c90cf1822351ae.py", line 46, in chall
    res = fixmatrix(res, blocks[i])
  File "handout.4838bbdb8619b3a581352c628c6b0b86475b94c9519347a520c90cf1822351ae.py", line 33, in fixmatrix
    out[cn][rn] = (int(matrixa[rn][cn])|int(matrixb[cn][rn]))&~(int(matrixa[rn][cn])&int(matrixb[cn][rn]))
ValueError: invalid literal for int() with base 10: '?'

With this error it's obvious to see that the values provided in the script on lines 39 and 40 are the ones that are likely to be randomized with each connect to the remote version of the script. It is here that the meat of the challenge becomes apparent.

First Steps

We can see by looking at the chall() function's lines 58 and 62 two strict conditions for the program to be able to print the flag for us:

if len(data) != 9:
    return False

for i in xrange(len(IV)):
    if str(IV[i]) != str(data[i]):
        return False

where data is read in via raw_input(""). This indicates is that whatever data is sent in must be exactly 9 elements long, and, according to the code on line 55, must be comma delimited:

data = data.replace(' ', '').strip().split(',')

Additionally, we know from the source and output that the value of SEED is simply printed out, and is also 9 characters long, so we'll go ahead and fill those in on the local copy of the script:

IV = [c for c in '012345678']
seed = "HERPDERPP"

Running the local script again:

-> % python2 handout.py
SEED: HERPDERPP
72 70 84 
81 64 66 
80 85 8 

we see it is awaiting our raw_input(), and after supplying the IV in comma-delimited form:

0,1,2,3,4,5,6,7,8

we verify that the flag is output:

flag{1_sw34r_1F_p30Pl3_4cTu4lLy_TrY_Th1s}

The Challenge

Now the question is, how do we work backwards from what we're given (SEED and a 3x3 matrix of numbers) to get to the appropriate IV? Well, since we know the Matrix gets printed out, lets see what goes into making it.

We see that the printmat(matrix) function iterates over a nested iterable (probably a list) and prints each value in the row before printing a newline, meaning from our output before that matrix probably looks something like [[72, 70, 84], [81, 64, 66], [80, 85, 8]]. The only time printmat() gets called is on line 51 with res as the argument.

So now we must look at how res is constructed. On line 45, res is initialized to a list of three lists all with the value of 0:

res = [[0 for i in xrange(3)] for i in xrange(3)]

If you've never worked with list comprehensions then this line might look weird, however it's equivalent to writing:

res = []
for i in xrange(3):
    tmp = []
    for j in xrange(3):
        tmp.append(0)
    res.append(tmp)

which results in res holding [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

The next two lines show that a function fixmatrix(matrixa, matrixb) is run on res, outputing its result to res, but also making use of another variable, blocks.

blocks

blocks is generated on line 43 with:

blocks = genBlockMatrix(pad(IV + [ord(c) for c in seed]))

Here we've got another nested list comprehension statement within a double function call. I forgot to mention that this is also how IV is generated on line 39:

IV = [c for c in '012345678']

which produces ['0', '1', '2', '3', '4', '5', '6', '7', '8'].

[ord(c) for c in seed] generates the list [72, 69, 82, 80, 68, 69, 82, 80, 80], and using the + operator simply concatenates both lists into a single list:

['0', '1', '2', '3', '4', '5', '6', '7', '8', 72, 69, 82, 80, 68, 69, 82, 80, 80] which is 18 elements long.

When we look at the pad() function, we see that its main function is to ensure that the len() of the list supplied to the function is divisible by 9, which 18 already is. If it weren't, then 0's would simply be appended to the list until its length was divisible by 9:

def pad(s):
    if len(s)%9 == 0:
        return s
    for i in xrange((9-(len(s)%9))):
        s.append(0)
    return s

The last function call of this line (#43) is to genBlockMatrix().

genBlockMatrix()

This function starts off initializing a 3-dimensional array filled with 7's by using a list comprehension:

outm = [[[7 for x in xrange(3)] for x in xrange(3)] for x in xrange(len(s)/9)]

where the x and y dimensions are of magnitude 3, and the z dimension is of magnitude len(s)/9, which comes out to 2 when len(s) == 18. Therefore the matrix's "signature" is outm[z][y][x] == outm[2][3][3].

If you're having a hard time visualizing this, this is what it looks like:

[[[7, 7, 7], [7, 7, 7], [7, 7, 7]], [[7, 7, 7], [7, 7, 7], [7, 7, 7]]]

Alternatively:

[[ [7, 7, 7], 
   [7, 7, 7], 
   [7, 7, 7] ],

 [ [7, 7, 7], 
   [7, 7, 7], 
   [7, 7, 7] ]]

The next 4 lines (22-25) simply read in the supplied list (s) into the matrix, left-to-right, top-to-bottom, front-to-back. The result:

[[['0', '1', '2'], ['3', '4', '5'], ['6', '7', '8']], [[72, 69, 82], [80, 68, 69], [82, 80, 80]]]

Now that we have the value for blocks (and res) we can dive into the final method of the program, fixmatrix(matrixa, matrixb)

fixmatrix()

blocks = genBlockMatrix(pad(IV + [ord(c) for c in seed]))

res = [[0 for i in xrange(3)] for i in xrange(3)]
for i in xrange(len(blocks)):
    res = fixmatrix(res, blocks[i])

As we can see in the code, fixmatrix() is run a number of times equal to the len(blocks), which in our case is 2. Also to note, each time fixmatrix runs, the output is reassigned to res, and in the invocation, only blocks's index is incremented.

Now, for the meat of the function:

def fixmatrix(matrixa, matrixb):
    out = [[0 for x in xrange(3)] for x in xrange(3)]   
    for rn in xrange(3):
        for cn in xrange(3):
            out[cn][rn] = (int(matrixa[rn][cn])|int(matrixb[cn][rn]))\
            &~(int(matrixa[rn][cn])&int(matrixb[cn][rn]))
    return out

Here we can see that res is matrixa, and blocks[i] is matrixb. On the first line, a 3x3 matrix out is initialized with all 0's. Next is a double for loop which iterates over all 9 elements in the out matrix. The entirety of the transformation is done on the assignment line, out[cn][rn] =....

Keeping in mind that cn refers to column number and rn refers to row number, then each element of the out matrix is being set to the bitwise expression on the same line. Removing the unnecessary visual fluff from the expression yields:

(matrixa | matrixb) &~ (matrixa & matrixb), or in logical notation: \((A \lor B) \land \lnot (A \land B)\)

If you haven't already, you should recognize this expression as XOR or exclusive-or, which can also be written as \(A \oplus B\). I've included below a truth table so that you can see how A and B are related.

An important property of XOR is that when you XOR any data with 0, you simply get the supplied data as your result. For example, \(752875 \oplus 0 == 752875\). Now, back to the challenge, something important I have left out so far is that on the out[cn][rn] = ... assignment, you'll notice that the [cn][rn] are swapped for both out and matrixb. This means that both of these matrices are transposed. BUT, since out is being assigned to (and it's transposition matches matrixb's) then it's really as if matrixa is the one that is transposed.

Taking all this information into account, since the first run of fixmatrix is done with matrixa == res, and res being initialized 0's, and matrixb == blocks[0] == IV, we have:

A second run of fixmatrix has the previous result of res == IV assigned to matrixa, with matrixb set to seed:

Which means that the final value of res, which is printed out on line 51 with printmat(res) is simply the XOR of the seed string with the (transposed) values of IV!

One of the greatest properties of XOR is that if \(C = A \oplus B\), then \(C \oplus B = A\) (and \(C \oplus A = B\)). This means that if we simply XOR the values from the (transposed) output of printmatrix(res) with the ordinal values of the printed seed, we'll recover the IV.

The Solution

Here is my hacked-together solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#!/usr/bin/env python3
import sys
import socket
import re
from codecs import decode

#Regex Pattern to capture seed string
seedPat = re.compile(r'^SEED:\s(.+)$')

#Create our Socket object and connect to the challenge server
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('vermatrix.pwn.democrat', 4201))

#Receive the challenge data
data = b''
data += s.recv(128)
#Turn bytes into strings
data = data.decode('utf8')
#create a list
rows = data.split('\n')

#print formatted data
print(data)
#print list
print(rows)
#remove empty list element
del(rows[4])

#perform a regex match agains the seed string
#could also use rows[0][6:]
seedMatch = seedPat.match(rows[0]).groups(1)[0]

#construct our 'res' matrix
matrix = rows[1] + ' ' + rows[2] + ' ' + rows[3]
matrix = [int(x) for x in matrix.split(' ')]

#verify captured data
print(seedMatch)
print(matrix)

#if the seed is short (9 chars)
if len(seedMatch) == 9:
    #perform XOR of res and seed values:
    g = [x[0] ^ ord(x[1]) for x in zip(matrix,seedMatch)]

#otherwise seed is 18 chars
else:
    #use last half of seed first
    g = [x[0] ^ ord(x[1]) for x in zip(matrix,seedMatch[9:18])]
    #transpose intermediate result
    tmp = [g[0],g[3],g[6],g[1],g[4],g[7],g[2],g[5],g[8]]
    #then XOR tmp value with first half of seed
    g = [x[0] ^ ord(x[1]) for x in zip(tmp,seedMatch[0:9])]

print("G: {}".format(g))

#store transposed result
z = "{},{},{},{},{},{},{},{},{}\n".format(g[0],g[3],g[6],g[1],g[4],g[7],g[2],g[5],g[8])
#convert string to bytes
z = bytes(z,'ascii')

#verify bytestring about to be sent 
print("Calculated IV: {}".format(z))

#send response to server
s.sendall(z)

#receive flag
data = b''
data += s.recv(128)
data = data.decode('utf8')
rows = data.split('\n')

#print flag
print(data)

Something I didn't find out until after I coded up a quick solution is that the challenge server usually spit out seeds that were 18 characters in length instead of 9 like I had witnessed my first few times running the challenge. In these cases, this solution I had written failed since I didn't take into account the second half of the seed. After retrieving the flag by spamming my solution until I got a seed of 9, I modified it to accept seeds of length 18.

You'll see the extra step that is needed starting on line 47 (with the else statement) is that the last half of the seed must be used first, followed by transposing the intermediate solution, before XORing this with the first half of the seed.

In both cases the result matrix g has to be transposed a final time before returning the value to the server. What is interesting to note is that this form of encryption is extremely similar to CBC mode of AES, minus the matrix transposition. Read up on this here.

And finally, running the script:

-> % ./solver.py
SEED: S;edzS'IeF"MA_^:Lg
924 1224 798
926 410 845
801 521 1084

['SEED: S;edzS\'IeF"MA_^:Lg', '924 1224 798', '926 410 845', '801 521 1084', '']
S;edzS'IeF"MA_^:Lg
[924, 1224, 798, 926, 410, 845, 801, 521, 1084]
G: [905, 996, 894, 1166, 447, 534, 884, 858, 1086]
Calculated IV: b'905,1166,884,996,447,858,894,534,1086\n'
flag{IV_wh4t_y0u_DiD_Th3r3}