Hash irreversible sin colisión

4

Estamos buscando permitir que los usuarios inicien sesión con una tarjeta inteligente. El lector de tarjetas inteligentes puede leer la identificación de la tarjeta inteligente y enviarla a nosotros.

No podemos, sin embargo, almacenar la ID de la tarjeta inteligente. No en texto plano, no en una codificación reversible. Se permite un hashing irreversible .

Nuevamente, debemos asegurarnos de que cada ID contenga un resultado único para evitar colisiones.

¿Cómo podemos satisfacer las propiedades únicas y irreversibles ?

    
pregunta Konerak 26.11.2013 - 08:44
fuente

4 respuestas

16

Para que un hash esté libre de colisiones, cada entrada única tendría que asignarse a una salida única. Si cada salida es única, eso significa que se puede asignar de manera inversa a una entrada única. Eso no sería hash, eso sería solo una codificación. Sin colisiones y la no reversibilidad se excluyen mutuamente por definición.

El punto importante es cómo es probable una colisión, y la respuesta para los hashes modernos es muy poco probable . Si el espacio de la clave de salida es mayor que el espacio de la clave de entrada, es extremadamente improbable que alguna vez encuentre una colisión, e incluso si no lo es, es tan improbable que no valga la pena considerarlo en el mundo real.

Sin embargo, creo que esos identificadores de tarjetas inteligentes no son muy complejos, probablemente números decimales de la misma longitud (por ejemplo, 1234567890). Eso significa que no hay tantas entradas posibles y es probable que se puedan calcular los hashes de todos los identificadores posibles en un tiempo posible, creando una tabla de búsqueda para invertir los hashes. Si ese es el caso, querrás usar un hash lento como bcrypt, scrypt, PBKDF2, etc. para hacer que esto no sea factible.

Cuanto más lo pienso, menos tiene sentido el requisito. El secreto aquí debe estar entre la tarjeta y el lector, y el confianza debe estar entre el lector y el sistema al que está conectado. ¿Por qué es un problema de seguridad si se conoce la identificación de una tarjeta? ¿Qué puede hacer alguien con esta identificación si la obtiene? Si la respuesta es que la identificación es un secreto y alguien puede hacer lo que quiera si conoce el número de identificación, es una mala seguridad. La seguridad aquí debe provenir del hecho de que uno necesita tener posesión física de la tarjeta, lo que significa que todos los secretos se encuentran entre la tarjeta y el lector. Más allá de eso, solo hay un usuario autenticado con un ID, lo cual es una necesidad simple para hacer que el sistema funcione.

    
respondido por el deceze 26.11.2013 - 09:26
fuente
3

Use la función de hash de 512 bits como SHA-2-512 y cuando agregue una tarjeta "inteligente" a la base de datos, verifique si el hash ya existe. En un caso EXTREMADAMENTE DESEQUIADO que lo haga, no use la tarjeta. Incluso con billones de ID únicas, es poco probable que tenga una sola colisión.

    
respondido por el Matrix 26.11.2013 - 09:01
fuente
1

Como dijo @deceze, una función hash criptográfica tampoco puede ser una hash perfecto para su espacio clave.

Entonces, en lugar de exigir que todos los resultados sean únicos, debes concentrarte en lidiar con la colisión adecuadamente.

Hay muchas opciones para esto (consulte el artículo de wikipedia sobre tablas hash , está bastante bien escrito) pero todo depende de lo que no nos dijiste: qué quieres hacer con esa identificación.

Si desea usarlo para identificar a un usuario que usa esa ID y no tiene ningún otro elemento, entonces, en teoría, no hay manera de evitar que ocurra una colisión mientras aún se encuentra la propiedad de no reversibilidad del hash. Todo lo que puede hacer es reducir las posibilidades de colisión si los considera demasiado altos (pero, como se señaló en @Matrix, las posibilidades de colisión son realmente bajas y deben verificarse antes de asignar una tarjeta).

Si tiene alguna otra propiedad provista, por ejemplo, una contraseña hash, entonces podría usar el resultado del hash para identificar todas las filas potencialmente válidas y luego usar una búsqueda más costosa (por ejemplo, verificar la contraseña proporcionada en cada una de estas filas) para identificar la correcta.

Sin embargo, en la práctica, no me preocuparía demasiado la colisión a menos que emita un número realmente alto de tarjetas (millones).

    
respondido por el Stephane 26.11.2013 - 10:32
fuente
1

Considere este gráfico antes de preocuparse por las posibilidades de una colisión. Las direcciones de Bitcoin son el resultado de hash de una clave, que en su caso sería la identificación de la tarjeta inteligente. Como puede ver, el rango de direcciones es bastante grande y, por lo tanto, una colisión bastante improbable.

De hecho, se considera tan improbable que las direcciones se generen sin temor a que otra persona haya generado la misma dirección, aunque esto podría causar una pérdida financiera significativa para un usuario.

Por lo tanto, debe (teóricamente) elegir uno, único o irreversible. Sin embargo, tenga en cuenta que es extremadamente improbable que tenga que preocuparse de que el hecho de ser único sea un problema, así que simplemente elija un algoritmo hash sensible como el SHA-512 que tiene un grupo muy grande.

    
respondido por el deed02392 26.11.2013 - 15:55
fuente

Lea otras preguntas en las etiquetas