2
$\begingroup$

I was wondering if there are any hash functions that you can use over and over again on an input until it eventually leads to 0 (or 000000... or 111111... or just any value that would be always the same for any input). It doesn't matter for my question if it is actually bad or good if a hash function has this property.

Does anyone know functions like these? I would be also interested in how many times one would have to repeat the hashing on average to come to the final value.

$\endgroup$
5
  • 4
    $\begingroup$ How about H(X) = X+1 ? $\endgroup$ Aug 31, 2021 at 18:06
  • 4
    $\begingroup$ "Hash function" is a very broad term -- you should clarify what other security properties you desire of the hash function (collision-resistance, second-preimage resistance, one-wayness, etc), besides this property of "eventually 0". Otherwise the question can be answered with trivial functions, like the one above. $\endgroup$
    – Mikero
    Aug 31, 2021 at 20:37
  • $\begingroup$ Among other properties of the function that need to be specified: Must it be effectively possible to reach the final point from any input on a computer? Notice that's antagonist with standard definitions of cryptographic properties like collision-resistance! If yes, what's the desired maximum number of steps? If no, does the function nevertheless need to be efficiently computable ? Must the function definition be fully public, or can it embed a secret key? $\endgroup$
    – fgrieu
    Sep 1, 2021 at 10:27
  • $\begingroup$ It should be possible to reach 0 with any input after some iterations. The maximum number of steps should be polynomially bounded. The function should be efficiently computable and it can be fully public (though I think I don't really understand what public means, sorry. I need to research more). Since 0 is the final form for any input, the 'collisions' that should appear the least are essentially the number of steps to get to an answer. I know this doesn't follow the usual hashing functions, I am sorry to not have thought about the requirements a bit more. You ask great questions fgrieu. $\endgroup$
    – user94600
    Sep 1, 2021 at 11:19
  • $\begingroup$ So actually, there is no security needed for these kinds of functions. It should be collision-resistant in the number of steps needed till 0. There is no need for one-wayness or second-preimage resistance. $\endgroup$
    – user94600
    Sep 1, 2021 at 13:12

2 Answers 2

2
$\begingroup$

Suppose that $h:Z\rightarrow X$ is a cryptographic hash function. For simplicity, let's model your restrictions $h|_{X}:X\rightarrow X$ of cryptographic hash functions by random functions since random functions can be studied mathematically.

Using Cayley's formula, we shall calculate the probability that for a random function $f:X\rightarrow X$, there exists some $y\in X$ such that for all $x\in X$, there is some $m$ with $f^{m}(x)=y$; we will also calculate some other things as well. All of these probabilities are very low.

Let $X$ be a finite set with $X$, and let $f:X\rightarrow X$ be a function. Then if we set $\omega(f)=\bigcap_{n}f^{n}[X]$, then $\omega(f)$ is the largest subset of $X$ such that $f|_{\omega(f)}$ is a permutation of $\omega(f)$.

Define a mapping $f_{*}:X\rightarrow\omega(f)$ by letting $f_{*}(x)=f^{m}(x)$ where $m$ is the least natural number such that $f^{m}(x)\in \omega(f)$. Then for each $y\in \omega(f)$, the set $f_{*}^{-1}[\{y\}]$ is the vertex set for a rooted tree $(f_{*}^{-1}[\{y\}],E_{f,y})$ with root $y$. We define the edge set by setting $E_{f,y}=\{\{x,f(x)\}\mid x\in f_{*}^{-1}[\{y\}],x\neq y\}$.

Now, if $Y\subseteq X$, and $s$ is a permutation of $Y$, then by a version of Cayley's formula, there are $T_{|X|,|Y|}$ many functions $f:X\rightarrow X$ with $f|_{\omega(f)}=s$ where we define $T_{n,k}=k\cdot n^{n-k-1}$.

In particular, we have $$n^{n}=\sum_{k=1}^{n}\binom{n}{k}\cdot k!\cdot T_{n,k}= \sum_{k=1}^{n}\frac{n!}{(n-k)!}\cdot k\cdot n^{n-k-1}.$$

Let $c_{n}$ be the number of functions $f:X\rightarrow X$ with $|X|=n$ such that there exists some $y\in X$ such that for all $x\in X$, there exists an $m$ such that $f^{m}(x)=y$. Let $\gamma_{n}=c_{n}/(n^{n})$. In other words, $\gamma_{n}$ is the probability that for random $f:X\rightarrow X$ with $|X|=n$, there is some $y\in X$ such that for all $x\in X$ there is some $m$ with $f^{m}(x)=y$.

Now, observe that if $Y$ is a set, then there are $(|Y|-1)!$ many permutations of $Y$ consisting of a single cycle of length $|Y|$.

By using this calculation, we obtain $$c_{n}=\sum_{k=1}^{n}\binom{n}{k}(k-1)!T_{n,k}=\sum_{k=1}^{n}\frac{n!}{(n-k)!}\cdot n^{n-k-1},$$ and $$\gamma_{n}=\sum_{k=1}^{n}\frac{n!}{(n-k)!}\cdot n^{-(k+1)}.$$

Therefore, $$n\gamma_{n}=\sum_{k=1}^{n}(1-\frac{1}{n})(1-\frac{2}{n})\dots(1-\frac{k-1}{n}).$$

Theorem: $\lim_{n\rightarrow\infty}\gamma_{n}\sqrt{n}=\sqrt{\frac{\pi}{2}}$.

Proof outline: We have $$\lim_{n\rightarrow\infty}\gamma_{n}\sqrt{n}=\lim_{n\rightarrow\infty}\sum_{k=1}^{n}\frac{1}{\sqrt{n}}(1-\frac{1}{n})(1-\frac{2}{n})\dots(1-\frac{k-1}{n})$$

$$=\lim_{n\rightarrow\infty}\sum_{k=1}^{n}\frac{1}{\sqrt{n}}\exp(-(\frac{1}{n}+\dots+\frac{k-1}{n}))$$

$$=\lim_{n\rightarrow\infty}\sum_{k=1}^{n}\frac{1}{\sqrt{n}}\exp(-\frac{k(k-1)}{2n}))=\int_{0}^{\infty}\exp(\frac{-x^{2}}{2})dx=\sqrt{\frac{\pi}{2}}.$$

