Варианты t1ha, переименования для ясности и порядка

[erthink]

Варианты t1ha, переименования для ясности и порядка

[svpv]

Мужчины, здрасьте. Я ищу 96-128-битный хеш для идентификации элементов. Обратимость меня не очень беспокоит (т.е. пусть можно искусственно вызвать коллизию проще, чем полным перебором). В остальном коллизий быть не должно, т.е. вероятность коллизий на "реальных данных" должна быть близка к той, которая указана в самой левой колонке https://en.wikipedia.org/wiki/Birthday_problem#Probability_table

В частности, есть две практические задачи.

1. 96-битный хеш для идентификации set-версий. В rpm есть такие set-версии (их несколько тысяч штук), представленные в виде [0-9A-Za-z], они распаковываются в набор чисел int[]. Чтобы не выполнять повторную распаковку для Provides-версий, там есть LRU-кеш на 256 элементов. Сейчас для окончательного попадания в кеш нужен большой strcmp(), т.е. в кеше хранится как распакованный массив int[], так и сама строка для сравнения. Если вместо strcmp() для идентификации строк можно было бы использовать 96-битный хеш, это было бы здорово. 96-битов, если там не происходит потери энтропии, как раз должно хватить, чтобы без коллизий можно было отличать между собой несколько тысяч строк. 96-бит мне было бы еще очень удобно, потому что 32-битный ключ используется для быстрого линейного поиска в LRU-кеше, а дополнительно потом проверяется еще 64 бита (которые лежат в другом месте). Код можно здесь посмотреть: https://github.com/svpv/rpmss/blob/master/rpmsetcmp.c (искать "memcmp").

2. В ccache используется md4 примерно для того же: для идентификации исходного текста и опций компиляции. Там уже конечно требуется 128 бит, но больше - не нужно (потому что пустая трата места тоже не нужна). Заголовочные файлы хешируются целиком. Бывает ли что-то быстрее и более-менее не хуже по качеству, чем md4?

В обоих задачах совсем коротких строк не бывает. Но зато, поскольку требуется идентификация, окончательный mixing step должно быть достаточно надежным.

Я смотрел zzh, мне показалось, что там ввод дополняется нулями, а длина при этом примешивается в самом конце как-то слабовато:

U32 v6 = len + v1 + v2 + v3 + v4 + v5;

Но да, я тоже не специалист. :-)

[erthink]

@ymarkovitch, @Bulat-Ziganshin, @lemenkov FYI.

Комментарии и соображения приветствуются.

[lemenkov]

Глупый вопрос - это все тот же алгоритм, да? Т.е. различие будет исключительно в скорости на данном процессоре (какие-то функции более оптимизированы, какие-то менее, но результаты будут идентичные).

[erthink]

@lemenkov, нет, всё несколько сложнее.

Суть в том, что нужны несколько функций с различным соотношением качество/производительность. Причем качество (совокупность свойств хеша) тут примерно всегда обратно-пропорциональны производительности.

Соответственно, "алгоритм" не может быть одинаковым для всех вариантов, хотя какие-то элементы могут быть общими.

---

Далее, практика показала что мало кто может (без мануала, просто глядя в код), оценить адекватность хеша для конкретного применения, особенно с учетом неизбежного компромисса качество/скорость.

Проще говоря, большинство пользователей ожидает от всех вариантов t1ha(), t1ha_32le() и даже t1ha_ia32crc() примерно одинаковых свойств - чего не может быть в принципе.

Кто-то решил что t1ha - это круто-быстрый siphash и даже распространил эту гипотезу на t1ha_ia32crc(), а кто-то наоборот стал "кидаться помидорами".

Пожалуй я немного просчитался в "формате подачи", сделав ставку на "кому надо тот разберется", и теперь чувствую ответственность "за тех кого приручили". Поэтому планирую переименование, одновременно с явным описанием свойств и целевого применения.

[lemenkov]

@leo-yuriev да, в общих чертах понятно.

[Bulat-Ziganshin]

1. когда человек берётся соревноваться с siphash и первым делом пишет "я правда не криптограф" - это уже вызывает чувство глубокого недоумения. Бернштейн вообще-то - один из весьма известных криптографов. поэтому я советую оставить все сравнения с сипхешем. то же самое относится к argon2 - ты хотя бы все статьи участников конкурса прочитал?
2. более того, я лично не знаю как провести разницу между t1ha/spooky/mur3f и siphash. так что если ты хочешь сделать что-то более стойкое чем t1ha - для начала проясни как ты собираешься это проверять
3. что реально можно сделать - это хеши оптимизированные для 32/64-битных cpu и отдельно simd (sse/neon), хеши разного размера, хеши оптимизированные для коротких (<32 байт) или длинных цепочек, хеши готовые к gpu и m/t. собственно часть этих требований можно совместить, так что остаётся главным образом различение 32/64/simd, а результаты различной ширины можно генерить из большого внутреннего состояния. почитай https://encode.ru/threads/2556-Improving-xxHash

