브루트 포스 공격

|| 이 문서는 무차별 대입 공격, 무작위 대입 공격으로도 들어올 수 있습니다. ||

[목차]

개요

영어로는 brute-force attack 또는 exhaustive key search, 우리말로는 무차별 대입 공격, 무작위 대입 공격이라 부른다. 주로 암호학에서도 쓰이는 방법이긴 하지만, 굳이 암호학만의 문제는 아니고 다른 알고리듬 분야에서도 사용되고 있다.

장점...이라 할 수 있나?

조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 문제를 푸는 것인데, 얼핏 무식하다고 생각할 수도 있겠지만 항상 정확도 100%를 보장한다는 점에서, 자원만 충분하면 가장 무서운 방법이다. 이론적으로 가능한 모든 경우의 수를 다 검색해 보는 것이라 정확도 100%가 항상 보장되니, 암호학에서는 가장 확실한 방법으로 통용되고 있다. 무엇보다도 암호 확인 작업이라는 것이 손으로 입력한 문자열의 동일 여부를 확인하는 것이기 때문에, 가능한 경우를 하나씩 대입하다 보면 언젠가는 암호를 찾을 수 있게 되는 식이다.

또한 브루트 포스의 특장점은 거의 완벽하게 병렬 작업이 가능하다는 점이다. 이 때문에 병렬 프로그래밍 기법을 사용하거나, GPGPU이용하기도 하며, 여러 대의 컴퓨터를 연결해서 동시에 작업할 수도 있다. 이렇게 하면 투자 자원에 비례해서 문제를 해결하는 시간을 줄일 수 있다. 즉, 컴퓨터를 10대 쓰면 10일 걸릴 작업을 1일만에 끝낼 수 있다는 이야기 이다. (다만 암달의 법칙 때문에 이런 식으로 병렬화가 잘 되는 작업은 흔치 않다.)

예시

예를 들어, 4자리 숫자로 된 핸드폰의 암호는 0000, 0001, 0002... 9999 까지 총 1만개(10^4)의 조합 중 하나이므로, 이를 하나씩 대입해 보면 핸드폰의 암호를 통과할 수 있게 된다. 한번 암호를 입력해 보는데 5초가 걸린다면, 5만초 즉 14시간이면 충분하고, 이를 사람 손이 아닌 컴퓨터로 처리할 수 있다면 1초 이내로 찾아낼 수 있게 되는 것이다.

아래 영상은 터미네이터2 에서 존 코너 가 아타리 포트폴리오를 이용해서 ATM 머신을 해킹하는 장면. (얼핏 보면 브루트 포스처럼 보이지만 화면에 나오는 내용을 보면 진짜 부르트 포스는 아니다.) https://i.imgur.com/GIceyeC.gif

실제로 DES의 경우, 개발 당시에는 무결점 알고리즘이었으나 컴퓨터 성능이 크게 개선된 지금은 브루트 포스로도 다 뚫린다. 속도는 물론이고, 공격에 필요한 DES 사전 용량 역시 현재의 컴퓨터 환경에선 충분히 감당할 수 있기 때문. MD5 역시 컴퓨터의 발전 때문에 진작에 다 뚫린 지라 이미 SHA로 갈아탄 상태이다.

자원이 시궁창

하지만 앞서 언급했듯 자원이 문제, 브루트 포스 방법에는 문제의 복잡도에 매우 민감하다는 치명적인 단점을 지니고 있다.

달리 풀어서 말하면, 문제가 조금만 복잡해져도 매우 비효율적인 알고리즘이 될 수 있다는 것이다. 특히 경우의 수가 문제의 복잡도에 따라 기하급수적으로 증가하는 경우, 문제를 해결하는 데에 필요한 자원 역시 기하급수적으로 증가한다.

이 때문에 실제로 브루트 포스는 문제의 규모가 현재의 자원으로 충분히 커버가 가능한 경우에만 쓰이고, 대부분은 동적 계획법 등으로 많이 우회하는 편이다. 심지어는 정확도를 조금 희생해더라도 어떻게든 '이론상 가능한' 자원으로 해결할 수 있게 알고리즘을 설계하기도 한다. 후에 언급할 사전 공격 역시 정확도가 약간 희생된 것이다.

