Gibt es 'reflexive' Hash-Algorithmen?

Gibt es eine Klasse von Hash-Algorithmen, ob theoretisch oder praktisch, so dass ein Algorithmus in der Klasse gemäß der unten angegebenen Definition als "reflexiv" betrachtet werden kann:

hash1 = algo1 ("Eingabetext 1")
hash1 = algo1 ("Eingabetext 1" + hash1)

Der Operator + kann eine Verkettung oder eine andere angegebene Operation sein, um die Ausgabe (Hash1) wieder in die Eingabe ("Eingabetext 1") zu kombinieren, sodass der Algorithmus (algo1) genau das gleiche Ergebnis liefert. dh Kollision bei Eingabe und Eingabe + Ausgabe. Der Operator + muss die Gesamtheit beider Eingaben kombinieren, und der Algo darf einen Teil der Eingabe nicht verwerfen.

Der Algorithmus muss eine hohe Entropie in der Ausgabe erzeugen. Es kann, muss aber nicht kryptografisch schwierig sein, die Ausgabe auf eine oder beide mögliche Eingaben zurückzusetzen.

Ich bin kein Mathematiker, aber eine gute Antwort könnte einen Beweis dafür enthalten, warum eine solche Klasse von Algorithmen nicht existieren kann. Dies ist jedoch keine abstrakte Frage. Ich bin wirklich daran interessiert, einen solchen Algorithmus in meinem System zu verwenden, falls es einen gibt.

Dies ist ein Duplikat einer Frage, die zuerst unter /programming/4823680/reflexive-hash veröffentlicht wurde

ds.algorithms hash-function Gemeinschaft
quelle

Verwandte: Assoziative Hash-Mischung

Tsuyoshi Ito

Interessieren Sie sich für diese Eigenschaft, die für den gesamten Eingabetext oder für einen Eingabetext gilt? Wenn Sie möchten, dass es für den gesamten Eingabetext gilt, ist das Erstellen von Kollisionen von Natur aus trivial, sodass ich nicht denke, dass dies als gute Hash-Funktion angesehen werden kann.

Peter Taylor

Jemand möchte Dateien hashen, die ihre eigenen Hashes enthalten! ;)

Raphael

@ Peter Taylor - Ich suche eine Funktion, die wie für beliebigen Eingabetext beschrieben funktioniert. Jede unterschiedliche Eingabe erzeugt einen Hash, der im Allgemeinen eine hohe gegenseitige Entropie zu jeder anderen möglichen Eingabe aufweist. So gut wie eine gute irreversible Hash-Funktion funktioniert. Die gesuchte Hash-Funktion muss jedoch nicht die Eigenschaft der Irreversibilität haben. Eine hohe Entropie ist ausreichend.

@ Raphael - Ja, das ist eine prägnante Art, es auszudrücken.

Antworten:

Ich gebe eine triviale Konstruktion, die die Anforderung erfüllt. Ich stelle es zur Verfügung, um lediglich die Existenz einer "reflexiven" Hash-Funktion zu beantworten .

Sei eine beliebige Hash-Funktion, die eine hohe Entropie in der Ausgabe erzeugt. Angenommen, hasst Binärzeichenfolgen beliebiger Länge mit Binärzeichenfolgen Bit, wobei eine positive ganze Zahl ist. Sei der Verkettungsoperator und sei bezeichnen die Länge der Binärzeichenfolge . $G$ $G$ $k$ $k$ $+$ $|x|$ $x$

Definieren Sie die Hash-Funktion am Eingang wie folgt: $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)$

Wie gesagt, dies ist eine triviale Konstruktion. Es kann auf jede Hash-Funktion angewendet werden, praktisch (wie MD5, SHA-1, ...) oder theoretisch.

MS Dousti
quelle

H

$H$

| R | = k

$|R|=k$

@ Raphael: Danke, dass du auf den Tippfehler hingewiesen hast (korrigiert). H hat die gleiche Entropie wie G, es sei denn, R = G (L). Unter diesen Bedingungen sollte H (x) notwendigerweise gleich R sein. Wir können hier nichts tun, um die Entropie zu erhöhen; da die Anforderung "Reflexivität" uns daran hindert, die Ausgabe zu ändern.

MS Dousti

@Sadeq: Muss die Hash-Funktion rekursiv berechnet werden? Hat der Algorithmus in irgendeiner Weise von dieser Tatsache profitiert?

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, danke. Ich glaube, dies kann meine Frage beantworten, wie sie gestellt wurde. Sie haben die Antwort in einer geeigneten Einschränkung formuliert. Aus pragmatischer Sicht gefällt mir die Tatsache, dass es sich um eine Überlagerung für jeden bekannten Algorithmus wie SHA-1 handelt. Wenn ich es richtig verstanden habe, berechnet Ihr Algorithmus weiterhin rekursiv Hashes, bis er die erforderliche Kollision trifft, und stoppt dann. In diesem Fall können wir dies vielleicht als naive Lösung bezeichnen. Meine Sorge ist, dass es eine implizite Annahme zu geben scheint, dass der eingebettete Algorithmus (SHA-1 sagen) schließlich den erforderlichen Kollisions-Hash treffen wird, wenn ein