The OpenNET Project / Index page

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



"Быстрая хеш-функция HighwayHash и развитие SipHash от Google"
Вариант для распечатки  
Пред. тема | След. тема 
Форум Разговоры, обсуждение новостей
Изначальное сообщение [ Отслеживать ]

"Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от opennews (ok), 03-Мрт-16, 13:07 
Компания Google представила (http://google-opensource.blogspot.com/2016/03/new-algorithms...) три новые реализации хеш-функций: новая быстрая реализация SipHash-AVX2 (https://en.wikipedia.org/wiki/SipHash), быстрая криптографически стойкая псевдослучайная функция (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.7957) SipTreeHash и полностью новая хэш-функция HighwayHash (https://github.com/google/highwayhash/). Хэш-функции написаны на языке C++ с использованием intrinsics (https://en.wikipedia.org/wiki/Intrinsic_function) для обеспечения распараллеливания обработки данных с использованием инструкций AVX-2 и изначально рассчитаны на противостояние атакам  типа hashDoS (https://www.opennet.ru/opennews/art.shtml?num=32698) (трата чрезмерных ресурсов при обработке значений, вызывающих коллизии). Код хэш-функций открыт (https://github.com/google/highwayhash/) под лицензией Apache 2.0.


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

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

URL: http://www.metzdowd.com/pipermail/cryptography/2016-March/02...

Новость: http://www.opennet.ru/opennews/art.shtml?num=43979

Ответить | Правка | Cообщить модератору

Оглавление

Сообщения по теме [Сортировка по времени | RSS]


1. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +2 +/
Сообщение от Crazy Alex (ok), 03-Мрт-16, 13:07 
Хм, интересно, но если оно шустро работает только там, где есть AVX-2 - то несколько сомнительное изобретение. Как ни крути, ARM кругом - море.
Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

11. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +2 +/
Сообщение от Ivan (??), 03-Мрт-16, 14:29 
Не совсем.

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

Ответить | Правка | ^ к родителю #1 | Наверх | Cообщить модератору

53. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от kachsheev (ok), 05-Мрт-16, 18:37 
> набор векторных комманд
> ARM

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

Ответить | Правка | ^ к родителю #11 | Наверх | Cообщить модератору

2. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +1 +/
Сообщение от yaa (?), 03-Мрт-16, 13:21 
Дык, это более серверная (даже highload servers) сторона. В этой области ARM --- экзотика.
Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

3. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +3 +/
Сообщение от Аноним (-), 03-Мрт-16, 13:22 
Спасибо, что не на Гоу.
Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

34. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Аноним (-), 03-Мрт-16, 21:16 
Долго ждать не заставит
Ответить | Правка | ^ к родителю #3 | Наверх | Cообщить модератору

4. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  –5 +/
Сообщение от Аноним (-), 03-Мрт-16, 13:58 
я один не в курсе, зачем ускорять хеш-функции?
Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

5. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +5 +/
Сообщение от RazrFalconemail (ok), 03-Мрт-16, 14:05 
Затем, зачем ускоряют и остальной софт.
Ответить | Правка | ^ к родителю #4 | Наверх | Cообщить модератору

6. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +2 +/
Сообщение от VoDA (ok), 03-Мрт-16, 14:09 
> я один не в курсе, зачем ускорять хеш-функции?

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

Ответить | Правка | ^ к родителю #4 | Наверх | Cообщить модератору

7. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +2 +/
Сообщение от Аноним (-), 03-Мрт-16, 14:19 
В Map-ах нужны криптостойкие хеши? О_О
Ответить | Правка | ^ к родителю #6 | Наверх | Cообщить модератору

8. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +1 +/
Сообщение от Аноним (-), 03-Мрт-16, 14:22 
Если туда попадают юзерские данные, то да. Иначе злоумышленник, генерируя коллизии, заставит вашу мапку безумно тормозить.
Ответить | Правка | ^ к родителю #7 | Наверх | Cообщить модератору

9. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  –2 +/
Сообщение от Аноним (-), 03-Мрт-16, 14:24 
> Если туда попадают юзерские данные, то да. Иначе злоумышленник, генерируя коллизии, заставит
> вашу мапку безумно тормозить.

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

Ответить | Правка | ^ к родителю #8 | Наверх | Cообщить модератору

16. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  –1 +/
Сообщение от Аноним (-), 03-Мрт-16, 15:14 
про dht слышал, клоун?
Ответить | Правка | ^ к родителю #9 | Наверх | Cообщить модератору

10. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Аноним (-), 03-Мрт-16, 14:27 
> Если туда попадают юзерские данные, то да. Иначе злоумышленник, генерируя коллизии, заставит
> вашу мапку безумно тормозить.

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

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

Ответить | Правка | ^ к родителю #8 | Наверх | Cообщить модератору

12. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +1 +/
Сообщение от funny_falcon (ok), 03-Мрт-16, 14:38 
Я с тобою абсолютно согласен.

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

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

Ответить | Правка | ^ к родителю #10 | Наверх | Cообщить модератору

13. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  –1 +/
Сообщение от Аноним (-), 03-Мрт-16, 14:46 
> Я с тобою абсолютно согласен.

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

Ответить | Правка | ^ к родителю #12 | Наверх | Cообщить модератору

14. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +2 +/
Сообщение от funny_falcon (ok), 03-Мрт-16, 14:52 
Ну, не совсем.

Криптостойкость нужна разная: для паролей - медленная. Для подписей пакетов данных - быстрая.

Собственно, SipHash прежде всего предназначен для подписи по закрытому ключу - проверить, что пакет был послан тебе субъектом, знающим ваш общий секрет. Учитывая, что пакеты данных могут идти сотнями мегабайт в секунду, иметь для этого быструю криптостойкую хэш-функцию весьма желательно.

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

Ответить | Правка | ^ к родителю #13 | Наверх | Cообщить модератору

17. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Аноним (-), 03-Мрт-16, 15:30 
> Собственно, SipHash прежде всего предназначен для подписи по закрытому ключу - проверить,
> что пакет был послан тебе субъектом, знающим ваш общий секрет. Учитывая,
> что пакеты данных могут идти сотнями мегабайт в секунду, иметь для
> этого быструю криптостойкую хэш-функцию весьма желательно.

ИМХО не согласен. Во первых, никто не считает хеш TCP пакетов (я не про чексумы протокола). Т.е. ты наверняка имел ввиду пакеты данных. Да, там может быть хеш, пусть даже от всех данных. Но ведь если использовать быструю хеш-функцию - это может серъезно упростит атаку, разве нет? Хеш то идет рядом с открытыми данными, наша задача - подобрать соль. И чем быстрее мы сможем это сделать - тем лучше для атакующего.

Ответить | Правка | ^ к родителю #14 | Наверх | Cообщить модератору

18. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от funny_falcon (ok), 03-Мрт-16, 15:38 
Любой подбор занимает время. Пароль ты можешь подбирать неделями, и подобрав получать профит.

Поток передачи данных же устанавливается на относительно короткий срок, и каждые раз с новой солью. Большинство надёжных протоколов требуют генерацию не повторяющейся соли к каждому пакету в потоке данных. Т.е. у тебя есть только один шанс вклиниться в поток - подобрать секретный ключ, который обычно имеет энтропию не меньше 2^127 - в отличии от типичного пароля, энтропия которого редко достигает даже 2^63. Соотвественно, перебирать 2^127 вариантов даже с быстрой функцией .... не хватит тебе всех ASIC мира.... ок, может быть хватит, но стоит это будет половину бюджета USA.

Соответственно: для паролей нужна медленная функция потому, что энтропия пароля типичного юзера низкая. Энтропия секретного ключа в защищённом протоколе настолько высока, что даже быструю функция достаточна, при условии её криптостойкости.

Ответить | Правка | ^ к родителю #17 | Наверх | Cообщить модератору

24. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  –1 +/
Сообщение от Аноним (-), 03-Мрт-16, 17:07 
> Поток передачи данных же устанавливается на относительно короткий срок, и каждые раз
> с новой солью. Большинство надёжных протоколов требуют генерацию не повторяющейся соли
> к каждому пакету в потоке данных. Т.е. у тебя есть только
> один шанс вклиниться в поток - подобрать секретный ключ, который обычно
> имеет энтропию не меньше 2^127 - в отличии от типичного пароля,
> энтропия которого редко достигает даже 2^63. Соотвественно, перебирать 2^127 вариантов
> даже с быстрой функцией .... не хватит тебе всех ASIC мира....
> ок, может быть хватит, но стоит это будет половину бюджета USA.

Секундочку, а где вторая сторона будет каждый раз новую соль брать? Нельзя же делать известный двум сторонам алгоритм ее генерации, да и передавать ее, пусть даже зашифрованную, никто в здравом уме не будет.

Ответить | Правка | ^ к родителю #18 | Наверх | Cообщить модератору

28. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +1 +/
Сообщение от funny.falcon (?), 03-Мрт-16, 18:20 
Пожалуйста, почитайте об алгоритмах, тогда поговорим.

Да, я немножко слукавил: на каждый пакет соль требуют не все протоколы. Но даже если требуют, обычно важно только, чтобы она не повторялась "никогда" (вернее, за обозримый период времени). А то, что её могут "предугадать" не важно: соль - это не секрет.

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

Ответить | Правка | ^ к родителю #24 | Наверх | Cообщить модератору

21. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Sw00p aka Jerom (?), 03-Мрт-16, 16:18 
мммммм стоп - то, что пароли в базе хранятся в виде хешей - ни о чём не говорит, я могу хранить зашифрованный AES-ом пароль самим же паролем, и расшифровывать - если удачно - впускать, в случае с хешем мы просто сравниваем хеш полученный от введённого пароля. И как известно, что любая хеш функция поддвержена коллизиям - использовать этот метод для хранения паролей - не хороший, грубо говоря.

Быстрая хеш функция - упрощает перебор, хмммм а почему не быстрое оборудование ? Любой алгоритм должен стремится к быстроте и эффективности, ну представьте из ваших соображений - хеш функция должна быть медленная, чтоб предотвратить грубый метод перебора, в этом случае достаточно будет впихнуть в алгоритм пустой цикл который через рандомное время остановится и дальше пойдёт сам процесс хеширование - к чему это приведёт ?

Ответить | Правка | ^ к родителю #17 | Наверх | Cообщить модератору

25. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Аноним (-), 03-Мрт-16, 17:15 
> мммммм стоп - то, что пароли в базе хранятся в виде хешей
> - ни о чём не говорит, я могу хранить зашифрованный AES-ом
> пароль самим же паролем, и расшифровывать - если удачно - впускать,
> в случае с хешем мы просто сравниваем хеш полученный от введённого
> пароля. И как известно, что любая хеш функция поддвержена коллизиям -
> использовать этот метод для хранения паролей - не хороший, грубо говоря.

хранить шифрованные пароли - не особо безопаснее хранения паролей в открытом виде. если утек алгоритм шифрования + ключ = утекли все пароли. Разный ключ для разных паролей? Ок. Утекли все ключи.

В случае с хешом - если для каждого пароля используется своя соль, и алгоритм хеширования известен - по сути ничего страшного не происходит. Ну знаешь ты алгоритм, хеш и соль. Что дальше?

> Быстрая хеш функция - упрощает перебор, хмммм а почему не быстрое оборудование
> ? Любой алгоритм должен стремится к быстроте и эффективности, ну представьте
> из ваших соображений - хеш функция должна быть медленная, чтоб предотвратить
> грубый метод перебора, в этом случае достаточно будет впихнуть в алгоритм
> пустой цикл который через рандомное время остановится и дальше пойдёт сам
> процесс хеширование - к чему это приведёт ?

Пустой цикл не подойдет, т.к. его можно тупо выкинуть из кода. Важна как раз вычислительная сложность. Да, для оборудования, которое на данный момент существует либо ожидается в обозримом будущем. Помнишь, как быстро сдулись некоторые алгоритмы шифрования, когда оказалось, что можно выполнять операции на видеокартах?

Ответить | Правка | ^ к родителю #21 | Наверх | Cообщить модератору

27. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  –1 +/
Сообщение от Sw00p aka Jerom (?), 03-Мрт-16, 18:15 
>хранить шифрованные пароли - не особо безопаснее хранения паролей в открытом виде.
>> если утек алгоритм шифрования + ключ = утекли все пароли.

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

>>Ну знаешь ты алгоритм, хеш и соль. Что дальше?

в смысле, что дальше ? в вашем случае это брут форс, и соль вам ничем не поможет если она также будет известна.

>>Важна как раз вычислительная сложность.

P ≠ NP )))))))

