Quão único é o UUID?

451

Quão seguro é usar o UUID para identificar algo de maneira exclusiva (estou usando-o para arquivos carregados no servidor)? Pelo que entendi, é baseado em números aleatórios. No entanto, parece-me que, com tempo suficiente, acabaria por se repetir, apenas por puro acaso. Existe um sistema ou um padrão melhor de algum tipo para aliviar esse problema?

Jason
fonte
11
Para um valor suficientemente grande de "tempo suficiente" :)
91
"Quão único é o UUID?" Universalmente único, acredito. ;)
Miles
29
E, a menos que você planeje desenvolver Venus, um GUID deve ser suficiente.
21410 skaffman
1
mais detalhes e gerador aqui: gerador uuid on-line
Dave
2
"único" significa nunca colidir . Se tem algum potencial de colidir, não é único . Portanto, por definição, o UUID não é exclusivo e seguro apenas se você estiver preparado para possíveis colisões, independentemente da chance de colisões. Caso contrário, seu programa está simplesmente incorreto. Você pode dizer UUID como "quase único", mas isso não significa que seja "único".
Eonil

Respostas:

444

Muito seguro:

o risco anual de uma determinada pessoa ser atingida por um meteorito é estimado em uma chance em 17 bilhões, o que significa que a probabilidade é de cerca de 0,00000000006 (6 × 10-11 ), equivalente à probabilidade de criar algumas dezenas de trilhões de UUIDs em um ano e com uma duplicata. Em outras palavras, somente após gerar 1 bilhão de UUIDs a cada segundo nos próximos 100 anos, a probabilidade de criar apenas uma duplicata seria de cerca de 50%.

Embargo:

No entanto, essas probabilidades são válidas apenas quando os UUIDs são gerados usando entropia suficiente. Caso contrário, a probabilidade de duplicatas pode ser significativamente maior, pois a dispersão estatística pode ser menor. Onde identificadores exclusivos são necessários para aplicativos distribuídos, para que os UUIDs não colidam, mesmo quando os dados de muitos dispositivos são mesclados, a aleatoriedade das sementes e geradores usados ​​em cada dispositivo deve ser confiável para a vida útil do aplicativo. Onde isso não for possível, o RFC4122 recomenda o uso de uma variante de namespace.

Fonte: A seção de probabilidade de duplicatas UUID aleatória do artigo da Wikipedia sobre identificadores universalmente exclusivos (o link leva a uma revisão a partir de dezembro de 2016 antes de editar a seção reformulada).

Consulte também a seção atual sobre o mesmo assunto no mesmo artigo de identificador universalmente universal, Colisões .

Martijn Pieters
fonte
22
Eu gosto desta parte da Wikipedia: No entanto, essas probabilidades só são válidas quando os UUIDs são gerados usando entropia suficiente. Caso contrário, a probabilidade de duplicatas pode ser significativamente maior, pois a dispersão estatística pode ser menor. Então, qual é a chance real de duplicar a anotação desta frase. Não podemos criar números aleatórios reais no computador, podemos?
mans
6
Na verdade, muito trabalho foi feito para encontrar maneiras de introduzir o máximo possível de entropia ("aleatoriedade real", acho que você chamaria) em APIs de números aleatórios. Veja en.wikipedia.org/wiki/Entropy_%28computing%29
broofa
4
Essa é realmente uma maior probabilidade de colisão do que eu imaginava. Paradoxo de aniversário, eu acho.
Cameron
Você pode confirmar que o uso do UUID seria seguro entre as execuções de um aplicativo? (por exemplo, um script python)
George Sp
grande exemplo ...: D
NuttLoose
151

Se, por "tempo suficiente", você quer dizer 100 anos e os cria a uma taxa de um bilhão por segundo, então sim, você tem 50% de chance de ter uma colisão após 100 anos.

