id: Гость   вход   регистрация
текущее время 14:22 23/11/2017
Владелец: SATtva (создано 14/09/2006 22:50), редакция от 15/05/2007 21:15 (автор: SATtva) Печать
Категории: криптография, криптоанализ, алгоритмы, хэширование, сайт проекта, статьи, атаки, разное, события
https://www.pgpru.com/Библиотека/Статьи/НовоеНеВсегдаЛучшее
создать
просмотр
редакции
ссылки

Почему новое – далеко не всегда лучшее, когда дело касается криптографии


На нынешней конференции CRYPTO, проводящейся ежегодно в Калифорнийском Университете, Санта-Барбара, довольно большое внимание было посвящено математическим функциям, называемым хэш-функциями. Обычно, CRYPTO – весьма спокойное мероприятие; представляемые на конференции работы не оказывают влияния на индустрию в течение как минимум нескольких лет. Однако последняя была необычайно захватывающей, благодаря уязвимостям, обнаруженным в ряде хэш-функций, и ещё потому, как эти новости облетели весь Интернет – стремительно, широко и зачастую не совсем достоверно. Теперь, когда конференция завершилась, я бы хотел поделиться с вами своими соображениями о том, что же случилось и чем это нам грозит.


Но прежде чем мы перейдём непосредственно к истории, есть то, что следует иметь в виду: OpenPGP заслуженно является криптографическим стандартом. Ни одна другая криптографическая система не была признана более надёжной и стойкой. Ни одна другая криптосистема не подверглась такому же уровню исследования и аналитической проверки. Ни одна другая криптосистема. Точка.

Так что же такое хэш-функции?


Хэш-функция принимает кусок данных произвольной длины на входе и выдаёт на его основе короткий кусочек данных фиксированной длины. Можете представить оба как последовательности букв или цифр. Некоторые хэш-функции производят 16-байтовые последовательности, другие – 20-байтовые, а самые новые выдают последовательности до 64 байтов длиной. Хэш-значение, или "хэш", полученный из исходных данных, должен быть максимально отличным от любых других хэшей. (Хэш – это число, вырабатываемое из последовательности данных. Хэш гораздо меньше входных данных, и он генерируется таким образом, чтобы сделать маловероятным получение такого же хэш-значения из других входных данных.) Хэш-функция имеет собственный механизм, обеспечивающий такой результат.


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


Хэши имеют множество приложений. Например, они используются в протоколах аутентификации, дабы не приходилось пересылать сами секреты, такие как пароли. Вместо пароля вы можете отправить его хэш плюс некоторый набор цифр или метку времени – всё вместе подвергнутое хэшированию. Однонаправленность функции крайне важна в подобном примере. Но, возможно, более ценное применение хэши находят в электронных цифровых подписях. ЭЦП на самом деле – это подпись хэша документа. Так делается ради скорости, а ещё – ради объёма. Подписывая хэш, мы получаем небольшую ЭЦП фиксированной длины, независимо от того, сколь крупным был сам подписанный документ. В этом случае ЭЦП быстро обрабатывается и оказывается практичной в использовании. (Если бы цифровые подписи были столь же большими, сколь и подписанные документы, они бы не нашли применения, поскольку удваивали бы размер подписываемых и пересылаемых сообщений.)

Коллизии хэшей


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


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


Коллизии – довольно странные звери, потому что они не могут не существовать. У идеальной хэш-функции не должно быть лучшего способа найти коллизию, чем просто перебирать все варианты, пока вы на неё не натолкнётесь. Более того, "сталкивающиеся" исходные строки должны быть насколько возможно различны. Попробую объяснить это другими словами. Вам не захочется, чтобы строка "Обещаю заплатить US$100" имела то же хэш-значение, что и "Я угощу вас ужином в трёхзвёздочном ресторане, когда вы в следующий раз приедете в город", или даже "Мой босс – дурак". Если какие-то из этих строк хэшируются к одному значению, то цифровая подпись одной окажется такой же, как и подпись другой, и невозможно будет сказать, какая именно строка была заверена подписью изначально. Если взломщику удастся произвести коллизию хэшей, он сможет эффективно подделать цифровую подпись. Он сможет утверждать, что два предмета в ящике одинаковы.


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

Насколько трудно произвести коллизию?


В идеале, если взять два предмета и поместить их в произвольные ящики, шансы, что они окажутся в одном ящике, составляют 1 к количеству ящиков. Скажем, с 12 ящиками вероятность будет 1:12. С 16-байтовой хэш-функцией вероятность коллизии составляет 1 к 2128, с 20-байтовой – 1 к 2160.