Существование односторонних функций до сих пор не доказано. Так, что вся ваша мат сложность упрётся в железо.

>>Помнишь, как быстро сдулись некоторые алгоритмы шифрования, когда оказалось, что можно выполнять операции на видеокартах?

ну сдулись и что? разве видеокарты взломали их ? Тот же шифр Вернама никакой брутфорс вам его не взломает ) и доказана его стойкость.


>>Пустой цикл не подойдет, т.к. его можно тупо выкинуть из кода.

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

плюс один из важных моментов - атака по времени, её тож нуно учитывать.

Ответить | Правка | ^ к родителю #25 | Наверх | Cообщить модератору

37. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +1 +/
Сообщение от angra (ok), 04-Мрт-16, 09:31 
Объясняю разницу между шифрованием самим паролем и правильным использованием соли. При брутфорсе у нас есть некая последовательность(неважно словарь или генерация) кандидатов в пароли. Мы всю ее пропускаем через используемый метод сокрытия пароля. Потом сравниваем полученные значения с хешами. Для простоты возьмем последовательность A:(a0,a1,a2,a3,a4).

В случае шифрования самим паролем мы для каждого члена последовательности получим ровно один хеш H:(h1,h2,h3,h4). После чего нам достаточно пройтись по базе и сравнить каждый хеш в ней с элементами H. Говоря по другому, к тому моменту когда мы дойдем до a4 все пароли, которые соответствовали более ранним членам последовательности A, уже взломаны. И по A мы проходим только один раз.

