Comments (10)
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).
from t1ha.
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.
from t1ha.
@Bulat-Ziganshin, конечно я не имел в виду повторение аналогичных "граблей". Более того, я вижу определенную проблему в функциях подобных NH из UMAC.
Еще весной я сделал несколько экспериментов в направлении следующей версии t1ha, но они слишком сырые и у меня пока нет времени для доведения этих наработок до релиза.
from t1ha.
что-то я не понимаю. 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]
from t1ha.
Хмм, @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-битном умножении.
from t1ha.
- скорость будет ограничена двумя LD/такт у всех известных x86, т.е. 4 bpc
uint64_t(M[i*2]) + K[i*2]
можно записать какM[i*2] + K[i*2]
вообще, мне такие хеши кажутся менее интересными потому что в обычных смена одного бита лавинообразно меняет всё последующее состояние, а в этих - эффект ограничивается одним слагаемым в сумме. если же мы при этом теряем ещё и скорость...
from t1ha.
скорость будет ограничена двумя 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-сумма (которая тебе не-нравится). Т.е. тогда тебе не должен нравится собственный "фарш"?
from t1ha.
Все используемые операции ассоциативны, поэтому для суперскалярного 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-алгоритмы быстрее криптохешей. Почему? Потому что они опираются на неизвестный атакующему ключ, и именно случайный выбор этого неизвестного ключа даёт им гарантии оптимального числа коллизий - в среднем по всем ключам. Однако как только мы фиксируем ключ, само понятие универсальности теряет смысл и мы теряем какие-либо гарантии вообще, зато сталкиваемся с тем, что при выборе данной конкретной функции у нас есть очевидные зависимости между входными данными и значением хеш-функции. Заметь, что такие очевидные завиисимости будут при любом выборе конкретной хеш-функции из семейства, просто каждый раз разные. Для семейства в целом это ОК, а для конкретной функции - нет.
from t1ha.
... Все используемые операции ассоциативны, поэтому для суперскалярного 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.
from t1ha.
Obsoleted by #36
from t1ha.
Related Issues (20)
- Some strange issue with t1ha2_update HOT 37
- Add explicit description of T1HA_USE_FAST_ONESHOT_READ at the top of t1ha.h
- Streaming API does not match "atonce" API. HOT 3
- PERFORMANCE COMPARISON (this is not a bug or an issue) HOT 3
- Wrong x86 code generated by Microsoft Visual Studio 2015
- compatibility testing for implementation HOT 2
- Hello, can we contact? HOT 1
- Bus error on ARMv7 with Clang 8 HOT 3
- valgrind 'invalid read of size 8' in t1ha1 and t1ha2 HOT 1
- read_unaligned error HOT 5
- Работа со строками HOT 5
- Can't compile on virtualized FreeBSD 12.1
- Notes about t1ha_v3 design HOT 6
- Proxy for eBay payment HOT 2
- Проверка NIST тестом. HOT 4
- Enable T1HA0_AESNI_AVAILABLE for AES Supported ARM64 Processor HOT 1
- ARM64 AES acceleration? HOT 4
- __ImageBase in t1ha-static HOT 3
- SIGBUS due to unaligned access on armv7 (GCC 9) HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from t1ha.