В вашем случае разрыв алгоритма hashа эквивалентен обнаружению столкновения в hash-алгоритме. Это означает, что вам не нужно искать сам пароль (который был бы атакой preimage ), вам просто нужно найти выход hash-функции, равный хешу действительного пароля (таким образом, «столкновение»). При обнаружении столкновения с использованием атаки на день рождения происходит O (2 ^ (n / 2)) время, где n – длина вывода hash-функции в битах.

SHA-2 имеет выходной размер 512 бит, поэтому для нахождения столкновения потребуется время O (2 ^ 256). Учитывая, что не существует умных атак на сам алгоритм (в настоящее время ни один из них не известен для hash-семейства SHA-2), это то, что нужно, чтобы сломать алгоритм.

Чтобы получить представление о том, что на самом деле означает 2 ^ 256: в настоящее время считается, что число атомов в (цельной !!!) вseleniumной составляет примерно 10 ^ 80, что составляет примерно 2 ^ 266. Предполагая, что вход в 32 байта (что разумно для вашего случая – 20 байт соли + 12 байт), моя машина занимает ~ 0,22 с (~ 2 ^ -2 с) для 65536 (= 2 ^ 16) вычислений. Таким образом, 2 ^ 256 вычислений были бы выполнены при расчетах 2 ^ 240 * 2 ^ 16, которые потребовались бы

 2^240 * 2^-2 = 2^238 ~ 10^72s ~ 3,17 * 10^64 years 

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

Поэтому забудьте о грубо-форсирующем SHA-256 здесь. Ваш следующий вопрос касался словарных слов. Для извлечения таких слабых паролей традиционно использовались радужные таблицы . Радужный стол, как правило, представляет собой таблицу предварительно вычисленных значений hashа, идея в том, что если вы смогли прекомпретировать и сохранить все возможные hashи вместе со своим вводом, тогда вам понадобится O (1), чтобы найти заданный хеш и получить действительный прообраз для него. Конечно, это невозможно на практике, поскольку нет устройства хранения, которое могло бы хранить такие огромные объемы данных. Эта дилемма известна как компромисс между памятью и временем . Поскольку вы можете хранить столько значений, что обычные радужные таблицы include в себя некоторую форму hash-цепочки с промежуточными функциями сокращения (это подробно объясняется в статье Википедии), чтобы сэкономить на пространстве, отказавшись от экономии времени.

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

Низкая энтропия типичных паролей позволяет обеспечить относительно высокую вероятность того, что один из ваших пользователей использует пароль из относительно небольшой базы данных общих паролей. Если вы Google для них, вы в конечном итоге найти ссылки торрент для таких баз паролей, часто в категории размера гигабайта. Успех такого инструмента обычно составляет от нескольких минут до нескольких дней, если злоумышленник не ограничен каким-либо образом.

Вот почему в целом недостаточно хеширования и соления, вам также необходимо установить другие механизмы безопасности. Вы должны использовать искусственно замедленный метод энтропии, такой как PBKDF2, описанный в PKCS # 5, и вы должны обеспечить период ожидания для данного пользователя, прежде чем они смогут повторить ввод своего пароля. Хорошая схема – начать с 0,5 с, а затем удвоить это время для каждой неудачной попытки. В большинстве случаев пользователи этого не замечают и не терпят неудачу гораздо чаще, чем три раза в среднем. Но это значительно замедлит любого злонамеренного аутсайдера, пытающегося атаковать ваше приложение.

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

Словарь паролей

Баллонная цифра : есть около 1 000 000 английских слов, и если хакер может вычислить около 10000 SHA-512 hashей второй ( обновление: см. Комментарий CodesInChaos, эта оценка очень низкая), 1,000,000 / 10000 = 100 секунд . Так что потребовалось бы чуть более минуты, чтобы взломать пароль слова с одним словом для одного пользователя. Если пользователь объединяет два словаря, вы находитесь в области нескольких дней, но все же очень возможно, если атакующий достаточно заботится. Более того, и это начинает становиться жестким.

Случайный пароль

Если пароль – это действительно случайная последовательность буквенно-цифровых символов, верхний и нижний регистр, то число возможных паролей длины N равно 60 ^ N (имеется 60 возможных символов). На этот раз мы сделаем расчет в другом направлении; мы спросим: какой длины пароля мы могли бы взломать с учетом определенного периода времени? Просто используйте эту формулу:

