¿Qué tan único es UUID?

451

¿Qué tan seguro es usar UUID para identificar algo de manera única (lo estoy usando para archivos cargados en el servidor)? Según tengo entendido, se basa en números aleatorios. Sin embargo, me parece que con el tiempo suficiente, eventualmente se repetiría solo, por pura casualidad. ¿Existe un sistema mejor o un patrón de algún tipo para aliviar este problema?

Jason
fuente
11
Para un valor lo suficientemente grande de "tiempo suficiente" :)
9191
"¿Qué tan único es UUID?" Universalmente único, creo. ;)
Millas el
29
Y a menos que planee desarrollar en Venus, un GUID debería ser suficiente.
skaffman el
1
más detalles y generador aquí: generador de uuid en línea
Dave
2
"único" significa nunca chocar . Si tiene algún potencial de colisión, no es único . Por lo tanto, por definición, UUID no es único y seguro solo si está preparado para posibles colisiones, independientemente de la posibilidad de colisiones. De lo contrario, su programa es simplemente incorrecto. Puede decir UUID como "casi único" pero no significa que sea "único".
Eonil

Respuestas:

444

Muy seguro:

Se estima que el riesgo anual de que una persona determinada sea golpeada por un meteorito es de una posibilidad en 17 mil millones, lo que significa que la probabilidad es de aproximadamente 0.00000000006 (6 × 10 −11 ), equivalente a las probabilidades de crear unas pocas decenas de billones de UUID en un año y tener un duplicado. En otras palabras, solo después de generar mil millones de UUID por segundo durante los próximos 100 años, la probabilidad de crear un solo duplicado sería de aproximadamente el 50%.

Consideración:

Sin embargo, estas probabilidades solo se mantienen cuando los UUID se generan utilizando suficiente entropía. De lo contrario, la probabilidad de duplicados podría ser significativamente mayor, ya que la dispersión estadística podría ser menor. Cuando se requieren identificadores únicos para aplicaciones distribuidas, de modo que los UUID no entren en conflicto incluso cuando se fusionan los datos de muchos dispositivos, la aleatoriedad de las semillas y generadores utilizados en cada dispositivo debe ser confiable durante la vida útil de la aplicación. Cuando esto no sea factible, RFC4122 recomienda utilizar una variante de espacio de nombres.

Fuente: La sección de probabilidad aleatoria de duplicados de UUID del artículo de Wikipedia sobre identificadores únicos universalmente (el enlace lleva a una revisión de diciembre de 2016 antes de editar la sección reelaborada).

También vea la sección actual sobre el mismo tema en el mismo artículo de identificador único universal, Collisions .

Martijn Pieters
fuente
22
Me gusta esta parte de Wikipedia: sin embargo, estas probabilidades solo se mantienen cuando los UUID se generan utilizando suficiente entropía. De lo contrario, la probabilidad de duplicados podría ser significativamente mayor, ya que la dispersión estadística podría ser menor. Entonces, ¿cuál es la posibilidad real de duplicar anotando esta oración? No podemos crear números aleatorios reales en la computadora, ¿verdad?
Mans
66
En realidad, se ha trabajado mucho para encontrar formas de introducir tanta entropía ("aleatoriedad real", supongo que se llamaría) como sea posible en las API de números aleatorios. Ver en.wikipedia.org/wiki/Entropy_%28computing%29
broofa
44
Esa es en realidad una mayor probabilidad de colisión de lo que había imaginado. Paradoja de cumpleaños en, supongo.
Cameron
¿Puede confirmar que usar UUID sería seguro entre las ejecuciones de una aplicación? (por ejemplo, un script de Python)
George Sp
gran ejemplo ...: D
NuttLoose
151

Si por "tiempo suficiente" te refieres a 100 años y los estás creando a un ritmo de mil millones por segundo, entonces sí, tienes un 50% de posibilidades de tener una colisión después de 100 años.

