최근 수정 시각 : 2022-04-27 21:53:59

브루트 포스

{{{#!wiki style="margin: -5px -10px; padding: 10px 0px; color:#fff; background-image: linear-gradient(to right, #33CCCC , #0066DC); word-break:keep-all"
컴퓨터 과학 & 공학
Computer Science & Engineering

{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-8px -1px -11px"
<tablewidth=100%><colbgcolor=#eee,#555>기반 학문 <colbgcolor=#fff,#1f2023> 수학 ( 공업수학 · 해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 대수학 ( 환론 · 범주론) · 정수론) · 암호학 · 전자공학 · 언어학 ( 형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학
SoC · CPU · GPU( 그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품
기술 기계어 · 어셈블리어 · C( C++ · C#) · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍( 디자인 패턴) · 해킹 · ROT13 · OTP · IoT · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시( SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화
연구 논리 회로( 보수기 · 가산기 · 불 대수 · 플립플롭) · 이론전산학 · 알고리즘 · 자료구조 · 데이터베이스 · 프로그래밍 언어{ 컴파일러( 어셈블러 · JIT) · 인터프리터 · 유형 이론} · 메타데이터 · 딥러닝 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩( 유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도( 최적화) · 소프트웨어 개발 방법론 · 정보처리이론 · 오토마타 이론 · 재귀 이론 · 자연 언어 처리( 기계 번역 · 음성인식) }}}}}}}}}

1. 암호 해독법
1.1. 특징1.2. 예시1.3. 자원1.4. 암호학에서의 브루트 포스1.5. 실제적인 예시1.6. 유사한 방식1.7. 방어 방법1.8. 수학계에서 사용1.9. 관련 문서
2. 비디오 게임

1. 암호 해독법

브루트 포스(brute force), 키 전수조사(exhaustive key search) 또는 무차별 대입(無差別代入)은 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 흔히 암호학에서 연구되나, 다른 알고리즘 분야에서도 사용되고 있다.

흔히 수학 문제를 원시적으로 푸는 방법인 ' 수 대입 노가다'의 학술적 버전이다.

1.1. 특징

영어로 brute는 "짐승 같은, 난폭한"이라는 뜻이고, brute-force는 "난폭한 힘, 폭력"이라는 뜻이다. 오래 걸리는 데다 자원이 엄청나게 들어서 얼핏 보면 무식하다고 생각할 수도 있겠지만, 항상 정확도 100%를 보장한다는 점에서 암호 해독법 중 가장 확실하고 무서운 방법이다. 이론적으로 가능한 모든 경우의 수를 다 검색해 보는 것이라 정확도 100%가 항상 보장되니, 암호학에서는 가장 확실한 방법으로 통용되고 있다. 무엇보다도 암호 확인 작업은 손으로 입력한 문자열의 동일 여부를 확인하는 것이기 때문에, 가능한 경우의 수를 하나씩 대입하다 보면 언젠가는 암호를 찾을 수 있게 되는 식이다. 다만 정말로 그냥 무식하게 때려 박는 건 아니고, 숫자만 섞어서 대입해 보기 한 번, 로마자만 섞어서 대입해 보기 한 번 이런 식으로 하다가 안 되면 나머지를 순차적으로 하는 식으로 특정 규칙에 따라 우선순위를 두고 하기도 한다.

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

90년대 초 김재열이 ‘청와대 해킹사건’을 저지르는 과정에서 국세재판소 비밀번호를 알아낼 때 이런 식으로 일일이 노가다를 했다. 그렇게 알아낸 패스워드는 12345.진짜로 0부터 하나씩 시도했으면 어이 터졌을 듯하다

1.2. 예시

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

