# Hashing until reaching zero

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.

• How about H(X) = X+1 ? Aug 31, 2021 at 18:06
• "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. Aug 31, 2021 at 20:37
• 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?
– fgrieu
Sep 1, 2021 at 10:27
• 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.
– user94600
Sep 1, 2021 at 11:19
• 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.
– user94600
Sep 1, 2021 at 13:12

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 and $$P(B=m)=\big{(}(1-\frac{1}{n})\dots(1-\frac{m-1}{n})\big{)}\cdot\frac{m}{n}.$$

Therefore, if $$r, 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

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.$$

• 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... Sep 1, 2021 at 2:55
• @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. Sep 1, 2021 at 10:15
• 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 :)
– user94600
Sep 1, 2021 at 11:14

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$$.

• 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)?
– user94600
Sep 1, 2021 at 19:27
• @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.
– fgrieu
Sep 2, 2021 at 6:15
• 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. Sep 2, 2021 at 7:59
• @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.
– fgrieu
Sep 2, 2021 at 8:08