Let $ROTR^n(x)$ and $SHR^n(x)$ denote the rotate right (circular right shift) and the right shift operations, as defined in SHA-2 standard.

Consider any function of the form $$f(x) = ROTR^{n_1}(x) \oplus ROTR^{n_2}(x) \oplus \ldots \oplus ROTR^{n_z}(x).$$

According to the fifth element of this list, such functions are reversible (and bijective) if and only if the set $\{n_1, n_2, \ldots, n_{z-1}, n_z\}$ contains an odd number of elements (assuming that $0 \le n_i \le w-1$, where $w$ denotes the length of a word $x$). For example, $\Sigma$ functions in SHA-2 are of this form ($z=3$).

But I want to ask about functions of the form $$g(x) = F^{n_1}(x) \oplus F^{n_2}(x) \oplus \ldots \oplus F^{n_z}(x),$$ where $F^n(x)$ is either $ROTR^n(x)$ or $SHR^n(x)$ (assuming that $0 \le n_i \le w-1$ and $w$ denotes the length of a word $x$). How to determine if such function is reversible (for example, $\sigma$ functions in SHA-2 are of this form)?

  • $\begingroup$ Why don't you start with figuring out how to reverse $x \oplus (x \gg 1)$? $\endgroup$ – Squeamish Ossifrage Apr 17 '19 at 16:20
  • $\begingroup$ @SqueamishOssifrage: I am not asking how to reverse anything. This question is the following: given the description of $g(x)$, how to determine if the function is reversible (bijective)? For example, SHA-2 uses $g(x) = ROTR^{7}(x) \oplus ROTR^{18}(x) \oplus SHR^{3}(x)$ for 32-bit words. How to determine if this function is reversible (I am not asking for an explanation of how to reverse it)? $\endgroup$ – lyrically wicked Apr 19 '19 at 6:08

Your Answer

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

Browse other questions tagged or ask your own question.