mir.pe (일반/밝은 화면)
최근 수정 시각 : 2024-12-08 20:09:31

브루트 포스

무차별 대입에서 넘어옴

[[컴퓨터공학|컴퓨터 과학 & 공학
Computer Science & Engineering
]]
[ 펼치기 · 접기 ]
||<tablebgcolor=#fff,#1c1d1f><tablecolor=#373a3c,#ddd><colbgcolor=#0066DC><colcolor=white> 기반 학문 || 수학( 해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학( 환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학( 형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 ||
하드웨어 구성 SoC · CPU · GPU( 그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품
기술 기계어 · 어셈블리어 · C/ C++ · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시( SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속
연구

기타
논리 회로( 보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영 체제 · 데이터베이스 · 프로그래밍 언어{ 컴파일러( 어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩( 유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도( 최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리( 기계 번역 · 음성인식) · 버전 ( 버전 관리 시스템 · Git · GitHub)

1. 암호 해독법
1.1. 특징1.2. 예시1.3. 자원1.4. 암호학에서의 브루트 포스1.5. 로우 앤 슬로우 브루트포스1.6. 실제적인 예시1.7. 유사한 방식1.8. 방어 방법1.9. 수학계에서 사용1.10. 관련 문서
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자리인 영문 대소문자, 숫자를 충족하는 사전파일을 만들면 그 텍스트 파일의 용량은 약 8×348 바이트이며, 이것을 테라바이트로 환산해보면 대략 14.28TB(=12.99TiB)가 나온다.

만약 해당 사전파일을 만들려 한다면, 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배 더 복잡하다.

또한, 시도할 수 있는 횟수나 시간이 제한되어 있거나 틀렸을 때 패널티가 큰 경우는 사용하기 힘들다.

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. 로우 앤 슬로우 브루트포스

최근에는 대부분의 대형 사이트는 특정 시간 내에 로그인 실패 횟수가 많으면 계정이 잠기거나 IP 차단이 되는 식의 보안조치가 되어 있다. 이를 횟수 제한 (Rate Limiting) 방어법이라고 한다. 그러나 해커가 특정 시간 동안에 무작위 대입을 통한 로그인 시도 횟수를 줄인다면 어떻게 될까? 임계치 이하로 로그인 시도 간격을 늘리면 횟수 제한 필터를 회피할 수 있다. 이러한 방법으로 5회 시도하고 차단되는게 아니라 500번을 시도하고도 차단당하지 않을 수 있다. 이렇게 짧고 느리지만 꾸준한 공격 방식을 로우 앤 슬로우 (Low and Slow)라고 한다.

1.6. 실제적인 예시

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

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

암호는 아니지만, 이와 비슷한 방식으로 과거에 해외에서 로또 금액이 이월되면서 당첨금이 어마어마하게 불어나자 한 보험사에서 모든 로또 번호를 사서 당첨되기를 시도했다! 다만 시간 문제로 인해 전체 번호의 70%밖에(...) 모으지 못했지만 그 70% 중에 당첨 번호가 있어서 결국 당첨. 당첨금을 받아 갔다. 그러나 이월되지 않으면 전체 번호를 사면 손해다. 한국 로또는 이월이 되어도 금액이 크지 않으니 하지 말자.

비트코인 같은 작업증명 방식 암호화폐를 채굴하는 것도 사실상 무차별 대입의 일종이다.

1.7. 유사한 방식

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

1.8. 방어 방법

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

1.9. 수학계에서 사용

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

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

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

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

골드바흐의 약한 추측을 증명하는 데에도 사용되었는데, 1030보다 큰 수에 대해서 성립함을 수학적으로 증명한 후 브루트 포스로 이보다 작은 수에는 반례가 없음을 증명했다. 슬프게도 강한 추측에 대해서는 400경까지 대입해도 반례가 없었다(...).[6]

바쁜 비버 문서 내용에 따르면 현재 풀리지 않은 일부 난제들도 유한 번의 수 이내의 연산만으로 증명이 될 수 있다고 한다. 그 '유한 번'의 연산이 우주가 멸망할때까지도 해낼 수 없는 수리 문제일 뿐(…)

1.10. 관련 문서

2. 비디오 게임

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

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


[1] 0000~1999는 1번 컴퓨터 (혹은 코어), 2000~3999는 2번 컴퓨터 이런 식. [2] 일(一) - 만(萬) - 억(億) - 조(兆) - 경(京) - 해(垓) - 자(秭) - 양(壤) - 구(溝) - 간(澗) - 정(正) - 재(載) - 극(極), 각 단위의 차이는 만 배이다. [3] 전화・대면・우편 등 [4] 인증서, OTP, 이메일 등 [5] 무려 1해(...)까지 대입했는데도 반례가 없어 증명에는 실패했다. [6] 반례가 없는 건 절대로 좋은 게 아니다. 어차피 수는 무한히 커질 수 있기 때문에 대입으로 '언제나 성립'이 참이라고 증명할 수는 없다. 오히려 반례가 하나라도 나오면 그 명제가 거짓임을 증명할 수 있어서 더 좋다. [7] 윙커맨더 개발자인 크리스 로버츠가 오리진 시스템즈 퇴사 후 세운 회사.