algorithm - generar - sha-3

Probabilidad de colisiones de códigos Hash de 64 bits

Question

El libro Numerical Recipes ofrece un método para calcular los códigos hash de 64 bits para reducir el número de colisiones.

El algoritmo se muestra en http://www.javamex.com/tutorials/collections/strong_hash_code_implementation_2.shtml y se copia aquí para referencia:

private static final createLookupTable() {
  byteTable = new long[256];
  long h = 0x544B2FBACAAF1684L;
  for (int i = 0; i < 256; i++) {
    for (int j = 0; j < 31; j++) {
      h = (h >>> 7) ^ h;
      h = (h << 11) ^ h;
      h = (h >>> 10) ^ h;
    }
    byteTable[i] = h;
  }
  return byteTable;
}

public static long hash(CharSequence cs) {
  long h = HSTART;
  final long hmult = HMULT;
  final long[] ht = byteTable;
  final int len = cs.length();
  for (int i = 0; i < len; i++) {
    char ch = cs.charAt(i);
    h = (h * hmult) ^ ht[ch & 0xff];
    h = (h * hmult) ^ ht[(ch >>> 8) & 0xff];
  }
  return h;
}

Mis preguntas:

1) ¿Existe una fórmula para estimar la probabilidad de colisión teniendo en cuenta la denominada paradoja del cumpleaños?

2) ¿Puedes estimar la probabilidad de una colisión (es decir, dos teclas que tienen el mismo valor)? Digamos que con 1,000 teclas y con 10,000 teclas?

EDIT : pregunta reformulada / corregida 3

3) ¿Es seguro suponer que una colisión de un número razonable de claves (por ejemplo, menos de 10.000 claves) es tan improbable que si 2 códigos hash son iguales, podemos decir que las claves son las mismas sin ninguna verificación posterior? p.ej

static boolean equals(key1, key2) {

  if (key1.hash64() == key2.hash64())
    return true;  // probability of collision so low we don''t need further check

  return false;
}

Esto no es por seguridad, pero la velocidad de ejecución es imperativa, por lo que evitar más controles de las teclas ahorrará tiempo. Si la probabilidad es muy baja, digamos menor que (1 en 1 billón por 100,000 claves) probablemente será aceptable.

TIA!

Answer 1

¿Existe una fórmula para estimar la probabilidad de colisión teniendo en cuenta la llamada paradoja del cumpleaños?

Ver: Ataque de cumpleaños .

Suponiendo que la distribución de hash es uniforme, la probabilidad de una colisión para n teclas es aproximadamente n 2/2 ⁶⁵ .

¿Es seguro suponer que una colisión de un número razonable de claves (por ejemplo, menos de 10.000 claves) es tan improbable, de modo que si 2 códigos hash son diferentes, podemos decir que las claves son diferentes sin ninguna verificación adicional?

Solo es seguro cuando usa una función hash criptográfica. Incluso si puede tolerar un error cada 3 * 10 ¹¹ veces, puede que tenga que considerar la posibilidad de que la entrada esté específicamente diseñada para crear una colisión hash, como un ataque a su programa.

Answer 2

1) ¿Existe una fórmula para estimar la probabilidad de colisión teniendo en cuenta la denominada paradoja del cumpleaños?

La probabilidad de que ocurra una sola colisión depende del conjunto de claves generadas, ya que la función hash es uniforme, podemos hacer lo siguiente para calcular la probabilidad de que la colisión no ocurra en la generación de k teclas de la siguiente manera:

x = hash size
p(k=2) = (x-1)/x
p(k=3) = p(k=2)*(x-2)/x
..
p(k=n) = (x-1)*(x-2)..(x-n+1)/x^n

p(k=n) ~ e^-(n*n)/2x

p(collision|k=n) = 1-p(k=n) = 1 - e^(-n^2)/2x
p(collision) > 0.5 if n ~ sqrt(x)

Por lo tanto, si se generan claves sqrt(2^64) que son 2^32 teclas, hay una mayor probabilidad de que haya una sola colisión.

2) ¿Puedes estimar la probabilidad de una colisión (es decir, dos teclas que tienen el mismo valor)? Digamos que con 1,000 teclas y con 10,000 teclas?

x = 2^64 
Use the formula pc(k=n) = 1 - e^-(n^2)/2x

3) ¿Es seguro suponer que una colisión de un número razonable de claves (por ejemplo, menos de 10.000 claves) es tan improbable que si 2 códigos hash son iguales, podemos decir que las claves son las mismas sin ninguna verificación posterior?

Esta es una pregunta muy interesante porque depende del tamaño del espacio clave. Supongamos que las claves se generan al azar desde el espacio de size = s y el espacio hash es x=2^64 como mencionó. La probabilidad de colisión es Pc(k=n|x) = 1-e^(-n^2)/2x . Si la probabilidad de elegir la misma clave en el espacio clave es P(k=n|s) = 1-e^(-n^2)/2s . Para asegurarse de que si el hash es el mismo, las claves son las mismas:

P(k=n|s) > Pc(k=n|x)
1-e^-(n^2/2s) > 1-e^-(n^2/2x) 
n^2/2s > n^2/2x 
s < x
s < 2^64

Por lo tanto, muestra que para que las claves sean iguales si el hash es el mismo que el tamaño del conjunto de teclas debe ser menor que 2^64 aproximadamente; de ​​lo contrario, existe la posibilidad de colisión en hash más que en el conjunto de teclas. El resultado es independiente del número de claves generadas.

Answer 3

Proporcionaré una aproximación aproximada a las fórmulas exactas proporcionadas en las otras respuestas; la aproximación puede ayudarte a responder # 3. La aproximación aproximada es que la probabilidad de que ocurra una colisión con las teclas ky n valores posibles de hash con un buen algoritmo hash es aproximadamente (k ^ 2) / 2n, para k << n. Para 100.000 teclas con un hash de 64 bits, eso es 10 ^ 10 / 32x10 ^ 18 o aproximadamente 1 en 3 mil millones.

Sin embargo, sospecho que si no revisa los valores reales de la colisión, hay una gran probabilidad de que el algoritmo hash no sea lo suficientemente "bueno", después de todo.

Answer 4

¿Existe una fórmula para estimar la probabilidad de colisión teniendo en cuenta la llamada paradoja del cumpleaños?

El uso de la fórmula Birthday Paradox simplemente le indica en qué punto debe comenzar a preocuparse por la posibilidad de una colisión. Esto es alrededor de Sqrt[n] donde n es la cantidad total de posibles valores hash. En este caso n = 2^64 entonces la fórmula de la Paradoja de cumpleaños te dice que mientras el número de claves sea significativamente menor que Sqrt[n] = Sqrt[2^64] = 2^32 o aproximadamente 4 mil millones, no lo harás Necesito preocuparme por las colisiones. Cuanto mayor es la n , más precisa es esta estimación. De hecho, la probabilidad p(k) que se produzca una colisión con las teclas k acerca a una función escalonada a medida que n hace más grande, donde el paso ocurre en k=Sqrt[n] .

¿Puedes estimar la probabilidad de una colisión (es decir, dos teclas que tienen hash con el mismo valor)? Digamos que con 1,000 teclas y con 10,000 teclas?

Suponiendo que la función hash está distribuida uniformemente, es sencillo derivar la fórmula.

p(no collision for k keys) = 1 * (n-1)/n * (n-2)/n * (n-3)/n * ... * (n-(k-1))/n

Esa fórmula se sigue directamente de comenzar con la tecla 1: la probabilidad de que no haya una colisión con 1 tecla es, por supuesto, 1. La probabilidad de que no haya colisión con 2 teclas es 1 * (n-1)/n . Y así sucesivamente para todas las teclas k . Convenientemente, Mathematica tiene una función Pochhammer [] para este propósito para expresar esto de manera sucinta:

p(no collision for k keys) = Pochhammer[n-(k-1),k]/n^k

Luego, para calcular la probabilidad de que haya al menos 1 colisión para las claves k , reste de 1:

p(k) = 1 - p(no collision for k keys) = 1 - Pochhammer[n-(k-1),k]/n^k

Usando Mathematica, uno puede calcular para n=2^64 :

• p (1,000) = 1 de 3.7 * 10 ¹³
• p (10,000) = 1 de 3.7 * 10 ¹¹
• p (1,000,000) = 1 de 3.7 * 10 ⁷

¿Es seguro suponer que una colisión de un número razonable de claves (por ejemplo, menos de 10.000 claves) es tan improbable que si 2 códigos hash son iguales, podemos decir que las claves son las mismas sin ninguna verificación posterior?

Responder esto depende precisamente de la probabilidad de que 2 de las 10,000 claves sean idénticas. Lo que estamos buscando es:

p(a=b|h(a)=h(b)) = The probability that a=b given h(a)=h(b)

donde b son claves (posiblemente idénticas) y h() es la función hash. Podemos aplicar el teorema de Bayes directamente:

p(a=b|h(a)=h(b)) = p(h(a)=h(b)|a=b) * p(a=b) / p(h(a)=h(b))

Inmediatamente vemos que p(h(a)=h(b)|a=b) = 1 (si a=b entonces por supuesto h(a)=h(b) ) entonces obtenemos

p(a=b|h(a)=h(b)) = p(a=b) / p(h(a)=h(b))

Como puede ver, esto depende de p(a=b) que es la probabilidad de que a y b sean realmente la misma clave. Esto depende de cómo se seleccionó el grupo de 10,000 teclas en primer lugar. Los cálculos para las dos preguntas anteriores suponen que todas las claves son distintas, por lo que se necesita más información sobre este escenario para responderla por completo.