이러한 단점은 대부분의 암호화 알고리즘에서 역이용하고 있는데, 무어의 법칙 덕분에 컴퓨터 성능이 꾸준히 개선되고 있다 해도 그만큼 더 복잡한 암호화 기법을 이용하면 되기 때문이다. 현 세대의 암호화 기법을 브루트 포스로 다 뚫는다 해도, 그 시간이 지나고 나면 이미 구식도 아닌 구석기 알고리즘으로 전락해 있을 법하니 그만큼 시간을 충분히 벌 수 있는 것이다.

실제로 현재 가장 흔하게 사용되는 블럭암호인 AES 기반 암호화들의 경우에는 Weak Key를 사용하지 않는 이상 키를 모르는 이상 유의미한 시간 내에 풀 수 없으며, AES-256의 경우는 초당 100경(10^18) 개의 키 대입을 하는 슈퍼컴퓨터로도 3000극(3 * 10^51) 년은 족히 잡아먹는다. 아직 AES-128이 완전히 깨졌다는 보고가 없는데도 하나둘씩 AES-256으로 갈아타는 이상, AES-128이 다 깨질 때 쯤이면 이미 대다수가 AES-32k, 많이 봐 줘도 AES-2k를 쓰고 있을 판이 되는 것이다.(…)

암호학에서의 브루트 포스

앞서 언급했듯, 주로 암호학에서 사용 암호화에 사용되는 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와 같은 눈에 잘 보이지 않는 서비스에 대해서는 비정상적인 로그인 시도를 막지 않아서 사용자 계정이 털리는 경우가 있다.]

유사한 방식

위에서도 나오듯이 정말로 처음부터 끝가지 무작위 공격을 하는것은 시간이 오래 걸리고 비효율적이며, 특정 대상을 지정하는게 아닌 "최대한 대량"의 계정에 대한 공격을 수행하기에는 불필요하다. 왜냐하면 100개의 계정을 공격 해서 1개를 뚫을 시간에 100000개의 계정을 공격해서 1개를 찾는게 시간적으로도 빠르기 때문이다. 따라서 암호를 대입할 때 a, b, c, .... aa, ab, ac..... ba, bb, bc, .... 와 같은 모든 가능한 조합을 대입하는 방법 대신 사용자들이 많이 쓰는 암호를 - 예를 들자면 abcd, 1234, qwert, q1w2e3, .... - 모아서 대입하는 방법도 많이 쓰이는데, 이를 사전 공격(Dictionary attack)이라고 한다.

방어 방법

다른 사람에게 브루트 포스로 암호가 털리는 것을 원치 않는다면, 다음 사항을 지키자.

• 암호는 최소 10자리 이상을 사용하자. 암호가 12자리를 넘어간다면 슈퍼 컴퓨터를 가져와도 안전하다.
• 암호에 특수문자를 사용하면 좀더 좋겠지만, 특수 문자 안 쓰고 그냥 암호가 길기만 해도 된다. 아무리 특수 문자를 써도 암호가 6자리 이하라면 털릴 것을 각오해야 한다.
• 대부분 사전 공격부터 가하기 때문에 최소한 다음과 같은 단어들을 쓰는것은 자살행위이다. 브루트 포스 툴인 John The Ripper의 내장 사전파일의 맨 앞의 일부는 다음과 같다. 123456, abc123, password, computer, a1b2c3, qwerty, secret. 이것 말고도 3천여게정도 더 있으니 차라리 단어를 좀 섞자.
• 여러 단어를 조합해서 만든 패스워드는 기억하기 쉽고 의외로 엔트로피가 높다. [[1]] 사전공격이 걱정 된다면 일반적이지 않은 문자열을 넣어주면 좋다.
• 문장도 기억하기 어렵지 않고 사전공격에 강한 편이다. 단, iloveyou처럼 너무 정상적이거나 유명한 문장은 털리기 쉬울 수 있으므로 약간 비틀어 넣는 것이 좋다.