Конференция «Рус??Крип?то?»: крипто?графы ищут новые алгоритмы? хеширования
Еще буквально несколько лет назад казалось, что криптография уже решила все проблемы, и поэтому интерес к этой дисциплине начал угасать. Однако интерес к криптографии вырос с новой силой после того, как группа китайских исследователей в 2004 году предложила метод построения коллизий для функции хеширования серии SHA и MD, которые активно используются в Соединенных Штатах. Это пошатнуло стройную систему созданных криптографических протоколов и алгоритмов, а криптографы вновь получили интересные задачи, решению которых они могли бы посвятить себя.
О современном состоянии дел в сфере криптографии можно было услышать на недавней конференции «РусКрипто». Правда, указанные проблемы в основном возникли с алгоритмами хеширования, утвержденными в качестве обязательных для американских госструктур. Российский стандарт хеширования построен на другом принципе с использованием российского же стандарта шифрования, поэтому он относится к другому классу и не может быть взломан методом, предложенным для MD-хеша.
Результатом деятельности китайских криптографов стала разработка алгоритма для упрощения поиска коллизий для хеш-функций класса SHA и MD. Было показано, что с помощью Microsoft Word можно создавать документы, которые содержат разные тексты, хотя хеш у них при этом не меняется. Таким образом, подпись на документе уже можно оспорить, поскольку есть теоретическая возможность подделать документ, не меняя его электронной подписи. Нашлось и еще одно практическое применение коллизий — подделка подписей к программам, за счет чего можно выдавать вредоносный код за «нормальное» программное обеспечение. В общем, оказалось, что функция хеширования является не только одним из фундаментальных элементов криптографических протоколов, но и самым слабым их звеном.
Перед американским институтом NIST, который занимается стандартизацией криптографии, встала задача разработать новый стандарт хеширования, к которому также нельзя было бы применить использованные методы атаки. В прошлом году NIST инициировал процедуру разработки нового стандарта хеширования, которая должна завершиться в 2012 году. Сейчас проходит практически самый первый этап — выработка требований к функции хеширования. Предварительные требования опубликованы, но они еще обсуждаются. В 2008 году будут окончательно сформулированы требования. Затем будет проведен конкурсный отбор претендентов по традиционной для таких конкурсов схеме — в два этапа, где на первом выявляют тех, кто действительно удовлетворяет требованиям, а на втором — лучший стандарт. Окончательно итоги конкурса будут подведены осенью 2012 года. Сейчас же используются алгоритмы хеширования, которые построены по тем же принципам SHA, но с использованием эллиптических кривых.
Коллизия и хеш
Функция хеширования предназначена для изготовления цифрового отпечатка документа. Она позволяет сгенерировать для любого текста цифровую последовательность — так называемы «хеш». При этом по заданному хешу сложно подобрать текст, которому он бы соответствовал. Подобная «однонаправленность» хеша является его основным свойством, поскольку она гарантирует подлинность и неизменность документа, для которого известен хеш. Именно поэтому хеш используется при генерировании электронной подписи, для контроля изменений кода программ в операционных системах Windows и Linux, для проверки правильности передачи информации в сетевых протоколах и во многих других областях. Если же по хешу удается сгенерировать соответствующий ему текст, который будет отличаться от первоначального, то такая ситуация называется «коллизией».