[개념정리]브루트 포스_nabi

기록용

3줄 TMI

융합보안 논문 경진대회 준비를 위해 슬슬 양자컴퓨터에 대해 공부해야한다. 양자컴퓨터의 정의 정도는 알지만 그 이외내용은 찾아본적도, 공부해본 적도 없었다. 시험기간이 되니 느끼는 건데 동아리 활동이나 스터디 활동이 훨씬 힘들긴 해도 공부하는 과정은 비교도 안되게 재밌는 것 같다.

 

---

Brute force란 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법 - 나무위키

나무위키에서는 브루트 포스의 정의를 위와 같이 표현하고 있지만 알고리즘의 측면에서 본다면  그 예시로 완전 탐색 알고리즘을 들 수 있다. 즉, 모든 경우의 수를 비교해보고 답을 찾아내는 알고리즘이다. (친구와 스터디 진행 후 좀 더 보완을 하면) 완전 탐색 알고리즘의 종류 중 브루트 포스가 있다는 말도 있고 완전 탐색 알고리즘을 뜻하는 게 브루트 포스라는 말도 있다. 사실 이 둘을 구분하는게 그렇게 의미가 있을 것 같진 않지만 나중을 위해..

예를 들어 100이하의 숫자 중 % 3 계산을 했을 때 나머지가 1이 되는 숫자를 모두 찾아라 같은 문제가 있습니다. 1부터 100까지 모두 % 3 계산을 한 후 나머지가 1이 되는 경우를 찾으면 된다.

 

이렇게 단순한 알고리즘의 장점은 무엇이 있을까?

모든 경우의 수를 계산하고 비교해보기 때문에 정답을 찾을 확률이 100%이다. 또 구현이 다른 알고리즘에 비해 쉽다. 

 

하지만 장점이 있는만큼 단점도 있다.

데이터 범위에 따라 시간이 오래 걸릴 수도 짧게 걸릴 수도 있다. 예를 들어 1부터 100까지의 합을 구하는 경우 컴퓨터는 굉장히 빠르게 계산을 할 것이다. 하지만 만약 1부터 1억까지의 합을 구할 경우에는 1부터 100까지의 합을 구하는 경우보다 더욱 많은 시간이 걸릴 것이다.

 

따라서 브루트 포스 사용할 때는 데이터의 범위가 작은 문제에 한해서 사용해야한다.

 

---

브루트 포스는 굉장히 간단한 알고리즘이기에 여기서 설명을 끝내겠다. 

보안 분야에 많은 관심이 있는 사람으로서 브루트 포스 공격을 언급 안하고 넘어가면 아쉬울 것 같다.

브루트 포스 공격은 위 나무 위키에서 정의한 공격과 같다. 다른 말로는 무차별 대입 공격이라고도 한다.

또 대부분의 암호화 방식은 이론적으로 이런 무차별 대입 공격에 대해 안전하지 못하다. 

 

그럼 왜 암호화를 하는지 의문이 생길 것이다.

이론적으로 무차별 대입 공격을 하면 언젠가 키를 찾아낼 수 있다. 하지만 키 길이에 따라 바로 찾을 수도 몇천년이 걸릴 수도 있다. 대부분의 암호화 방식은 이러한 시간적 문제로 인해 키를 찾을 수 없다. 반대로 시간적 문제가 해결 된다면 키를 찾기 쉬워진다. 예를 들어 RSA 암호화 방식은 현재 컴퓨터의 성능으로 키를 찾을 수 없다. 너무 많은 시간이 소요되기 때문이다. 하지만 양자컴퓨터가 개발된다면 많은 연구원들은 RSA 암호와 같은 비대칭키 암호화 방식들이 무용지물이 될 것으로 보고 있다. 위에서 말한 시간적 문제가 해결되었기 때문이다.

 

무차별 대입 공격의 유형

역 무차별 대입 공격 : 많은 계정을 대상으로 소수의 흔한 비밀번호를 반복 시도한다.
인증 정보 스터핑 : 사이트 또는 서비스에서 훔친 사용자 이름과 비밀번호를 사용해 다른 서비스와 애플리케이션의 계정을 하이재킹한다.
사전 공격 : 사전의 단어 또는 다른 데이터 침해에서 얻은 일반적인 비밀번호를 돌아가면서 시도한다.
레인보우 테이블 공격 : 공격자는 평문 비밀번호와 각 비밀번호의 해시값이 저장된 사전 계산된 사전을 사용해 해싱 함수를 반대로 되돌려 비밀번호를 알아낸다. 
- https://www.itworld.co.kr/news/156683 

무차별 대입 공격 방어 방법

길고 복잡하며 암호화된 비밀번호를 사용한다(256비트 암호화가 이상적).

비밀번호 해시에 솔트(salt)를 넣는다. 엠은 "문자열을 별도의 데이터베이스에 저장하고 비밀번호를 해시하기 전에 불러와 추가하는 방법으로 같은 비밀번호를 사용하는 직원이 서로 다른 해시를 갖도록 해야 한다"라고 말했다.

비밀번호 복잡성과 여러 계정에서의 비밀번호 재사용에 관한 정책을 직원에게 명확하게 전달한다.

특정 시간 내의 로그인 시도 횟수를 제한하거나 특정 횟수의 부정확한 시도 이후 비밀번호 재설정을 의무화한다.

비밀번호 인증에 속도 제한을 적용한다.

캡차(captcha)를 활성화한다.

가능한 경우 다중 요소 인증을 활성화한다.

가급적 비밀번호 관리자를 사용한다.
- https://www.itworld.co.kr/news/156683

 

대표 이미지 출처 : https://pixabay.com/ko/?utm_source=link-attribution&utm_medium=referral&utm_campaign=image&utm_content=1653351">Pixabay로부터 입수된 https://pixabay.com/ko/users/200degrees-2051452/?utm_source=link-attribution&utm_medium=referral&utm_campaign=image&utm_content=1653351">200 Degrees님의 이미지 입니다.