브루트-포스 공격
* 관련 문서: 컴퓨터 관련 정보
개요
brute는 "짐승같은, 난폭한"이라는 뜻이고, brute-force는 "난폭한 힘, 폭력"이라는 뜻이다. 암호학 용어로는 brute-force attack 또는 exhaustive key search, 우리말로는 --노가다 또는-- 무차별 대입 공격이라 부른다. 주로 암호학에서도 쓰이는 방법이긴 하지만, 굳이 암호학만의 문제는 아니고 다른 알고리즘 분야에서도 사용되고 있다. 간단하게 말하자면 노가다와 다굴을 논리적이고 과학적으로 하는 방식. ~~다 넣어보는게 무슨 논리여~~
특징
조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 문제를 푸는 것인데, 얼핏 무식하다고 생각할 수도 있겠지만 --성공한다는 가정 하에-- 항상 정확도 100%를 보장한다는 점에서, 자원만 충분하면 가장 무서운 방법이다. 이론적으로 가능한 모든 경우의 수를 다 검색해 보는 것이라 정확도 100%가 항상 보장되니, 암호학에서는 가장 확실한 방법으로 통용되고 있다. 무엇보다도 암호 확인 작업이라는 것이 손으로 입력한 문자열의 동일 여부를 확인하는 것이기 때문에, 가능한 경우를 하나씩 대입하다 보면 언젠가는 암호를 찾을 수 있게 되는 식이다. 다만 정말로 그냥 무식하게 때려박는 건 아니고, 숫자만 섞어서 대입해보기 한번, 로마자만 섞어서 대입해보기 한번 이런식으로 하다가 안되면 나머지를 순차적으로 하는 식으로 특정 규칙에 따라 우선순위를 두고 하기도 한다.
또한 브루트 포스의 특장점은 거의 완벽하게 병렬 작업이 가능하다는 점이다.[* 0000~1999는 1번 컴퓨터 (혹은 코어), 2000~3999는 2번 컴퓨터 이런 식.] 이 때문에 병렬 프로그래밍 기법을 사용하거나, GPGPU를 이용하기도 하며, 여러 대의 컴퓨터를 연결해서 동시에 작업할 수도 있다. 이렇게 하면 투자 자원에 비례해서 문제를 해결하는 시간을 줄일 수 있다. 즉, 컴퓨터를 10대 쓰면 10일 걸릴 작업을 1일만에 끝낼 수 있다는 이야기 이다. (다만 암달의 법칙 때문에 이런 식으로 병렬화가 잘 되는 작업은 흔치 않다.)
90년대 초 김재열이 ‘청와대 해킹사건’을 저지르는 과정에서 국제재판소 비밀번호를 알아낼 때 이런 식으로 일일이 노가다를 했다. 그렇게 알아낸 패스워드는 12345(...).
예시
예를 들어, 4자리 숫자로 된 핸드폰의 암호는 0000, 0001, 0002... 9999 까지 총 1만개(10^4)의 조합 중 하나이므로, 이를 하나씩 대입해 보면 핸드폰의 암호를 통과할 수 있게 된다. 한 번 암호를 입력해 보는데 5초가 걸린다면, 5만 초 즉 14시간이면 충분하고, 이를 사람 손이 아닌 컴퓨터로 처리할 수 있다면 1초 이내로 찾아낼 수 있게 되는 것이다. 알집 압축파일의 암호풀기도 있다.
아래 영상은 터미네이터2 에서 존 코너가 아타리 포트폴리오를 이용해서 ATM 머신을 해킹하는 장면. (얼핏 보면 브루트 포스처럼 보이지만 화면에 나오는 내용을 보면 진짜 브루트 포스는 아니다.)
실제로 DES의 경우, 개발 당시에는 무결점 알고리즘이었으나 컴퓨터 성능이 크게 개선된 지금은 브루트 포스로도 다 뚫린다. 속도는 물론이고, 공격에 필요한 DES 사전 용량 역시 현재의 컴퓨터 환경에선 충분히 감당할 수 있기 때문. 물론 요즘은 세 번 DES를 돌려서 대응한다. MD5 역시 컴퓨터의 발전 때문에 진작에 다 뚫린 지라 이미 SHA로 갈아탄 상태이다.
자원이 시궁창
하지만 앞서 언급했듯 자원이 문제, 브루트 포스 방법에는 문제의 복잡도에 매우 민감하다는 치명적인 단점을 지니고 있다.
자릿수가 최대 8자리, 영문 대소문자, 숫자를 충족하는 사전파일을 만들면 그 텍스트 파일의 용량은 34^8×2이다 여기서 2가 붙은 이유는 영문자, 숫자 인코딩은 한글자당 2Byte를 차지하기 때문인데, 위 공식에 따라서 나온 Byte를 GB로 환산해보면 대략 3572GB가 나온다, 만약 해당 사전파일을 만드려 한다면, 4~8GB 단위로 파일을 끊어서 저장하지 않는 한 오버플로우 또는 저장공간의 용량 부족이 일어날 것이다. 또한 저것을 대입하는 것도 똑같다. 다시말해서 왠만한 비밀번호를 다 뚫을 수 있는 사전파일을 만들고 실제로 사용하려면 양자컴퓨터 기술과 초고용량 메모리/저장장치가 대중화 되어야 한다. --위와 같은 초고사양 양자컴퓨터가 대중화되면 AES256도 깨지게 된다--
달리 풀어서 말하면, 문제가 조금만 복잡해져도 매우 비효율적인 알고리즘이 될 수 있다는 것이다. 특히 경우의 수가 문제의 복잡도에 따라 기하급수적으로 증가하는 경우, 문제를 해결하는 데에 필요한 자원 역시 기하급수적으로 증가한다.
때문에 체스나 바둑과 같이 경우의 수가 많은 경우, 일반적으로 브루트포스를 쓰지 않고, AI나 알고리즘을 통해 보다 효율적으로 접근한다.
이 때문에 실제로 브루트 포스는 문제의 규모가 현재의 자원으로 충분히 커버가 가능한 경우에만 쓰이고, 대부분은 동적 계획법 등으로 많이 우회하는 편이다. 심지어는 정확도를 조금 희생해더라도 어떻게든 '이론상 가능한' 자원으로 해결할 수 있게 알고리즘을 설계하기도 한다. 후에 언급할 사전 공격 역시 정확도가 약간 희생된 것이다.
이러한 단점은 대부분의 암호화 알고리즘에서 역이용하고 있는데, 무어의 법칙 덕분에 컴퓨터 성능이 꾸준히 개선되고 있다 해도 그만큼 더 복잡한 암호화 기법을 이용하면 되기 때문이다. 현 세대의 암호화 기법을 브루트 포스로 다 뚫는다 해도, 그 시간이 지나고 나면 이미 구식도 아닌 구석기 알고리즘으로 전락해 있을 법하니 그만큼 시간을 충분히 벌 수 있는 것이다. 게다가 무어의 법칙은 2016년 2월 [[1]].
실제로 현재 가장 흔하게 사용되는 블럭암호인 AES 기반 암호화들의 경우에는 Weak Key를 사용하지 않는 이상 키를 모르면 유의미한 시간 내에 풀 수 없으며, AES-256의 경우는 초당 100경(10^18) 개의 키 대입(= 1 엑사플롭스)을 하는 슈퍼컴퓨터로도 3000극(3 * 10^51)년은 족히 잡아먹는다. 아직 AES-128이 완전히 깨졌다는 보고가 없는데도 하나둘씩 AES-256으로 갈아타는 이상, AES-128이 다 깨질 때 쯤이면 이미 대다수가 AES-32k, 많이 봐 줘도 AES-2k를 쓰고 있을 판이 되는 것이다. 사족으로 만약 AES-2K/AES-2048이 나온다면 키대입 경우의 수는 AES-256의 8배가 아니고 AES-2048={(AES-256^2)^2}^2...=(AES-256^256)^256. 즉 8제곱이다. 2의 1792제곱배.이것은 <math>{2}^{2048}</math> 이다. 256^256=약10^616.5. AES-2048 경우의 수=<math>2^{2048}</math>개이다.
또한 n번 안에 풀지 못할 시 자폭하거나 데이터를 삭제하는 등의 프로그램이면 때려넣기를 하기가 힘들다.
암호학에서의 브루트 포스
앞서 언급했듯, 주로 암호학에서 사용 암호화에 사용되는 key나, 찾고자 하는 비밀번호가 길수록 시간이 기하급수적으로 증가한다.
조합 가능한 모든 문자열을 대입하기 때문에 아무리 컴퓨터가 빠르다고 하더라도 시간이 매우 많이 걸린다. 당장 영문 소문자 + 숫자 조합만 쳐도 n자리의 암호를 뚫는 데에는 <math>O\left(36^n\right)</math>의 시간이 걸린다. 즉, 10글자만 되어도 36^10 = 3,656,158,440,062,976 가지가 된다. 이 정도면 쉬운 암호 알고리즘이라 해도 초당 1억번 계산 기준 대충 14개월 걸리는 수준이다. 물론 암호가 더 복잡하거나 길이가 더 길어지면 수백 ~ 수천 년은 기본으로 기다려야 한다.
좀 더 확장시켜서 암호로 입력할 수 있는 알파벳의 수를 k개라 치면, 이를 조합한 n자리 암호를 뚫는 데에는 <math>O\left(k^n\right)</math>의 시간이 걸리니 P-NP 문제로 치면 이 문제는 EXP 완전 문제가 된다. 사정이 이러니 낭비되는 시간을 최소화하려고 도입한 게 레인보우 테이블인데, 입력할 때 마다 계산(특히 해쉬 함수)하는 대신 미리 계산된 테이블을 참조하는 것이기 때문에 시간이 훨씬 단축되는 것이다. 물론 풍선 효과로 인해, 저장공간이 아주 많이 희생된다.
실제적인 예시
예를 들어 예전 하나 워드 같은 프로그램은 문서에 암호를 걸어 놓은 후, 문서 파일을 헥스 에디터로 열어보면 암호가 문서 파일 헤더에 적혀있는 것을 볼 수 있다. 즉, 문서 파일 자체가 암호화가 된 것이 아니라, 문서에 암호가 걸렸다라는 표시만 해 놓고, 프로그램에서 사용자에게 암호를 물어보아 암호가 동일하면 문서 파일을 보여주는 구조이기 때문에 암호를 아무리 어렵게 저장을 해도 손쉽게 암호를 통과할 수가 있게 되는 것이다.
하지만, 아래아 한글, MS워드, ZIP 포맷과 같은 파일 포맷은 사용자가 입력한 암호를 통해서 데이터를 암호화 했기 때문에, 암호를 통과하는 방법 따위는 존재하지 않고, 암호를 하나씩 대입해서 데이터를 풀어보는 것 이외에는 우회 방법 따위는 존재하지 않는다. 따라서, 이러한 암호화 된 파일을 풀어준다고 나와있는 프로그램들은 이러한 brute force공격을 대신 수행하주는 프로그램으로 봐도 무방하며, 해커들이 웹페이지에 로그인을 시도할 때에도 자주 사용된다. 브루트 포스 방식을 이용한 공격은 암호가 걸린 문서나 압축 파일의 암호를 해독하는데도 사용하지만, 온라인 로그인이 필요한 서비스에도 역시 동일한 방식으로 공격할 수 있다. 만일 서버에서 특정 사용자의 ID에 대해서 ID/PW 를 대입하는데 실패 횟수에 대해서 제한을 걸지 않는다면, 병렬로 사용자의 PW를 무차별 대입해서 암호를 알아낼 수 있기 때문에, 제정신을 가진 서버 관리자+프로그래머라면 비 정상적인 로그인 시도에 대해서는 항상 대비를 해야만 한다. 간혹 웹페이지를 통한 비정상적인 로그인 시도에 대해서는 차단을 하지만, POP3와 같은 눈에 잘 보이지 않는 서비스에 대해서는 비정상적인 로그인 시도를 막지 않아서 사용자 계정이 털리는 경우가 있다.
암호는 아니지만, 과거에 해외에서 로또 금액이 이월되자 한 보험사에서 모든 로또 번호를 사서 당첨되기를 시도했다! 전체 번호의 70%밖에(...) 못 모았지만 결국 당첨. 당첨금을 받아갔다. 그러나 이월되지 않으면 전체 번호를 사면 손해다. 한국 로또는 이월이 되어도 금액이 크지 않으니 하지 말자.
* 미국 FBI도 이 방법을 이용해 아이폰의 암호를 풀기도 했다. 다만, 낸드 메모리 자체를 복재(낸드 미러링)해서 해결 기회자체를 늘리는 방법을 통해 횟수제한을 회피했다고 추측된다.[[2]][[3]] 하지만, 낸드 미러링으로는 성공하지 못했다는 [[4]]도 있다.
유사한 방식
위에서도 나오듯이 정말로 처음부터 끝가지 무작위 공격을 하는 것은 시간이 오래 걸리고 비효율적이며, 특정 대상을 지정하는게 아닌 "최대한 대량"의 계정에 대한 공격을 수행하기에는 불필요하다. 왜냐하면 100개의 계정을 공격 해서 1개를 뚫을 시간에 100,000개의 계정을 공격해서 1개를 찾는게 시간적으로도 빠르기 때문이다. 따라서 암호를 대입할 때 a, b, c, .... aa, ab, ac..... ba, bb, bc, .... 와 같은 모든 가능한 조합을 대입하는 방법 대신 사용자들이 많이 쓰는 암호를 - 예를 들자면 abcd, 1234, qwert, q1w2e3, .... - 모아서 대입하는 방법도 많이 쓰이는데, 이를 사전 공격(Dictionary attack)이라고 한다.
방어 방법
다른 사람에게 브루트 포스로 암호가 털리는 것을 원치 않는다면, 다음 사항을 지키자.
* 암호는 최소 10자리 이상을 사용하자. 암호가 12자리를 넘어간다면 슈퍼 컴퓨터를 가져와도 안전하다. 숫자만으로 이루어져있다 해도 암호 한 자리당 경우의 수가 10배씩 늘어난다. 12자리이면 10^12이며 영문 대소문자 섞은 12자리라면 경우의 수는 (대문자 26개+소문자26개+숫자10개=62)^12가 된다. 이러면 전 세계의 연산기기를 전부 동원해도 우주의 엔트로피가 0이 되기 전에 못 뚫는다. * 암호에 특수문자를 사용하면 좀더 좋겠지만, 특수 문자 안 쓰고 그냥 암호가 길기만 해도 된다. 아무리 대소문자에 특수 문자를 써도 암호가 6자리 이하라면 털릴 것을 각오해야 한다. 반면 위에 서술했듯 12자리가 넘어가면 숫자만 써도 안전하다. * 대부분 사전 공격부터 가하기 때문에 최소한 다음과 같은 단어들을 쓰는 것은 자살행위이다. 브루트 포스 툴인 John The Ripper의 내장 사전 파일의 맨 앞의 일부는 다음과 같다. 123456, abc123, password, computer, a1b2c3, qwerty, secret. --그리고 군사기밀 q1w2e3r4!-- 이것 말고도 3천여개 정도 더 있으니 차라리 단어를 좀 섞자. * 여러 단어를 랜덤하게 조합해서 만든 패스워드는 기억하기 쉬운 반면 워낙 길고 무작위적이므로 이 방식으로는 깨기가 힘들다. [[5]] 사전 공격이 걱정 된다면 일반적이지 않은 문자열을 넣어주면 좋다. 같은 이유로 문장도 기억하기 어렵지 않고 사전 공격에 강한 편이다. * 외국계 해커 상대로는 한타를 영타 그대로 치는 것도 좋은 방법이다. 중간에 쉬프트가 필요한 쌍자음이 있으면 금상첨화. 숫자랑 특문을 넣으면 거의 뚫리지 않는다고 보면 된다. 물론 자신이 한국인이라는 게 알려지는 순간 사전공격으로 단숨에 뚫릴 수 있다. 한국 사이트에서는 하지 말자. 외국어 좀 하는 사람이라면 약간 마이너한 제3의 언어 독음(외국어 표기법에 안 맞는다면 더욱 좋다)을 한국어로 읽어서 영타 그대로 치는 식의 방법도 괜찮다. * 맞을 때까지 몇 번이고 틀릴 것을 전제로 하는 방법이라서 몇 번 이상 틀리면 접속을 차단하는 방어 방법이 먹힌다. 웬만한 사이트나 전자거래에서는 일정 횟수 이상 암호를 잘못 입력할 경우 계정이 일시동결된다. 민감한 분야(인터넷 뱅킹이나 신용카드 결제처럼)에서는 대면적 방법으로 새로 인증을 받지 않고서는 다시 서비스를 사용할 수 없게 해 놓기까지 한다. 이럴 경우는 브루트 포스가 쉽지 않다. 사실 오래 전에는 웬만한 포털도 브루트 포스로 크래킹이 가능했던 때가 있었다. * 브루트 포스의 경우 마구 대는 게 아닌 비트 순서대로 대는 것인데, 이를 역이용해서 첫 글자의 비트 크기에 따라 비밀번호가 뚫리는 시간은 크게 차이난다. 예를 들어서 아스키 코드 65인 대문자 A로 시작하는 비밀번호와 아스키 코드 122인 소문자 z로 시작하는 비밀번호는 깨지는 속도가 두 배 가까이 차이난다. 심지어는 프로그램에서 로마자만 따질 경우 A보다 z로 하는 것이 50배 넘게 이득이 된다. 거의 글자 하나 있고 없고의 차이가 난다. ~~대신 정방향과 역방향을 번갈아가면서 대조하면 소용없다~~