실제로 DES의 경우, 개발 당시에는 무결점 알고리즘이었으나 컴퓨터 성능이 크게 개선된 지금은 브루트 포스로도 다 뚫린다. 속도는 물론이고, 공격에 필요한 DES 사전 용량 역시 현재의 컴퓨터 환경에선 충분히 감당할 수 있기 때문. 이 때문에 한때 3번 DES를 돌려서 대응하기도 했지만, 이마저도 Sweet32 공격이라는 변종 브루트 포스에 다 뚫린 탓에 2018년에 이미 사장되었다. ( 공식 은퇴 기사, Sweet32 공격 설명(위키백과)) MD5 역시 컴퓨터의 발전 때문에 진작에 다 뚫린지라 이미 SHA 등 보다 안전한 해시 알고리즘으로 갈아탄 상태이다. 대신 MD5는 연산 속도가 빠르다는 장점 때문에 파일 무결성 검사 용도로 아직도 절찬리에 사용 중이다.

1.3. 자원

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

보통 비밀번호로 자주 쓰이는 자릿수가 최대 8자리인 영문 대소문자, 숫자를 충족하는 사전파일을 만들면 그 텍스트 파일의 용량은 348 바이트이며, 이것을 GB로 환산해보면 대략 1663GB가 나온다.

만약 해당 사전파일을 만들려 한다면, 4~8GB 단위로 파일을 끊어서 저장하지 않는 한 오버플로 또는 저장공간의 용량 부족이 일어날 것이다. 또한 저것을 대입하는 것도 똑같다. 다시 말해서 웬만한 비밀번호를 다 뚫을 수 있는 사전파일을 만들고 실제로 사용하려면 양자컴퓨터 기술과 초고용량 메모리/저장장치가 대중화되어야 한다. 위와 같은 초고사양 양자컴퓨터가 대중화되면 AES도 깨지게 된다

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

때문에 체스 바둑과 같이 경우의 수가 많은 경우, 일반적으로 브루트 포스를 쓰지 않고 AI나 알고리즘을 통해 보다 효율적으로 접근한다. 하지만 이보다 훨씬 규칙이 간단한 체커의 경우 실제로 컴퓨터를 이용한 브루트 포스로 18년간 계산하여 모든 경우의 수를 분석했다. 결과는 양쪽 모두 최선의 플레이를 하면 무조건 비긴다는 것.

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

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

실제로 현재 가장 흔하게 사용되는 블록암호인 AES 기반 암호화들의 경우에는 Weak Key를 사용하지 않는 이상 키를 모르면 유의미한 시간 내에 풀 수 없으며, AES-256의 경우는 초당 100(1018) 개의 키 대입(= 1 엑사플롭스)을 하는 슈퍼컴퓨터로도 3000(3×1051)년[2]은 족히 잡아먹는다. 아직 AES-128이 완전히 깨졌다는 보고가 없는데도 하나둘씩 AES-256으로 갈아타는 이상, AES-128이 다 깨질 때쯤이면 이미 대다수가 AES-32k, 많이 봐줘도 AES-2k를 쓰고 있을 판이 되는 것이다. 사족으로 AES-2K/AES-2048에서 가능한 키 대입 경우의 수는 22048으로, AES-256보다 문제가 21792배 더 복잡하다.

또한, [math(n)]번 안에 풀지 못할 시 자폭하거나 데이터를 삭제하는 등의 프로그램이면 때려 넣기를 하기가 힘들다. 물론 공인인증서처럼 우회가 가능하면 예외이다

1.4. 암호학에서의 브루트 포스

앞서 언급했듯, 주로 암호학에서 사용 암호화에 사용되는 key나, 찾고자 하는 비밀번호가 길수록 시간이 기하급수적으로 증가한다.

조합 가능한 모든 문자열을 대입하기 때문에 아무리 컴퓨터가 빠르다고 하더라도 시간이 매우 많이 걸린다. 당장 영문 소문자 + 숫자 조합만 쳐도 [math(n)]자리의 암호를 뚫는 데에는 [math(\mathcal{O}(36^n))]의 시간이 걸린다. 즉, 10글자만 되어도 3610 = 3,656,158,440,062,976 가지가 된다. 이 정도면 쉬운 암호 알고리즘이라 해도 초당 1억 번 계산 기준 대충 14개월 걸리는 수준이다. 물론 암호가 더 복잡하거나 길이가 더 길어지면 수백~수천 년은 기본으로 기다려야 한다.

