Score:3

Crypto

One way function candidate based on the Collatz function

Craig Feinstein

3/22/24, 7:13 AM

I am relatively new to cryptography and am curious what cryptographers would say about what I think is a beautiful one-way hash function described in a paper I found here https://arxiv.org/abs/1801.05079

To summarize the hash function, the Collatz function $f: \mathbb N \rightarrow \mathbb N$, is defined as $f(n)=(3n+1)/2$ when $n$ is odd and $f(n)=n/2$ when $n$ is even.

Let $n$ be composed of 512 bits. Let $m$ equal the function $f$ composed 256 times of $n$. Then this function has a computation path which can be specified with 256 bits, where each of the bits represents whether the formula for each $f$ is $(3n+1)/2$ or $n/2$. Call this path $p$.

Split the bits of $m$ and $n$ into left and right parts, of 256 bits each. Then XOR these four numbers together and XOR this new number with $p$. This will be the output of the one way function.

It is easy to compute the output given the input, but computing the input given the output seems impossible to me. How would cryptographers deal with such a function? Are there features of it that make it inferior to more popular one way hash functions?

307

1 + 4

fgrieu

3/22/24, 1:28 PM

Among issues that pop to mind: $m$ will occasionally exceed 512 bits, and then "split the bits of $m$ (…) into left and right parts" is ambiguous. That seems more expensive than a SHA-512 compression, for half the input and output. Often $n$ and $n'\ne n$ will have computation paths with the same Hamming weight (number of multiplications by 3), and within that if $n\approx n'$ then $m\approx m'$ to some degree. Within that those $(n,n')$ sharing say 320 high-order bit and having low $m\approx m'$ might lead to 256-bit hashes with overly frequent collisions in the say 64 high-order bits.

Daniel Wagner

3/22/24, 7:47 PM

The linked paper has a *lot* of red flags.

Craig Feinstein

3/23/24, 2:26 AM

Red flags? Like what? I thought the function is beautiful because it is so simple, yet apparently very complex.

fgrieu

3/23/24, 4:58 AM

Red flag: The second paragraph in the introduction of the cited paper does not distinguish OWF (the paper's aim) and _trapdoor_ OWF (which the construction is not): "OWF candidates are used in practice. The bulk of asymmetrical encryption is based on OWF candidates such as factoring and discrete logarithm problems. It is not proven that they are reversible, but so far no efficient and non quantum algorithms are found yet. For example: if a relatively large composite integer is given, it is difficult to decompose it into a product of two integers (integer factorization)."

Score:5

Crypto

Daniel S

3/22/24, 8:06 AM

Cryptographically, this would not be a good choice. Firstly note that there are $2^{256}$ pre-images of zero which consist of any 256-bit value followed by 256 zeros. This makes collision finding trivial.

Next, there's a large class of outputs for which computing a pre-image is trivial, and there may be further weaknesses.

Let $y$ be a 256-bit number with the 2nd, 1st and 0th bits (the three least significant bits) set to 010 and with bits 3-255 such that there are no adjacent 1s in $y\oplus 2^{255}$. There are $F_{253}$ such numbers where $F_i$ is the $i$th Fibonacci number. I claim that it is trivial to find a pre-image for any $y$ of this form.

Specifically, let $z$ be the number created by masking off bits $2-255$ of $y$ and shifting down by 1 position (so that the 0th and 1st bits are 0). In other words $z=(y\oplus 2)/2$. Now let $x=2^{256}z+2^{255}$.

The first 255 applications of $f$ shift this number down by a bit each. The 256th application is the Collatz function applied to a 256-bit input $t=2z\oplus 1$ which is a number with no consecutive 1s in its binary representation. For such a number multiplication by 3 has no binary carriers and so $3t=2t\oplus t$. By our structure the last three bits of $3t$ are 011 and so $3t+1=4z\oplus 2z\oplus 4$ and $(3t+1)/2=2z\oplus z\oplus 2$.

Now note that the 4 256-bit numbers that we must XOR are 0, $2^{255}$, $z$ and $2z\oplus z\oplus 2$, which gives the answer $2z\oplus 2^{255}\oplus 2$. We then XOR on $p$ the path value, which is 1 followed by 255 zeroes (I'm assuming that the path is recorded with the initial step recorded in the least significant bit, but the generalisation is obvious) and obtain output $2z\oplus 2=y$.

+ 3

Oscar Smith

3/22/24, 5:05 PM

I don't think this automatically makes this a bad function. These all seem fairly similar to the flaws with RSA and it's not clear that there isn't a PKCS type protocal for this one way function. For example, all the attack you have described are invalid if you make `n` be a 516 bit number with the 4 lowest bits set to 1.

Daniel S

3/22/24, 7:56 PM

I agree that my answer only describes why the function presented in the question would make a poor cryptographic hash function and does not answer how suitable a different function is as a PKC primitive.

fgrieu

3/23/24, 8:21 AM

@OscarSmith: with some adaptation, it's conceivable we could make a secure (if not efficient OWF from the construction. But Public Key encryption, at least as practiced, requires a _trapdoor_ OWF. RSA is one. The construction does not even pretend being one.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: One way function candidate based on the Collatz function

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.