Hash de una cadena de longitud específica

Question

¿Hay alguna forma de generar un hash de una cadena para que el hash en sí tenga una longitud específica? Tengo una función que genera hashes de 41 bytes (SHA-1), pero necesito que sea de 33 bytes como máximo (debido a ciertas limitaciones de hardware). Si trunco ​​el hash de 41 bytes a 33, probablemente (¡ciertamente!) Perdí la singularidad.

O en realidad, supongo que un algoritmo MD5 podría encajar muy bien, si pudiera encontrar algún código C para uno con su ayuda.

EDIT: Gracias a todos por las respuestas rápidas y bien informadas. He elegido ir con un hash MD5 y me queda bien para mi propósito. La singularidad es un tema importante, pero no espero que la cantidad de hashes sea muy grande en un momento dado; estos hashes representan servidores de software en una LAN doméstica, por lo que al máximo habría 5, tal vez 10 en ejecución.

Answer 1

Se calcula el camino hash que desafortunadamente no es posible. Para limitar la longitud de hash a 33 bytes, tendrá que cortarla. Podría xor los primeros y últimos 33 bytes, ya que eso podría mantener más información. Pero incluso con 33 bytes, no tienes una gran posibilidad de colisión.

md5: http://www.md5hashing.com/c++/

por cierto. md5 tiene 16 bytes, sha1 20 bytes y sha256 tiene 32 bytes, sin embargo, como cadenas hexadecimales, todos duplican su tamaño. Si puedes almacenar bytes, incluso puedes usar sha256.

Answer 2

Creo que el algoritmo de hash MD5 da como resultado un número de 32 dígitos, por lo que quizás ese sea el más adecuado.

Editar: para acceder a la funcionalidad de MD5, debería ser posible enganchar en las bibliotecas de openssl. Sin embargo, usted mencionó las limitaciones de hardware, por lo que es posible que esto no sea posible en su caso.

Answer 3

Puede usar un Elf hash (< - código C incluido) o alguna otra función hash simple como esa en lugar de MD5 o SHA-X. Ellos no son seguras, pero pueden ser sintonizados a cualquier longitud que necesita

Answer 4

La posibilidad de una colisión de 33 bytes es 1/2^132 (por la paradoja del cumpleaños)

Así que no se preocupe por perdiendo la unicidad

Actualización: No verifiqué la longitud del byte real de SHA1. Aquí está el cálculo relevante: una colisión de 32 nibble (33 bytes de hex: 1 char de terminación) ocurre solo cuando el número de cadenas se convierte en hash sqrt (2^(32 * 4)) = 2^64.

Answer 5

Here es una implementación MD5 en C.

Answer 6

hashes son, por definición, solamente es único para la pequeña cantidad de datos (e incluso entonces todavía no está garantizada). Es imposible asignar una gran cantidad de información de forma exclusiva a una pequeña cantidad de información en virtud del hecho de que no se puede eliminar mágicamente la información y recuperarla más tarde. Tenga en cuenta que esto no está pasando compresión.

Personalmente, usaría MD5 (si necesita almacenar en texto), o un hash 256b (32B) como SHA256 (si puede almacenar en binario) en esta situación. Truncar otro algoritmo hash a 33B también funciona, y PUEDE aumentar la posibilidad de generar colisiones hash. Depende mucho del algoritmo.

Also, yet another C implementation of MD5, by the people who designed it.

Answer 7

No hay más probabilidades de colisión con subcadena (sha_hash, 0, 33) que con cualquier otro hash que es de 33 bytes de longitud, debido a la forma algoritmos hash están diseñados (entropía está uniformemente disperso en la cadena resultante).

Answer 8

Si trunco ​​el hash de 41 bytes a 33, es probable que (¡ciertamente!) Haya perdido la singularidad.

¿Qué te hace pensar que tienes unicidad ahora? Sí, claramente hay una mayor probabilidad de colisión cuando solo juegas con 33 bytes en lugar de 41, pero debes ser plenamente consciente de que las colisiones son poco probables, no imposibles, para cualquier situación en la que tenga sentido usar un hash. en primer lugar. Si está almacenando más de 41 bytes de datos, hay claramente más combinaciones posibles que hashes disponibles.

Ahora, ya sea que sea mejor truncar el hash SHA-1 o utilizar un hash más corto como MD5, no lo sé. Creo que sería más seguro en general al mantener el hash completo, pero MD5 tiene known vulnerabilities, lo que puede o no ser un problema para su aplicación en particular.

Answer 9

DigestUtils de Uso Apache:

http://commons.apache.org/codec/api-release/org/apache/commons/codec/digest/DigestUtils.html#md5Hex(java.lang.String)

Convierte el hash en cadena hexadecimal de 32 caracteres.