키 길이와 무차별 대입: 암호는 얼마나 버틸까
암호 이야기에는 128비트, 256비트 같은 숫자가 자주 나옵니다. 숫자가 클수록 안전하다는 것은 대략 알겠는데, 그 숫자가 실제로 무엇을 뜻하는지 감을 잡기는 어렵습니다. 이 글에서는 키 길이가 의미하는 바와 무차별 대입 공격의 규모를 직접 계산해 보고, 현실에서 암호가 뚫리는 지점이 어디인지 살펴봅니다.
키 길이란 무엇인가요
현대 암호는 알고리즘 자체는 모두에게 공개하고, 비밀은 오직 키 하나에만 둡니다. 키는 결국 0과 1로 이루어진 긴 숫자이고, 키 길이는 그 숫자가 몇 비트인지를 말합니다. 비트가 하나 늘어날 때마다 가능한 키의 개수는 정확히 두 배가 됩니다. 1비트면 키가 2개, 2비트면 4개, 10비트면 1,024개입니다.
그래서 128비트 키가 가질 수 있는 경우의 수는 2의 128제곱이고, 이는 약 3.4 곱하기 10의 38제곱입니다. 256비트라면 2의 256제곱, 약 1.16 곱하기 10의 77제곱입니다. 둘의 차이는 128비트 더 길다는 것이 아니라, 경우의 수가 2의 128제곱 배 더 많다는 뜻입니다. 숫자가 선형이 아니라 지수로 커진다는 점이 키 길이를 이해하는 출발점입니다.
무차별 대입 공격이란
무차별 대입(brute force) 공격은 가능한 키를 하나씩 모두 넣어 보는 방법입니다. 머리를 쓰는 기술이 아니라 시간과 계산 능력으로 밀어붙이는 방식이어서, 어떤 암호든 원리상 이 공격은 통합니다. 따라서 암호의 안전성은 이 공격이 현실적으로 불가능하도록 키 공간을 충분히 크게 잡는 데서 시작합니다.
평균적으로는 전체 키 공간의 절반쯤을 시도했을 때 정답을 만난다고 봅니다. 하지만 경우의 수가 천문학적이면 절반이든 전부든 차이가 없습니다. 아래에서 보듯 지수적 크기 앞에서는 상수 배 정도의 차이가 의미를 잃기 때문입니다.
숫자로 느껴 보는 규모
직접 계산해 보겠습니다. 어떤 공격자가 놀랄 만큼 강력한 장비를 갖추어 1초에 1조(10의 12제곱) 개의 키를 시험할 수 있다고 가정합니다. 이는 일반적인 컴퓨터 한 대와는 비교할 수 없는 속도입니다.
- 128비트 키의 전체 경우의 수는 약 3.4 곱하기 10의 38제곱입니다.
- 초당 10의 12제곱 개를 시험하면 전부 시험하는 데 약 3.4 곱하기 10의 26제곱 초가 걸립니다.
- 1년은 약 3.15 곱하기 10의 7제곱 초이므로, 이는 대략 10의 19제곱 년, 즉 1천경 년 정도입니다.
- 우주의 나이는 약 138억 년이니, 우주 나이의 10억 배에 가까운 시간입니다.
이 계산은 초당 1조 개라는 아주 후한 속도를 가정한 것입니다. 이런 장비를 1억 대로 늘려도 시간이 1억 분의 1로 줄 뿐이어서 여전히 비현실적입니다. 반대로 오래된 DES 암호는 키가 56비트로, 경우의 수가 약 7.2 곱하기 10의 16제곱에 불과했습니다. 1990년대 후반에 전용 장비를 만든 연구 단체가 며칠 안에 DES 키를 찾아내는 데 성공했고, 이 사건으로 키 길이가 짧은 암호는 더는 안전하지 않다는 점이 분명해졌습니다. 이후 표준은 AES로 교체되었고, AES는 128, 192, 256비트 키를 지원합니다.
256비트는 128비트보다 꼭 필요할까요
128비트만으로도 현재 알려진 방법으로는 무차별 대입이 불가능합니다. 그럼에도 256비트를 쓰는 곳이 많은 이유는 여유를 두기 위해서입니다. 양자컴퓨터가 충분히 발전하면 탐색 속도를 제곱근 수준으로 높이는 알고리즘이 쓰일 수 있다고 알려져 있고, 그렇게 되면 유효한 키 길이가 대략 절반으로 줄어듭니다. 256비트라면 그런 경우에도 128비트에 상당하는 여유가 남습니다. 다만 이는 이론적인 이야기이고, 지금 당장 양자컴퓨터가 이런 규모의 공격을 할 수 있다는 뜻은 아닙니다.
이 서비스에서 글을 암호화하는 AES-GCM 키는 256비트입니다. 번역기 주소 조각에 들어 있는 번역기 키도 무작위로 만든 32바이트, 즉 256비트 값이며, 여기서 HKDF로 256비트 해독 키를 유도합니다. 키 공간만 놓고 보면 무차별 대입으로 접근할 방법이 없는 크기입니다.
그런데 왜 암호는 여전히 뚫릴까요
현실에서 암호가 무너지는 경우를 보면, 키 공간 전체를 헤집는 공격은 거의 없습니다. 대부분 아래와 같은 더 쉬운 길로 들어옵니다.
- 사람이 정한 비밀번호가 짧거나 예측하기 쉬운 경우
- 키가 적힌 파일이나 메모, 화면이 유출되는 경우
- 기기가 악성코드에 감염되어 입력 값이 그대로 넘어가는 경우
- 구현 실수나 난수 오류로 키가 예측 가능해지는 경우
- 속아서 직접 알려 주는 사칭, 피싱
쇠사슬이 아무리 굵어도 열쇠를 현관 매트 아래에 두면 소용이 없다는 것과 같습니다. 키 길이는 가장 튼튼한 고리일 뿐이고, 사슬의 강도는 가장 약한 고리가 결정합니다.
사람이 만든 비밀번호는 키보다 약합니다
사람이 기억할 수 있는 비밀번호는 무작위 256비트 키에 비하면 극도로 작은 공간에 모여 있습니다. 예를 들어 영문 대소문자와 숫자로만 된 8글자 비밀번호는 경우의 수가 62의 8제곱, 약 2.18 곱하기 10의 14제곱입니다. 이는 2의 47~48제곱 정도로, 128비트와는 비교도 되지 않습니다. 게다가 실제 사람들은 무작위로 고르지 않고 이름, 생일, 단어를 조합하기 때문에, 공격자는 흔한 패턴 목록부터 시험하는 사전 공격으로 훨씬 빨리 찾아냅니다.
이 약점을 줄이는 방법은 두 가지입니다. 하나는 비밀번호를 길게, 무작위로 만드는 것입니다. 단어 몇 개를 무작위로 이어 붙인 문장형 암호문이 외우기도 쉽고 경우의 수도 큽니다. 자세한 방법은 강한 비밀번호와 암호문을 만드는 법에서 다루었습니다. 다른 하나는 비밀번호를 키로 바꾸는 과정을 일부러 느리게 만드는 것입니다. 한 번 시도하는 비용이 600,000배로 늘면 같은 시간에 시험할 수 있는 후보 수가 그만큼 줄어듭니다. 이 서비스가 비밀번호 번역기에서 PBKDF2를 600,000회 반복하는 이유가 이것이며, 원리는 비밀번호에서 키를 만드는 PBKDF2와 키 유도에 풀어 두었습니다. 다만 반복 횟수는 공격 비용을 올릴 뿐이므로 약한 비밀번호가 강해지지는 않습니다.
무차별 대입보다 영리한 공격은 없을까요
암호학자들은 키를 전부 시험하는 대신 알고리즘의 수학적 구조를 파고들어 시험 횟수를 줄이는 방법을 끊임없이 연구합니다. 어떤 암호에서 키 공간보다 훨씬 적은 노력으로 키를 찾는 방법이 발견되면, 그 암호는 이름에 적힌 키 길이만큼의 안전성을 갖지 못하게 됩니다. 이런 이유로 오래 검증받은 알고리즘이 중요합니다. AES는 공개 공모와 오랜 분석을 거쳐 표준이 되었고, 지금까지 키 전체를 시험하는 것보다 현실적으로 훨씬 빠른 공격이 알려지지 않았습니다. 일부 이론적 약화는 보고되었지만 실제 사용에 위협이 되는 수준은 아닌 것으로 평가됩니다.
또 하나는 암호 알고리즘이 아니라 그것을 실행하는 장치를 노리는 부채널 공격입니다. 계산 시간, 전력 소모, 메모리에 남은 흔적 같은 정보에서 키를 짐작하는 방식입니다. 그래서 암호는 직접 구현하지 않고 브라우저나 운영체제에 내장된 검증된 구현을 쓰는 것이 원칙입니다. 이 서비스가 Web Crypto API를 쓰는 이유도 같습니다.
이런 사정을 종합하면, 키 길이는 안전성의 상한선을 정해 주는 숫자일 뿐 보장은 아닙니다. 상한이 높다고 해서 실제 안전성이 그만큼 나오는 것은 아니며, 알고리즘의 검증 상태, 구현의 품질, 키의 무작위성, 사용자의 습관이 모두 받쳐 주어야 실제 안전이 됩니다.
외우기 쉬운 암호문은 얼마나 강할까요
단어를 무작위로 골라 이어 붙인 암호문은 단어 목록의 크기와 단어 수로 경우의 수를 셀 수 있습니다. 예를 들어 단어 목록이 2,000개이고 세 단어를 무작위로 고르면 경우의 수는 2,000의 세제곱, 80억 가지입니다. 이는 약 33비트에 해당하는 크기여서 공격자가 빠르게 시험할 수 있는 환경에서는 충분히 크지 않습니다. 단어 수를 늘리면 경우의 수가 곱절로 커지므로 4개, 5개, 6개로 늘려 가는 것이 효과적이고, 여기에 키 유도를 느리게 만드는 장치가 더해지면 비용이 한 번 더 올라갑니다. 중요한 점은 사람이 머릿속에서 그럴듯하게 고른 문장은 무작위가 아니라는 것이며, 무작위 선택은 도구의 도움을 받는 것이 좋습니다.
정리: 키 길이를 볼 때의 기준
핵심을 정리하면 다음과 같습니다.
- 키가 1비트 길어질 때마다 무차별 대입에 드는 노력은 두 배가 됩니다.
- 무작위로 만든 128비트 이상의 키는 현재 알려진 방법으로 무차별 대입이 불가능합니다.
- 중요한 것은 키가 정말 무작위인지, 그리고 키가 어디에 어떻게 보관되는지입니다.
- 사람이 정하는 비밀번호는 키 길이 숫자보다 훨씬 약한 고리가 됩니다.
난수가 왜 중요한지는 암호에서 난수가 중요한 이유에서 이어서 볼 수 있고, 직접 암호화를 해 보고 싶으시면 번역기 열기에서 써 보시기 바랍니다.
잘못된 내용이나 보완할 점을 발견하셨다면 소개·문의의 이메일로 알려 주세요. 확인 후 글을 고치고 수정일을 갱신합니다.