Правильная соль для каждого пароля зависит не от самого пароля и не от фиксированного значения. Это может быть уникальный логин пользователя, может быть время в микросекундах, может результат PRNG, ну или комбинация всего этого. Как следствие, если у двух пользователей пароль a0, то хеши пароля у них будут разными h0 и h`0. А значит вся последовательность H будет верна только для одного единственного значения соли, то есть для одного пользователя. И для взлома другого пользователя нам нужно заново пройтись по всей A и получить новую H`. И так для каждого пользователя в БД. Ну или в случае большой A надо для каждого ее члена считать хеши для солей каждого еще не взломанного пользователя. Так что если в базе десять тысяч пользователей, то начальный перебор замедляется сразу на четыре порядка. Вместо одного часа придется перебирать около года.

Ответить | Правка | ^ к родителю #27 | Наверх | Cообщить модератору

38. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Аноним (-), 04-Мрт-16, 11:32 
> а кто вас просит один ключ использовать?, я же привёл пример тупо
> шифровать пароль самим паролем в виде ключа шифрования.

Ты это серьезно? Выше уже все расписали, но все равно я не могу мимо этого пройти (вдруг кто-то не поймет сказанное выше).

Два юзера с одинаковым паролем, например abc123. Мы знаем алгоритм шифрования, знаем и ключ. Для одинаковых паролей будет одинаковый результат шифрования. Строим радужную таблицу по словарику и вытягиваем ~60% паролей за один проход.

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

Брутфорсом, да не только. Т.к. мы знаем зашифрованный текст (нам же никто не мешает зарегистрировать пачку юзеров с известными нам паролями?), есть большая вероятность существенно упростить себе задачу получения ключа, правда это справедливо далеко не для всех алгоритмов шифрования. Но насколько мне известно, хеш-функции такой проблеме не подвержены, а вот блочные алгоритмы шифрования частенько на этом сыпятся. Кто даст гарантию, что завтра в самом современном и подтвержденном всеми алгоритме не найдется такая уязвимость? Повторюсь, насколько я понимаю (пусть я и очень далек от криптоанализа), современные хеш-функции такому не подвержены в принципе (помню, в том же md5 иногда было видно, когда две строки имеют много общего - хеш "сдвигался" в сторону)

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

> Существование односторонних функций до сих пор не доказано. Так, что вся ваша
> мат сложность упрётся в железо.

Вопросов нет, через 1000 лет, если человечество выживет, современные крипто-хеши будут взламываться за миллисекунды контроллером USB 100500.3.rev12. Вопрос стоит - насколько сложно это сделать в обозримом будущем. Для этого и нужна медленная хеш-функция, чтобы подбор одного пароля занимал непозволительно много времени.

>>>Помнишь, как быстро сдулись некоторые алгоритмы шифрования, когда оказалось, что можно выполнять операции на видеокартах?
> ну сдулись и что? разве видеокарты взломали их ?

Взломали конечно не видеокарты. Но время на "взлом" сократилось ЕМНИП не на один порядок.


> Тот же шифр  Вернама никакой брутфорс вам его не взломает ) и доказана его
> стойкость.

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

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

Значит нужно делать не a+b, а например (a+b)^a*sqrt(b%sin(a)) и т.д.

> плюс один из важных моментов - атака по времени, её тож нуно
> учитывать.

sleep(random(100,500)) например

Ответить | Правка | ^ к родителю #27 | Наверх | Cообщить модератору

22. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Sw00p aka Jerom (?), 03-Мрт-16, 16:24 
> Хеш то идет рядом с открытыми данными, наша задача - подобрать соль.

про это чёть по подробнее не совсем понял, вы имели ввиду подпись (она открыто не передаётся)?

Ответить | Правка | ^ к родителю #17 | Наверх | Cообщить модератору

26. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Аноним (-), 03-Мрт-16, 17:21 
>> Хеш то идет рядом с открытыми данными, наша задача - подобрать соль.
> про это чёть по подробнее не совсем понял, вы имели ввиду подпись
> (она открыто не передаётся)?

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

Ответить | Правка | ^ к родителю #22 | Наверх | Cообщить модератору

29. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Sw00p aka Jerom (?), 03-Мрт-16, 18:27 
>[оверквотинг удален]
>> (она открыто не передаётся)?
> Да, я имел в виду именно подпись. Но утверждение, что она открыто
> не передается - очень спорное. Вот недавно работал с CyberSource -
> там соль хранится локально, я на основании данных, которые передаются в
> открытом виде (пусть и по https), и этой соли считаю хеш,
> затем передаю его рядом с этими же данными. Та сторона знает
> мою соль и видит переданные данные - считает хеш и сравнивает
> с переданным. Алгоритма динамической смены соли там нет (и я слабо
> представляю себе, как это можно сделать безопасно), соответственно чем быстрее хеш-функция,
> тем быстрее можно подобрать мою соль.

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

>>Но утверждение, что она открыто не передается - очень спорное.

Даже подпись на бумаге проверяется через эксперта и анализ подчерка автора.


пс:

merchant_id = your_merchant_id
transaction_key = "your_transaction_key"

банальная практика реквест токенов для API. хотя он там используется как пароль, а не хеш.

$soapUsername = new SoapVar(
            $this->merchantId,
            XSD_STRING,
            NULL,
            $nameSpace,
            NULL,
            $nameSpace
        );
        $soapPassword = new SoapVar(
            $this->transactionKey,
            XSD_STRING,
            NULL,
            $nameSpace,
            NULL,
            $nameSpace
        );
        $auth = new stdClass();
        $auth->Username = $soapUsername;
        $auth->Password = $soapPassword;

Ответить | Правка | ^ к родителю #26 | Наверх | Cообщить модератору

32. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  –1 +/
Сообщение от Аноним (-), 03-Мрт-16, 19:08 
> хмммм соль да соль, а причём тут соль ? речь о подписи,
> а подпись это хеш зашифрованный приватным ключём отправителя, получатель зная публичный
> ключь отправителя раскрывает этот хеш и сверяет с полученным хешом от
> отправленных данных, как можно просто посылать хеш в месте с данными
> ? я спокойно изменю данные по пути и вычислю от них
> хеш, где гарантии того, что данные не изменены ?

Вот при этом и соль. Дописываем ее к данным и считаем хеш. Теперь если ты что-то поменяешь, то тебе нужно посчитать хеш от новых данных + соль. А соль ты не знаешь.

Описанный тобой способ тоже имеет право на жизнь. Но я его не встречал нигде. У тебя нужно и хешировать, и шифровать, "мой" (в кавычках, т.к. не я его придумал) предполагает только хеширование. Но уровень защиты - одинаковый - "я" полагаюсь на соль, ты - на приватный ключ. Что быстрее раскрутить - хеширование или шифрование, я предлагаю оставить за рамками данной дискуссии, т.к. тут все зависит от выбора алгоритма.

Ответить | Правка | ^ к родителю #29 | Наверх | Cообщить модератору

33. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +1 +/
Сообщение от Sw00p aka Jerom (?), 03-Мрт-16, 19:58 
не люблю пруфничать, но пользы ради скину две ссылки.

https://ru.wikipedia.org/wiki/%D0%A1%D0%...

раздел Частые вопросы о соли для новичков

и собственно https://ru.wikipedia.org/wiki/PBKDF2 (думаю вы с этим знакомы)

Ответить | Правка | ^ к родителю #32 | Наверх | Cообщить модератору

39. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Аноним (-), 04-Мрт-16, 11:42 
> не люблю пруфничать, но пользы ради скину две ссылки.
> https://ru.wikipedia.org/wiki/%D0%A1%D0%...
> раздел Частые вопросы о соли для новичков

Не увидел тут ничего, что опровергало бы мои слова

> и собственно https://ru.wikipedia.org/wiki/PBKDF2 (думаю вы с этим знакомы)

я не понял, к чему это

Ответить | Правка | ^ к родителю #33 | Наверх | Cообщить модератору

40. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Sw00p aka Jerom (?), 04-Мрт-16, 16:16 
>>я не понял, к чему это

значить нужно вам перечитать ссылку выше раздел "Частые вопросы о соли для новичков"

Ответить | Правка | ^ к родителю #39 | Наверх | Cообщить модератору

41. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Sw00p aka Jerom (?), 04-Мрт-16, 16:32 
Ответ пользователю  angra, 09:31, 04/03/2016 , требует почемуто регистрации пишу тут сорри.

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

Ответить | Правка | ^ к родителю #40 | Наверх | Cообщить модератору

42. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Sw00p aka Jerom (?), 04-Мрт-16, 16:39 
> Ответ пользователю  angra, 09:31, 04/03/2016 , требует почемуто регистрации пишу тут
> сорри.
>>В случае шифрования самим паролем мы для каждого члена последовательности получим ровно один хеш

смотря какой режим блин, в режиме Electronic code book (ECB) да один и тот же, ну откройте и почитайте хотя бы википедию.

вот ссылка https://ru.wikipedia.org/wiki/%D0%A0%D0%...

