이틀 전 Mike Malone이 Medium에 V8의 Math.random() 구현과 사용된 PRNG의 품질이 얼마나 취약한지에 대한 흥미로운 글을 올렸습니다: http://bit.ly/1SPDraN.

이 글은 오늘 Hacker News의 주요 뉴스 중 하나였습니다. Math.random()이 어떻게 망가져 있고 어떻게 고쳐야 하는지에 대한 관점에서 매우 명확하고 유익해서, 그 자체에 대해서는 덧붙일 말이 없습니다. 하지만 저자가 충돌 가능성이 낮은 큰 ID를 생성하는 맥락에서 PRNG의 취약점을 발견했기에, 과거에 여러 번 사용했던 빠르고 매우 안정적인 대안을 여러분께 공유하고자 합니다.

고유 ID의 문제

이론적으로 고유 ID를 생성하려면 ID가 절대 반복되지 않도록 보장하는 어떤 상태를 저장해야 합니다. 가장 단순한 경우에는 그냥 카운터 하나를 쓰면 됩니다. 하지만 이전에 생성된 ID는 일관된 방식으로 저장되어야 합니다. 시스템이 재시작되더라도 저장된 카운터가 디스크에 제대로 저장되지 않았다는 이유로 동일한 ID가 다시 생성되는 일은 절대 없어야 합니다.

여러 프로세스를 이용해 고유 ID를 생성하려면 각 프로세스가 다른 프로세스의 접두사와 절대 충돌하지 않는 프로세스별 접두사를 ID 앞에 붙이도록 해야 합니다. 이것 역시 관리가 복잡할 수 있습니다. 이전 ID를 안정적으로 저장해야 한다는 사실 자체가 초당 많은 수의 ID를 생성하고자 할 때는 매우 큰 부담이 됩니다.

다행히 간단한 해결책이 있습니다. 0부터 N 사이의 난수를 생성하되, N을 충돌 확률이 사실상 모든 실제 응용 분야에서 무시해도 될 정도로 작아지도록 충분히 크게 잡는 것입니다. 이 방법은 우리가 생성하는 숫자가 0과 N 사이에 균등하게 분포할 때 동작합니다. 이 전제 조건이 충족되면 생일 문제 역설을 이용해 충돌 확률을 계산할 수 있습니다.

충분한 비트를 사용하면 수백 년 동안 초당 수백만 개의 ID를 생성하더라도 충돌 확률을 소행성이 지구를 정통으로 강타할 확률보다 수십억 배 더 낮게 만드는 것은 간단합니다. 이 정도 여유로도 부족하다면 비트를 더 추가하면 됩니다. 우주의 원자 수보다 더 큰 ID 공간에도 쉽게 도달할 수 있습니다.

이 생성 방식에는 큰 장점이 있습니다. 완전히 무상태(stateless)라는 점입니다. 여러 노드가 메시지를 주고받지 않고도 동시에 ID를 생성할 수 있습니다. 게다가 디스크에 저장할 것도 없으므로 CPU가 허용하는 한 최대한 빠르게 동작할 수 있습니다. 연산은 CPU 캐시에 충분히 들어갑니다. 그래서 엄청나게 빠르고 편리합니다.

Mike Malone은 64개의 가능한 문자 중 하나로 이루어진 문자 집합으로 구성된 ID를 만들 때 PRNG를 사용하면서 이 아이디어를 활용했습니다. 각 문자를 만들기 위해 취약한 V8 PRNG가 사용되었고, 그 결과 충돌이 발생했습니다. 우리의 초기 가정은 각각의 새로운 ID가 0과 N 사이의 공간에서 균등하게 선택되어야 한다는 점을 기억하십시오.

더 강력한 PRNG를 사용하면 이 문제를 해결할 수 있지만, 그러려면 PRNG에 대한 분석이 필요합니다. 또 다른 문제는 시딩(seeding)입니다. 재시작 후에 PRNG의 초기 상태를 다시 선택하지 않도록 하려면 어떻게 프로세스를 다시 시작해야 할까요? 그렇지 않으면 실제 ID 공간은 출력 공간 자체가 아니라 PRNG의 시딩에 의해 제한됩니다.

이러한 모든 이유 때문에 대부분의 문제를 피할 수 있는 간단한 기법을 보여드리고자 합니다.

암호학적 해시 함수를 이용해 고유 ID 생성하기

암호학적 해시 함수는 비트 수열을 고정된 길이의 비트 수열로 변환하는 비가역 함수입니다. 다양한 공격에 저항하도록 설계되었지만, 이 응용에서는 해시 함수가 가진 한 가지 특성, 즉 출력의 균일성에만 의존합니다. 해시 함수 입력의 비트 하나를 바꾸면 출력의 각 비트가 50% 확률로 바뀝니다.

신뢰할 수 있는 시드를 얻기 위해 운영체제의 도움을 받아 /dev/urandom을 조회합니다. 생성기에 시드를 부여하는 순간이야말로 외부 엔트로피가 정말로 필요한 순간입니다. 그렇지 않으면 큰 실수를 저질러 동일한 수열을 다시 생성할 위험이 큽니다.

암호학적 해시 함수의 예로는 출력이 160비트인 잘 알려진 SHA1을 사용하겠습니다. 이 용도라면 MD5를 사용해도 무방하다는 점을 참고하십시오. MD5가 가진 취약점은 여기서는 아무런 영향을 주지 않습니다.

먼저 /dev/urandom에서 160비트를 읽어 시드를 만듭니다. 의사 코드로는 다음과 같습니다.

seed = devurandom.read(160/8)

카운터도 초기화합니다.

counter = 0

이제 매번 새로운 ID를 생성할 함수는 다음과 같습니다.

function get_new_id()
    myid = SHA1(string(counter) + seed)
    counter = counter + 1
    return myid
end

기본적으로 시드인 고정된 문자열이 있고, 이를 증가하는 카운터와 함께 해시합니다. 따라서 시드가 “foo”라면 새로운 ID는 다음과 같이 출력됩니다.

SHA1(“0foo”)
SHA1(“1foo”)
SHA1(“2foo”)

이것만으로도 우리의 사용 사례에는 이미 충분합니다. 하지만 ID를 쉽게 예측할 수 없도록 해야 할 수도 있습니다. ID를 예측하기 매우 어렵게 만들려면 get_new_id() 함수에서 SHA1 대신 SHA1_HMAC()을 사용하십시오. 이때 시드가 비밀 키가 되고 카운터가 HMAC의 메시지가 됩니다.

이 방법은 빠르고 분포가 좋다는 것이 보장되므로 충돌은 생일 문제 역설이 예측한 만큼 어려울 것이며, PRNG에 대한 분석이 필요 없고 완전히 무상태입니다.

저는 분산 시스템의 여러 노드 간에 메시지 ID를 생성하기 위해 제 Disque 프로젝트에서 이 방법을 사용하고 있습니다.

Hacker News 스레드는 여기에서 확인할 수 있습니다: https://news.ycombinator.com/item?id=10606910