Если у вас есть кучка предметов, которые вы помещаете в ящики произвольно, вероятность возникновения коллизии будет приблизительно равна квадратному корню из числа ящиков. Это и есть знаменитая статистическая проблема, называемая "парадоксом дней рождений". В простых словах, какова вероятность того, что у двух человек в комнате, полной народа, будет общий день рождения? Если в комнате только два человека, вероятность будет весьма близка к 1:365. Я говорю "весьма близка" из-за наличия високосного года. В комнате с 367 людьми вместо вероятности будет достоверность, исходя из принципа ящиков Дирихле.


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


Эта идея очень важна, применительно к хэш-функциям, поскольку, несмотря на то, что вероятность получения идентичных хэшей от двух разных строк ничтожно мала, если у вас есть набор из огромного количества входных строк, вероятность получения одинакового хэш-значения для любой их пары будет выше, чем можно себе представить. Так, для 16-байтового хэша (того, что состоит из 128 битов) равная вероятность получения коллизии появится у вас, если вы располагаете набором из всего лишь 264 (или 18,446,744,073,709,551,616) входных строк. Надеюсь, вы понимаете, что я улыбаюсь, говоря "всего лишь". Для 20-байтового хэша (160 бит) этот порог составит 280, или 1,208,925,819,614,629,174,706,176, строк.


Оба этих числа настолько огромны, что мы, криптологи, предпочитаем считать, что они не случаются слишком уж часто. 280 – это приблизительное количество молекул в одной унции воды (1 жидкостная унция ~ 28-29 см3, – прим. пер.). Это намного больше числа всех интересных строк, написанных в мире. Нас мало волнует, если неинтересная строка ("sd5iujhfkw473q0r") имеет то же хэш-значение, что и интересная ("Я с радостью заплачу тебе во вторник за сегодняшний гамбургер"). Нам важно, чтобы не происходило коллизий между интересными строками.


Вот почему нахождение коллизий не является новостью, в то же время являясь новостью тревожной, по крайней мере для таких людей, как я. К сожалению, нет ясного математического определения "интересного". Это одно из тех непонятных человеческих понятий, делающих мир, хм, ну... интересным.


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

Что случилось на CRYPTO?


Эли Бихам (Eli Biham) и Рафи Чен (Rafi Chen) представили работу, описывающую нахождение предколлизии в алгоритме сжатия хэш-функции SHA-0. (Предколлизиями называются такие коллизии, где идентичными оказываются только часть битов выходного значения – исследователи получили 142 из 160.)


SHA-0 – это 20-байтовая хэш-функция, разработанная Правительством США в 1993 году. В 1995-м её сменила SHA-1. Нам никогда не сообщали, почему произошла замена, но мы всегда считали, что причиной этому послужили уязвимости SHA-0. В 1998 году Флорен Шабо (Florent Chabaud) и Антуан Жу (Antoine Joux) опубликовали результаты исследования, описывающие ряд математических ошибок в SHA-0, и мы предполагаем, что это именно те, которые привели к появлению SHA-1.


В ранних сообщениях с CRYPTO SHA-0 и SHA-1 оказались перепутаны, вокруг чего возникла шумиха об атаке на SHA-1. Сегодня никто не использует SHA-0, так что любые уязвимости в ней не представляют прямой угрозы. В течение десяти лет мы знали, что в ней есть ошибки; теперь мы всё больше узнаём их природу.


Последние горячие новости, представленные Бихамом и Ченом на предварительной сессии CRYPTO (презентативная сессия, на которой участники дают краткие представления последних результатов, ведущихся исследований и прочих близких по тематике вопросов), были посвящены тому, что им удалось получить коллизии и предколлизии в версии SHA-1 с уменьшенным числом циклов. В общей сложности SHA-1 состоит из 80 циклов, им же удалось получить коллизии только после 42 циклов и предколлизии после 45 циклов. Вероятно, эти результаты привели к ещё большей путанице в новостных сообщениях.


Нахождение коллизий в "укороченных" версиях функций на самом деле хорошая новость. В течение жизни функции стоит ожидать появления атак на сокращённое число циклов; отсутствие таковых свидетельствует о том, что алгоритм не получил должного криптографического анализа. Существует, например, атака на 7 из 10 раундов шифра Advanced Encryption Standard (AES).


Антуан Жу, один из пары учёных, первыми обнаруживших ошибки в SHA-0, представил работу по нахождению коллизий в хэш-функциях, состоящих из нескольких хэш-функций, где одна выполняется следом за другой. Его результаты пока отсутствуют в электронном архиве Международной ассоциации криптологических исследований (IACR).


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


