.net - net - ¿Cómo Random es System.Guid.NewGuid()?(Toma dos)

system guid newguid c#

Question

Antes de comenzar a marcar esto como un duplicado , léame. La otra pregunta tiene una (probablemente) respuesta incorrecta aceptada.

No sé cómo .NET genera sus GUID, probablemente solo lo haga Microsoft, pero hay muchas posibilidades de que simplemente llame a CoCreateGuid() . Sin embargo, se ha documentado que esa función llama a UuidCreate() . Y los algoritmos para crear un UUID están bastante bien documentados .

Para abreviar, sea como fuere, parece que System.Guid.NewGuid() usa el algoritmo de generación de UUID de la versión 4 , porque todos los GUID que genera coinciden con los criterios (compruébalo, probé un par de millones de GUID, todos ellos emparejado).

En otras palabras, estos GUID son casi aleatorios, excepto por algunos bits conocidos.

Esto nuevamente plantea la pregunta: ¿qué tan aleatorio ES este azar? Como todo buen programador sabe, un algoritmo de número pseudoaleatorio es tan aleatorio como su semilla (también conocida como entropía). Entonces, ¿cuál es la semilla de UuidCreate() ? ¿Con qué frecuencia se vuelve a sembrar el PRNG? ¿Es criptográficamente fuerte, o puedo esperar que los mismos GUID comiencen a fluir si dos computadoras accidentalmente llaman a System.Guid.NewGuid() al mismo tiempo? ¿Y se puede adivinar el estado del PRNG si se recopilan suficientes GUID generados secuencialmente?

Agregado: para aclarar, me gustaría saber qué tan aleatorio puedo confiar que sea y, por lo tanto, dónde puedo usarlo. Entonces, establezcamos una escala aproximada de "aleatoriedad" aquí:

1. Aleatoriedad básica, tomando la hora actual como la semilla. Se puede usar para barajar cartas en el Solitario pero poco más, ya que las colisiones son muy fáciles de conseguir incluso sin intentarlo.
2. Aleatoriedad más avanzada, utilizando no solo el tiempo sino otros factores específicos de la máquina para la semilla. Tal vez también se siembra solo una vez en el arranque del sistema. Esto se puede usar para generar ID en un DB porque los duplicados son poco probables. Aún así, no es bueno para la seguridad porque los resultados se pueden predecir con suficiente esfuerzo.
3. Cryptograhpically al azar, usando el ruido del dispositivo u otras fuentes avanzadas de aleatoriedad para la semilla. Reclutado en cada invocación o al menos bastante a menudo. Puede ser utilizado para ID de sesión, entregado a partes no confiables, etc.

Llegué a esta pregunta mientras pensaba si estaría bien usarlos como ID de DB, y si la implementación del algoritmo Guid.comb junto con System.Guid.NewGuid() (como NHibernate lo hace) sería errónea o no.

Answer 1

Algunas personas ya lo insinuaron, pero quiero repetirlo ya que parece haber una idea falsa:

La aleatoriedad y la singularidad son conceptos ortogonales.

Los datos aleatorios pueden ser únicos o redundantes, y de la misma manera, los datos únicos pueden usar una fuente aleatoria o una fuente determinista (piense en un contador global que se bloquea e incrementa para cada GUID que se haya creado).

Los GUID fueron diseñados para ser únicos, no aleatorios. Si el generador de .NET parece usar una entrada aleatoria, bien. Pero no confíe en él como fuente de aleatoriedad, ni para criptografía ni para otros fines (en particular, ¿qué función de distribución espera obtener?). Por otro lado, puede estar razonablemente seguro de que los GUID creados por .NET, incluso en grandes volúmenes, serán únicos.

Answer 2

Centrándose en su pregunta sobre el uso de GUID como identificadores de fila :

Los GUID son para bases de datos orientadas a la replicación, o que generan filas antes de agregarlas al DB. Si no necesita GUID para resolver un problema en particular, intente seguir con la numeración incremental. Los GUID complican la depuración y las pruebas un poco.

El método COMB en el artículo que mencionas parece bastante bueno, en realidad. Nunca me di cuenta, ¡gracias por eso! ( ps la versión fácil de imprimir de ese artículo lee mucho mejor )

Por lo tanto, si no necesita generar un GUID antes de tiempo, puede dejar que la base de datos maneje la generación de GUID por usted. Las diferencias de velocidad que solo notará si comienza a agregar 10.000 de registros de una sola vez, lo cual no debe hacer de todos modos, para eso está la importación masiva.

También eche un vistazo a Jeff en ID vs GUID''s

create table #temp ([id] uniqueidentifier primary key default(newid()), [name] varchar(20))
insert into #temp (name) values (''apple'')
insert into #temp (name) values (''orange'')
insert into #temp (name) values (''banana'')
select * from #temp
drop table #temp

