위키원
"레인보우 테이블"의 두 판 사이의 차이
wlgns12244 (토론 | 기여) (→collision attack) |
wlgns12244 (토론 | 기여) |
||
| 14번째 줄: | 14번째 줄: | ||
해시테이블을 다른 자료구조와 비교해보면 이진탐색트리와 그 변형의 경우 메모리를 효율적으로 사용하는 편이지만 데이터 탐색에 소요되는 계산복잡성은 O(logn)입니다. 배열(array)의 경우 데이터 탐색에 따른 계산복잡성은 O(1)이지만, 메모리를 미리 할당해 둬야 하기 때문에 공간 효율적이라고 말하기 어렵다. | 해시테이블을 다른 자료구조와 비교해보면 이진탐색트리와 그 변형의 경우 메모리를 효율적으로 사용하는 편이지만 데이터 탐색에 소요되는 계산복잡성은 O(logn)입니다. 배열(array)의 경우 데이터 탐색에 따른 계산복잡성은 O(1)이지만, 메모리를 미리 할당해 둬야 하기 때문에 공간 효율적이라고 말하기 어렵다. | ||
해시는 보안 분야에서도 널리 사용된다. 키와 해시값 사이에 직접적인 연관이 없기 때문에 해시값만 가지고는 키를 온전히 복원하기 어렵기 때문이다. 아울러 해시함수는 길이가 서로 다른 입력데이터에 대해 일정한 길이의 출력을 만들 수 있어서 ‘데이터 축약’ 기능도 수행할 수 있다. | 해시는 보안 분야에서도 널리 사용된다. 키와 해시값 사이에 직접적인 연관이 없기 때문에 해시값만 가지고는 키를 온전히 복원하기 어렵기 때문이다. 아울러 해시함수는 길이가 서로 다른 입력데이터에 대해 일정한 길이의 출력을 만들 수 있어서 ‘데이터 축약’ 기능도 수행할 수 있다. | ||
| − | 다만 현재까지 개발된 거의 모든 해시함수는 해시충돌을 일으키는 것으로 확인됐다. 물론 해시충돌 자체를 줄이는 것도 의미가 있겠다만, 중요한 것은 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 하는 것이다. 극단적으로 위 그림에서 모든 키가 02라는 동일한 해시값으로 매핑이 될 경우 데이터를 액세스할 때 비효율성이 커지고, 보안이 취약(서로 다른 키인데도 동일한 해시값)해져 굳이 해시를 도입해 데이터를 관리할 이유가 없어진다.<ref> | + | 다만 현재까지 개발된 거의 모든 해시함수는 해시충돌을 일으키는 것으로 확인됐다. 물론 해시충돌 자체를 줄이는 것도 의미가 있겠다만, 중요한 것은 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 하는 것이다. 극단적으로 위 그림에서 모든 키가 02라는 동일한 해시값으로 매핑이 될 경우 데이터를 액세스할 때 비효율성이 커지고, 보안이 취약(서로 다른 키인데도 동일한 해시값)해져 굳이 해시를 도입해 데이터를 관리할 이유가 없어진다.<ref>〈[https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/ 해싱, 해시함수, 해시테이블]〉, 《랫츠고 블로그》, 2017-10-25</ref> |
==활용== | ==활용== | ||
| 46번째 줄: | 46번째 줄: | ||
대칭키 암호의 경우 암호에 사용된 키를 알아내면 암호화된 정보를 복원할 수 있고, 여기에서 사용한 키 길이에 따라 무차별 대입 공격의 최대 소요 시간이 정해진다. 암호화 키가 n비트일 경우 가능한 값은 최대 {\displaystyle 2^{n}} 2^{n}가지가 존재한다. | 대칭키 암호의 경우 암호에 사용된 키를 알아내면 암호화된 정보를 복원할 수 있고, 여기에서 사용한 키 길이에 따라 무차별 대입 공격의 최대 소요 시간이 정해진다. 암호화 키가 n비트일 경우 가능한 값은 최대 {\displaystyle 2^{n}} 2^{n}가지가 존재한다. | ||
2009년 기준으로 128비트 이상의 키는 안전하다고 평가된다. 64비트 이하의 경우 실제 무차별 대입 공격이 성공하였다. 예를 들어, 56비트를 사용하는 DES의 경우 약 하루 안에 전체 키를 대입하는 하드웨어가 1999년에 공개되었다. 64비트 키를 사용하는 RC5의 경우 Distributed.net이라는 분산 컴퓨팅 프로젝트에서 해독한 사례가 있다. | 2009년 기준으로 128비트 이상의 키는 안전하다고 평가된다. 64비트 이하의 경우 실제 무차별 대입 공격이 성공하였다. 예를 들어, 56비트를 사용하는 DES의 경우 약 하루 안에 전체 키를 대입하는 하드웨어가 1999년에 공개되었다. 64비트 키를 사용하는 RC5의 경우 Distributed.net이라는 분산 컴퓨팅 프로젝트에서 해독한 사례가 있다. | ||
| − | 사용자 암호와 같이 암호가 특정 패턴을 이루고 있을 경우에는 대입해야 할 값의 범위를 크게 줄일 수 있다. 이 경우 사전의 단어를 조합하여 대입하는 사전 공격이 사용된다. 그러므로 암호의 패턴을 불규칙적으로 하고 자신의 개인정보와 연계되지 않도록 하는 것이 좋다.<ref> | + | 사용자 암호와 같이 암호가 특정 패턴을 이루고 있을 경우에는 대입해야 할 값의 범위를 크게 줄일 수 있다. 이 경우 사전의 단어를 조합하여 대입하는 사전 공격이 사용된다. 그러므로 암호의 패턴을 불규칙적으로 하고 자신의 개인정보와 연계되지 않도록 하는 것이 좋다.<ref>〈[https://ko.wikipedia.org/wiki/%EB%AC%B4%EC%B0%A8%EB%B3%84_%EB%8C%80%EC%9E%85_%EA%B3%B5%EA%B2%A9 무차별 대입 공격]〉, 《위키백과》</ref> |
====collision 공격==== | ====collision 공격==== | ||
2019년 8월 6일 (화) 13:17 판
레인보우 테이블(rainbow table)은 해시함수(MD-5, SHA-1, SHA-2 등)를 사용하여 만들어낼 수 있는 값들을 대량으로 저장한 표이다. 보통 해시함수를 이용하여 저장된 비밀번호로부터 원래의 비밀번호를 추출해 내는데 사용된다.
목차
개요
레인보우 테이블은 해시 함수(MD5, SHA-1, SHA-2 등)을 사용하여 만들어낼 수 있는 값들을 대량으로 저장한 표이다. 1980년 마틴 헬만에 의해 소개되었고 MD5 암호화가 쉽게 복호화될 수 있다는 것을 보여준 해킹기법 중 하나이다. 하나의 패스워드에서 시작해 변이된 형태의 여러 패스워드를 생성하여 그 패스워드의 해시를 고리처럼 연결해 일정 수의 패스워드와 해시로 이루어진 테이블이다. 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 문제를 푸는 브루트 포스 공격을 뒷받침 해주는 역할을 하기도 하고 해시에서 평문을 추출해내기 위함의 역할도 있다.
특징
해시함수(hash function)
해시함수(hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 한다. 해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one 대응)하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생하게 된다. 아래 그림은 이름-전화번호부를 매핑하기 위한 해시함수를 개념적으로 나타냈다. 해시충돌이 발생할 가능성이 있음에도 해시테이블을 쓰는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리하기 위해서이다. 예컨대 해시함수로 하드디스크나 클라우드에 존재하는 무한에 가까운 데이터(키)들을 유한한 개수의 해시값으로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있게 된다. 색인(index)에 해시값을 사용함으로써 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행할 수 있다. 해시함수는 언제나 동일한 해시값을 리턴하고, 해당 색인만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근할 수 있으며, 색인은 계산이 간단한 함수(상수시간)로 작동하기 때문에 매우 효율적이다. 다시 말해 해시는 데이터 액세스(삽입, 삭제, 탐색)시 계산복잡성을 O(1)을 지향한다. 해시테이블을 다른 자료구조와 비교해보면 이진탐색트리와 그 변형의 경우 메모리를 효율적으로 사용하는 편이지만 데이터 탐색에 소요되는 계산복잡성은 O(logn)입니다. 배열(array)의 경우 데이터 탐색에 따른 계산복잡성은 O(1)이지만, 메모리를 미리 할당해 둬야 하기 때문에 공간 효율적이라고 말하기 어렵다. 해시는 보안 분야에서도 널리 사용된다. 키와 해시값 사이에 직접적인 연관이 없기 때문에 해시값만 가지고는 키를 온전히 복원하기 어렵기 때문이다. 아울러 해시함수는 길이가 서로 다른 입력데이터에 대해 일정한 길이의 출력을 만들 수 있어서 ‘데이터 축약’ 기능도 수행할 수 있다. 다만 현재까지 개발된 거의 모든 해시함수는 해시충돌을 일으키는 것으로 확인됐다. 물론 해시충돌 자체를 줄이는 것도 의미가 있겠다만, 중요한 것은 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 하는 것이다. 극단적으로 위 그림에서 모든 키가 02라는 동일한 해시값으로 매핑이 될 경우 데이터를 액세스할 때 비효율성이 커지고, 보안이 취약(서로 다른 키인데도 동일한 해시값)해져 굳이 해시를 도입해 데이터를 관리할 이유가 없어진다.[1]
활용
레인보우 테이블의 원리
- 레인보우 테이블은 한 개가 아니라 몇 천개로 이뤄져 있다. 이 몇 천개가 생성된 후 진짜 최종 테이블이 생성된다.
- 최종 테이블: 해당 테이블의 최초 패스워드랑 최종 해시값 저장
- 최초 패스워드에서 해시 함수를 이용해 해시 값 생성, 생성된 해시 값 사용하여 R함수로 두번째 확인하고자 하는 패스워드를 생성한다.
- R함수: 앞에서부터 숫자인걸 가져와서 저장하는 식으로 이뤄진다.
- 최종 테이블은 각각의 테이블의 최초 패스워드와 마지막 해시값으로 이뤄진다.[2]
레인보우 테이블을 이용한 공격
공격자의 사전 공격 방법 중 하나이다.
- 레인보우 테이블에 크래킹하려는 해시값과 같은 MD5 해시값이 있는지 확인
- 레인보우 테이블에 크래킹하려는 해시값이 없으면 크래킹할 해시값에 R함수를 적용한다. 패스워드를 구하고 다시 해시값을 구한다.
- 구한 해시값이 레인보우 테이블이 있는지 확인한다.
- 레인보우 테이블에서 확인한 해시값을 발견한 뒤 그 해시값에 해당하는 최초 패스워드를 구한다.
- 확인한 최초 패스워드에서 다시 패스워드와 일치하는 해시값이 나올 때까지 MD5 해시와 R함수를 반복 수행한다. 해당 해시값이 확인 되면 찾는 패스워드는 해당 해시값을 생성한 문자열이다.[3]
종류
패스워드 크래킹
공격 대상이 이미 ID를 알고 있다는 가정 하에 비밀번호를 알아내는 해킹 기법으로 이 기법은 해킹 기법중 난이도는 낮은 편이나 가장 강력한 공격이다.
사전공격(dictionary attack)
원본(평문)에 대해 미리 계산된 해쉬값들을 모아서 사전 형태로 만들어놓고, 대입해보는 공격 방법[4] 사전 공격(Dictionary attack)은 사전에 있는 단어를 입력하여 암호를 알아내거나 해독하는 컴퓨터 공격법이다. 암호를 알아내기 위한 공격은 사전의 단어를 순차적으로 입력하는 것이다. 단어를 그대로 입력할 뿐 아니라, 대문자와 소문자를 뒤섞기도 하고, 단어에 숫자를 첨부하기도 하는 등의 처리도 병행하면서 공격을 할 수 있다. 수십만 개의 단어가 수록되어 있는 사전을 컴퓨터에 자동 처리시킴으로써 짧은 시간 안에 모든 단어를 입력할 수 있기 때문에 사전단어공격은 기본적인 패스워드 탐색의 수법으로 이용된다. 이에 대처하기 위해서는 인명이나 의미가 있는 단어를 패스워드로 쓰지 말아야 하며, 기호나 숫자 등을 랜덤으로 결합시키는 방법을 사용해야 한다. 암호해독의 수법으로 사서공격을 이용하는 경우에는, 사서에 있는 단어나 무작위로 모은 평문(平文)을 모두 암호화하여 이것을 해독하고자 하는 암호에 맞춰보고 일치 여부를 조사하는 방법을 쓴다. 이에 대한 대처법으로는 암호문을 길게 하는 것이 효과적이다. 사전 공격은 미리 만들어진 목록에 의한 공격만 해당하며 드루킹 특검에서처럼 비밀구절(passphrase)에 특정인이 넣을만한 단어들을 추측해서 집어넣는 것은 사전 공격의 범주에 들어가지 않는다는 주장도 있다. 이런 식의 공격은 사전 지식을 이용한 추측(educated guess)을 사용한 공격이다. 이런 educated guess attack은 해커들이 선호하는 공격 중 하나이다. 레인보우 테이블도 사전공격과 비슷한 해킹기술이다.[5]
무차별 대입 공격
무차별 대입 공격(영어: brute force attack)은 특정한 암호를 풀기 위해 가능한 모든 값을 대입하는 것을 의미한다. 대부분의 암호화 방식은 이론적으로 무차별 대입 공격에 대해 안전하지 못하며, 충분한 시간이 존재한다면 암호화된 정보를 해독할 수 있다. 하지만 대부분의 경우 모든 계산을 마치려면 실용적이지 못한 비용이나 시간을 소요하게 되어, 공격을 방지하게 한다. 암호의 '취약점'이라는 의미에는 무차별 대입 공격보다 더 빠른 공격 방법이 존재한다는 것을 의미한다. 대칭키 암호의 경우 암호에 사용된 키를 알아내면 암호화된 정보를 복원할 수 있고, 여기에서 사용한 키 길이에 따라 무차별 대입 공격의 최대 소요 시간이 정해진다. 암호화 키가 n비트일 경우 가능한 값은 최대 {\displaystyle 2^{n}} 2^{n}가지가 존재한다. 2009년 기준으로 128비트 이상의 키는 안전하다고 평가된다. 64비트 이하의 경우 실제 무차별 대입 공격이 성공하였다. 예를 들어, 56비트를 사용하는 DES의 경우 약 하루 안에 전체 키를 대입하는 하드웨어가 1999년에 공개되었다. 64비트 키를 사용하는 RC5의 경우 Distributed.net이라는 분산 컴퓨팅 프로젝트에서 해독한 사례가 있다. 사용자 암호와 같이 암호가 특정 패턴을 이루고 있을 경우에는 대입해야 할 값의 범위를 크게 줄일 수 있다. 이 경우 사전의 단어를 조합하여 대입하는 사전 공격이 사용된다. 그러므로 암호의 패턴을 불규칙적으로 하고 자신의 개인정보와 연계되지 않도록 하는 것이 좋다.[6]
collision 공격
충돌이 발생하는 경우를 공격하는 것으로 해시 함수 특성상 같은 문자의 경우 같은 해시값을 가져 충돌이 발생한다는 것이다. 따라서 해당 해시함수를 통해 무작위로 패스워드를 입력하여 같은 해시 값이 나올때까지 반복하는 것이다. 해당 공격을 방지하기 위해 나온 것이 다양한 해시 함수를 사용하는 것과 salt 기술을 병합하는 것이다. 해당 기술은 앞서 충돌 공격을 방지하기 위한 것으로 같은 패스워드일지라도 패스워드+해시+salt 구조로 인해 해시 값은 다른 결과를 가져온다. 장점은 무작위 공격과 유사하여 100%찾아낸다는 것이고 단점은 현재 보안 정책이나 기술로 인해 현실적으로 불가능에 가깝다.
패스워드 크래킹 툴
- john the ripper: 패스워드 크래킹 툴의 대표적인 툴이다. 앞서 설명한 대부분의 기법들이 포함되어 있다.
- ophcracker: 레인보우 테이블을 통한 크래킹 툴이다.
- cain&abel: 윈도우 GUI기반 도구로 Sniffing과 ARP poisoning과 함께 MITM공격에 주로 사용된다.
- hydra: 네트워크 패스워드 크래킹 툴이다.
- Medusa: 히드라와 유사한 툴이며 히드라에 비해 빠른 속도를 지니고 있다.
- Aircrack:무선 네트워크의 패스워드를 크래킹 하는 툴이다.[7]
방어법
솔티드 해시(Salted hashed)
기존에는 패스워드만 해시함수에 통과시켰으나 최근에는 가입 시간이나 난수를 비밀번호와 같이 해시값에 포함시킨다. 이 때 추가적으로 포함된 가입 시간이나 난수를 솔트(salt)라고 한다. 이는 서로 다른 계정이 같은 비밀번호를 사용하더라고 솔트가 다르면 완전 다른 해시값이 생성되며, 설령 같은 해시값을 같더라 하여도 솔트 값이 전혀 다르기 때문에 평문을 유추하기 힘들다는 논리다. 일방향성이 아닌 암호화/역암호화시 둘다 사용되는(쌍으로 이루어지는) 솔트는, 같은 솔트가 사용되어야 하고 레인보우 테이블에 의한 암호 크랙 공격(사전 공격)을 어느정도 무력화시킬 수 있다.[4]
블룸 필터(Bloom filter)
블룸 필터는 원소가 집합에 속하는지 여부를 검사하는데 사용되는 확률적 자료 구조이다. 즉, 개발자들은 사용자가 회원 가입을 할때 레인보우 테이블에 있는 비밀번호에 대하여 사용을 금지하는 방법을 선택하는데 이러한 과정속에서 금지된 비밀번호를 걸러 내는 역할을 한다. 이 방법을 사용하면 사용자는 취약한 비밀번호의 사용이 금지되어 공격자가 가지고 있는 패스워드 사전도 취약하게 된다. 설령 공격자가 갱신을 한 패스워드 사전을 가지고 있다 하여도 개발자가 해당 사전을 수집할 수 있으므로 금지 비밀번호를 갱신하면 된다.[8]
각주
- ↑ 〈해싱, 해시함수, 해시테이블〉, 《랫츠고 블로그》, 2017-10-25
- ↑ 이해빈,〈패스워드 크래킹〉, 《티스토리》, 2018-01-07
- ↑ 달콤맛마이쮸, 〈유동현〉, 《네이버 블로그》, 2016-09-18
- ↑ 4.0 4.1 차재복, 〈Dictionary Attack 사전 공격〉, 《정보통신기술용어해설》, 2017-12-11
- ↑ 〈사전 공격〉, 《위키백과》
- ↑ 〈무차별 대입 공격〉, 《위키백과》
- ↑ *〈패스워드 크래킹〉, 《티스토리》, 2018-12-12
- ↑ 수니감자, 〈(보안)SALTED HASH / BLOOM FILTER〉, 《티스토리》, 2016-10-23
참고자료
- 달콤맛마이쮸, 〈유동현〉, 《네이버 블로그》, 2016-09-18
- 수니감자, 〈(보안)SALTED HASH / BLOOM FILTER〉, 《티스토리》, 2016-10-23
- 차재복, 〈Dictionary Attack 사전 공격〉, 《정보통신기술용어해설》, 2017-12-11
- 〈사전 공격〉, 《위키백과》
- 〈무차별 대입 공격〉, 《위키백과》
- 〈해싱, 해시함수, 해시테이블〉, 《랫츠고 블로그》, 2017-10-25
- 이해빈,〈패스워드 크래킹〉, 《티스토리》, 2018-01-07
- 〈패스워드 크래킹〉, 《티스토리》, 2018-12-12
같이 보기
| ||||||||||||||||||||||||||