좀 더 확장시켜서 암호로 입력할 수 있는 알파벳의 수를 [math(k)]개라 치면, 이를 조합한 [math(n)]자리 암호를 뚫는 데에는 [math(\mathcal{O}(k^n))]의 시간이 걸리니 P-NP 문제로 치면 이 문제는 EXP 완전 문제가 된다. 사정이 이러니 낭비되는 시간을 최소화하려고 도입한 게 레인보우 테이블인데, 입력할 때마다 계산(특히 해시 함수)하는 대신 미리 계산된 테이블을 참조하는 것이기 때문에 시간이 훨씬 단축되는 것이다. 물론 풍선 효과로 인해, 저장공간이 아주 많이 희생된다.

1.5. 실제적인 예시

예를 들어 예전 하나 워드 같은 프로그램은 문서에 암호를 걸어 놓고 문서 파일을 헥스 에디터로 열어보면 암호가 문서 파일 헤더에 적혀있는 것을 볼 수 있다. 즉, 데이터는 그대로 평문인 채 액세스만 막아 놓고 프로그램에서 사용자에게 암호를 물어보아 암호가 동일하면 문서 파일을 보여주는 구조이기 때문에 암호를 아무리 어렵게 설정해도 헤더 변조로 손쉽게 암호를 우회할 수 있다.

하지만, 아래아 한글, MS워드 등 현대에 많이 쓰는 문서 포맷은 데이터를 모두 암호화했기 때문에 헥스 에디터로 뜯어도 암호를 통과하는 방법 따위는 존재하지 않고, 암호를 하나씩 대입해서 풀어보는 것 이외에는 우회 방법 따위는 존재하지 않는다. 따라서 이런 파일의 암호를 풀어주는 간단한 프로그램들은 그냥 브루트 포스를 수행하는 프로그램으로 봐도 무방하며, 해커들이 웹페이지에 로그인을 시도할 때에도 자주 사용된다. 브루트 포스 방식을 이용한 공격은 암호가 걸린 문서나 압축 파일의 암호를 해독하는 데도 사용하지만, 온라인 로그인이 필요한 서비스에도 역시 동일한 방식으로 공격할 수 있다. 만일 서버에서 비정상적인 인증 시도를 막는 대비책이 없으면 될 때까지 무제한으로 대입해서 암호를 알아낼 수 있기 때문에 제정신을 가진 서버 관리자+프로그래머라면 비정상적인 로그인 시도에 대해서는 항상 대비를 해야만 한다. 간혹 웹페이지를 통한 비정상적인 로그인 시도에 대해서는 차단을 하지만, POP3와 같은 눈에 잘 보이지 않는 서비스에 대해서는 비정상적인 로그인 시도를 막지 않아서 사용자 계정이 털리는 경우가 있다. telnet이나 ssh 등으로 유닉스 서버에 로그인할 때 암호가 틀리면 패스워드를 재차 묻는 프롬프트가 다시 떨어지기 이전에 약간의 시간 지연이 있는 이유도 브루트 포스 공격을 막기 위함이다.

암호는 아니지만, 이와 비슷한 방식으로 과거에 해외에서 로또 금액이 이월되면서 당첨금이 어마어마하게 불어나자 한 보험사에서 모든 로또 번호를 사서 당첨되기를 시도했다! 다만 시간 문제로 인해 전체 번호의 70%밖에(...) 모으지 못했지만 그 70% 중에 당첨 번호가 있어서 결국 당첨. 당첨금을 받아 갔다. 그러나 이월되지 않으면 전체 번호를 사면 손해다. 한국 로또는 이월이 되어도 금액이 크지 않으니 하지 말자.
  • 미국 FBI도 이 방법을 이용해 아이폰의 암호를 풀기도 했다.
    다만, 낸드 메모리 자체를 복제(낸드 미러링)해서 해결 기회 자체를 늘리는 방법을 통해 횟수 제한을 회피했다고 추측된다. # ##
    하지만, 낸드 미러링으로는 성공하지 못했다는 기사도 있다. 현재는 Secure Enclave에 비밀번호를 저장하기 때문에 불가능하다. 다만 이것도 무력화가 가능하니 가능하면 긴 비밀번호를 사용하는 것이 좋다.

