Возможный дубликат:
md5-декодирование. Как они это делают?
эта страница предполагает, что алгоритм хэша, такой как md5 () и sha1 (), может быть отменен из-за огромной вычислительной мощности, которую мы имеем в настоящее время. В этот момент я смог это сделать только с Rainbow Tables. Был ли я неправ?
В случае, если Rainbow Tables – единственный способ пойти, как кто-то может изменить хэш, который был сделан с солью?
Ну, этот вопрос в целом является дубликатом этого вопроса . Однако, чтобы ответить на ваши точные вопросы:
В этот момент я смог это сделать только с Rainbow Tables. Был ли я неправ?
Технически, да, вы ошибаетесь. Никакая функция хэша не восстанавливается, учитывая достаточную вычислительную мощность. Ключевым моментом является то, сколько процессорной мощности требуется, что в большинстве случаев намного больше, чем вы можете себе представить. Причина в том, что количество возможных значений экспоненциально возрастает на каждом этапе хеш-цикла. Для MD5 каждый этап (из них 64) будет умножать количество возможностей на 10 ^ 77 (много нулей). Таким образом, чтобы успешно сменить MD5, вам нужно попробовать действительно большое количество возможных перестановок (расчет на основе обратного конверта показывает где-то порядка 10 ^ 4932 попыток). С самым быстрым суперкомпьютером, когда-либо созданным сегодня (около 8 петафлоп, или 8×10 ^ 15 операций с плавающей запятой в секунду), вы смотрите примерно на 10 ^ 4908 лет, чтобы отменить его. Который, кстати, в 2.5×10 ^ 4898 раз больше возраста вселенной прямо сейчас. Действительно, это огромное количество, которое превосходит наши человеческие способности постигать …
И это абсолютно возможная ситуация.
Так что технически можно отменить. Но практически, нет, это не так.
В случае, если Rainbow Tables – единственный способ пойти, как кто-то может изменить хэш, который был сделан с солью?
Дело в том, что никто не должен его менять. Им просто нужно найти столкновение. В принципе, столкновение – это два входа, которые приводят к одному и тому же выводу. Поэтому, если hash(a) = x и hash(b) = x , a и b являются столкновениями друг с другом. Итак, все, что нам нужно сделать, это найти столкновение (которые считают, что это или нет, проще, чем поиск точного ввода, поскольку существует технически бесконечное количество входов, которые могут дать определенный выход). При вводе размера паролей обычно столкновение является исходным паролем.
Самый простой способ найти это столкновение – это предварительно вычисленный список хешей (обычно называемый радужной таблицей). В основном все, что вам нужно сделать, – это посмотреть хэш в таблице, чтобы увидеть, есть ли оригинал. Если это так, вы закончите (это легко).
Соли обычно добавляются для борьбы с радужными столами. Это связано с тем, что если пользователь вводит 1234 качестве своего пароля, и вы используете abcdefghijklmnop в качестве соли, оригиналом будет 1234abcdefgjhijklmnop , что значительно меньше шансов появиться в радужном столе. Поэтому добавление сильной соли защитит от предварительно вычисленных радужных столов.
Жестокое принуждение
Однако есть серьезная проблема, если вы просто делаете hash(pass + salt) . Он не восприимчив к предварительно вычисленным радужным таблицам, но он восприимчив к грубому форсированию. Причина в том, что криптографические хэш-функции (такие как sha1, md5, sha256 и т. Д.) Предназначены для быстрой работы. Их традиционная роль заключается в подписании , поэтому они должны быть быстрыми, чтобы быть полезными. Однако в хранилище паролей это слабость. С помощью современных графических процессоров злоумышленник может использовать грубую силу (просто попробовать всевозможные перестановки пароля) простой хеш с солью в течение нескольких часов (более подробно см. Статью в блоге об этом) …
Лучшая профилактика
Лучшая профилактика имеет две особенности:
Непросто предварительно вычислить таблицу значений (радужный стол)
Это не быстро для хэша одно значение (не так легко грубой силы).
Как оказалось, есть простой способ сделать это с помощью хэш-функции. Просто перебирайте его и делайте вывод зависимым от большого числа хеш-функций:
var result = password + salt; for (var i = 0; i < 10000000; i++) { result = hash(result + salt); }
Ключ заключается в том, что, делая искусственно медленным и используя соль, вы делаете ее устойчивой к предвычислению и жестокому форсированию.
Как оказалось, есть 2 стандартных алгоритма, которые делают это (ну, используйте принципы).
Лучший из них – хеш Blowfish (bcrypt), который на самом деле не использует примитивную функцию хэша, но использует цикл деления ключей в шифре Blowfish. Он доступен в PHP через crypt() . Чтобы использовать его:
$hash = crypt($password, '$2a$07$' . $salt . '$');
И подтвердите это с помощью
$hash == crypt($password, $hash);
Другим способом (который немного менее предпочтительным) является PBKDF2 . Чтобы запрограммировать его в PHP:
function pbkdf2($hashFunc, $password, $salt, $iterations, $length = 32) { $size = strlen(hash($hashFunc, '', true)); $len = ceil($length / $size); $result = ''; for ($i = 1; $i <= $len; $i++) { $tmp = hash_hmac($hashFunc, $salt . pack('N', $i), $password, true); $res = $tmp; for ($j = 1; $j < $iterations; $j++) { $tmp = hash_hmac($hashFunc, $tmp, $password, true); $res ^= $tmp; } $result .= $res; } return substr($result, 0, $length); }
Заметка:
Ни один из них не защитит пользователя от очень слабого пароля. Если они вводят словарное слово или общий пароль, все равно вероятнее всего, что злоумышленник сможет его взломать. Тем не менее, они добавят защиты от умеренных прочных паролей …
Еще немного чтения:
Радужный стол – это «просто» большая таблица предварительно вычисленных значений хеша с некоторым обманом, чтобы хранить только небольшую часть таблицы и все еще иметь возможность искать все значения. В тонких деталях радужная таблица, которая может «инвертировать» N возможных значений (т. Е. Есть N хэш-выходов, для которых таблица даст соответствующий вход), требует времени около 1,7 * N для сборки, поэтому построение таблицы на самом деле медленнее, чем «просто» опробовать N входов и посмотреть, соответствует ли данный хэш-выход. Преимущество таблицы заключается в том, что у вас есть несколько хэш-выходов, для которых вы хотите найти соответствующий вход.
Возможно, вы могли бы использовать следующую атаку, применяя технику, используемую для создания хэша, – это простой расчет.
Например, если расчет будет выполнен с модульным хешем в 100, мы имеем:
Пример ввода: 8379547378 Выходной хеш: 78
Общая формула для хэш-значения 78 будет 78 + 100 * k (k, принадлежащих целым числам). Таким образом, можно попробовать все возможные последовательности. Обратите внимание, что это уменьшает пространство поиска от 100% до 1% в этом случае модуля 100. Если бы можно было установить догадку, что это число было 10 цифр, мы могли бы сделать поиск еще более уменьшенным до 78 +100 к (10 ^ 7 <= k <10 ^ 8).
Другой способ – заполнить базу данных множеством действительно больших хэшей и их входов, а затем выполнить поиск в этой базе данных.
Надеюсь, я немного помог.
Технически любые стандартные алгоритмы хэширования не обратимы! поэтому, как только вы получите хэш сообщения, не должно быть способа получить исходное сообщение из его хэш-строки. Единственный способ, с помощью которого люди пытаются взломать его, – использовать атаку грубой силы. Жестокое форсирование – это самая глупая вещь, которую вы можете сделать, пробуя все возможные ключи! Это объясняет, почему одной из характеристик безопасного криптографического алгоритма является наличие большого пространства ключей. Но если вы используете процесс в некоторых случаях, это может быть практичным, вот что делают таблицы радуги.
Радужный стол представляет собой предварительно вычисленный стол для всех возможных комбинаций до определенной длины. Это означает, что вы создаете все возможные комбинации символов (верхний регистр и строчный регистр), цифры и специальные символы до определенной длины. Насколько я знаю, самая полная таблица радуги может ломать хэш строк до 10 символов, которые включают числа, прописные и специальные символы, поэтому, если у вас есть строка дольше, то не должно быть никаких опасений по поводу нарушения самого хэша. как вы можете видеть здесь, размер таблицы, которая может сломать пароли vista до 8 символов, составляет более 100 ГБ, и это число увеличивается экспоненциально, что делает невозможным дальнейшее продвижение на 10 или 12 символов.
Пока ваша строка нелегко угадать, достаточно длинная и содержит буквы верхнего регистра, цифры и специальные символы, нет необходимости беспокоиться 🙂
Во-первых, в общем случае невозможно «перевернуть» криптографическую хэш-функцию. Это связано с тем, что эти функции обычно принимают гораздо больше входных данных, чем выводятся.
Например, MD5 принимает 512 входных битов (64 байта) и производит вывод на 128 бит (16 байт). Таким образом, во входном файле просто недостаточно информации для восстановления вывода. Фактически, будет около 2 ^ 384 ( действительно большое количество) разных входов, которые имеют точно такой же хэш-выход.
Вместо этого криптографы говорят о трех различных видах атак на хэши:
Теперь вернемся к этому «реверсивному» бизнесу. Когда вы хотите «разорвать пароль MD5», то, что вы действительно хотите сделать, это первая атака с прообразом: найдите любой «пароль» m, чтобы хэш (m) соответствовал сохраненному хэшу h. Обычно это займет порядка 2 ^ 128 догадок, выполняемых грубой силой (больше, чем все компьютеры на Земле могли бы справиться через столетие). Существуют известные слабости в MD5, которые сводят это к ~ 2 ^ 123, что по-прежнему слишком сложно, чтобы быть практичным.
Но поскольку пароли, как правило, представляют собой короткие строки букв и цифр, существует гораздо меньше, чем 2 ^ 128 паролей, которые люди действительно могут использовать. Там больше, чем 2 ^ 40 (т. Е. Около триллиона). Это все еще много, но не так много, что их невозможно попробовать, если у вас есть год или около того, или много PS3. Но что, если бы вы знали, что хотите разбить много паролей? Вместо того, чтобы делать 2 ^ 40 догадок каждый раз, вы можете хранить хэши всех вероятных паролей на диске для будущего использования. Это (более или менее) то, что представляет собой стол радуги: кто-то уже выполнил всю работу, чтобы просто найти ответ и пропустить большую часть работы.
Вы правы, что с использованием соляных перерывов. Теперь вы снова вернетесь к 2 ^ 40 догадкам и своей комнате PS3. Использование лучшей хеш-функции (например, SHA512 или SKEIN) на самом деле не изменяет это, потому что оно не изменяет количество вероятных паролей, которые вам нужно попробовать. Урок: вам нужно использовать очень трудно угадать пароль!
Хорошо, но не MD5 и SHA1 все еще считаются сломанными? Да, но не так, как это действительно важно (пока). Увлекательные новости в этой области касались коллизионных атак , которые имеют отношение к разрыву частей безопасности SSL и цифровых подписей, но не имеют отношения к нарушению сохраненных паролей. Криптографы ожидают, что эта работа приведет к еще более быстрым атакам, поэтому, вероятно, не рекомендуется использовать MD5 или SHA1 в новых программах, но программы, которые используют MD5 / SHA1 +, правильно засовывают для хранения паролей, все еще прекрасны.
Оскорбительная толчка, о которой идет речь, – это, в основном, создание радужного стола на лету.