Во-первых, вы не говорите о столкновении .Столкновение - это когда кто-то находит два различных сообщения, которые хэшируются с одинаковым значением.Здесь вы не боитесь, что кто-то найдет другой вход, который хэширует значение, которое вы публикуете;действительно, вы боитесь, что кто-то найдет ваш вход.Правильный термин - прообразная атака .Иногда мы говорим, что злоумышленник пытается «инвертировать» хеш-функцию (найти вход, соответствующий заданному выводу).
Есть два способа попытаться найти прообраз для заданного хеш-значения: использоватьСлабость хеш-функции, или угадать ввод, проверяя кандидатов.
Не существует известной слабости SHA-2 в отношении сопротивления прообразам.Приходите к этому, нет такой известной слабости для MD5 или даже MD4, хотя эти две функции, как говорят криптографически, полностью нарушены.Поэтому, за исключением колоссальных достижений в научных исследованиях хеш-функции, есть вероятность, что ваше хеш-значение не будет найдено из-за слабой криптографической функции хеш-функции.
Попытка кандидатов может быть возможной или нет, в зависимости от того, что знает злоумышленникввода.Это довольно сложно точно моделировать.Предположим, например, что ввод представляет собой одно слово, содержащее семь букв.Всего таких слов 26 7 = 8031810176.Испытание всех из них с SHA-256, сравнение каждого раза с вашим значением хеш-функции, занимает несколько минут на последнем ПК с наивной реализацией.
В более общем плане, исследуя набор возможных входных данныхназывается атака по словарю , потому что она часто применяется к проблеме восстановления пароля пользователя: пользователи удручающе невообразимы и часто выбирают пароли из ограниченного набора, ну, в общем, «слов», и это кажется логичным дляНазовите «словарь» этот набор слов.Мы также называем это «грубой силой» или «исчерпывающим поиском».
Если предположить, что словарь достаточно мал для того, чтобы злоумышленник реально опробовал все его слова, то не только ваше хеш-значение будет в конечном итоге инвертировано (еслиу злоумышленника достаточно стимула), но это также открывает путь для распределения затрат : злоумышленник может попытаться разделить свои вычислительные усилия на несколько похожих ситуаций атаки (т. е. несколько хеш-значений для инвертирования с одинаковымихэш-функция - снова общая модель атаки, связанная с паролями).Основной метод разделения затрат - создать предварительно вычисленную таблицу : атакующий вычисляет все хэши для своего словаря , один раз ;затем все последующие хеш-значения можно атаковать, просто просматривая хеш-значение в таблице.Поиск выполняется очень быстро (атакующий сортирует свои хэши в порядке возрастания). Радужные таблицы являются своего рода предварительно вычисляемой таблицей, разумным способом, которая обеспечивает компактное представление: они позволяют злоумышленнику "хранить" большую предварительно вычисленную таблицу без необходимости загружать жесткие диски.Тем не менее, радуга или нет, все значения в таблице (одно до сжатия в случае радужной таблицы) должны быть вычислены, по крайней мере, один раз злоумышленником где-то, то есть кто-то может сделатьполная атака по словарю.Это имеет две стоимости: стоимость процессора (для вычисления всех хэшей) и стоимость хранения (для хранения хэш-значений).Радужный стол удешевляет хранилище, но не улучшает работу процессора.
Salting побеждает предварительно вычисленные таблицы (включая радужные таблицы).Это делает небольшие словари более терпимыми.То есть, если мы предположим, что инвертирование одного хеш-значения выполнимо, то соль гарантирует, что не менее злоумышленнику придется оплатить полную стоимость ЦП при атаке по словарюкаждый раз, и он не сможет разделить свои затраты на несколько атак или с другими злоумышленниками.Для паролей требуется засоление, потому что оказалось невозможным, в общем, заставить общих пользователей выбирать и запоминать пароли из достаточно большого набора возможных паролей.
Все равно будет намного лучше, если ваш вводиз словаря, достаточно большого, чтобы победить одно грубое усилие.Важной вещью является размер набора значений, который может принимать ваша входная строка;этот набор должен быть оценен относительно того, что злоумышленник знает о атакованных данных.Например, если злоумышленник пытается найти пароль пользователя, он знает, что строка ввода короткая (у пользователей мало терпения) и состоит только из символов, которые можно вводить (вслепую!) С клавиатуры;и он также знает, что последовательность может быть запомнена, что делает такие вещи, как ".% f * (. ds / ~ \ d09j @" весьма маловероятными. По сути, нет никаких ограничений на размер ввода; мы говорим, что радужные таблицы ограниченыдо «15 символов или около того», потому что пользователи, которые разрешают вводить более 15 символов, также будут выбирать пароли из слишком большого набора, чтобы разрешить одно грубое усилие, необходимое для построения таблицы. Обратите внимание, что при попытке всех последовательностей15 символов - это уже слишком много (даже все последовательности из 15 строчных букв подразумевают более 2 70 хеш-вычислений, а в современных технологиях это неосуществимо).