Truncando la salida de hash para una ID única

5

Esto parece una pregunta común, pero mi conocimiento sobre el hash es muy limitado, por lo que estoy buscando una respuesta más de tipo ELI5. Agradecería si alguien pudiera ayudarme con mis preguntas

Un poco de contexto: estoy trabajando en un requisito para generar una ID de 12 caracteres (para recibos de pago de clientes) que utilice el conjunto de símbolos AZ 0-9 sin O, I, Z y U. Eso me da 32 símbolos, lo que significa 5 bits por símbolo y, por lo tanto, el ID sería de 60 bits. El requisito es que estas ID sean únicas, pero se almacenarán en una base de datos para que pueda buscar en la base de datos y regenerar otra si ya existe una. Sería genial si las ID fueran inherentemente únicas (por lo que no se seguiría con una nueva ID para buscar en la base de datos)

Mi pregunta es

Si elijo crear, obtenga un SHA-256 de un UUID o algún valor obtenido al concatenar la dirección IP privada del host, la marca de tiempo y la identificación del hilo que maneja una solicitud de generación de ID, luego obtenga su SHA- 256 hash, y usa sus 60 bits

  1. ¿Obtendría el máximo beneficio al usar los primeros 60 o los últimos 60 (o medio) para conservar la máxima singularidad? ¿Obtendría un mayor beneficio si utilizara los primeros 12 caracteres del número hexadecimal del valor SHA?
  2. Leí aquí que para los valores de n bits, el límite de cumpleaños es 2 ^ (n / 2). Entonces, ¿eso significa que si hago el procesamiento anterior, podría esperar colisiones después de 2 ^ (30) generaciones con un 50% de probabilidad?

Los requisitos no son flexibles (de lo contrario, obviamente iría con un UUID).

¡Gracias!

    
pregunta Shobit 11.02.2015 - 20:08
fuente

1 respuesta

4

No se conoce ninguna propiedad de los primeros / últimos / medios / whatev 60 bits de una salida SHA-256 que los haga más / menos "aleatorios" que los últimos / whatev / middle / primeros 60 bits. En otras palabras, podrías tomar los primeros 60 bits, y eso será lo mejor que puedas obtener.

Con una generación tan aleatoria, puede esperar que aparezcan las primeras colisiones después de que se hayan acumulado más de mil millones (2 30 ). Incluso si obtienes tu primera colisión en ese punto, las colisiones seguirán siendo un evento raro. Con las ID de 60 bits, cuando tenga, digamos, 2 35 de ellas (más de treinta mil millones), solo una de cada 2 25 de las nuevas ID colisionará uno existente (por lo que esto aún sucedería menos de una vez en 30 millones de casos). Si tiene una base de datos y puede tolerar la colisión ocasional pero bastante rara, entonces el camino a seguir es la generación aleatoria de la ID de 60 bits.

(O, dicho de otro modo, si tiene colisiones con frecuencia, esto significa que ya ha reunido una gran cantidad de ID y su base de datos central debe tener proporciones bíblicas).

Si desea más singularidad que eso, entonces necesita algún tipo de generador de ID central. Por ejemplo, hay un servidor central que puede ser interrogado y devuelve el siguiente valor de un contador. El servidor siempre aumenta el valor del contador después de ser interrogado, por lo que nunca devuelve dos veces el mismo valor. El servidor no se quedará sin enteros de 60 bits en mucho tiempo, porque, seamos sinceros, 2 60 sigue siendo enorme.

Ahora viene la parte difícil, que es de la que no hablaste: ¿deben ser impredecibles las ID? Ésta no es una pregunta fácil; Depende de lo que hagas con ellos y, básicamente, todo en tu sistema. Si necesita ID impredecibles, entonces un contador central no funcionará, porque todos pueden obtener un valor de ID y predecir el siguiente con el 100% de precisión. La solución habitual, en ese caso, sería tener un contador, pero cifrar los valores sucesivos con un cifrado de bloque cuyo tamaño de bloque es idéntico al del ID. Aquí necesitaría un cifrado de bloque con bloques de 60 bits; esto se puede construir a partir de un cifrado de bloque con bloques ligeramente más grandes, por ejemplo. 3DES (bloques de 64 bits). Sin embargo, esto tiene sentido solo en el contexto de un generador de ID central.

Si debe permitir la generación de ID desde varias máquinas "cliente" sin que hablen juntos o con algún sistema central, entonces tendrá que confiar en la aleatoriedad y tolerar las pocas colisiones ocasionales (que será bastante raro durante mucho tiempo) ). Si necesita imprevisibilidad, utilice un PRNG criptográficamente seguro . Dependiendo de su sistema operativo y marco de programación, esto puede llamarse /dev/urandom (sistemas Linux / Solaris / * BSD), CryptGenRandom() (Windows C / C ++), java.security.SecureRandom (Java), System.Security.Cryptography.RNGCryptoServiceProvider (.NET) ... ¿Es posible que el sistema de generación de UUID inherente de su entorno de programación local se base en un PRNG criptográficamente seguro (por lo que el hashing de un UUID con SHA-256 estaría bien, incluso por imprevisibilidad), pero ¿Por qué arriesgarse? Solo usa un PRNG fuerte directamente.

    
respondido por el Thomas Pornin 11.02.2015 - 20:30
fuente

Lea otras preguntas en las etiquetas