¿Cuándo chocan los hash?

Question

Entiendo que, de acuerdo con el principio de casillero, si el número de artículos es mayor que el número de contenedores, entonces al menos un contenedor tendrá más de un artículo. ¿Importa qué contenedor será? ¿Cómo se aplica esto a los hashes MD5, SHA1, SHA2?

Answer 1

No, no importa qué contenedor es, y de hecho esto no es tan importante para hashes criptográficos; mucho más importante es el birthday paradox, que dice que solo necesita valores hash sqrt(numberNeededByPigeonHolePrincipal), en promedio, antes de encontrar una colisión.

Por lo tanto, el hash debe ser lo suficientemente grande como para que la raíz cuadrada del espacio de búsqueda sea demasiado grande para la fuerza bruta. El espacio de raíz cuadrada de búsqueda para SHA1 es 2 y, a partir de marzo de 2012, no se han encontrado dos valores con el mismo SHA1-hash (aunque predigo que sucederá dentro del próximo año o dos ..); lo mismo con SHA2, una familia de hashes que tienen un espacio de búsqueda aún mayor. MD5 ha sido broken for a while sin embargo.

Answer 2

El objetivo de una función hash es distribuir aleatoriamente elementos en contenedores. Para cualquier buena función hash, no debe/no debe "importar" qué contenedor es el que debe ser indistinguible.

Esto no se aplica a las implementaciones de "hash perfecto" que intentan hacer mejor que la distribución aleatoria, a diferencia de los algoritmos que usted mencionó.

Como mencionó Michael, las colisiones ocurren MUCHO antes de que haya tantos elementos como ranuras. Debe manejar correctamente la colisión (o un hash perfecto) si desea manejar el birthday paradox.

Answer 3

Si tiene más elementos para hash que ranuras, entonces tendrá colisiones hash. Pero si tiene un algoritmo de hashing pobre, entonces verá colisiones incluso cuando la relación ítems/ranuras sea muy pequeña. Un buen algoritmo hash (que incluye la mayoría de los que verá en la naturaleza) intentará repartir los hash resultantes en todo el espacio de salida de la forma más pareja posible, y así minimizar las colisiones.

Tenga en cuenta que una colisión hash no es el fin del mundo. Cuando se usa en una tabla hash, por ejemplo, simplemente significa que se almacena más de un elemento en una ranura, y el código de la tabla tendrá que atravesar un poco más para encontrar o agregar el elemento objetivo, aumentando el tiempo de búsqueda ligeramente.

Verá que las personas se refieren a MD5 como un algoritmo de hash "roto", cuando en realidad, es simplemente uno deficiente para usar como un hash criptográfico. Será mejor que uno que construyas tú mismo.

Answer 4

Creo que la aplicación para la que está utilizando la función hash es una distinción importante. La colisión frecuente en contenedores hash, por ejemplo, puede degradar el rendimiento. La colisión frecuente en la criptografía tendrá consecuencias mucho más devastadoras (ver: cryptographic hash function on Wikipedia).

La colisión ocurre con relativa facilidad incluso con un algoritmo hash "decente". Por ejemplo, en Java,

String s = new String(new char[size]); 

siempre hashes a 0. Es decir, todas las cadenas que contienen sólo \0 de hash a 0 en Java.

---

En cuanto a "¿importa qué contenedor será?", De nuevo depende de la aplicación. Puede diseñar funciones hash que cortarían objetos "similares" a valores cercanos. Esto es útil cuando quiere buscar objetos similares, por ejemplo. Solo pellizque a todos y vea dónde caen. En este caso, las colisiones o las colisiones cercanas son deseables, ya que agrupan objetos que son similares.

En otras aplicaciones, desea que incluso el más mínimo cambio en el objeto resulte en un valor de hash completamente diferente. Este es el caso en la criptografía, por ejemplo, donde quiere estar tan seguro como sea posible de que algo no se ha modificado. Es mucho más difícil encontrar diferentes objetos que tengan el mismo valor en este caso.

Answer 5

Dependiendo de su aplicación, hashes criptográficos como MDA, SHA1/2, etc. pueden no ser la opción ideal, precisamente porque parecen completamente aleatorios, colocándolos de la manera prevista por la paradoja del cumpleaños. Tradicionalmente, una razón para usar algoritmos hash simples basados ​​en la operación restante es que se esperaba que las claves fueran números de serie o similares, de modo que una operación restante soportaría menos colisiones de las esperadas al azar. P.ej. si las claves son los enteros 1..1000, es posible que no tenga colisiones en un contenedor de tamaño 1009 si su función de almohadilla es la clave mod 1009. Algunas veces la gente afinaba manualmente los sistemas seleccionando cuidadosamente el tamaño del contenedor y la función hash para lograr una división pareja.

Por supuesto, si tiene que preocuparse de que las personas elijan maliciosamente claves que le causen dificultades, o un sistema ascendente que le envíe claves muy sesgadas (porque, por ejemplo, tiene su propia tabla hash y decide procesar todas las claves que X a la vez). es posible que desee utilizar un hash basado en una función de hash criptográfica con clave para defenderse de esto.