The OpenNET Project

 
Поиск (теги):    НОВОСТИ (+) КОНТЕНТ WIKI MAN'ы ФОРУМ twitter

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, 13:07, 03/03/2016 [ответить] [смотреть все]
  • +2 +/
    Хм, интересно, но если оно шустро работает только там, где есть AVX-2 - то несколько сомнительное изобретение. Как ни крути, ARM кругом - море.
     
     
  • 2.11, Ivan, 14:29, 03/03/2016 [^] [ответить] [смотреть все] [показать ветку]
  • +2 +/
    Не совсем Раз оно шустро работает на AVX2 это означает, что вычисление этой фун... весь текст скрыт [показать] [показать ветку]
     
     
  • 3.53, kachsheev, 18:37, 05/03/2016 [^] [ответить] [смотреть все]  
  • +/
    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, 14:05, 03/03/2016 [^] [ответить] [смотреть все] [показать ветку]  
  • +5 +/
    Затем, зачем ускоряют и остальной софт.
     
  • 2.6, VoDA, 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, 14:38, 03/03/2016 [^] [ответить] [смотреть все]  
  • +1 +/
    Я с тобою абсолютно согласен Могу только предположить, что если назвать функцию... весь текст скрыт [показать]
     
     
  • 7.13, Аноним, 14:46, 03/03/2016 [^] [ответить] [смотреть все]  
  • –1 +/
    Отлично, значит не я один не понимаю, зачем ускорять криптостойкие хеш функции ... весь текст скрыт [показать]
     
     
  • 8.14, funny_falcon, 14:52, 03/03/2016 [^] [ответить] [смотреть все]  
  • +2 +/
    Ну, не совсем Криптостойкость нужна разная для паролей - медленная Для подпис... весь текст скрыт [показать]
     
     
  • 9.17, Аноним, 15:30, 03/03/2016 [^] [ответить] [смотреть все]  
  • +/
    ИМХО не согласен Во первых, никто не считает хеш TCP пакетов я не про чексумы ... весь текст скрыт [показать]
     
     
  • 10.18, funny_falcon, 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, 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, 18:14, 04/03/2016 [^] [ответить] [смотреть все]  
  • +/
    > И опять таки - почему криптостойкие, а не просто с защитой от hashDoS атак?

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

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

     
  • 5.15, angra, 15:10, 03/03/2016 [^] [ответить] [смотреть все]  
  • +1 +/
    Во-первых, без злоумышленника она будет просто тормозить всегда по сравнению с н... весь текст скрыт [показать]
     
     
  • 6.20, cebka, 16:17, 03/03/2016 [^] [ответить] [смотреть все]  
  • +/
    Не знаю термина "криптостойкие" относительно хеш-функций, но, разумеется, ваше определение подходит к любой хеш функции - в общем случае исходные данные *невозможно* восстановить для любой хеш функции, т.к. пространство выходных значений всегда меньше пространства входных значений просто по определению хеш функции. А вот криптографические хеши отличаются от обычных тем, что *подобрать* к ним коллизию очень сложно для любых входных данных. Они потому и называются collision-resistant. Siphash НЕ является collision resistant хеш-функцией.
     
     
  • 7.35, funny_falcon, 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, 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-2016 by Maxim Chirkov  
    ДобавитьРекламаВебмастеруГИД  
    Hosting by BSH TopList