Чем заменят SHA-1
АрхивВ фокусеДва года назад в популярном криптографическом алгоритме SHA-1 нашли уязвимость. Теперь американский Национальный институт стандартов и технологий ищет хеш-функцию, которая могла бы стать заменой SHA-1.
В феврале 2005 года международное сообщество криптографов взбудоражила новость о потенциальной уязвимости, впервые обнаруженной в алгоритме SHA-1. Поскольку SHA-1 на сегодняшний день фактически является общепринятым стандартом для хеш-функций, реализованным в самых разнообразных системах защиты информации, известие о признаках угрозы было воспринято очень серьезно.
В первую очередь обеспокоился американский Национальный институт стандартов и технологий (НИСТ), в свое время издавший спецификации SHA-1 в качестве FIPS 180-2 - официального федерального стандарта США на обработку информации.
В последующие месяцы НИСТ оперативно устраивал консультации и международные научно-технические семинары для объективной оценки статуса и стойкости своих хеш-функций. Хотя реальных атак против "полновесной" SHA-1 (с полным числом циклов обработки) пока так и не было, НИСТ настоятельно рекомендует заблаговременно переходить от сравнительно короткого 160-битного стандарта на "запасной аэродром", к семейству более стойких хеш-функций SHA-2 (SHA-224, SHA-256, SHA-384 и SHA-512). Но самым главным решением Института стало объявление в начале нынешнего года о запуске крупномасштабного открытого конкурса на новый стандарт хеш-функции - по аналогии с недавним плодотворным конкурсом на AES, "продвинутый стандарт шифрования".
Нельзя сказать, что это было очевидное и назревшее решение. Проблема в том, что в мировой криптографической науке раздел о хеш-функциях развит гораздо хуже других - таких, скажем, как разделы о блочных шифрах, поточных шифрах или генерации псевдослучайных последовательностей чисел. При объявлении конкурса на AES организаторы четко представляли себе, что именно хотели бы получить в итоге и каковы должны быть критерии отбора для определения наилучшего кандидата среди всех блочных шифров. В случае хеш-функций того же самого сказать нельзя, ибо теория и общее понимание предмета пока оставляют желать лучшего. Но как показали семинары в НИСТ и обратная связь от криптографического сообщества в целом, целесообразно начинать движение к новому стандарту уже сейчас, а не дожидаться, когда точные и строгие критерии выбора сформируются естественным образом.
Что определилось вполне естественным путем, так это время проведения конкурса. По существующим в США правилам, ближайшая оценка состояния стандарта FIPS 180-2 (Secure Hash Standard) запланирована на текущий год, а следующая намечена на 2012-й. Поскольку с применяемым в настоящее время хеш-стандартом ситуация уже более или менее ясна, то сочтено разумным за грядущую пятилетку определиться с оптимальным преемником. Чтобы к 2012 году подойти с уже зрелым кандидатом на роль нового стандарта.
В отличие от более привычных терминов "шифр" или "ключ" словосочетание "однонаправленная хеш-функция" по сию пору может звучать замысловато даже для людей, достаточно близко знакомых с принципами работы компьютера и его программ. Однако суть этой конструкции прозрачна. Хеш-функция - это (с точностью до деталей) такое математическое преобразование, которое на входе получает файл или "сообщение" произвольной длины и вычисляет для него подающийся на выход "дайджест" (иначе именуемый также "хеш" или "цифровой отпечаток"), то есть последовательность фиксированной (сравнительно небольшой) длины и уникального вида. В принципе, все хеш-функции устроены примерно одинаково - как многократное повторение итераций (циклов) некоторого хитрого преобразования, постепенно ужимающего файл до длины дайджеста с одновременным мощным перемешиванием битов содержимого.
Всякая хорошая хеш-функция действует так, что даже единственное изменение байта или бита в файле на входе приводит на выходе к хеш-значению совершенно иного вида. Иногда даже требуют, чтобы при изменении единственного бита на входе менялось не менее половины битов на выходе - это условие называют лавинным свойством (avalanche property). Кроме того, чтобы быть полезной в криптографии, хеш-функция должна обладать еще двумя важнейшими свойствами.
Во-первых, криптографические хеш-функции должны быть однонаправленными. Под этим принято понимать легкое вычисление в одну сторону и невозможность вычисления в обратную. Иначе говоря, всегда можно и удобно подать нечто на вход и быстро получить соответствующее хеш-значение на выходе, однако нет никакой возможности за разумное время по выходному значению хеш-функции вычислить, что подавалось на вход.
Во-вторых, криптографические хеш-функции не должны иметь коллизий. Это означает, что хотя для каждого хеш-значения в принципе имеется бесконечное число вариантов входных последовательностей, нельзя отыскать два разных входа, дающих одинаковый дайджест (образующих "коллизию"). "Нельзя" здесь понимается опять-таки в вычислительном смысле - "невозможно за приемлемое в реальных условиях время".
Наиболее типичный и повсеместно распространенный способ применения криптографического хеширования - это проверка целостности сообщений. Для простой проверки того, были ли внесены какие-то изменения или искажения в файл на этапе доставки, очень удобно сравнивать дайджесты, вычисляемые до и после передачи информации (или извлечения файла из хранилища, или любого другого события). Другая, близко связанная с первой область - цифровая подпись. Из соображений общей безопасности и для существенного ускорения обработки подавляющее большинство алгоритмов цифровой подписи устроены так, что всегда "подписывается" только дайджест сообщения, а не весь файл.
Еще одно важное приложение - верификация правильности пароля доступа. Пароли обычно не хранят в открытом виде - чтобы они не становились легкой добычей похитителей и злоумышленников. Вместо этого в базе хранятся дайджесты паролей. Тогда система, чтобы проверить подлинность пользователя, хеширует представленный им пароль и сравнивает результат со значением, хранящимся в базе дайджестов паролей. И это, конечно, далеко не все. Благодаря свойствам рандомизации, хеш-функции могут использоваться в качестве генераторов псевдослучайных чисел, а благодаря блочной структуре, они иногда выступают в качестве основы алгоритмов шифрования - блочных и поточных. Бывает и наоборот, когда блочный шифр становится основой криптопреобразования, применяемого в циклах хеш-функции.
Проблемы с формализацией
На сегодняшний день в криптологии не существует строгого формального определения, которое бы охватывало все свойства, необходимые и достаточные для того, чтобы хеш-функция именовалась "криптографической". Но есть несколько свойств, которые для этого класса функций предполагаются обязательными:
Стойкость к отысканию прообраза: по дайджесту h должно быть сложным отыскание такого сообщения-прообраза m, для которого h = hash(m).
Стойкость к отысканию второго прообраза: по входному сообщению m1 должно быть сложным отыскание второго входа m2 (не равного m1), такого, что hash(m1) = hash(m2).
Стойкость к коллизиям: должно быть сложным отыскание двух разных сообщений m1 и m2 таких, что hash(m1) = hash(m2).
Общий набор требований к криптографическим хеш-функциям столь специфичен, что - как признают математики - идеальная хеш-функция должна быть максимально "скучной", то есть не иметь никаких интересных свойств. В идеале она должна выглядеть как чисто случайная функция - подаешь что угодно на вход, а на выходе получаешь случайное число фиксированной длины. С тем лишь существенным отличием, что в действительности выходной хеш - далеко не случайное, а строго детерминированное значение, вычисляемое быстро и эффективно. Как это ни парадоксально звучит, но можно сказать, что даже на интуитивном уровне понятно - подобный критерий для поиска оптимума сильнейшим образом сопротивляется каким-либо формальным определениям.
Тем не менее есть надежда, что грядущие пять лет напряженных практических поисков кандидата на наилучшую хеш-функцию приведут и к заметным сдвигам в общей теории.
Короче говоря, хеш-функции стали чуть ли не важнейшим элементом современной криптографии. Они обеспечивают безопасность в повсеместно применяемом протоколе защищенных веб-соединений SSL. Они помогают организовывать эффективное управление ключами в защищенной электронной почте и в программах шифрования телефонии, начиная от самых известных, вроде PGP или Skype, и заканчивая всеми остальными. Если говорить о сетевой безопасности, то хеш-функции используются и в виртуальных частных сетях, и в защите системы доменных имен DNS, и для подтверждения того, что автоматические обновления программ являются подлинными. Внутри операционной системы хеш-функции так или иначе задействованы практически во всех структурах, обеспечивающих безопасность. Иными словами, каждый раз, когда в компьютере или сети происходит что-то, подразумевающее защиту информации, рано или поздно в действие непременно вступает хеш-функция.
Продолжение статьи на следующей странице.
- Из журнала "Компьютерра"