и читайте про плюсы и минусы, и особенно про вектор инициализации

пс: всё холивар окончен.


Ответить | Правка | ^ к родителю #41 | Наверх | Cообщить модератору

45. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Аноним (-), 04-Мрт-16, 17:51 
>> Ответ пользователю  angra, 09:31, 04/03/2016 , требует почемуто регистрации пишу тут
>> сорри.
>>>В случае шифрования самим паролем мы для каждого члена последовательности получим ровно один хеш
> смотря какой режим блин, в режиме Electronic code book (ECB) да один
> и тот же, ну откройте и почитайте хотя бы википедию.
> вот ссылка https://ru.wikipedia.org/wiki/%D0%A0%D0%...
> и читайте про плюсы и минусы, и особенно про вектор инициализации
> пс: всё холивар окончен.

Не, ты его сейчас зачем-то начал. До этого был нормальный разговор.

Давай так - можешь дать код на bash, который зашифрует одну и ту же последовательность символов (пароль) используя эту же последовательность как ключ, но чтобы в результате получились 2 разных значения, которые потом можно обратно дешифровать?

Ответить | Правка | ^ к родителю #42 | Наверх | Cообщить модератору

49. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Sw00p aka Jerom (?), 04-Мрт-16, 19:06 
> Давай так - можешь дать код на bash, который зашифрует одну и
> ту же последовательность символов (пароль) используя эту же последовательность как ключ,
> но чтобы в результате получились 2 разных значения, которые потом можно
> обратно дешифровать?

Зачем писать? ссылку почитайте про режимы шифрования, убедитесь сами.

Ответить | Правка | ^ к родителю #45 | Наверх | Cообщить модератору

54. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Аноним (-), 07-Мрт-16, 10:33 
>> Давай так - можешь дать код на bash, который зашифрует одну и
>> ту же последовательность символов (пароль) используя эту же последовательность как ключ,
>> но чтобы в результате получились 2 разных значения, которые потом можно
>> обратно дешифровать?
> Зачем писать? ссылку почитайте про режимы шифрования, убедитесь сами.

Я перечитал. И либо я что-то не понял, либо ты пытаешься ввести меня в заблуждение. Поэтому для того, чтобы определиться с этим вопросом, я и попросил конкретный пример. Так проще и быстрее, чем кидаться ссылками.

Ответить | Правка | ^ к родителю #49 | Наверх | Cообщить модератору

44. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Аноним (-), 04-Мрт-16, 17:47 
> Ответ пользователю  angra, 09:31, 04/03/2016 , требует почемуто регистрации пишу тут
> сорри.
> Так вернёмся к основному вопросу, хеш функция должна быть медленной, чтобы брутфорс
> был дольше, утверждение сделанное в самом начале треда, так вот собственно
> вопрос покажите мне хеш функцию которая работала медленнее чем какойто алгоритм
> шифрование. Вам же нужно замедлить брутфорс, так? тогда зачем юзать хеш
> функции если алгоритм шифрования в разы медленнее.

scrypt например.

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

Ответить | Правка | ^ к родителю #41 | Наверх | Cообщить модератору

50. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Sw00p aka Jerom (?), 04-Мрт-16, 19:12 
> scrypt например.
> А хеш вместо шифра, т.к. по хешу значительно сложнее восстановить исходные данные,
> чем по шифру в ситуации, когда все "секреты" утекли.

https://ru.wikipedia.org/wiki/PBKDF2

раздел Использование


>>по хешу значительно сложнее восстановить исходные данные,

Это практически должно быть не возможно, вы о чём ?


Ответить | Правка | ^ к родителю #44 | Наверх | Cообщить модератору

55. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Аноним (-), 07-Мрт-16, 10:45 
>> scrypt например.
>> А хеш вместо шифра, т.к. по хешу значительно сложнее восстановить исходные данные,
>> чем по шифру в ситуации, когда все "секреты" утекли.
> https://ru.wikipedia.org/wiki/PBKDF2
> раздел Использование

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


>>>по хешу значительно сложнее восстановить исходные данные,
> Это практически должно быть не возможно, вы о чём ?

Да вот собственно об этом же. Даже получив доступ ко всем "секретам" это мало что даст злоумышленнику.

Ответить | Правка | ^ к родителю #50 | Наверх | Cообщить модератору

57. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Sw00p aka Jerom (?), 07-Мрт-16, 14:07 
>>А теперь то же самое, только с шифрованием.

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

Ответить | Правка | ^ к родителю #55 | Наверх | Cообщить модератору

58. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Sw00p aka Jerom (?), 07-Мрт-16, 14:10 
> чем по шифру в ситуации, когда все "секреты" утекли.

