무차별 대입 공격 (Brute Force Attack)

개요

무차별 대입 공격이란 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 문제를 푸는 것인데, 얼핏 무식하다고 생각할 수도 있겠지만 항상 정확도 100%를 보장한다는 점에서, 자원만 충분하면 가장 무서운 방법입니다. 이론적으로 가능한 모든 경우의 수를 다 검색해 보는 것이라 정확도 100%가 항상 보장되니, 암호학에서는 가장 확실한 방법으로 통용되고 있습니다. 무엇보다도 암호 확인 작업이라는 것이 손으로 입력한 문자열의 동일 여부를 확인하는 것이기 때문에, 가능한 경우를 하나씩 대입하다 보면 언젠가는 암호를 찾을 수 있게 되는 식입니다. 다만 정말로 그냥 무식하게 하는건 아니고, 숫자만 섞어서 대입해보기 한번, 로마자만 섞어서 대입해보기 한번 이런식으로 하다가 안되면 나머지를 순차적으로 하는 식으로 특정 규칙에 따라 우선순위를 두고 하기도 합니다.

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

단점

자원이 가장 큰 문제이며, 브루트 포스 방법에는 문제의 복잡도에 매우 민감하다는 치명적인 단점을 지니고 있습니다. 문제가 조금만 복잡해져도 매우 비효율적인 알고리즘이 될 수 있다는 것입니다. 특히 경우의 수가 문제의 복잡도에 따라 기하급수적으로 증가하는 경우, 문제를 해결하는 데에 필요한 자원 역시 기하급수적으로 증가합니다.

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

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

방어방법

• 암호는 최소 10자리 이상을 사용. 암호가 12자리를 넘어간다면 슈퍼 컴퓨터를 가져와도 안전. 숫자만으로 이루어져있다 해도 암호 한 자리당 경우의 수가 10배씩 늘어나고 12자리이면 10^12.

• 암호에 특수문자를 사용하면 좀더 좋겠지만, 특수 문자 안 쓰고 그냥 암호가 길기만 해도 됨. 아무리 특수 문자를 써도 암호가 6자리 이하라면 털릴 것을 각오해야 함.

• 대부분 사전 공격부터 가하기 때문에 최소한 다음과 같은 단어들을 쓰는 것은 자살행위. 브루트 포스 툴인 John The Ripper의 내장 사전 파일의 맨 앞의 일부는 다음과 같음. 123456, abc123, password, computer, a1b2c3, qwerty, secret. q1w2e3r4! 이것 말고도 3천여개 정도 더 존재.

• 사전 공격에서도 브루트 포스 기술을 동시 적용하면 단어 몇개 배열해놓은 건 뚫리는 건 금방.

• 단어조합이 힘들다면, 외국계 해커 상대로는 한타를 영타 그대로 치는 것도 좋은 방법. 중간에 쉬프트가 필요한 쌍자음이 있으면 금상첨화. 숫자랑 특문을 넣으면 거의 뚫리지 않는다고 보면 됨.

• 웬만한 사이트나 전자거래에서는 일정 횟수 이상 암호를 잘못 입력할 경우 계정이 일시동결. 민감한 분야에서는 대면적 방법으로 새로 인증을 받지 않고서는 다시 서비스를 사용할 수 없게 해 놓기까지 함. 이럴 경우는 브루트 포스가 쉽지 않음.

• 브루트 포스의 경우 마구 대는 게 아닌 비트 순서대로 대는 것인데, 이를 역이용해서 첫 글자의 비트 크기에 따라 비밀번호가 뚫리는 시간은 크게 차이남. 예를 들어서 아스키 코드 65인 대문자 A로 시작하는 비밀번호와 아스키 코드 122인 소문자 z로 시작하는 비밀번호는 깨지는 속도가 두 배 가까이 차이남. 심지어는 프로그램에서 로마자만 따질 경우 A보다 z로 하는 것이 50배 넘게 이득이 된다. 거의 글자 하나 있고 없고의 차이. 다만 이 방법은 현실적으로 힘든 편. 자신의 비밀번호가 원래부터 이랬다면 좋았겠지만 이미 쓰던 비밀번호를 바꾸는 것은 심히 좋지 않음.