Блок-вечеринка: веселая вечеринка по криптографическим стандартам
Тетрис, Лего, Дэвид Робинсон и Бельгия
Если бы вы спросили меня о моем мнении о лучшем вкладе в криптографию за последние несколько десятилетий, мой ответ вообще не касался бы криптографии. Это не потоковый шифр, не блочный шифр, не хеш-функция и не протокол. На самом деле, мы как потребители безопасности ничего не «используем» сами по себе. Однако это то, что измеряет то, что мы используем; это криптографическое соревнование. Такой конкурс представляет собой в основном процесс отбора, в котором участвуют криптографы с конкурирующими разработками. Эти конструкции проходят раунды и раунды криптоанализа. Помимо тщательного изучения аспектов безопасности проектов, вводятся различные метрики и критерии проектирования для изучения характеристик их производительности и эффективности во множестве программных и аппаратных сред. Потенциальный стандарт, очевидно, должен быть безопасным, но жизненно важно, чтобы он позволял экономить время и снижал затраты в процессе. Иначе не разрежется. Даже надежной защиты недостаточно, чтобы компенсировать неэффективную и неэффективную криптографическую схему.
Некоторым из вас интересно, где вы видели подобные ситуации раньше. Вот подсказка: в чем больше кубиков, чем в романе тетриса и лего? Нет, не карьерная статистика Дэвида Робинсона. Хорошая попытка, однако. Если вы ответили: «Каков процесс выбора расширенного стандарта шифрования?» вы были бы правы здесь, и на Jeopardy тоже. Наш текущий стандарт блочного шифра, разработанный в Бельгии 128-битный SPN или Substitution Permutation Network, получивший название Rijndael, стал чемпионом этого соревнования. Этот пятилетний процесс продемонстрировал плоды открытой конкуренции. Результат переполнен добром, и есть веские причины верить в стандарт. В конце концов, он пережил натиск самой безжалостной группы криптоаналитиков из когда-либо существовавших. Кроме того, он все еще выживает после анализа. Если этого недостаточно, подумайте вот о чем: криптоаналитики уделяют ему больше внимания, чем любому другому блочному шифру, включая двух лидеров-финалистов, Twofish и Serpent.
Конкуренция от начала до конца очень похожа на песочницу для методологий проектирования. Вы соберете вместе лучших криптографов, предложите им использовать различные Фейстели, имена участников-служб и так далее, основанные на множестве различных стратегий проектирования, связанных как с безопасностью, так и с производительностью реализации, и вы получите идеальные условия для отсеивания хороший, плохой и уродливый. Вы можете не только отсеять, что небезопасно и что работает не очень хорошо, но и начать создавать метрики для того, что представляет собой безопасный, хорошо работающий блочный шифр в программных и аппаратных средах, где ограничения обработки и памяти могут стать невероятно требовательными. Это необходимо для практической криптографии. Теоретически там, где условия произвольны и идеалистичны, можно сосредоточиться только на безопасности. На практике все более требовательно; выигрывает не безопасный дизайн, а полезный дизайн.
Я бы хотел заказать картофельные оладьи, пожалуйста
Теперь, когда мы усвоили все эти хорошие уроки о том, как выбрать криптографический стандарт, что мы можем с ними сделать? Оказывается, нам очень нужен еще один стандарт, и на этот раз, вероятно, это будет еще более сложный процесс. Как известно большинству из нас, хеш-функции за последние несколько лет сильно пострадали. За относительно короткий промежуток времени всплыла совокупность криптоанализа на различных хеш-функциях. Наряду с этим появилось множество самоуверенных взглядов на последствия. Уже после беглого взгляда на то, что влечет за собой большинство этих взглядов, становится очевидным забвение вопроса — у широкой общественности крайне ограниченное понимание того, что происходит, если оставить в стороне повторения очевидных вещей, которые до сих пор осмыслены до некоторой степени. малая степень. Без дальнейших церемоний или перефразирования (слегка умышленного каламбура) того, что средства массовой информации уже проделали фантастическую работу по преувеличению, я остановлюсь на «структурной» точке зрения на этот вопрос, которая является не столько общей, сколько должно быть. Другими словами, если кто-то не занимается криптографией в академических кругах, вполне вероятно, что они понятия не имеют. Надеюсь, это даст толчок, который может понадобиться неакадемическим людям, чтобы, так сказать, «догадаться».
Основное наблюдение, к которому я хотел бы обратиться, касается стратегии проектирования, из которой состоит большинство семейства (например, семейства MD4) обычных хеш-функций; это семейство состоит из MD4, MD5, HAVAL, RIPEMD, SHA-1 и SHA-2, а также соответствующих расширений выходной длины, где это применимо. По сути, в семействе хеш-функций MD4 мы имеем дело с общей структурой, которая представляет собой преобразование блочного шифра в одностороннюю хэш-функцию с использованием конструкции прямой связи Дэвиса-Мейера ; эти функции, по большей части, можно резюмировать как демонстрацию структуры UFN или несбалансированной сети Фейстеля, которые являются одновременно и гетерогенными, и с большим количеством источников. За последнее десятилетие или около того, вплоть до последних месяцев, мы видели довольно много криптоанализа, касающегося этих функций, в том числе Бихама, Р. Чена, Шабо, Жу, Доббертина, Вана, Ю, Инь, Фэна, Х. Чен, Лай, Ван Ромпей, Бирюков, Пренил, Вандевалле, Хоукс, Паддон, Роуз и так далее.
После криптоаналитического снижения общего уровня сложности SHA-1 с 2^80 до 2^63 средства массовой информации стали непрошеным катализатором бессмысленного мышления. Многие предложения вращаются вокруг паники, вызванной спешкой с внесением изменений в инфраструктуру для поддержки SHA-2 и поэтапным отказом от использования SHA-1. Прежде чем идти дальше, я хочу кратко подчеркнуть важность того, чтобы не торопить криптографию на уровне реализации; нет ничего более вредного для безопасности, чем изменение криптографии по прихоти на уровне реализации. Именно на этом уровне во многом определяется эффективность криптографии.
Во-первых, этот [переход на более крупный вывод хэш-функции] должен был быть реализован задолго до этого. Защита примитивов, по крайней мере, с 128-битными уровнями безопасности уже должна стать стандартной практикой, даже если только де-факто. Во-вторых, хотя SHA-256, например, должно быть достаточно, чтобы удовлетворить потребность в 128-битной безопасности, это не терминальное решение. В лучшем случае это промежуточный вариант, и вот почему: недавний криптоанализ представил усовершенствованные методологии и расширения, которые в той или иной форме применимы к каждой конструкции в семействе MD4. Сейчас не время использовать функции из этого семейства, которые поддерживают больший вывод; пришло время изучить путь разработки хэш-функций, которые не только поддерживают большую длину вывода, но и состоят из совершенно других стратегий проектирования. Пришло время проанализировать другие стратегии построения криптографически безопасных хеш-функций.
Под «другими стратегиями» мы просто подразумеваем что угодно, но только не UFN-природу большинства существующих обычных хеш-функций. Есть одна специфическая стратегия, которая, на мой взгляд, является идеальной точкой интереса в подобном случае. Эта конкретная стратегия является стратегией широкой тропы. Звучит знакомо? Базовый примитив AES, Rijndael, является потомком этой стратегии, как и множество других подобных шифров в семействе предшественников. Винсент Риймен, «Рий» в «Рейндале», вместе с Пауло Баррето дали нам Whirlpool; это интересный дизайн, в котором используется усиление разновидности Меркла-Дамгарда и конструкция хэширования Миягути-Пренеля с блочным шифром, который в некоторых аспектах похож на Rijndael. Эта 512-битная хеш-функция также опирается на стратегию широкого следа и должна быть моделью направления или одного из направлений, которые нам следует исследовать. Другим эффектом, как прямым, так и косвенным, является тот факт, что такое направление побудило бы к дальнейшему, более широкому и строгому криптоанализу стратегии широкого следа. Это не только укрепит уверенность в этой стратегии как методологии построения криптографически безопасных хэш-функций, но и позволит лучше изучить те же общие принципы, на которых основан Rijndael, что, безусловно, является полезной тактикой.
Настоящая проблема и правильная атмосфера
В заключение я считаю, что рассматриваемая проблема — реальная проблема — намного глубже, чем просто увеличение длины вывода хеш-функции для обеспечения большего запаса общей безопасности. Я чувствую, что это вопрос структурной важности, когда нам нужно направить наши аналитические усилия на другие стратегии, помимо UFN и состава семейства MD4, чтобы мы не оказались в положении, когда каждая конструкция в единственном имеющемся у нас семействе подвержен атакам, которые могут стать более эффективными. Обратите внимание: я никоим образом не заявляю, что UFN по своей сути небезопасны. Я просто предлагаю изменить политику дизайна, так сказать. Посмотрите на это как на подход к проектированию хэш-функции, как мы подошли к проектированию блочного шифра.
Несмотря на то, что хеш-функции являются мастерами на все руки и универсальными функциями в криптографии, мы, кажется, знаем немного больше о конструкции блочных шифров, учитывая, что большинство обычных хеш-функций, которые у нас есть, являются производными от одного и того же семейства, в то время как блочные шифры могут похвастаться разнообразием контрастных конструкций. Проведение конкурса на федеральный стандарт — самый плодотворный способ доить криптографическое сообщество своим дизайнерским мастерством. Ограничения стандарта обеспечивают правильную атмосферу для интенсивного анализа, что гарантирует, что критерии сбалансированы между консерватизмом и компромиссом. Поступая таким образом, мы максимизируем количество экземпляров, в которых функция подходит для реализации, обеспечивая при этом криптографическую безопасность, которую мы ожидаем от такой функции.
Попрощаться с SHA-1 уже давно пора. SHA-256 отвечает за то, чтобы его ремень был туго натянут до 2011 года, когда ожидается появление нового стандарта хэш-функции. Начиная с 2008 года, мы начнем этот долгий путь к пониманию, пожалуй, самых универсальных криптографических функций. Мы в долгу перед ними. Как и в случае с процессом выбора AES, мы увидим широкое сотрудничество между лучшими из лучших с множества континентов, объединяющее школы мысли и методологии дизайна. Благодаря NIST и всем участвующим криптографам пришло время поделиться оптимизмом. Понимание дизайна хеш-функции, которое мы получим только из процесса, будет столь же важным, как и выбранный стандарт. Без сомнения, это будет один из самых больших шагов, предпринятых криптографией. Пусть начнется криптографическое кумитэ.