где с шифрованием утекли секреты ? я что в базе ключ от шифротекста храню ?

пс: Перечитайте все мои коменты!!!


Ответить | Правка | ^ к родителю #44 | Наверх | Cообщить модератору

43. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Аноним (-), 04-Мрт-16, 17:39 
>>>я не понял, к чему это
> значить нужно вам перечитать ссылку выше раздел "Частые вопросы о соли для
> новичков"

Может не будем таки говорить загадками? Накидать ссылок и я могу - сказать то что хотел?

Ответить | Правка | ^ к родителю #40 | Наверх | Cообщить модератору

46. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Sw00p aka Jerom (?), 04-Мрт-16, 17:54 
Выдержка из https://ru.wikipedia.org/wiki/PBKDF2

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

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

Ответить | Правка | ^ к родителю #43 | Наверх | Cообщить модератору

48. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Аноним (-), 04-Мрт-16, 18:45 
> Выдержка из https://ru.wikipedia.org/wiki/PBKDF2
> Одной из задач при создании PBKDF2 было усложнить перебор паролей. Благодаря множеству
> зацепленных вычислений PRF скорость генерации ключа является небольшой.
> пс: парадокс весь в том, что для одних целей хеш функция должна
> быть довольно быстрой, а для других (в частности к применимости к
> паролям) "якобы" должна быть медленной, чтобы избежать быстрого перебора паролей буээээээээээээээээээ.
> Зачем вся это костыльная сложность? Я не представляю что будет, если
> также и относится к алгоритмам шифрования. Если вас не устраивает хеш
> функция, - юзайте шифрование.

У меня складывается стойкое впечатление, что ты не до конца понимаешь, о чем говоришь. Каким боком стандарт формирования ключа, который, на секундочку, внутри использует хеш-функцию, имеет отношение к скорости алгоритма шифрования?

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

https://ru.wikipedia.org/wiki/Функция_формирования_ключа

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

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

Ответить | Правка | ^ к родителю #46 | Наверх | Cообщить модератору

51. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Sw00p aka Jerom (?), 04-Мрт-16, 19:34 
>>Еще раз - это "обертка" над хеш функцией, которая на основании парольной фразы генерирует ключ шифрования (один или несколько).

речь щас о хешировании? а то вы про хеш функцию начинаете а кончаете "генерирует ключ шифрования" - определитесь.

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

Ок, не понимание - не страшно, я хочу сконцентрироваться на изначальном треде - было высказано мнение "Хеш функции должны быть медленными" - я категорически против этого высказывания. Усложнить жизнь брутфорсеру можно всегда, и есть конкретные методы в данном случае привёл пример использования PBKDF2 она именно для этого и предназначена. В тоже время я предложил для усложнения использовать не хеш функцию, а конкретно какой либо алгоритм симметричного, а ещё лучше ассиметричного, шифрования. И вспыл такой вопрос, что и алгоритм шифрования так же быстро можно пробрутить. )))) Как и на скока быстро? Достаточно того, что (не буду точно утверждать) хеш функция быстрее вычисляется чем происходит шифрование (дешифрование) каким либо алгоритмом симметричного (асимметричного).

>>Спорить о способах хранения пароля в мои планы не входило - я знаю, что ты предлагаешь неправильный вариант, т.к. он основан на наличии секретной информации.

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

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

Не знание ключа шифрование так же заставит вас их брутить, или вы знаете метод как расшифровать.

Ответить | Правка | ^ к родителю #48 | Наверх | Cообщить модератору

56. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Аноним (-), 07-Мрт-16, 11:32 
>>>Еще раз - это "обертка" над хеш функцией, которая на основании парольной фразы генерирует ключ шифрования (один или несколько).
> речь щас о хешировании? а то вы про хеш функцию начинаете а
> кончаете "генерирует ключ шифрования" - определитесь.

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

>[оверквотинг удален]
> - было высказано мнение "Хеш функции должны быть медленными" - я
> категорически против этого высказывания. Усложнить жизнь брутфорсеру можно всегда, и есть
> конкретные методы в данном случае привёл пример использования PBKDF2 она именно
> для этого и предназначена. В тоже время я предложил для усложнения
> использовать не хеш функцию, а конкретно какой либо алгоритм симметричного, а
> ещё лучше ассиметричного, шифрования. И вспыл такой вопрос, что и алгоритм
> шифрования так же быстро можно пробрутить. )))) Как и на скока
> быстро? Достаточно того, что (не буду точно утверждать) хеш функция быстрее
> вычисляется чем происходит шифрование (дешифрование) каким либо алгоритмом симметричного
> (асимметричного).

Не все так однозначно:
$ openssl genrsa -out key.txt 512 > key.txt

