Outperform wyhash

[erthink]

Currently wyhash outperforms t1ha.
Nevertheless I think the next version of t1ha will be even faster.

[erthink]

russian:
В последнее время, некоторые друзья и знакомые спрашивают меня: как ты мог пропустить такое простое и очевидное решение, которое нашел @wangyi-fudan?

Короткий ответ — я не знаю.
Насколько я помню, я пробовал массу подобных ходов, но их результат был хуже текущей версии t1ha. Более того, у меня буквально дежавю в отношении mul-xor конструкций.

Использование ядра конгруэнтного генератора является довольно очевидным подходом, и многие (в том числе и я) применяли в подобных условиях его более 20 лет назад.
Тем не менее, @wangyi-fudan показал код, который в актуальных условиях работает быстрее. Это несколько неожиданно (и даже немного обидно), но в любом случае это шаг в перед и стимул для меня сделать еще лучше. В частности, для лучших свойств качества и даже необратимости (контролируемой не-инъективности).

english:
Recently, some friends and acquaintances have been asking me: how could you miss such a simple and obvious solution that @wangyi-fudan found?

The short answer is - I don't know.
As far as I remember, I tried a lot of similar somersaults, but their result was worse than the current version of t1ha. Moreover, I have literally deja vu regarding mul-xor designs.

The use of a congruent generator core is a fairly obvious approach, and many (including myself) used it under similar conditions more than 20 years ago.
Nevertheless, @wangyi-fudan showed the code that works faster in current conditions. This is somewhat unexpected (and even it's a shame that so simply), but in any case it is a step forward and an incentive for me to do even better. In particular, for better quality properties and even irreversibility (controlled non-injectivity).

[Bulat-Ziganshin]

This formula

_wymum(_wyr64(p)^_wyp1,_wyr64(p+8)^_wyp2)

means that when p[0]==_wyp1, then p[1] value is completely ignored. Do you really like such construct?

It's used by UMAC/FARSH/XXH3:

• FARSH is 32-bit hash that suffers from the same effect. It passed SMHasher, and with AVX2 reached speed 16 bpc.
• UMAC combines larger hashes from 32-bit chunks, each using different constant table, mitigating the effect.
• XXH3 mitigates the effect by extra add operation.

[erthink]

@Bulat-Ziganshin, конечно я не имел в виду повторение аналогичных "граблей". Более того, я вижу определенную проблему в функциях подобных NH из UMAC.

Еще весной я сделал несколько экспериментов в направлении следующей версии t1ha, но они слишком сырые и у меня пока нет времени для доведения этих наработок до релиза.

[Bulat-Ziganshin]

что-то я не понимаю. wyhash использует ту же функцию, тогда почему ты хочешь её скопировать? или речь о копировании других идей из этого хеша?

    H += (uint64_t(M[i*2]) + K[i*2]) * (uint64_t(M[i*2+1]) + K[i*2+1]);

в этом коде та же самая порблема - если (M[i*2]) + K[i*2])==0, то мы игнорируем значение M[i*2+1]

[erthink]

Хмм, @Bulat-Ziganshin, я точно не собирался ничего копировать (смысла нет и не красиво).
Если такое можно подумать исходя из какого-то текста, то подскажи где, я поправлю.

в этом коде та же самая порблема - если (M[i2]) + K[i2])==0, то мы игнорируем значение M[i*2+1]

Нет, это не так. Следует обратить чуть больше внимания на детали.
В массиве M[] значения 32-битные, но в uint64_t(M[i*2]) + K[i*2] сложение будет 64-битное и далее 64-битное умножение. Поэтому переполнения и нуля тут никогда не будет (при ненулевых значениях в K[]).

Кроме этого, используя 64-битные значения для K[] и выбирая их должным образом можно получить гарантированно неплохой лавинный эффект даже при обычном (не широком) 64-битном умножении.

[Bulat-Ziganshin]

