Годен к строевой

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

Вот уже почти неделю компьютерная пресса переваривает сообщение китайских математиков (Shandong University in China), сумевших скомпрометировать хэш-алгоритм SHA-1. В полном объёме их работа до сих пор не опубликована, поэтому ориентироваться можно только по отзывам избранных профессионалов в области крипто, которым посчастливилось держать отчёт в своих руках. Собственно, именно благодаря одному из них эта история всега за шесть дней и успела наделать столько шуму: первым из тех, кто сообщил о случившемся публике, стал self-made криптоавторитет Брюс Шнайер. К настоящему моменту пыль, поднятая проехавшимися по теме первопроходцами улеглась, и можно в спокойной обстановке оценить что же произошло.

Впрочем, прежде стоит сделать небольшой экскурс в криптографию и разобраться с тем, что представляет из себя сам SHA. Придумали этот алгоритм больше десяти лет назад сотрудники Агентства национальной безопасности США (АНБ), а название его расшифровывается как Secure Hash Algorithm, что в буквальном переводе на русский выглядит едва ли более понятно: "стойкий хэш-алгоритм". С другой стороны, уяснить смысл SHA просто, если представить, зачем он нужен. Вообразите себе простое электронное письмо. Пропустив этот кусок текста через функцию SHA, вы получите на выходе число длиною в 160 бит, которое как раз и называют хэш. Прелести SHA заключены в трёх его свойствах. Во-первых, внеся даже мельчайшее изменение в текст исходного письма и вновь прогнав его через SHA, вы получите на выходе хэш, изменённый до неузнаваемости. Во-вторых, имея на руках только хэш, невозможно восстановить текст письма. Наконец, в-третьих, алгоритм SHA гарантирует отсутствие двух писем, для которых хэш получился бы одинаковым (т.н. пересечение).

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

Но вернёмся к SHA. Первый вариант этого алгоритма, позже (определённости ради) названный SHA-0, просуществовал всего два года. В 1995 он был заменён на более совершенный SHA-1 и в таком виде дошёл до наших дней, получив, благодаря официальному статусу промышленного стандарта, весьма широкое распространение. Сам по себе SHA ценности почти не представляет, но в сочетании с другими криптоалгоритмами превращается в грозное информационное оружие: SHA-1 и его вариации используются в самых разнообразных системах и инструментах, где требуется подтверждение аутентичности. Сами того не подозревая вы эксплуатируете SHA работая через защищённый канал в браузере, оперируя с электронными ключами PGP и аналогичных систем, снимая деньги со смарт-карт и даже запуская игры на приставке Xbox.

Теория утверждает, что для возникновения пересечения хэшей (в нашем примере - подбора второго письма с тем же хэшем) в SHA-1 требуется организовать 2^80 попыток. На протяжении десяти лет эта истина считалась бесспорной, но китайские математики сумели внести поправку, придумав способ атаки на SHA-1, гарантирующий успех уже через 2^69 попыток. Цифра по-прежнему невообразимо большая, но всё познаётся в сравнении: упростив задачу "взлома" в две тысячи раз, китайцы тем самым сделали её практически осуществимой. По оценке Шнайера, взяв за основу специализированный параллельный вычислитель DESCracker (реально построенный в 1998 году) и затратив около сорока миллионов долларов на постройку его "масштабированной вверх" версии, можно получить машину, способную устроить пересечение для хэша SHA-1 в среднем за 56 часов.

Вывод из всей этой истории простой и в некотором смысле закономерный. SHA-1, как и любой другой криптоалгоритм, с самого рождения поставлены между молотом и наковальней: с одной стороны на них давят криптаналитики, изобретающие всё более хитроумные схемы атак, с другой - закон Мура. SHA-1 ещё не раздавлен, эксперты (NIST) считают, что впереди у него ещё как минимум пять лет беспорочной службы. Но техника и мысль человеческая прогрессируют и недалёк тот день, когда цена атаки упадёт в разы, сделав переход на более совершенный алгоритм необходимостью. Замена уже есть: семейство алгоритмов SHA-2, несколько отличающихся от своего знаменитого предка алгоритмически и значительно - длиной хэша, уже придумана и стандартизована.