Strumenti per sviluppatori · Generatore UUID
Quanti bit casuali ha un UUID v4? 122, non 128
· Come funziona
uuid crittografia API del browser
Sei dei 128 bits in un UUID casuale sono fissi dallo standard, lasciando 122 per la casualità. Questo post mostra come stimare onestamente le probabilità di collisione e perché le collisioni reali derivano da generatori guasti e non dalla matematica.
La domanda dell'architetto: ne avremo mai un duplicato? – da dove viene la preoccupazione e perché la risposta dipende dal generatore
L'architetto si chiede: se generiamo 10 milioni di UUID al giorno per dieci anni, ne otterremo mai un duplicato? La risposta onesta è: quasi certamente no, se il generatore è crittograficamente sicuro; quasi certamente sì, se il generatore è rotto. I calcoli di RFC 9562 sono validi: un v4 UUID con 122 bit casuali ha una probabilità di collisione di circa n² / 2 elevato alla 123a potenza, dove n è il numero di identificatori generati. Per la maggior parte dei sistemi reali, questa probabilità è trascurabile. Il problema è che questa formula presuppone che ogni bit sia veramente casuale. Se il generatore perde, si ripete o è stato seminato in modo prevedibile, la formula è sbagliata e i duplicati diventano inevitabili. Il layout 128-bit include quattro bit di versione (0100 per v4) e due bit di variante (10 per RFC 9562), che sono fissi e impostati dallo standard.
Per quali sei bit si parla: i quattro bit della versione e i due bit della variante, e perché sono impostati anziché casuali
Ciò lascia 122 bits alla casualità. La formulazione a volte viene chiamata 2 nei bit casuali 122, producendo valori univoci. Utilizzando l'approssimazione del paradosso del compleanno, la probabilità di almeno una collisione tra n valori generati casualmente è di circa n² / 2 alla 123esima. Per n = 1 milioni, questo è (10^6)² / 2^123 = 10^12 / 9. 3 × 10^36, ovvero circa 10^-25. Per n = 10 miliardi, si tratta ancora di 10^-16. Questi non sono "effettivamente zero"; sono "non lo osserverai mai". L'approssimazione della data di nascita fornisce un modo concreto per calcolare il rischio: conta gli UUID che intendi generare, eleva il numero a quel numero, dividi per 2 alla 123a potenza. Se il generatore è crypto.getRandomValues del browser, ogni bit è supportato dall'entropia del sistema operativo. Se è matematica.
L'approssimazione della data di nascita in termini semplici: la probabilità di almeno una collisione tra n identificatori è approssimativamente n al quadrato diviso per 2 per 123
Per un UUID prodotto da un generatore inadatto o a stati ripetuti, il modello matematico fallisce perché il suo presupposto di indipendenza è falso. Un seed di test fisso, un dispositivo copiato o un'istantanea del processo possono riprodurre i valori anche se il testo contiene ancora il nibble versione-4. Questi sono difetti di implementazione, non una prova che il calcolo del campo 122 fosse sbagliato. Un'altra fonte banale consiste nel copiare lo stesso identificatore letterale in diversi dispositivi e successivamente unire i loro dati. Quando si indaga su un duplicato, preservare il generatore, la policy di seed, il ciclo di vita del processo e la cronologia delle importazioni. Non saltare da un valore ripetuto all'affermazione che l'output CSPRNG indipendente ha esaurito lo spazio UUID.
Esempio pratico: inserimento di un tasso di generazione e di un intervallo di tempo dichiarati nell'approssimazione, con ogni passaggio mostrato in modo da poter sostituire le proprie cifre
Forking del processo senza risincronizzazione dello stato casuale. Un bug in cui veniva utilizzato Math.random invece di crypto.getRandomValues. Un apparecchio di prova realizzato a mano con lo stesso UUID su più file e utilizzato accidentalmente in produzione. Una vecchia versione di una libreria UUID che presentava una limitazione di intervallo o un bug di stato. Nessuno di questi scenari coinvolge la matematica di approssimazione del compleanno; implicano implementazioni non corrette o errori operativi. Calcola onestamente il rischio di collisione per il tuo sistema: conta il tasso di generazione di UUID (al secondo, al giorno, all'anno), proiettalo nel tempo in cui il sistema funzionerà e inserisci il totale nella formula del compleanno. Se il tuo sistema genera 100,000 UUID al giorno per cinque anni (182 milioni in totale), la probabilità di collisione è (1. 82 × 10^8)² / 2^123 ≈ 3. 3 × 10^-22, che è trascurabile.
Da dove provengono effettivamente i duplicati: seed Math.random, macchine virtuali clonate, processi biforcati con stato copiato e copia-incolla nelle apparecchiature
Se generi 10 milioni al secondo per un anno (315 trilioni in totale), la probabilità è (3. 15 × 10^14)² / 2^123 ≈ 10^-10, che è ancora incredibilmente piccolo. Queste stime presuppongono che ogni bit sia indipendente e casuale. Il generatore ToolAcre utilizza crypto.getRandomValues, che ti offre casualità supportata da CSPRNG; l'operazione è l'unica parte di cui ti devi fidare. Non fare mai affidamento sulla probabilità di collisione come scusa per saltare i controlli di autorizzazione adeguati. A UUID non è una password, non un token di accesso e non un segreto anche se si tratta di 122 bit casuali. L'unicità è il vantaggio; l'imprevedibilità è una proprietà separata (e più importante) che impedisce di indovinare. La matematica del compleanno gestisce l'unicità; non riguarda la durata (questo UUID dovrebbe scadere? ), la segretezza (deve essere sottoposto ad hashing prima dell'archiviazione?) o l'autorizzazione (il possesso di questo UUID prova qualcosa sul chiamante?). Il generatore ToolAcre ti fornisce UUID supportati da CSPRNG con 122 bit casuali, il che significa che l'unicità della matematica è mantenuta e l'imprevedibilità è valida. Tutto il resto (convalida del token, scadenza, controllo dell'accesso) è responsabilità della tua applicazione. La formula della probabilità presuppone l'indipendenza di ciascun UUID generato dalle generazioni precedenti. Se il tuo sistema genera identificatori da una singola istanza CSPRNG e ogni chiamata trae nuova casualità dal sistema operativo, vale il presupposto di indipendenza. Se il tuo sistema utilizza uno stato CSPRNG memorizzato nella cache o un generatore di seeding senza reseeding del sistema operativo, il presupposto non funziona. Il rischio di collisione aumenta notevolmente se la fonte di entropia è esaurita (si verifica su alcuni sistemi embedded o macchine virtuali sotto carico) o se lo stato casuale non viene mai reimpostato tra i processi (biforcazione del processo senza re-seeding di CSPRNG).
Ciò che questo non copre: l'unicità delle versioni v1 e v7, che si basa su timestamp e sequenze di clock piuttosto che sulla sola casualità
Il fallback ToolAcre chiama crypto.getRandomValues per ogni matrice di byte e non mantiene lo stato PRNG a livello di applicazione. Gli aspetti interni della piattaforma rimangono di responsabilità del browser e del sistema operativo. La simulazione di collisioni con generatori reali mostra la differenza tra teoria e pratica fallita. Un generatore costruito con Math.random partendo dallo stesso seed produrrà sequenze identiche; vedrai la prima collisione UUID entro poche centinaia o poche migliaia di valori generati, non dopo i valori 2^60 (la radice quadrata di 2^122) come prevede l'approssimazione della data di nascita. Un generatore che utilizza crypto.getRandomValues dall'entropia del sistema operativo audio produrrà collisioni solo quando la probabilità teorica diventa inevitabile (intorno a 2^60 UUID), un numero così grande che non lo raggiungerai mai. Un generatore che utilizza una fonte di entropia debole o riutilizzata (comune nelle librerie UUID o nei framework di test scarsamente implementati) produrrà collisioni nel mezzo.
Conclusione: fidati dei calcoli, controlla il generatore: il generatore ToolAcre utilizza CSPRNG del browser, che è la parte che non deve essere falsificata
Un test batch può individuare un'implementazione che restituisce una costante o riproduce una sequenza ovvia, ma un campione passante non può dimostrare la futura unicità. I sistemi di produzione dovrebbero comunque applicare un vincolo univoco ovunque gli identificatori duplicati danneggino i dati. Le importazioni meritano un'attenzione speciale perché due sistemi di origine validi possono già contenere lo stesso identificatore letterale e le apparecchiature possono essere copiate tra ambienti. I test di ToolAcre verificano che un batch di 500 contenga 500 valori distinti; si tratta di un controllo di regressione per questa implementazione, non di una garanzia statistica. Se viene visualizzato un duplicato, conservare le prove e ispezionare i percorsi di generazione, importazione, fissaggio e archiviazione prima di attribuire una causa.