하용권

tcp/ip는 본질적으로 해킹에 취약. 연결 설정 및 통신 과정에 많은 문제 있음.

1. 클라이언트에서 서버로 최초 연결을 시도하는 syn 패킷 전송하면 서버는 연결을 위해  버퍼 자원을 할당.

   계속 syn 패킷만 전송하는 클라이언트가 있다면 서버는 통신 버퍼를 모두 소진해 네트워킹 불가능.

2. 정상적인 통신 연결이 완료된 후에 해커는 클라이언트를 가장해서 통신 세션을 쉽게 가로챌 수 있음.

   통신 상대방을 인증하기 위해 tcp 헤더에 있는 시퀀스 번호를 확인 하는데, 제삼자가 이 번호를 쉽게 알아내서 위장       가능

3. ip 헤더에 있는 소스 ip 정보는 쉽게 위조 가능. 소스 ip를 클라이언트 pc가 아닌 공격 대상 시스템 ip로 위조해 syn 패     킷을 서버에 전송하면 서버는 agk 패킷을 공격 대상 시스템으로 보내게 됨. 일종의 dos공격 가능.

1. 포트 스캐닝

ip는 서버를 식별하는 논리적인 주소. 포트는 하나의 ip를 여러 개의 애플리케이션이 공유하기 위한 논리적인 단위.

ip는 ip 프로토콜에서 식별자로 사용되고, 포트는 tcp/udp 프로토콜에서 식별자로 사용 됨. 방화벽 또는 서버에서 네트워크 서비스를 위해 포트를 개방하고 있음.

대표적인 것이 80 과 443 포트. 각각 http와 https 서비스를 위해 방화벽에서 개방하고 있음. 필수적인 포트 외에 관리 편의성을 위해 몇 개의 포트를 추가로 사용하고 있음. 대표적으로 ftp나 텔넷 서비스를 제공하는 21,22번 포트.

포트 스캐닝은 서비스를 위해 방화벽이나 서버에서 개방한 포트 목록을 알아내는 기술

다양한 기법이 존재. 

크게 udp기반, tcp 기반 기법 으로 분류됨.

udp 기반 : udp패킷을 전송해서 확인

tcp 기반 : syn, fin등 다양한 패킷을 전송하면서 포트 개방 여부 확인. 

기법별로 성능과 은닉성의 차이가 있음.

2. 패킷 스니핑

tcp/ip 통신을 하는 이더텟 기반 동일 네트워크 환경(하나의 라우터 사용)에서는 mac주소 기반으로 패킷이 동작.

하나의 pc에서 다른 pc로 데이터를 전송할 때, 전체 pc에 데이터를 브로드캐스트함. 패킷의 목적지 mac주소가 자신의 것과 같으면 받아들여서 처리하고, 그렇지 않으면 버리는 방식.

패킷 스니퍼는 모든 패킷을 버리지 않고 처리해서 동일 네트워크에서 이동하는 모든 데이터의 흐름을 한눈에 파악 가능.

3. 세션 하이재킹

http 세션 하이재킹과 tcp 세션 하이재킹으로 나뉨. 

전자는 웹 서비스 인증 정보를 저장할 쿠키의 SessionId 값을 탈취해서 해킹에 이용하는 방식.

후자는 tcp 패킷 정보를 탈취하는 방식. 

tcp 프로토콜은 통신 상대방을 인증하기 위해, ip, port, sequence number 3개 요소를 사용함. 

tcp 세션 하이재킹은 패킷 스니핑을 통해 알아낸 인증정보를 가지고 클라이언트와 서버 사이의 통신을 중간에서 가로챔.해커는 클라이언트와 서버와의 연결을 잠시 끊고 발신지 ip를 해커 pc로 변경해서 서버와 커넥션을 재설정.

서버는 통신 연결이 끊겼다가 다시 연결 됐다고 생각하고, 해커 pc를 클라이언트로 인식함.