rédea
fonte
185
Mas somente depois de usar 256 exabytes de armazenamento para esses IDs.
22610 Bob Aman
16
O engraçado é que você pode gerar dois seguidos que são idênticos, é claro, em níveis incompreensíveis 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 naquele momento em que você criou uma duplicata! Captura de tela de vídeo!
scalabl3
4
A singularidade é puramente por causa da aleatoriedade? Ou há outros fatores? (por exemplo, carimbo de data / hora, ip etc.)
Weishi Zeng
15
@TheTahaan Isso não é o que significa aleatório. Isso não significa "totalmente imprevisível" - geralmente eles seguem algum tipo de distribuição. Se você jogar 10 moedas, a chance de ganhar 2 caras, seguida de 3 caudas, seguida de 5 caras, é bem baixa (2 ^ -10, cerca de 0,001). É verdadeiramente aleatório, mas nós absolutamente pode conhecer a oportunidade de obter um determinado resultado. Nós simplesmente não podemos dizer antecipadamente se vai acontecer.
Richard Rast
5
Apenas para explicar o que essa implementação fez de errado, eles estão usando um UUID versão 1, que depende de uma combinação de carimbo de data e hora e endereço mac para sua exclusividade. No entanto, se você gerar UUIDs com rapidez suficiente, o registro de data e hora ainda não será incrementado. Nesse cenário, seu algoritmo de geração UUID deve rastrear o último registro de data e hora usado e aumentá-lo em 1. Eles claramente falharam em executar essa etapa. No entanto, todos os UUIDs da versão 1 gerados corretamente pela mesma máquina em um curto período exibem semelhanças óbvias, mas ainda devem ser únicos.
Bob Aman
103

Há mais de um tipo de UUID; portanto, "quão seguro" depende do tipo (que as especificações do UUID chamam de "versão") que você está usando.

  • A versão 1 é o UUID do endereço MAC com base no tempo. Os 128 bits contêm 48 bits para o endereço MAC da placa de rede (atribuído exclusivamente pelo fabricante) e um relógio de 60 bits com uma resolução de 100 nanossegundos. Esse relógio termina no 3603 AD, para que esses UUIDs estejam seguros pelo menos até então (a menos que você precise de mais de 10 milhões de novos UUIDs por segundo ou alguém clone sua placa de rede). Digo "pelo menos" porque o relógio começa em 15 de outubro de 1582, então você tem cerca de 400 anos depois que o relógio termina antes que haja uma pequena possibilidade de duplicação.

  • A versão 4 é o número aleatório UUID. Há seis bits fixos e o restante do UUID tem 122 bits de aleatoriedade. Veja a Wikipedia ou outra análise que descreve como é improvável uma duplicata.

  • A versão 3 usa MD5 e a versão 5 usa SHA-1 para criar esses 122 bits, em vez de um gerador de números aleatórios ou pseudo-aleatórios. Portanto, em termos de segurança, é como se a Versão 4 fosse um problema estatístico (desde que você tenha certeza de que o algoritmo de resumo está processando é sempre único).

  • A versão 2 é semelhante à versão 1, mas com um relógio menor, o que possibilitará a instalação muito mais cedo. Mas como os UUIDs da versão 2 são para DCE, você não deve usá-los.

Portanto, para todos os problemas práticos, eles são seguros. Se você não se sentir à vontade em deixar as probabilidades (por exemplo, você é o tipo de pessoa preocupada com a destruição da Terra por um grande asteróide em sua vida), certifique-se de usar um UUID da versão 1 e é garantido que ele seja único ( em sua vida, a menos que você planeje viver além do 3603 AD).

Então, por que todo mundo simplesmente não usa os UUIDs da versão 1? Isso ocorre porque os UUIDs da versão 1 revelam o endereço MAC da máquina em que foi gerado e podem ser previsíveis - duas coisas que podem ter implicações de segurança para o aplicativo que usa esses UUIDs.

