Page 2 of 2 FirstFirst 12
Results 31 to 44 of 44

Thread: Improving xxHash

  1. #31
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    i was wrong - the tramsformation is really reversible. if we fix higher dword of a, the lower dword of a is xored with fixed value, so each of 2^32 possible values are mapped to different result. since the mapping doesn't change higher dword at all, this means that all 2^64 values can be a result. reverse operation is the same as direct one, i.e. x ^ ((x >> 32) >> (x >> 60))

    i even think that it may be improved to x ^ ((x >> 16) >> (x >> 59)) or at least x ^ ((x >> 24) >> (x >> 60))

    PS: i see that your also added this proof
    Last edited by Bulat Ziganshin; 10th January 2017 at 19:03.

  2. #32
    Member
    Join Date
    Jan 2017
    Location
    Selo Bliny-S'edeny
    Posts
    24
    Thanks
    7
    Thanked 10 Times in 8 Posts

    t1ha - Fast Positive Hash

    Recently Leo Yuriev published the "t1ha" hash function, which also goes by the name of Fast Positive Hash. It outperforms xxHash in terms of speed, while also passing SMHasher tests. Like xxHash, it has a portable loop which does 4 integers at a time. Unlike xxHash, which uses the same update() routine for each integer, t1ha implements a clever round() mechanism which combines both bit diffusion and mixing with the internal state. It uses only two multiplications per round.

    Code:
          uint32_t w0 = fetch32_le(v + 0);
          uint32_t w1 = fetch32_le(v + 1);
          uint32_t w2 = fetch32_le(v + 2);
          uint32_t w3 = fetch32_le(v + 3);
    
          uint32_t c02 = w0 ^ rot32(w2 + c, 11);
          uint32_t d13 = w1 + rot32(w3 + d, 17);
          c ^= rot32(b + w1, 7);
          d ^= rot32(a + w0, 3);
          b = q1 * (c02 + w3);
          a = q0 * (d13 ^ w2);
    where a, b, c and d is the internal state, and q0 and q1 are constants.

    I wonder how this approach fares against the mixing introduced in the ZZH32 round() routine.

  3. #33
    Member
    Join Date
    Nov 2015
    Location
    ?l?nsk, PL
    Posts
    81
    Thanks
    9
    Thanked 13 Times in 11 Posts
    Quote Originally Posted by svpv View Post
    Recently Leo Yuriev published the "t1ha" hash function, which also goes by the name of Fast Positive Hash. It outperforms xxHash in terms of speed, while also passing SMHasher tests. Like xxHash, it has a portable loop which does 4 integers at a time. Unlike xxHash, which uses the same update() routine for each integer, t1ha implements a clever round() mechanism which combines both bit diffusion and mixing with the internal state. It uses only two multiplications per round.

    Code:
          uint32_t w0 = fetch32_le(v + 0);
          uint32_t w1 = fetch32_le(v + 1);
          uint32_t w2 = fetch32_le(v + 2);
          uint32_t w3 = fetch32_le(v + 3);
    
          uint32_t c02 = w0 ^ rot32(w2 + c, 11);
          uint32_t d13 = w1 + rot32(w3 + d, 17);
          c ^= rot32(b + w1, 7);
          d ^= rot32(a + w0, 3);
          b = q1 * (c02 + w3);
          a = q0 * (d13 ^ w2);
    where a, b, c and d is the internal state, and q0 and q1 are constants.

    I wonder how this approach fares against the mixing introduced in the ZZH32 round() routine.
    Interesting.
    2 multiplications, not much. It tries to make up with other operations.
    2 injection points for each word.
    Avalanching between state words. It has 2 pairs of words in the state with avalanching within pair, but not between pairs. Better than xxhash, but not great. I wonder why is it so, because there seems to be no speed penalty for changing it. And there's a different algorithm for each pair. Maybe it's a bug?

    Anyway, it would take some actual qa to tell how strong it is.

    Added:
    Let's assume for a while that having different algorithms for different input words is intentional.
    It causes the hash to be about as strong as the weaker of the algorithms.

  4. #34
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    t1ha_32le is 1.5 bytes/cycle, that's slower than xxh32.

    t1ha employs 64-bit operations and 3 bpc that's slower than xxh64/spooky

  5. #35
    Member erthink's Avatar
    Join Date
    Sep 2018
    Location
    Moscow
    Posts
    1
    Thanks
    0
    Thanked 4 Times in 1 Post
    Quote Originally Posted by Bulat Ziganshin View Post
    t1ha_32le is 1.5 bytes/cycle, that's slower than xxh32.

    t1ha employs 64-bit operations and 3 bpc that's slower than xxh64/spooky
    On modern processors t1ha is faster than xxHash. This is easy to check by test.
    For example:
    Code:
    $ git clone https://github.com/leo-yuriev/t1ha.git
    $ cd t1ha
    $ make check
    ...
    Preparing to benchmarking...
     - running on CPU#0
     - use RDPMC_40000001 as clock source for benchmarking
     - assume it cheap and stable
     - measure granularity and overhead: 53 cycle, 0.0188679 iteration/cycle
    
    Bench for tiny keys (7 bytes):
    t1ha2_atonce            :     17.266 cycle/hash,  2.467 cycle/byte,  0.405 byte/cycle,  1.216 Gb/s @3GHz 
    t1ha2_atonce128*        :     34.344 cycle/hash,  4.906 cycle/byte,  0.204 byte/cycle,  0.611 Gb/s @3GHz 
    t1ha2_stream*           :     80.750 cycle/hash, 11.536 cycle/byte,  0.087 byte/cycle,  0.260 Gb/s @3GHz 
    t1ha2_stream128*        :    102.000 cycle/hash, 14.571 cycle/byte,  0.069 byte/cycle,  0.206 Gb/s @3GHz 
    t1ha1_64le              :     19.234 cycle/hash,  2.748 cycle/byte,  0.364 byte/cycle,  1.092 Gb/s @3GHz 
    t1ha0                   :     15.000 cycle/hash,  2.143 cycle/byte,  0.467 byte/cycle,  1.400 Gb/s @3GHz 
    xxhash32                :     18.672 cycle/hash,  2.667 cycle/byte,  0.375 byte/cycle,  1.125 Gb/s @3GHz 
    xxhash64                :     25.203 cycle/hash,  3.600 cycle/byte,  0.278 byte/cycle,  0.833 Gb/s @3GHz 
    StadtX                  :     20.219 cycle/hash,  2.888 cycle/byte,  0.346 byte/cycle,  1.039 Gb/s @3GHz 
    HighwayHash64_pure_c    :    507.500 cycle/hash, 72.500 cycle/byte,  0.014 byte/cycle,  0.041 Gb/s @3GHz 
    HighwayHash64_portable  :    493.250 cycle/hash, 70.464 cycle/byte,  0.014 byte/cycle,  0.043 Gb/s @3GHz 
    HighwayHash64_sse41     :     67.938 cycle/hash,  9.705 cycle/byte,  0.103 byte/cycle,  0.309 Gb/s @3GHz 
    HighwayHash64_avx2      :     57.125 cycle/hash,  8.161 cycle/byte,  0.123 byte/cycle,  0.368 Gb/s @3GHz 
    
    Bench for large keys (16384 bytes):
    t1ha2_atonce            :   3561.000 cycle/hash,  0.217 cycle/byte,  4.601 byte/cycle, 13.803 Gb/s @3GHz 
    t1ha2_atonce128*        :   3566.000 cycle/hash,  0.218 cycle/byte,  4.595 byte/cycle, 13.784 Gb/s @3GHz 
    t1ha2_stream*           :   3661.000 cycle/hash,  0.223 cycle/byte,  4.475 byte/cycle, 13.426 Gb/s @3GHz 
    t1ha2_stream128*        :   3685.000 cycle/hash,  0.225 cycle/byte,  4.446 byte/cycle, 13.338 Gb/s @3GHz 
    t1ha1_64le              :   3546.000 cycle/hash,  0.216 cycle/byte,  4.620 byte/cycle, 13.861 Gb/s @3GHz 
    t1ha0                   :   1267.000 cycle/hash,  0.077 cycle/byte, 12.931 byte/cycle, 38.794 Gb/s @3GHz 
    xxhash32                :   8198.000 cycle/hash,  0.500 cycle/byte,  1.999 byte/cycle,  5.996 Gb/s @3GHz 
    xxhash64                :   4120.000 cycle/hash,  0.251 cycle/byte,  3.977 byte/cycle, 11.930 Gb/s @3GHz 
    StadtX                  :   3659.000 cycle/hash,  0.223 cycle/byte,  4.478 byte/cycle, 13.433 Gb/s @3GHz 
    HighwayHash64_pure_c    :  49100.911 cycle/hash,  2.997 cycle/byte,  0.334 byte/cycle,  1.001 Gb/s @3GHz 
    HighwayHash64_portable  :  43949.776 cycle/hash,  2.682 cycle/byte,  0.373 byte/cycle,  1.118 Gb/s @3GHz 
    HighwayHash64_sse41     :   6407.000 cycle/hash,  0.391 cycle/byte,  2.557 byte/cycle,  7.672 Gb/s @3GHz 
    HighwayHash64_avx2      :   4448.000 cycle/hash,  0.271 cycle/byte,  3.683 byte/cycle, 11.050 Gb/s @3GHz

  6. Thanks (4):

    Bulat Ziganshin (16th September 2018),JamesB (21st September 2018),Jyrki Alakuijala (16th September 2018),Mike (16th September 2018)

  7. #36
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    976
    Thanks
    266
    Thanked 350 Times in 221 Posts
    Highwayhash has a design compromise that makes it difficult to reverse it and consequently no practical attack has yet been proposed against it. For this one needs to extract more than just 64 bits of course, but that is just a change in the end phase.

    Other fast hashes let the input control their full internal state, which makes them trivial to reverse.

  8. #37
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    Other fast hashes let the input control their full internal state, which makes them trivial to reverse.
    can you please show us how to reverse any popular hash successfully passing smhasher, aside of already known xxhash32/murmur3a attacks?

  9. #38
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    976
    Thanks
    266
    Thanked 350 Times in 221 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    can you please show us how to reverse any popular hash successfully passing smhasher, aside of already known xxhash32/murmur3a attacks?
    Is t1ha a good target?

  10. #39
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    absolutely

  11. #40
    Member
    Join Date
    Apr 2019
    Location
    Home
    Posts
    7
    Thanks
    4
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    reverse any popular hash
    What does "reverse" mean in this context?

  12. #41
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    Dernm, it means - propose DDoS attack against server using considered hash with unknown seed. Highwayhash is an attempt to provide faster alternative to SipHash: https://en.wikipedia.org/wiki/Murmur...ulnerabilities

    some more details at https://131002.net/siphash/#at

  13. Thanks:

    DernmIl (2nd April 2019)

  14. #42
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    976
    Thanks
    266
    Thanked 350 Times in 221 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    Dernm, it means - propose DDoS attack against server using considered hash with unknown seed. Highwayhash is an attempt to provide faster alternative to SipHash: https://en.wikipedia.org/wiki/Murmur...ulnerabilities

    some more details at https://131002.net/siphash/#at
    The HighwayHash repository contains a fast implementation of SipHash, but the HighwayHash itself is still faster and more versatile.

    HighwayHash is a cryptographic hash using a large sponge, whereas SipHash is a keyed hash function. Any cryptographic hash can be used as a keyed hash function, but not the other way around.

  15. #43
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    SipHash is 'cryptographically strong' keyed hash developed by one of the most recognized cryptographers specifically to deal with DDoS attacks.

    HighwayHash is a cryptographic hash developed by non-cryptographers and never tested by anyone but the authors.

    Your mileage may vary. For me,
    HighwayHash is just non-crypto hash using novel data shuffling technique.

  16. #44
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    976
    Thanks
    266
    Thanked 350 Times in 221 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    For me, HighwayHash is just non-crypto hash using novel data shuffling technique.
    For everyone sensible, every new crypto algorithm is a non-crypto algorithm for the first five years.

Page 2 of 2 FirstFirst 12

Similar Threads

  1. improving brotli
    By inikep in forum Data Compression
    Replies: 6
    Last Post: 18th November 2015, 22:45
  2. [Java] Improving efficiency of arithmetic decompression
    By rhulcomputerscience in forum Data Compression
    Replies: 1
    Last Post: 17th September 2015, 19:31
  3. Improving CM state machines
    By Mat Chartier in forum Data Compression
    Replies: 3
    Last Post: 3rd July 2013, 17:54
  4. Improving LZ78/LZW?
    By RichSelian in forum Data Compression
    Replies: 7
    Last Post: 19th September 2011, 19:05
  5. Improving RC4 (MC1 cipher proposal)
    By encode in forum The Off-Topic Lounge
    Replies: 14
    Last Post: 5th August 2010, 21:57

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •