무차별 대입 공격의 작동 방식

암호에 대한 무차별 대입 공격은 올바른 키를 찾을 때까지 가능한 모든 키를 시도합니다. n비트 키의 경우 2^n개의 가능한 키가 존재합니다. 3비트 키는 단 8가지 경우의 수만 있지만, 56비트 키는 72경 개가 넘습니다. 무차별 대입 공격에 대한 근본적인 방어책은, 완전 탐색이 실질적인 시간 내에 계산상 불가능하도록 충분히 큰 키를 선택하는 것입니다.

DES(Data Encryption Standard)는 56비트 키를 사용하며, 약 7.2 * 10^16개의 키 공간을 가집니다. 1977년에는 이 숫자가 엄청나게 커 보였습니다. 하지만 1998년에 EFF의 Deep Crack 머신은 25만 달러의 비용으로 56시간 만에 DES를 해독하는 데 성공했습니다. 2006년에는 전용 클러스터가 1만 달러 미만의 비용으로 9일도 채 걸리지 않아 DES를 해독할 수 있었습니다. 여기서 얻은 교훈은 분명했습니다. 56비트 키는 강력한 공격자에 맞서기에는 더 이상 충분한 보안이 아니라는 것이었습니다.

AES-128은 128비트 키를 사용하며, 이는 약 3.4 * 10^38개에 달하는 2^128개의 가능한 키를 제공합니다. 관측 가능한 우주의 모든 원자가 컴퓨터가 되어 빅뱅 이후부터 초당 10억 개의 키를 테스트한다고 해도, 이 탐색은 완료에 근접하지 못할 것입니다. 미래에 기하급수적으로 더 빠른 하드웨어가 등장하더라도, 128비트 키는 가까운 미래에도 고전적인 무차별 대입 공격에 대해 안전하게 유지될 것으로 예상됩니다.

온라인 무차별 대입 공격은 인증 요청을 반복적으로 전송하여 실제 시스템을 대상으로 합니다. 이러한 공격은 네트워크 지연 시간, 서버 응답 시간 및 속도 제한에 의해 제한되므로 속도가 느립니다. 오프라인 무차별 대입 공격은 비밀번호 해시 데이터베이스와 같이 도난당한 데이터를 대상으로 합니다. 공격자는 해시를 확보하면 네트워크 제약 없이 로컬 하드웨어를 사용하여 초당 수십억 개의 후보를 테스트할 수 있습니다.

현대 GPU는 부동 소수점 연산에 최적화된 수천 개의 병렬 처리 코어를 포함하고 있습니다. 선도적인 GPU 해시 크래킹 도구인 Hashcat은 단일 고성능 GPU에서 초당 1,000억 개 이상의 MD5 해시를 테스트할 수 있습니다. 8개의 GPU로 구성된 리그는 초당 8,000억 개 이상의 후보를 테스트할 수 있습니다. 이로 인해 잘못 선택된 비밀번호와 약한 해시 함수는 빠른 오프라인 크래킹에 취약해집니다.

ASIC(Application-Specific Integrated Circuits)은 특정 연산만을 위해 전용으로 설계된 칩입니다. 비트코인 채굴자들은 초당 수십 테라해시의 속도로 SHA-256 해시를 계산하는 ASIC을 사용하며, 이는 어떤 GPU보다도 훨씬 빠릅니다. 비트코인 ASIC이 암호 크래킹과는 다른 연산을 수행하지만, 이 원리는 동일하게 적용됩니다. 특정 암호화 연산의 경우, 전용 하드웨어는 범용 하드웨어에 비해 수십, 수백 배의 속도 향상을 제공합니다.

무어의 법칙은 트랜지스터 밀도가 대략 2년마다 두 배로 증가하며, 이는 역사적으로 컴퓨팅 성능의 동등한 속도 향상을 가져왔다고 설명합니다. 오늘날 안전하다고 여겨지는 키 길이는 수십 년간의 미래 하드웨어 발전에도 불구하고 안전하게 유지되어야 합니다. 따라서 보안 권고 사항들은 상당한 안전 여유를 포함합니다. AES-128은 고전적인 무차별 대입 공격에 취약해지려면 컴퓨팅 성능이 2^64배 빨라져야 하는데, 이는 무어의 법칙의 어떤 그럴듯한 예측치를 훨씬 뛰어넘는 수준입니다.

NIST SP 800-57은 암호화 알고리즘의 보안 강도를 규정하고 있습니다. 새로운 시스템에는 112비트 보안이 현재 최소 수준입니다. 장기적인 보호를 위해서는 128비트 보안이 권장됩니다. 256비트 대칭키는 현재 예측 가능한 고전 컴퓨팅 위협을 넘어선 안전 여유를 제공합니다. NIST는 80비트 이하의 보안 수준을 권장하지 않으며, 이는 어떠한 새로운 애플리케이션에도 부적절하다고 간주됩니다.

그로버 양자 검색 알고리즘은 비정형 검색(unstructured search)에 대해 2차 가속(quadratic speedup)을 제공합니다. 즉, N개의 항목으로 구성된 키 공간을 N단계 대신 대략 sqrt(N) 단계로 검색할 수 있습니다. AES-128의 경우, 이는 양자 공격자에 대해 보안 강도를 효과적으로 64비트로 낮춥니다. AES-256의 경우, 그로버 알고리즘에 대한 유효 보안(effective security)은 128비트이며, 이러한 이유로 포스트 양자 보안(post-quantum security)을 위해 256비트 대칭 키가 권장됩니다.

그로버 알고리즘을 실행하는 양자 컴퓨터에 대비하여 128비트 보안을 유지하려면, 대칭 키는 최소 256비트여야 합니다. AES-256은 이미 이 크기이며, 대칭 암호화에 대해 양자 안전(quantum-safe)하다고 간주됩니다. 참고로, 키 길이를 128비트에서 256비트로 두 배로 늘리는 것은 정당한 사용자의 연산량을 두 배로 늘리지 않지만 (AES 라운드를 몇 개만 더 추가할 뿐입니다), 공격자의 양자 자원을 제곱으로 증가시켜야 합니다.

보안 팀은 공격자들이 취약한 자격 증명을 발견하기 전에, 승인된 비밀번호 감사에서 브루트 포스 도구를 사용하여 이를 식별합니다. `Hashcat`과 `John the Ripper`는 내보낸 비밀번호 해시 데이터베이스를 대상으로 실행되어, 비밀번호 중 어느 정도 비율이 크랙될 수 있는지 확인합니다. 감사 결과는 최소 길이 요건, 복잡도 규칙, 그리고 `bcrypt` 또는 `Argon2`와 같은 최신 비밀번호 해싱 알고리즘의 채택과 같은 비밀번호 정책 개선을 이끌어냅니다.

그로버의 양자 알고리즘은 AES-128의 실질적인 보안에 어떻게 영향을 미치나요?

무차별 대입 공격은 가능한 모든 키를 시도합니다. 보안을 위해서는 현실적으로 열거하기에는 너무 큰 키 공간이 필요합니다. 56비트 DES는 1998년에 해독되었습니다. 2^128개의 키를 가진 AES-128은 고전 컴퓨터로는 사실상 불가능합니다. GPU 클러스터는 오프라인에서 초당 수천억 개의 해시를 해독합니다. 그로버 양자 알고리즘은 비트 보안을 절반으로 줄여, 128비트 양자 내성 보안을 위해 256비트 키를 요구합니다. NIST는 새로운 시스템에 대해 최소 128비트 보안을 권장합니다.