rienda
fuente
185
Pero solo después de usar hasta 256 exabytes de almacenamiento para esas ID.
Bob Aman
16
Lo curioso es que podría generar 2 seguidos que fueran idénticos, por supuesto, en niveles alucinantes de coincidencia, suerte e intervención divina, pero a pesar de las posibilidades insondables, ¡todavía es posible! : D Sí, no va a suceder. ¡solo por la diversión de pensar en ese momento en que creaste un duplicado! Captura de pantalla de video!
scalabl3
44
¿La unicidad se debe únicamente a la aleatoriedad? ¿O hay otros factores? (por ejemplo, marca de tiempo, ip, etc.)
Weishi Zeng
15
@TheTahaan Eso no es lo que significa aleatorio. No significa "totalmente impredecible", generalmente siguen algún tipo de distribución. Si lanza 10 monedas, la posibilidad de obtener 2 caras, seguidas de 3 colas, seguidas de 5 caras, es bastante baja (2 ^ -10, aproximadamente 0.001). Es verdaderamente aleatoria, pero absolutamente puede conocer la posibilidad de conseguir un resultado particular. Simplemente no podemos decir de antemano si va a suceder.
Richard Rast
55
Solo para explicar qué hizo mal esta implementación, están utilizando un UUID de la versión 1, que se basa en una combinación de marca de tiempo y dirección mac para su singularidad. Sin embargo, si genera UUID lo suficientemente rápido, la marca de tiempo aún no se habrá incrementado. En este escenario, se supone que su algoritmo de generación de UUID debe rastrear la última marca de tiempo utilizada e incrementarla en 1. Claramente no pudieron dar ese paso. Sin embargo, todos los UUID de la versión 1 generados correctamente por la misma máquina en un corto período exhibirán similitudes obvias, pero aún deben ser únicos.
Bob Aman
103

Hay más de un tipo de UUID, por lo que "qué tan seguro" depende del tipo (que las especificaciones de UUID llaman "versión") que está utilizando.

  • La versión 1 es el UUID basado en el tiempo más la dirección MAC. Los 128 bits contienen 48 bits para la dirección MAC de la tarjeta de red (que es asignada exclusivamente por el fabricante) y un reloj de 60 bits con una resolución de 100 nanosegundos. Ese reloj se ajusta en 3603 AD para que estos UUID estén seguros al menos hasta entonces (a menos que necesite más de 10 millones de nuevos UUID por segundo o alguien clone su tarjeta de red). Digo "al menos" porque el reloj comienza el 15 de octubre de 1582, por lo que tiene unos 400 años después de que el reloj termina antes de que haya incluso una pequeña posibilidad de duplicaciones.

  • La versión 4 es el número aleatorio UUID. Hay seis bits fijos y el resto del UUID son 122 bits de aleatoriedad. Consulte Wikipedia u otro análisis que describa lo poco probable que es un duplicado.

  • La versión 3 usa MD5 y la versión 5 usa SHA-1 para crear esos 122 bits, en lugar de un generador de números aleatorio o pseudoaleatorio. Entonces, en términos de seguridad, es como si la Versión 4 fuera un problema estadístico (siempre y cuando se asegure de que el algoritmo de resumen está procesando siempre es único).

  • La versión 2 es similar a la versión 1, pero con un reloj más pequeño, por lo que terminará mucho antes. Pero dado que los UUID de la Versión 2 son para DCE, no debería usarlos.

Entonces, para todos los problemas prácticos, son seguros. Si no se siente cómodo al dejarlo a las probabilidades (p. Ej., Es el tipo de persona preocupada por la destrucción de la Tierra por un gran asteroide en su vida), solo asegúrese de usar un UUID de la Versión 1 y se garantiza que será único ( en su vida, a menos que planee vivir más allá de 3603 AD).

Entonces, ¿por qué no todos simplemente usan UUID de la Versión 1? Esto se debe a que los UUID de la Versión 1 revelan la dirección MAC de la máquina en la que se generó y pueden ser predecibles, dos cosas que pueden tener implicaciones de seguridad para la aplicación que usa esos UUID.

Hoylen
fuente
1
Por defecto, el UUID de la versión 1 tiene serios problemas cuando son generados por el mismo servidor para muchas personas. El UUID de la versión 4 es mi predeterminado, ya que puede escribir rápidamente algo para generar uno en cualquier idioma o plataforma (incluido javascript).
Justin Bozonier
1
@Hoylen Bien explicado! pero ¿se requiere tanta exageración?
Dinoop paloli
1
Teóricamente , es asignado exclusivamente por el fabricante.
OrangeDog
44
No es necesario generar 10 millones de UUID versión 1 en un segundo para encontrar un duplicado; uno simplemente debe generar un lote de 16,384 UUID dentro del lapso de un solo "tic" para desbordar el número de secuencia. He visto que esto sucede con una implementación que se basaba ingenuamente en una fuente de reloj que (1) tenía una granularidad de nivel μs, y (2) no se garantizaba que fuera monótono (los relojes del sistema no lo son). Tenga cuidado con el código de generación de UUID que usa y tenga especial cuidado con los generadores de UUID basados ​​en el tiempo. Son difíciles de acertar, por lo que debe someterlos a pruebas de carga antes de usarlos.
Mike Strobel
¿El lapso de tiempo entre los UUID v4 generados podría generar más probabilidades de colisión? Quiero decir, en una aplicación de tráfico pesado, supongamos que se generan miles de líquidos al mismo tiempo, ¿hay más posibilidades de colisión que si se generara la misma cantidad de líquidos durante un período de tiempo relativamente más largo?
Jonathan
18

La respuesta a esto puede depender en gran medida de la versión UUID.

Muchos generadores UUID usan un número aleatorio de la versión 4. Sin embargo, muchos de estos usan Pseudo un generador de números aleatorios para generarlos.

Si se usa un PRNG mal sembrado con un período pequeño para generar el UUID, diría que no es muy seguro en absoluto.

Por lo tanto, es tan seguro como los algoritmos utilizados para generarlo.

Por otro lado, si conoce la respuesta a estas preguntas, creo que un uuid de la versión 4 debería ser muy seguro de usar. De hecho, lo estoy usando para identificar bloques en un sistema de archivos de bloques de red y hasta ahora no he tenido un choque.

En mi caso, el PRNG que estoy usando es un tornado de mersenne y estoy teniendo cuidado con la forma en que se siembra, que proviene de múltiples fuentes, incluido / dev / urandom. El trabalenguas de Mersenne tiene un período de 2 ^ 19937 - 1. Pasará mucho, mucho tiempo antes de que vea un líquido repetido.

Mate
fuente
14

Citando de Wikipedia :

Por lo tanto, cualquiera puede crear un UUID y usarlo para identificar algo con la confianza razonable de que el identificador nunca será utilizado involuntariamente por otra cosa

Continúa explicando con bastante buen detalle qué tan seguro es en realidad. Entonces, para responder a su pregunta: Sí, es lo suficientemente seguro.

Dave Vogt
fuente
9

Estoy de acuerdo con las otras respuestas. Los UUID son lo suficientemente seguros para casi todos los fines prácticos 1 , y ciertamente para los suyos.

Pero supongamos (hipotéticamente) que no lo son.

¿Existe un sistema mejor o un patrón de algún tipo para aliviar este problema?

Aquí hay un par de enfoques:

  1. Use un UUID más grande. Por ejemplo, en lugar de 128 bits aleatorios, use 256 o 512 o ... Cada bit que agregue a un UUID de estilo tipo 4 reducirá la probabilidad de colisión a la mitad, suponiendo que tenga una fuente confiable de entropía 2 .

  2. Cree un servicio centralizado o distribuido que genere UUID y registre todos y cada uno de los que haya emitido. Cada vez que genera uno nuevo, verifica que el UUID nunca se haya emitido antes. Tal servicio sería técnicamente sencillo de implementar (creo) si asumiéramos que las personas que administran el servicio son absolutamente confiables, incorruptible, etc. Desafortunadamente, no lo son ... especialmente cuando existe la posibilidad de que las organizaciones de seguridad de los gobiernos interfieran. Por lo tanto, este método es probablemente poco práctico, y puede ser 3 imposible en el mundo real.


1 - Si la unicidad de los UUID determinara si los misiles nucleares se lanzaron en la capital de su país, muchos de sus conciudadanos no estarían convencidos por "la probabilidad es extremadamente baja". De ahí mi calificación de "casi todos".

2 - Y aquí hay una pregunta filosófica para ti. ¿Hay algo realmente al azar? ¿Cómo sabríamos si no fuera así? ¿Es el universo como lo conocemos una simulación? ¿Hay un Dios que posiblemente podría "modificar" las leyes de la física para alterar un resultado?

3 - Si alguien conoce algún trabajo de investigación sobre este problema, por favor comente.

Stephen C
fuente
Solo quiero señalar que el método número 2 básicamente derrota el propósito principal de usar UUID y también podría usar una identificación numerada clásica en ese punto.
Petr Vnenk
Estoy en desacuerdo. La falla en las identificaciones numeradas secuenciales es que son demasiado fáciles de adivinar. Debería poder implementar el método 2 de una manera que haga que los UUID sean difíciles de adivinar.
Stephen C
8

Los esquemas de UUID generalmente usan no solo un elemento pseudoaleatorio, sino también la hora actual del sistema y algún tipo de identificación de hardware a menudo única si está disponible, como una dirección MAC de red.

El punto principal del uso de UUID es que confía en que hará un mejor trabajo al proporcionar una identificación única de lo que usted mismo podría hacer. Esta es la misma razón detrás del uso de una biblioteca de criptografía de terceros en lugar de crear la suya propia. Hacerlo usted mismo puede ser más divertido, pero generalmente es menos responsable hacerlo.

Parappa
fuente
5

Lo he estado haciendo por años. Nunca te encuentres con un problema.

Por lo general, configuro mis bases de datos para tener una tabla que contenga todas las claves y las fechas modificadas y demás. Nunca me he encontrado con un problema de duplicar claves.

El único inconveniente que tiene es que cuando está escribiendo algunas consultas para encontrar información rápidamente, está copiando y pegando muchas teclas. Ya no tienes los identificadores cortos y fáciles de recordar.

Posthuma
fuente
5

Aquí hay un fragmento de prueba para que pueda probar su originalidad. inspirado en el comentario de @ scalabl3

Lo curioso es que podrías generar 2 seguidos que fueran idénticos, por supuesto, en niveles alucinantes de coincidencia, suerte e intervención divina, pero a pesar de las posibilidades insondables, ¡todavía es posible! : D Sí, no va a suceder. ¡solo por la diversión de pensar en ese momento en que creaste un duplicado! Captura de pantalla de video! - scalabl3 Oct 20 '15 a las 19:11

Si se siente afortunado, marque la casilla de verificación, solo verifica la identificación generada actualmente. Si desea una verificación del historial, no la marque. Tenga en cuenta que puede quedarse sin memoria RAM en algún momento si lo deja sin marcar. Traté de hacerlo compatible con la CPU para que pueda abortar rápidamente cuando sea necesario, simplemente presione el botón Ejecutar fragmento nuevamente o salga de la 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
fuente
Pruebe con un RFID 4122 Versión 1 (fecha-hora y dirección MAC) UUID.
zaph
Solía ​​ser increíblemente rápido, hasta una actualización de Chrome recientemente. Había notado lo mismo hace 4 semanas.
Tschallacka
3

No sé si esto es importante para usted, pero tenga en cuenta que los GUID son globalmente únicos, pero las subcadenas de GUID no lo son .

Grant Wagner
fuente
1
Tenga en cuenta que la referencia vinculada aquí habla sobre los UUID de la Versión 1 (que llevan información sobre la computadora generadora, etc., a la identificación). La mayoría de las otras respuestas hablan sobre la Versión 4 (que son totalmente aleatorias). El artículo de Wikipedia vinculado anteriormente en.wikipedia.org/wiki/Universally_unique_identifier explica los diferentes tipos de UUID.
kratenko
3

Para UUID4, hago que haya aproximadamente tantas identificaciones como granos de arena en una caja en forma de cubo con lados de 360,000 km de largo. Esa es una caja con lados ~ 2 1/2 veces más largos que el diámetro de Júpiter.

Trabajando para que alguien pueda decirme si he estropeado las unidades:

  • volumen de grano de arena 0.00947mm ^ 3 ( Guardian )
  • UUID4 tiene 122 bits aleatorios -> 5.3e36 valores posibles ( wikipedia )
  • volumen de tantos granos de arena = 5.0191e34 mm ^ 3 o 5.0191e + 25m ^ 3
  • longitud lateral de la caja cúbica con ese volumen = 3.69E8m o 369,000 km
  • diámetro de Júpiter: 139,820km (google)
perdió
fuente
En realidad, supongo que esto supone un 100% de empaque, ¡así que tal vez debería agregar un factor para eso!
perdido el