1
$\begingroup$

Given $x$, a vector of $m$ distinct bit vectors of bit length $N$, I want to use an XOR-hash $h$ such that all $x_i$ collide to the same value.

I define an XOR hash $h$ which takes bit vector $q$ as input and performs an AND operation on each bit of $q$ with a bit vector $k_i$ of bit length $S$.

$h(q) = (k_1.q_1)\oplus(k_2.q_2)\oplus...\oplus(k_N.q_N)$

The "AND" dot operation $a.b$ takes bit vector $a$ and boolean/bit $b$ and returns ($a$ if $b$ else 0).

Here $k$ is a vector of bit vectors, and my goal is to find $k$ such that for some constant bit vector $y$ of bit length $S$, $h(x_i) = y$ for all $i$.

Section 4.3 in this paper describes this hash function. http://www.mathcs.emory.edu/~whalen/Hash/Hash_Articles/IEEE/Efficient%20hardware%20hashing%20functions%20for%20high%20performance%20computers.pdf

It is my understanding that when you try to XOR-hash a bit vector of size $N$ to a bit vector of size $S$, there will be $2^{N-S}$ collisions. I want to choose $k$ so that all $m$ bit vectors in $x$ hash to the same value $y$.

For example, take $N=15$, and $m=200$.

I am trying to round $m$ to the next power of 2. In this case, I would like to round 200 to 256 and then have $2^{N-S}=256=2^8$, so that $N-S=8$ and thus $S=7$.

In other words, I can now XOR-hash from a $N=15$-bit space to a $S=7$-bit space with all the $m=200$ inputs colliding to the same output. I understand that there are an additional 56 numbers which are not accounted for. We choose any bit vector of size 15 which is not in $x$.

How do I go about finding $k$ deterministically (or closed-loop fashion) to make all the hashes collide?

$\endgroup$
  • $\begingroup$ Not exactly a clear question. What is $N(15)$? do you mean the number of bit o each $m$ us 15? then you should use $N=15$. Dou you hash $m_i$ with a cryptographic hash function then x-or the output? $$\bigoplus_{m=1}^{200} hash(m_i)$$ $\endgroup$ – kelalaka Jul 5 at 7:55
  • $\begingroup$ @kelalaka . Thanks for the advice. I have corrected the post accordingly. I am trying to generate a hash function which outputs the same value for all the m values. In other words $hash(m_0)$ = $hash(m_1)$ =$hash(m_{200})$ $\endgroup$ – Acinonyx Jul 5 at 11:38
  • $\begingroup$ If the hash is a Cryptographic hash than it is an impossible task. However, once you find a collision, a multi-collision is much easier. $\endgroup$ – kelalaka Jul 5 at 11:54
  • 1
    $\begingroup$ Explain what you mean by "using an XOR hash". XOR is not a hash algorithm. You can use XOR as one of operations when calculating hash. But describe what else are you doing to calculate hash. $\endgroup$ – mentallurg Jul 5 at 12:01
  • $\begingroup$ @mentallurg I have added more detail to the question. I think this is call XOR AND or maybe it is called AND XOR. Cannot remember the full name. $\endgroup$ – Acinonyx Jul 5 at 14:02

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.