# Is it possible to generate a hash function that produces similar output to SHA-256?

Is it possible to create a hash function that generates a correlated to SHA-256 when given the same input?

In other words, given a fixed input X:

SHA-256(X)=A
SHA-256'(X)=B


where he outputs A and B are similar, or correlated.

I was thinking about remodeling a few parts of the SHA-256 function without changing the underlying construction too much. Can someone offer more insight or suggestions on whether it is possible to do this?

EDIT: I was thinking of creating a hash function with a *built-in "backdoor" that allows for preimage attacks. Sort of creating a breakable version of SHA-256.

• It's trivial to just add a post-processing to SHA-256 and call it something new, but you may be looking for something low-level. – DannyNiu Jan 2 at 13:54
• What is your aim? Why do you want to remodel? – kelalaka Jan 2 at 14:02
• This seems like a XY problem, where you want a hash function with a pre-image backdoor, but you asked tweaking SHA-256. I'd suggest considering "Universal Hashing", they have simple maths that're useful for MACs, but not useful for normal hashing functions. Also CRCs may work for you. – DannyNiu Jan 2 at 14:33
• If A and B are just related, then are we really talking about a pre-image attack where $H(x) = y$ given $y$? My answer was for a pre-image attack... – Maarten Bodewes Jan 2 at 16:08

## 3 Answers

I was thinking of creating a hash function that produces a similar/correlated output to SHA256, but with an in-built "backdoor" that allows for preimage attacks. Sort of creating a "breakable" version of SHA-256.

That is not possible for arbitrary sized messages and unkeyed hash functions.

Assume that you created a hash function such that $$h(m) \approx SHA256(m)$$. This similarity is not defined in the question, however, we can consider that it a permutation, or small edit distance, or correlated. Assume that the similarity can be found faster than pre-image attack of SHA256.

Now assume that $$h()$$ is a weak hash function that you can find pre-images easily. Now;

• take $$z = SHA256(m)$$
• use the similarity to find all possible candidates ( from the premutation, small edit, correlation, or..) $$z_i \in \{ a\;|\; a \text{ similar to } z\}$$
• find pre-images of each $$z_i$$; $$m_i = \operatorname{pre-image-h}(z_i)$$
• check all $$m_i$$ on SHA256 to see that one of them is the pre-image $$z \stackrel{?}{=} \operatorname{SHA256}(m_i).$$

That is the break of the pre-image of SHA256. Not expected!.

• Sorry, just defined one in my own answer. – Maarten Bodewes Jan 2 at 14:40
• That is not a problem. – kelalaka Jan 2 at 14:40
• The problem with your answers is that it is not possible to get a pre-image attack on $H$, but that's not necessarily the case with $H'$. The fact that you cannot get pre-images on $H$ does not preclude pre-images on derived functions. Actually, if you think of H as a map, then you can simply create a special case for a specific input that collides with another hash. – Maarten Bodewes Jan 2 at 14:43
• @MaartenBodewes there was a typo there $h'=h$ – kelalaka Jan 2 at 14:45

To backdoor short messages or e.g. their prefixes, you can choose some deterministic public key encryption scheme $$PK$$ with short ciphertexts (not sure if there are ones suitable here), generate key pair $$(Pub,Priv)$$ and define hash as

$$H(m) = FirstBits_{128}(SHA256(m)) ~||~ Pub.Encrypt(FirstBits_t(m)).$$

$$H$$ will be "similar" to SHA256 in that first 128 bits would be the same. And, having the private key, you can make the preimage attack: given $$(h~||~c) = H(m)$$, you can recover $$FirstBits_t(m) = Priv.decrypt(c)$$. This recovers full short message or its prefix. In the latter case, you won't get a preimage for $$H$$ but only some information about the input.

Of course parameters can be adjusted, but the idea should work. I don't know whether such short public-key systems exist, but at least it could work for larger hashes.

Possible design for SHA512:

Disclaimer: I am not sure this is a good way to do public key encryption

We shall use curve25519 and a stream cipher (e.g. AES in counter mode or simply one-time pad). Let $$G$$ be the generator of the group. The hash designer generates private key $$a \in \mathbb{Z}_{256}$$ (there's some bit post-processing to be done, see the curve page) and computes public key $$P=[a]G$$ which has size 256 bits. Then, the hash function of a message $$m$$ is defined as:

1. Compute a deterministic ephemeral key with, say, $$b = SHAKE256(m).$$
2. Compute the shared secret key $$k = SHAKE128([b]P) = SHAKE128([ab]G).$$
3. Compute the ciphertext $$c = k \oplus FirstBits_{128}(m).$$
4. Compute the digest $$H(m) = FirstBits_{128}(SHA512(m)) ~||~ [b]G ~||~ c.$$

As a designer, you can utilize the backdoor in the following way:

1. Let $$(h, [b]G, c) = H(m).$$
2. Compute the shared secret key $$k = SHAKE128([a][b]G) = SHAKE128([ab]G).$$
3. Compute the ciphertext $$FirstBits_{128}(m) = k \oplus c.$$
4. Try to verify $$H(m)$$ by recomputing. This will fail either if $$H(m)$$ was modified (computed incorrectly) or if $$m$$ was longer than 128 bits.

Note that this scheme does not provide integrity for long messages. That is, even the designer can not distinguish $$H(m)$$ for long secret $$m$$ from random strings.

• Nice, however, this assumes that the hash function cannot support messages larger than the message space of the Public-key cryptosystem. And, this is also a keyed hash function by design. – kelalaka Jan 2 at 15:09
• As I wrote, this allows to backdoor short messages, or e.g. a prefix of the message. You can still hash long messages if you want. Public key is a hardcoded part of the hash function so I won't call it "keyed". – Fractalice Jan 2 at 15:15
• Could you work out a bit more on how you can create a pre-image attack for this function using the private key? – Maarten Bodewes Jan 2 at 16:06
• This also reduces the pre-image of the $\operatorname{SHA256}(m)$. Since we always assume that the method is public, then the SHA256 has only 128-bit preimage security. – kelalaka Jan 2 at 17:59

That is possible if ...

SHA-256 is not broken today, but it is not a provable collision resistance hash function and it will be broken in the future.

If you know the collisions or preimages for SHA-256, you can change some parts of this hash function and design a new modified hash function that its output is similar/correlated to SHA-256.

In Malicious Hashing, Ange Albertini et al modified four 32-bit constants of SHA-1 and designed a custom SHA-1 that can be fully compromised. Changing some functions or constants of a broken SHA-256 to design a new hash function that its output is correlated to SHA-256 is much easier.

• But this custom SHA-1 is not really correlated to the real SHA-1, except the algorithm itself? – Fractalice Jan 3 at 21:42
• Yes, the goal of designing Malicious SHA-1 was not be to design a custom SHA-1 that its output is correlated to SHA-1. – Hypatia Jan 4 at 0:39