Хеш-пятилетка

(Март 2007)

О том, как работает кухня для приготовления новых мировых криптостандартов.

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

Но в первую очередь, конечно, американским Национальным институтом стандартов и технологий (НИСТ), в свое время издавшим спецификации SHA-1 в качестве FIPS 180-2 — официального федерального стандарта США на обработку информации. В последующие месяцы НИСТ весьма оперативно устраивал консультации и международные научно-технические семинары для объективной оценки статуса и стойкости своих хеш-функций.

Хотя реальных атак против «полновесной» SHA-1 (с полным числом циклов обработки) пока что так и не появилось, в НИСТ настоятельно рекомендуют заблаговременно переходить от сравнительно короткого 160-битного стандарта на «запасной аэродром», к семейству более стойких хеш-функций SHA-2 (SHA-224, SHA-256, SHA-384 и SHA-512).

Но самым главным решением НИСТ США, официально опубликованным в начале 2007 года, стало объявление о запуске крупномасштабного открытого конкурса на новый стандарт хеш-функции — по аналогии с недавним плодотворным конкурсом на AES, «продвинутый стандарт шифрования».

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

Таких, скажем, как блочные шифры, поточные шифры или генерация псевдослучайных последовательностей чисел. При объявлении конкурса на AES, к примеру, организаторы вполне четко представляли себе, что именно желательно получить в итоге и каковы должны быть критерии отбора для определения наилучшего кандидата среди всех блочных шифров.

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

Что же определилось вполне естественным путем, так это временной интервал, в рамках которого задумано устроить конкурс. Согласно существующим в США правилам, ближайшая по плану оценка состояния стандарта FIPS 180-2 (Secure Hash Standard) предусмотрена в 2007 году, а следующая — еще через 5 лет, в 2012.

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

«Рабочая лошадка» криптографии

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

Всякая хеш-функция — это такое математическое преобразование, которое, грубо говоря, на входе берет файл или «сообщение» совершенно произвольной длины и вычисляет для него на выходе своего рода «дайджест» (иначе именуемый также «хеш» или «цифровой отпечаток»), т.е. последовательность фиксированной, сравнительно небольшой длины и уникального вида.

В принципе, все хеш-функции устроены примерно одинаково — как многократное повторение итераций (циклов) некоторого хитрого преобразования, постепенно ужимающего файл до длины дайджеста с одновременным мощным перемешиванием битов содержимого.

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

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

Во-вторых, криптографические хеш-функции не должны иметь коллизий. Это означает, что хотя для каждого хеш-значения в принципе имеется бесконечное число вариантов входных последовательностей, нельзя отыскать даже два разных входа такого рода (порождающих «коллизию» на выходе). «Нельзя» здесь понимается опять-таки в вычислительном смысле — невозможно отыскать за приемлемое в реальных условиях время.

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

Другая, близко связанная с первой, область — цифровая подпись. Как из соображений общей безопасности, так и для существенного ускорения обработки, подавляющее большинство алгоритмов цифровой подписи устроены так, что всегда «подписывается» только дайджест сообщения, а не весь файл целиком.

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

И это, конечно, далеко не все. Благодаря своим случайным свойствам на выходе хеш-функции могут использоваться в качестве генераторов псевдослучайных чисел. Благодаря блочной структуре иногда могут выступать в качестве основы алгоритмов шифрования — блочных и поточных. Бывает и наоборот, когда блочный шифр становится основой криптопреобразования, применемого в циклах хеш-функции.

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

Они помогают организовывать эффективное управление ключами в защищенной электронной почте и в программах шифрования телефонии, начиная от самых известных, вроде PGP или Skype, и заканчивая всеми остальными.

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

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

[ВРЕЗКА]

Проблемы с формализацией

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

Стойкость к отысканию прообраза: имея дайджест h, должно быть сложным отыскание такого сообщения-прообраза m, для которого h = hash(m);

Стойкость к отысканию второго прообраза: имея входное сообщение m1, должно быть сложным отыскание второго входа m2 (не равного m1), такого, что hash(m1) = hash(m2);

Стойкость к коллизиям: должно быть сложным отыскание двух разных сообщений m1 и m2 таких, что hash(m1) = hash(m2).

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

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

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

[КОНЕЦ ВРЕЗКИ]

НИСТ как двигатель прогресса

Сложилось так, что хеш-функция, которую с наибольшей вероятностью использует всякий среднестатистический компьютер — это SHA-1. Данная функция сконструирована безымянными засекреченными умельцами в недрах Агентства национальной безопасности США и с подачи НИСТ запущена во всеобщее употребление в середине 1990-х годов.

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

Однако, как говорит старая поговорка, бытующая среди сотрудников АНБ: «Атаки всегда становятся только лучше и никогда не становятся хуже». Иначе говоря, для алгоритма SHA-1 начали отмечаться признаки устарелости, и все понимают, что пришло время от него уходить.

Переход к альтернативным хеш-функциям происходит в целом очень спокойно и без паники, ибо более стойкие альтернативы на ближайшие годы уже вполне определены. Наиболее очевидная — это родственный алгоритм SHA-256 с длиной хеша 256 бит.

