아인스트라세의 SW 블로그

https://medium.com/@sasaxxx777/cors-misconfiguration-leading-to-private-information-disclosure-9ebcbd4740d9

본 포스팅은 위 블로그 글의 번역본입니다.

----------------------------------------------------------------------------------------

이번 글에서는 CORS에 관하여 다루어볼 예정이다.

일단 이 사이트를 private.com이라고 해보자.

이것 저것 좀 시도해본 뒤, 이 사이트의 서브도메인을 찾았는데 이거를 xyz.private.com이라고 부르겠다.

그리고 나서 burp suite로 크롤링이랑 파라메터 digging을 시도했고, origin 헤더랑 같이 요청이 날아갔다.

origin 헤더는 이 요청이 어느 도메인에서 시작되었는지를 나타내는 HTTP 헤더이고, path information은 갖지 않는다. 즉 xyz.private.com/index.php 에서 요청을 보냈다면 /index.php 부분의 값은 무시하고 domian 부분만 해당한다는 뜻.

Origin 헤더는 Access-Control-Allow-Origin 헤더에 의해 accept되었고, Access-Control-Allow-Credentials 헤더가 true로 값이 설정되었다.

Access-Control-Allow-Origin 헤더는, 해당 Origin에서 온 요청이 Accept될 것인지 아닌지를 알려주는데, xyz.private.com이 값으로 있으므로, 해당 URL의 Origin에서 시작된 요청은 Accept된다는 뜻이다. Origin 구분없이 Accept될 것이라면 *라고 쓰여있을 것이다.

Access-Control-Allow-Credentials라는 HTTP 헤더는 응답 헤더인데, credential이 포함된 요청을 보냈을 때, 응답 값을 브라우저가 프론트엔드 자바스크립트한테 요청할 지 안할지를 정해주는 그런 헤더라고 한다.

이 현상을 보고, 저자는 서버가 어떻게 origin header를 처리하는지를 조사를 했다.

그리고 원래 메인 도메인으로 요청을 보냈고, 서버는 이에 대하여 accept 했다.

그래서 private.com에서 점을 지우고 보냈는데, 서버가 또다시 accpet을 해 주었다. 서버는 도메인 이름과 com이 있는지만 체크하고, 그 사이에는 무엇이 있든간에 무시하는 것 같았다. 그래서 private와 com사이에 1을 넣어서 보내보았다.

그리고 똑같이 accept가 응답이 돌아왔다.

그래서 privatescom.000webhostapp.com이라는 주소로 하나 도메인을 만들었고, 이를 이용해서 POC 코드를 작성해 보았다.

그리고 만든 도메인에서 응답을 받을 수 있었고, 유저 정보를 훔칠 수 있었다.

바이너리 서치(binary search)

바이너리 서치는 아마 컴퓨터공학과 1~2학년이라면 자료구조시간이나 알고리즘 시간에 이름 한번쯤은 들어봤을 것이다.

그만큼 기본적이지만 강력한 알고리즘 중 하나이다. 

근데 요녀석은 정렬처럼 그냥 라이브러리 하나 호출해서 띡~ 하고 끝날때도 있는데, 뭔가 응용해야할 때가 간혹 있다.

대충 한번 정리해보자.

일단 바이너리 서치를 할려면 선행조건이 있다. 

정렬되어 있어야 한다는 점

그래서 중간에 하나 아무거나 짚어서 봐도 그 이전과 그 다음 값들이 어떨지 예상을 할 수 있는 것이다. 이를 이용해서 시간복잡도를 //(O(lgN)//)으로 줄일 수 있다.

일단그리고 C++ SLT에 binary_search라는 함수가 있다. 배열같은 컨테이너 시작과 끝 iterator를 넣고, 찾는 값을 넣으면 bool을 리턴해준다. 원하는 값이 있으면 true, 그렇지 않으면 false를 리턴한다.

근데 그러면 내가 찾는 녀석이 어디쯤에 존재하는지를 알 수가 없다.

그래서 보통 직접 구현해서 쓰곤 한다.

lower_bound와 upper_bound

근데 생각을 해 보자. 원래 배열이 잘 정렬되어 있긴 한데, 중복된 수가 있다면?

그리고 그 중복된 수가 몇 개인지를 알아야 하는 경우라면? 아니면, 그 중복된 수 모두를 체크해야 하는 경우라면 어떻게 해야할까?

위와 같이 중복이 있는 배열이라고 할 때, 모든 40을 다 찾아야 한다면 다음과 같이 lower bound와 upper bound를 이용하면 된다.

lower_bound(40)을 행하면 첫번째로 나타나는 40의 인덱스인 4를 리턴하고, upper_bound(40)을 행하면 마지막으로 나타나는 40의 인덱스 다음 값인 7을 리턴한다.

그러면 lower_bound부터 upper_bound까지 for-loop을 돌면 모든 40인 값들을 찾을 수 있다.

그렇다면 lower_bound(35)를 수행한다면? 35는 배열에 없는 값이다.

그러면 35가 들어갈 수 있는 4라는 인덱스를 똑같이 리턴한다. 4번자리는 기존 40이 있던 자리이다. 그러면 4번 자리에 35를 넣고, 기존 값들인 40, 50 등 을 한 칸씩 뒤로 밀면 35가 들어가도 전체 배열은 그대로 정렬된 상태를 유지하게 된다.

