Come unica è UUID?
https://stackoverflow.com/questions/1155008
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Quanto è sicuro da usare UUID per identificare in modo univoco qualcosa (lo sto usando per i file caricati sul server)? A quanto mi risulta, si è basato fuori numeri casuali. Tuttavia, sembra a me che dato abbastanza tempo, si sarebbe poi ripeterlo sé, solo per puro caso. Esiste un sistema migliore o uno schema di un certo tipo per alleviare questo problema?
Soluzione
Molto sicuro:
il rischio annuale di una data persona che viene colpita da un meteorite è stimata essere una possibilità su 17 miliardi, il che significa che il probabilità è di circa ,00000000006 (6 × 10 -11 ), equivalente alle probabilità della creazione di poche decine di bilioni di UUID in un anno e che hanno uno duplicare. In altre parole, solo dopo che la generazione di 1 miliardo di UUID ogni secondo per i prossimi 100 anni, la probabilità di creare un solo duplicare sarebbe di circa il 50%.
Caveat:
Tuttavia, queste probabilità tengono solo quando gli UUID vengono generati utilizzando entropia sufficiente. In caso contrario, la probabilità di duplicati potrebbe essere significativamente superiore, in quanto la dispersione statistica potrebbe essere inferiore. Dove unico identificatori sono necessari per distribuire le applicazioni, in modo che gli UUID non si scontrano anche quando i dati da molti dispositivi è uniti, la casualità dei semi e generatori usato su Ogni dispositivo deve essere affidabile per la durata dell'applicazione. Dove questo non è fattibile, RFC4122 consiglia di utilizzare una variante namespace invece.
Fonte: Il a caso UUID probabilità di duplicati sezione di questo articolo di Wikipedia su uuid (link porta ad una revisione da dicembre 2016 prima della modifica rielaborato la sezione).
Si veda anche la sezione corrente sullo stesso argomento sullo stesso articolo identificatore univoco universale, collisioni .
Altri suggerimenti
Se per "dato abbastanza tempo" intendi 100 anni e si sta creando loro al ritmo di un miliardo di un secondo, allora sì, si ha una probabilità del 50% di avere una collisione dopo 100 anni.
C'è più di un tipo di UUID, così "come sicuro" dipende da quale tipo (che le specifiche UUID chiamano "versione") che si sta utilizzando.
-
La versione 1 è il tempo basato più l'indirizzo MAC UUID. Il 128-bit contiene 48 bit di indirizzo MAC della scheda di rete (che è assegnato in modo univoco dal costruttore) e un orologio 60 bit con una risoluzione di 100 nanosecondi. Questo orologio avvolge nel 3603 dC così questi UUID sono sicuri, almeno fino a quel momento (a meno che non avete bisogno di più di 10 milioni di nuovi UUID al secondo o qualcuno cloni la scheda di rete). Dico "almeno" perché l'orologio inizia al 15 ottobre 1582, in modo da avere circa 400 anni dopo che l'orologio si avvolge prima che ci sia anche una piccola possibilità di duplicazioni.
-
La versione 4 è il numero UUID casuale. C'è sei bit fissi e il resto del UUID è 122 bit di casualità. Vedere Wikipedia o altra analisi che descrivono il modo molto improbabile un duplicato è.
-
Versione 3 è utilizza MD5 e Versione 5 utilizza SHA-1 per creare quei 122 bit, invece di un generatore di numeri casuali o pseudo-casuale. Quindi, in termini di sicurezza è come la versione 4 di essere un problema di statistica (fino a quando si assicurarsi che ciò che il digest algoritmo è l'elaborazione è sempre unico).
-
La versione 2 è simile alla versione 1, ma con un orologio più piccolo in modo che sta per avvolgere intorno molto prima. Ma dal momento che la versione 2 UUID sono per DCE, non si dovrebbe essere l'utilizzo di questi.
Quindi, per tutti i problemi pratici che sono sicuri. Se vi sentite a disagio con lasciando a probabilità (per esempio il vostro sono il tipo di persona preoccupata per la terra ottenendo distrutta da un asteroide di grandi dimensioni nella vostra vita), basta assicurarsi di utilizzare una versione 1 UUID ed è garantito per essere unico ( nella tua vita, a meno che non si ha intenzione di vivere oltre 3603 dC).
Allora, perché non tutti è sufficiente utilizzare la versione 1 UUID? Questo perché la versione 1 UUID rivelano l'indirizzo MAC della macchina è stato generato su e possono essere prevedibile -. Due cose che potrebbero avere implicazioni di sicurezza per l'applicazione utilizzando quei UUID
La risposta a questa può dipendere in larga misura dalla versione UUID.
Molti generatori UUID utilizzano un numero casuale versione 4. Tuttavia, molti di questi utilizzano Pseudo un generatore di numeri casuali per generare loro.
Se un PRNG mal testa di serie, con un piccolo periodo viene utilizzato per generare l'UUID direi che non è molto sicuro a tutti.
Pertanto, è solo sicuro come gli algoritmi utilizzati per generarla.
Il rovescio della medaglia, se si conosce la risposta a queste domande, allora penso che un uuid versione 4 dovrebbe essere molto sicuro da usare. In realtà sto usando per identificare i blocchi su un file system di rete di blocco e finora non ho avuto uno scontro.
Nel mio caso, il PRNG che sto utilizzando è un tornado Mersenne e sto prestando attenzione al modo in cui è testa di serie, che è da più fonti, tra cui / dev / urandom. twister Mersenne ha un periodo di 2 ^ 19937 -. 1. Sta andando essere un tempo molto lungo prima di vedere una ripetizione uuid
In questo modo, chiunque può creare un UUID e l'uso di identificare qualcosa con ragionevole fiducia che il identificatore non sarà mai involontariamente utilizzato da chiunque per nient'altro
Si va avanti a spiegare in buona dettagli su come sicuro sia in realtà. Quindi, per rispondere alla tua domanda:. Sì, è abbastanza sicuro
regimi UUID utilizzano generalmente non solo un elemento pseudo-casuale, ma anche il tempo di sistema attuale, e una sorta di ID hardware spesso unico se disponibile, ad esempio un indirizzo MAC di rete.
Il punto di usare UUID è che vi fidate a fare un lavoro migliore di fornire un ID univoco di quanto voi stessi sarebbe in grado di fare. Questa è la stessa logica che sta dietro all'uso di un terzo libreria di crittografia partito piuttosto che rotolare il proprio. Fai da te può essere più divertente, ma è in genere meno responsabile di farlo.
ha fatto per anni. Mai incontrato un problema.
Io di solito impostato il mio DB di avere una tabella che contiene tutte le chiavi e le date modificate e così via. Non hanno incontrato un problema di chiavi duplicate di sempre.
L'unico svantaggio che ha è quando si sta scrivendo alcune query per trovare qualche informazione in fretta si sta facendo un sacco di copia e incolla delle chiavi. Non si dispone di breve facile da ricordare più id.
Ecco un frammento di prova per testare è uniquenes. ispirato dal commento di @ scalabl3
La cosa divertente è, si potrebbe generare 2 di fila che erano identici, ovviamente a livelli da capogiro di coincidenza, fortuna e l'intervento divino, ma nonostante le probabilità insondabili, è ancora possibile! : D Sì, non accadrà. solo dicendo per il divertimento di pensare a quel momento in cui si è creato un duplicato! il video screenshot! - scalabl3 20 ottobre '15 a 19:11
Se ti senti fortunato, selezionare la casella di controllo, che controlla solo le attualmente generati id. Se si desidera un controllo di storia, lasciare incontrollato. Ti informiamo che potrebbe a corto di RAM ad un certo punto se si lascia deselezionato. Ho cercato di rendere più accogliente della CPU in modo da poter interrompere rapidamente quando necessario, basta premere nuovamente il pulsante di esecuzione frammento o lasciare la pagina.
Math.log2 = Math.log2 || function(n){ return Math.log(n) / Math.log(2); }
Math.trueRandom = (function() {
var crypt = window.crypto || window.msCrypto;
if (crypt && crypt.getRandomValues) {
// if we have a crypto library, use it
var random = function(min, max) {
var rval = 0;
var range = max - min;
if (range < 2) {
return min;
}
var bits_needed = Math.ceil(Math.log2(range));
if (bits_needed > 53) {
throw new Exception("We cannot generate numbers larger than 53 bits.");
}
var bytes_needed = Math.ceil(bits_needed / 8);
var mask = Math.pow(2, bits_needed) - 1;
// 7776 -> (2^13 = 8192) -1 == 8191 or 0x00001111 11111111
// Create byte array and fill with N random numbers
var byteArray = new Uint8Array(bytes_needed);
crypt.getRandomValues(byteArray);
var p = (bytes_needed - 1) * 8;
for(var i = 0; i < bytes_needed; i++ ) {
rval += byteArray[i] * Math.pow(2, p);
p -= 8;
}
// Use & to apply the mask and reduce the number of recursive lookups
rval = rval & mask;
if (rval >= range) {
// Integer out of acceptable range
return random(min, max);
}
// Return an integer that falls within the range
return min + rval;
}
return function() {
var r = random(0, 1000000000) / 1000000000;
return r;
};
} else {
// From http://baagoe.com/en/RandomMusings/javascript/
// Johannes Baagøe <baagoe@baagoe.com>, 2010
function Mash() {
var n = 0xefc8249d;
var mash = function(data) {
data = data.toString();
for (var i = 0; i < data.length; i++) {
n += data.charCodeAt(i);
var h = 0.02519603282416938 * n;
n = h >>> 0;
h -= n;
h *= n;
n = h >>> 0;
h -= n;
n += h * 0x100000000; // 2^32
}
return (n >>> 0) * 2.3283064365386963e-10; // 2^-32
};
mash.version = 'Mash 0.9';
return mash;
}
// From http://baagoe.com/en/RandomMusings/javascript/
function Alea() {
return (function(args) {
// Johannes Baagøe <baagoe@baagoe.com>, 2010
var s0 = 0;
var s1 = 0;
var s2 = 0;
var c = 1;
if (args.length == 0) {
args = [+new Date()];
}
var mash = Mash();
s0 = mash(' ');
s1 = mash(' ');
s2 = mash(' ');
for (var i = 0; i < args.length; i++) {
s0 -= mash(args[i]);
if (s0 < 0) {
s0 += 1;
}
s1 -= mash(args[i]);
if (s1 < 0) {
s1 += 1;
}
s2 -= mash(args[i]);
if (s2 < 0) {
s2 += 1;
}
}
mash = null;
var random = function() {
var t = 2091639 * s0 + c * 2.3283064365386963e-10; // 2^-32
s0 = s1;
s1 = s2;
return s2 = t - (c = t | 0);
};
random.uint32 = function() {
return random() * 0x100000000; // 2^32
};
random.fract53 = function() {
return random() +
(random() * 0x200000 | 0) * 1.1102230246251565e-16; // 2^-53
};
random.version = 'Alea 0.9';
random.args = args;
return random;
}(Array.prototype.slice.call(arguments)));
};
return Alea();
}
}());
Math.guid = function() {
return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
var r = Math.trueRandom() * 16 | 0,
v = c == 'x' ? r : (r & 0x3 | 0x8);
return v.toString(16);
});
};
function logit(item1, item2) {
console.log("Do "+item1+" and "+item2+" equal? "+(item1 == item2 ? "OMG! take a screenshot and you'll be epic on the world of cryptography, buy a lottery ticket now!":"No they do not. shame. no fame")+ ", runs: "+window.numberofRuns);
}
numberofRuns = 0;
function test() {
window.numberofRuns++;
var x = Math.guid();
var y = Math.guid();
var test = x == y || historyTest(x,y);
logit(x,y);
return test;
}
historyArr = [];
historyCount = 0;
function historyTest(item1, item2) {
if(window.luckyDog) {
return false;
}
for(var i = historyCount; i > -1; i--) {
logit(item1,window.historyArr[i]);
if(item1 == history[i]) {
return true;
}
logit(item2,window.historyArr[i]);
if(item2 == history[i]) {
return true;
}
}
window.historyArr.push(item1);
window.historyArr.push(item2);
window.historyCount+=2;
return false;
}
luckyDog = false;
document.body.onload = function() {
document.getElementById('runit').onclick = function() {
window.luckyDog = document.getElementById('lucky').checked;
var val = document.getElementById('input').value
if(val.trim() == '0') {
var intervaltimer = window.setInterval(function() {
var test = window.test();
if(test) {
window.clearInterval(intervaltimer);
}
},0);
}
else {
var num = parseInt(val);
if(num > 0) {
var intervaltimer = window.setInterval(function() {
var test = window.test();
num--;
if(num < 0 || test) {
window.clearInterval(intervaltimer);
}
},0);
}
}
};
};Please input how often the calulation should run. set to 0 for forever. Check the checkbox if you feel lucky.<BR/>
<input type="text" value="0" id="input"><input type="checkbox" id="lucky"><button id="runit">Run</button><BR/>
Sono d'accordo con le altre risposte. UUID sono abbastanza sicuro per gli scopi pratici quasi tutti 1 , e certamente per il vostro.
Ma supponiamo (ipoteticamente) che non lo sono.
Esiste un sistema migliore o uno schema di un certo tipo per alleviare questo problema?
Qui ci sono un paio di approcci
-
Usa un UUID più grande. Per esempio, invece di un 128 bit casuali, utilizzare 256 o 512 o ... Ogni bit si aggiunge ad un UUID tipo-4 stile ridurrà la probabilità di una collisione con un mezzo, a patto che abbiate una fonte affidabile di entropia < sup> 2 .
-
Creare un servizio centralizzata o distribuita che genera UUID e registra tutti e ciascuno ha mai emesso. Ogni volta che genera uno nuovo, controlla che l'UUID non è mai stato rilasciato prima. Tale servizio sarebbe tecnicamente straight-forward per implementare (credo) se abbiamo ipotizzato che le persone che gestiscono il servizio erano assolutamente affidabile, incorruttibile, eccetera. Purtroppo, non sono ... soprattutto quando c'è la possibilità dei governi interferenti. Quindi, questo approccio è probabilmente impraticabile, e può essere 3 impossibili nel mondo reale.
1 - Se unicità di UUID verificare se missili nucleari lanciati ricevuti a capitale del suo paese, un sacco di vostri concittadini non sarebbe stato convinto da "la probabilità è molto bassa". Da qui la mia "quasi tutti" qualificazione.
2 - Ed ecco una questione filosofica per voi. C'è qualcosa che non mai veramente casuale? Come potremmo sapere se non fosse? È l'universo come lo conosciamo una simulazione? Esiste un Dio che potrebbe plausibilmente "tweak" le leggi della fisica per alterare un risultato?
3 -. Se qualcuno sa di eventuali documenti di ricerca su questo problema, si prega di commento
Non so se questo è importante per voi, ma tenete a mente che GUID sono globalmente unici, ma sottostringhe di GUID non sono .