1. скорость будет ограничена двумя LD/такт у всех известных x86, т.е. 4 bpc
2. uint64_t(M[i*2]) + K[i*2] можно записать как M[i*2] + K[i*2]

вообще, мне такие хеши кажутся менее интересными потому что в обычных смена одного бита лавинообразно меняет всё последующее состояние, а в этих - эффект ограничивается одним слагаемым в сумме. если же мы при этом теряем ещё и скорость...

[erthink]

скорость будет ограничена двумя LD/такт у всех известных x86, т.е. 4 bpc

Я бы считал иначе. Все используемые операции ассоциативны, поэтому для суперскалярного CPU реальным ограничением должна быть производительность "Execution units". Соответственно многое зависти от раскладки алгоритма в "тетрис" из инструкций.

uint64_t(M[i2]) + K[i2] можно записать как M[i2] + K[i2]

Конечно, при условии, что K[] 64-битный массив. Однако, практика показывает, что большинство наблюдателей не замечают uint64_t в объявлении K. Поэтому я добавил явное (но избыточное) преобразование в 64-битное значение.

---

вообще, мне такие хеши кажутся менее интересными потому что в обычных смена одного бита лавинообразно меняет всё последующее состояние, а в этих - эффект ограничивается одним слагаемым в сумме. если же мы при этом теряем ещё и скорость...

В MMH нет обсуждаемых проблем, там был mod 4294967311 (2^32+15) и простыми выкладками показано что "всё хорошо" (но именно для 32-битного результата после mod 4294967311).

В той же работе вскользь описана NMH с тем-же mod 4294967311. Но если присмотреться: проблема нулей не упомянута, нет замечания о 64-битных сложении, но есть примечание "вдвое быстрее".

В UMAC с NH пошли еще дальше - резонно выкинули модуль простого числа (так как 64-битный результат идет в SHA1 или POLY) и явно перешли на "узкое сложение". Тут логика авторов мне не совсем понятна, в том числе в близкой работе (может я что-то упускаю?). Исследуются и доказывается масса всего вокруг, но как-бы не замечается проблема игнорирования данных из-за получения нулей при сложении. Точнее говоря, проблема сводится/прячется в оценку вероятности коллизий, уровень которых приемлем "в среднем по больнице".

У меня ощущение что (например) где-то потерялось примечания, о "циклическом" сложении с добавлением переноса (т.е. вместо 0 будет 1), либо это какой-то умышленный изъян. Т.е. совершенно очевидно, что зная часть ключа и не зная Nonce можно генерировать сообщения в которых HMAC не будет зависеть от некоторых 32-битных слов...

С другой стороны, там есть рекомендация "для умных" использовать "Toeplitz construction" (хешировать не-единожды со сдвигом ключа), что устраняет проблему. Однако, в RFC4418 это не попало.

Так вот, @Bulat-Ziganshin, для меня несколько неожиданно твое высказывание "такие хеши кажутся менее интересными", так как:

• в MMH не проблем для 32-битного результата, в NMH тоже нет, если считать сложение 64-битным.
• NH тоже "delta-universal" если забыть про проблему нулей, а результат подавать в другую хеш-функцию (т.е. результат NH не должен использоваться без отбеливания/перемешивания).
• таким образом, нет проблем, если забыть о нулях в NH и остальное делать правильно.

При этом, в твоём FARSH-е есть "отбеливание" (как на уровне блоков, так и финальное), но в ядре проблема нулей и без-лавинная NH-сумма (которая тебе не-нравится). Т.е. тогда тебе не должен нравится собственный "фарш"?

[Bulat-Ziganshin]

Все используемые операции ассоциативны, поэтому для суперскалярного CPU реальным ограничением должна быть производительность "Execution units".

смотри - этот цикл обрабатывает 8 байт входных данных и для этого загружает 4 значения. Во всех существующих x86 cpu есть от силы два Load engine, поэтому этот цикл будет выполняться два такта.

Однако, практика показывает, что большинство наблюдателей не замечают uint64_t в объявлении K.

