Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Hmm, Meow fails the TwoLongNeighbors test. More information on this test here: https://github.com/hmakholm/smhasher/blob/master/src/LongNei...

  [[[ Keyset 'TestLongNeighbors' Tests ]]]

  Looking for 2-bit collisions in the last 2400 bits.
  Looking for 4-bit collisions in the last 2048 bits.
  Looking for 6-bit collisions in the last 160 bits.
  Trying bases of length 10 to 300, 5 of each length.
  ......[16]...............[32]............... [48]...............[64].

  Among 285 tested bases, we expected 4.25749e-06 bads. 
  Actually there were 5.
  The most striking collision has surprise score 3.52004e+06 and length 46 bytes:
  000: BD 8D 12 8C FB EE 75 2E 17 80 4E 26 8C E7 75 94 DA EF 12 8C 95 CA 91 0D
  018: 08 BD 8D 5F F2 78 FF 64 88 27 88 3F 8E 8F CE FC E2 8A 99 CE 2B E3
                  ^D2^                 ^7F^              ^18^     ^0B^
  The hashes are length 8 bytes:
  000: 35 C1 E6 5B 6B 66 C7 28
  *********FAIL*********


I can make Meow pass the LongNeighbors test by doubling the number of AES rounds on each pass.

The original Meow algo:

    while(Len >= 64)
    {
        S0 = Meow128_AESDEC_Mem(S0, Source);
        S1 = Meow128_AESDEC_Mem(S1, Source + 16);
        S2 = Meow128_AESDEC_Mem(S2, Source + 32);
        S3 = Meow128_AESDEC_Mem(S3, Source + 48);

        Len -= 64;
        Source += 64;
    }
The modified algo:

    while(Len >= 64)
    {
        S0 = Meow128_AESDEC_Mem(S0, Source);
        S0 = Meow128_AESDEC_Mem(S0, Source);
        S1 = Meow128_AESDEC_Mem(S1, Source + 16);
        S1 = Meow128_AESDEC_Mem(S1, Source + 16);
        S2 = Meow128_AESDEC_Mem(S2, Source + 32);
        S2 = Meow128_AESDEC_Mem(S2, Source + 32);
        S3 = Meow128_AESDEC_Mem(S3, Source + 48);
        S3 = Meow128_AESDEC_Mem(S3, Source + 48);

        Len -= 64;
        Source += 64;
    }
(also changed the partial rounds, but this is not shown here)

This doesn't change it's performance that much, maybe 1 or 2 extra CPU cycles. My i9 CPU must be able to run these extra rounds in parallel... I do have hyperthreading disabled, if that matters.

Update:

Ah, it does cause the bulk speed test to be 50% of the original (48MiB vs 24Mib). The small key test only adds 1/2/3/4 extra AES instructions since they are manipulating 16 bytes at a time. It looks like this is only taking a cycle.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: