BKP2016 Unholy and Ashmont writeup

unholy

It was a reverse challenge two files are given main.rb and unholy.so

#!/usr/bin/env ruby
require_relative 'unholy'  
include UnHoly  
python_hi  
puts ruby_hi  
puts "Programming Skills: PRIMARILY RUBY AND PYTHON BUT I CAN USE ANY TYPE OF GEM TO CONTROL ANY TYPE OF SNAKE"  
puts "give me your flag"  
flag = gets.chomp!  
arr = flag.unpack("V*")  
is_key_correct? arr  

So we need to reverse is_key_correct from unholy.so. The function method_check_key located at 0xB61 is the one that checks the input.

The function expect a 9 integer inputs it then goes into a loop doing some crypto stuff that I don't recognize, and at the end it does this.

   if ( mat[9] == 0x4DE3F9FD )
    {
      __sprintf_chk(
        stacker,
        1LL,
        5000LL,
        "exec \"\"\"\\nimport struct\\ne=range\\nI=len\\nimport sys\\nF=sys.exit\\nX=[[%d,%d,%d],[%d,%d,%d],[%d,%d,%d]]\\"
        "nY = [[383212,38297,8201833],[382494 ,348234985,3492834886],[3842947 ,984328,38423942839]]\\nn=[5034563854941868"
        ",252734795015555591,55088063485350767967,-2770438152229037,142904135684288795,-33469734302639376803,-36335073107"
        "95117,195138776204250759,-34639402662163370450]\\ny=[[0,0,0],[0,0,0],[0,0,0]]\\nA=[0,0,0,0,0,0,0,0,0]\\nfor i in"
        " e(I(X)):\\n for j in e(I(Y[0])):\\n  for k in e(I(Y)):\\n   y[i][j]+=X[i][k]*Y[k][j]\\nc=0\\nfor r in y:\\n for"
        " x in r:\\n  if x!=n[c]:\\n   print \"dang...\"\\n   F(47)\\n  c=c+1\\nprint \":)\"\\n\"\"\"",
        mat[0],
        mat[1],...,mat[8]);
      Py_Initialize(stacker, 1LL);
      PyRun_SimpleStringFlags(stacker, 0LL);
      Py_Finalize(stacker, 0LL);
    }

It's calling the python script simplified below

import struct  
import sys

X = ....  
Y = [[383212,38297,8201833],[382494 ,348234985,3492834886],[3842947 ,984328,38423942839]]  
n=[5034563854941868,252734795015555591,55088063485350767967,-2770438152229037,142904135684288795,-33469734302639376803,-3633507310795117,195138776204250759,-34639402662163370450]  
y=[[0,0,0],[0,0,0],[0,0,0]]  
A=[0,0,0,0,0,0,0,0,0]  
for i in range(len(X)):  
 for j in range(len(Y[0])):
  for k in range(len(Y)):
   y[i][j]+=X[i][k]*Y[k][j]
c=0  
for r in y:  
    for x in r:
      if x!=n[c]:
          print x
          print n[0]
          print "dang..."
          sys.exit(47)
      c=c+1
print ":) "  

The X matrix is our input it goes through the matrix swapping and summation below and checking if y matrix's elements are similar to those in n array.

I use z3 to solve the constrains and find such input that will result in this comparison success.

We start building the constrains. We first define our knowns and unknowns

    x_matrix  = [[z3.BitVec("xm%d%d" % (x,y), bits) for y in range(3)] for x in range(0,3)]                                                                                        
    ys_matrix = [[z3.BitVec("ysm%d%d" % (x,y), bits) for y in range(3)] for x in range(0,3)]                                                                                       
    _y = [[383212,38297,8201833],[382494 ,348234985,3492834886],[3842947 ,984328,38423942839]]                                                                                     
    _n = [5034563854941868,252734795015555591,55088063485350767967,-2770438152229037,142904135684288795,-33469734302639376803,-3633507310795117,195138776204250759,-346394026621633
70450]  

