개발자 도구 · UUID 생성기
v4 UUID에는 몇 개의 임의 비트가 있습니까? 122, 128 아님
· 작동 방식
uuid 암호화 브라우저 API
무작위 UUID의 128 비트 중 6개는 표준에 의해 고정되어 있으며 122는 무작위로 남겨져 있습니다. 이 게시물에서는 충돌 확률을 정직하게 추정하는 방법과 실제 충돌이 수학이 아닌 고장난 발전기에서 발생하는 이유를 보여줍니다.
건축가의 질문: 복제품을 얻을 수 있을까요? — 걱정은 어디에서 발생하며 왜 대답은 발전기에 따라 달라지는가
설계자는 다음과 같이 묻습니다. 10년 동안 매일 10백만 UUID를 생성하면 복제본을 얻을 수 있습니까? 정직한 대답은 다음과 같습니다. 생성기가 암호화되어 안전하다면 거의 확실하지 않습니다. 거의 확실하게 그렇습니다. 발전기가 고장난 경우에는 가능합니다. RFC 9562 수학은 타당합니다. 122 임의 비트가 포함된 v4 UUID의 충돌 확률은 대략 n² / 2의 123승입니다. 여기서 n은 생성된 식별자 수입니다. 대부분의 실제 시스템에서 이 확률은 무시할 수 있습니다. 문제는 이 공식이 모든 비트가 실제로 무작위라고 가정한다는 것입니다. 생성기가 누출되거나 반복되거나 예상대로 시드된 경우 공식이 잘못된 것이며 중복이 불가피해집니다. 128비트 레이아웃에는 4개의 버전 비트(v4의 경우 0100)와 2개의 변형 비트(RFC 9562의 경우 10)가 포함되어 있으며 이는 표준에 의해 고정되고 설정됩니다.
6개 비트가 사용되는 항목 — 4개 버전 비트와 2개 변형 비트 및 이들이 무작위가 아닌 설정되는 이유
무작위성을 위해 122 비트가 남습니다. 이 공식은 때때로 122 임의 비트에 대해 2이라고 불리며 고유한 값을 생성합니다. 생일 역설 근사법을 사용하면 무작위로 생성된 n개의 값 중 적어도 한 번 충돌할 확률은 대략 n² / 2의 123승입니다. n = 1백만의 경우 이는 (10^6)² / 2^123 = 10^12 / 9입니다. 3 × 10^36, 이는 약 10^-25입니다. n = 10십억의 경우 여전히 약 10^-16입니다. 이는 "실질적으로 0"이 아닙니다. 그들은 "당신은 이것을 결코 관찰하지 못할 것입니다." 생일 근사치는 위험을 계산하는 구체적인 방법을 제공합니다. 생성하려는 UUID를 세고 그 숫자를 제곱한 다음 2의 123제곱으로 나눕니다. 생성기가 브라우저의 crypto.getRandomValues인 경우 모든 비트는 운영 체제 엔트로피의 지원을 받습니다. 수학이라면.
일반 용어로 생일 근사치 — n개의 식별자 중 적어도 한 번 충돌할 확률은 대략 n 제곱을 2에서 123로 나눈 값입니다.
부적합하거나 반복 상태 생성기에 의해 생성된 UUID의 경우 독립 가정이 거짓이므로 수학적 모델이 무너집니다. 고정된 테스트 시드, 복사된 고정 장치 또는 프로세스 스냅샷은 텍스트가 여전히 버전-4 니블을 전달하더라도 값을 재생할 수 있습니다. 이는 구현 결함이며 122 필드 계산이 잘못되었다는 증거는 아닙니다. 또 다른 평범한 소스는 동일한 리터럴 식별자를 여러 픽스처에 복사하고 나중에 해당 데이터를 병합하는 것입니다. 중복을 조사할 때 생성기, 시드 정책, 프로세스 수명 주기 및 가져오기 기록을 보존하세요. 하나의 반복되는 값에서 독립적인 CSPRNG 출력이 UUID 공간을 소진했다는 주장으로 점프하지 마세요.
실제 사례 — 명시된 생성 속도와 시간 범위를 근사치에 연결하고 모든 단계를 표시하여 자신의 수치로 대체할 수 있습니다.
무작위 상태 재동기화 없이 프로세스 분기. crypto.getRandomValues 대신 Math.random이 사용된 버그입니다. 여러 행에 동일한 UUID을 사용하여 수작업으로 제작되었으며 실수로 생산에 사용된 테스트 픽스처입니다. 범위 제한이나 상태 버그가 있는 UUID 라이브러리의 이전 버전입니다. 이러한 시나리오 중 어느 것도 생일 근사 수학을 포함하지 않습니다. 여기에는 구현이 깨졌거나 운영상의 실수가 포함됩니다. 시스템의 충돌 위험을 정직하게 계산하십시오. UUID 생성 속도(초당, 하루당, 연간)를 계산하고 시스템이 실행되는 시간에 걸쳐 이를 예측한 다음 총계를 생일 공식에 연결하십시오. 시스템이 5년 동안 매일 100,000 UUID를 생성하는 경우(총 182백만) 충돌 확률은 (1. 82 × 10^8)² / 2^123 ≒입니다. 3. 3 × 10^-22, 이는 무시할 수 있는 수준입니다.
실제로 중복이 발생하는 위치 — Math.random 시드, 복제된 가상 머신, 복사된 상태의 포크된 프로세스, 픽스처의 복사-붙여넣기
1년 동안 초당 10백만(총 315조)을 생성하는 경우 확률은 (3. 15 × 10^14)² / 2^123 입니다. 10^-10, 이는 여전히 매우 작습니다. 이러한 추정에서는 모든 비트가 독립적이고 무작위적이라고 가정합니다. ToolAcre 생성기는 CSPRNG 지원 무작위성을 제공하는 crypto.getRandomValues를 사용합니다. 수술은 신뢰해야 할 유일한 부분입니다. 적절한 인증 확인을 건너뛰기 위한 핑계로 충돌 가능성에 의존하지 마십시오. UUID은(는) 비밀번호나 액세스 토큰이 아니며 122 임의 비트인 경우에도 비밀이 아닙니다. 독창성은 이점입니다. 예측 불가능성은 추측을 방지하는 별도의(더 중요한) 속성입니다. 생일 수학은 고유성을 처리합니다. 수명(이 UUID이 만료되어야 합니까?), 비밀성(저장하기 전에 해시해야 합니까?) 또는 승인(이 UUID을 소유하는 것이 호출자에 대해 무엇을 증명합니까?)을 다루지 않습니다. ToolAcre 생성기는 122 임의 비트가 포함된 CSPRNG 지원 UUID를 제공합니다. 이는 수학의 고유성이 유지되고 예측 불가능성이 건전함을 의미합니다. 토큰 검증, 만료, 액세스 제어 등 그 밖의 모든 것은 애플리케이션의 책임입니다. 확률 공식은 생성된 각 UUID가 이전 세대로부터 독립된 것으로 가정합니다. 시스템이 단일 CSPRNG 인스턴스에서 식별자를 생성하고 각 호출이 OS에서 새로운 임의성을 가져오는 경우 독립 가정이 유지됩니다. 시스템이 OS 재시드 없이 캐시된 CSPRNG 상태 또는 시드 생성기를 사용하는 경우 가정이 무너집니다. 엔트로피 소스가 고갈되거나(일부 임베디드 시스템이나 로드 중인 가상 머신에서 발생) 프로세스 간에 무작위 상태가 재설정되지 않는 경우(CSPRNG를 다시 시드하지 않고 프로세스 분기) 충돌 위험이 급격히 증가합니다.
여기서 다루지 않는 내용 — v1 및 v7 고유성, 이는 무작위성보다는 타임스탬프 및 시계 시퀀스에 달려 있습니다.
ToolAcre 폴백은 각 바이트 배열에 대해 crypto.getRandomValues를 호출하고 애플리케이션 수준 PRNG 상태를 유지하지 않습니다. 플랫폼 내부는 브라우저와 운영 체제의 책임입니다. 실제 발전기와의 충돌 시뮬레이션은 이론과 실제 사례의 차이를 보여줍니다. 동일한 시드에서 시작하여 Math.random으로 구축된 생성기는 동일한 시퀀스를 생성합니다. 생일 근사치가 예측하는 대로 2^60 값(2^122의 제곱근) 이후가 아닌 수백에서 수천 개의 생성된 값 내에서 첫 번째 UUID 충돌을 볼 수 있습니다. 건전한 OS 엔트로피의 crypto.getRandomValues를 사용하는 생성기는 이론적 확률이 피할 수 없게 되는 경우에만(약 2^60 UUID) 충돌을 생성합니다. 이 숫자는 너무 커서 절대 도달할 수 없습니다. 약하거나 재사용되는 엔트로피 소스(잘못 구현된 UUID 라이브러리 또는 테스트 프레임워크에서 흔히 발생)를 사용하는 생성기는 그 사이 어딘가에서 충돌을 생성합니다.
요점: 수학을 신뢰하고 생성기를 감사합니다. ToolAcre 생성기는 위조해서는 안 되는 부분인 브라우저의 CSPRNG를 사용합니다.
일괄 테스트는 상수를 반환하거나 명확한 시퀀스를 재생하는 구현을 포착할 수 있지만 합격 샘플은 미래의 고유성을 증명할 수 없습니다. 프로덕션 시스템은 중복 식별자로 인해 데이터가 손상될 수 있는 경우에도 고유 제약 조건을 적용해야 합니다. 두 개의 유효한 소스 시스템이 이미 동일한 리터럴 식별자를 포함할 수 있고 설비가 환경 간에 복사될 수 있으므로 가져오기에는 특별한 주의가 필요합니다. ToolAcre의 테스트는 500 배치에 500 고유 값이 포함되어 있는지 확인합니다. 이는 통계적 보장이 아니라 이 구현에 대한 회귀 확인입니다. 중복이 나타나면 원인을 규명하기 전에 증거를 보존하고 생성, 가져오기, 고정 및 저장 경로를 검사합니다.