Existe-t-il des algorithmes de hachage «réflexifs»?

Existe-t-il une classe d'algorithmes de hachage, qu'ils soient théoriques ou pratiques, de sorte qu'un algorithme de la classe puisse être considéré comme «réflexif» selon une définition donnée ci-dessous:

hash1 = algo1 ("texte d'entrée 1")
hash1 = algo1 ("texte d'entrée 1" + hash1)

L'opérateur + peut être une concaténation ou toute autre opération spécifiée pour combiner la sortie (hachage1) dans l'entrée ("texte d'entrée 1") afin que l'algorithme (algo1) produise exactement le même résultat. c'est-à-dire collision sur entrée et entrée + sortie. L'opérateur + doit combiner l'intégralité des deux entrées et l'algo ne peut pas rejeter une partie de l'entrée.

L'algorithme doit produire une entropie élevée dans la sortie. Il peut, mais pas nécessairement, être cryptographiquement difficile de retourner la sortie à une ou aux deux entrées possibles.

Je ne suis pas mathématicien, mais une bonne réponse pourrait inclure une preuve de la raison pour laquelle une telle classe d'algorithmes ne peut pas exister. Ce n'est cependant pas une question abstraite. Je suis vraiment intéressé à utiliser un tel algorithme dans mon système, s'il en existe un.

Il s'agit d'un doublon d'une question qui a été publiée pour la première fois sur /programming/4823680/reflexive-hash

ds.algorithms hash-function Communauté
la source

En relation: Mélange associatif de hachage

Tsuyoshi Ito

Êtes-vous intéressé par cette propriété tenant pour tout le texte d'entrée ou pour un texte d'entrée? Si vous voulez qu'il tienne pour tout le texte d'entrée, la construction de collisions est triviale par conception, donc je ne pense pas que cela puisse être considéré comme une bonne fonction de hachage.

Peter Taylor

Quelqu'un veut hacher des fichiers contenant leurs propres hachages! ;)

Raphael

@Peter Taylor - Je recherche une fonction qui fonctionne comme décrit pour le texte d'entrée arbitraire. Chaque entrée différente produit un hachage qui, en général, a une entropie mutuelle élevée pour toutes les autres entrées possibles. Tout comme une bonne fonction de hachage irréversible fonctionne. Cependant, la fonction de hachage que je recherche n'a pas besoin d'avoir la propriété d'irréversibilité. Une entropie élevée est suffisante.

@Raphael - Oui, c'est une façon succincte de le dire.

Réponses:

Je donne une construction triviale qui satisfait à l'exigence. Je le fournis pour répondre simplement à l' existence d'une fonction de hachage "réflexive".

Soit toute fonction de hachage produisant une entropie élevée dans la sortie. Supposons que hache des chaînes binaires de longueur arbitraire en chaînes binaires de bits, où est un entier positif. Soit désigne l' opérateur de concaténation , et soit désigne la longueur de la chaîne binaire . $G$ $G$ $k$ $k$ $+$ $|x|$ $x$

Définissez la fonction de hachage sur l'entrée comme suit: $H$ $x$

Si , alors . $|x| \le k$ $H(x) \overset{\text{def}}{=} G(x)$
Si , soit et le préfixe bits et le suffixe . Autrement dit, et . Si (où est calculé récursivement ), alors $|x| > k$ $L$ $R$ $(|x|-k)$ $k$ $x$ $x = L + R$ $|R|=k$ $R = H(L)$ $H(L)$ .; sinon, $H(x) \overset{\text{def}}{=} R$ $H(x) \overset{\text{def}}{=} G(x)$

Comme je l'ai dit, c'est une construction banale. Il peut être appliqué à n'importe quelle fonction de hachage, pratique (comme MD5, SHA-1, ...) ou théorique.

MS Dousti
la source

Je ne suis pas très sûr dans le domaine des encodages, mais

toujours une entropie élevée? Par construction, il a certainement le même hachage pour doubler autant de cordes qu'auparavant. Et ils viennent par paires très proches les uns des autres. (Oh, ça devrait être

dans la deuxième ligne de 2.)

H

$H$

| R | = k

$|R|=k$

Raphael

@Raphael: Merci d'avoir souligné la faute de frappe (corrigée). H a la même entropie que G, sauf dans la condition où R = G (L). Par exigence, dans cette condition, H (x) doit être égal à R. Nous ne pouvons rien faire ici pour augmenter l'entropie; car l'exigence de «réflexivité» nous empêche de modifier la sortie.

MS Dousti

@Sadeq: Faut-il que la fonction de hachage soit calculée récursivement? Est-ce que l'algorithme profite de ce fait de quelque façon?

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, merci. Je crois que cela peut répondre à ma question, comme elle a été posée. Vous avez formulé la réponse dans une mise en garde appropriée. D'un point de vue pragmatique, j'aime le fait que c'est une superposition pour tout algorithme bien connu tel que SHA-1. Si j'ai bien compris, votre algorithme continuera de calculer récursivement les hachages jusqu'à ce qu'il atteigne la collision requise puis s'arrête. Dans ce cas, nous pouvons peut-être doubler cette solution naïve. Ma préoccupation est qu'il semble y avoir une hypothèse implicite que l'algorithme intégré (SHA-1 disons) finira par atteindre le hachage de collision requis, étant donné un