클라이언트와 해커pc도 같은 방식으로 연결이 설정됨. 클라이언트와 서버와의 통신은 모두 해커 pc를 거치게 되고 해커는 모든 정보를 제어할 수 있게 된다.

4. 스푸핑

네트워크 관점에서는 크게 dns, ip, arp 3개의 자원에 대해서 위장을 통한 공격이 가능.

대표적으로 arp 스푸핑에 대해 알아보면,

arp는 ip주소를 가지고 mac주소를 알아내는 프로토콜.

pc는 내부에 ip와 mac정보가 저장된 arp 캐시 테이블을 가지고 있음. 통신 상대방을 인지하기 위해 해당 테이블을 조회해서 mac 정보를 추출. arp 캐시 테이블에서 정보를 찾지 못하면 arp 프로토클을 통해 ip에 해당하는 amc 정보를 찾을 수 있음.

arp 프로토콜은 보안이 고려되지 않았기 때문에 쉽게 해킹 가능.

arp reply 패킷을 통해 상대방의 arp 캐시테이블을 간단하게 조장 가능. arp 캐시 테이블에는 상대방 ip와 mac이 매핑 되어 있음. pc a와 b에 해당하는 정보를 해커 pc의 mac주소로 교체하면 모든 통신은 해커 pc를 거치게 됨.

5. dos

서비스 거부 공격은 인터넷에서 갖아 많이 활용되는 해킹 기법의 하나.

syn패킷의 발신지 주솔르 변경하거나, syn 패킷만 지속적으로 전송하고, 대량의 ip 패킷을 작은 단위로 쪼개서 전송하는 등의 행위를 통해 시스템을 서비스불능 상태로 만들 수 있다. 이뿐만 아니라 dos는 정상적인 패킷을 대량으로 발생시켜 서비스를 마비시킬 수 있음.

현재는 dos 대응 장비들이 발달해서 소수의 pc로 공격대상 시스템을 서비스 불능 상태로 만들기 어려움.

이를 극복하기 위해 해커는 바이러스를 배포해서 불특정 다수의 pc를 좀비 pc로 만들고, 원격에서 대량의 트래픽을 발생시키도록 제어하는 분산 서비스 거부공격(ddos)가 등장.

ddos는 봇넷을 활용. 봇넷은 악성 코드가 포함된 파일을 인터넷을 통해 배포해서 다수의 좀비pc를 확보, c&c서버를 통해 종비 pc를 통제하는 기술. 

웹은 기본적으로 인터넷 브라우저, 웹 서버, 데이터베이스 3개의 요소로 구성.

인터넷 브라우저 : 사용자의 입력 처리, 웹 서버로부터 받은 데이터를 가공해 화면을 구성.

웹 서버 :             http 요청을 분석해 정해진 기능 수행. 데이터 처리가 필요한 경우 데이터 베이스를 연결해 관련                                작업 수행.

데이터베이스     : 데이터를 안전하게 관리, 자료 입력과 조회 기능 지원.

파일 업로등 기능일 이용해 웹 셸 파일과 악성 코드를 업로드 한다. 업로드한 파일의 위치를 알아내 웹 셸 파일을 실행하면 해커는 웹 서버 장악 가능.

1. XSS(Cross-SITE Scripting)

게시판 게시물에 악성코드를 포함하는 스크립트를 심어놓고 게시물 읽은 사용자 pc에서 개인정보를 추출하는 해킹 기법.

악성 코드는 대부분 스크립트 코드, 쿠키를 읽어 특정 url로 전송하는 기능 수행. 현재는 장비발달로 인해 공격 빈도 감소

2.CSRF(Cross Site Request Forgery)

게시판에 악성코드 삽입, 사용자가 해당 게시물 읽으면 공격이 수행 됨.(XSS와 비슷)

차이점은 사용자 pc를 통해 웹 서버 공격. 

3. 피싱

은행이나 증권사이트와 비슷한 웹사이트 만들어, 사용자의 금융정보나 개인정보 타루치하는 기법. 

4. 파밍

