My question is whether it is possible to use "another" algorithm than the sha256 to hash data but end up with the identical sha256 hash (obviously without using the sha256 algorithm)?
-
3$\begingroup$ Are we talking about all $m$ or just a single $m$? Are we talking a specific $m$ or looking for a collision between the outputs see here $\endgroup$– kelalakaSep 3, 2022 at 20:40
-
$\begingroup$ I Like both your ideas, Forest and elderlPednt. @Forest: i get your Point. How would you evaluate If the result should be Always the First 32 Characters? Would that Be possible without going theough sha256? (and removing the Last 32 chars) @ elderlypedant: great thought. I would say No, both are Not the Same. One is obv more efficient in getting the Same result. Can this Idea Be appliwd to sha256? (make algorithm quickeer?) Sorry for typos, bumpy road $\endgroup$– user103673Sep 4, 2022 at 9:47
2 Answers
Due to the pigeonhole principle, any random function will eventually produce collisions with any other random function. After all, there are far more possible inputs than there are possible outputs (for most traditional cryptographic hashes). However, there isn't any way to create an algorithm that always produces the same hash as SHA-256 for the same input without that algorithm being SHA-256.
Given two random functions $f$ and $g$ (any good cryptographic hash will adequately approximate a random function for all intents and purposes), $\exists{m}:f(m) = g(m)$. This means that there will exist some message $m$ that produces the same hash with both functions. It is also true that there can exist two different messages which, when hashed with different functions, produce the same result (i.e. $\exists m,n: f(m) = g(n)$, which is called a claw). However, if $\forall{m}:f(m) = g(m)$ (i.e. every message results in the same hash when hashed with the other function), then the functions are identical. There is no situation where that can be true but $f$ and $g$ are not the same.
-
$\begingroup$ i get your Point. How would you evaluate If the result should be Always the First 32 Characters? Would that Be possible without going theough sha256? (and removing the Last 32 chars) $\endgroup$ Sep 4, 2022 at 13:40
-
$\begingroup$ @user103667 Not really. I mean, you could argue that a function defined as a truncated version of SHA-256 technically isn't identical to SHA-256... $\endgroup$– forest ♦Sep 5, 2022 at 11:04
-
$\begingroup$ Beware that there is no way of validating that $f = g$ by trying all $m$ as that's infeasible. It is definitely possible to generate a $g$ which is virtually identical to the hash function, but returns a different value for a certain $m$. This is obvious, just set $m$ to a random value of 256 bit, then return a specific value for that $m$, otherwise return $f$. Or, for an actual example, take hardened SHA-1. $\endgroup$– Maarten Bodewes ♦Sep 6, 2022 at 7:44
In my opinion, it depends on what you mean by “another” (ie. “different”) algorithm.
Here are two algorithms. Each one takes a number as input, and produces a new number as output:
(1)
- Take input number
- Add 25
(2)
- Take input number
- Add 30
- Subtract 5
Are those the same algorithm?
From one viewpoint, clearly NO – one of them has only two steps, the other has three.
But from another viewpoint, YES – given the same input, they both produce exactly the same output.
So like many questions, it really depends on what you actually mean by the terms in the question. For your question, it depends on what you actually mean by the term “another algorithm”.
-
$\begingroup$ @ elderlypedant: great thought. I would say No, both are Not the Same. One is obv more efficient in getting the Same result. Can this Idea Be appliwd to sha256? (make algorithm quickeer?) $\endgroup$ Sep 4, 2022 at 13:41
-
$\begingroup$ @user103667: I’m still not really sure what you’re asking. You could probably make some version of the SHA256 algorithm faster, by carefully re-writing it to better match the features of the compiler you’re going to compile it with, and the hardware you’re going to run it on. The rewritten algorithm would produce the same result, but run faster. Would those two algorithms be “the same” algorithm”? $\endgroup$ Sep 4, 2022 at 14:41
-
$\begingroup$ I would say, no? These are two different algorithms? But there is no question left ;-) $\endgroup$ Sep 4, 2022 at 18:46