The OpenNET Project / Index page

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

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

Компания 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
Автор новости: Аноним
Тип: Программы
Ключевые слова: hash, highwayhash, siphash
При перепечатке указание ссылки на opennet.ru обязательно
Обсуждение Ajax/Линейный | Раскрыть все сообщения | 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 это означает, что вычисление этой фун... весь текст скрыт [показать]
     
     
  • 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 [ответить] [показать ветку] [···]    [к модератору]  
  • +4 +/
    Спасибо, что не на Гоу.
     
     
  • 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 +/
    Хэши используются практически везде и всегда К примеру, Хэш функции используютс... весь текст скрыт [показать]
     
     
  • 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 атак Еще ... весь текст скрыт [показать]
     
     
  • 6.12, funny_falcon (ok), 14:38, 03/03/2016 [^] [ответить]     [к модератору]  
  • +1 +/
    Я с тобою абсолютно согласен Могу только предположить, что если назвать функцию... весь текст скрыт [показать]
     
     
  • 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 [^] [ответить]    [к модератору]  
  • +/
    > scrypt например.
    > А хеш вместо шифра, т.к. по хешу значительно сложнее восстановить исходные данные,
    > чем по шифру в ситуации, когда все "секреты" утекли.

    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

    Одной из задач при создании PBKDF2 было усложнить перебор паролей. Благодаря множеству зацепленных вычислений PRF скорость генерации ключа является небольшой.

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

     
     
  • 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, а не Си+интринсики?
     

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


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