Q.E.D.

Suppose $X$ is a set with $0\in X,|X|=n$. Let $d_{n}$ be the number of functions $f:X\rightarrow X$ where for all $x\in X$, there exists an $n$ with $f^{n}(x)=0$. Let $\delta_{n}$ be the probability that given a random function $f:X\rightarrow X$, for each $x\in X$, there exists an $n$ with $f^{n}(x)=0$. Then $\delta_{n}=1/n$ and $d_{n}=n^{n-1}$. To see that $d_{n}=n^{n-1}$, one can put the collection of all functions $f:X\rightarrow X$ where $\forall x\exists n,f^{n}(x)=0$ into a one-to-one correspondence with the set of all pairs $(E,x_{0})$ such that $(X,E)$ is a tree and $x_{0}\in X$, and then one can apply Cayley's formula to count the number of such trees.

In any case, since the probabilities $\gamma_{n},\delta_{n}$ approach zero as $n$ approaches infinity, we know that it is unlikely for there to exist a point $x\in X$ such that for all $y$, there is an $m$ with $f^{m}(x)=y$ is infinite.

Using arguments similar to the ones I already gave, we also compute the following probabilities.

Suppose $0\in X,|X|=n$. Given a random function $f:X\rightarrow X$, there is an $n^{-2}$ probability that $f(0)=0$ and for all $x\in X$, there is an $m$ where $f^{m}(x)=0$. Furthermore, there is a $1/n$ probability that there exists a $y\in X$ such that $f(y)=y$ and for all $x\in X$, there is an $m$ with $f^{m}(x)=y$.

Given $|X|=n,a,b\in X,a\neq b$, let $\alpha_{n}$ denote the probability that $f^{n}(a)=b$ for some $n$. Then $\lim_{n\rightarrow\infty}\alpha_{n}\sqrt{n}=\sqrt{\frac{\pi}{2}}$.

The expected amount of time to arrive at final point