Но все алгоритмы семейства SHA построены на вполне определенном классе хеш-функций MD, появившихся в начале 1990-х годов. За прошедшие с тех пор полтора десятка лет криптографы успели узнать в области хеш-функций очень много нового и вне всяких сомнений сейчас могут сконструировать нечто существенно более мощное.

[ВРЕЗКА]

Что применяют?

Наиболее широко используемыми в мире алгоритмами криптографического хеширования на сегодняшний день являются SHA-1, MD5 и RIPEMD-160 (если же говорить конкретно о России, то еще ГОСТ Р34.11-94 или «центробанковская» хеш-функция).

Все самые популярные криптоалгоритмы хеширования так или иначе построены на единой основе — семействе функций MD (от Message Digest — «дайджест сообщения»), разработанных известным американским ученым Рональдом Райвестом, более всего знаменитым в качестве одного из соавторов алгоритма RSA. Поначалу какое-то время самым удачным считался алгоритм 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 бит.

[КОНЕЦ ВРЕЗКИ]

Почему, собственно, новый стандарт ждут от НИСТ США? По той, главным образом, причине, что эта организация обладает именно тем опытом и именно той репутацией, которые устраивают все мировое криптографическое сообщество.

Десять лет назад, в 1997 году была очень похожая ситуация с алгоритмом шифрования. Для всех было совершенно очевидно, что алгоритм DES или Data Encryption Standard нуждается в замене, но вот на что его менять — это было весьма неочевидно.

И тогда руководство НИСТ решилось на беспрецедентный шаг — организовать всемирный открытый конкурс на новый криптоалгоритм. Были отобраны 15 предложений из 10 стран (Россию, правда, в конкурс тогда не пустили, прикрывшись формальными придирками к оформлению заявки). И после 4 лет публичных обсуждений и коллективного криптоанализа НИСТ США выбрал бельгийский алгоритм Rijndael, который стал AES, «продвинутым стандартом шифрования» на грядущие десятилетия.

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

Лучшие умы криптографической науки вывели на трассу свои лучшие алгоритмы как автомобили, а затем стали что есть силы крушить всех соперников, дабы обеспечить приход к финишу для своего детища — поскольку «остаться должен только один».

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

Огромная и плодотворная работа, которую проделал НИСТ при организации AES-конкурса, сделала практически очевидной траекторию, по которой следует двигать разработку и выбор новой хеш-функции. Два рабочих семинара по хеш-функциям, организованных силами НИСТ в 2005 и 2006 году, только подтвердили, что новый конкурс явно назрел. И когда он был действительно объявлен в январе 2007, все криптографы восприняли это как должное.

Предложения по новым хеш-функциям будут приниматься до осени 2008, а выбор должен быть сделан к концу 2011 года. Более длительный, чем в случае AES, срок отбора кандидатов представляется вполне разумным и обоснованным.

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

Вполне возможно, что в процессе прохождения этапов начавшегося конкурса несколько прояснится и этот вопрос.

* * *

[ВРЕЗКА]

Как это будет

В документе НИСТ США, объявляющем о начале конкурса на новый стандарт хеш-функции, приведено «Предварительное расписание» мероприятий, составляющих процесс разработки и выбора. В самом кратком виде намеченный график событий выглядит следующим образом.

Год первый (2007). Опубликовать для ознакомления и комментариев общественности базовые требования к кандидатам, правила оформления заявок и общие критерии отбора. В третьем квартале закончить данный этап, сформулировать окончательные требования и критерии для кандидатов, к концу года объявить о начале приема заявок.

Год второй (2008). Третий квартал — окончание приема заявок-кандидатов на новую хеш-функцию. В четвертом квартале отобрать кандидатов, отвечающих базовым требованиям, и провести Первую конференцию для объявления функций, участвующих в первом круге конкурса. Представлять кандидатов будут их авторы. Одновременно объявляется прием комментариев (результатов криптоанализа) по всем кандидатам.

Год третий (2009). К четвертому кварталу закончить этап комментариев по кандидатам. (В зависимости от числа отобранных кандидатов, НИСТ оставляет за собой право либо продлить этот этап, либо добавить число этапов для сокращения общего количества кандидатов перед отбором финалистов. Для этого могут понадобиться дополнительные семинары.) В конце года устроить Вторую конференцию для обсуждения результатов анализа, где разработчикам будет предоставлено право внести улучшения в свои алгоритмы.

Год четвертый (2010). В первом квартале выбрать и объявить финалистов, победивших в первом круге. Подготовить отчет, объясняющий данный выбор. Во втором квартале дать старт очередному кругу, перед началом которого финалистам позволено внести любые нужные улучшения в схему.

Год пятый (2011). Во втором квартале закончить этап комментариев общественности, в третьем квартале устроить Финальную конференцию, где будут подведены общие итоги анализа и обсуждений. В четвертом квартале выбрать победителя и до конца года объявить хеш-функцию (или, возможно, хеш-функции) для нового стандарта.

На этом собственно конкурс будет закончен, а в течение 2012 года НИСТ подготовит новую версию федерального стандарта США на хеш-функцию, который, скорее всего, как и AES затем станет де-факто общемировым.

[КОНЕЦ ВРЕЗКИ]

The END

Post Scriptum из 2015:

В октябре 2012 года НИСТ США объявил, что победителем конкурса стал алгоритм Keccak (произносится «кечак»), который и стал SHA-3 — новым криптографическим стандартом хеширования.