요즘 자꾸 배가 나와서 운동을 다시 시작하려고 하는데, 맨몸운동을 한번 시작해볼까 하면서 주변에서 철봉을 찾으려고 했다. 그런데 요즈음 대 IT 시대에 해외 여행을 가서도 구글링과 어느정도 검색만으로 왠만한 맛집도 다 찾고 다 하는 시댄데, 철봉을 찾기가 어려웠다. 내가 어렸을 때만 해도 철봉이랑 평행봉이 어느정도는 있었던 것 같았는데도 불구하고 말이다.
그래서 이것저것 검색을 해 보다 보니, 나와 비슷한 생각을 하는 사람들이 좀 있었다. 어떤 사람은 구청에 철봉 만들어달라고 민원도 넣었다고 한다.
그래서 나도 민원을 넣었다.
나와 비슷한 생각을 했던 사람들이 꽤 있다.
그리고 얼마 안 되어서 답변이 왔다.
철봉이 이미 많다고 한다.
그래서 이렇게 철봉이 많지만 내가 찾기 힘들었으니, 이를 찾아주는 서비스를 한번 만들어 보면 어떨까 싶어서 만들어 보았다.
어떻게 만들었는가?
일단 내가 만든 서비스의 가장 중요한 요구사항은 이것이다. 유지비용이 들지 않을 것!
그래서 네이버 지도 API와 구글 지도 API를 알아보았는데, 네이버 지도 API는 사실상 무료나 다름없었다. 그래서 네이버 지도 API를 이용했다.
그리고 DB따위는 쓰지 않는 정적 HTML+CSS+JS 웹 호스팅을 하였는데, 이 또한 github 블로그 페이지를 이용해서 유지비용 0으로 만들었다.
데이터는 어디서 구했는가?
저기 구청장님께서 알려주신 데이터 + 내가 발품팔아서 알아낸 데이터가 전부이다. 지금 이 글을 쓰는 시점에는 9개 정도 밖에 없다. 물론 내가 쓰기에는 무리가 없는 듯 하다. 추가적으로 데이터를 기부받고 싶은데 그래서 홍보를 해야 하는데 좀 귀찮기도 하다.
버그같은걸 발견하거나 데이터를 추가하려면 어떻게 해야하는가?
일단 철봉 지도 웹 하단에다가 링크를 두긴 했는데, 데이터 추가는 내 이메일로 철봉의 위도, 경도, 간단한 설명과 사진 정도를 보내주면 된다. 위도와 경도는 저기 지도 웹에서 우측 하단에 +라고되있는 버튼을 누르면 숫자로 나타나게 된다.
그러면 내가 하나하나 검토해서 수작업으로 올릴 예정이다. 아직 홍보를 1도 안했으니 제보도 1도 안왔다.
버그발견시도 웹 하단에 링크에 github issue 페이지로 연결시켜놨다. 그쪽으로 남겨주면 내가 확인하고 처리하겠다.
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()
