사전 공격과 레인보 테이블

딕셔너리 공격은 가능한 모든 조합을 시도하는 것이 아니라, 잘 선별된 가능성 있는 비밀번호 목록을 시도합니다. 실제 사용자들은 일반적인 단어, 이름, 날짜, 구문과 같은 제한된 어휘 내에서 비밀번호를 선택합니다. 백만 개의 가능성 있는 비밀번호로 이루어진 워드리스트를 테스트하는 것은 모든 가능한 8자리 문자열(200조 개의 조합)을 테스트하는 것보다 훨씬 빠릅니다. 딕셔너리 공격이 성공하는 이유는 인간의 비밀번호 선택이 예측 가능하기 때문입니다.

2009년, 소셜 네트워킹 사이트 RockYou는 데이터 유출 사고를 겪었고, 이로 인해 3천 2백만 명의 사용자 비밀번호가 평문(plaintext)으로 노출되었습니다. 그 결과 생성된 목록은 현재 `rockyou.txt`라고 불리며, 약 1천 4백만 개의 고유한 비밀번호를 포함하고 있고, 비밀번호 크래킹(password cracking)에 사용되는 표준적인 첫 번째 워드리스트(wordlist)입니다. `rockyou.txt`를 살펴보면, 가장 흔한 비밀번호는 `123456`, `password`, 그리고 이름 뒤에 숫자가 붙는 변형된 형태들임을 알 수 있습니다.

하이브리드 공격은 변형 규칙을 적용하여 기본 단어 목록을 확장합니다. 'password'와 같은 단어는 Password, P@ssword, p4ssword, password1, password123 등 수백 가지 더 많은 변형 형태로 바뀝니다. Hashcat의 규칙 엔진은 첫 글자 대문자화, 두 자리 숫자 덧붙이기, 문자를 기호로 대체하는 것과 같이 어떤 변형을 적용할지 정확히 지정할 수 있게 해줍니다. 이는 완전히 무작위 문자열을 일일이 테스트하지 않고도 공격 범위를 극적으로 확장합니다.

릿 스피크 치환(e=3, a=4, i=1, o=0, s=5와 같이 문자를 숫자로 대체하는 것)은 한때 비밀번호 보안을 향상시킨다고 여겨졌습니다. 규칙 기반 크래커는 이러한 치환을 표준 변환으로 포함합니다. s3cur1ty와 같은 비밀번호는 기본 단어 security에 릿 스피크 치환 규칙을 추가하면 아주 쉽게 해독됩니다. 크래커는 또한 모든 사전 단어에 !, 123, 또는 현재 연도를 덧붙이는 것과 같은 일반적인 패턴을 시도합니다.

레인보우 테이블은 해시 값을 원래 비밀번호로 다시 매핑하는 거대한 사전 계산된 데이터베이스입니다. 공격자는 후보를 해싱하여 비교하는 대신, 테이블에서 해당 해시 값을 찾습니다. 이 테이블을 구축하는 데는 엄청난 시간과 저장 공간이 필요하지만, 각 조회는 즉각적으로 이루어집니다. 모든 8자리 영숫자 비밀번호에 대한 MD5 레인보우 테이블은 몇 테라바이트 안에 저장될 수 있으며, 일치하는 모든 비밀번호를 밀리초 단위로 해독할 수 있습니다.

레인보우 테이블은 시간-메모리 트레이드오프의 전형적인 예시입니다. 테이블을 한 번 계산하는 데 시간을 투자하고, 이후 조회를 빠르게 하기 위해 메모리를 사용하죠. 이 테이블은 해시 체인을 저장하는데요, 각 체인은 추측 값으로 시작하여 이를 해시하고, 환원 함수를 적용해 다른 추측 값을 생성하는 과정을 반복합니다. 체인의 끝점만 저장함으로써, 저장 공간과 계산량 사이의 균형을 이루는 체인 재구성 과정을 통해 해시로부터 비밀번호를 복구할 수 있습니다.

