Is it possible to find equivalent hash function? Under equivalent, i assume same input produce same output, but they have different initial integer values and/or different set of bitwise operators. Or in other words, does there exist another algorithm of hash function, but having same input->output mapping. If exist, how to find or construct such algorithm, if not exist, do we have some proof of it? For example, we have different search algorithms, they have same input->output mapping, but different properties, for example complexity. Does this analogy work for hash function?

  • $\begingroup$ If you present hash function as a Boolean function I think that there can exist many functions which can be presented as same Boolean function (using different notations for example). $\endgroup$
    – ventaquil
    Apr 14 '19 at 20:26
  • 1
    $\begingroup$ You can always reformulate the same function in many different ways. X+X = X*2 $\endgroup$
    – Natanael
    Apr 14 '19 at 20:33

If a hash function can be described using boolean algebra, you can transform it into an equivalent function using distributivity, commutativity, associativity, De Morgan laws, absorption, etc... Two functions will be equivalent if you can find a serie of transformations that will lead to one another while preserving the equivalence.

See: https://en.wikipedia.org/wiki/Logical_equivalence

If you need a more complex function with flow control, whether two Turing machines are equivalent is undecidable in the general case. You might construct two functions with the same input/output mapping without being able to prove it except by testing all possible inputs, which hashing functions are designed to prevent. However, yes, you can always construct an equivalent function by yourself, by replacing subparts which are provably equivalent ($y+y+y$ becomes $y*3$) or reorder instructions when the order is commutative.

  • 1
    $\begingroup$ For Turing Machnines (or circuits for that matter) it's actually even easier, since it's trivial to introduce additional parts that have no influence on the input output behavior. If the original TM has an initial state $q_0$, just introduce a new initial state $q_0'$ and a state transition from $q_0$ to $q_0'$. This can be done entirely black-box without even looking at the TM. $\endgroup$
    – Maeher
    Apr 16 '19 at 7:00

The compression function of SHA-1 and SHA-2 are defined in terms of bitwise majority and bitwise choice functions:

\begin{align*} \operatorname{Ch}(b, c, d) &:= (b \mathbin\& c) \mathbin| (\lnot b \mathbin\& d), \\ \operatorname{Maj}(b, c, d) &:= (b \mathbin\& c) \oplus (b \mathbin\& d) \oplus (c \mathbin\& d). \end{align*}

Here $\&$ is bitwise and (i.e., $\operatorname{GF}(2)^n$ multiplication), $|$ is bitwise inclusive-or, $\lnot$ is bitwise not, and $\oplus$ is bitwise xor (i.e., $\operatorname{GF}(2^n)$ or $\operatorname{GF}(2)^n$ addition). These functions can be written in many equivalent ways. For example,

\begin{align} \operatorname{Ch}(b, c, d) &= d \oplus (b \mathbin\& (c \oplus d)) \\ \operatorname{Maj}(b, c ,d) &= (b \mathbin\& c) \mathbin| (d \mathbin\& (b \mathbin| c)). \end{align}

Implementations will be written in terms of one form or the other for various reasons like optimizing use of a vector unit or minimizing number of sequential operations, depending on the but the resulting hash function is the same.


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.