1
$\begingroup$

I need a compression function $F$ that uses only bitwise operations (AND, NOT, OR, XOR, shifts, rotations) and outputs one 32-bit word $W$ from four 32-bit words $w_1 \mathbin\Vert w_2 \mathbin\Vert w_3 \mathbin\Vert w_4$. The function is required to satisfy one special property: if two 128-bit blocks

$$\begin{array}{l} B_1 = w_{1.1} \mathbin\Vert w_{1.2} \mathbin\Vert w_{1.3} \mathbin\Vert w_{1.4},\\ B_2 = w_{2.1} \mathbin\Vert w_{2.2} \mathbin\Vert w_{2.3} \mathbin\Vert w_{2.4} \end{array}$$

differ only in one word (that is, there exists only one number $x$ such that $w_{1.x} \neq w_{2.x}$), then $$F(B_1) \neq F(B_2).$$

But if we have a set $S$ of $y$ different 128-bit blocks

$$S = \{B_1, B_2, \ldots, B_{y-1}, B_y\}$$

such that for any pair $(B_m, B_n)$ of elements, $B_m$ differs from $B_n$ in two or more words, then the probability of $F(B_m) = F(B_n)$ is the same as for any standard cryptographic compression function (that outputs one 32-bit word from four 32-bit words).

Is it possible to construct such a function? If yes, can anyone give an example of a function that fits the above description?

EDIT

The connection to cryptography is that some attacks on EnRUPT and XXTEA use the fact that the round function does not satisfy the property described above:

The round function of EnRUPT is not bijective for the given key word

and

XXTEA’s $F$ is not bijective for either neighbor

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ The operations you specified make the system Turing complete, so you could describe any algorithm as NOT+AND. Also, what you're looking for is a property called "burst detection", which is in the realm of CRCs. $\endgroup$
    – forest
    Commented Apr 6, 2019 at 7:50
  • 1
    $\begingroup$ @forest: I used the term "bitwise operations" as related to a practical implementation of a function. For example, Keccak block permutations use only bitwise operations, but a practical implementation of a block transformation in SHA-2 also uses additions, hence does not use "only bitwise operations". $\endgroup$
    – lyrically wicked
    Commented Apr 6, 2019 at 8:04
  • $\begingroup$ You can use the parity of the bits: guaranteed to change under single-bit errors (and as a bonus, errors of any odd Hamming weight); cheap to compute using only XOR; extends naturally to larger error-detecting capacity as a special case of any CRC over a polynomial with $x + 1$ as a factor. But there's no cryptographic content here. What do you want this for? What is the connection to cryptography? $\endgroup$
    – Squeamish Ossifrage
    Commented Apr 7, 2019 at 20:48
  • $\begingroup$ @SqueamishOssifrage: I edited the question to explain the connection to cryptography. What do I want this for? The answer depends on the performance of a function with the described property. If the algorithm is fast, then at least it can be used as a non-cryptographic hashing function for 128-bit integers... $\endgroup$
    – lyrically wicked
    Commented Apr 8, 2019 at 5:23
  • $\begingroup$ What are you planning to do with this? Suppose it's fast; what do you need it for then? ‘Hashing function’ doesn't narrow it down—that could mean any of umpteen different things. Are you using it for a hash table? For a message authentication code? For content-addressed storage? For error detection in a nonmalicious noisy channel? $\endgroup$
    – Squeamish Ossifrage
    Commented Apr 8, 2019 at 5:28

1 Answer 1

Reset to default
2
$\begingroup$

I may be missing some subtlety intended by the problem-setter, but the simple answer that satisfies the stated conditions, or damn near, is to just xor the words:

$$F = w_1 \oplus w_2 \oplus w_3 \oplus w_4$$

If we model any change to $w_i$ as xoring with a nonzero error term $e_i$, since xor is linear in $GF(2^n)$

$$F' = (w_1\oplus e_1)\oplus (w_2\oplus e_2)\oplus (w_3\oplus e_3)\oplus (w_4\oplus e_4) \\ = F \oplus (e_1\oplus e_2\oplus e_3\oplus e_4)$$

If only one of $e_i$ is nonzero, the net error is nonzero. If more than one of $e_i$ is nonzero, independently at random, the probability that the net error is zero is almost $2^{-32}$ -- excluding zero from some of the choices throws it off slightly, but I don't remember enough probability to compute exactly how.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, but a simple XOR lacks two basic cryptographic properties: sufficient diffusion of bits and non-linearity. It is possible to choose four different keys $(a, b, c, d)$ for an appropriate PRP $E$ and use $F(B) = E_a(w_1) \oplus E_b(w_2) \oplus E_c(w_3) \oplus E_d(w_4)$, but the problem is obvious: such functions make the performance absolutely unacceptable... $\endgroup$
    – lyrically wicked
    Commented Apr 8, 2019 at 5:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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