Then we convert the summation and swapping loop into a constrain as follows

    s.add(ys_matrix[0][0]==(x_matrix[0][0]*_y[0][0])+(x_matrix[0][1]*_y[1][0])+(x_matrix[0][2]*_y[2][0]))                                                                          
    s.add(ys_matrix[0][1]==(x_matrix[0][0]*_y[0][1])+(x_matrix[0][1]*_y[1][1])+(x_matrix[0][2]*_y[2][1]))                                                                          
    s.add(ys_matrix[0][2]==(x_matrix[0][0]*_y[0][2])+(x_matrix[0][1]*_y[1][2])+(x_matrix[0][2]*_y[2][2]))                                                                          
    s.add(ys_matrix[1][0]==(x_matrix[1][0]*_y[0][0])+(x_matrix[1][1]*_y[1][0])+(x_matrix[1][2]*_y[2][0]))                                                                          
    s.add(ys_matrix[1][1]==(x_matrix[1][0]*_y[0][1])+(x_matrix[1][1]*_y[1][1])+(x_matrix[1][2]*_y[2][1]))                                                                          
    s.add(ys_matrix[1][2]==(x_matrix[1][0]*_y[0][2])+(x_matrix[1][1]*_y[1][2])+(x_matrix[1][2]*_y[2][2]))                                                                          
    s.add(ys_matrix[2][0]==(x_matrix[2][0]*_y[0][0])+(x_matrix[2][1]*_y[1][0])+(x_matrix[2][2]*_y[2][0]))                                                                          
    s.add(ys_matrix[2][1]==(x_matrix[2][0]*_y[0][1])+(x_matrix[2][1]*_y[1][1])+(x_matrix[2][2]*_y[2][1]))                                                                          
    s.add(ys_matrix[2][2]==(x_matrix[2][0]*_y[0][2])+(x_matrix[2][1]*_y[1][2])+(x_matrix[2][2]*_y[2][2]))                                                                          

and finally define the equality part in the final loop

    s.add (ys_matrix[0][0] == _n[0])                                                                                                                                               
    s.add (ys_matrix[0][1] == _n[1])                                                                                                                                               
    s.add (ys_matrix[0][2] == _n[2])                                                                                                                                               
    s.add (ys_matrix[1][0] == _n[3])                                                                                                                                               
    s.add (ys_matrix[1][1] == _n[4])                                                                                                                                               
    s.add (ys_matrix[1][2] == _n[5])                                                                                                                                               
    s.add (ys_matrix[2][0] == _n[6])                                                                                                                                               
    s.add (ys_matrix[2][1] == _n[7])                                                                                                                                               
    s.add (ys_matrix[2][2] == _n[8])

and we solve it, giving us the result of X

Using : 64 bits  
[xm20 = 18446744073218584611,
 xm10 = 1473172750,
 xm21 = 563111828,
 xm01 = 722035088,
 xm02 = 1368334760,
 xm22 = 18446744072756962429,
 xm12 = 18446744072800650391,
 xm11 = 412774077,
 xm00 = 18446744072404665039,
 ysm22 = 2254085485255732782,
 ysm21 = 195138776204250759,
 ysm20 = 18443110566398756499,
 ysm12 = 3423753844779726429,
 ysm11 = 142904135684288795,
 ysm10 = 18443973635557322579,
 ysm02 = 18194575337931664735,
 ysm01 = 252734795015555591,
 ysm00 = 5034563854941868]
X = [[-1304886577, 722035088, 1368334760], [1473172750, 412774077, -908901225], [-490967005, 563111828, -952589187]]  

X values are casted to c_int. Checking in the original python script