DNS를 해킹, 정상적인 도메인 이름을 호출해도 위장 사이트가 전송되게 하는 해킹 기술. 

위장 사이트의 IP가 사용자 브라우저에 정송되면 사용자는 해커가 만든 웹 사이트에 개인정보를 입력하게 됨.

5. SQL 인젝션

HTML input 태그를 활용.

브라우저에서 사용자 아이디와 비밀먼호를 입력받아 웹 서버로 전달하면 웹 서버는 데이터베이스에 일치하는 정보가 있는지 sql문을 통해 확인.

이때 아이디와 비밀번호에 일반적인 값을 넣는 것이 아니라, 데이터베이스에 오동작을 유발할 수 있는 값 입력.

다양한 비정상 sql문을 반복적으로 입력하면서 데이터를 관찰하면 시스템 해킹이 가능한 sql 문 획등 가능.

6. 웹 셸 (web shell)

웹에서 제공하는 파일 업로드 기능 악용. 서버를 원격에서 조정할 수 있는 파일을 웹 서버를 통해 업로드.

해커는 업로드 한 파일 위치를 파악하고 접근 가능한 url을 찾아냄.

이 url을 통해 웹 셸 파일을 실행해서 운영 체제를 통제할 수 있는 강력한 권한 획등 가능.

1. 메시지 후킹

 user32.dll 의 SetWindowsHookExA() 메서드를 이용.

윈도우는 키보드, 마우스 등에서부터 들어오는 메시지를 훅 체인을 통해 처리.

훅 체인은 메시지를 처리하는 일련의 함수 포인터를 모아놓은 리스트.

훅 체인 상에 강제적으로 프로그래머가 원하는 처리 프로세스에 대한 포인터를 등록 -> 메시지 들어올 때 원하는 작업 가능.

이를 이용한 해킹 기법 

key logger : 키보드 입력 메시지를 중간에 가로채 해커에게 전송.

2. API 후킹

운영체제에서 제공하는 디버깅 프로세스를 이용.

디버거 이용해 애플리케이션 특정 명령어에 breakpoint 설정, 특정 메서드를 수행하도록 등록.

애플리케이션은 작업을 수행하다 중단점을 만나면 등록된 메서드를 실행.(콜백 메서드라고 함)

여기에 해킹 코드를 심어 놓으면 원하는 동작 가능.

3. DLL 인젝션

동적으로 사용할 수 있는 라이브러리인 DLL을 애플리케이션에 삽입하는 기술.

3가지 방법

 - 레지스트리를 사용. 레지스트리의 특정위치에 원하는 dll 이름을 입력해 놓음. 

 - 후킹 함수 사용. 특정 이벤트가 발생했을 때 dll을 로딩하는 후킹 함수로 등록하는 것.

 - 실행 중인 애플리케이션에 원격 스레드 생성해 dll을 삽입하는 것.(윈도우는 CreateRemoteThread() 함수 제공)

4. 코드 인젝션(code injection)

스레드를 활용한 dll인젝션 기법과 유사. 

차이점은 dll 대신 직접 샐항 가능한 셸 코드(shell code)를 삽입.

장점 : dll을 미리 시스템 특정 위치에 저장할 필요 x, 속도 빠르면 노출이 쉽지 않음.

