유명한 알고리즘 중 하나로 유클리드 호제법(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;
}
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 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.
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 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.
