Что делает алгоритм хеширования «безопасным»?

19

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

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

CodexArcanum
источник
8
Этот вопрос лучше подходит для сайта IT Security SE.
Бернард
@Bernard Если это так, то я в порядке с этим, но мой вопрос был не о том, как и когда использовать безопасный хеш, а о том, что отличает алгоритм безопасного хеширования от небезопасного. Для меня это больше похоже на вопрос программирования, но я не просматриваю IT Security SE, так что, возможно, это тоже работает.
CodexArcanum
2
Очень похожий вопрос уже задавался по информационной безопасности
ChrisF

Ответы:

34

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

  • сопротивление прообразу : Учитывая h, что это должно быть трудно найти какое-либо значение xс h = H(x).

  • сопротивление второму прообразу : Учитывая x1, это должно быть трудно найти x2 != x1с H(x1) = H(x2).

  • сопротивление столкновению : должно быть трудно найти два значения x1 != x2с H(x1) = H(x2).

С хэш-функциями, которые используются в распространенных языках программирования для хеш-таблиц (строк), обычно ничего из них не дается, они обеспечивают только:

  • слабое сопротивление столкновению : для случайно (или «типично») выбранных значений домена вероятность столкновения мала. Это ничего не говорит о том, что злоумышленник намеренно пытается создать столкновение или пытается найти прообразы.

Три свойства, приведенные выше, являются (среди) целями разработки для каждой криптографической хеш-функции. Для некоторых функций (таких как MD4, SHA-0, MD5) известно, что это не удалось (по крайней мере, частично). Предполагается, что текущее поколение (SHA-2) является безопасным, а следующее («алгоритм безопасного хеширования 3») в настоящее время находится в процессе стандартизации после соревнования .

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

  • медленное выполнение : учитывая x, что для вычисления значения требуется некоторое минимальное (предпочтительно настраиваемое) количество ресурсов H(x).

Но для большинства других целей это нежелательно, вместо этого нужно:

  • быстрое выполнение : учитывая x, что вычисление значения H(x)выполняется максимально быстро (хотя все еще безопасно).

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

Для более подробной информации взгляните на хеш-тег на нашем дочернем сайте Cryptography Stack Exchange.

Пауло Эберманн
источник
3

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

Некоторые характеристики:

  • зная хеш, сложно создать файл, который хэширует это значение (вариант, указывается часть нового файла и желаемый хеш)

  • сложное построение двух разных файлов, хеш которых к одному и тому же значению (вариант, часть файлов указана)

AProgrammer
источник
3

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

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

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

Джерри Гроб
источник
3
В области криптографических хеш-функций есть две важные подгруппы: быстрая (используется для аутентификации сообщения, подписи и т. П.) И медленная - для получения ключа и хеширования пароля. Не смешивайте их, есть приложения для обоих.
Паŭло Эберманн
На самом деле, есть также хэш-функции, которые предназначены для максимизации коллизий: примером является Soundex. Очевидно, это делает его очень дрянной безопасной хеш-функцией.
Йорг Миттаг
@ JörgWMittag: не просто дрянной как безопасный хеш, но и очень плохой для использования с хеш-таблицей. С другой стороны, хотя это, конечно, несколько похоже на хэш, я не решался бы назвать Soundex хеш-функцией просто потому, что ее назначение и использование так сильно отличаются от обычных хеш-функций.
Джерри Коффин
@JerryCoffin: я думаю, это зависит от определения. Например, на странице английской Википедии просто говорится, что хеш-функция - это любой алгоритм или подпрограмма, которая отображает больший (потенциально бесконечный) набор произвольных значений в меньший, конечный набор (обычно скалярных) значений. Принимая во внимание, что на немецкой странице Википедии говорится, что «хеширование» (по-немецки «zerhacken») является неотъемлемой частью, т. Е. Что предотвращение столкновений и распределение отображаемых значений является ключевым. Soundex очень соответствует первому определению, но не второму.
Йорг Миттаг
3

Прочитайте это http://www.codinghorror.com/blog/2012/04/speed-hashing.html, это объяснит все гораздо лучше, чем я мог бы объяснить. Вот два самых важных заголовка в статье, которые непосредственно касаются вашего вопроса:

  • Безопасные хэши разработаны так, чтобы быть защищенными от несанкционированного доступа
    • радикально меняет свой вывод с крошечными однобитными изменениями во входных данных
  • Безопасные хеши разработаны так, чтобы быть медленными

Его раздел TL; DR в конце:

Если вы пользователь:

Убедитесь, что все ваши пароли 12 или более символов, в идеале намного больше. Я рекомендую использовать парольные фразы, которые не только намного легче запомнить, чем пароли (если не тип), но и смехотворно защищены от перебора просто из-за их длины.

Если вы разработчик:

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