마찬가지로 그렇다면 upper_bound(35)를 수행한다면? 35는 배열에 없는 값인데, lower_bound(35)를 한 값과 마찬가지로 4라는 인덱스를 리턴한다. 마찬가지로 4번 자리에 35를 넣을 수 있다는 뜻이다.

배열에 없는 값에 대하여 lower_bound나 upper_bound 연산을 수행하면 같은 값이 나오게 된다.

이는 즉, 배열 안에 있는 x값의 개수를 찾고 싶다면 upper_bound(x) - lower_bound(x)라는 연산으로 할 수 있다.

그렇다면 그 정의는 다음과 같게된다.

lower_bound

- x라는 값을 배열에 넣을 때, 정렬된 상태를 유지하면서 넣을 수 있는 위치 중 가장 앞

(이때 넣는다는 개념은 해당 자리에 x를 넣고, 기존 값들은 다 1칸씩 뒤로 민다고 가정함)

- x라는 값 보다 같거나 큰 값 중 가장 앞에 있는 원소 위치

upper_bound

- x라는 값을 배열에 넣을 때, 정렬된 상태를 유지하면서 넣을 수 있는 위치 중 가장 뒤

- x라는 값보다 큰 값 중 가장 앞에 있는 원소 위치

---------------------------------------------------------------------

https://12bme.tistory.com/120

http://soen.kr/lecture/ccpp/cpp4/42-3-2.htm

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

설날 큰집을 가면서 노란책을 들고갔는데, 책을 보다가 나온 POJ문제 풀이를 보다가 혹시 백준에도 같은 문제가 있나 싶어서 확인해보니 있었다.

그래서 백준에 있는 김에 한번 풀어보았다.

POJ에서는 1182번 문제였는데, 직접 가보니까 중국어로 문제가 써있어서 해석은 안된다 싶었는데, Sample Input 까지도 일치하더라. 대신 크롬에 내장된 구글 번역기를 사용하니 그런대로 해석은 되는 듯 하다.

문제 분석

일단 나는 책을 보면서 문제를 봤기 때문에, 풀이를 거의 바로 보아서 힌트 없이 스스로 생각해볼 만한 시간이 조금 부족하긴 했다.

대충 보면 명제와 관련된 문제이고, 논리와도 관련이 있다. 여태까지의 정보를 조합해서 모순이 되는 논리를 찾아야 한다.

내가 풀고나서 찍은 스샷이니, 내가 풀 당시에는 15명밖에 안푼 문제이기도 하다.

일단 풀이부분은 스포일러 방지로 접은글로 표현하겠다.

풀이

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define MAXN 50020

// disjoint set (DSU)
int parent[MAXN * 3];
int depth[MAXN * 3];

int root(int a) {
	int p = a;
	while (p != parent[p])
		p = parent[p];
	parent[a] = p;
	return p;
}
bool same(int a, int b) {
	return root(a) == root(b);
}
void unite(int a, int b) {
	a = root(a);
	b = root(b);
	if (a == b) return;
	if (depth[a] < depth[b]) {
		parent[a] = b;
	}
	else {
		parent[b] = a;
		if (depth[a] == depth[b])
			depth[b]++;
	}
}
int main() {
	int N, K;
	scanf("%d%d", &N, &K);
	//init
	for (int i = 0; i <= N * 3 + 10; i++) {
		parent[i] = i;
		depth[i] = 0;
	}
	// i => i는 A이다.
	// i + N => i는 B이다.
	// i + N*2 => i는 C이다.
	int ans = 0;
	while (K--) {
		int t, a, b;
		scanf("%d%d%d", &t, &a, &b);
		a--;
		b--;
		if (a < 0 || b < 0 || a >= N || b >= N) {
			ans++;
			continue;
		}
		if (t == 1) {
			//a랑 b랑 같은 종류이다.
			if (same(a, b + N) || same(b, a+N) || same(a+N, b+N+N) || same(b+N, a+N+N) ||
				same(a, b + N + N) || same(b, a + N + N)) {
				ans++;
			}
			else {
				unite(a, b);
				unite(a + N, b + N);
				unite(a + N + N, b + N + N);
			}
		}
		else {
			//a는 b를 잡아먹는다.
			if (same(a, b) || same(a + N, b + N) || same(a + N + N, b + N + N) ||
				same(a, b + N + N) || same(a + N, b) || same(a + N + N, b + N)) {
				ans++;
			}
			else {
				unite(a, b + N);
				unite(a + N, b + N + N);
				unite(a + N + N, b);
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

if (t == 1) {
	//a랑 b랑 같은 종류이다.
	//if (same(a, b + N) || same(b, a + N) || same(a + N, b + N + N) || same(b + N, a + N + N) ||	same(a, b + N + N) || same(b, a + N + N)) {
	if (same(a, b+N) || same(a, b+N+N)) {
		//다른걸로 분류하면 모순
		ans++;
	}
	else {
		unite(a, b);
		unite(a + N, b + N);
		unite(a + N + N, b + N + N);
	}
}
else {
	//a는 b를 잡아먹는다.
	//if (same(a, b) || same(a + N, b + N) || same(a + N + N, b + N + N) || same(a, b + N + N) || same(a + N, b) || same(a + N + N, b + N)) {
	if (same(a,b) || same(a, b+N+N)) {
		ans++;
	}
	else {
		unite(a, b + N);
		unite(a + N, b + N + N);
		unite(a + N + N, b);
	}
}