$ time for i in {1..100000}; do echo "qwertyuiop" | openssl rsautl -inkey key.txt -encrypt > /dev/null; done

real    4m35.424s
user    2m21.907s
sys     1m51.257s


$ time for i in {1..100000}; do echo "qwertyuiop" | openssl sha1 -sha512 > /dev/null; done

real    4m27.662s
user    2m9.487s
sys     1m56.034s

Да, разница есть, но она несущественна. И это я еще не брал самый быстрый алгоритм шифрования и самую медленную хеш-функцию.

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

Да, коллизии есть, не спорю. И не спорю с тем, что даже соль тут кардинально ничего не изменит (она не для этого и используется). Т.е. чисто теоретически вполне возможно подобрать парольную фразу, которая с той же солью даст тот же хеш. Вопрос стоит в количестве трудозатрат на поиск такой коллизии. Да, гарантию, что пользователь ввел именно тот пароль никто не даст. Но ИМХО это все-таки надежнее, чем полагаться на неуязвимость других компонентов системы, которые в случае взлома могут привести к утечке всех "секретов" в случае использования шифрования. В случае хеша - что поиск пароля, что поиск коллизии - это все время и ресурсы. В случае шифрования пароля - утечка "секретов" сразу приводит к раскрытию паролей всех пользователей, и тут нет смысла сравнивать скорость хеширования со скоростью шифрования - дешифровать нам нужно каждый пароль по разу, а считать хеш - миллионы раз для каждого пароля.

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

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


Ответить | Правка | ^ к родителю #51 | Наверх | Cообщить модератору

30. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Sw00p aka Jerom (?), 03-Мрт-16, 18:44 
>но если ты сам не эксперт в криптографии, тебе всё равно никто не поверит.

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


Ответить | Правка | ^ к родителю #12 | Наверх | Cообщить модератору

47. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Orduemail (ok), 04-Мрт-16, 18:14 
> И опять таки - почему криптостойкие, а не просто с защитой от hashDoS атак?

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

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

Ответить | Правка | ^ к родителю #10 | Наверх | Cообщить модератору

15. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +1 +/
Сообщение от angra (ok), 03-Мрт-16, 15:10 
Во-первых, без злоумышленника она будет просто тормозить всегда по сравнению с некриптостойкой хеш-функцией.
Во-вторых, криптостойкие хеш-функции от некриптостойких отличаются в первую очередь не количеством коллизий, а сложностью восстановления исходных данные по хешу.
Ответить | Правка | ^ к родителю #8 | Наверх | Cообщить модератору

20. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от cebkaemail (?), 03-Мрт-16, 16:17 
Не знаю термина "криптостойкие" относительно хеш-функций, но, разумеется, ваше определение подходит к любой хеш функции - в общем случае исходные данные *невозможно* восстановить для любой хеш функции, т.к. пространство выходных значений всегда меньше пространства входных значений просто по определению хеш функции. А вот криптографические хеши отличаются от обычных тем, что *подобрать* к ним коллизию очень сложно для любых входных данных. Они потому и называются collision-resistant. Siphash НЕ является collision resistant хеш-функцией.
Ответить | Правка | ^ к родителю #15 | Наверх | Cообщить модератору

35. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от funny_falcon (ok), 03-Мрт-16, 21:29 
https://ru.wikipedia.org/wiki/%D0%9A%D1%...

Цитата:

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

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

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

Ответить | Правка | ^ к родителю #20 | Наверх | Cообщить модератору

36. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от funny_falcon (ok), 03-Мрт-16, 21:30 
Сорри, вот ссылка

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

Ответить | Правка | ^ к родителю #20 | Наверх | Cообщить модератору

31. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Sw00p aka Jerom (?), 03-Мрт-16, 18:48 
> в первую очередь не количеством коллизий, а сложностью восстановления исходных данные по хешу.

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


Ответить | Правка | ^ к родителю #15 | Наверх | Cообщить модератору

19. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +5 +/
Сообщение от cebkaemail (?), 03-Мрт-16, 16:12 
Переделал у себя на ассемблере: 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 версии без интринисков пока использовать не буду, хотя для моих задач она просто неприлично хорошо подходит.

Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

52. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от Анонон (?), 05-Мрт-16, 01:11 
Почему asm, а не Си+интринсики?
Ответить | Правка | ^ к родителю #19 | Наверх | Cообщить модератору

59. "Быстрая хеш-функция HighwayHash и развитие SipHash от Google"  +/
Сообщение от erthink (ok), 07-Мрт-19, 13:58 
Лучше поздно чем никогда.

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).

Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

Архив | Удалить

Рекомендовать для помещения в FAQ | Индекс форумов | Темы | Пред. тема | След. тема




Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

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