단점 : shell code의 특성상 복잡한 해킹 코드 삽입 불가.

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

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
	int map[100][100] = { 0 };
	int m, n, k;
	int cnt = 0;
	int dx[4] = { 0, 0, 1, -1 };
	int dy[4] = { 1, -1, 0, 0 };
	vector<int> ret;
	bool visited[100][100] = { 0 };
	cin >> m >> n >> k;

	for (int i = 0; i < k; i++){
		int r_x, r_y, l_x, l_y;
		cin >> l_x >> l_y >> r_x >> r_y;
		l_y = m-1 - l_y;
		r_y = m-1 - r_y;
		for (int j = l_y; j > r_y; j--){
			for (int k = l_x; k < r_x; k++){
				map[j][k] = 1;
			}
		}
	}

	for (int i = 0; i < m; i++){
		for (int j = 0; j < n; j++){
			queue<pair<int, int>> q;
			int tmp_ret = 0;
			if (visited[i][j] || map[i][j]) continue;
			cnt += 1;
			q.push({ i, j }); visited[i][j] = true;


			while (!q.empty()){
				tmp_ret += 1;
				int x = q.front().second, y = q.front().first;
				q.pop();

				for (int k = 0; k < 4; k++){
					int xx = x + dx[k], yy = y + dy[k];

					if (xx >= n || yy >= m || xx < 0 || yy < 0) continue;
					if (map[yy][xx] == 1 ||visited[yy][xx]) continue;
					q.push({ yy, xx }); visited[yy][xx] = 1;
				}
			}

			ret.push_back(tmp_ret);
		}
	}

	sort(ret.begin(), ret.end());

	cout << cnt << endl;
	for (int i = 0; i < cnt; i++){
		cout << ret[i] << ' ';
	}

}

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

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
	int n, c;
	int arr[200000];
	
	cin >> n >> c;
	for(int i = 0; i < n; i++) scanf("%d", arr+i);
	sort(arr,arr+n);
	
	int left = 0, right = arr[n-1]-arr[0]+1;

	while(left + 1 < right){
		int mid = (left+right)/2;
		int cnt = 1;
		int start = arr[0];
		
		for(int i = 1; i < n; i++){
			if(arr[i] - start >= mid){
				cnt++;
				start =arr[i];
			}
		}
		
		if(cnt < c) right = mid;
		else		 left = mid;
		
	}
	
	cout << left;
	
}

mid를 공유기 간의 거리로 설정하고 풀었습니다.

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

길이(mid)를 정해두고, 만약 이 길이를 넘거 같아지면 새로운 블루레이 cd에 길이를 저장하는 방식으로 풀었습니다.

	#include <iostream>
	#include <algorithm>
	#define MAX_SIZE 100000
	using namespace std;
	
	int main(){
		int n, m;
		int arr[MAX_SIZE] = {0};
		int left = 0, right = 0;
		cin >> n >> m;
		
		for(int i = 0; i < n; i++){
			scanf("%d", &arr[i]);
			left = max(left,arr[i]);
		}
		right = 1000000000/m;

		
		while(left +1< right){
			int mid = (right + left) /2;
			int sum = 0, cnt = 0;
			
			for(int i = 0; i < n; i++){
				
				if(sum + arr[i]>= mid){
					cnt++;
					sum = 0;
				}
				sum += arr[i];
			}
			
			if(sum!=0) cnt++;
			
			if(cnt <= m) right = mid;
			else		left = mid;
		}
		
		
		
		cout << left;
		
	}

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

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
	int n, m;
	int arr[500000];
	int ans[500000] = {0};
	
	cin >> n;
	for(int i = 0 ; i < n; i++) scanf("%d", &arr[i]);
	sort(arr,arr+n);
	
	cin >> m;
	for(int i = 0; i < m; i++)scanf("%d", &ans[i]);
	

	
	for(int i = 0;  i < m; i++){
		bool chk = 0;
		int l_tmp = -1,r_tmp = n;
		int left = -1, right = n;

		while(left + 1 < right){
			int mid = (left+right)/2;
			
			if(arr[mid] > ans[i]) right = mid;
			else if(arr[mid] < ans[i])  left = mid;
			if(arr[mid] == ans[i]){
				l_tmp = mid;
				right = mid;
				left = -1;
				chk =true;
			}
		}
		
		left = -1, right = n;
		while(left + 1 < right){
			int mid = (left+right)/2;
			
			if(arr[mid] > ans[i]) right = mid;
			else if(arr[mid] < ans[i])  left = mid;
			if(arr[mid] == ans[i]){
				r_tmp = mid;
				left = mid;
				right = n;
				chk=true;
			}
		}
		if(chk)printf("%d ", r_tmp-l_tmp+1);
		else   printf("0 ");
	}
}

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