id                                   name
------------------------------------ --------------------
911B0CBD-4EED-4EB0-8488-1B2CDD915C02 banana
56CF3A80-A2DE-4949-9C9B-5F890824EA9C orange
5990B9FD-143D-41B0-89D1-957B2C57AB94 apple

Answer 3

De acuerdo con https://msdn.microsoft.com/en-us/library/bb417a2c-7a58-404f-84dd-6b494ecf0d13#id11 , desde Windows 2000 en 1999,

"los bits aleatorios para todos los GUID de la versión 4 creados en Windows se obtienen a través de la API criptográfica CryptGenRandom de Windows o su equivalente, la misma fuente que se utiliza para la generación de claves criptográficas"

Así que los consideraría criptográficamente seguros, al menos en la medida de los 122 bits de entropía que proporcionan.

También vea https://.com/a/35384818/284704 , donde se verifica a través de un paso de depuración que el CLR está llamando al generador aleatorio de SO seguro.

Answer 4

La definición de Random de ninguna manera se relaciona con la definición de Globally Unique.

Voltear una moneda dos veces y obtener HH, HT, TH, TT son todos aleatorios. HH es tan aleatorio como HT.

Lanzar una moneda "especial" dos veces y garantizar que solo obtendrás HT o TH es singularidad.

Answer 5

La respuesta aceptada a una pregunta relacionada dice:

Un GUID no garantiza la aleatoriedad, sino que garantiza la exclusividad. Si quieres aleatoriedad, utiliza Aleatorio para generar una cadena.

Cualquier otra cosa es un detalle de implementación (y podría cambiar).

Actualización: Para aclarar mi punto: incluso si la implementación actual de .NET 3.5 produce un guid verdaderamente aleatorio (que no es el caso) no hay garantía de que este sea el caso en el futuro o verdadero para otras implementaciones del BCL ( por ejemplo, Mono, Silverlight, CF, etc.)

Actualización 2: El formato de UUID está especificado por RFC4122 . La Sección 6 hace una declaración explícita sobre seguridad:

No suponga que los UUID son difíciles de adivinar; no deben usarse como capacidades de seguridad (identificadores cuya mera posesión concede acceso), por ejemplo. Una fuente de números aleatorios predecibles exacerbará la situación.

Answer 6

Leí en alguna parte que las posibilidades de ganar la lotería serían equivalentes a 2 colisiones de "GUID" de 4 bytes. Los GUID estándar de 16 bytes ofrecerían muchas menos posibilidades de colisión.

Answer 7

Los GUID están diseñados para estar en el número 2 en su escala, es decir, "se pueden usar para generar ID en un DB porque los duplicados son poco probables *".

En cuanto a la seguridad, el problema no es "no es bueno para la seguridad porque los resultados se pueden predecir con suficiente esfuerzo". El problema es que nadie le da una garantía de seguridad documentada.

En la práctica, de acuerdo con este comentario y este , la generación de GUID se implementa en términos de un RNG criptográficamente seguro ( CryptGenRandom ). Pero eso parece ser un detalle de implementación no documentado. (Y no he verificado esto - son comentarios aleatorios en Internet, tomados con un camión cargado de sal).

(* Donde "poco probable" significa algo así como "las posibilidades de que alguien encuentre un GUID duplicado antes del final del universo son menores que las posibilidades de que usted gane la lotería personalmente". Por supuesto, se excluyeron los errores de implementación).

Answer 8

No se puede confiar en que las API que producen bytes aleatorios pero que no están explícitamente documentadas para producir bytes aleatorios criptográficamente fuertes producen bytes aleatorios criptográficamente fuertes.

Si necesita bytes aleatorios criptográficamente fuertes, entonces debe utilizar una API que esté explícitamente documentada para producirlos.

public Guid CreateCryptographicallyStrongGuid() {
    var rng = new System.Security.Cryptography.RNGCryptoServiceProvider();
    var data = new byte[16];
    rng.GetBytes(data);
    return new Guid(data);
}

Estos GUID son simplemente 128 bits de aleatoriedad criptográfica. No están estructurados, y no colisionarán.

Vea este artículo para algunas de las matemáticas. Usando "La fórmula general del cumpleaños", reorganizar da

n = sqrt (-2T * ln (p))

donde n es el número de elementos elegidos, T es el número total de elementos (2 ^ 128) y p es la probabilidad objetivo de que los n elementos elegidos sean diferentes. Con p = .99 , esto da * n = 2.61532104 * 10 ^ 18 *. Esto significa que podemos generar un billón de GUIDs verdaderamente aleatorias por segundo dentro de un sistema por mil millones de segundos (32 años), y tenemos más del 99% de posibilidades al final de que cada uno sea único dentro del sistema.

Answer 9

Son aleatorios, por lo que es demostrable desde el punto de vista matemático que las colisiones no deberían producirse durante mucho tiempo, por lo que puede suponer que son únicas a nivel mundial. Sin embargo, no son criptográficamente fuertes, ya que esto requeriría una verdadera aleatoriedad, lo que no es realmente posible en computadoras sin hardware dedicado.