Есть ли надежный алгоритм хеширования?

Question

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

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

Answer 1

Единственной защитой от грубой силы является тот факт, что для грубой силы требуется чрезмерно много времени.

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

Answer 2

Все криптографические системы уязвимы для грубой силы. Еще один термин для этого - «банальная атака».

Простое объяснение хэширования заключается в том, что все используемые нами алгоритмы хэширования принимают входные данные бесконечного размера и имеют выход фиксированного размера. Это неизбежное столкновение, и для чего-то вроде sha256 требуется 2 ^ 256 операций, чтобы найти его естественным образом. У md5 () есть ярлык, делающий 2 ^ 39-ые операции по нахождению столкновения.

Одна вещь, которую вы можете сделать, чтобы укрепить свои пароли, это спрятать соль. Хэш пароля не может быть взломан до тех пор, пока его соль не будет получена. John The Ripper может быть предоставлен словарь, соль и пароль для восстановления хэшей паролей любого типа. В этом случае sha256 () и md5 () будут работать примерно одинаково. Если у злоумышленника нет соли, он должен будет сделать значительно больше догадок. Если ваш размер соли равен sha256 (32 байта), потребуется (dictionary size)*2^256 догадок, чтобы взломать один пароль. Это свойство солей является основой CWE-760 .

Answer 3

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

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

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

, поскольку хэш-функция H допускает ввод произвольного размера [0,1]^n и выводит постоянный вывод [0,1]^k, когда размер ввода превышает размер вывода :, n>k, обязательно есть несколько выходов, которые могут быть получены более чем один вход.

Вы можете визуализировать это с помощью квадрата, разделенного на 9 вспомогательных квадратов.

 0 | 0 | 0
 0 | 0 | 0
 0 | 0 | 0

это ваши 9 лунок. Мы нападающий грубой силы, у нас есть неограниченные шансы атаковать ... у нас есть неограниченное количество голубей ... но нам самое большее нужно 10, чтобы найти столкновение ...

после 4 пиджонов и хорошего алгоритма хеширования, устойчивого к столкновениям:

 P | 0 | 0
 0 | P | P
 0 | 0 | P

после 9 пиджонов:

 P | P | P
 P | P | P
 P | P | P

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

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

Answer 4

Если вы знаете, что пространство ввода достаточно мало, чтобы атака грубой силой была осуществима, то есть два варианта защиты от атак грубой силой:

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

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

(следует оригинальный ответ)

Любой дополнительный бит в выходном формате делает алгоритм в два раза сильнее против простой атаки методом перебора.

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

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

Answer 5

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

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

Если вы используете соленый пароль длиной 12–14 символов, предпочтительно хэшированный с помощью алгоритма sha2 (или его эквивалента), вы получите довольно безопасный пароль.

Подробнее здесь: http://www.codinghorror.com/blog/2007/10/hardware-assisted-brute-force-attacks-still-for-dummies.html

Answer 6

Рассмотрим вывод алгоритмов хеширования.

MD5 (128-битный) или SHA-1 (160-битный), безусловно, проще перебором, чем SHA-2 (224, 384 или даже 512-битный).

Конечно, могут быть и другие недостатки (как в MD5 или чуть меньше в SHA-1 ), которые значительно ослабляют алгоритм.