이틀 전 마이크 말론이 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 캐시에 충분히 들어갈 정도다. 그래서 엄청나게 빠르고 편리하다.

마이크 말론은 PRNG를 이용해 64가지 가능한 문자 중 하나로 이루어진 문자 집합으로 구성된 ID를 만드는 방식으로 이 아이디어를 사용하고 있었다. 각 문자를 만들기 위해 취약한 V8 PRNG가 사용되면서 충돌이 발생한 것이다. 우리의 초기 가정은 각각의 새로운 ID가 0과 N 사이의 공간에서 균등하게 선택되어야 한다는 것임을 기억하자.

더 강력한 PRNG를 사용하면 이 문제를 해결할 수 있지만, 그러려면 PRNG에 대한 분석이 필요하다. 또 다른 문제는 시딩이다. 재시작 후 PRNG의 초기 상태를 다시 선택하지 않도록 하려면 어떻게 다시 시작해야 할까? 그렇지 않으면 실제 ID 공간은 PRNG의 출력 공간이 아니라 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