Сёюн Ван (Xiaoyun Wang) обнародовала на предварительной сессии результаты работы своей команды: Денжуо Фэн (Dengguo Feng), Суджья Лаи (Xuejia Lai) и Хонбо Ю (Hongbo Yu). Результаты, но не сама работа, доступны на сайте IACR. Им удалось найти коллизии в 16-байтовых функциях MD4, MD5, HAVAL-128 и RIPEMD. (Последнюю не следует путать с RIPEMD-160. В ряде сообщений с CRYPTO названия были спутаны, и исследователи особо подчёркивают, что у них нет атаки на RIPEMD-160.) Также они отмечают, что по их подсчётам вычислительная нагрузка для нахождения коллизии в SHA-0 должна составить 240, а для HAVAL-160 – 232.


Поскольку у нас пока нет подробностей их исследования, нам неизвестно, как они находили коллизии. Однако мы знаем, что их метод очень хорош. Они заявили, что их взлом MD4 потребовал рабочую нагрузку от 22 до 26 операций.


Да, вы всё прочитали верно, это было 22, обычно называемое 4 (или, по-русски, "четыре"), и 26, больше известное как 64 ("шестьдесят четыре"). Они отметили, что в этом случае весь взлом может быть произведён вручную – компьютеры просто не требуются. В течение многих лет мы знали, что MD4 взломана, но нынешний результат всё равно впечатляет. Им пока не удалось обнаружить способ для нахождения коллизий произвольных входных строк, возможно и никогда не удастся, но уже сейчас они могут парами забрасывать предметы в ящик. Вероятно, что когда-нибудь у них получится и метить в тот ящик, в который захочется.


С последней интересной темой на сессии выступил Филип Хоукс (Philip Hawkes) из компании Qualcomm, обсудивший ряд своих результатов по SHA-256, показавших, что некоторые части функции слабее, чем считалось ранее; однако в настоящее время нет способов по обращению этой ситуации в коллизию или предколлизию.


На ужине перед началом сессии Ади Шамир (Adi Shamir, "S" в аббревиатуре RSA) сказал, что всегда считал хэш-функции самой изученной частью криптографии. Рон Райвест (Ron Rivest, "R" в RSA и автор MD4 и MD5) заметил, что создать стойкую хэш-функцию легко – трюк в том, как сделать её и надёжной, и быстрой. Он добавил, что всегда знал, что MD4 имеет энергичный дизайн. Мы знали, что MD5 содержит ошибки уже с тех пор, как Ганс Доббертин (Hans Dobbertin) обнаружил их в 1995-м, но Ван была первой, кто произвёл взлом.


В общем, эти обсуждения составили весьма захватывающую неделю.

Что всё это значит для пользователей PGP?


В программах PGP есть два типа ключей: ключи обратной совместимости RSA Legacy и новые ключи. Ключи обратной совместимости используют MD5 для формирования отпечатков и выработки цифровых подписей. Новые ключи используют SHA-1. Мы ввели новый формат ключей в 1997 г. из-за ряда вопросов со старым форматом, одним из которых стала работа Доббертина по уязвимостям в MD5. Теперь, когда Ван и её команда могут легко находить коллизии, пришло время, так сказать, упаковывать ящики.


Если у вас есть ключ обратной совместимости, пора отправить его в утиль. Вы можете отличить такие ключи на своей связке по пиктограмме старомодного серебристого ключика (Ключ обратной совместимости RSA v3 (1 Кб)). Мы сделали иконку такой не напрасно и имели в виду именно это: аннулируйте ключ. Сейчас. Немедленно.


Черчиль говорил, что нет ничего страшнее, чем когда в вас стреляют и промахиваются. Несколько атак просвистело рядом с SHA-1, которую мы используем для нынешних ключей, но не ранили её. Она по-прежнему безопасна, и так же в безопасности вы.


Тем не менее, стоит начинать думать, что мы будем делать, если в SHA-1 попадут.


Мы уже делаем это. В своём последнем исследовании Жу говорит, что каскадные хэш-функции не более надёжны. Он также отметил, что некоторые из инженеров PGP экспериментировали с таким подходом, но отказались от него. Это происходило в 96-м и 97-м, но никогда не было реализовано в массовых продуктах или в стандарте OpenPGP. Мы этим довольны. Однако, учитывая работу Филипа Хоукса по тематике SHA-256, не совсем ясно, не окажется ли немедленный переход туда прыжком с одной недоисследованной проблемы в другую недоисследованную проблему. Там, где мы сейчас, пока безопасно, так что мы хотим проявить всю свою осторожность и мудрость, прежде чем давать вам новые возможности.


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


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


Джон Каллас, директор по технологиям
и безопасности PGP Corporation
Перевод © 2004 SATtva


 
Комментариев нет [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3