N = Log60(t * 10,000) где t – время, затрачиваемое на вычисление hashей в секундах (опять же, предполагая 10000 хешей в секунду).

 1 minute: 3.2 5 minute: 3.6 30 minutes: 4.1 2 hours: 4.4 3 days: 5.2 

Поэтому, учитывая 3 дня, мы сможем взломать пароль, если он длится 5 символов.

Это все очень шарик-парк, но вы получите эту идею. Обновление: см. Комментарий ниже, на самом деле можно взломать гораздо более длинные пароли, чем это.

Что тут происходит?

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

• Соль не замедляет вычисление hashей , это просто означает, что они должны взламывать каждый пользовательский пароль отдельно, а предварительно вычисленные hash-таблицы (buzz-word: rainbow tables ) становятся абсолютно бесполезными. Если у вас нет предварительно вычисленной hash-таблицы, и вы только взламываете один hash пароля, соление не имеет никакого значения.

• SHA-512 не предназначен для грубой силы . Более эффективные алгоритмы hashирования, такие как BCrypt, PBKDF2 или SCrypt, могут быть сконфигурированы так, чтобы они занимали намного больше времени, и средний компьютер мог бы вычислить только 10-20 hashей в секунду. Прочитайте этот отличный ответ о хешировании паролей, если вы еще этого не сделали.

• update: Как написано в комментарии CodesInChaos, даже высокие энтропийные пароли (около 10 символов) могут быть грубыми, если использовать правильное оборудование для вычисления hashей SHA-512.

Примечания к принятому ответу:

Принятый ответ на сентябрь 2014 года неверен и опасен неправильно:

В вашем случае разрыв алгоритма hashа эквивалентен обнаружению столкновения в hash-алгоритме. Это означает, что вам не нужно искать сам пароль (который был бы атакой с прообразом). Поиск столкновения с использованием атаки на день рождения занимает время O (2 ^ n / 2), где n – длина вывода hashа функция в битах.

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

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

Вот почему в целом недостаточно хеширования и соления, вам также необходимо установить другие механизмы безопасности. Вы должны использовать искусственно замедленный метод энтропии, такой как PBKDF2, описанный в PKCS # 5 …

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

На этот вопрос нет ни одного ответа, так как слишком много переменных, но SHA2 еще не взломан (см.: Время жизни криптографических хеш-функций ), поэтому он по-прежнему является хорошим алгоритмом для хранения паролей. Использование соль хороша тем, что предотвращает атаку со словарных атак или радужных таблиц. Важность соли заключается в том, что она должна быть уникальной для каждого пароля. При хранении хешированных паролей вы можете использовать формат, например [128-bit salt] [512-bit password hash].

Единственный жизнеспособный способ атаки – фактически вычислить hashи для разных возможностей пароля и в конечном итоге найти правильный, сопоставив хеши.

Чтобы дать представление о том, сколько hashей можно сделать за секунду, я думаю, что биткойн – достойный пример. Биткойн использует SHA256 и сокращает его, чем больше hashей вы генерируете, тем больше биткойнов вы получаете (которые вы можете торговать на реальные деньги), и поскольку у таких людей есть мотивация использовать графические процессоры для этой цели. Вы можете увидеть в обзоре аппаратного обеспечения, что средняя графическая карта, стоимость которой стоит всего 150 долларов, может вычислить более 200 миллионов хешей / с. Чем длиннее и сложнее ваш пароль, тем больше времени потребуется. Вычисляя при 200 М / с, чтобы попробовать все возможности для буквенно-буквенного символа с 8 символами (столица, ниже, цифры), потребуется около 300 часов. В реальном времени, скорее всего, меньше, если пароль является чем-то подходящим или общим английским словом.

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

Одна вещь, которую вы можете сделать, также добавляет дополнительную защиту от грубой силы, замедляя процедуру hashирования. Поскольку вы только hash-пароль один раз, и злоумышленник должен делать это много раз, это работает в вашу пользу. Типичный способ сделать это – принять значение, хеш его, вывести на выходе, hash снова и так далее для фиксированного количества итераций. Например, вы можете попробовать что-то вроде 1000 или 10000 итераций. Это заставит злоумышленника находить каждый пароль в несколько раз.