소수는 에라토스테네스의 채를 이용해서 구했습니다.

처음에 풀 때는 queue에 넣을 값을 찾기 위해 1000부터 9999까지 모두 뒤졌습니다. 당연하게도  시간초과가 뜨더군요.

그래서 1,10,100,1000 자리의 숫자만 변경하는 것으로 하니 잘 되네요.

#include <iostream>
#include <queue>
#include <cmath>
#include <string>
using namespace std;
bool num[10000] = { 0 };

void num_set() {

	for (int i = 2; i <= sqrt(9999); i++) {
		if (!num[i]) {
			for (int j = i + i; j <= 9999; j += i)
				num[j] = true;
		}
	}

}


int main() {
	ios_base::sync_with_stdio(false);
	num_set();
	int t;
	cin >> t;

	while (t--) {
		string x, y;
		int cnt = -1;
		bool chk = false;
		queue<string> q;
		bool visited[10000] = { 0 };

		cin >> x >> y;
		q.push(x); visited[atoi(x.c_str())] = true;

		while (!q.empty()) {
			cnt++;
			int size = q.size();
			
			for (int i = 0; i < size; i++) {
				string tmp = q.front(); q.pop();

				if (tmp == y) {
					chk = true; break;
				}

				for (int j = 0; j < 4; j++) {
					for (int k = 0; k <= 9; k++) {
						string dtmp = tmp;
						dtmp[j] = k + 48;
						if (visited[atoi(dtmp.c_str())]) continue;
						if (num[atoi(dtmp.c_str())]) continue;
						if (atoi(dtmp.c_str()) < 1000) continue;
						q.push(dtmp);
						visited[atoi(dtmp.c_str())] = true;
					}
				}

			}
			if (chk) break;
		}

		if (chk) cout << cnt << endl;
		else    cout << "Impossible" << endl;
	}

}

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

모든 정점을 돌아다니면서 bfs를 수행하면서, 시간을 증가시킵니다. 그리고 ret 변수를 최대 시간으로 계속 갱신합니다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int main(){
	char map[51][51];
	int dx[4] = {0,0,1,-1};
	int dy[4] = {1,-1,0,0};
	int ret = 0;
	int l,w;
	
	cin >> l >> w;
	
	for(int i = 0; i  < l; i++){
		cin >> map[i];
	}
	
	for(int i = 0; i < l; i++){
		for(int j = 0; j < w; j++){
			if(map[i][j] == 'L'){
				int cnt = 0;
				int chk = false;
				queue<pair<int,int> > q;
				bool visited[50][50] = {0};
				q.push({i,j}); visited[i][j] =true;
				
				while(!q.empty()){
					if(chk){
						cnt+=1;
						ret = max(ret, cnt);
					}
					int size = q.size();
					for(int h = 0; h < size; h++){
						int x = q.front().second, y = q.front().first;
						q.pop();
						for(int k = 0; k < 4; k++){
							int xx = x+dx[k], yy = y + dy[k];
							
							if(xx < 0 || yy < 0 || xx >= w || yy >= l) continue;
							if(visited[yy][xx] || map[yy][xx] == 'W') continue;
							visited[yy][xx] = true;
							q.push({yy,xx});
						}
					}
					chk = true;
				}
				
				
			}
		}
	}
	cout << ret;
}

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

#include <iostream>
#include <vector>
using namespace std;
vector<int> v[100];
int ret[100][100] = {0};
int n;

void dfs(int start, int y){
	
	for(int i = 0; i < v[start].size(); i++){
		int tmp = v[start][i];
		if(ret[y][tmp]) continue;
		ret[y][tmp] = 1;
		dfs(tmp,y);
	}
}

int main(){
	int tmp;
	cin >> n;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> tmp;
			if(tmp == 1)
				v[i].push_back(j);
		}	
	}
	
	
	for(int i = 0; i < n; i++){
		dfs(i,i);
	}
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++)
			cout << ret[i][j] << ' ';
		cout << endl;
	}
}