Есть ли способ отменить хэш без радужных таблиц?
Возможный дубликат:
декодирование md5. Как они это делают?
эта страница предполагает, что алгоритм хэширования, такой как md5() и sha1(), может быть обращен вспять из-за огромной вычислительной мощности, которой мы располагаем в настоящее время. На данный момент я думал, что это возможно только с Rainbow Tables. Был ли я не прав?
В случае, если Rainbow Tables - единственный путь, как кто-то может изменить хеш, который был сделан с солью?
6 ответов
Ну, этот вопрос в целом является дубликатом этого вопроса. Однако, чтобы ответить на ваши точные вопросы:
На данный момент я думал, что это возможно только с Rainbow Tables. Был ли я не прав?
Технически, да, вы не правы. Ни одна хеш-функция не подлежит восстановлению при достаточной вычислительной мощности. Ключевым моментом является то, сколько вычислительной мощности требуется, что в большинстве случаев намного больше, чем вы можете себе представить. Причина в том, что число возможных значений увеличивается экспоненциально на каждой стадии цикла хеширования. Для MD5 каждый этап (их 64) умножил бы количество возможностей на 10^77 (много нулей). Таким образом, чтобы успешно перевернуть MD5, вам нужно попробовать действительно большое количество возможных перестановок (вычисление обратной оболочки показывает где-то порядка 10^4932 попыток). С самым быстрым суперкомпьютером, когда-либо созданным сегодня (около 8 петафлопс, или 8x10^15 операций с плавающей запятой в секунду), вам нужно примерно 10^4908 лет, чтобы обратить его вспять. Что, кстати, сейчас в 2.5x10^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);
}
Замечания:
Ничто из этого не защитит пользователя от очень слабого пароля. Если они введут словарное слово или общий пароль, вероятно, злоумышленник сможет его взломать. Однако они добавят защиту от паролей средней надежности...
Еще немного чтения:
Во-первых, как правило, невозможно "обратить" криптографическую хеш-функцию. Это связано с тем, что эти функции обычно принимают гораздо больше входных данных, чем выводят.
Например, MD5 принимает 512 входных бит (64 байта) и выдает 128-битный выход (16 байтов). Таким образом, на входе просто недостаточно информации для восстановления выходных данных. Фактически, будет приблизительно 2^384 (действительно большое количество) различных входных данных, которые имеют точно такой же выходной хэш.
Вместо этого криптографы говорят о трех различных видах атак на хэши:
- Первая атака с прообразом: с учетом хэша h найдите любое сообщение m такое, что hash(m) = h
- атака второго прообраза: для фиксированного сообщения m1 найдите любое другое сообщение m2, такое что hash(m1) = hash(m2)
- атака столкновением: найдите любые два сообщения m1 и m2, такие что hash(m1) = hash(m2)
Теперь вернемся к этому "движению вспять". Если вы хотите "взломать пароль MD5", то вы действительно хотите сделать первую атаку с прообразом: найдите любой "пароль" m такой, что hash (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 + надлежащую защиту для хранения паролей, все еще в порядке.
Возможно, вы могли бы использовать следующую атаку, применяя технику, используемую для создания хеша, это простой расчет.
Например, если вычисление будет выполнено с модульным хешем в 100, мы имеем:
Пример ввода: 8379547378 Хэш вывода: 78
Общая формула для значения хэш-функции 78 будет 78 +100*k (k принадлежит целым числам). Таким образом, можно попробовать все возможные последовательности. Обратите внимание, что это сокращает пространство поиска со 100% до 1% в этом случае модуля 100. Если бы можно было догадаться, что это число было 10 цифрами, мы могли бы сделать поиск еще более сокращенным до 78 +100 k (10^7<=k< 10^8).
Другим способом было бы заполнить базу данных множеством действительно больших хешей и их входов, а затем выполнить поиск в этой базе данных.
Надеюсь, я немного помог.
Радужная таблица - это "просто" большая таблица предварительно вычисленных значений хешей с некоторыми хитростями, чтобы хранить только небольшую часть таблицы и при этом иметь возможность поиска всех значений. В деталях, радужная таблица, которая может "инвертировать" N возможных значений (т. Е. Есть N выходов хеш-функции, для которых таблица будет выдавать соответствующий вход), занимает около 1,7*N времени для построения - поэтому создание таблицы на самом деле медленнее, чем "просто" опробовать N входных данных и посмотреть, соответствует ли один заданному выходному хешу. Преимущество таблицы заключается в том, что у вас есть несколько хеш-выходов, для которых вы хотите найти совпадающий вход.
Технически любые стандартные алгоритмы хеширования необратимы! поэтому, как только вы получите хеш сообщения, не должно быть способа извлечь исходное сообщение из его строки хеша. Единственный способ, которым люди пытаются его взломать, - это использовать атаку грубой силой. Грубое принуждение - самая глупая вещь, которую вы можете сделать, испробовав все возможные ключи! Это объясняет, почему одной из характеристик безопасного криптографического алгоритма является наличие большого пространства ключей. Но если вы используете процесс в некоторых случаях, он может быть практичным, именно так и поступают радужные столы.
Радужный стол - это предварительно вычисленный стол для всех возможных комбинаций до определенной длины. Это означает, что вы создаете все возможные комбинации символов (прописные и строчные), цифр и специальных символов до определенной длины. Насколько я знаю, самая полная радужная таблица может разбить хеш строк до 10 символов, которые включают цифры, заглавные и специальные символы, поэтому, если у вас строка длиннее этой, не должно быть никаких проблем с безопасностью при разрыве самого хеша. как вы можете видеть здесь, размер таблицы, которая может взламывать пароли Vista до 8 символов, превышает 100 ГБ, и это число увеличивается в геометрической прогрессии, что делает невозможным дальнейшее развитие этих 10 или 12 символов.
Пока ваша строка не легко угадать, она достаточно длинная и содержит заглавные буквы, цифры и специальные символы, поэтому вам не о чем беспокоиться:)
Грубое принуждение, о котором идет речь на этой странице, - это в основном создание радужного стола на лету.