Рейтинг:2

Насколько сильным будет сочетание двух хэш-функций, таких как MD5 (SHA256 (ввод))?

флаг in

Если я попытаюсь сделать MD5 (SHA256 (ввод)), в чем сила этого так называемого подхода двойного хеширования?

Является ли он таким же сильным, как SHA256, или таким же сильным, как MD5, или таким же сильным, как SHA256 + MD5?

Кстати, это не вопрос домашнего задания, я задаю его из-за реальной проблемы в моем проекте. По праву мне нужно сделать только SHA256 (ввод) на входе и сохраните его в столбце в одной таблице MySQL. Но моя практическая проблема заключается в следующем: SHA256 имеет длину 64 при кодировании base64, но MD5 имеет длину 32 при кодировании base64. Мне нужен индекс для этого столбца. Будет ли MySQL работать лучше, если я использую MD5 (SHA256 (ввод)), потому что он короче (либо из-за более сжатого дерева B +, либо из-за меньшего размера, означающего меньше места для хранения)?


Редактирую сам: попробуйте подумать, что мы подразумеваем под «сильным» здесь? Это сопротивление прообразу или сопротивление второму прообразу?

флаг us
Подумайте о какой-нибудь другой хеш-функции, которая гораздо хуже справляется с коллизиями, чем MD5, — скажем, Hash(X) = 1... какова будет безопасность Hash(SHA256(X))? Та же логика применима и к этому вопросу.
fgrieu avatar
флаг ng
Хэш SHA-256 (соответственно MD5) _не_ имеет длину 64 (соответственно 32) при кодировании base-64.Использование двоичного файла в качестве ключа поиска не имеет _хороших_ ИТ-причин быть проблемой и имеет причины быть быстрее. Поскольку цели безопасности всей системы не указаны, мы не можем сказать, выполнены ли они. Я переоткрыл вопрос, но действительно: с чего бы это считать, со сломанным MD5? Почему не современный усеченный хэш?
kelalaka avatar
флаг in
[RIPEMD](https://en.wikipedia.org/wiki/RIPEMD) лучше использовать, чем MD5, который Биткойн уже использует RIPEMD-160.
kelalaka avatar
флаг in
Каков общий объем данных? Почему столкновение важно для вас? Почему нельзя использовать PRP, гарантирующий уникальность при условии, что данные уникальны? Ваша цель не ясна, чтобы дать полный ответ ... И часть дерева B + здесь не по теме.
dave_thompson_085 avatar
флаг cn
Помимо того факта, что хранение усеченного SHA256 так же хорошо с криптографической точки зрения, если вы хотите, вы можете хранить полный SHA256 и иметь MySQL _index_ только его префикс; см. руководство. Но это не криптография и оффтоп.
Рейтинг:3
флаг ng

Мы изучаем хэш $Ч$ определяется $H(м):=H_2(H_1(м))$, с SHA-256 для $H_1$ и MD5 для $H_2$.

сопротивление столкновению MD5 сильно нарушено, поэтому общий аргумент ¹, что сопротивление столкновению $Ч$ по крайней мере, самое слабое сопротивление столкновению $H_1$ и $H_2$ ведет нас в никуда.

Общий аргумент² о том, что сопротивление первому прообразу $Ч$ по крайней мере, $H_2$ работает в той мере, в какой мы доверяем прообразному сопротивлению MD5; который подвергается сомнению (см. это), но на практике не нарушается.

Единственное, что я могу придумать о сопротивлении второму прообразу $Ч$ заключается в том, что он не может быть лучше, чем сопротивление второго прообраза $H_1$. Это не дает гарантии безопасности, и, поскольку сопротивление второго прообраза SHA-256 считается хорошим, это также не дает атаки.


С прикладной точки зрения (о чем, похоже, и идет речь, поскольку в нем упоминается конкретное приложение) я не вижу, чтобы какие-либо из существующих криптоаналитических атак на MD5 или SHA-256 были актуальны.

  • Сопротивление столкновениям MD5 нарушено.Но короткий входной размер MD5 (256-битный выходной размер SHA-256 составляет только половину входного блока MD5) и жесткое ограничение, что этот ввод является хэшем, достаточны, чтобы сделать существующие атаки столкновений MD5 неприменимыми (ограничение тем намного лучше, чем грубая сила).
  • И SHA-256, и MD5 имеют нежелательный свойство расширения длины, но фиксированная длина входных блоков MD5 соответствует свойству MD5. И повторное хеширование вывода SHA-256 до блоков вдвое меньше, чем для SHA-256.

Таким образом, единственные криптографически значимые атаки, которые я вижу, — это атаки на идеальные хэши. $H_1$ и $H_2$ с соответствующей выходной шириной. С $H_2$ намного уже, чем $H_1$, атаки грубой силы ограничены шириной $H_2$ и соображений скорости. В частности:

  • Составной хэш вопроса имеет ширину всего 128 бит, поэтому коллизии могут отображаться примерно с $2^{66}$ оценки (как SHA-256, так и MD5) с использованием стандарта распределенный поиск столкновений. Я могу представить себе ситуации, когда это низкое сопротивление столкновению является проблемой (и не могу сказать здесь, это зависит от приложения).
  • Составной хеш нельзя использовать для растяжка ключей, что было бы необходимо для паролей, потому что это слишком быстро и не требует памяти. Однако нет никаких указаний на то, что растяжка клавиш является обязательным требованием.

В этом составном хэше отсутствует четкий аргумент безопасности, он не очень быстр, особенно для коротких вводов, и плох, по крайней мере, с точки зрения связей с общественностью, потому что MD5 не работает. Насколько я могу судить, это на практике примерно так же хорош, как любой умеренно быстрый 128-битный хеш может быть на всех технический точки зрения, в том числе неудовлетворительные по сопротивлению столкновению (но нет уверенности в том, что сопротивление столкновению является требованием в случае использования).Я не вижу причин использовать этот составной хеш, а не что-то более современное и безопасное, чем MD5, включая какой-нибудь (возможно, усеченный) SHA-2, или SHA-3 SHAKE128 с его настраиваемым размером вывода, или Blake2b (или Blake3 после того, как пыль осядет) .


¹ Предположите столкновение для $Ч$, это $(м,м')$ с $м\не м'$ и $Ч(м)=Ч(м')$. Мы можем вычислить $w=H_1(м)$ и $w'=H_1(m')$. Если $w=w'$, у нас есть коллизия для $H_1$. В противном случае мы имеем $H_2(ш)=H_2(ш')$ с $w\ne w'$, таким образом, столкновение для $H_2$. Таким образом, мы сломали сопротивление столкновению для $H_1$ или же $H_2$.

² Предложите алгоритм, находящий первый прообраз для $Ч$, это дано $ч$ найти $м$ такой, что $Ч(м)=ч$ с незначительной вероятностью и возможными усилиями. Мы можем вычислить $w=H_1(м)$ и это такое, что $ч=H_2(ш)$. Таким образом, мы построили метод нахождения первого прообраза для $H_2$ с той же немаловажной вероятностью успеха и практически с теми же усилиями, что и в гипотетическом алгоритме.

³ Алгоритм нахождения второго прообраза для $H_1$, это дано $м$ найти $m'\ne m$ такой, что $H_1(м)=H_1(м')$, также находит второй прообраз для $Ч$.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.