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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.