Suppose that $X$ is an random set with $|X|=n$. Let $a\in X$ be randomly selected, and let $f:X\rightarrow X$ be a random function. Then let $A,B$ be the random variables where $A=k$ precisely when $k$ is the least non-negative integer such that $f^{k}(x)\in\omega(f)$ and $B=m$ precisely when $m$ is the least natural number with $m>k$ and $f^{m}(x)=f^{k}(x)$.

First of all, observe that the conditional distribution of $A$ given that $B=m$ is uniform on $\{0,\dots,m-1\}$. In other words, $P(A=k\mid B=m)=\frac{1}{m}$. Now, let's calculate the probability distribution of $B$.

Observe that $P(r<B)=(1-\frac{1}{n})\dots(1-\frac{r}{n})$ and $$P(B=m)=\big{(}(1-\frac{1}{n})\dots(1-\frac{m-1}{n})\big{)}\cdot\frac{m}{n}.$$

Therefore, if $r<m$, then $$P(A=r,b=m)=\big{(}(1-\frac{1}{n})\dots(1-\frac{m-1}{n})\big{)}\cdot\frac{1}{n}.$$

When $m$ is large, we have

$$P(m<B)\approx\exp\big{(}-(\frac{1}{n}+\dots+\frac{m}{n})\big{)}=\exp\big{(}\frac{m(m+1)}{2n}\big{)}\approx\exp\big{(}\frac{m^{2}}{2n}\big{)}.$$

We have $$P(A=r)=\sum_{m=r+1}^{n-1}P(A=r,B=m)=\sum_{m=r+1}^{n-1}(1-\frac{1}{n})\dots(1-\frac{m-1}{n})\cdot\frac{1}{n}.$$

When $n$ is large, we have

$$P(A=r)\approx\sum_{m=r+1}^{n-1}\exp(-(\frac{1}{n}+\dots+\frac{m-1}{n}))\cdot\frac{1}{n}=\sum_{m=r+1}^{n-1}\exp(-(\frac{(m-1)m}{n}))\cdot\frac{1}{n}$$ $$\approx\sum_{m=r+1}^{n-1}\exp(-(\frac{m^{2}}{2n}))\cdot\frac{1}{n}.$$

Therefore, $$P(A=r)\cdot\sqrt{n}\approx \sum_{m=r+1}^{n-1}\exp(-\frac{1}{2}\cdot(\frac{m}{\sqrt{n}})^{2})\cdot\frac{1}{\sqrt{n}}\approx\int_{r/\sqrt{n}}^{\infty}\exp(\frac{-x^{2}}{2})dx.$$

$\endgroup$
3
  • 1
    $\begingroup$ This answer shows that it is quite unlikely that a random function has the property that the OP asks for. What it doesn't address is whether one can devise a hash function that has that property, and meets some additional unspecified security properties... $\endgroup$
    – poncho
    Sep 1, 2021 at 2:55
  • 1
    $\begingroup$ @poncho Would it be enough to answer the question for any trivial adaptation of the SHA cryptographic hash algorithms currently in use? I do think that the onus is on the asker to define the requirements and security properties. $\endgroup$
    – Maarten Bodewes
    Sep 1, 2021 at 10:15
  • $\begingroup$ Hello, thank you very much for this answer, but I am not able to understand it because I not educated enough. I hope it can still be useful for others :) $\endgroup$
    – user94600
    Sep 1, 2021 at 11:14
0
$\begingroup$