1.6. 유사한 방식

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

1.7. 방어 방법

다른 사람에게 브루트 포스로 암호가 털리는 것을 원치 않는다면, 다음 사항을 지키자.
  • 암호는 최소 10자리 이상을 사용하자. 암호가 12자리를 넘어간다면 슈퍼컴퓨터를 가져와도 안전하다. 숫자만으로 이루어져 있다 해도 암호 한 자리당 경우의 수가 10배씩 늘어난다. 12자리이면 1012이며 영문 대소문자 섞은 12자리라면 경우의 수는 (대문자 26개+소문자 26개+숫자 10개=62)12=3.2262667624×1021)가 된다. 이러면 태양의 수명이 다할 때까지 시도해도 못 뚫는다.
  • 암호에 특수문자를 사용하면 좀 더 좋겠지만, 특수 문자 안 쓰고 그냥 암호의 길이가 길기만 해도 된다. 일반적인 키보드로 입력 가능한 특수문자 32개를 알파벳과 숫자와 섞어 8자리 암호를 만들면 경우의 수는 948(= 6.0957×1015)이다. 반면 알파벳과 숫자만 사용하는 대신 자릿수를 하나 늘리면 경우의 수는 629(= 1.3537×1016)이다. 자릿수를 하나 늘리는 게 2.22배가량 효과가 더 좋다는 뜻이다. 단 이게 일정한 건 아니고 자릿수가 늘어날수록 특수문자를 섞는 쪽이 점점 유리해진다. 물론 가장 좋은 방법은 특수문자를 섞어서 길게 짜는 것이다.
  • 대부분 사전 공격부터 가하기 때문에 최소한 다음과 같은 단어들만 쓰는 것은 자살행위이다. 브루트 포스 툴인 John The Ripper의 내장 사전 파일의 맨 앞의 일부는 다음과 같다. 123456, abc123, password, computer, a1b2c3, qwerty, secret. 그리고 군사기밀 1q2w3e4r 이것 말고도 3천여 개 정도 더 있으니 차라리 단어를 좀 섞자.
  • 여러 개의 관련 없는 단어를 조합해서 만든 암호는 길이가 길며 무작위적이므로 이 방식으로는 깨기가 힘들며, 사용자가 기억하기에도 어렵지 않다. # 사전 공격이 걱정된다면 일반적이지 않은 문자열을 넣어주면 좋다. 같은 이유로 문장도 기억하기 어렵지 않고 사전 공격에 강한 편이다.
  • 외국계 해커 상대로는 한타를 영타 그대로 치는 것도 좋은 방법이다. 중간에 시프트가 필요한 쌍자음이 있으면 금상첨화. 숫자랑 특문을 넣으면 거의 뚫리지 않는다고 보면 된다. 물론 자신이 한국인이라는 게 알려지는 순간 사전공격으로 단숨에 뚫릴 수 있다. 한국 사이트에서는 하지 말자. 외국어 좀 하는 사람이라면 약간 마이너한 제3의 언어 독음(외국어 표기법에 안 맞는다면 더욱 좋다)을 한국어로 읽어서 영타 그대로 치는 식의 방법도 괜찮다. 아니면 Base64 같은 걸로 인코딩해 버리거나 뷁어 번역기 같은 걸로 외국어 문자열을 깨뜨린 뒤 Ctrl CV해도 된다.
  • 오류 횟수가 초과되면 접속을 차단하는 방어 방법이 먹힌다. 웬만한 사이트나 전자거래에서는 암호를 잘못 입력한 횟수가 특정한 수를 넘을 경우 계정이 일시적으로 잠기게 된다. 민감한 분야(인터넷 뱅킹이나 신용카드 결제처럼)에서는 아예 오프라인으로 인증을 받지 않고서는 다시 서비스를 사용할 수 없도록 설정한다. 이럴 경우는 브루트 포스가 쉽지 않다. 사실 오래전에는 웬만한 포털도 브루트 포스로 크래킹이 가능했던 때가 있었다. 스마트폰도 비밀번호를 계속 틀리면 해당 기기에 연결된 계정을 통해 인증을 받아야만 잠금이 해제되거나, 아예 데이터를 싹 지워버리는 방어 체계를 제공한다. 그러나 보안 취약점 공격을 통해 이를 우회하는 것이 가능하기 때문에 기본적으로는 안전한 비밀번호를 사용하고 이는 보조적인 방어 수단으로만 생각하는 것이 좋다.
  • 브루트 포스는 보통 비트 순서대로 대입하는데, 첫 글자의 비트 크기에 따라 비밀번호가 뚫리는 시간이 크게 차이 난다. 예를 들어서 아스키코드 65인 대문자 A로 시작하는 비밀번호와 아스키코드 122인 소문자 z로 시작하는 비밀번호는 깨지는 속도가 두 배 가까이 차이 난다. 심지어는 프로그램에서 로마자만 따질 경우 A보다 z로 하는 것이 50배 넘게 이득이 된다. 거의 글자 하나 있고 없고의 차이가 난다. 대신 정방향과 역방향을 번갈아 가면서 대조하면 소용없다