솔트는 해싱하기 전에 비밀번호에 덧붙여지는 무작위 값입니다. 솔트는 사용자마다 고유하기 때문에, 동일한 비밀번호를 가진 두 사용자도 다른 해시 값을 생성합니다. 이는 공격자가 솔트된 비밀번호에 대한 레인보우 테이블을 미리 계산할 수 없다는 것을 의미합니다. 모든 가능한 솔트 값에 대해 별도의 테이블을 구축해야 하는데, 이는 계산적으로 불가능합니다. 모든 안전한 비밀번호 저장 시스템에서 솔팅은 필수적입니다.

많은 초기 웹 애플리케이션들은 비밀번호를 솔트되지 않은 MD5 해시로 저장했습니다. 문자열 password의 MD5 값은 5f4dcc3b5aa765d61d8327deb882cf99이며, 고정된 값입니다. 이 해시를 이전에 본 적이 있거나 미리 계산된 데이터베이스에서 찾아본 사람이라면 누구든지 즉시 비밀번호를 알 수 있습니다. CrackStation과 같은 사이트들은 수십억 개의 미리 계산된 MD5 및 SHA-1 해시를 유지합니다. 솔트되지 않은 일반적인 비밀번호는 1초도 안 되어 해독됩니다.

보안 연구원 Troy Hunt가 만든 Have I Been Pwned (HIBP)는 주요 데이터 유출 사고에서 유출된 비밀번호 해시들을 수집합니다. 사용자는 자신의 이메일 주소나 비밀번호가 유출 사고에 포함되었는지 확인할 수 있습니다. 개발자는 HIBP API를 사용하여 8억 5천만 개의 유출된 해시에 대해 후보 비밀번호를 확인할 수 있으며, 이는 k-익명성 모델을 통해 이루어집니다. SHA-1 해시의 처음 5개 16진수 문자를 API로 전송하면 서버가 전체 해시를 알지 못한 채 일치하는 접미사를 반환합니다.

크리덴셜 스터핑 공격은 한 번의 유출에서 얻은 사용자 이름-비밀번호 쌍을 다른 서비스에 대입하여 시도합니다. 많은 사용자가 여러 사이트에서 비밀번호를 재사용하기 때문에, 보안 수준이 낮은 사이트에서의 유출이 은행 및 이메일과 같은 가치가 높은 대상에 대한 유효한 자격 증명을 제공하게 됩니다. 자동화된 도구는 여러 서비스에 걸쳐 초당 수천 건의 로그인 시도를 합니다. 속도 제한(Rate limiting)과 다단계 인증(multi-factor authentication)은 크리덴셜 스터핑에 대한 주요 방어 수단입니다.

안전한 비밀번호 저장은 솔팅과 느리고 적응형 해시 함수를 함께 사용합니다. bcrypt, Argon2, scrypt는 연산 비용이 많이 들도록 설계되어, 마이크로초 단위가 아닌 해시당 밀리초 단위의 시간이 소요됩니다. 이는 공격자의 처리량을 초당 수십억 회의 시도에서 수천 회로 제한합니다. 하드웨어 성능이 향상됨에 따라 연산 비용 매개변수를 늘려 일관된 작업량을 유지할 수 있습니다. 이러한 알고리즘은 비밀번호 저장의 현재 표준입니다.

각 비밀번호를 해싱하기 전에 고유한 무작위 솔트를 추가하는 것이 미리 계산된 레인보우 테이블 공격을 왜 무력화시킬까요?

사전 공격은 모든 조합을 시도하는 대신 가능성이 높은 비밀번호를 테스트합니다. rockyou.txt는 1,400만 개의 실제 사례를 제공합니다. 하이브리드 및 규칙 기반 공격은 변형을 사용하여 단어 목록을 확장합니다. 레인보우 테이블은 솔트되지 않은 해시에 대해 즉각적인 조회를 가능하게 합니다. 솔팅은 각 해시를 고유하게 만듦으로써 레인보우 테이블을 무력화시킵니다. HIBP는 알려진 유출에서 비밀번호가 나타나는지 확인합니다. bcrypt 및 Argon2와 같은 적응형 해시 함수는 안전한 저장을 위해 필요합니다.