Here is a proposal for a $w$-bit efficiently computable function $F:\{0,1\}^*\to\{0,1\}^w$ which after at most $2^n+1$ iterations of $F$ reaches $0^w$ (the all-zero bitstring of $w$ bits), and otherwise attempts to mascarade as a passable hash. It has parameters $(w,n,H,K)$ with $0<2n\le w$, an ideal public hash $H$ of $w$ bits, and a bitstring $K$ (it's a technically so that $F$ is a family of functions, and we can choose a random fixed $K$, public or secret).

[Skip for a simplified version] We construct an efficient permutation $E$ of $\{0,1\}^w$ keyed by $K$; and it's inverse permutation $D$. One way is to build an (almost, for odd $w$) symmetric Feistel cipher $E$ using at round $r$ (among say 6) the round function $X\mapsto H(\underline r\mathbin\|K\mathbin\|X)$, truncated to $\lfloor w/2\rfloor$ or $\lceil w/2\rceil$ per the parity of $r$, where $\underline r$ encodes the round number on a byte. The construction of $D$ is well-known.

We construct $F$ as follows

  1. If input $X$ if not $w$-bit, then output $H(X\mathbin\|K)$
  2. [Skip for a simplified version] $X\gets D(X)\oplus D(0^w)$
  3. Split $X$ into $(w-n)$-bit $X_0$ and $n$-bit $X_1$, so that $X=X_0\mathbin\|X_1$
  4. If $X_1=0^n$, then output $0^w$ and stop
  5. Change $X_0$ to $H(K\mathbin\|X)$ truncated to $(w-n)$-bit
  6. Decrease $X_1$, considered as an integer in range $[0,2^n)$ per e.g. big-endian binary
  7. $X\gets X_0\mathbin\|X_1$
  8. [Skip for a simplified version] $X\gets E(X\oplus D(0^w))$
  9. Output $X$.

Design rationale:

  • In the simplified version
    • The rightmost $n$ bits of $X$, noted $X_1$, are a down-counter (step 6) of how many iterations of $F$ are needed until $X_1$ reaches zero. The next iteration of $F$ will see $X_1=0^n$ (step 4) and output $X=0^w$.
    • The other bits of $X$, noted $X_0$, evolve per a normal hash of $X$ (step 5).
    • Step 1 handles arbitrary bitstrings not $w$-bit, giving a pseudo-random $X_1$ at the next iteration.
  • In the full version, the externally visible $X$ is encrypted using $E$ and XOR with an appropriate constant so that $0^w$ encrypts to itself (step 8); then decrypted at the next iteration of $F$ (step 2). That makes $F$ look more like a normal hash, hiding the down-counter.

Overall the construction is such that $F(0^w)=0^w$, and $0^w$ is reached after at most $2^n$ iterations of $F$ for $w$-bit starting point, with the number of steps roughly uniformly distributed on $[1,2^n]$. It's one more for other input sizes. The goal is that $F$ for random unknown $K$ is computationally indistinguishable from a random function among those with similarly weird distribution of their iteration map.

$F$ is not good hash by standard measures, in particular because

  • It's easy to exhibit many preimages of $0^w$, thus many collisions (but the lack of collision resistance is unavoidable given the specification, for one knowing $K$ or otherwise able to obtain $F(X)$ for arbitrary $X$).
  • One knowing secret $K$ can perform some weird things, like predicting without trial and error how many iterations of $F$ remains from any given point (with only a vanishingly small probability of error when $X=0^w$ at step 7, which causes $0^w$ to be reached one sooner than predicted).

Note: in order to keep the effort to reach $0^w$ polynomial (as asked) w.r.t. the customary security parameter $w$, we can choose e.g. $n=\lceil4+\log_2w\rceil$.

$\endgroup$
4
  • $\begingroup$ Thank you. I appreciate the effort, though I am not educated enough on the subject to understand everything. I got 2 questions though. How would you predict (almost) without error how many iterations remain and why are there many preimages (and thus collisions) with the same number of iterations (for $2^n$ max iterations)? $\endgroup$
    – user94600
    Sep 1, 2021 at 19:27
  • $\begingroup$ @Dude: I modified the definition of $F$ to have a simplified version; added a design rationale, starting with the simplified version; and rounded some rough edges. First grasp what happens when iterating $F$ in the simplified version. $\endgroup$
    – fgrieu
    Sep 2, 2021 at 6:15
  • $\begingroup$ But is this computeable without knowing K? Except using some super slow homomorphic encryption? If I understsrand correctly and it isn't than the security properties are fairly week. $\endgroup$
    – Meir Maor
    Sep 2, 2021 at 7:59
  • $\begingroup$ @MeirMaor: no, $F$ is not computable without knowing $K$ (except for the fixed point $0^w$). $K$ has the role of the magic constants in hashes like MD5. I acknowledge the security properties are weak. Reducing what's possible with knowledge of $K$ does not seem impossible, but would be a major redesign. $\endgroup$
    – fgrieu
    Sep 2, 2021 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.