This challenge involves three languages: Ruby, Python, and x86-64 assembly. They are combined by some kind of native extension mechanism, but we don’t have to understand the details of the mechanism nor master these languages to solve the problem. Just make the best guess and verify it. First, have a look at the main program.
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
The methods used in main.rb can be found in unholy.so. Here is the piece of code that register the Ruby module and methods.
The main program want us to enter the flag, and then it will unpack the input string into integer array and pass it to the method is_key_correct?. According to Init_unholy above, we should look into method_check_key now. method_check_key can be divided into three parts.
I have spent some time investigating why it check whether the first byte of the payload is 0x20, what rb_ary_entry, rb_fix2int, and rb_num2int do, and so on. However, they are quite irrelevant. They are all about the memory representation of Ruby’s data structure (e.g. the first byte of the payload is the length of the Ruby’s array). Using gdb, we can directly find out what Part1 does is putting our input (in integer array format) into matrix and initialize some other data.
In Part2, it applys some operations on matrix (our input) and key (known data) two entries at a time. It look messy at the first glance, but the operations can actually be inverted. Values derived from v8 are constant, so we know that the inner loop will iterate 32 times and the operation can be simplify as
Part2
1 2 3
for i in range(32): v9 = (C ^ (16*v10 ^ (v10 >> 5)) + v10) + v9 v10 = (C ^ (16*v9 ^ (v9 >> 5)) + v9) + v10
where C stands for known constant. We can calculate v10 of the previous loop by current v10 and v9, and then we can use previous v10 and current v9 to calculate previous v9. Following this process, we can get the initial v9 and v10.
Part3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
... if ( matrix[9] == 1306786301 ) { __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,-3633507310795117,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\"\"\"", matrix[0], matrix[1]); Py_Initialize(stacker, 1LL); PyRun_SimpleStringFlags(stacker, 0LL); Py_Finalize(stacker, 0LL); } }
The parameters of sprintf is incorrect in the decompiled code, but it suggests that Part3 prints the values in matrix into following Python code and execute it.
&0xffffffff which scatters in the script is to simulate integer overflow.
Flag: BKPCTF{hmmm _why did i even do this}
Note
It seems that Python doesn’t provide a handy way to compute integer with overflow.
I try to solve Part2 by Z3 at the beginning, but it hang forever. Sometimes we should just settle down to read the code and get our hands dirty. Don’t depend on tools too much.
I debug by gdb --args ruby main.rb, but it is hard to set breakpoints in a shared library. Maybe there is a better way to debug.
According to other people’s writeup, the Part2 is actually doing XTEA cipher. The clue is lots of xor and shift operations which implie it is performing some kind of cipher. By googling the constant 0xc6ef3720, we can find out that the answer is XTEA.