Nate
источник
4
Джефф ошибается здесь во втором пункте ... в то время как для некоторых целей (например, для хеширования пароля и получения ключа из пароля) вы хотите быть медленным, для других целей (таких как аутентификация сообщений, подписи и т. Д.) Быстрым (безопасным) хэш-функции хороши.
Паŭло Эберманн
Вы правы, Paŭlo. Производительность хэша зависит от применения хэша. Однако медленные хэши всегда более безопасны, чем быстрые. Причина, по которой вы бы использовали быстрый хеш, заключается в том, что вы жертвуете безопасностью ради производительности.
Nate
2
@Nate «Более безопасный» всегда неоднозначен, но даже в самом благотворительном приложении «медленные хэши всегда более безопасны, чем быстрые», безусловно, неправильно. Существует множество приложений, где скорость хэша не имеет значения.
Жиль "ТАК ... перестать быть злым"
@ Жиль, можешь привести пример? Это на самом деле звучит правдоподобно для меня, но больше подробностей будет полезно.
Nate
2
@Nate Наиболее очевидным применением хэшей является проверка целостности фрагмента данных: передайте хеш по безопасному каналу, но, возможно, с низкой пропускной способностью, передайте, возможно, большую полезную нагрузку по небезопасному каналу, затем проверьте, что полученная полезная нагрузка имеет ожидаемую хэш. Хэши также занимают важное место в методах подписания (где вы проверяете не только целостность, но и отправителя данных). Хэширование паролей является скорее исключением.
Жиль "ТАК - перестать быть злым"
2

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

Хеш обычно считается «безопасным», если с учетом сообщения M, хеш-функции hash () и хеш-значения H, созданного хешем (M) с длиной в битах L, ни одно из следующего не может быть выполнено менее чем за O (2 л ) время:

  • Учитывая hash () и H, производим M. (сопротивление прообразу)
  • Учитывая hash () и M, создайте другой M 2 такой, что hash (M 2 ) == H. (слабое сопротивление столкновению)
  • Учитывая hash (), выведите любые M 1 и M 2 такие, что hash (M 1 ) == hash (M 2 ). (сильное сопротивление столкновению)

Кроме того, «защищенный» хеш должен иметь длину хеша L, такую ​​что 2 Lне является допустимым числом шагов для компьютера для выполнения данного текущего оборудования. Хэш 32-битного целого может иметь только 2,1 миллиарда значений; в то время как атака с прообразом (поиск сообщения, генерирующего определенный хэш H) займет некоторое время, для многих компьютеров это становится недопустимым, особенно для тех, которые находятся в руках правительственных учреждений, застрахованных от взлома кода. Кроме того, алгоритм, который создает и хранит случайные сообщения и их хэши, будет, по всей вероятности, иметь 50% вероятности найти дублирующийся хэш с каждым новым сообщением после попытки только 77 000 сообщений и иметь 75% -ную вероятность попадания в дублировать только после 110 000. Даже 64-битные хэши все еще имеют 50% -ную вероятность столкновения после попытки только около 5 миллиардов значений. Такова сила атаки на маленькие хеш-коды. В отличие отдесятичные числа (1,5 * 10 34 ).

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

В дополнение к небольшому размеру хэша, другие факторы, которые могут сделать хэш явно небезопасным:

Низкая работа - хеш, предназначенный для использования хеш-таблицей или для других целей типа «контрольной суммы», обычно разрабатывается как недорогой в вычислительном отношении. Это делает атаку грубой силой намного проще.

«Sticky State» - функция хеширования склонна к шаблонам ввода, где текущее хешированное значение всех входных данных до сих пор не изменяется при задании определенного дополнительного байта ввода. Наличие «закрепленного состояния» облегчает обнаружение коллизий, потому что, как только вы идентифицируете сообщение, которое создает хеш «застрявшего состояния», тривиально генерировать другие сообщения, которые имеют такой же хеш, добавляя входные байты, которые сохраняют хеш в «закрепленном состоянии». ».

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

Keiths
источник
0

Используйте правильный алгоритм для поставленной задачи.

CRCs используются для обнаружения / исправления ошибок.

Дайджесты криптографических сообщений, такие как SHA2, используются в качестве строительного блока для криптографических конструкций (цифровые подписи, MAC, функции получения ключей / хеширования паролей) и протоколов безопасности.

В хеш-таблицах / словарях / картах используйте SipHash .

То, что вы называете небезопасными алгоритмами хеширования, не должно использоваться в хеш-таблицах , что подтверждается следующими записями CVE: CVE-2003-0364, CVE-2011-4461, CVE-2011-4838, CVE-2011-4885, CVE-2011- 4462, CVE-2011-4815, CVE-2012-0840, CVE-2012-5371 , CVE-2012-5374, CVE-2012-5375

Эрван Легран
источник