The collision handling code in KkrtPsiSender seems not working.

The cuckoo hash of KKRT needs to produce 3 hash locations for each input, these locations may collide. So, the function hashItems of KkrtPsiSender contains some codes for dealing the collisions. The dealing logic is as follows. If the itemIdx input got a collision, then the position perm[itemIdx] of the array myMaskBuff will fill with junk data.

// if we got a collision, then fill the final mask locations with junk data
prngs[0].get(masks.data() + (perm[itemIdx0] * mNumHashFunctions + 1) * masks.stride(), c01 * masks.stride());
prngs[1].get(masks.data() + (perm[itemIdx1] * mNumHashFunctions + 1) * masks.stride(), c11 * masks.stride());
prngs[2].get(masks.data() + (perm[itemIdx2] * mNumHashFunctions + 1) * masks.stride(), c21 * masks.stride());
prngs[3].get(masks.data() + (perm[itemIdx3] * mNumHashFunctions + 1) * masks.stride(), c31 * masks.stride());
prngs[4].get(masks.data() + (perm[itemIdx4] * mNumHashFunctions + 1) * masks.stride(), c41 * masks.stride());
prngs[5].get(masks.data() + (perm[itemIdx5] * mNumHashFunctions + 1) * masks.stride(), c51 * masks.stride());
prngs[6].get(masks.data() + (perm[itemIdx6] * mNumHashFunctions + 1) * masks.stride(), c61 * masks.stride());
prngs[7].get(masks.data() + (perm[itemIdx7] * mNumHashFunctions + 1) * masks.stride(), c71 * masks.stride());

However, ignoring the syntax mistake that the hashItems has not used the correct c02~c72, these codes for dealing with collisions seem still not working.

The reason is that during the encoding part, the encoding codes as follow will try to encode the inputIdx = mPermute[i] input into location i of array myMaskBuff.

// lets check a random item to see if it can be encoded. If so,
// we will write this item's encodings in the myMaskBuff at position i.
auto inputIdx = mPermute[i];

// for each hash function, try to encode the item.
for (u64 h = 0; h < mParams.mNumHashes; ++h)
{
    auto& bIdx = binIdxs(inputIdx, h);

    // if the bin index is less than r, then we have received
    // the correction and can encode it
    if (bIdx < r)
    {
        // write the encoding into myMaskBuff at position  i, h
        auto encoding = myMaskBuff.data() + (i * mParams.mNumHashes + h) * myMaskBuff.stride();
        mOtSender->encode(bIdx, &inputs[inputIdx], encoding, myMaskBuff.stride());

        // make this location as already been encoded
        bIdx = -1;
    }
}

This permutation logic of encoding is different from the permutation logic used to fill junk data in hashItems, one is using perm[itemIdx](itemIdx is index of input) and the other is using mPermute[i](i is the current location of myMaskBuff), and will result in the junk data being rewritten while the actual location of the collision will not be filled.

Here is a toy example

Assuming that the permutation array is perm[3]=9, perm[9]=19, perm[19]=7, and the 9th input gots a collision.
Then, in the hashItems function, the location myMaskBuff[perm[9]=19] will be filled with junk data.
Then, during the encoding part, only when i is equal to 3, the inputIdx used for encoding will equal to perm[3]=9. In other words, the 9th input where the collision occurred will be encoded to the myMaskBuff[3]. However, in the subsequent code, only the positions where no collisions occurred will be encoded, and the positions where collisions occurred will be ignored. This is reasonable, because the collision is expected to have been handled by filling myMaskBuff [19] with junk data, and this is where the problem lies, the filled junk data is actually in a wrong location.
When i equals 19, the inputIdx used for encoding will be equal to perm[19]=7, then the junk data filled in myMaskBuff[19] will be rewritten by encoding the 7th input, and the collision handling code in the hashItems is totally disabled.

We also run a test using command line ./frontend.exe -kkrt -n 1000000, and following is our observation.

When i is equal to 209718 or 474447, collision is found. And the inputIdx=mPermute[i] is equal to 172890 and 42021.
We output myMaskBuff[209718] and myMaskBuff[474447] into console before encoding part, and found that all of them are initially zero as follow.
After the encoding part, we output myMaskBuff[209718] and myMaskBuff[474447] into console again, and found that the first and second location is successfully encoded into mask, however, the third location is still zero. This means that collisions are not handled, as we described in the toy example.

Overall, because the collision handling code in hashItems places the junk data in the wrong position, and the encoding part ignores the collisions, the myMaskBuff that send to the receiver contains zero values, which might leak the information of collisions.

osu-crypto / libPSI

The collision handling code in KkrtPsiSender seems not working. #57