1
$\begingroup$

Do any streaming hash functions exist that provide the same result if the input is reversed?

That is to say, is there some hash function, $h$, such that:

$$ h(h(h(h(0, x_1), x_2), ...), x_n) = h(h(h(h(0, x_n), ...), x_2), x_1) $$

If this is impossible, why is it impossible?

I am interested in sending packets of constant size around a circuit in a network in both directions, having each node add its value to the hash and then, when the packets meet, compare the hash values.

$\endgroup$
1
  • $\begingroup$ @JörgWMittag, not a dup, because that question does not contain the requirement to be able to compute it in a streaming fashion. $\endgroup$
    – D.W.
    Dec 8, 2023 at 22:31

2 Answers 2

3
$\begingroup$

As stated, the problem is impossible (with a non-trivial hash function). Consider the case n=2, then you have that, for example,

$$h(h(0, 1), 2) = h(h(0, 2), 1)$$

That implies that

$$h(h(h(0, 1), 2), 3) = h(h(h(0, 2), 1), 3)$$

So the strings $1,2,3$ and $2,1,3$ are forced to have the same hash even if one is not the reverse of the other. A similar argument shows that any such hash function is not only reversal-independent, but in general permutation-independent, so it is equivalent to storing the multiset of characters of the input.

An alternative is to have a normal streaming hash function $h$ which is not reversal-independent, and then have a function $r$ that identifies the hashes of a string and its reverse. So the condition would become something like

$$ r(β„Ž(β„Ž(β„Ž(β„Ž(0,π‘₯_1),π‘₯_2),...),π‘₯_𝑛))=r(β„Ž(β„Ž(β„Ž(β„Ž(0,π‘₯_𝑛),...),π‘₯_2),π‘₯_1)) $$

And that is certainly possible with a reasonably strong hash function, as show by D.W.

$\endgroup$
2
  • $\begingroup$ Thank you! I'm struggling to understand how the last part would be possible in practice. Is $r$ basically a rainbow table? I.e. it involves knowing all the possible inputs to the hash function? $\endgroup$
    – Zaz
    Dec 10, 2023 at 0:37
  • $\begingroup$ D.W. provided an excellent example. The function h would return the pair (H(m), H(rev(m))) and then r(H(m), H(rev(m)) would just be the xor of both elements of the pair, therefore "forgetting" about the order. $\endgroup$ Dec 10, 2023 at 15:40
3
$\begingroup$

There are several polynomial-based hash functions $H$, where you can rapidly compute $H(m)$ or $H(\text{rev}(m))$ given $m$, and you can do both in a streaming fashion. See below for several candidates for $H$. Then, you can use

$$H'(m) = H(m) \oplus H(\text{rev}(m)),$$

and $H'$ will have the property you are looking for.

Rabin hash

For instance, consider the Rabin hash. Specifically, given a $n$-bit message $m=(m_0,\dots,m_{n-1})$, the hash is

$$H(m) = m_0 + m_1 x + \dots + m_{n-1} x^{n-1} \bmod p(x),$$

where $p(x)$ is an irreducible polynomial of degree $k$ over $GF(2)$. This is easy to compute in a streaming fashion via the recurrence

$$w_i = x w_{i-1} \bmod p(x), \qquad h_i = h_{i-1} + m_i w_i \bmod p(x).$$

Now $\text{rev}(m)=(m_{n-1},\dots,m_1,m_0)$, so

$$H(\text{rev}(x)) = m_{n-1} + m_{n-2} x + \dots + m_0 x^{n-1} \bmod p(x),$$

which can be computed in a streaming fashion with the recurrence

$$h_i = x h_{i-1} + m_i \bmod p(x).$$

Polynomial hash over the integers

A related scheme is to use the integers modulo $p$ (a prime). instead of the polynomials over $GF(2)$ modulo $p(x)$. Specifically, given a $n$-bit message $m=(m_0,\dots,m_{n-1})$, the hash is

$$H(m) = m_0 + m_1 a + \dots + m_{n-1} a^{n-1} \bmod p,$$

where $p$ is a prime number and $1<a<p$. This too can be computed in a streaming fashion, both for the message and for the reverse of the message, in the same manner as above. This can be made more efficient by breaking $m$ down into $n$ chunks, with each chunk of $c$ bits, such that $2^n<p$, and let $m_i$ be the $i$th chunk of $m$. For instance, each chunk might represent a byte or character of $m$.

Note that if you use chunks larger than a bit, then this assumes reversal means not "reversal as a bit-string" but "reversal as a sequence of characters". If you want one notion of reversal, but a different granularity for computing the hash, this can be arranged by with a little bit of additional arithmetic, but it's probably not worth the bother to work out the equations.

Buzhash

Another choice for $H$ is Buzhash. Let $h$ be some hash function that maps from characters to $k$-bit values. Define $\oplus$ to represent xor, and $a \lll b$ to represent circular left-rotate of $a$ by $b$ bit positions (I will assume that $b$ is implicitly taken modulo $l$). Given a $n$-character message $m=(m_0,\dots,m_{n-1})$, Buzhash is defined as

$$H(m) = (h(m_0) \lll n-1) \oplus (h(m_1) \lll n-2) \oplus \cdots \oplus (h(m_{n-2}) \lll 1) \oplus m_{n-1}.$$

This can be easily computed in a streaming fashion by

$$h_i = (h_{i-1} \lll 1) \oplus h(m_i).$$

Also $H(\text{rev}(m))$ can be easily computed in a streaming fashion by

$$h_i = h_{i-1} \oplus (m_i \lll i).$$

The same comments apply about the granularity of chunks.

$\endgroup$
2
  • $\begingroup$ Thank you for the very detailed answer! Apologies if my question was still not clear. $\endgroup$
    – Zaz
    Dec 10, 2023 at 0:38
  • $\begingroup$ This is the answer! $\endgroup$
    – kelalaka
    Dec 11, 2023 at 17:31

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.