The OpenNET Project / Index page

[ новости /+++ | форум | wiki | теги | ]

Быстрая хеш-функция HighwayHash и развитие SipHash от Google

03.03.2016 12:02

Компания Google представила три новые реализации хеш-функций: быстрая реализация SipHash-AVX2, модификация SipTreeHash и полностью новая хеш-функция HighwayHash. Одно из основных предназначений хеш-функций этой категории - противостояние атакам типа hashDoS (трата чрезмерных ресурсов при обработке значений, вызывающих коллизии). Реализации написаны на языке C++ с использованием intrinsics для обеспечения распараллеливания обработки данных с использованием инструкций AVX2. Код хеш-функций открыт под лицензией Apache 2.0.

Реализация SipHash-AVX2 полностью совместима на уровне выдаваемых значений с оригинальной SipHash, но в полтора раза быстрее ранее доступного варианта, оптимизированного с использованием инструкций SSE4.1. Модификация SipTreeHash, кроме инструкций AVX2, использует хеширование на основе деревьев j-lanes, позволяющих одновременно в несколько параллельных потоков обрабатывать входные данные (ввод разбивается на 8-байтовые пакеты, которые обрабатываются параллельно). SipTreeHash в три раза быстрее исходного SipHash, за исключением случаев с расчётом хешей для мелких наборов данных (на данных менее 96 байтов SipTreeHash медленнее SipHash).

В хеш-функции HighwayHash применяется новый метод смешивания входных данных, используя минимум AVX-2 инструкций умножения и переставления. По мнению инженеров Google, получившаяся хеш-функция является криптографически надёжной, но для подтверждения стойкости требуется проверка при помощи новых методов криптоанализа. При обработке больших входных данных эффективность HighwayHash достигает 0.3 процессорных такта на байт, но и на небольших данных HighwayHash также остаётся эффективнее SipHash. Например, при обработке блоков в 1 KiB HighwayHash в семь раз быстрее исходного SipHash, а пропускная способность на CPU Xeon E5-1650 v3 3.5 GHz составляет 11.3 GB/s (SipHash - 1.7 GB/s, SipTreeHash - 4.8 GB/s).

Дополнение: Появилась реализация SipHash-AVX2 на языке C (вместо C++) от мейнтейнера libsodium.

  1. Главная ссылка к новости (http://www.metzdowd.com/piperm...)
  2. OpenNews: Первый стабильный выпуск криптографической библиотеки Sodium
  3. OpenNews: Автор md5crypt подчеркнул небезопасность данного алгоритма и призвал перейти на более стойкие методы хэширования паролей
  4. OpenNews: Оценка эффективности хэширования паролей на крупном GPU-кластере
  5. OpenNews: Инициатива по разработке новых методов хэширования паролей
  6. OpenNews: Компания Google открыла код набора хэш-функций FarmHash
Автор новости: Аноним
Тип: Программы
Короткая ссылка: https://opennet.ru/43979-hash
Ключевые слова: hash, highwayhash, siphash
При перепечатке указание ссылки на opennet.ru обязательно
Обсуждение (58) Ajax | 1 уровень | Линейный | +/- | Раскрыть всё | RSS
  • 1.1, Crazy Alex (ok), 13:07, 03/03/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • +2 +/
    Хм, интересно, но если оно шустро работает только там, где есть AVX-2 - то несколько сомнительное изобретение. Как ни крути, ARM кругом - море.
     
     
  • 2.11, Ivan (??), 14:29, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +2 +/
    Не совсем.

    Раз оно шустро работает на AVX2 это означает, что вычисление этой функции параллелизуется. Т.е. даже если набор векторных комманд не позволяет реализовать это на ARM (я не знаю так ли это), скалярный код можно написать так, чтобы он по макимуму использовал параллелизм на уровне инструкций (для супер скалярных процессоров).

     
     
  • 3.53, kachsheev (ok), 18:37, 05/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    > набор векторных комманд
    > ARM

    NEON же (не уверен, что на всех процах). 128-битные регистры как раз есть.

     

  • 1.2, yaa (?), 13:21, 03/03/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • +1 +/
    Дык, это более серверная (даже highload servers) сторона. В этой области ARM --- экзотика.
     
  • 1.3, Аноним (-), 13:22, 03/03/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • +3 +/
    Спасибо, что не на Гоу.
     
     
  • 2.34, Аноним (-), 21:16, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Долго ждать не заставит
     

  • 1.4, Аноним (-), 13:58, 03/03/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • –5 +/
    я один не в курсе, зачем ускорять хеш-функции?
     
     
  • 2.5, RazrFalcon (ok), 14:05, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +5 +/
    Затем, зачем ускоряют и остальной софт.
     
  • 2.6, VoDA (ok), 14:09, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +2 +/
    > я один не в курсе, зачем ускорять хеш-функции?

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

     
     
  • 3.7, Аноним (-), 14:19, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +2 +/
    В Map-ах нужны криптостойкие хеши? О_О
     
     
  • 4.8, Аноним (-), 14:22, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Если туда попадают юзерские данные, то да. Иначе злоумышленник, генерируя коллизии, заставит вашу мапку безумно тормозить.
     
     
  • 5.9, Аноним (-), 14:24, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • –2 +/
    > Если туда попадают юзерские данные, то да. Иначе злоумышленник, генерируя коллизии, заставит
    > вашу мапку безумно тормозить.

    И часто у тебя в Map-ы попадают юзерские данные в качестве ключей?

     
     
  • 6.16, Аноним (-), 15:14, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • –1 +/
    про dht слышал, клоун?
     
  • 5.10, Аноним (-), 14:27, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    > Если туда попадают юзерские данные, то да. Иначе злоумышленник, генерируя коллизии, заставит
    > вашу мапку безумно тормозить.

    И опять таки - почему криптостойкие, а не просто с защитой от hashDoS атак?

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

     
     
  • 6.12, funny_falcon (ok), 14:38, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Я с тобою абсолютно согласен.

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

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

     
     
  • 7.13, Аноним (-), 14:46, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • –1 +/
    > Я с тобою абсолютно согласен.

    Отлично, значит не я один не понимаю, зачем ускорять криптостойкие хеш функции :D

     
     
  • 8.14, funny_falcon (ok), 14:52, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +2 +/
    Ну, не совсем Криптостойкость нужна разная для паролей - медленная Для подпис... текст свёрнут, показать
     
     
  • 9.17, Аноним (-), 15:30, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    ИМХО не согласен Во первых, никто не считает хеш TCP пакетов я не про чексумы ... текст свёрнут, показать
     
     
  • 10.18, funny_falcon (ok), 15:38, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Любой подбор занимает время Пароль ты можешь подбирать неделями, и подобрав пол... текст свёрнут, показать
     
     
  • 11.24, Аноним (-), 17:07, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • –1 +/
    Секундочку, а где вторая сторона будет каждый раз новую соль брать Нельзя же де... большой текст свёрнут, показать
     
     
  • 12.28, funny.falcon (?), 18:20, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Пожалуйста, почитайте об алгоритмах, тогда поговорим Да, я немножко слукавил н... текст свёрнут, показать
     
  • 10.21, Sw00p aka Jerom (?), 16:18, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    мммммм стоп - то, что пароли в базе хранятся в виде хешей - ни о чём не говорит,... текст свёрнут, показать
     
     
  • 11.25, Аноним (-), 17:15, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    хранить шифрованные пароли - не особо безопаснее хранения паролей в открытом вид... большой текст свёрнут, показать
     
     
  • 12.27, Sw00p aka Jerom (?), 18:15, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • –1 +/
    а кто вас просит один ключ использовать , я же привёл пример тупо шифровать паро... текст свёрнут, показать
     
     
  • 13.37, angra (ok), 09:31, 04/03/2016 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Объясняю разницу между шифрованием самим паролем и правильным использованием сол... текст свёрнут, показать
     
  • 13.38, Аноним (-), 11:32, 04/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Ты это серьезно Выше уже все расписали, но все равно я не могу мимо этого пройт... большой текст свёрнут, показать
     
  • 10.22, Sw00p aka Jerom (?), 16:24, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    про это чёть по подробнее не совсем понял, вы имели ввиду подпись она открыто н... текст свёрнут, показать
     
     
  • 11.26, Аноним (-), 17:21, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Да, я имел в виду именно подпись Но утверждение, что она открыто не передается ... текст свёрнут, показать
     
     
  • 12.29, Sw00p aka Jerom (?), 18:27, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    gt оверквотинг удален хмммм соль да соль, а причём тут соль речь о подписи, ... текст свёрнут, показать
     
     
  • 13.32, Аноним (-), 19:08, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • –1 +/
    Вот при этом и соль Дописываем ее к данным и считаем хеш Теперь если ты что-то... большой текст свёрнут, показать
     
     
  • 14.33, Sw00p aka Jerom (?), 19:58, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +1 +/
    не люблю пруфничать, но пользы ради скину две ссылки https ru wikipedia org w... текст свёрнут, показать
     
     
  • 15.39, Аноним (-), 11:42, 04/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Не увидел тут ничего, что опровергало бы мои слова я не понял, к чему это ... текст свёрнут, показать
     
     
  • 16.40, Sw00p aka Jerom (?), 16:16, 04/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    значить нужно вам перечитать ссылку выше раздел Частые вопросы о соли для нович... текст свёрнут, показать
     
     
  • 17.41, Sw00p aka Jerom (?), 16:32, 04/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Ответ пользователю angra, 09 31, 04 03 2016 , требует почемуто регистрации пишу... текст свёрнут, показать
     
     
  • 18.42, Sw00p aka Jerom (?), 16:39, 04/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    смотря какой режим блин, в режиме Electronic code book ECB да один и тот же, н... текст свёрнут, показать
     
     
  • 19.45, Аноним (-), 17:51, 04/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Не, ты его сейчас зачем-то начал До этого был нормальный разговор Давай так - ... большой текст свёрнут, показать
     
     
  • 20.49, Sw00p aka Jerom (?), 19:06, 04/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Зачем писать ссылку почитайте про режимы шифрования, убедитесь сами ... текст свёрнут, показать
     
  • 21.54, Аноним (-), 10:33, 07/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Я перечитал И либо я что-то не понял, либо ты пытаешься ввести меня в заблужден... текст свёрнут, показать
     
  • 18.44, Аноним (-), 17:47, 04/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    scrypt например А хеш вместо шифра, т к по хешу значительно сложнее восстанови... текст свёрнут, показать
     
     
  • 19.50, Sw00p aka Jerom (?), 19:12, 04/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    https ru wikipedia org wiki PBKDF2 раздел Использование Это практически должно... текст свёрнут, показать
     
     
  • 20.55, Аноним (-), 10:45, 07/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Еще раз, на пальцах Вариант с хранением хеша посоленого пароля Утекает хеш, ... текст свёрнут, показать
     
  • 21.57, Sw00p aka Jerom (?), 14:07, 07/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Ну, повторите высказанное для хеша - шифрованию, вы думаете достав шифрованный п... текст свёрнут, показать
     
  • 19.58, Sw00p aka Jerom (?), 14:10, 07/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    где с шифрованием утекли секреты я что в базе ключ от шифротекста храню пс ... текст свёрнут, показать
     
  • 17.43, Аноним (-), 17:39, 04/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Может не будем таки говорить загадками Накидать ссылок и я могу - сказать то чт... текст свёрнут, показать
     
     
  • 18.46, Sw00p aka Jerom (?), 17:54, 04/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Выдержка из https ru wikipedia org wiki PBKDF2 Одной из задач при создании PBK... текст свёрнут, показать
     
     
  • 19.48, Аноним (-), 18:45, 04/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    У меня складывается стойкое впечатление, что ты не до конца понимаешь, о чем гов... большой текст свёрнут, показать
     
     
  • 20.51, Sw00p aka Jerom (?), 19:34, 04/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    речь щас о хешировании а то вы про хеш функцию начинаете а кончаете генерирует... текст свёрнут, показать
     
  • 21.56, Аноним (-), 11:32, 07/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    не придирайся к словам тут по сути берется хеш функция от заданной парольной фр... большой текст свёрнут, показать
     
  • 7.30, Sw00p aka Jerom (?), 18:44, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    >но если ты сам не эксперт в криптографии, тебе всё равно никто не поверит.

    и каков критерий оценки экспертства? премия тюринга, или клэя ?


     
  • 6.47, Ordu (ok), 18:14, 04/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    > И опять таки - почему криптостойкие, а не просто с защитой от hashDoS атак?

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

    Если вам это удастся, то расскажите об отличиях. Мне было бы интересно услышать: мне кажется, что разницы нет никакой, но я, в конечном итоге, не специалист в этих вопросах и могу ошибаться.

     
  • 5.15, angra (ok), 15:10, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Во-первых, без злоумышленника она будет просто тормозить всегда по сравнению с некриптостойкой хеш-функцией.
    Во-вторых, криптостойкие хеш-функции от некриптостойких отличаются в первую очередь не количеством коллизий, а сложностью восстановления исходных данные по хешу.
     
     
  • 6.20, cebka (?), 16:17, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Не знаю термина "криптостойкие" относительно хеш-функций, но, разумеется, ваше определение подходит к любой хеш функции - в общем случае исходные данные *невозможно* восстановить для любой хеш функции, т.к. пространство выходных значений всегда меньше пространства входных значений просто по определению хеш функции. А вот криптографические хеши отличаются от обычных тем, что *подобрать* к ним коллизию очень сложно для любых входных данных. Они потому и называются collision-resistant. Siphash НЕ является collision resistant хеш-функцией.
     
     
  • 7.35, funny_falcon (ok), 21:29, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8

    Цитата:

    Для того, чтобы хеш-функция H считалась криптографически стойкой, она должна удовлетворять трём основным требованиям, на которых основано большинство применений хеш-функций в криптографии:

    - Необратимость или стойкость к восстановлению прообраза: для заданного значения хеш-функции m не должен быть вычислен блок данных X, для которого {H(X)=m}.
    - Стойкость к коллизиям первого рода или восстановлению вторых прообразов: для заданного сообщения M должно быть вычислительно невозможно подобрать другое сообщение N, для которого H(N)=H(M).
    - Стойкость к коллизиям второго рода: должно быть вычислительно невозможно подобрать пару сообщений ~(M, M'), имеющих одинаковый хеш.

    (Согласно третьему пункту, MD5 считается взломанной, хотя относительно первых двух пунктов пока нет)

     
  • 7.36, funny_falcon (ok), 21:30, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Сорри, вот ссылка

    https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8

     
  • 6.31, Sw00p aka Jerom (?), 18:48, 03/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    > в первую очередь не количеством коллизий, а сложностью восстановления исходных данные по хешу.

    не в первую, но во вторую и третью, соответственно коллизиям первого и второго рода.


     

  • 1.19, cebka (?), 16:12, 03/03/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • +5 +/
    Переделал у себя на ассемблере: https://git.io/v29iL

    Производительность реально довольно хорошо подросла (я сравнивал не с sse4.2 версией, которая на x86_64 работает не быстрее generic, а с самим generic):

    Refrence siphash (1KB): 0.30127492197789 sec
    Optimized siphash (1KB): 0.07682267203927 sec
    Refrence siphash (5B): 0.082667203852907 sec
    Optimized siphash (5B): 0.032516790088266 sec
    Refrence siphash (50B): 0.21968871704303 sec
    Optimized siphash (50B): 0.071362769929692 sec

    Highway hash интересный, но до подробного криптоанализа и до наличия reference версии без интринисков пока использовать не буду, хотя для моих задач она просто неприлично хорошо подходит.

     
     
  • 2.52, Анонон (?), 01:11, 05/03/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Почему asm, а не Си+интринсики?
     

  • 1.59, erthink (ok), 13:58, 07/03/2019 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Лучше поздно чем никогда.

    HighwayHash не является официальным проектом гугла, это pet-проект нескольких сотрудников. Поэтому фразу "Компания Google представила HighwayHash" нельзя назвать полностью корректной.

    Криптографическая "стойкость" HighwayHash никак не доказана. Но об этом "доказательстве" стоит упомянуть отдельно, ибо оно сводится к двум пунктам:

    1) Авторы провели статистические тесты SMHasher-ом и с ними все хорошо.
    Однако, буквальные результаты не были где-либо показан. Более того, был использован доработанный вариант SMHasher, исходные тексты которого авторы показывать отказались. Не были открыты даже параметры запуска/скрипты/сценарии. Поэтому невозможно воспроизвести или перепроверить результаты, либо поковыраться в них.
    При этом стоит отметить что есть доработанный (более строгий) вариант SMHasher от  Yves Orton, который бракует очень многие их "хороших" хеш-функций.

    2) HighwayHash внутри выполняет операции аналогичные SipHash, и поэтому его стойкость следует из доказательств свойств SipHash.
    Тут проблема в том, что операции всё-таки не совсем аналогичные.
    Более того, внутри HighwayHash есть умножение данных на сами данные (упрощенно конечно). Поэтому в принципе возможен вектор атаки подтасовкой данных с целью получения нуля в одном из множителей. И вот никакого достойного анализа этого вектора атаки нет, только общие фразы.


    Ну и напоследок, HighwayHash сильно завязан на SSE4/AVX, т.е. без них производительность катиться к неприемлемым значениям. Поэтому, лично у меня возникает вопрос - а не лучше ли просто использовать AES-NI. Даже если это делать не так наивно как в MeowHash, то все равно будет быстрее и не менее переносимо (на разных архитектурах ускорение AES работает одинаково и распространено шире, в сравнении с аналогами SSE4/AVX).

     

     Добавить комментарий
    Имя:
    E-Mail:
    Текст:



    Спонсоры:
    Inferno Solutions
    Hosting by Hoster.ru
    Хостинг:

    Закладки на сайте
    Проследить за страницей
    Created 1996-2021 by Maxim Chirkov
    Добавить, Поддержать, Вебмастеру