The challenge is an HTML file called index.html, which contains obfuscated and minified Javascript. When browsing the page we receive 34 prompts and after trying to enter some different strings they all lead to the same skull unicode character being displayed to the user.
After passing it to a beautifier we see the script is composed of several components. All variable and function names are different capitalization permutations of the word “yield”. In some of the screenshots the variables were renamed for clarity. The script parts:
4 consts which equal this, 0, 1 and 2 respectively
A dictionary yiElD which has keys again with different yield permutations, with values that are Javascript keywords / functions / property names like “function”, “forEach” etc.
An array which will be used as a stack for passing parameters, described later.
A generator yiELd which:
Receives a function and number of arguments for that function
Pops the arguments for the received function (number is known from second argument) by pushing the return value of yield statement into a local array.
Calls the received function object with the expanded argument list received via … operator.
Returns the return value from the called received function via yield if it is non-void.
So essentially a relayer from yield-based parameter passing to traditional parameter passing.
A dictionary containing 17 generators and 4 lambdas. The lambdas are four Javascript functions: String.fromCodePoint, codePointAt, prompt and alert, each passed to the yield relayer at 4 with the respective number of arguments it receives. The rest of the functions receive variables via yield statements and perform different actions such as bitwise or, subtraction, shifting and so on, then output their return value via yield.
An array with about 2800 elements, which are either one of the yield functions from above or constants.
Call forEach on the array which does the follows:
If the element is a function, call it (it will be a generator function) and call next() on it to reach the first yield
as long as the generator is not done and there no return value, call next() on the generator with an argument popped from the top of the stack.
While generator is not done and the next() return value is defined, push the value on the stack.
If the element is not a function, just push it on the stack
Below is the de-obfuscated forEach:
To summarize what the script is doing, it implements a stack machine which runs a series of instructions. DATA instructions store an element on the stack, FUNCTION instructions are called and passed parameters from the stack via next() and the return values are stored on the stack. Our goal is to find the logic implemented by the specific instruction array and probably make it output a different message than a skull.
The instruction array has several stages, below is the pseudo-code:
TUPLES =
[[-95, 31, 58, -19, -87, -51, 71, 72, -9, 79, 33, -35, -21, 42, 13, -70, -5309],[64, 100, -27, 66, 22, 68, -21, -2, 26, 74, 48, 93, 68, -79, 69, 92, 63804],[49, 56, -75, 16, -79, 21, -5, 27, -7, 27, 50, -3, 13, -39, 2, 91, 11382],[82, 40, 15, 31, 56, 78, -6, 55, -53, 81, -42, 24, -15, 80, 46, -50, 42834],[-49, -92, -1, -83, -18, -87, -78, -58, -52, 39, 46, -67, -48, -79, -95, 98, -4613],[39, 69, 25, -28, -44, 58, 87, -10, 0, -29, 18, -44, -25, 23, 3, -1, 11286],[-79, 70, -70, 10, 10, -11, -79, -17, -11, 37, -30, 62, -27, -69, -49, 58, -12031],[35, -59, -41, -80, 53, -55, 21, -88, 88, 72, -19, -57, -85, -72, -60, -35, -29429],[100, 49, 98, -60, 33, 95, 51, -21, -94, -13, -43, -93, 70, -13, 11, 62, 24097],[-75, -81, 29, -89, -79, 60, -16, -59, 67, -85, 51, -13, 18, -44, -13, -56, -42878],[-53, 75, -74, -71, -53, 28, -36, -79, 5, -61, -61, 3, 50, -58, 50, 80, -21351],[-68, 94, 100, -75, 56, 96, 40, 84, -46, -13, 72, 29, 67, -20, 0, -6, 32963],[98, 35, 61, -95, -29, 71, -3, -5, -73, -11, 46, -91, -19, 67, 98, 10, 15523],[22, -10, 77, -63, -1, -46, 65, 31, -17, -37, -74, 32, 10, 80, -56, -46, -6633],[-34, 28, 61, 85, -65, 62, -46, 53, -28, 54, 44, 26, -93, 18, -15, -8, 14673],[20, -9, -80, -41, -18, -90, -51, 85, 12, -3, -28, -48, -98, -4, 57, -98, -33143]]
SUBTRACTORS = [ -182857, -207457, -205769, -149913, -221729 ]
XOR_LIST = [ 89, 11025, 328509, 33362176, 10000000000, 1291467969, 42618442977, 59604644775390625]
input -> (p1, p2, …, p16)
or_sum = 0
counter = 0
for each tuple (q1, q2..q16, subtractor) in TUPLES:
for each index 1..16:
counter += p[index] * q[index]
or_sum |= subtractor – counter
input -> ((t11, t12), (t21,t22), (t31,t32), (t41,t42), (t51,t52))
for (t1, t2) in ((t11, t12), (t21,t22), (t31,t32), (t41,t42), (t51,t52)):
or_sum |= (((t1 << 8) | t2 ) << 4) / 2 - ~- SUBTRACTORS[index]
input -> (b1, b2, …, b8)
for b in (b1, b2, …, b8):
or_sum |= (b pow index) ^ XOR_LIST[index]
if or_sum == 0:
print ‘HAPPY’
else:
print ‘SKULL’It is worth showing some of the generator functions used to implement the stack machine.
function* dup_yield(arg) {
arg = yield, yield(arg_copy), yield(arg_copy)
}
function* swap_yield(arg1, arg2) {
arg1 = yield, arg2 = yield, yield(arg1), yield(arg2)
}
function* from_arr_end_yield() {
yield(stack[stack['length'] – 1 - (yield)])
}Swap_yield swaps the two variables on top of the stack as they are pushed from top to bottom and are plopped out from bottom to top.
From_arr_end_yield fetches variables from elements in arbitrary depth on the stack
We can write a solver using z3 which will give us the input 16 + 10 + 8 bytes to the different stages that will result in or_sum = 0. Below we will discuss the solver script we coded:
The first stage requires solving a system of 16 linear equations.
While SMT solvers aren’t the sharpest tools in the shed when it comes to linear algebra (compared to Sage or MATLAB), we used z3 either way, being our go-to tool for constraint solving.
import z3
BIT_SIZE = 16
def dot_product(lhs_vec, rhs_vec):
assert len(lhs_vec) == len(rhs_vec)
dp = z3.BitVecVal(0, BIT_SIZE)
for lhs, rhs in zip(lhs_vec, rhs_vec):
dp += lhs * rhs
return dp
def stage1():
inputs = z3.BitVecs('s1_1 s1_2 s1_3 s1_4 s1_5 s1_6 s1_7 s1_8 s1_9 s1_10 s1_11 s1_12 s1_13 s1_14 s1_15 s1_16', BIT_SIZE)
consts = (
[-95, 31, 58, -19, -87, -51, 71, 72, -9, 79, 33, -35, -21, 42, 13, -70],[64, 100, -27, 66, 22, 68, -21, -2, 26,
74, 48, 93, 68, -79, 69, 92],[49, 56, -75, 16, -79, 21, -5, 27, -7,
27, 50, -3, 13, -39, 2, 91],[82, 40, 15, 31, 56, 78, -6, 55, -53,
81, -42, 24, -15, 80, 46, -50],[-49, -92, -1, -83, -18, -87, -78, -58,
-52, 39, 46, -67, -48, -79, -95, 98],[39, 69, 25, -28, -44, 58, 87, -10, 0,-29, 18, -44, -25, 23, 3, -1],[-79, 70, -70, 10, 10, -11, -79, -17, -11, 37, -30, 62, -27, -69, -49, 58], [35, -59, -41, -80, 53, -55, 21, -88, 88, 72, -19, -57, -85, -72, -60, -35], [100, 49, 98, -60, 33, 95, 51, -21, -94, -13, -43, -93, 70, -13, 11, 62], [-75, -81, 29, -89, -79, 60, -16, -59, 67, -85, 51, -13, 18, -44, -13, -56], [-53, 75, -74, -71, -53, 28, -36, -79, 5, -61, -61, 3, 50, -58, 50, 80], [-68, 94, 100, -75, 56, 96, 40, 84, -46, -13, 72, 29, 67, -20, 0, -6], [98, 35, 61, -95, -29, 71, -3, -5, -73, -11, 46, -91, -19, 67, 98, 10], [22, -10, 77, -63, -1, -46, 65, 31, -17, -37, -74, 32, 10, 80, -56, -46], [-34, 28, 61, 85, -65, 62, -46, 53, -28, 54, 44, 26, -93, 18, -15, -8], [20, -9, -80, -41, -18, -90, -51, 85, 12, -3, -28, -48, -98, -4, 57, -98])
sums = ( -5309, 63804, 11382, 42834, -54613, 11286, -12031, -29429, 24097, -42878, -21351, 32963, 15523, -6633, 14673, -33143, )
assert len(inputs) == len(consts) == len(sums)
s = z3.Solver()
for i in range(len(inputs)):
s.add(dot_product(inputs, consts[i]) == sums[i])
s.check()
m = s.model()
for i in range(len(inputs)):
yield chr(m[inputs[i]].as_long())
print ''.join(stage1())The second stage requires solving a small set of constraints for pairs of flag-characters.
There’s some educational merit in solving this manually (each bit-wise operation used is trivially inversible, so it’s mostly grunt work) — but z3 is the perfect tool for the task at hand.
import z3
BIT_SIZE = 64
def stage2():
consts = (-182857, -207457, -205769, -149913, -221729)
inputs = z3.BitVecs("s2_1 s2_2 s2_3 s2_4 s2_5 s2_6 s2_7 s2_8 s2_9 s2_10", BIT_SIZE)
s = z3.Solver()
for i in range(len(inputs) / 2):
inp1, inp2 = inputs[i*2], inputs[i*2 + 1]
s.add (((((inp1 << 8) | inp2) << 4) / 2) == ~consts[i])
s.check()
m = s.model()
for i in range(len(inputs)):
print m
yield chr(m[inputs[i]].as_long() & 0x7F)
print ''.join(stage2())The third stage is solved by computing the n-th root of each of the constants.
def stage3():
for idx, n in enumerate((89, 11025, 328509, 33362176, 10000000000, 1291467969, 42618442977, 59604644775390625)):
exp = 1.0 / (idx + 1)
base = n ** exp # exp is 1/2, 1/3, 1/4, …
yield chr(int(round(base)))
print ''.join(stage3())After running the solver we append the results of the three stages and receive the flag:
flag{YIELd?Y1EldYIeLdyI3lDYiELd!!}
Comentários