Hoylen
fonte
1
A padronização para uma versão 1 do UUID apresenta sérios problemas quando são geradas pelo mesmo servidor para muitas pessoas. O UUID da versão 4 é o meu padrão, pois você pode escrever rapidamente algo para gerar um em qualquer idioma ou plataforma (incluindo javascript).
Justin Bozonier
1
@ Haylen Bem explicado! mas esse exagero é necessário?
Dinoop paloli
1
Teoricamente , é atribuído exclusivamente pelo fabricante.
OrangeDog
4
Não é necessário gerar 10 milhões de UUIDs da versão 1 em um segundo para encontrar uma duplicata; é preciso apenas gerar um lote de 16.384 UUIDs no intervalo de um único "tick" para exceder o número de sequência. Vi isso acontecer com uma implementação que se baseava, ingenuamente, em uma fonte de relógio que (1) apresentava granularidade no nível μs e (2) não era garantido que fosse monotônico (os relógios do sistema não são). Tenha cuidado com o código de geração UUID que você usa e tenha especial cuidado com os geradores UUID baseados em tempo. Eles são difíceis de acertar, então submeta-os a carregar testes antes de usá-los.
Mike Strobel
O intervalo de tempo entre os UUIDs v4 gerados pode levar a mais probabilidades de colisão? Em uma aplicação de tráfego pesado, suponha que milhares de uuids sejam gerados ao mesmo tempo, há mais chances de colisão do que se a mesma quantidade de uuids fosse gerada por um período de tempo relativamente mais longo?
Jonathan
18

A resposta para isso pode depender muito da versão do UUID.

Muitos geradores UUID usam um número aleatório da versão 4. No entanto, muitos deles usam o Pseudo um gerador de números aleatórios para gerá-los.

Se um PRNG mal propagado com um pequeno período for usado para gerar o UUID, eu diria que não é muito seguro.

Portanto, é tão seguro quanto os algoritmos usados ​​para gerá-lo.

Por outro lado, se você souber a resposta para essas perguntas, acho que um uuid da versão 4 deve ser muito seguro de usar. Na verdade, estou usando-o para identificar blocos em um sistema de arquivos de blocos de rede e até agora não houve um conflito.

No meu caso, o PRNG que estou usando é um twister de mersenne e estou sendo cuidadoso com o modo como é propagado, proveniente de várias fontes, incluindo / dev / urandom. Mersenne twister tem um período de 2 ^ 19937 - 1. Vai demorar muito, muito tempo até eu ver um uuid repetido.

Matt
fonte
14

Citando da Wikipedia :

Assim, qualquer pessoa pode criar um UUID e usá-lo para identificar algo com razoável confiança de que o identificador nunca será usado acidentalmente por alguém para qualquer outra coisa

Ele continua explicando com bastante bons detalhes como é realmente seguro. Então, para responder sua pergunta: Sim, é seguro o suficiente.

Dave Vogt
fonte
9

Eu concordo com as outras respostas. Os UUIDs são seguros o suficiente para quase todos os propósitos práticos 1 e certamente para os seus.

Mas suponha (hipoteticamente) que não sejam.

Existe um sistema ou um padrão melhor de algum tipo para aliviar esse problema?

Aqui estão algumas abordagens:

  1. Use um UUID maior. Por exemplo, em vez de 128 bits aleatórios, use 256 ou 512 ou ... Cada bit adicionado a um UUID do tipo 4 reduzirá pela metade a probabilidade de uma colisão, assumindo que você tenha uma fonte confiável de entropia 2 .

  2. Crie um serviço centralizado ou distribuído que gere UUIDs e registre todos e cada um que já emitiu. Cada vez que gera um novo, ele verifica se o UUID nunca foi emitido antes. Esse serviço seria tecnicamente simples de implementar (eu acho) se assumirmos que as pessoas que executam o serviço são absolutamente confiáveis, incorruptíveis, etc. Infelizmente, eles não são ... especialmente quando existe a possibilidade de as organizações de segurança dos governos interferirem. Assim, esta abordagem é provavelmente impraticável, e pode ser 3 impossível no mundo real.


1 - Se a singularidade dos UUIDs determinasse se os mísseis nucleares foram lançados na capital do seu país, muitos de seus concidadãos não se convenceriam de "a probabilidade é extremamente baixa". Daí a minha qualificação "quase toda".

2 - E aqui está uma pergunta filosófica para você. Alguma coisa é realmente aleatória? Como saberíamos se não fosse? O universo como o conhecemos é uma simulação? Existe um Deus que possa "ajustar" as leis da física para alterar um resultado?

