Стойкость к отысканию прообраза: по дайджесту h должно быть сложным отыскание такого сообщения-прообраза m, для которого h = hash(m).
Стойкость к отысканию второго прообраза: по входному сообщению m1 должно быть сложным отыскание второго входа m2 (не равного m1), такого, что hash(m1) = hash(m2).
Стойкость к коллизиям: должно быть сложным отыскание двух разных сообщений m1 и m2 таких, что hash(m1) = hash(m2).
Общий набор требований к криптографическим хеш-функциям столь специфичен, что - как признают математики - идеальная хеш-функция должна быть максимально «скучной», то есть не иметь никаких интересных свойств. В идеале она должна выглядеть как чисто случайная функция - подаешь что угодно на вход, а на выходе получаешь случайное число фиксированной длины. С тем лишь существенным отличием, что в действительности выходной хеш - далеко не случайное, а строго детерминированное значение, вычисляемое быстро и эффективно. Как это ни парадоксально звучит, но можно сказать, что даже на интуитивном уровне понятно - подобный критерий для поиска оптимума сильнейшим образом сопротивляется каким-либо формальным определениям.
Тем не менее есть надежда, что грядущие пять лет напряженных практических поисков кандидата на наилучшую хеш-функцию приведут и к заметным сдвигам в общей теории.
«Рабочая лошадка» криптографии
В отличие от более привычных терминов «шифр» или «ключ» словосочетание «однонаправленная хеш-функция» по сию пору может звучать замысловато даже для людей, достаточно близко знакомых с принципами работы компьютера и его программ. Однако суть этой конструкции прозрачна. Хеш-функция - это (с точностью до деталей) такое математическое преобразование, которое на входе получает файл или «сообщение» произвольной длины и вычисляет для него подающийся на выход «дайджест» (иначе именуемый также «хеш» или «цифровой отпечаток»), то есть последовательность фиксированной (сравнительно небольшой) длины и уникального вида. В принципе, все хеш-функции устроены примерно одинаково - как многократное повторение итераций (циклов) некоторого хитрого преобразования, постепенно ужимающего файл до длины дайджеста с одновременным мощным перемешиванием битов содержимого.
Всякая хорошая хеш-функция действует так, что даже единственное изменение байта или бита в файле на входе приводит на выходе к хеш-значению совершенно иного вида. Иногда даже требуют, чтобы при изменении единственного бита на входе менялось не менее половины битов на выходе - это условие называют лавинным свойством (avalanche property). Кроме того, чтобы быть полезной в криптографии, хеш-функция должна обладать еще двумя важнейшими свойствами.
Во-первых, криптографические хеш-функции должны быть однонаправленными. Под этим принято понимать легкое вычисление в одну сторону и невозможность вычисления в обратную. Иначе говоря, всегда можно и удобно подать нечто на вход и быстро получить соответствующее хеш-значение на выходе, однако нет никакой возможности за разумное время по выходному значению хеш-функции вычислить, что подавалось на вход.
Во-вторых, криптографические хеш-функции не должны иметь коллизий. Это означает, что хотя для каждого хеш-значения в принципе имеется бесконечное число вариантов входных последовательностей, нельзя отыскать два разных входа, дающих одинаковый дайджест (образующих «коллизию»). «Нельзя» здесь понимается опять-таки в вычислительном смысле - «невозможно за приемлемое в реальных условиях время».
Наиболее типичный и повсеместно распространенный способ применения криптографического хеширования - это проверка целостности сообщений. Для простой проверки того, были ли внесены какие-то изменения или искажения в файл на этапе доставки, очень удобно сравнивать дайджесты, вычисляемые до и после передачи информации (или извлечения файла из хранилища, или любого другого события). Другая, близко связанная с первой область - цифровая подпись. Из соображений общей безопасности и для существенного ускорения обработки подавляющее большинство алгоритмов цифровой подписи устроены так, что всегда «подписывается» только дайджест сообщения, а не весь файл.
Еще одно важное приложение - верификация правильности пароля доступа. Пароли обычно не хранят в открытом виде - чтобы они не становились легкой добычей похитителей и злоумышленников. Вместо этого в базе хранятся дайджесты паролей. Тогда система, чтобы проверить подлинность пользователя, хеширует представленный им пароль и сравнивает результат со значением, хранящимся в базе дайджестов паролей. И это, конечно, далеко не все. Благодаря свойствам рандомизации, хеш-функции могут использоваться в качестве генераторов псевдослучайных чисел, а благодаря блочной структуре, они иногда выступают в качестве основы алгоритмов шифрования - блочных и поточных. Бывает и наоборот, когда блочный шифр становится основой криптопреобразования, применяемого в циклах хеш-функции.
Короче говоря, хеш-функции стали чуть ли не важнейшим элементом современной криптографии. Они обеспечивают безопасность в повсеместно применяемом протоколе защищенных веб-соединений SSL. Они помогают организовывать эффективное управление ключами в защищенной электронной почте и в программах шифрования телефонии, начиная от самых известных, вроде PGP или Skype, и заканчивая всеми остальными. Если говорить о сетевой безопасности, то хеш-функции используются и в виртуальных частных сетях, и в защите системы доменных имен DNS, и для подтверждения того, что автоматические обновления программ являются подлинными. Внутри операционной системы хеш-функции так или иначе задействованы практически во всех структурах, обеспечивающих безопасность. Иными словами, каждый раз, когда в компьютере или сети происходит что-то, подразумевающее защиту информации, рано или поздно в действие непременно вступает хеш-функция.
Что применяют?
Наиболее широко используемые в мире алгоритмы криптографического хеширования - это SHA-1, MD5 и RIPEMD-160 (если же говорить о России, то еще и ГОСТ Р34.11-94, она же «центробанковская» хеш-функция).
Все самые популярные криптоалгоритмы хеширования построены на единой основе - семействе функций MD (от Message Digest - «дайджест сообщения»), разработанных известным американским ученым Рональдом Райвестом. Поначалу самым удачным считался алгоритм MD4, а когда в нем нашли слабости, Райвест придумал усиленную модификацию под названием MD5.
На основе идей 128-битного MD4 математики Агентства национальной безопасности США создали более стойкий вариант - 160-битный «Безопасный алгоритм хеширования», или SHA. Но если Райвест подробно разъяснял в своих описаниях, чему служит и каким образом повышает безопасность каждый из этапов его алгоритма, то АНБ в присущей спецслужбе манере никаких комментариев не дало. Более того, через некоторое время после публикации SHA был отозван и переиздан в модифицированной, очевидно более сильной версии SHA-1, ставшей федеральным стандартом (прежняя получила название SHA-0).
В Европейском сообществе, в свою очередь, разработали собственный 128-битный стандарт криптографического хеширования, получивший название RIPE-MD и также развивающий идеи Райвеста. По мере осуществления успешных криптоаналитических атак против хеш-функций стали появляться усиленные версии этого алгоритма с увеличенной длиной хеша - RIPEMD-160, -256 и -320. Для SHA, соответственно, в АНБ создали укрепленное семейство SHA-2 с длинами хеша 224, 256, 384 и 512 бит. Российская хеш-функция, построенная на основе отечественных крипторазработок, имеет длину 256 бит.
НИСТ как двигатель прогресса
Сложилось так, что хеш-функция, которую с наибольшей вероятностью использует всякий среднестатистический компьютер, - это SHA-1. Эта функция сконструирована безымянными засекреченными умельцами в недрах Агентства национальной безопасности США и с подачи НИСТ запущена во всеобщее употребление в середине 1990-х годов.
За последние годы качество найденных и опубликованных атак в отношении хеш-функций вообще и SHA-1 в частности заметно повысилось, что связано с общим прогрессом в теории и методах криптоанализа. Пока, правда, даже самая лучшая из атак требует вычислительных ресурсов на грани возможного, да и в этом виде бессильна перед полным набором циклов SHA-1. Однако, как гласит поговорка, бытующая среди сотрудников АНБ: «Атаки всегда становятся только лучше и никогда не становятся хуже». Иначе говоря, для алгоритма SHA-1 начали отмечаться признаки слабости, и все понимают, что пришло время от него отказываться.
Переход к альтернативным хеш-функциям происходит в целом спокойно, без паники, ибо более стойкие альтернативы на ближайшие годы вполне определены. Наиболее очевидная - это родственный алгоритм SHA-256 с длиной хеша 256 бит. Но все алгоритмы семейства SHA построены на конкретном классе хеш-функций MD, появившихся в начале 1990-х годов. За прошедшие с тех пор полтора десятка лет криптографы успели узнать о хеш-функциях очень много нового и, несомненно, сейчас могут сконструировать нечто значительно более мощное.