Спецпроекты

Интернет Безопасность Бизнес Веб-сервисы

Взлом алгоритмов хеширования: смерть e-commerce?

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

Сначала в сети появились сообщения о наличии уязвимости в алгоритме md5, затем и в алгоритме sha-1. Поскольку эти два алгоритма являются самыми используемыми в современных системах защиты данных, сообщения вызвали бурную реакцию. Обсуждение этих новостей можно найти практически на любом форуме по тематике, близкой к теме защиты информации. Иногда в них встречаются фразы вроде "конец электронной коммерции", "теперь любой может подобрать пароль", "все пропало". Некоторые специалисты же заявляют, что при правильном подходе эти уязвимости безопасны. Так ли все на самом деле?

Алгоритмы хеширования

Алгоритм хеширования - математическое преобразование, с помощью которого для строки практически любой длины рассчитывается число фиксированной длины. Для md5 длина полученного числа составляет 128 битов, для sha-1 – 160 битов. Очевидно, поскольку для длинной строки рассчитывается одно относительно короткое число, много последовательностей символов будут иметь одинаковое значение хеш-функции.

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

Существенно более простой задачей является нахождение двух произвольных строк, имеющих одинаковый хеш. Хочется подчеркнуть различие двух задач – в первом случае мы по заданному значению хеш должны найти соответствующую строку, во втором - найти две строки, имеющие любой хеш, но он должен быть у них одинаковым. Вторая задача несравненно проще, тем не менее, для хорошего алгоритма и она практически нерешаема.

Свойства хеш-функций и определяют их области использования. Перечислим некоторые важные из этих областей. Многие операционные системы на жестком диске хранят не пароли пользователей, а значение их хеш–функций. Таким образом, если злоумышленнику удалось получить доступ к ним, вероятность найти пароли будет достаточно мала. А когда пользователь вводит пароль, посчитать значение хеш–функции и сравнить с хранимой достаточно просто. В этом приложении используется свойство сложности восстановления строки по значению хеш-функции для этой строки.

Еще одно использование хеш–функций - для контроля неизменности файлов на диске или при передаче по сети. Для каждого файла рассчитывается значение хеш–функции, и это значение хранится или передается отдельно. Если возникает подозрение, что файл был модифицирован, можно еще раз посчитать для него криптографические контрольные суммы и, сравнив их с хранящимися, проверить такое предположение. Считается, что злоумышленнику практически невозможно модифицировать файл таким образом, чтобы его криптографическая контрольная сумма не изменилась. В этом приложении используется свойство сложности подбора последовательности символов, значение хеш-функции для которой совпадало бы со значением хеш-функции для другой, заранее заданной последовательности.

И последний пример использования, который мы рассмотрим в этой статье – хеш–функции в электронных подписях. А именно, рассчитанная для данного документа хеш–функция, зашифрованная на закрытом ключе пользователя, является основой электронной подписи. При проверке электронной подписи документа для него рассчитывается значение хеш-функции и сравнивается со значением, хранящимся в электронной подписи. Если они совпадают, считается, что электронная подпись соответствует именно этому документу. Таким образом, подписав любой документ, пользователь фактически подписывает и все остальные документы, имеющие такое же значение хеш–функции. Доверие к электронной подписи основывается на предположении, что сложно найти два документа, имеющих одинаковое значение хеш-функции.

Из перечисленного ясно, что хеш-функции играют огромную роль в ИТ. Обнаружение уязвимостей в таких алгоритмах может привести к серьезнейшим последствиям.

Псевдовзлом

Несколько лет назад появились статьи, в которых показывалось, что можно, используя современные, широко распространенные компьютеры, относительно быстро подобрать пару последовательностей символов, имеющих одинаковое значение md5. "Быстро" означает время: часы, сутки, несколько суток, в зависимости от мощности используемой техники. Таким образом, можно было создать два документа, подписав один из которых, атакуемый автоматически подписывал бы и другой. В тот момент большинство интересующихся не придали большого значения данному факту. Действительно, подобранные строки выглядели совсем не как нормальный текст. Подобрать два нормально выглядящих текста на данный момент быстро не получается. Потому все считали, что ни один нормальный человек не подпишет странно выглядящий документ. Потом появились статьи, в которых демонстрировался подбор документов с более сложной, чем простые текстовые документы, структурой. В частности, в интернете можно найти пример двух постскриптовских документов, имеющих одинаковое значение хеш-функции и при печати или просмотре дающие документы совершенно разного смысла. Появились статьи и об обнаружении подобной уязвимости в sha-1.

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

Безусловно, существуют другие пути взлома паролей по их хешам. Это и подбор по словарю, и использование предварительно рассчитанных таблиц. Надо понимать, что эти атаки не используют указанную уязвимость в алгоритмах хеширования. И они примерно одинаково работают при использовании практически любой хеш-функции, но это – скорее проблема парольной защиты вообще, и ее нельзя радикально решить внедрением более стойкой хеш-функции. Однако, найденная уязвимость действительно ставит под сомнение возможности использования и md5 и sha-1 для создания электронной подписи. Например, легко создать два совершенно разных документа с равным хешем, дать подписать один из них атакуемому и потом утверждать, что на самом деле он подписал другой документ. Конец электронной подписи на md5 и sha-1?

За и против существующих методов

Да, не следует создавать новые системы, которые будут использовать md5 или sha-1. Очевидно, они недостаточно стойки. И при увеличении мощности вычислительной техники, системы, использующие этот алгоритм, будут все более и более уязвимы. Но прощаться с привычными алгоритмами пока рано! Грамотно построенные системы, использующие эти алгоритмы, еще поживут. Возникает вопрос "а как же тогда с уязвимостью?"

Специалисты, даже поверхностно знакомые с основами криптографии, знают и давно знали о возможности существования таких уязвимостей, и в любой популярной книге по криптографии вы найдете описание атаки "дней рождения". В тех же популярных книгах говорится, что ни в коем случае нельзя ставить электронную подпись на документ, который был полностью сформирован не вами. Перед подписыванием в документ необходимо внести небольшие изменения, которые другой стороне трудно предсказать заранее. Это может быть, например, добавление "исходящего номера" документа, выбранный случайным образом. Выбор длины добавления, способ случайного выбора – вопросы отдельные, и ответ на них зависит от очень многих обстоятельств. После такой модификации вы можете смело подписывать полученный итоговый документ, так как значение его хеша будет отличаться от исходного документа и от, возможно, созданного "двойника". Грамотно построенные системы всегда это делают. Таким образом, этим системам пока не страшна описанная атака.

При работе со старыми системами, если есть выбор использовать md5 или sha-1, лучше выбрать sha-1. Этот алгоритм более стоек и требует большей работы для взлома. В настоящее время в интернете можно найти примеры практического использования уязвимости md5. Для sha-1 таких примеров найти не удалось.

Но какие же алгоритмы использовать в новых системах? В России в качестве алгоритма хеширования должен использоваться тот, который описан в ГОСТ Р 34.11-94. Поскольку в нашей стране работают криптографы очень высокого уровня, можно ожидать, что описанный алгоритм окажется достаточно стоек. Те, кто должен создавать продукты, совместимые с западными системами, возможно, будут использовать алгоритмы SHA-256 или SHA-512. Но, в любом случае, стоит проконсультироваться со специалистами и о выборе алгоритма и о тонкостях его использования.

Геннадий Махметов

Короткая ссылка