database design - Hash Collision: ¿cuáles son las posibilidades?
database-design (11)
Tengo un código en mi sitio con PHP que crea un hash aleatorio (usando sha1() ) y lo uso para unir registros en la base de datos.
¿Cuáles son las posibilidades de una colisión? Si genero el hash, primero verifique si está en la base de datos (prefiero evitar una consulta adicional) o insértelo automáticamente, según la probabilidad de que probablemente no colisione con otro.
De los primeros principios:
SHA-1 produce un resumen de 160 bits. Suponiendo que utiliza todo el espacio de bits de manera uniforme (que es, presumiblemente, lo que estaba diseñado para hacer), que es sólo una probabilidad de 2 ^ -160 en cada inserción que obtendría una colisión.
Por lo tanto, para cada inserción, debería ser seguro suponer que no hay colisión, y tratar el error si es que existe.
Eso no quiere decir que pueda ignorar por completo la posibilidad de una colisión.
La paradoja del cumpleaños sugiere que la posibilidad de que exista al menos una colisión en su base de datos es más alta de lo que se podría imaginar, debido a las posibles colisiones O (N ^ 2).
Haga la pregunta ¿cuánto le costará si se produce una colisión? Si este es un sitio gratuito bien. Si está ejecutando un negocio de hacer dinero y una anulación le costará un contrato de un millón de dólares, entonces lo pensaría de nuevo.
Creo que estás haciendo esto de la manera incorrecta.
Creo que debe conservar la ID única, pero quiere asegurarse de que los usuarios no puedan cambiarla manualmente.
Una forma de hacerlo es colocar el ID y el hash de la ID (con algunos datos adicionales) en el enlace.
Por ejemplo: (mi PHP está oxidado, por lo que el algoritmo general sería :)
id = 5;
hash = hash("My Private String " + id)
link = "http://mySite.com/resource?id=" + id + "&hash=" + hash
Luego, cuando reciba una solicitud, solo valide que puede regenerar el hash desde ID. Esto te deja abierto a un ataque para resolver "Mi cadena privada", pero eso será muy difícil desde el punto de vista computacional y siempre podrías añadir algo único que no esté directamente disponible para el usuario (como la ID de la sesión).
Hay una regla muy simple para averiguar si algún algoritmo hash tendría colisiones o no. Si el rango de salida de un algoritmo es un número finito, uno está destinado a tener una colisión, tarde o temprano.
Aunque SHA1 tiene un rango muy amplio de 2 ^ 160 posibilidades de hash, sigue siendo un número finito. Sin embargo, las entradas que se pueden pasar en esa función son literalmente infinitas. Dado un conjunto de datos de entrada lo suficientemente grande, las colisiones están destinadas a suceder.
Los otros comentarios te han cubierto sobre las probabilidades; sin embargo, si lo ves pragmáticamente, entonces puedes obtener una respuesta definitiva para ti.
Usted mismo dijo que va a hacer hash con sus ID secuenciales. Sería fácil codificar un caso de prueba. Itere a través de ~ 100,000,000 de identificadores y verifique si hay colisiones. Eso no tomaría mucho tiempo para hacer. Por otro lado, es posible que se quede sin memoria a la mitad del camino.
No creo que sha1 () te vaya a dar problemas aquí, la débil generación de números aleatorios es un candidato más probable para colisiones.
Stefan Esser escribió un buen article sobre el tema.
SHA-1 produce una digestión larga de 160 bit. Por lo tanto, está seguro siempre que tenga menos de 2 ^ (160/2) entradas. La división por 2 se debe a la paradoja del cumpleaños .
Si supone que SHA-1 hace un buen trabajo, puede concluir que existe una probabilidad 1 en 2 ^ 160 de que dos mensajes tengan el mismo hash (ya que SHA-1 produce un hash de 160 bits).
2 ^ 160 es un número ridículamente grande. Son aproximadamente 10 ^ 48. Incluso si tiene un millón de entradas en su base de datos, todavía hay una probabilidad de 1 en 10 ^ 42 de que una nueva entrada comparta el mismo hash.
SHA-1 ha demostrado ser bastante bueno, así que no creo que deba preocuparse por las colisiones en absoluto.
Como nota al margen, use la función raw_output de PHP cuando use SHA-1 ya que esto conducirá a una cadena más corta y por lo tanto hará que las operaciones de su base de datos sean un poco más rápidas.
EDITAR: Para abordar la paradoja del cumpleaños, una base de datos con 10 ^ 18 (un millón de millones de entradas) tiene una probabilidad de alrededor de 1 en 0.0000000000003 de una colisión. Realmente no vale la pena preocuparse por eso.
Si tiene que ofuscar algunos datos en su url para ocultar los datos, está haciendo algo mal.
Si usa identificaciones que aumentan numéricamente como entrada, entonces las posibilidades son prácticamente nulas de que SHA-1 colisione.
Si la identificación es la única entrada, entonces SHA-1 parece ser un poco exagerado, produciendo un hash de 160 bits a partir de un entero de 32 bits. Prefiero usar la exponenciación modular, por ejemplo, elegir un primo p grande (32 bits), calcular el generador modular g de ese grupo y luego usar g ^ id. Esto se garantizará sin colisiones, y solo dará "hashes" de 32 bits.
Utilice un esquema de cifrado simétrico y una clave de servidor privada para encriptar la ID (y otros valores) cuando los envíe al cliente y descifre nuevamente en la recepción. Tenga cuidado de que su función criptográfica proporcione comprobaciones de confidencialidad e integridad.
Esto le permite usar valores razonables cuando habla con el DB sin ningún tipo de colisión , una gran seguridad cuando habla con el cliente y reduce su probabilidad de aterrizar en el primer thedailyWTF en aproximadamente 2 ^ 160.
Ver también Pounding A Nail: Old Shoe o Glass Bottle? !
por qué no hacer algo que garantice que no habrá colisiones, y se asegura de que nadie pueda cambiar un parámetro GET para ver algo que no debería: usando un salt, combine el id y su hash.
$salt = "salty";
$key = sha1($salt . $id) . "-" . $id;
// 0c9ab85f8f9670a5ef2ac76beae296f47427a60a-5
incluso si tropiezas accidentalmente con dos números que tienen exactamente el mismo hash sha1 (con tu sal), entonces la tecla $ seguirá siendo diferente y evitarás todas las colisiones.