[보안] 패스워드 해킹과 레인보우 테이블

안녕하세요 오늘은 한번 학교를 째고-_- 패스워드(비밀번호) 해킹과 레인보우 테이블에 대해서 써볼까 합니다. (이 글에서는 혼란을 방지하기 위해서 비밀번호라는 말 대신에 패스워드를 사용하겠습니다.) 요즘 대부분의 웹사이트에서는 가입할 때 ID와 패스워드를 요구하죠? 그럼 그 웹사이트에서는 이 패스워드를 어떻게 보관할까요? 뭐 여러가지 방법이 있겠습니다만, 대충 2가지만 살펴보겠습니다. 1. 패스워드를 그대로 보관 가장 무식한 방법입니다. 개발자 입장에서는 정말 편하죠. 그냥 if문을 이용한 코드 한줄이면 로그인 성공유무를 체크할 수 있으니깐요. ID 패스워드 김개똥 123456 홍길똥 q1w2e3 이나라 asdf12340987 박순이 sodlfmadmsqkrtnsdl958182 하지만 해당 사이트가 해킹당하면 한방에 모든 사용자의 패스워드가 노출됩니다. 해당 사이트 관리자도 몰래 사용자의 ID, 패스워드를 볼 수 있게 되어있죠. 사용자 입장에서는 아무리 패스워드를 잘 설정해봤자 한방에 뚫리니 불쾌하기 짝이 없습니다. 따라서 부득이하게 이런 사이트에 가입을 해야한다면, 패스워드 선택에 신중을 기해야 합니다. 그럼 어떻게 패스워드를 그대로 보관하는 웹사이트를 판별할 수 있을까요? 여기에 몇가지 트릭이 있습니다. 보통 대부분의 사이트에서는 패스워드를 분실하였을 경우 복원받을 수 있는 절차를 제공하고 있습니다. 이때 패스워드를 그대로 보관하는 사이트는 대체적으로 생짜로 패스워드를 알려주는 반면, 해쉬를 통해서 안전하게 보관하고 있는 사이트는 패스워드 변경 절차만 제공해 줍니다. 따라서 의심이 간다면 패스워드 분실을 가장해서 복구절차를 밟아보는 것도 좋은 방법입니다. 2. 해쉬함수를 이용한 암호화 현재 많은 곳에서 사용하고 있는 방식입니다. 이 방식을 이해하려면 해쉬함수에 대해서 이해해야 합니다. 함수란 간단히 말해서 입력 / 출력으로 이루어진 수학연산입니다. 학교다닐때 지겹게 배운 f(x) = 2x + 1 이런 것도 일종의 함수죠. (x:입력, f(x):출력) 역함수는 Output을 이용해서 거꾸로 Input을 도출하는 함수입니다. 위의 f(x) = 2x + 1 은 역함수는 x = (1/2)f(x) - (1/2) 가 될 수 있겠네요. 이렇게 역함수를 통하면 출력값만 가지고 바로 원본값(입력값)을 알아낼 수 있습니다. 하지만 특이하게 수학적으로 역함수가 존재하지 않는 함수도 있습니다. 해쉬함수는 이러한 성질을 이용해서 만들어진 특별한 함수입니다. 수많은 종류의 해쉬함수가 있지만, 컴퓨터 보안 분야에서는 그 중에서도 수학적으로 더욱 뚫기 어렵다고 알려진 것들을 사용하고 있습니다. 대표적으로 MD5, SHA-1 같은게 널리 쓰여왔죠. 이러한 해쉬함수들은 추적을 피하기 위해서 입력값이 단 1글자만 바뀌어도 전체 결과값이 완전히 뒤바뀌는 특성을 가지고 있습니다. 정리하자면 위 그림의 해쉬값(Digest)만 가지고는 원문을 복원하는것은 현재까지 역함수를 통해서는 불가능하다고 알려져 있습니다. 여기서 "현재까지 역함수를 통해서"라는 말이 중요합니다. 1. 앞으로 깨질 수도 있다는 뜻도 되죠. 2. 또는 역함수를 회피해서 깰 수 있다는 뜻도 됩니다. 자. 이제 본격적으로 해쉬함수를 깨는 방법을 살펴봅시다. 그중에서 하나를 콕 찝어서 MD5를 살펴보겠습니다. MD5는 1991년도에 M.I.T.의 Ron Rivest에 의해서 발명된 함수입니다. 그 이전에는 다들 예상할 수 있다시피 MD4 가 있었으나, 차츰차츰 약점이 까발려지고 있던 상황이었고, 1995년이 되어서는 완전히 깨졌다고 알려져 있습니다. (참고로 정확히 말씀드리면 Collision을 찾게된 것입니다. Collision에 대한 내용은 위키피디어를 참조해 주세요. MD5는 어떠한 입력을 받더라도 128비트 해쉬값을 만들어내는 성질을 가지고 있습니다. 따라서 해쉬값만 가지고는 원본, 또는 원본의 길이조차 찾기 불가능해 보였죠. MD5("The quick brown fox jumps over the lazy dog") = 9e107d9d372bb6826bd81d3542a419d6 하지만 이런 MD5 에도 암흑의 기운(???)이 드리우기 시작합니다. 1996년에 한차례씩 약점이 제시되었다가, 2004년에 중국인 학자들에 의해서 상당히 치명적인 약점이 공개되었습니다. 그러다가 급기야 2008년도에는 Verisign의 하위 인증기관인 RapidSSL의 인증서가 조작되는 사태가 발생합니다. 우리나라로 친다면 공인인증서가 뜬금없이 해커에 의해서 마구 발행이 될 수 있는 사태가 벌어진 것이죠. 그래서 대부분의 국가에서는 국가 프로젝트에서 MD5 사용 중지를 명령했으며, 현재 거의 대부분의 공인인증서도 SHA-1 함수를 이용하는 것으로 바뀌었습니다. 미국 정부 내에서는 의무적으로 SHA-2 까지 사용하도록 요구수준이 높아졌고요. 엎친데 덮친겪으로, 이러한 수학적인 분석 외에도 비수학적인 방법(역함수를 회피하는 방법)이 본격적으로 도입되기 시작했습니다. 바로 레인보우 테이블이라는 녀석이죠. 레인보우 테이블이란건 단순무식하게 가능한 모든 해쉬의 쌍(원본:해쉬값)을 미리 계산해서 저장해놓은 표입니다. 이를 이용해서 나중에 필요할때 고속으로 검색해서 뚫을 수 있게 되어있죠. 해쉬값 패스워드 0cc175b9c0f1b6a831c399e269772661 a 92eb5ffee6ae2fec3ad71c777531578f b 749d7048edd2de31c2c7a88d4d196254 ab12 7cbb3252ba6b7e9c422fac5334d22054 q1w2e3 이러한 무자비한 특성으로 인해서 데이터의 크기가 기본적으로 테라바이트 단위입니다. 게다가 이 테이블을 구축하는데만해도 어마어마한 CPU 자원이 필요하고요. 그래서 과거에는 사전에 있는 단어만 우선순위를 둬서 테이블을 만들곤 했습니다. 그래도 용량이 제법 크게 나오곤 했죠. 하지만 최근에는 저렴한 HDD의 가격과 고성능 PC로 인해서, 이제는 첩보기관, 해커들 뿐만 아니라 일반인들도 누구나 Full version의 레인보우 테이블을 쉽게 접할 수 있게 됩니다. Distributed Rainbow Table Project는 그리드 컴퓨팅을 이용하여 누구나 레인보우 테이블 생성 및 다운로드에 참여할 수 있도록 되어있는 프로젝트입니다. 자세한 참여방법에 대한 내용은 이 글의 신철현님의 댓글을 참고해주세요. 아무튼 저 프로젝트에서는 이미 3TB에 가까운 테이블을 구축해서 BitTorrent 로 공유하고 있습니다. MD5만 따지자면 1TB 약간 넘겠네요. 무엇보다도 지금 이시각에도 계속 수많은 사용자들의 도움으로 계속 늘어날 전망입니다. 저 자료만 가지고도 아래와 같은 상당한 수준의 해킹이 가능하죠. 숫자로 된 패스워드는 12자리까지 소문자로 된 패스워드는 10자리까지 숫자+소문자 패스워드는 8자리까지 숫자+소문자+대문자 패스워드는 7자리까지 위 난이도 정도는 정말 순식간에 뚫을 수 있습니다. 레인보우 테이블을 이용한 공격으로부터 방어하기 위해서는 패스워드를 가능한한 길게, 그리고 다양한 종류의 문자를 포함하도록 사용하는 것이 좋습니다. 하지만 모든 사용자로하여금 그렇게 사용하도록 강제할 수는 없는 노릇이기 때문에, 상당수 개발자들은 Salt라는 약간 변칙적인 방법을 가미한 해쉬를 사용하고 있습니다. 이 방법은 랜덤한 문자열을 앞이나 뒤, 중간에 덧붙여서 원본의 길이가 길어지게 만드는 것입니다. 아래는 asdf(하늘색)라는 입력에 대해서 Salt(빨간색)를 덧붙여서 해쉬(초록색)를 계산하는 예제입니다. "xR1nTH#iz!" + SHA1("asdf"+"xR1nTH#iz!") = xR1nTH#iz!c41fb2bab867b14aff8072c0af4fc6b9c7216918 위와 같이 Salt를 가미하면 어떻게 될까요? 저걸 뚫기 위해서는 4자리 이상 소문자 테이블 대신에 14자리 이상 대문자+소문자+숫자+특수문자 테이블을 뒤져봐야 합니다. 다행히 아직까지 14자리 이상의 짬뽕 문자들로 이루어진 레인보우 테이블이 완성되기 위해서는 제법 시간이 남아있으므로, 그동안은 쪼금~ 안심하고 사용할 수 있죠. 현재 대부분의 유명한 오픈소스 프로그램들은 Salt를 가미한 해쉬를 사용하고 있습니다. (리눅스 등등...) 비공개 프로그램들은 리버스 엔지니어링을 안하면 평문을 저장하는지, 뭘 사용하는지는 알 도리가 없지만요... 이러한 이론적인 발전에도 불구하고 안타깝게도 현재 많은 웹사이트에서는 최대 패스워드 길이를 제한하고 있으며, 일부 사이트는 특수문자를 사용할 수 없는 곳도 있습니다. 같은 컴퓨터 업종에 있는 사람으로서 화가나고 참 부끄럽기 그지없습니다만...... 제가 어떻게할 방법이 없군요. 읽느라 고생하셨습니다. ^^; 대충 여기까지네요. 사실 이 외에도 몇가지 해쉬에 대한 역사적인, 기술적인 이야기를 풀까했는데, 너무 전문적인 내용으로 흘러가는 것 같아서 포기했네요... 관심있으신 분들은 영문 위키피디어를 참고하시면 재미있을 겁니다.

원본출처 : Wikipedia, Distributed Rainbow Table Project 등등

본 내용의 해당 저작자와 번역자는 저작권법의 보호를 받습니다.

원본 URL : http://parkoz.com/bk_upr