위키원
"레인보우 테이블"의 두 판 사이의 차이
wlgns12244 (토론 | 기여) |
(→특징) |
||
| (사용자 3명의 중간 판 48개는 보이지 않습니다) | |||
| 2번째 줄: | 2번째 줄: | ||
== 개요 == | == 개요 == | ||
| − | 레인보우 | + | [[레인보우 테이블]]은 [[해시]] 함수(MD5, SHA-1, SHA-2 등)을 사용하여 만들어낼 수 있는 값들을 대량으로 저장한 표이다. |
| − | 1980년 [[마틴 헬만]]에 의해 소개되었고 MD5 암호화가 쉽게 [[복호화]]될 수 있다는 것을 보여준 해킹기법 중 하나이다. 하나의 | + | 1980년 [[마틴 헬만]]에 의해 소개되었고 MD5 암호화가 쉽게 [[복호화]]될 수 있다는 것을 보여준 해킹기법 중 하나이다. 하나의 [[패스워드]]에서 시작해 [[변이]]된 형태의 여러 패스워드를 생성하여 그 패스워드의 해시를 고리처럼 연결해 일정 수의 패스워드와 해시로 이루어진 [[테이블]]이다. 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 문제를 푸는 [[브루트 포스 공격]]을 뒷받침 해주는 역할을 하기도 하고 해시에서 [[평문]]을 추출해내기 위함의 역할도 있다. |
==특징== | ==특징== | ||
| + | 현재 패스워드는 '패스워드 + 해시'를 통해 저장되어 있다. 따라서 패스워드별로 해당 [[해시값]]을 미리 저장한 이후 해당 해시값을 통해 역으로 패스워드를 찾아내는 방식이다. 하지만 해시함수는 다양하며 해당 데이터를 모두 저장한다는 것은 메모리 적으로 많은 부담이 된다. 또한 해당 레인보우 테이블을 만드는 데에도 많은 시간이 소요되며 해시에 대한 알고리즘 수행 시간이 길수록 해당 테이블을 얻어내는 것 역시 아주 어렵다. 또한 레인보우 테이블 특성상 무한적으로 값을 대입하는 방식이기 때문에 작은 테이블도 기본 100[[GB]]가 가뜬히 넘어간다. 거기에 | ||
| + | 영어 대문자+소문자+숫자 조합까지 가기 때문에 용량은 엄청나게 증가하게 된다. 올라가는 것도 [[테라바이트]] 단위로 용량이 커진다. 이러한 특성 때문에 기업,단체에서 주로 사용한다. | ||
| + | 개인이 사용하기엔 자원이 너무나도 많이 들어가고 비용도 엄청나기 때문이다. 이러한 단점을 보완하기 위해 나온 것이 R[[(Reduction)]] 함수이다. R 함수는 레인보우 테이블을 작은 크기로 줄이는 데 사용되며 일정한 [[패턴]]이나 유사한 것들을 이용하여 모든 값을 저장하는 것이 아닌 특정 값만 저장하여 패스워드를 역으로 알아내는 것이다. | ||
| + | *장점 : 해시 함수를 통한 패스워드 [[크래킹]]이 가능하다. | ||
| + | *단점 : 테이블 생성에 많은 시간이 소요된다.<ref name="fdsa">〈[http://wiki.hash.kr/index.php/%ED%8C%A8%EC%8A%A4%EC%9B%8C%EB%93%9C_%ED%81%AC%EB%9E%98%ED%82%B9 패스워드 크래킹]〉,《해시넷》</ref> | ||
| + | |||
| + | 해쉬는 기본적으로 [[역함수]]가 존재하지 않는 함수로 계산해낸다. 즉, [[암호화]]-[[복호화]] 과정이 불가능하다는 말이다. 그래서 사람들이 고안해낸 방법은 수학적으로 아예 역함수가 존재하지 않는 함수 가지고 씨름할 바에 차라리 가능한 모든 경우의 수를 다 써놓고 거기서 찾아내자는 방법이다. 그래서 [[데이터베이스]]와 같은 자료에서 뽑아낸 해쉬값을 레인보우 테이블과 [[대조]]하여 평문을 찾아내는 것이다. | ||
| + | |||
| + | 비밀번호는 대부분 암호화 해시 함수를 사용한 결과 값을 데이터베이스에 저장된다. 해시 함수는 [[일방향 함수]]로 암호화 과정만 있고 복호화 과정이 없는 특징이 있어서 해당 값을 복호화하는 것은 불가능하다. 하지만 공격자가 해시함수에 다양한 값을 입력하여 얻은 해시 값들을 정리해 넣은 테이블인 레인보우 테이블이 있다면 해당 데이터 베이스에서 비밀번호를 알아 낼 수도 있다. 또한 우연하게 같은 비밀번호를 사용하는 사람들이 있다면 데이터 베이스에 저장된 해시 값이 나타나므로 하나의 비밀번호를 크랙하는 동시에 여러 계정이 폭발하는 문제도 발생할 수 있다.<ref> 수니감자,〈[https://ssoonidev.tistory.com/45 패스워드 크래킹]〉, 《티스토리》,2016-10-22</ref> | ||
| + | |||
| + | 브루트 포스 항목에도 나와 있듯이, [[무한적]]으로 대입을 하는 데에는 시간이 엄청나게 걸린다. 10자리 영문 소문자+숫자 조합을 초당 1억번 대입을 한다 하더라도 1년 이상 걸리는데, 해쉬를 계산하느라 초당 [[대입량]]이 적어지면 기간은 더늘어나게 된다. | ||
| + | 이러한 문제를 조금이나마 해결하기 위해 나온 것이 레인보우 테이블이다. 해쉬를 일일히 계산하는 것보다 미리 만들어진 테이블에서 해쉬값만 쏙쏙 뽑아서 집어넣으면 해쉬 계산하는 | ||
| + | 시간이 절약되니 공격 과정을 좀 더 빨리 끝낼 수 있는 것이다. 일종의 사전 공격이다.<ref>〈[https://namu.wiki/w/%EB%A0%88%EC%9D%B8%EB%B3%B4%EC%9A%B0%20%ED%85%8C%EC%9D%B4%EB%B8%94 레인보우 테이블]〉,《나무위키》</ref> | ||
| + | |||
| + | ===패스워드(password)=== | ||
| + | 나 이외에는 그 누구에게도 알려서는 안 되는 비밀의 암호 문자. 영어로는 패스워드(Password) 혹은 [[PIN]] [[패스코드]](passcode)라고 하는 경우도 있다. | ||
| + | 정의를 따지자면, 특정 사용자에 대한 본인 이중 인증성 문자라고 볼 수 있다. 인증이라는 점에서는 아이디도 그런 의미에서 보면 같은 역할을 하고 있다고도 볼 수 있지만, | ||
| + | 아이디는 사용자 자신을 남에게 표현하기 위해 [[필연적]]으로 노출될 수밖에 없기에 사용자 당사자만 아는 암호성 성격을 띤 특수 문자나 문장으로 이중 인증을 함으로서 해당 아이디에 대한 타인의 불법적인 개입을 차단하는 시스템이라고 볼 수 있다. | ||
| + | 아이디가 집 주소라면 비밀번호는 집 열쇠다. 결국 비밀번호는 암호와 비슷한 [[맥락]]이라고 볼 수 있다. | ||
| + | 다만 암호가 특정 메세지를 숨기는 기능도 있으니 활용의 폭은 더 좁다고 할 수 있다.<ref>〈[https://namu.wiki/w/%EB%B9%84%EB%B0%80%EB%B2%88%ED%98%B8 패스워드]〉, 《나무위키》</ref> | ||
| + | |||
| + | ===해시함수(hash function)=== | ||
| + | [[해시함수]](hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 [[매핑]]하는 함수이다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 한다. | ||
| + | 해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one 대응)하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 [[해시충돌]](collision)이 발생하게 된다. 이름-전화번호부를 매핑하기 위한 해시함수를 개념적으로 나타냈다. | ||
| + | 해시충돌이 발생할 가능성이 있음에도 [[해시테이블]]을 쓰는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리하기 위해서이다. 예컨대 해시함수로 [[하드디스크]]나 [[클라우드]]에 존재하는 무한에 가까운 데이터(키)들을 유한한 개수의 해시값으로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있게 된다. | ||
| + | [[색인]](index)에 해시값을 사용함으로써 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행할 수 있다. | ||
| + | 해시함수는 언제나 동일한 해시값을 리턴하고, 해당 색인만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근할 수 있으며, 색인은 계산이 간단한 함수(상수시간)로 작동하기 때문에 매우 효율적이다. 다시 말해 해시는 데이터 [[액세스]](삽입, 삭제, 탐색)시 계산복잡성을 O(1)을 지향한다. | ||
| + | 해시테이블을 다른 자료구조와 비교해보면 [[이진탐색트리]]와 그 변형의 경우 메모리를 효율적으로 사용하는 편이지만 데이터 탐색에 소요되는 [[계산복잡성]]은 O(logn)입니다. 배열(array)의 경우 데이터 탐색에 따른 계산복잡성은 O(1)이지만, 메모리를 미리 할당해 둬야 하기 때문에 공간 효율적이라고 말하기 어렵다. | ||
| + | 해시는 보안 분야에서도 널리 사용된다. 키와 해시값 사이에 직접적인 연관이 없기 때문에 해시값만 가지고는 키를 온전히 복원하기 어렵기 때문이다. 아울러 해시함수는 길이가 서로 다른 입력데이터에 대해 일정한 길이의 출력을 만들 수 있어서 ‘[[데이터 축약]]’ 기능도 수행할 수 있다. | ||
| + | 다만 현재까지 개발된 거의 모든 해시함수는 해시충돌을 일으키는 것으로 확인됐다. 물론 해시충돌 자체를 줄이는 것도 의미가 있겠다만, 중요한 것은 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 하는 것이다. 극단적으로 위 그림에서 모든 키가 02라는 동일한 해시값으로 매핑이 될 경우 데이터를 액세스할 때 비효율성이 커지고, 보안이 취약(서로 다른 키인데도 동일한 해시값)해져 굳이 해시를 도입해 데이터를 관리할 이유가 없어진다.<ref>〈[https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/ 해싱, 해시함수, 해시테이블]〉, 《랫츠고 블로그》, 2017-10-25</ref> | ||
| + | ====MD5==== | ||
| + | [[MD5]](Message-Digest algorithm 5)는 128비트 암호화 해시 함수이다. RFC 1321로 지정되어 있으며, 주로 프로그램이나 파일이 원본 그대로인지를 확인하는 무결성 검사 등에 사용된다. 1991년에 [[로널드 라이베스트]]가 예전에 쓰이던 [[MD4]]를 대체하기 위해 고안했다. | ||
| + | 1996년에 MD5의 설계상 결함이 발견되었다. 이것은 매우 치명적인 결함은 아니었지만, 암호학자들은 해시 용도로 SHA-1과 같이 다른 안전한 [[알고리즘]]을 사용할 것을 권장하기 시작했다. 2004년에는 더욱 심한 암호화 결함이 발견되었고. 2006년에는 노트북 컴퓨터 한 대의 계산 능력으로 1분 내에 해시 충돌을 찾을 정도로 빠른 알고리즘이 발표되기도 하였다. 현재는 MD5 알고리즘을 보안 관련 용도로 쓰는 것은 권장하지 않으며, 심각한 보안 문제를 야기할 수도 있다. 2008년 12월에는 MD5의 결함을 이용해 [[SSL]] 인증서를 변조하는 것이 가능하다는 것이 발표되었다.MD5는 임의의 길이의 메시지(variable-length message)를 입력받아, 128비트짜리 고정 길이의 출력값을 낸다. 입력 메시지는 512 비트 블록들로 쪼개진다. 메시지를 우선 패딩하여 512로 나누어떨어질 수 있는 길이가 되게 한다. [[패딩]]은 다음과 같이 한다: 우선 첫 단일 [[비트]], 1을 메시지 끝부분에 추가한다. 512의 배수의 길이보다 64 비트가 적은 곳까지 0으로 채운다. 나머지 64 비트는 최초의(오리지널) 메시지의 길이를 나타내는 64 [[비트 정수]](integer)값으로 채워진다. | ||
| + | 메인 MD5 알고리즘은 A,B,C,D라고 이름이 붙은 32 비트 워드 네 개로 이루어진 하나의 128 [[비트 스테이트]](state)에 대해 동작한다. A,B,C,D는 소정의 상수값으로 초기화된다. 메인 MD5 알고리즘은 각각의 512 비트짜리 입력 메시지 블록에 대해 차례로 동작한다. 각 512 비트 입력 메시지 블록을 처리하고 나면 128 비트 스테이트(state)의 값이 변하게 된다.<ref>〈[https://ko.wikipedia.org/wiki/MD5 Md5]〉, 《위키백과》</ref> | ||
| + | |||
| + | ====SHA-1==== | ||
| + | [[SHA]]는 Secure Hash Algorithm의 줄임말로 1993년 미국 국가안보국([[NSA]])에 의해 설계되고 표준으로 지정되었다. | ||
| + | 이때 출간된 SHA는 구분상 SHA-0이라하고 2년 뒤인 1995년에 개정된 SHA-1을 발표했고 현재 널리 쓰이는 해쉬 알고리즘이다. | ||
| + | SHA-1은 메시지 길이에 상관없이 512비트씩 잘라서 메시지 다이제스트 함수를 돌린 뒤 160비트의 출력을 낸다. | ||
| + | 메시지 길이가 512비트의 배수가 아닐 경우 패딩을 하는데 패딩은 맨 뒤 64비트에는 메시지 전체 길이를 넣고 | ||
| + | 나머지 비트는 최상위 비트 1을 제외하고 0으로 채운다. | ||
| + | 메시지가 512비트보다 길 경우 다음 번 메시지 다이제스트 함수의 입력으로 전 함수의 출력을 받는다. 주요 처리에는 | ||
| + | 패딩 처리,메세지 길이를 512 비트 단위(입력 블록 상한)로 잘라서 512 비트의 정수배로 처리, 입력 블록 단위의 처리(32 비트 x 80개 값(W0~W79)을 계산),블록 처리등을 한다. <ref>〈[http://www.ktword.co.kr/word/abbr_view.php?m_temp1=2941 SHA, SHA-1, SHA1]〉, 《정보통신기술용어해설》 | ||
| + | </ref> | ||
| + | |||
| + | ====SHA-2==== | ||
| + | [[SHA-2]] (Secure Hash Algorithm 2)는 미국 국가안보국(NSA)가 설계한 암호화 해시 함수들의 집합이다. 암호 해시 함수는 디지털 데이터 상에서 수학적으로 동작하며 알려져 있고 예측된 해시값에 대해 계산된 해시(알고리즘의 실행 출력)를 비교함으로써 사람이 데이터의 무결성을 파악할 수 있게 된다. 이를테면 다운로드한 파일의 해시를 계산한 다음 이전에 게시한 해시 결과물의 결과와 비교하면 다운로드한 파일이 수정 또는 조작되었는지 알 수 있다. 암호 해시 함수의 주요 개념은 충돌 회피이다. 즉, 누구도 동일한 해시 출력 결과가 있는 두 개의 다른 입력값을 알아낼 수 없다. | ||
| + | SHA-2는 전작 SHA-1으로부터 상당한 변경사항을 포함하고 있다. SHA-2 계열은 224, 256, 384, 512비트로 된 [[다이제스트]](해시값)이 있는 6개의 해시 함수를 구성하고 있다: SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256<ref>〈[https://ko.wikipedia.org/wiki/SHA-2 SHA-2]〉, 《위키백과》</ref> | ||
==활용== | ==활용== | ||
| + | ===레인보우 테이블의 원리=== | ||
| + | * 레인보우 테이블은 한 개가 아니라 몇 천개로 이뤄져 있다. 이 몇 천개가 생성된 후 진짜 최종 테이블이 생성된다. | ||
| + | * 최종 테이블: 해당 테이블의 최초 패스워드랑 최종 해시값을 저장한다. | ||
| + | * 최초 패스워드에서 해시 함수를 이용해 해시 값 생성, 생성된 해시 값 사용하여 R함수로 두번째 확인하고자 하는 패스워드를 생성한다. | ||
| + | * [[R함수]]: 앞에서부터 숫자인걸 가져와서 저장하는 식으로 이뤄진다. | ||
| + | * 최종 테이블은 각각의 테이블의 최초 패스워드와 마지막 해시값으로 이뤄진다. | ||
| + | |||
| + | ===패스워드를 찾는 방법=== | ||
| + | # 현재 해시값이 최종 테이블에 있는지 확인한다. | ||
| + | # 없으면 해시값을 R함수로 추출한다.-> 31945 | ||
| + | # 추출해낸 패스워드 기준으로 해시값을 생성한다. -> F55078E976DF9B3214D3F222 | ||
| + | # 생성한 해시값이 최종 테이블에 있는지 확인한다. | ||
| + | # 생성한 해시값이 최종 테이블에 있으면 최종 테이블에서 생성한 해시값에 해당하는 패스워드가 최초 패스워드인 테이블로 이동한다. | ||
| + | # 이동한 테이블에 찾고자 하는 해시값에 대한 패스워드가 있는 것을 확인한다.-> 38059 <ref>이해빈,〈[https://xn--ex3bt1ov9l.kr/163 패스워드 크래킹]〉, 《티스토리》, 2018-01-07</ref> | ||
| + | |||
=== 레인보우 테이블을 이용한 공격 === | === 레인보우 테이블을 이용한 공격 === | ||
| − | 공격자의 사전 공격 방법 중 하나이다. | + | 만약에 해시 알고리즘을 엄청나게 복잡하게 만들어서 오래 걸리게 하면 [[brute force]] 공격으로부터 안전해지지 않을까? |
| + | 이를테면 SHA-512의 경우는 앞서의 공격으로도 초당 364000개 밖에 대입하지 못한다. 물론 이것도 엄청나지만 | ||
| + | 앞서의 8자리 영문자 숫자 조합의 경우 7만년 쯤 걸린다. 이 정도면 안전하지 않을까? | ||
| + | 그렇지 않다. Brute force attack을 생각해보면 더 좋은 방법을 생각해낼 수 있다. 미리 가능한 패스워드 조합을 다 계산한 테이블을 가지고 비교만 수행하는 것이다. | ||
| + | 이것이 [[사전 공격]]인데, 이 [[dictionary]]를 해시값 검색에 최적화시킨 것을 레인보우테이블이라고 한다. MD5의 경우는 인터넷에 이미 수백억 개의 해시값에 대한 레인보우테이블이 있다. | ||
| + | 이미 계산된 값을 이용하므로 알고리즘의 복잡도도 큰 상관이 없다. 이 안에 있는 패스워드는 그냥 금방 뚫리는 것이다. 공개된 MD5 레인보우테이블로 찾으면 대부분의 웹사이트에서 90% 정도의 사용자 패스워드가 크랙된다고 하니 이쯤되면 md5는 이미 뚫려 있게 되는것이다. | ||
| + | 물론 레인보우테이블을 만드는데도 시간이 많이 들기 때문에 알고리즘의 복잡도가 전혀 상관이 없는 것은 아니다. 알고리즘 수행시간이 길면 충분한 규모의 레인보우테이블을 확보하기도 어렵다. 그렇치만 쉬운 패스워드의 경우 쉽게 뚫릴 수 있으므로 보안성을 크게 높일 수 있다고 말하긴 어렵다.<ref>박영록,〈[http://www.codeok.net/%ED%8C%A8%EC%8A%A4%EC%9B%8C%EB%93%9C%20%EB%B3%B4%EC%95%88%EC%9D%98%20%EA%B8%B0%EC%88%A0 패스워드 보안의 기술]〉,《코드오케이넷》</ref> 레인보우 테이블은 공격자의 사전 공격 방법 중 하나이다. | ||
# 레인보우 테이블에 크래킹하려는 해시값과 같은 MD5 해시값이 있는지 확인 | # 레인보우 테이블에 크래킹하려는 해시값과 같은 MD5 해시값이 있는지 확인 | ||
# 레인보우 테이블에 크래킹하려는 해시값이 없으면 크래킹할 해시값에 R함수를 적용한다. 패스워드를 구하고 다시 해시값을 구한다. | # 레인보우 테이블에 크래킹하려는 해시값이 없으면 크래킹할 해시값에 R함수를 적용한다. 패스워드를 구하고 다시 해시값을 구한다. | ||
# 구한 해시값이 레인보우 테이블이 있는지 확인한다. | # 구한 해시값이 레인보우 테이블이 있는지 확인한다. | ||
# 레인보우 테이블에서 확인한 해시값을 발견한 뒤 그 해시값에 해당하는 최초 패스워드를 구한다. | # 레인보우 테이블에서 확인한 해시값을 발견한 뒤 그 해시값에 해당하는 최초 패스워드를 구한다. | ||
| − | # 확인한 최초 패스워드에서 다시 패스워드와 일치하는 해시값이 나올 때까지 MD5 해시와 R함수를 반복 수행한다. 해당 해시값이 확인 되면 찾는 패스워드는 해당 해시값을 생성한 | + | # 확인한 최초 패스워드에서 다시 패스워드와 일치하는 해시값이 나올 때까지 MD5 해시와 R함수를 반복 수행한다. 해당 해시값이 확인 되면 찾는 패스워드는 해당 해시값을 생성한 [[문자열]]이다.<ref>달콤맛마이쮸, 〈[https://dalkom7.tistory.com/12 유동현]〉, 《네이버 블로그》, 2016-09-18</ref> |
| − | |||
== 종류 == | == 종류 == | ||
===패스워드 크래킹=== | ===패스워드 크래킹=== | ||
| + | [[패스워드 크래킹]]은 네트워크 컴퓨터 시스템에 의해 전송된 저장 위치로부터 또는 [[데이터]]로부터 패스워드를 복구하는 것을 포함한다. 패스워드 크래킹의 목적은 컴퓨터 시스템에 무단 접근을 통해 권한을 얻거나 잊어버린 암호를 복구하기 위해 사용한다. 해커가 시스템을 [[해킹]]할 수 있도록 테스트 암호 강도를 위한 기술은 크래킹 암호를 사용하는 또 다른 이유가 될 수 있다. 일반적으로 반복적 작업이나 일정한 [[패턴]], 조합 등을 통해 알아내기도 한다. 패스워드 크래킹은 해킹 기법 중 난이도는 낮지만 가장 강력한 공격이다. 또한 보안 프로그램이 설치되어 있어도 얼마든지 [[크래킹]]이 가능하다.<ref name="fdsa"></ref> | ||
| + | |||
====사전공격(dictionary attack)==== | ====사전공격(dictionary attack)==== | ||
원본(평문)에 대해 미리 계산된 해쉬값들을 모아서 사전 형태로 만들어놓고, 대입해보는 공격 방법<ref name="fd">차재복, 〈[http://www.ktword.co.kr/word/abbr_view.php?m_temp1=5739 Dictionary Attack 사전 공격]〉, 《정보통신기술용어해설》, 2017-12-11</ref> | 원본(평문)에 대해 미리 계산된 해쉬값들을 모아서 사전 형태로 만들어놓고, 대입해보는 공격 방법<ref name="fd">차재복, 〈[http://www.ktword.co.kr/word/abbr_view.php?m_temp1=5739 Dictionary Attack 사전 공격]〉, 《정보통신기술용어해설》, 2017-12-11</ref> | ||
| − | 사전 공격(Dictionary attack)은 사전에 있는 단어를 입력하여 암호를 알아내거나 해독하는 컴퓨터 공격법이다. 암호를 알아내기 위한 공격은 사전의 단어를 순차적으로 입력하는 것이다. 단어를 그대로 입력할 뿐 아니라, 대문자와 소문자를 뒤섞기도 하고, 단어에 숫자를 첨부하기도 하는 등의 처리도 병행하면서 공격을 할 수 있다. | + | [[사전 공격]](Dictionary attack)은 사전에 있는 단어를 입력하여 암호를 알아내거나 해독하는 컴퓨터 공격법이다. 암호를 알아내기 위한 공격은 사전의 단어를 순차적으로 입력하는 것이다. 단어를 그대로 입력할 뿐 아니라, 대문자와 소문자를 뒤섞기도 하고, 단어에 숫자를 첨부하기도 하는 등의 처리도 병행하면서 공격을 할 수 있다. |
수십만 개의 단어가 수록되어 있는 사전을 컴퓨터에 자동 처리시킴으로써 짧은 시간 안에 모든 단어를 입력할 수 있기 때문에 사전단어공격은 기본적인 패스워드 탐색의 수법으로 이용된다. 이에 대처하기 위해서는 인명이나 의미가 있는 단어를 패스워드로 쓰지 말아야 하며, 기호나 숫자 등을 랜덤으로 결합시키는 방법을 사용해야 한다. | 수십만 개의 단어가 수록되어 있는 사전을 컴퓨터에 자동 처리시킴으로써 짧은 시간 안에 모든 단어를 입력할 수 있기 때문에 사전단어공격은 기본적인 패스워드 탐색의 수법으로 이용된다. 이에 대처하기 위해서는 인명이나 의미가 있는 단어를 패스워드로 쓰지 말아야 하며, 기호나 숫자 등을 랜덤으로 결합시키는 방법을 사용해야 한다. | ||
| − | 암호해독의 수법으로 사서공격을 이용하는 경우에는, 사서에 있는 단어나 무작위로 모은 평문(平文)을 모두 암호화하여 이것을 해독하고자 하는 암호에 맞춰보고 일치 여부를 조사하는 방법을 쓴다. 이에 대한 대처법으로는 암호문을 길게 하는 것이 효과적이다. | + | 암호해독의 수법으로 사서공격을 이용하는 경우에는, 사서에 있는 단어나 무작위로 모은 [[평문]](平文)을 모두 암호화하여 이것을 해독하고자 하는 암호에 맞춰보고 일치 여부를 조사하는 방법을 쓴다. 이에 대한 대처법으로는 암호문을 길게 하는 것이 효과적이다. |
| − | 사전 공격은 미리 만들어진 목록에 의한 공격만 해당하며 드루킹 특검에서처럼 비밀구절(passphrase)에 | + | 사전 공격은 미리 만들어진 목록에 의한 공격만 해당하며 [[드루킹]] 특검에서처럼 [[비밀구절]](passphrase)에 [[특정인]]이 넣을만한 단어들을 추측해서 집어넣는 것은 사전 공격의 범주에 들어가지 않는다는 주장도 있다. 이런 식의 공격은 사전 지식을 이용한 추측(educated guess)을 사용한 공격이다. 이런 educated guess attack은 해커들이 선호하는 공격 중 하나이다. 레인보우 테이블도 사전공격과 비슷한 해킹기술이다.<ref>〈[https://ko.wikipedia.org/wiki/%EC%82%AC%EC%A0%84_%EA%B3%B5%EA%B2%A9 사전 공격]〉, 《위키백과》</ref> |
| − | ====무차별 대입 공격==== | + | |
| − | 무차별 대입 공격(영어: brute force attack)은 특정한 암호를 풀기 위해 가능한 모든 값을 대입하는 것을 의미한다. 대부분의 암호화 방식은 이론적으로 무차별 대입 공격에 대해 안전하지 못하며, 충분한 시간이 존재한다면 암호화된 정보를 해독할 수 있다. 하지만 대부분의 경우 모든 계산을 마치려면 실용적이지 못한 비용이나 시간을 소요하게 되어, 공격을 방지하게 한다. 암호의 '취약점'이라는 의미에는 무차별 대입 공격보다 더 빠른 공격 방법이 존재한다는 것을 의미한다. | + | ====무차별 대입 공격(Brute Force Attack)==== |
| − | 대칭키 암호의 경우 암호에 사용된 | + | [[무차별 대입 공격]](영어: brute force attack)은 특정한 암호를 풀기 위해 가능한 모든 값을 대입하는 것을 의미한다. 대부분의 암호화 방식은 이론적으로 무차별 대입 공격에 대해 안전하지 못하며, 충분한 시간이 존재한다면 암호화된 정보를 해독할 수 있다. 하지만 대부분의 경우 모든 계산을 마치려면 실용적이지 못한 비용이나 시간을 소요하게 되어, 공격을 방지하게 한다. 암호의 '취약점'이라는 의미에는 무차별 대입 공격보다 더 빠른 공격 방법이 존재한다는 것을 의미한다. |
| − | 2009년 기준으로 128비트 이상의 키는 안전하다고 평가된다. | + | 대칭키 암호의 경우 암호에 사용된 [[키]]를 알아내면 암호화된 정보를 복원할 수 있고, 여기에서 사용한 키 길이에 따라 무차별 대입 공격의 최대 소요 시간이 정해진다. 암호화 키가 n비트일 경우 가능한 값은 최대 {\displaystyle 2^{n}} 2^{n}가지가 존재한다. |
| − | 사용자 암호와 같이 암호가 특정 패턴을 이루고 있을 경우에는 대입해야 할 값의 범위를 크게 줄일 수 있다. 이 경우 사전의 단어를 조합하여 대입하는 사전 공격이 사용된다. 그러므로 암호의 패턴을 불규칙적으로 하고 자신의 개인정보와 연계되지 않도록 하는 것이 좋다.<ref> | + | 2009년 기준으로 128비트 이상의 키는 안전하다고 평가된다. 64[[비트]] 이하의 경우 실제 무차별 대입 공격이 성공하였다. 예를 들어, 56비트를 사용하는 DES의 경우 약 하루 안에 전체 키를 대입하는 하드웨어가 1999년에 공개되었다. 64비트 키를 사용하는 RC5의 경우 Distributed.net이라는 분산 컴퓨팅 프로젝트에서 해독한 사례가 있다. |
| + | 사용자 암호와 같이 암호가 특정 패턴을 이루고 있을 경우에는 대입해야 할 값의 범위를 크게 줄일 수 있다. 이 경우 사전의 단어를 조합하여 대입하는 사전 공격이 사용된다. 그러므로 암호의 패턴을 불규칙적으로 하고 자신의 개인정보와 연계되지 않도록 하는 것이 좋다.<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 공격==== | ||
| + | 충돌이 발생하는 경우를 공격하는 것으로 해시 함수 특성상 같은 문자의 경우 같은 해시값을 가져 충돌이 발생한다는 것이다. 따라서 해당 해시함수를 통해 무작위로 패스워드를 입력하여 같은 해시 값이 나올때까지 반복하는 것이다. 해당 공격을 방지하기 위해 나온 것이 다양한 해시 함수를 사용하는 것과 [[salt]] 기술을 병합하는 것이다. 해당 기술은 앞서 충돌 공격을 방지하기 위한 것으로 같은 패스워드일지라도 패스워드+해시+salt 구조로 인해 해시 값은 다른 결과를 가져온다. | ||
| + | 장점은 무작위 공격과 유사하여 100%찾아낸다는 것이고 단점은 현재 보안 정책이나 기술로 인해 현실적으로 불가능에 가깝다. | ||
| + | |||
| + | ====사회공학적 공격(Guessing Attack)==== | ||
| + | [[사회공학적]] 공격이란 해당 사용자가 인적사항이나 행동, 실수 등을 통해 패스워드를 알아내는 것이다. 직업이나 환경, 공동체 내의 공통적인 암호 등을 통해 유추해내어 패스워드를 알아내는 것이다. 현재 암호화가 강화되어 위에 기술된 방법을 통해 찾는 것은 많은 시간이 걸려 상황에 따라 비효율적일 수 있으며 찾지 못하는 경우도 있으나 짧은 시간에 찾을 수 있다는 장점이 있다.<ref name="fdsa"></ref> | ||
| + | |||
| + | ====패스워드 크래킹 툴==== | ||
| + | *john the ripper: 패스워드 크래킹 툴의 대표적인 툴이다. 앞서 설명한 대부분의 기법들이 포함되어 있다. | ||
| + | *ophcracker: 레인보우 테이블을 통한 크래킹 툴이다. | ||
| + | *cain&abel: 윈도우 GUI기반 도구로 Sniffing과 ARP poisoning과 함께 MITM공격에 주로 사용된다. | ||
| + | *hydra: 네트워크 패스워드 크래킹 툴이다. | ||
| + | *Medusa: 히드라와 유사한 툴이며 히드라에 비해 빠른 속도를 지니고 있다. | ||
| + | *Aircrack:무선 네트워크의 패스워드를 크래킹 하는 툴이다.<ref>〈[https://goodplayer.tistory.com/23 패스워드 크래킹]〉, 《티스토리》, 2018-12-12</ref> | ||
| + | |||
| + | == 방어법 == | ||
| + | 길이가 짧거나 단순 조합에 의한 패스워드, 반복적인 단어나 특정 단어에 의한 패스워드, 유추가 가능하거나 많은 사람이 사용할만한 패스워드는 패스워드 크래킹 공격에 취약하므로 사용을 자제 해야한다. 따라서 안전한 패스워드는 몇 가지로 정리 할 수 있다. | ||
| + | # 적절한 [[알고리즘]] 사용(PBKDF2, Bcrypt, Scrypt 등) | ||
| + | # 길이 및 다양한 조합의 패스워드 설정(영문, 숫자, 특수문자 조합 등) | ||
| + | # 패스워드를 암호화할 때 해시값의 반복을 통해 암호화를 극대화해주는 [[키 스트레칭]] | ||
| + | # 일정시간 반복된 로그인 실패 차단 | ||
| + | # 정해진 로그인 실패 회수 초과시 계정 잠금 | ||
| + | # 2-factor 인증 | ||
| + | # [[otp]]사용 | ||
| + | # 패스워드 저장시 암호화 | ||
| + | 패스워드 크래킹의 경우 해킹에 있어 필수적인 요소이며, 사용자의 입장에서 본인을 인증하기에 필수적인 요소이다. 해커에 의해 패스워드가 탈취당할 수 있지만, 대부분 해킹의 경우 사용자나 관리자의 부주의나 안일한 태도로 인해 대부분 발생하기 때문에 조금의 보안 의식을 가지고 책임감을 느낀다면 많은 사고가 발생하지 않을 것이다.<ref name="fdsa"></ref> | ||
| − | |||
=== 솔티드 해시(Salted hashed) === | === 솔티드 해시(Salted hashed) === | ||
기존에는 패스워드만 해시함수에 통과시켰으나 최근에는 가입 시간이나 난수를 비밀번호와 같이 해시값에 포함시킨다. 이 때 추가적으로 포함된 가입 시간이나 난수를 솔트(salt)라고 한다. 이는 서로 다른 계정이 같은 비밀번호를 사용하더라고 솔트가 다르면 완전 다른 해시값이 생성되며, 설령 같은 해시값을 같더라 하여도 솔트 값이 전혀 다르기 때문에 평문을 유추하기 힘들다는 논리다. 일방향성이 아닌 암호화/역암호화시 둘다 사용되는(쌍으로 이루어지는) 솔트는, 같은 솔트가 사용되어야 하고 레인보우 테이블에 의한 암호 크랙 공격(사전 공격)을 어느정도 무력화시킬 수 있다.<ref name="fd"></ref> | 기존에는 패스워드만 해시함수에 통과시켰으나 최근에는 가입 시간이나 난수를 비밀번호와 같이 해시값에 포함시킨다. 이 때 추가적으로 포함된 가입 시간이나 난수를 솔트(salt)라고 한다. 이는 서로 다른 계정이 같은 비밀번호를 사용하더라고 솔트가 다르면 완전 다른 해시값이 생성되며, 설령 같은 해시값을 같더라 하여도 솔트 값이 전혀 다르기 때문에 평문을 유추하기 힘들다는 논리다. 일방향성이 아닌 암호화/역암호화시 둘다 사용되는(쌍으로 이루어지는) 솔트는, 같은 솔트가 사용되어야 하고 레인보우 테이블에 의한 암호 크랙 공격(사전 공격)을 어느정도 무력화시킬 수 있다.<ref name="fd"></ref> | ||
=== 블룸 필터(Bloom filter) === | === 블룸 필터(Bloom filter) === | ||
| − | 블룸 | + | [[블룸 필터]]는 원소가 집합에 속하는지 여부를 검사하는데 사용되는 [[확률적]] 자료 구조이다. 즉, 개발자들은 사용자가 회원 가입을 할때 레인보우 테이블에 있는 비밀번호에 대하여 사용을 금지하는 방법을 선택하는데 이러한 과정속에서 금지된 비밀번호를 걸러 내는 역할을 한다. 이 방법을 사용하면 사용자는 취약한 비밀번호의 사용이 금지되어 공격자가 가지고 있는 패스워드 사전도 취약하게 된다. 설령 공격자가 갱신을 한 패스워드 사전을 가지고 있다 하여도 개발자가 해당 사전을 수집할 수 있으므로 금지 비밀번호를 갱신하면 된다.<ref>수니감자, 〈[https://ssoonidev.tistory.com/46 (보안)SALTED HASH / BLOOM FILTER]〉, 《티스토리》, 2016-10-23</ref> |
{{각주}} | {{각주}} | ||
== 참고자료 == | == 참고자료 == | ||
| − | * 달콤맛마이쮸, | + | * 달콤맛마이쮸, 〈[https://dalkom7.tistory.com/12 유동현]〉, 《네이버 블로그》, 2016-09-18 |
* 수니감자, 〈[https://ssoonidev.tistory.com/46 (보안)SALTED HASH / BLOOM FILTER]〉, 《티스토리》, 2016-10-23 | * 수니감자, 〈[https://ssoonidev.tistory.com/46 (보안)SALTED HASH / BLOOM FILTER]〉, 《티스토리》, 2016-10-23 | ||
* 차재복, 〈[http://www.ktword.co.kr/word/abbr_view.php?m_temp1=5739 Dictionary Attack 사전 공격]〉, 《정보통신기술용어해설》, 2017-12-11 | * 차재복, 〈[http://www.ktword.co.kr/word/abbr_view.php?m_temp1=5739 Dictionary Attack 사전 공격]〉, 《정보통신기술용어해설》, 2017-12-11 | ||
*〈[https://ko.wikipedia.org/wiki/%EC%82%AC%EC%A0%84_%EA%B3%B5%EA%B2%A9 사전 공격]〉, 《위키백과》 | *〈[https://ko.wikipedia.org/wiki/%EC%82%AC%EC%A0%84_%EA%B3%B5%EA%B2%A9 사전 공격]〉, 《위키백과》 | ||
*〈[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 무차별 대입 공격]〉, 《위키백과》 | *〈[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 무차별 대입 공격]〉, 《위키백과》 | ||
| − | + | *〈[https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/ 해싱, 해시함수, 해시테이블]〉, 《랫츠고 블로그》, 2017-10-25 | |
| − | + | * 이해빈,〈[https://xn--ex3bt1ov9l.kr/163 패스워드 크래킹]〉, 《티스토리》, 2018-01-07 | |
| − | + | *〈[https://goodplayer.tistory.com/23 패스워드 크래킹]〉, 《티스토리》, 2018-12-12 | |
| − | + | *〈[https://namu.wiki/w/%EB%B9%84%EB%B0%80%EB%B2%88%ED%98%B8 패스워드]〉, 《나무위키》 | |
| − | + | *〈[https://ko.wikipedia.org/wiki/MD5 Md5]〉, 《위키백과》 | |
| + | *〈[http://www.ktword.co.kr/word/abbr_view.php?m_temp1=2941 SHA, SHA-1, SHA1]〉, 《정보통신기술용어해설》 | ||
| + | *〈[https://ko.wikipedia.org/wiki/SHA-2 SHA-2]〉, 《위키백과》 | ||
| + | * 수니감자,〈[https://ssoonidev.tistory.com/45 패스워드 크래킹]〉,《티스토리》,2016-10-22 | ||
| + | *〈[http://wiki.hash.kr/index.php/%ED%8C%A8%EC%8A%A4%EC%9B%8C%EB%93%9C_%ED%81%AC%EB%9E%98%ED%82%B9 패스워드 크래킹]〉,《해시넷》 | ||
| + | *〈[https://namu.wiki/w/%EB%A0%88%EC%9D%B8%EB%B3%B4%EC%9A%B0%20%ED%85%8C%EC%9D%B4%EB%B8%94 레인보우 테이블]〉,《나무위키》 | ||
| + | * 박영록,〈[http://www.codeok.net/%ED%8C%A8%EC%8A%A4%EC%9B%8C%EB%93%9C%20%EB%B3%B4%EC%95%88%EC%9D%98%20%EA%B8%B0%EC%88%A0 패스워드 보안의 기술]〉,《코드오케이넷》 | ||
== 같이 보기 == | == 같이 보기 == | ||
2022년 8월 25일 (목) 10:21 기준 최신판
레인보우 테이블(rainbow table)은 해시함수(MD-5, SHA-1, SHA-2 등)를 사용하여 만들어낼 수 있는 값들을 대량으로 저장한 표이다. 보통 해시함수를 이용하여 저장된 비밀번호로부터 원래의 비밀번호를 추출해 내는데 사용된다.
개요[편집]
레인보우 테이블은 해시 함수(MD5, SHA-1, SHA-2 등)을 사용하여 만들어낼 수 있는 값들을 대량으로 저장한 표이다. 1980년 마틴 헬만에 의해 소개되었고 MD5 암호화가 쉽게 복호화될 수 있다는 것을 보여준 해킹기법 중 하나이다. 하나의 패스워드에서 시작해 변이된 형태의 여러 패스워드를 생성하여 그 패스워드의 해시를 고리처럼 연결해 일정 수의 패스워드와 해시로 이루어진 테이블이다. 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 문제를 푸는 브루트 포스 공격을 뒷받침 해주는 역할을 하기도 하고 해시에서 평문을 추출해내기 위함의 역할도 있다.
특징[편집]
현재 패스워드는 '패스워드 + 해시'를 통해 저장되어 있다. 따라서 패스워드별로 해당 해시값을 미리 저장한 이후 해당 해시값을 통해 역으로 패스워드를 찾아내는 방식이다. 하지만 해시함수는 다양하며 해당 데이터를 모두 저장한다는 것은 메모리 적으로 많은 부담이 된다. 또한 해당 레인보우 테이블을 만드는 데에도 많은 시간이 소요되며 해시에 대한 알고리즘 수행 시간이 길수록 해당 테이블을 얻어내는 것 역시 아주 어렵다. 또한 레인보우 테이블 특성상 무한적으로 값을 대입하는 방식이기 때문에 작은 테이블도 기본 100GB가 가뜬히 넘어간다. 거기에 영어 대문자+소문자+숫자 조합까지 가기 때문에 용량은 엄청나게 증가하게 된다. 올라가는 것도 테라바이트 단위로 용량이 커진다. 이러한 특성 때문에 기업,단체에서 주로 사용한다. 개인이 사용하기엔 자원이 너무나도 많이 들어가고 비용도 엄청나기 때문이다. 이러한 단점을 보완하기 위해 나온 것이 R(Reduction) 함수이다. R 함수는 레인보우 테이블을 작은 크기로 줄이는 데 사용되며 일정한 패턴이나 유사한 것들을 이용하여 모든 값을 저장하는 것이 아닌 특정 값만 저장하여 패스워드를 역으로 알아내는 것이다.
해쉬는 기본적으로 역함수가 존재하지 않는 함수로 계산해낸다. 즉, 암호화-복호화 과정이 불가능하다는 말이다. 그래서 사람들이 고안해낸 방법은 수학적으로 아예 역함수가 존재하지 않는 함수 가지고 씨름할 바에 차라리 가능한 모든 경우의 수를 다 써놓고 거기서 찾아내자는 방법이다. 그래서 데이터베이스와 같은 자료에서 뽑아낸 해쉬값을 레인보우 테이블과 대조하여 평문을 찾아내는 것이다.
비밀번호는 대부분 암호화 해시 함수를 사용한 결과 값을 데이터베이스에 저장된다. 해시 함수는 일방향 함수로 암호화 과정만 있고 복호화 과정이 없는 특징이 있어서 해당 값을 복호화하는 것은 불가능하다. 하지만 공격자가 해시함수에 다양한 값을 입력하여 얻은 해시 값들을 정리해 넣은 테이블인 레인보우 테이블이 있다면 해당 데이터 베이스에서 비밀번호를 알아 낼 수도 있다. 또한 우연하게 같은 비밀번호를 사용하는 사람들이 있다면 데이터 베이스에 저장된 해시 값이 나타나므로 하나의 비밀번호를 크랙하는 동시에 여러 계정이 폭발하는 문제도 발생할 수 있다.[2]
브루트 포스 항목에도 나와 있듯이, 무한적으로 대입을 하는 데에는 시간이 엄청나게 걸린다. 10자리 영문 소문자+숫자 조합을 초당 1억번 대입을 한다 하더라도 1년 이상 걸리는데, 해쉬를 계산하느라 초당 대입량이 적어지면 기간은 더늘어나게 된다. 이러한 문제를 조금이나마 해결하기 위해 나온 것이 레인보우 테이블이다. 해쉬를 일일히 계산하는 것보다 미리 만들어진 테이블에서 해쉬값만 쏙쏙 뽑아서 집어넣으면 해쉬 계산하는 시간이 절약되니 공격 과정을 좀 더 빨리 끝낼 수 있는 것이다. 일종의 사전 공격이다.[3]
패스워드(password)[편집]
나 이외에는 그 누구에게도 알려서는 안 되는 비밀의 암호 문자. 영어로는 패스워드(Password) 혹은 PIN 패스코드(passcode)라고 하는 경우도 있다. 정의를 따지자면, 특정 사용자에 대한 본인 이중 인증성 문자라고 볼 수 있다. 인증이라는 점에서는 아이디도 그런 의미에서 보면 같은 역할을 하고 있다고도 볼 수 있지만, 아이디는 사용자 자신을 남에게 표현하기 위해 필연적으로 노출될 수밖에 없기에 사용자 당사자만 아는 암호성 성격을 띤 특수 문자나 문장으로 이중 인증을 함으로서 해당 아이디에 대한 타인의 불법적인 개입을 차단하는 시스템이라고 볼 수 있다. 아이디가 집 주소라면 비밀번호는 집 열쇠다. 결국 비밀번호는 암호와 비슷한 맥락이라고 볼 수 있다. 다만 암호가 특정 메세지를 숨기는 기능도 있으니 활용의 폭은 더 좁다고 할 수 있다.[4]
해시함수(hash function)[편집]
해시함수(hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 한다. 해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one 대응)하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생하게 된다. 이름-전화번호부를 매핑하기 위한 해시함수를 개념적으로 나타냈다. 해시충돌이 발생할 가능성이 있음에도 해시테이블을 쓰는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리하기 위해서이다. 예컨대 해시함수로 하드디스크나 클라우드에 존재하는 무한에 가까운 데이터(키)들을 유한한 개수의 해시값으로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있게 된다. 색인(index)에 해시값을 사용함으로써 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행할 수 있다. 해시함수는 언제나 동일한 해시값을 리턴하고, 해당 색인만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근할 수 있으며, 색인은 계산이 간단한 함수(상수시간)로 작동하기 때문에 매우 효율적이다. 다시 말해 해시는 데이터 액세스(삽입, 삭제, 탐색)시 계산복잡성을 O(1)을 지향한다. 해시테이블을 다른 자료구조와 비교해보면 이진탐색트리와 그 변형의 경우 메모리를 효율적으로 사용하는 편이지만 데이터 탐색에 소요되는 계산복잡성은 O(logn)입니다. 배열(array)의 경우 데이터 탐색에 따른 계산복잡성은 O(1)이지만, 메모리를 미리 할당해 둬야 하기 때문에 공간 효율적이라고 말하기 어렵다. 해시는 보안 분야에서도 널리 사용된다. 키와 해시값 사이에 직접적인 연관이 없기 때문에 해시값만 가지고는 키를 온전히 복원하기 어렵기 때문이다. 아울러 해시함수는 길이가 서로 다른 입력데이터에 대해 일정한 길이의 출력을 만들 수 있어서 ‘데이터 축약’ 기능도 수행할 수 있다. 다만 현재까지 개발된 거의 모든 해시함수는 해시충돌을 일으키는 것으로 확인됐다. 물론 해시충돌 자체를 줄이는 것도 의미가 있겠다만, 중요한 것은 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 하는 것이다. 극단적으로 위 그림에서 모든 키가 02라는 동일한 해시값으로 매핑이 될 경우 데이터를 액세스할 때 비효율성이 커지고, 보안이 취약(서로 다른 키인데도 동일한 해시값)해져 굳이 해시를 도입해 데이터를 관리할 이유가 없어진다.[5]
MD5[편집]
MD5(Message-Digest algorithm 5)는 128비트 암호화 해시 함수이다. RFC 1321로 지정되어 있으며, 주로 프로그램이나 파일이 원본 그대로인지를 확인하는 무결성 검사 등에 사용된다. 1991년에 로널드 라이베스트가 예전에 쓰이던 MD4를 대체하기 위해 고안했다. 1996년에 MD5의 설계상 결함이 발견되었다. 이것은 매우 치명적인 결함은 아니었지만, 암호학자들은 해시 용도로 SHA-1과 같이 다른 안전한 알고리즘을 사용할 것을 권장하기 시작했다. 2004년에는 더욱 심한 암호화 결함이 발견되었고. 2006년에는 노트북 컴퓨터 한 대의 계산 능력으로 1분 내에 해시 충돌을 찾을 정도로 빠른 알고리즘이 발표되기도 하였다. 현재는 MD5 알고리즘을 보안 관련 용도로 쓰는 것은 권장하지 않으며, 심각한 보안 문제를 야기할 수도 있다. 2008년 12월에는 MD5의 결함을 이용해 SSL 인증서를 변조하는 것이 가능하다는 것이 발표되었다.MD5는 임의의 길이의 메시지(variable-length message)를 입력받아, 128비트짜리 고정 길이의 출력값을 낸다. 입력 메시지는 512 비트 블록들로 쪼개진다. 메시지를 우선 패딩하여 512로 나누어떨어질 수 있는 길이가 되게 한다. 패딩은 다음과 같이 한다: 우선 첫 단일 비트, 1을 메시지 끝부분에 추가한다. 512의 배수의 길이보다 64 비트가 적은 곳까지 0으로 채운다. 나머지 64 비트는 최초의(오리지널) 메시지의 길이를 나타내는 64 비트 정수(integer)값으로 채워진다. 메인 MD5 알고리즘은 A,B,C,D라고 이름이 붙은 32 비트 워드 네 개로 이루어진 하나의 128 비트 스테이트(state)에 대해 동작한다. A,B,C,D는 소정의 상수값으로 초기화된다. 메인 MD5 알고리즘은 각각의 512 비트짜리 입력 메시지 블록에 대해 차례로 동작한다. 각 512 비트 입력 메시지 블록을 처리하고 나면 128 비트 스테이트(state)의 값이 변하게 된다.[6]
SHA-1[편집]
SHA는 Secure Hash Algorithm의 줄임말로 1993년 미국 국가안보국(NSA)에 의해 설계되고 표준으로 지정되었다. 이때 출간된 SHA는 구분상 SHA-0이라하고 2년 뒤인 1995년에 개정된 SHA-1을 발표했고 현재 널리 쓰이는 해쉬 알고리즘이다. SHA-1은 메시지 길이에 상관없이 512비트씩 잘라서 메시지 다이제스트 함수를 돌린 뒤 160비트의 출력을 낸다. 메시지 길이가 512비트의 배수가 아닐 경우 패딩을 하는데 패딩은 맨 뒤 64비트에는 메시지 전체 길이를 넣고 나머지 비트는 최상위 비트 1을 제외하고 0으로 채운다. 메시지가 512비트보다 길 경우 다음 번 메시지 다이제스트 함수의 입력으로 전 함수의 출력을 받는다. 주요 처리에는 패딩 처리,메세지 길이를 512 비트 단위(입력 블록 상한)로 잘라서 512 비트의 정수배로 처리, 입력 블록 단위의 처리(32 비트 x 80개 값(W0~W79)을 계산),블록 처리등을 한다. [7]
SHA-2[편집]
SHA-2 (Secure Hash Algorithm 2)는 미국 국가안보국(NSA)가 설계한 암호화 해시 함수들의 집합이다. 암호 해시 함수는 디지털 데이터 상에서 수학적으로 동작하며 알려져 있고 예측된 해시값에 대해 계산된 해시(알고리즘의 실행 출력)를 비교함으로써 사람이 데이터의 무결성을 파악할 수 있게 된다. 이를테면 다운로드한 파일의 해시를 계산한 다음 이전에 게시한 해시 결과물의 결과와 비교하면 다운로드한 파일이 수정 또는 조작되었는지 알 수 있다. 암호 해시 함수의 주요 개념은 충돌 회피이다. 즉, 누구도 동일한 해시 출력 결과가 있는 두 개의 다른 입력값을 알아낼 수 없다. SHA-2는 전작 SHA-1으로부터 상당한 변경사항을 포함하고 있다. SHA-2 계열은 224, 256, 384, 512비트로 된 다이제스트(해시값)이 있는 6개의 해시 함수를 구성하고 있다: SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256[8]
활용[편집]
레인보우 테이블의 원리[편집]
- 레인보우 테이블은 한 개가 아니라 몇 천개로 이뤄져 있다. 이 몇 천개가 생성된 후 진짜 최종 테이블이 생성된다.
- 최종 테이블: 해당 테이블의 최초 패스워드랑 최종 해시값을 저장한다.
- 최초 패스워드에서 해시 함수를 이용해 해시 값 생성, 생성된 해시 값 사용하여 R함수로 두번째 확인하고자 하는 패스워드를 생성한다.
- R함수: 앞에서부터 숫자인걸 가져와서 저장하는 식으로 이뤄진다.
- 최종 테이블은 각각의 테이블의 최초 패스워드와 마지막 해시값으로 이뤄진다.
패스워드를 찾는 방법[편집]
- 현재 해시값이 최종 테이블에 있는지 확인한다.
- 없으면 해시값을 R함수로 추출한다.-> 31945
- 추출해낸 패스워드 기준으로 해시값을 생성한다. -> F55078E976DF9B3214D3F222
- 생성한 해시값이 최종 테이블에 있는지 확인한다.
- 생성한 해시값이 최종 테이블에 있으면 최종 테이블에서 생성한 해시값에 해당하는 패스워드가 최초 패스워드인 테이블로 이동한다.
- 이동한 테이블에 찾고자 하는 해시값에 대한 패스워드가 있는 것을 확인한다.-> 38059 [9]
레인보우 테이블을 이용한 공격[편집]
만약에 해시 알고리즘을 엄청나게 복잡하게 만들어서 오래 걸리게 하면 brute force 공격으로부터 안전해지지 않을까? 이를테면 SHA-512의 경우는 앞서의 공격으로도 초당 364000개 밖에 대입하지 못한다. 물론 이것도 엄청나지만 앞서의 8자리 영문자 숫자 조합의 경우 7만년 쯤 걸린다. 이 정도면 안전하지 않을까? 그렇지 않다. Brute force attack을 생각해보면 더 좋은 방법을 생각해낼 수 있다. 미리 가능한 패스워드 조합을 다 계산한 테이블을 가지고 비교만 수행하는 것이다. 이것이 사전 공격인데, 이 dictionary를 해시값 검색에 최적화시킨 것을 레인보우테이블이라고 한다. MD5의 경우는 인터넷에 이미 수백억 개의 해시값에 대한 레인보우테이블이 있다. 이미 계산된 값을 이용하므로 알고리즘의 복잡도도 큰 상관이 없다. 이 안에 있는 패스워드는 그냥 금방 뚫리는 것이다. 공개된 MD5 레인보우테이블로 찾으면 대부분의 웹사이트에서 90% 정도의 사용자 패스워드가 크랙된다고 하니 이쯤되면 md5는 이미 뚫려 있게 되는것이다. 물론 레인보우테이블을 만드는데도 시간이 많이 들기 때문에 알고리즘의 복잡도가 전혀 상관이 없는 것은 아니다. 알고리즘 수행시간이 길면 충분한 규모의 레인보우테이블을 확보하기도 어렵다. 그렇치만 쉬운 패스워드의 경우 쉽게 뚫릴 수 있으므로 보안성을 크게 높일 수 있다고 말하긴 어렵다.[10] 레인보우 테이블은 공격자의 사전 공격 방법 중 하나이다.
- 레인보우 테이블에 크래킹하려는 해시값과 같은 MD5 해시값이 있는지 확인
- 레인보우 테이블에 크래킹하려는 해시값이 없으면 크래킹할 해시값에 R함수를 적용한다. 패스워드를 구하고 다시 해시값을 구한다.
- 구한 해시값이 레인보우 테이블이 있는지 확인한다.
- 레인보우 테이블에서 확인한 해시값을 발견한 뒤 그 해시값에 해당하는 최초 패스워드를 구한다.
- 확인한 최초 패스워드에서 다시 패스워드와 일치하는 해시값이 나올 때까지 MD5 해시와 R함수를 반복 수행한다. 해당 해시값이 확인 되면 찾는 패스워드는 해당 해시값을 생성한 문자열이다.[11]
종류[편집]
패스워드 크래킹[편집]
패스워드 크래킹은 네트워크 컴퓨터 시스템에 의해 전송된 저장 위치로부터 또는 데이터로부터 패스워드를 복구하는 것을 포함한다. 패스워드 크래킹의 목적은 컴퓨터 시스템에 무단 접근을 통해 권한을 얻거나 잊어버린 암호를 복구하기 위해 사용한다. 해커가 시스템을 해킹할 수 있도록 테스트 암호 강도를 위한 기술은 크래킹 암호를 사용하는 또 다른 이유가 될 수 있다. 일반적으로 반복적 작업이나 일정한 패턴, 조합 등을 통해 알아내기도 한다. 패스워드 크래킹은 해킹 기법 중 난이도는 낮지만 가장 강력한 공격이다. 또한 보안 프로그램이 설치되어 있어도 얼마든지 크래킹이 가능하다.[1]
사전공격(dictionary attack)[편집]
원본(평문)에 대해 미리 계산된 해쉬값들을 모아서 사전 형태로 만들어놓고, 대입해보는 공격 방법[12] 사전 공격(Dictionary attack)은 사전에 있는 단어를 입력하여 암호를 알아내거나 해독하는 컴퓨터 공격법이다. 암호를 알아내기 위한 공격은 사전의 단어를 순차적으로 입력하는 것이다. 단어를 그대로 입력할 뿐 아니라, 대문자와 소문자를 뒤섞기도 하고, 단어에 숫자를 첨부하기도 하는 등의 처리도 병행하면서 공격을 할 수 있다. 수십만 개의 단어가 수록되어 있는 사전을 컴퓨터에 자동 처리시킴으로써 짧은 시간 안에 모든 단어를 입력할 수 있기 때문에 사전단어공격은 기본적인 패스워드 탐색의 수법으로 이용된다. 이에 대처하기 위해서는 인명이나 의미가 있는 단어를 패스워드로 쓰지 말아야 하며, 기호나 숫자 등을 랜덤으로 결합시키는 방법을 사용해야 한다. 암호해독의 수법으로 사서공격을 이용하는 경우에는, 사서에 있는 단어나 무작위로 모은 평문(平文)을 모두 암호화하여 이것을 해독하고자 하는 암호에 맞춰보고 일치 여부를 조사하는 방법을 쓴다. 이에 대한 대처법으로는 암호문을 길게 하는 것이 효과적이다. 사전 공격은 미리 만들어진 목록에 의한 공격만 해당하며 드루킹 특검에서처럼 비밀구절(passphrase)에 특정인이 넣을만한 단어들을 추측해서 집어넣는 것은 사전 공격의 범주에 들어가지 않는다는 주장도 있다. 이런 식의 공격은 사전 지식을 이용한 추측(educated guess)을 사용한 공격이다. 이런 educated guess attack은 해커들이 선호하는 공격 중 하나이다. 레인보우 테이블도 사전공격과 비슷한 해킹기술이다.[13]
무차별 대입 공격(Brute Force Attack)[편집]
무차별 대입 공격(영어: brute force attack)은 특정한 암호를 풀기 위해 가능한 모든 값을 대입하는 것을 의미한다. 대부분의 암호화 방식은 이론적으로 무차별 대입 공격에 대해 안전하지 못하며, 충분한 시간이 존재한다면 암호화된 정보를 해독할 수 있다. 하지만 대부분의 경우 모든 계산을 마치려면 실용적이지 못한 비용이나 시간을 소요하게 되어, 공격을 방지하게 한다. 암호의 '취약점'이라는 의미에는 무차별 대입 공격보다 더 빠른 공격 방법이 존재한다는 것을 의미한다. 대칭키 암호의 경우 암호에 사용된 키를 알아내면 암호화된 정보를 복원할 수 있고, 여기에서 사용한 키 길이에 따라 무차별 대입 공격의 최대 소요 시간이 정해진다. 암호화 키가 n비트일 경우 가능한 값은 최대 {\displaystyle 2^{n}} 2^{n}가지가 존재한다. 2009년 기준으로 128비트 이상의 키는 안전하다고 평가된다. 64비트 이하의 경우 실제 무차별 대입 공격이 성공하였다. 예를 들어, 56비트를 사용하는 DES의 경우 약 하루 안에 전체 키를 대입하는 하드웨어가 1999년에 공개되었다. 64비트 키를 사용하는 RC5의 경우 Distributed.net이라는 분산 컴퓨팅 프로젝트에서 해독한 사례가 있다. 사용자 암호와 같이 암호가 특정 패턴을 이루고 있을 경우에는 대입해야 할 값의 범위를 크게 줄일 수 있다. 이 경우 사전의 단어를 조합하여 대입하는 사전 공격이 사용된다. 그러므로 암호의 패턴을 불규칙적으로 하고 자신의 개인정보와 연계되지 않도록 하는 것이 좋다.[14]
collision 공격[편집]
충돌이 발생하는 경우를 공격하는 것으로 해시 함수 특성상 같은 문자의 경우 같은 해시값을 가져 충돌이 발생한다는 것이다. 따라서 해당 해시함수를 통해 무작위로 패스워드를 입력하여 같은 해시 값이 나올때까지 반복하는 것이다. 해당 공격을 방지하기 위해 나온 것이 다양한 해시 함수를 사용하는 것과 salt 기술을 병합하는 것이다. 해당 기술은 앞서 충돌 공격을 방지하기 위한 것으로 같은 패스워드일지라도 패스워드+해시+salt 구조로 인해 해시 값은 다른 결과를 가져온다. 장점은 무작위 공격과 유사하여 100%찾아낸다는 것이고 단점은 현재 보안 정책이나 기술로 인해 현실적으로 불가능에 가깝다.
사회공학적 공격(Guessing Attack)[편집]
사회공학적 공격이란 해당 사용자가 인적사항이나 행동, 실수 등을 통해 패스워드를 알아내는 것이다. 직업이나 환경, 공동체 내의 공통적인 암호 등을 통해 유추해내어 패스워드를 알아내는 것이다. 현재 암호화가 강화되어 위에 기술된 방법을 통해 찾는 것은 많은 시간이 걸려 상황에 따라 비효율적일 수 있으며 찾지 못하는 경우도 있으나 짧은 시간에 찾을 수 있다는 장점이 있다.[1]
패스워드 크래킹 툴[편집]
- john the ripper: 패스워드 크래킹 툴의 대표적인 툴이다. 앞서 설명한 대부분의 기법들이 포함되어 있다.
- ophcracker: 레인보우 테이블을 통한 크래킹 툴이다.
- cain&abel: 윈도우 GUI기반 도구로 Sniffing과 ARP poisoning과 함께 MITM공격에 주로 사용된다.
- hydra: 네트워크 패스워드 크래킹 툴이다.
- Medusa: 히드라와 유사한 툴이며 히드라에 비해 빠른 속도를 지니고 있다.
- Aircrack:무선 네트워크의 패스워드를 크래킹 하는 툴이다.[15]
방어법[편집]
길이가 짧거나 단순 조합에 의한 패스워드, 반복적인 단어나 특정 단어에 의한 패스워드, 유추가 가능하거나 많은 사람이 사용할만한 패스워드는 패스워드 크래킹 공격에 취약하므로 사용을 자제 해야한다. 따라서 안전한 패스워드는 몇 가지로 정리 할 수 있다.
- 적절한 알고리즘 사용(PBKDF2, Bcrypt, Scrypt 등)
- 길이 및 다양한 조합의 패스워드 설정(영문, 숫자, 특수문자 조합 등)
- 패스워드를 암호화할 때 해시값의 반복을 통해 암호화를 극대화해주는 키 스트레칭
- 일정시간 반복된 로그인 실패 차단
- 정해진 로그인 실패 회수 초과시 계정 잠금
- 2-factor 인증
- otp사용
- 패스워드 저장시 암호화
패스워드 크래킹의 경우 해킹에 있어 필수적인 요소이며, 사용자의 입장에서 본인을 인증하기에 필수적인 요소이다. 해커에 의해 패스워드가 탈취당할 수 있지만, 대부분 해킹의 경우 사용자나 관리자의 부주의나 안일한 태도로 인해 대부분 발생하기 때문에 조금의 보안 의식을 가지고 책임감을 느낀다면 많은 사고가 발생하지 않을 것이다.[1]
솔티드 해시(Salted hashed)[편집]
기존에는 패스워드만 해시함수에 통과시켰으나 최근에는 가입 시간이나 난수를 비밀번호와 같이 해시값에 포함시킨다. 이 때 추가적으로 포함된 가입 시간이나 난수를 솔트(salt)라고 한다. 이는 서로 다른 계정이 같은 비밀번호를 사용하더라고 솔트가 다르면 완전 다른 해시값이 생성되며, 설령 같은 해시값을 같더라 하여도 솔트 값이 전혀 다르기 때문에 평문을 유추하기 힘들다는 논리다. 일방향성이 아닌 암호화/역암호화시 둘다 사용되는(쌍으로 이루어지는) 솔트는, 같은 솔트가 사용되어야 하고 레인보우 테이블에 의한 암호 크랙 공격(사전 공격)을 어느정도 무력화시킬 수 있다.[12]
블룸 필터(Bloom filter)[편집]
블룸 필터는 원소가 집합에 속하는지 여부를 검사하는데 사용되는 확률적 자료 구조이다. 즉, 개발자들은 사용자가 회원 가입을 할때 레인보우 테이블에 있는 비밀번호에 대하여 사용을 금지하는 방법을 선택하는데 이러한 과정속에서 금지된 비밀번호를 걸러 내는 역할을 한다. 이 방법을 사용하면 사용자는 취약한 비밀번호의 사용이 금지되어 공격자가 가지고 있는 패스워드 사전도 취약하게 된다. 설령 공격자가 갱신을 한 패스워드 사전을 가지고 있다 하여도 개발자가 해당 사전을 수집할 수 있으므로 금지 비밀번호를 갱신하면 된다.[16]
각주[편집]
- ↑ 1.0 1.1 1.2 1.3 〈패스워드 크래킹〉,《해시넷》
- ↑ 수니감자,〈패스워드 크래킹〉, 《티스토리》,2016-10-22
- ↑ 〈레인보우 테이블〉,《나무위키》
- ↑ 〈패스워드〉, 《나무위키》
- ↑ 〈해싱, 해시함수, 해시테이블〉, 《랫츠고 블로그》, 2017-10-25
- ↑ 〈Md5〉, 《위키백과》
- ↑ 〈SHA, SHA-1, SHA1〉, 《정보통신기술용어해설》
- ↑ 〈SHA-2〉, 《위키백과》
- ↑ 이해빈,〈패스워드 크래킹〉, 《티스토리》, 2018-01-07
- ↑ 박영록,〈패스워드 보안의 기술〉,《코드오케이넷》
- ↑ 달콤맛마이쮸, 〈유동현〉, 《네이버 블로그》, 2016-09-18
- ↑ 12.0 12.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
- 〈패스워드〉, 《나무위키》
- 〈Md5〉, 《위키백과》
- 〈SHA, SHA-1, SHA1〉, 《정보통신기술용어해설》
- 〈SHA-2〉, 《위키백과》
- 수니감자,〈패스워드 크래킹〉,《티스토리》,2016-10-22
- 〈패스워드 크래킹〉,《해시넷》
- 〈레인보우 테이블〉,《나무위키》
- 박영록,〈패스워드 보안의 기술〉,《코드오케이넷》
같이 보기[편집]
| ||||||||||||||||||||||||||