3 - Se alguém souber de algum trabalho de pesquisa sobre esse problema, comente.

Stephen C
fonte
Eu só quero ressaltar que o método número 2 basicamente derrota o principal objetivo do uso de UUID e você também pode usar apenas um ID numerado clássico nesse momento.
Petr Vnenk
Discordo. A falha nos IDs numerados sequenciais é que eles são fáceis de adivinhar. Você deve conseguir implementar o método 2 de uma maneira que dificilmente adivinhe os UUIDs.
Stephen C
8

Os esquemas UUID geralmente usam não apenas um elemento pseudo-aleatório, mas também a hora atual do sistema e algum tipo de ID de hardware frequentemente único, se disponível, como um endereço MAC de rede.

O objetivo principal do uso do UUID é que você confia nele para oferecer um ID melhor do que você seria capaz de fazer. Essa é a mesma lógica por trás do uso de uma biblioteca de criptografia de terceiros, em vez de criar a sua própria. Fazer você mesmo pode ser mais divertido, mas geralmente é menos responsável.

Parappa
fonte
5

Faz isso há anos. Nunca tenha problemas.

Normalmente, configuro meus bancos de dados para ter uma tabela que contém todas as chaves e as datas modificadas e outras. Nunca deparei com um problema de chaves duplicadas.

A única desvantagem disso é que, quando você está escrevendo algumas consultas para encontrar rapidamente algumas informações, está copiando e colando muitas chaves. Você não tem mais os IDs curtos e fáceis de lembrar.

Póstuma
fonte
5

Aqui está um trecho de teste para você testar suas exclusões. inspirado pelo comentário de @ scalabl3

O engraçado é que você pode gerar dois seguidos que são idênticos, é claro, em níveis surpreendentes 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 naquele momento em que você criou uma duplicata! Captura de tela de vídeo! Você pode usar o seguinte código:

Se você tiver sorte, marque a caixa de seleção, que verifica apenas os IDs gerados atualmente. Se você deseja uma verificação do histórico, deixe-a desmarcada. Observe que você pode ficar sem memória RAM em algum momento se você a deixar desmarcada. Tentei torná-lo compatível com a CPU, para que você possa abortar rapidamente quando necessário, basta pressionar o botão de snippet de execução 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 <[email protected]>, 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 <[email protected]>, 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/>

Tschallacka
fonte
Tente com um UUID da RFC 4122 versão 1 (data e hora e endereço MAC).
Zaph 19/08/16
Costumava ser rápido, até uma atualização do Chrome recentemente. Eu tinha notado o mesmo há 4 semanas.
Tschallacka 16/03/19
3

Não sei se isso é importante para você, mas lembre-se de que os GUIDs são globalmente exclusivos, mas as subseqüências dos GUIDs não são .

Grant Wagner
fonte
1
Lembre-se de que a referência vinculada aqui fala sobre os UUIDs da versão 1 (que levam informações sobre o computador gerador etc. para o ID). A maioria das outras respostas fala sobre a versão 4 (que é totalmente aleatória). O artigo da Wikipedia vinculado acima en.wikipedia.org/wiki/Universally_unique_identifier explica os diferentes tipos de UUIDs.
precisa saber é o seguinte
3

Para o UUID4, considero que existem aproximadamente tantos IDs quanto grãos de areia em uma caixa em forma de cubo com lados de 360.000 km de comprimento. Essa é uma caixa com lados ~ 2 1/2 vezes mais que o diâmetro de Júpiter.

Trabalhando para que alguém possa me dizer se eu estraguei as unidades:

  • volume de grão de areia 0.00947mm ^ 3 ( Guardião )
  • O UUID4 possui 122 bits aleatórios -> 5.3e36 valores possíveis ( wikipedia )
  • volume de tantos grãos de areia = 5.0191e34 mm ^ 3 ou 5.0191e + 25m ^ 3
  • comprimento lateral da caixa cúbica com esse volume = 3,69E8m ou 369.000 km
  • diâmetro de Júpiter: 139.820 km (google)
perdido
fonte
Na verdade, acho que isso assume 100% de embalagem, então talvez eu deva adicionar um fator para isso!
perdeu