вообще я сделал значительную часть работы над x86 хешем в zzh, так что можешь взять его последний код. по большому счёту там не хватает только ещё одного уровня распараллеливания для поддержки gpu. ну или во всяком случае посмотри его насчёт идей - они всё равно не мои :)

мой widezzh достигает скорости 5.5 байт/цикл - почти вдвое больше чем t1ha. я думаю, что если ты удвоишь внутреннее состояние t1ha (и будешь обрабатывать 64 байта за цикл) - ты сможешь его лучше распараллелить

[erthink]

@Bulat-Ziganshin, да, это всё тоже требует уточнения и некой "фиксации". Образно говоря, в меня прилетело достаточно "помидоров", просто потому что каждая недосказанность трактуется в "удобную" и/или "нужную" стороны.

Теперь немного по-пунктам:

1. Видимо есть какое-то недопонимание, поэтому я еще раз повторю некоторые очевидные вещи:

   • t1ha (текущие варианты) не является конкурентом siphash и никакого соревнования не было и быть не могло;
   • Все "сравнения" с siphash были в ключе "t1ha - это одно, а siphash - другое";
   • t1ha - это попытка сделать быструю 64-битную хэш-функцию для 64-битных CPU, с прицелом на x86 (было несколько вариантов, но текущий с "широким" умножением не очень быстр на архитектурах без инструкции "широкого" умножения, поэтому я буду добавлять варианты в t1ha0);
   • Идея оценить "потерю стойкости" в t1ha от теоретического потолка не была удачной, так как не принесла ничего полезного, только флейм и троллинг;
   • Обсуждать планируемые/будущие реализации t1ha (номера 4,6,7) можно будет после появления какого-либо кода или концепта. Причем хотелось бы надеяться, что меня правильно поняли: я не собираюсь "достать кролика из шляпы", обозначенная шкала 0...7 это прежде всего варианты использования, под которые можно подобрать готовые функции или составить их из исследованных примитивов/преобразований.
   • Говорить что-либо другое кроме "я правда не криптограф" видимо я никогда не буду (если только после PhD), а сочетание "крипто-энтузиаст" меня почему-то смешит (некрофилия какая-то ;)

2. Как уже отметил шкала 0...7 - это прежде всего сценарии использования, а не обещание сделать замену siphash и/или argon.

   • Конечно "хочется" сделать достойные варианты 4,6 и 7, но совершенно не факт что что-либо получится.
   • По каждому из вариантов 4,6 и 7 есть идеи, но за разработку я не брался (некогда и до лета видимо не получится).
   • На всякий еще раз отмечу: все текущие идеи базируются на уже исследованных преобразованиях, включая тот-же siphash (ARX). По-большому счету - это не сделать что-то новое, а сделать что-то иначе (так чтобы не хуже, но быстрее).

3. С практической точки зрения мне (с коллегами) в ближайшее время нужны варианты 2 и 3, а также дополнительные реализации t1ha0() c оптимизацией под конкретные платформы/процессоры. Собственно этим я и думаю заниматься некоторое ближайшее время.

   • подход с расширением state я как-то уже обыгрывал и даже декларировал что он будет использован в t1ha4().
   • тем не менее расширение state требует кратного увеличения затрат на перемешивание, либо не перекрывает многие векторы атак.
   • с другой стороны, более широкий state позволяет развязать зависимость по данным для конвейера CPU;
   • поэтому в целом я планирую придерживаться компромисса как в текущей t1ha:
     -- примерно удвоенный state (две ширины результата) для коротких ключей;
     -- примерно учетверенный state (четыре ширины результата) в цикле для длинных ключей;
     -- соответствующее кол-во injection points;
   • на 32-битные платформы будет минимум внимания, точнее говоря я не буду делать какие-либо варианты t1ha ориентированными на 32-битные платформы (только внутренние суррогаты t1ha0, как текущие t1ha_32le или t1ha_ia32aes).
   • SIMD конечно буду использовать, причем постараюсь классически, т.е. "просто" буду делать основную арифметику векторизируемой, так чтобы хороший компилятор сам задействовал SIMD.
   • ходить в GPU пока намерения нет, просто я не вижу тут востребованных сценариев применения.

Буквально сейчас я по-немного делаю необходимые инструменты. Например, небольшой с++ framewok, который позволит комфортно оценивать каждую операцию, каждый примитив (смещения, коллизии/иньективность, лавинный эффект). Как минимум это требуется для нестойких вариантов t1ha, в частности для №3.

В реальности двигаюсь совсем по-немного, почти не двигаюсь - потому что есть другие deadlines и т.п.