1.8. 수학계에서 사용

수학계에서 이런 무식한 방법을 쓰겠냐 싶지만, 의외로 널리 쓰인다. 한마디로 문서 상단의 노가다(수학)의 내용 그 자체다.

일단 반례를 찾아내기 위해서 쓰인다. 컴퓨터로 다룰 수 있을 만한 작은 수 범위 내에서 반례가 등장하면 그것으로 증명이 끝나기 때문이다.

또한, 반대로 일정 범위 이내에는 반례가 없음을 보이기 위해서도 사용된다. 참일 것 같은데도 여전히 증명 안 되는 문제들에 대해서 꼬박꼬박 나온다. 골드바흐 추측, 콜라츠 추측 같은 경우에 언급이 있고, 페르마의 마지막 정리에서 컴퓨터를 이용한 방법이 나온다.

다만, 완전히 브루트 포스만으로 문제를 해결한 경우는 흔치 않은데, 4색정리가 이에 해당한다. 지도에서 가능한 모든 경우의 수를 분류하고, 각각에 대해서 4색 정리가 성립한다는 것을 보이는 방법으로 증명했다.

골드바흐의 약한 추측에서도 사용되었는데, 1030보다 큰 수에 대해서 성립함을 수학적 증명으로 보였다. 그리고, 이보다 작은 수는 컴퓨터를 동원해서 반례가 없다는 것을 보이면서 해결되었다.

1.9. 관련 문서

2. 비디오 게임

2003년 Xbox 독점작으로 출시된 3인칭 액션 게임이다. 당시 마이크로소프트 게임 스튜디오 산하의 디지털 앤빌[3]이 개발한 게임으로, 기어스 시리즈가 나오기 전에 XBOX 진영 3인칭 슈터중 그런대로 이름이 알려진 게임인듯 하다. 한국에서도 더빙 한글화를 통해 정발했다. 관련 기사

PC로도 이식하려고 했으나 취소되었다는 듯하다.


[1] 0000~1999는 1번 컴퓨터 (혹은 코어), 2000~3999는 2번 컴퓨터 이런 식. [2] 일(一) - 만(萬) - 억(億) - 조(兆) - 경(京) - 해(垓) - 자(秭) - 양(壤) - 구(溝) - 간(澗) - 정(正) - 재(載) - 극(極), 각 단위의 차이는 만 배이다. [3] 윙커맨더 개발자인 크리스 로버츠가 오리진 시스템즈 퇴사 후 세운 회사.