1
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$ – DannyNiu Jan 2 at 13:54
  • 1
    $\begingroup$ What is your aim? Why do you want to remodel? $\endgroup$ – kelalaka Jan 2 at 14:02
  • $\begingroup$ 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. $\endgroup$ – DannyNiu Jan 2 at 14:33
  • $\begingroup$ 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... $\endgroup$ – Maarten Bodewes Jan 2 at 16:08
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Sorry, just defined one in my own answer. $\endgroup$ – Maarten Bodewes Jan 2 at 14:40
  • $\begingroup$ That is not a problem. $\endgroup$ – kelalaka Jan 2 at 14:40
  • $\begingroup$ 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. $\endgroup$ – Maarten Bodewes Jan 2 at 14:43
  • $\begingroup$ @MaartenBodewes there was a typo there $h'=h$ $\endgroup$ – kelalaka Jan 2 at 14:45
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – kelalaka Jan 2 at 15:09
  • $\begingroup$ 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". $\endgroup$ – Fractalice Jan 2 at 15:15
  • $\begingroup$ Could you work out a bit more on how you can create a pre-image attack for this function using the private key? $\endgroup$ – Maarten Bodewes Jan 2 at 16:06
  • 1
    $\begingroup$ 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. $\endgroup$ – kelalaka Jan 2 at 17:59
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ But this custom SHA-1 is not really correlated to the real SHA-1, except the algorithm itself? $\endgroup$ – Fractalice Jan 3 at 21:42
  • $\begingroup$ 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. $\endgroup$ – Hypatia Jan 4 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.