Найти $секрет в $a ==md5($b. $секрет)
Функция:
$a == md5($b . $secret);
- Вы можете выбрать $a и $b
- Ты не знаешь $секрет
- Вы получаете значение функции для выбранных вами значений $a и $b как true или false.
Есть ли лучшая атака, чем грубая сила, чтобы найти $secret в целом? Есть ли лучшая атака, чем грубая сила, чтобы найти $secret, используя функцию md5 PHP?
Из того, что я нашел в Интернете, я думаю, что нет, хотя md5 устарел для некоторые другие варианты использования. Так что просто для уверенности...
С уважением
3 answers
Если MD5 ведет себя как случайный оракул (это большое "если", см. Ниже), То исчерпывающий поиск по $secret является наилучшей возможной атакой - и, что более важно, каждое "предположение" о значении $secret ДОЛЖНО использовать запрос к функции (поскольку вы используете PHP, я предполагаю, что функция реализована на веб-сервере, и каждый "запрос" требует общения с этим сервером). Последнее подразумевается отсутствием информации, отправленной обратно злоумышленнику: злоумышленник не получает ничего, кроме одного бита (результат "True" или "False"). В частности, он не получает сам вывод MD5. Злоумышленник получит длинный поток неинформативных результатов "False", если он не попадет в правильный вывод MD5, либо по чистой случайности (вероятности 2-128, что на самом деле чертовски мало), или потому, что он правильно угадал значение $secret заранее. Стоит отметить, что это не позволяет злоумышленнику использовать многие методы совместного несения расходов, включая предварительно вычисленные таблицы, в частности чрезмерно раздутые радужные таблицы.
Случайный оракул - это мифический объект, который можно рассматривать как детерминированный черный ящик: вы знаете ничего на выходе, который вы получите от данного ввода, за исключением того, что поле всегда будет возвращать один и тот же результат для данного ввода. Модель следующая: в коробке находится гном, несколько кубиков и большая книга. Гном использует кости, чтобы случайным образом выбрать результат. Он также использует книгу, чтобы отслеживать ответы, которые он уже отправил, чтобы чтобы быть последовательным, т. Е. Если входные данные идентичны ранее отправленным входным данным, гном вернет тот же результат, что и ранее, вместо того, чтобы бросать кости.
MD5, однако, не случайный оракул. Например, мы можем создавать коллизии для MD5 намного быстрее, чем теоретические 264 сопротивление для функции со 128-битным выходом. Также обратите внимание, что хорошая хэш-функция (устойчивая к столкновениям и т. Д.) Не требует абсолютной "случайности". Для например, SHA-256 считается безопасной хэш-функцией, хотя она все еще страдает от так называемой "атаки на расширение длины" (учитывая SHA256($a), можно вычислить SHA256($a . $b), не зная $a, для почти произвольных значений $b). Таким образом, гарантии случайного оракула не соответствуют MD5 (или, если на то пошло, SHA-256). Это не означает, что известны более быстрые атаки! Только то, что вы здесь сами по себе.
Можно также указать, что md5($b . $secret) является своего рода "хэшем с ключом", т. Е. MAC (Код аутентификации сообщения). Создание MAC из хэш-функции непросто, именно из-за таких вещей, как атака на расширение длины (md5($secret . $b), например, был бы очень плохим MAC). Был разработан надежный способ построения MAC из хэш-функции; он называется HMAC и включает в себя два вызова базовой хэш-функции (но один из них находится на коротком входе, так что это, тем не менее, эффективно). Безопасность HMAC, точнее, как HMAC может быть считается, что он ведет себя как случайный оракул, может быть "доказан", т.Е. сведен к некоторым внутренним свойствам хеш-функции, которые считаются истинными в случае SHA-256 (см. Новые доказательства для NMAC и HMAC: Безопасность без сопротивления столкновению Михира Беллара для подробных сведений). Используя HMAC/SHA-256 поверх $b с $secret в качестве ключа, вы выиграете от этих результатов безопасности, и ваша конструкция будет более убедительно надежной. С другой стороны, я не утверждаю, что существует известная атака на md5($b . $secret), только то, что как использование MD5 , так и самодельная конструкция MAC поднимают красные флаги, которые снижают уровень доверия, который может быть передан такой системе.
Это интересный вопрос, потому что в типичных сценариях ИТ-безопасности вы не можете выбрать $a и $b в качестве злоумышленника. Если вы можете получить хэшированный пароль, например, $a и $b уже определены, и вам придется с этим работать. В этом случае вы можете использовать только грубую силу или радужную таблицу, если доступна таблица с солью $b.
С другой стороны, в вашем примере вы вольны выбирать оба значения. Вы можете взять произвольный секрет, например test и выберите значения для $a и $b соответственно. Я выбираю $b как empty string и вычисляю $a с помощью $a = md5($secret), что приводит к 098f6bcd4621d373cade4e832627b4f6.
Я выбираю $a = "098f6bcd4621d373cade4e832627b4f6" и $b= "" и спрашиваю вас, $secret == "test". Вы говорите "правда", а я говорю "проблема решена".
Это, наконец, приводит нас к реальному ответу. Два заданных условия
- Вы можете выбрать $a и $b
- Ты не знаешь $секрет
Не работайте вместе. В моем примере я сам определил $secret. Я нарушил второе условие. С другой стороны, я не могу выбрать $a и $b произвольно, не выводя их из $secret, потому что у них может не быть решения.
Если мы предположим, что существует хотя бы одно решение для всех возможных пар $a и $b (возможно, для этого есть доказательства, я не знаю), и вы выбираете их таким образом, что вы действительно не знаете $secret, я всегда хотел бы определить $b = "", чтобы сделать атаку как можно проще. Радужные столы - ваши друзья в этом случай.
Загрузите радужную таблицу /хэш пароля знаменитого пароля!:)