[Bulat-Ziganshin]

все текущие идеи базируются на уже исследованных преобразованиях, включая тот-же siphash (ARX).

и что это за исследования?? что ты вообще понимаешь под arx?

[erthink]

1. The Additive Differential Probability of ARX
2. Construction of Differential Characteristics in ARX Designs
3. Differential Cryptanalysis of SipHash
4. Rotational Cryptanalysis of ARX Revisited
5. Tuple cryptanalysis of ARX

[Bulat-Ziganshin]

судя по названиям, речь о применении arx в криптографических алгоритмах, которыми ты поклялся не заниматься. так что мантра о применении "исследованного" arx применительно к обычным хешам звучит примерно так же как применение "исследованного C" или "исследованной двоичной арифметики". или ты серьёхно собрался отказаться от умножения, чтобы противостоять дифференциальным атакам при фиксированном seed?

SIMD конечно буду использовать, причем постараюсь классически, т.е. "просто" буду делать основную арифметику векторизируемой, так чтобы хороший компилятор сам задействовал SIMD.

не получится. вероятно, ты не знаком с набором команд sse. страшно далеки они от наших нужд :)

[erthink]

@Bulat-Ziganshin, я ни о чем не клялся )

Еще раз для каждого из вариантов 2..7 планируется свое решение, что-то на ARX. При этом для некоторых вариантов скорость не нужда (даже вредна).

MUL-XOR может иногда может быть сильно похож на ARX, например широкое умножение на степень двойки и XOR старшей и младшей частей результата равносилен циклическому сдвигу, и т.п.

C SIMD я знаком более 15 лет, начиная с alpha-blending и write-back в PCI для StreamAlpha.

Считаю тему закрытой.

[Bulat-Ziganshin]

96-битных хешей никто не делает, просто обрезайте 128-битный. У всех приличных хешей вероятность коллизии на случайных данных, как и на несложных тестовых паттернах из smhasher, равна теоретической. Чем отличаются более качественные хеши - тем, что паттерны, на которых будут коллизии, у них более сложны. К сожалению, область эта чисто эмпирическая - думаю, для современных sha-хешей и даже для md4 такие паттерны неизвестны, в то время как для простых хешей типа zzh их несложно сконструировать

далее, выбор хеша определяется двумя параметрами

1. минимальный проц на котром нужно обеспечить высокую скорость (x86/x64? sseN?)
2. (средний) размер хешируемых строк
3. выбор между оптимизацией задержки или производительности, но при строках от сотни байт тут уже нет разницы

[Bulat-Ziganshin]

из имеющихся хешей могу предложить:

• spooky: x64, 4 byte/cycle. Один из самых известных хешей, автор которого собственно и начал исследования в области проверки качества хеширования, которые привели к созданию smhasher. Автор занимается созданием хешей уже лет 10-20 и это последняя версия в его линейке хешей. Недостатком можно считать использование только ARX, так что возможно перемешивание у него хуже чем у новейших хешей
• murmur3 x64-128 и x86-128. Хеши от автора smhasher, уже третья версия с исправлением недостатков, найденных в предыдущих. Вроде помедленней spooky, используется умножение
• HighwayHash, 1024-битное внутреннее состояние, новая эффективная операция обновления, включающая умножение и грамотное перемешивание байтов. Требует x64 ssse3 для получения производительности где-то 2-3 byte/cycle, без ssse3 на порядок медленней (впрочем, 64-битные хеши на x86 ведут себя так же)

t1ha находится где-то на уровне murmur3 x64-128

[erthink]

@svpv,

В основном всё сказано верно. Доступная в паблике версия t1ha по качеству/стойкости примерно соответствует murmur, только быстрее.

Но хочу дополнить:

1. Для аутентификации 96 бит мало, нужно минимум 128 вне зависимости от стойкости хеша.

2. Скорость принципиально зависит от заточки под систему команд и фичи конкретного процессора. При этом стойкость в любом случае требует 3-5 раундов перемешивания/сжатия состояния перед возвратом результата.

3. Заявленные планы по развитию t1ha (варианты 2..4) будут реализовываться. Это нужно для продуктов, которые выйдут на рынок до конца года. Т.е. вы можете на это рассчитывать, но точных сроков я назвать её могу (многое упирается в тщательность проработки вопроса, в том числе заточку под Эльбрус и Байкал/MIPS64).

4. Если нужно что-то прямо сейчас или "вчера", то берите SipHash или что-нибудь из ближайших производных.

5. В качестве бонуса для x86 в обойме t1ha будут различные хэши на основе AES-NI инструкций. Причин для этого две:

   • aes инструкции одни из лучших " по перемешиванию" и недооценены (imho) в этом плане.
   • они доступны на "ширпотребных" платформах.