я наоборот привык к конструкциям вида u64(a)*b, поэтому твой код автоматом прочёл как длинное сложение 32-битных чисел ))

Т.е. тогда тебе не должен нравится собственный "фарш"?

именно. Поэтому я его забросил и перешёл к разработке zzHash: Bulat-Ziganshin/FARSH#6

Далее, термины типа "всё хорошо" дезориентируют. Дело в том, что есть множество разных недостатков, разных целей и даже разных начальных условий. То что хорошо для MAC-алгоритмов - необязательно хорошо для нас (в обратную сторону это очевидно). Надо говорить конкретно что хорошо и что плохо в каждом алгоритме.

зная часть ключа и не зная Nonce

дело в том, что этот ключ (массив, передаваемый в NH) генерится по значению Nonce, например AES(Nonce), AES(Nonce+1).... Таким образом, атакующий ключа не знает и вероятность того что какое-то data[i] позволит игнорировать значение data[i+1] равна вероятности того, что хеш вообще случайно совпадёт.

В целом, авторы статей о MAC говорят о collision probability и universality, чего нам совершенно недостаточно. Для нас важнее коллизии на "похожих" входных значениях и smhasher - это как раз генератор таких значений.

Например, MMH возвращает ноль на последовательности нолей любой длины. Для неё это приемлемо, поскольку вероятность таких совпадений в мире, где все значения полагаются одинаково вероятными, мала. Для нас же это особый, достаточно вероятный случай, и нам важно чтобы таких коллизий не было. Поэтому farsh без постобработки проваливает часть тестов smhasher, а crc32 которая afair тоже как-то универсальная, проваливает 5 из 10 тестов.

Ну и в целом - MAC-алгоритмы быстрее криптохешей. Почему? Потому что они опираются на неизвестный атакующему ключ, и именно случайный выбор этого неизвестного ключа даёт им гарантии оптимального числа коллизий - в среднем по всем ключам. Однако как только мы фиксируем ключ, само понятие универсальности теряет смысл и мы теряем какие-либо гарантии вообще, зато сталкиваемся с тем, что при выборе данной конкретной функции у нас есть очевидные зависимости между входными данными и значением хеш-функции. Заметь, что такие очевидные завиисимости будут при любом выборе конкретной хеш-функции из семейства, просто каждый раз разные. Для семейства в целом это ОК, а для конкретной функции - нет.

[erthink]

... Все используемые операции ассоциативны, поэтому для суперскалярного CPU реальным ограничением должна быть производительность "Execution units".

смотри - этот цикл обрабатывает 8 байт входных данных и для этого загружает 4 значения. Во всех существующих x86 cpu есть от силы два Load engine, поэтому этот цикл будет выполняться два такта.

Угу. После Nehalem именно так (ранее был один read-port). Собственно я ведь тоже само писал, только в более широкой формулировке и без привязки к x86. На других архитектурах узким местом может стать умножение и т.д.

именно. Поэтому я его забросил и перешёл к разработке zzHash: Bulat-Ziganshin/FARSH#6

О, теперь буду знать, и возьмусь за yyHash ;)

зная часть ключа и не зная Nonce

дело в том, что этот ключ (массив, передаваемый в NH) генерится по значению Nonce

Видимо у меня (было) какое-то ассоциативное наложение по поводу Nonce из других мест, т.е. я считал именно как написал (а сейчас глянул внимательно и увидел).

В целом, авторы статей о MAC говорят о collision probability и universality, чего нам совершенно недостаточно.
....

Собственно я полностью с тобой согласен. В том числе поэтому "ноль от нулей" в случае MMH для меня выглядит приемлемым. Но вот вероятность полного игнорирования данных в NH/UMAC - уже как-бы за гранью, не говоря о XXH3. Причем ведь эти "черти" сами написали о "Toeplitz construction", а потом забили. Тем не менее, как писал, всё это IMHO.

[erthink]

Obsoleted by #36