| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
[[컴퓨터공학|컴퓨터 과학 & 공학
Computer Science & Engineering
]]- [ 펼치기 · 접기 ]
- ||<tablebgcolor=#fff,#1c1d1f><tablecolor=#373a3c,#ddd><colbgcolor=#0066DC><colcolor=white> 기반 학문 ||수학(해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학(환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학(형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 ||
하드웨어 구성 SoC · CPU · GPU(그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품 기술 기계어 · 어셈블리어 · C/C++ · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시(SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속 연구
및
기타논리 회로(보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영 체제 · 데이터베이스 · 프로그래밍 언어{컴파일러(어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩(유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도(최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리(기계 번역 · 음성인식) · 버전 (버전 관리 시스템 · Git · GitHub)
Rainbow Table
1. 설명
레인보우 테이블은 해시 함수(MD5, SHA-1, SHA-2 등)을 사용하여 만들어낼 수 있는 값들을 왕창 저장한 표이다. 물론 해시 함수는 입력이 무제한이라서 모든 내용을 넣는 게 아니고, 이를테면 영어 소문자와 숫자 조합으로 일정 길이까지의 모든 문자열에 대해서 계산한다거나 하는 것이다. 이걸 그대로 저장하면 거듭제곱의 위력을 확실하게 체험할 수 있기 때문에 (문자열에 한 글자 추가할 때마다 아무리 적어도 30배, 문자 조합이 많으면 200배씩 커진다!) 적절한 가공 과정을 거친다. 이건 후술.이렇게 무식하게 값을 때려박는 테이블의 특성상, 작은 테이블도 기본 100GB는 거뜬히 넘는다. 아스키 코드를 전부 커버하는 테이블은 전용 알고리즘까지 만들어 최대한 쥐어짜내봐야 4글자에 약 75GB, 6글자는 58,824TB, 실효성이 생기는 정도인 8글자는 47,225,249,742TB에 달한다. 참고로 8글자짜리 소문자+숫자 조합은 약 328GB.
2. 만들어진 이유
2.1. 브루트 포스 공격시 더 빠르게 비밀번호를 시도해 보기 위해서
브루트 포스 항목에도 나와 있듯이, 무식하게 대입을 하는 데에는 시간이 엄청나게 걸린다. 10자리 영문 소문자+숫자 조합을 초당 1억번 대입을 한다 하더라도 1년 이상 걸리는데, 해시를 계산하느라 초당 대입량이 적어지면... 이러한 문제를 조금이나마 해결하기 위해 나온 것이 첫 번째 이유이다. 해시를 일일이 계산해 내느니 차라리 미리 만들어진 테이블에서 해시값만 쏙쏙 뽑아다가 집어넣으면 해시 계산하는 시간이 절약되니 공격 과정을 좀 더 빨리 끝낼 수 있다. 일종의 사전 공격.2.2. 해시(Hash)에서 평문을 추출해내기 위해서
해시는 기본적으로 역함수가 존재하지 않는 함수로 계산해낸다. 즉, 암호화-복호화 과정이 불가능하다는 말이다. 그래서 사람들이 고안해낸 방법은 수학적으로 아예 역함수가 존재하지 않는 함수 가지고 씨름할 바에 차라리 가능한 모든 경우의 수를 다 써놓고 거기서 찾아내자!이다. 그래서 데이터베이스와 같은 자료에서 뽑아낸 해시값을 레인보우 테이블과 대조하여 평문을 찾아내는 것이다.비슷하게 발표된 통계데이터만 가지고 전체 데이터 셋을 추론할 수도 있다. 특히 값이 실수가 아니라 정수형이 많은 인구조사라던가... 해서 미국의 인구조사 결과는 1980년도부터 발표 전에 데이터를 살짝 고친다고 한다.
3. 아이디어
그냥 가능한 모든 값들을 저장하면 되는 걸 굳이 왜 "레인보우 테이블"이라고 부르냐 하면, 레인보우 테이블은 계산 시간을 희생해서 공간을 압도적으로 줄일 수 있다. 이를테면 암호 하나를 찾는 시간을 10만배 늘리는 대신 테이블을 10만분의 1로 줄일 수 있는 것. 어차피 해시 함수는 10만배 느려져 봤자 밀리초 단위기도 하고, 레인보우 테이블에 저장되는 값 숫자 대비 찾을 암호 숫자가 매우 적기 때문에 쓸만한 것이다.(원 이미지, CC-by-sa 2.5로 배포됨)
레인보우 테이블에는 해시 함수 H 말고도 이 해시의 결과를 레인보우 테이블의 가능한 입력으로 변환해 주는 함수 R이 더 들어간다. 물론 R은 입력에 따라 다르고, 해시 함수와는 달리 원래 가능한 입력에 적절히 대응만 되기만 하면 된다. 다르게 생각하면, 레인보우 테이블은 H를 깨는 게 아니라 f(x) = R(H(x))인 f를 깬다. H와는 달리 f는 입력과 출력이 같기 때문에 다루기가 쉽다.
처음에 테이블을 만들 때는...
- 가능한 입력 중 하나를 잡아서 H를 적용한다.
- 함수의 결과를 R로 변환한다.
- 이 과정을 필요한 숫자(k회라고 하자)만큼 반복한다.
- 이제 입력 x와 마지막에 변환된 값 y = R(H(...R(H(x))...)) = fk(x)를 저장한다.
- 이 작업을 최대한 많은 입력에 대해 반복한다.
여기서 중요한 점은, x와 y만 저장해도 계산만 좀 더 하면 f(x), f(f(x)), ..., fk-1(x)의 다른 k-1개의 입력이 커버된다는 것이다. 중간에 저장해야 할 게 k개에서 1개가 되었으니 공간이 1/k가 된다!
이 테이블을 써 먹으려면, 입력 a = H(b)가 있을 때 R(a), R(H(R(a))), ...를 계산해서 테이블의 y에 겹치는 게 있는지 보면 된다. 겹치는 게 있다면 대응되는 x로부터 최대 k번 f를 적용해서 b가 나오는지 확인해 보면 된다. (f(b) = f(c)인 c가 있을 수 있으므로 확인이 실패할 수 있다.) 안 나오면 그냥 한 번도 커버가 안 된 거고 나오면 잘 된 거다. 참 쉽죠?
...실은 뻥이고, 이 방법은 치명적인 문제가 있는데 입력이 많이 들어가면 많이 들어갈수록 f(x), f(f(x)) 등이 서로 충돌할 가능성이 높아진다. 한 번 충돌이 나는 입력이 나오면 거기서부터는 커버되는 입력들이 똑같으니까 공간 절약이 1/k에서 확 줄어들 수 있는데, 이런 (x, y) 쌍들을 걸러낼 수 없다! 예를 들어 "뿌뿌뽕"을 f에 세 번 돌린 것과 "용개"를 f에 다섯 번 돌린 게 같은 값이 나온다고 하자. 그러면 이 두 값이 커버하는 입력의 개수는 2k개가 아니라 k+5개[1]밖에 안 되니까 도움이 안 된다. 이럴 바에는 둘 중 하나를 날려 버리면 좋겠는데 (x, y) 쌍만 가지고는 이걸 알 수 없다.
(원 이미지, CC-by-sa 2.5로 배포됨)
그래서 진짜 레인보우 테이블은 각 단계별로 서로 다른 R을 쓴다(위 그림들에서 첨자가 붙어 있는 게 이 때문). 서로 다른 R을 쓰기 때문에 앞에서 "뿌뿌뽕"과 "용개"가 우연히 같은 값이 나왔어도 같은 위치에서 충돌이 난 게 아니면 서로 다른 입력을 커버하게 된다. 이 경우 커버하는 입력의 개수는 2k개에서 2k-1개로 줄어드는 수준으로, k가 크다면 무시해도 될 수준. 같은 위치에서 충돌이 나오면 그 뒤로는 같은 입력이 생성되긴 할텐데, 이러면 y가 겹칠테니 그냥 제거하면 된다.
이런 레인보우 테이블을 만들 가능성 자체를 없애기 위해 오늘날 암호를 저장할 때는 bcrypt나 scrypt와 같이 한 번 해시 함수를 적용하는 데 더럽게 오래 걸리는 함수를 써야 한다.
4. 관련 문서
5. 관련 링크
[1] "뿌뿌뽕", f("뿌뿌뽕") .. f2("뿌뿌뽕"), "용개", f("용개") .. f4("용개"), f3("뿌뿌뽕") = f5("용개"), .., fk("뿌뿌뽕") = fk+2("용개").