import struct  
import sys  
import ctypes  
X = [[18446744072404665039L, 722035088, 1368334760], [1473172750, 412774077, 18446744072800650391L], [18446744073218584611L, 563111828, 18446744072756962429L]]  
X = [[ctypes.c_int(y&0xffffffff).value for y in x] for x in X]  
Y = [[383212,38297,8201833],[382494 ,348234985,3492834886],[3842947 ,984328,38423942839]]  
n=[5034563854941868,252734795015555591,55088063485350767967,-2770438152229037,142904135684288795,-33469734302639376803,-3633507310795117,195138776204250759,-34639402662163370450]  
y=[[0,0,0],[0,0,0],[0,0,0]]  
A=[0,0,0,0,0,0,0,0,0]  
for i in range(len(X)):  
 for j in range(len(Y[0])):
  for k in range(len(Y)):
   y[i][j]+=X[i][k]*Y[k][j]
c=0  
for r in y:  
    for x in r:
      if x!=n[c]:
          print x
          print n[0]
          print "dang..."
          sys.exit(47)
      c=c+1
print ":) "  

and we get the smiley face :), anyway at this point we have half the solution we need to decrypt the matrix X to get the input used to generate it. I couldn't recognize the crypto used at the beginning of method_check_key nor be able to inverse it, but a friend of mine solarwind recognized that it is an XTEA block cipher and wrote a quick decryptor and decrypted X using the key mentioned there.

#!/usr/bin/python
from struct import *

mat = [-1304886577, 722035088, 1368334760, 1473172750, 412774077, -908901225, -490967005, 563111828, -952589187, 1306786301]  
k = [1952540791, 1768908659, 1852794734, 1701995880]  
def dec(v0, v1):  
    delta,mask = 0x9e3779b9L,0xffffffffL
    n = 32
    sum = (delta * n) & mask
    for round in range(n):
        v1 = (v1 - (((v0<<4 ^ v0>>5) + v0) ^ (sum + k[sum>>11 & 3]))) & mask
        sum = (sum - delta) & mask
        v0 = (v0 - (((v1<<4 ^ v1>>5) + v1) ^ (sum + k[sum & 3]))) & mask
    return v0, v1

res = ""  
for i in xrange(0, 10, 2):  
    v0, v1 = mat[i], mat[i+1]
    v0 = (2**32 + v0) % 2**32
    v1 = (2**32 + v1) % 2**32
    v0,v1 = dec(v0, v1)
    res += pack("<II", v0, v1)
print res  

giving us BKPCTF{hmmm _why did i even do this}

Ashmont

Another RE challenge was a pain to reverse statically. After some minutes I decided to take another approach by going for a side-channel attack.

I started counting instructions (using pintool) and it seemed to be randomly increasing and decreasing between tests, a quick trace shows that gettimeofday is executing different times between tries, so since this is a dynamic binary I do the LD_PRELOAD and control this function and set tp and tzp values, so we avoid this anti-side-channel attack :)

struct timeval {  
    long int tv_sec;
    long int tv_usec;
};

int gettimeofday(struct timeval *restrict tp, void *restrict tzp) {  
    tp->tv_sec = 0;
    tp->tv_usec = 0;
    return 0;
}

and the script to do the instruction counting (exportPIN_APP_LD_PRELOAD=env)

#!/usr/bin/env python2

import os  
import string  
import operator  
import sys

charset = string.ascii_letters + string.digits + "_#{}"

def main():

    res = {}
    for c in charset:
        flag = sys.argv[1]+c
        cmd = "./pin -ifeellucky -t inscount.so -- ./c3803116bd70e802483d3bc4c4b564d2 '%s'" % flag
        os.system(cmd)
        fd = open("inscount.out", "r")
        count = int(fd.read().split(" ")[1])
        fd.close()
        res[c] = count
        print '[+] count %s : %d' % (flag, count)
    print "Results : "
    for k in sorted(res.items(), key=operator.itemgetter(1)):
        print k

if __name__ == "__main__":  
    main()

run and get the flag a step at a time BKPCTF{S1de_Ch4nnel_att4cks_are_s0_1338}

}}