Como original é UUID?
https://stackoverflow.com/questions/1155008
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Como é que é seguro usar UUID para identificar alguma coisa (eu estou usando-o para arquivos enviados para o servidor)? Pelo que entendi, ele é baseado fora números aleatórios. No entanto, parece-me que, dado tempo suficiente, ele acabaria por repeti-lo auto, apenas por puro acaso. Existe um sistema melhor ou um padrão de algum tipo para aliviar este problema?
Solução
Muito seguro:
O risco anual de uma determinada pessoa ser atingida por um meteorito é Estima-se que uma chance em 17 mil milhões, o que significa o probabilidade é de cerca de ,00000000006 (6 × 10 -11 ), equivalente às probabilidades da criação de algumas dezenas de trilhões de UUIDs em um ano e ter um duplicado. Em outras palavras, somente depois de gerar 1 bilhão de UUIDs cada segundo para os próximos 100 anos, a probabilidade de criar apenas uma duplicata seria cerca de 50%.
Aviso:
No entanto, estas probabilidades detêm apenas quando os UUIDs são gerados usando entropia suficiente. Caso contrário, a probabilidade de duplicatas Pode ser significativamente mais elevada, uma vez que a força de dispersão estatística ser inferior. Onde identificadores exclusivos são necessários para distribuídos aplicações, de modo que UUIDs não se chocam mesmo quando os dados de muitos dispositivos é mesclado, a aleatoriedade das sementes e geradores utilizados em cada dispositivo deve ser confiável para a vida da aplicação. Onde isso não é viável, RFC4122 recomenda o uso de uma variante namespace em seu lugar.
Fonte: Aleatório UUID probabilidade de duplicatas seção do artigo da Wikipedia sobre identificadores universalmente exclusivo (link leva a uma revisão de dezembro 2016 antes de editar reformulado seção).
Veja também a seção atual sobre o mesmo assunto no mesmo artigo identificador universalmente exclusivo, colisões .
Outras dicas
Se por "dado tempo suficiente" você quer dizer 100 anos e você está criando-os a uma taxa de um bilhão de um segundo, então sim, você tem 50% de chance de ter uma colisão depois de 100 anos.
Há mais de um tipo de UUID, por isso "o quão seguro" depende do tipo (que as especificações UUID chamamos de "versão") que você está usando.
-
Versão 1 é o tempo com base acrescido de endereço MAC UUID. Os 128 bits contém 48 bits de endereço MAC da placa de rede (que é atribuído exclusivamente pelo fabricante) e um relógio de 60 bits com uma resolução de 100 nanossegundos. Aquele relógio wraps em 3603 AD assim que estes UUIDs são seguros, pelo menos até então (a menos que você precisa de mais de 10 milhões de novos UUIDs por segundo ou alguém clones sua placa de rede). Digo "pelo menos", porque o relógio começa em 15 de Outubro de 1582, assim que você tem cerca de 400 anos após os envoltórios relógio antes que haja mesmo uma pequena possibilidade de duplicações.
-
A versão 4 é o número aleatório UUID. Há seis bits fixos e o resto do UUID é de 122-bits de aleatoriedade. Consulte Wikipedia ou outra análise que descrevem como muito uma duplicata improvável é.
-
Versão 3 é usos MD5 e Versão 5 usos SHA-1 para criar essas 122 bits, em vez de um gerador de números aleatórios ou pseudo-aleatórios. Assim, em termos de segurança é como Versão 4 ser uma questão estatística (contanto que você certifique-se que o algoritmo de digerir é o processamento é sempre único).
-
A versão 2 é similar à versão 1, mas com um relógio menor de modo que vai envolver em torno de muito mais cedo. Mas desde a versão 2 UUIDs são para DCE, você não deve estar usando estes.
Assim, para todos os problemas práticos que são seguros. Se você está desconfortável com deixando para probabilidades (por exemplo, o seu é o tipo de pessoa preocupada com a terra ser destruído por um grande asteróide em sua vida), apenas certifique-se de usar uma versão 1 UUID e é garantido que ser exclusivo ( em sua vida, a menos que você planeja para o passado vivo 3603 AD).
Então, por que nem todo mundo simplesmente usar a versão 1 UUIDs? Isso é porque a Versão 1 UUIDs revelar o endereço MAC da máquina que foi gerado e eles podem ser previsível -. Duas coisas que podem ter implicações de segurança para o aplicativo usando esses UUIDs
A resposta a esta pode depender em grande parte da versão UUID.
Muitos geradores UUID usar um número aleatório versão 4. No entanto, muitos destes uso Pseudo um número gerador aleatório para gerá-los.
Se um mal semeado PRNG com um pequeno período é usado para gerar o UUID eu diria que não é muito seguro em tudo.
Por isso, é apenas tão seguro quanto os algoritmos usados ??para gerá-la.
Por outro lado, se você sabe a resposta a estas perguntas, então eu acho que a versão 4 UUID deve ser muito seguro de usar. Na verdade eu estou usando-o para identificar blocos em um sistema de arquivos bloco de rede e até agora não tive um choque.
No meu caso, o PRNG que estou usando é um Mersenne twister e eu estou tendo o cuidado com a forma como ele é semeado que é a partir de múltiplas fontes, incluindo / dev / urandom. Mersenne twister tem um período de 2 ^ 19937 -. 1. Vai ser um muito, muito tempo antes de eu ver uma repetição uuid
Assim, qualquer pessoa pode criar um UUID e uso -lo para identificar algo com confiança razoável de que a identificador nunca será inadvertidamente usado por qualquer pessoa para qualquer outra coisa
Ele passa a explicar em detalhe boa bonita em quão seguro ele realmente é. Então, para responder sua pergunta:. Sim, é bastante segura
esquemas UUID geralmente usam não só um elemento pseudo-aleatório, mas também o tempo atual do sistema, e algum tipo de identificação de hardware muitas vezes única, se disponíveis, como um endereço MAC da rede.
O ponto inteiro de usar UUID é que você confiar nele para fazer um trabalho melhor de fornecer uma identificação única que você mesmo seria capaz de fazer. Esta é a mesma lógica por trás usando uma biblioteca parte 3 criptografia em vez de rolar seus próprios. Fazê-lo sozinho pode ser mais divertido, mas é tipicamente menos responsáveis ??para fazê-lo.
vem fazendo isso há anos. Nunca correr em um problema.
Normalmente, eu configurar meu DB é ter uma tabela que contém todas as chaves e as datas modificadas e tal. Já não correr em um problema de chaves duplicadas de sempre.
A única desvantagem que tem é quando você está escrevendo algumas consultas para encontrar algumas informações rapidamente você está fazendo um monte de copiar e colar das chaves. Você não tem a curto fácil de lembrar ids mais.
Aqui está um trecho de teste para que você possa testá-lo de uniquenes. inspirado por @ o comentário de scalabl3
O engraçado é que você poderia gerar 2 em uma linha que eram idênticos, naturalmente em níveis alucinantes de coincidência, sorte e intervenção divina, mas apesar das probabilidades insondáveis, ainda é possível! : D Sim, isso não vai acontecer. apenas dizendo para a diversão de pensar sobre aquele momento em que você criou uma duplicata! Capturas de tela video! - scalabl3 20 de outubro '15 em 19:11
Se você se sente com sorte, marque a caixa de seleção, ele só verifica a ID gerada atualmente de. Se você deseja um cheque história, deixá-la desmarcada. Por favor, note que você pode funcionar fora do carneiro, em algum momento, se você deixá-la desmarcada. Eu tentei fazê-lo CPU amigável para que você possa abortar rapidamente quando necessário, é só apertar o botão de execução trecho novamente ou sair da página.
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/>
Concordo com as outras respostas. UUIDs são suficientes seguro para fins de quase todos práticos 1 , e certamente para o seu.
Mas suponha (hipoteticamente) que eles não são.
Existe um sistema melhor ou um padrão de algum tipo para aliviar este problema?
Aqui estão algumas abordagens:
-
Use um maior UUID. Por exemplo, em vez de um 128 bits aleatórios, use 256 ou 512 ou ... Cada bit você adicionar a um UUID tipo 4 estilo vai reduzir a probabilidade de uma colisão por um semestre, supondo que você tem uma fonte confiável de entropia < sup> 2 .
-
Criar um serviço centralizado ou distribuído que gera UUIDs e registra todos e cada um que jamais emitido. Cada vez que ele gera um novo, ele verifica que o UUID nunca foi emitido antes. serviço tal seria tecnicamente simples e direta para implementar (eu acho), se assumimos que as pessoas que executam o serviço eram absolutamente confiável, incorruptível, etcetera. Infelizmente, eles não são ... especialmente quando há a possibilidade dos governos interferem. Assim, esta abordagem é provavelmente impraticável, e pode ser 3 impossível no mundo real.
1 - Se singularidade de UUIDs determinado se os mísseis nucleares foi lançada na capital do seu país, muitos de seus concidadãos não seria convencido por "a probabilidade é extremamente baixa". Daí a minha "quase todos" qualificação.
2 - E aqui está uma questão filosófica para você. É qualquer coisa que nunca verdadeiramente aleatório? Como saberíamos se não fosse? É o universo como o conhecemos uma simulação? Existe um Deus que poderia concebivelmente "ajustar" as leis da física para alterar um resultado?
3 -. Se alguém souber de quaisquer trabalhos de pesquisa sobre este problema, por favor comentário
Eu não sei se isso é importante para você, mas tenha em mente que GUIDs são globalmente únicos, mas substrings de GUIDs não são .
