Existem algoritmos de hash 'reflexivo'?

Existe uma classe de algoritmos de hash, teóricos ou práticos, de modo que um algoritmo na classe possa ser considerado 'reflexivo' de acordo com uma definição dada abaixo:

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

O operador + pode ser concatenação ou qualquer outra operação especificada para combinar a saída (hash1) de volta na entrada ("texto de entrada 1") para que o algoritmo (algo1) produza exatamente o mesmo resultado. ou seja, colisão na entrada e entrada + saída. O operador + deve combinar a totalidade de ambas as entradas e o algo não pode descartar parte da entrada.

O algoritmo deve produzir alta entropia na saída. Pode, mas não precisa, ser criptograficamente difícil reverter a saída de volta para uma ou ambas as entradas possíveis.

Eu não sou um matemático, mas uma boa resposta pode incluir uma prova de por que essa classe de algoritmos não pode existir. Esta não é uma questão abstrata, no entanto. Estou genuinamente interessado em usar esse algoritmo no meu sistema, se houver.

Esta é uma duplicata de uma pergunta que foi publicada pela primeira vez em /programming/4823680/reflexive-hash

ds.algorithms hash-function Comunidade
fonte

Relacionado: Mistura associativa de hash

Tsuyoshi Ito

Você está interessado nessa propriedade segurando para todo o texto de entrada ou para um texto de entrada? Se você deseja que ele retenha todo o texto de entrada, a construção de colisões é trivial por design, portanto, não acho que possa ser considerada uma boa função de hash.

Peter Taylor

Alguém quer arquivos de hash que contenham seus próprios hashes! ;)

Raphael

@ Peter Taylor - Estou procurando uma função que funcione conforme descrito para texto de entrada arbitrário. Cada entrada diferente produz um hash que, em geral, possui alta entropia mútua para todas as outras entradas possíveis. Da mesma forma que uma boa função irreversível de hash funciona. No entanto, a função de hash que estou procurando não precisa ter a propriedade de irreversibilidade. Alta entropia é suficiente.

@Raphael - Sim, essa é uma maneira sucinta de colocá-lo.

Respostas:

Dou uma construção trivial que satisfaz a exigência. Forneci-o para responder meramente à existência da função 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 eu disse, essa é uma construção trivial. Pode ser aplicado a qualquer função hash, prática (como MD5, SHA-1, ...) ou teórica.

MS Dousti
fonte

H

$H$

| R | = k

$|R|=k$

@ Rafael: Obrigado por apontar o erro de digitação (corrigido). H tem a mesma entropia que G, a menos que na condição em que R = G (L). Por exigência, nessa condição, H (x) deve ser igual a R. Não podemos fazer nada aqui para aumentar a entropia; já que o requisito de "reflexividade" nos impede de alterar a saída.

MS Dousti

@Sadeq: É necessário que a função hash seja computada recursivamente? Eu o algoritmo se beneficiando com esse fato de alguma forma?

Yasser Sobhdel 30/01

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

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

H (M)

$H(M)$

Sadeq, obrigado. Acredito que isso possa responder à minha pergunta, como foi solicitado. Você apresentou a resposta em uma ressalva adequada. Do ponto de vista pragmático, gosto do fato de ser uma sobreposição para qualquer algoritmo conhecido como o SHA-1. Se eu entendi corretamente, seu algoritmo continuará a calcular hashes recursivamente até atingir a colisão necessária e depois parar. Nesse caso, talvez possamos chamar isso de solução ingênua. Minha preocupação é que parece haver uma suposição implícita de que o algoritmo incorporado (por exemplo, SHA-1) atingirá o hash de colisão necessário, dado o seguinte: