¿Existen algoritmos hash 'reflexivos'?

¿Existe una clase de algoritmos hash, ya sean teóricos o prácticos, de modo que un algoritmo en la clase pueda considerarse 'reflexivo' de acuerdo con una definición dada a continuación?

hash1 = algo1 ("texto de entrada 1")
hash1 = algo1 ("texto de entrada 1" + hash1)

El operador + podría ser una concatenación o cualquier otra operación especificada para combinar la salida (hash1) nuevamente en la entrada ("texto de entrada 1") para que el algoritmo (algo1) produzca exactamente el mismo resultado. es decir, colisión en entrada y entrada + salida. El operador + debe combinar la totalidad de ambas entradas y el algoritmo no puede descartar parte de la entrada.

El algoritmo debe producir una alta entropía en la salida. Puede, pero no necesariamente, ser criptográficamente difícil revertir la salida a una o ambas entradas posibles.

No soy matemático, pero una buena respuesta podría incluir una prueba de por qué no puede existir tal clase de algoritmos. Sin embargo, esta no es una pregunta abstracta. Estoy realmente interesado en utilizar un algoritmo de este tipo en mi sistema, si es que existe.

Este es un duplicado de una pregunta que se publicó por primera vez en /programming/4823680/reflexive-hash

ds.algorithms hash-function Comunidad
fuente

Relacionado: Mezcla de hash asociativa

Tsuyoshi Ito

¿Está interesado en esta propiedad para todo el texto de entrada o para un texto de entrada? Si desea que se mantenga para todo el texto de entrada, la construcción de colisiones es trivial por diseño, por lo que no creo que pueda considerarse una buena función hash.

Peter Taylor

¡Alguien quiere hacer hash de archivos que contienen sus propios hashes! ;)

Raphael

@ Peter Taylor: estoy buscando una función que funcione como se describe para el texto de entrada arbitrario. Cada entrada diferente produce un hash que en general tiene una alta entropía mutua a cualquier otra entrada posible. Como funciona una buena función hash irreversible. Sin embargo, la función hash que estoy buscando no necesita tener la propiedad de irreversibilidad. La entropía alta es suficiente.

@Raphael - Sí, esa es una manera sucinta de decirlo.

Respuestas:

Doy una construcción trivial que satisface el requisito. Lo proporciono simplemente para responder a la existencia de la función hash "reflexiva".

$G$ $G$ $k$ $k$ $+$ $|x|$ $x$

$H$ $x$

$|x| \le k$ $H(x) \overset{\text{def}}{=} G(x)$
$|x| > k$ $L$ $R$ $(|x|-k)$ $k$ $x$ $x = L + R$ $|R|=k$ $R = H(L)$ $H(L)$ $H(x) \overset{\text{def}}{=} R$ $H(x) \overset{\text{def}}{=} G(x)$

Como dije, esta es una construcción trivial. Se puede aplicar a cualquier función hash, práctica (como MD5, SHA-1, ...) o teórica.

MS Dousti
fuente

H

$H$

| R | = k

$|R|=k$

@Raphael: Gracias por señalar el error tipográfico (corregido). H tiene la misma entropía que G, a menos que esté en la condición donde R = G (L). Por requerimiento, en esta condición, H (x) debería ser igual a R. No podemos hacer nada aquí para aumentar la entropía; ya que el requisito de "reflexividad" nos impide alterar la salida.

MS Dousti

@Sadeq: ¿Se requiere que la función hash se calcule recursivamente? ¿El algoritmo se beneficia de este hecho de alguna manera?

Yasser Sobhdel

H (M + H (M) + H (M) + \dots + H (M))

$H(M+H(M)+H(M)+\ldots+H(M))$

H (M)

$H(M)$

Sadeq, gracias. Creo que esto puede responder a mi pregunta, tal como fue formulada. Has formulado la respuesta en una advertencia adecuada. Desde un punto de vista pragmático, me gusta el hecho de que es una superposición para cualquier algoritmo conocido como SHA-1. Si lo he entendido correctamente, su algoritmo continuará calculando hashes recursivamente hasta que llegue a la colisión requerida y luego se detendrá. En cuyo caso quizás podamos llamar a esto la solución ingenua. Mi preocupación se parece que hay una suposición implícita de que el algoritmo incorporado (SHA-1 por ejemplo) con el tiempo se golpeó el hash de colisión prescrito, dado un