Регистрация24.03 // Комбинирование криптоалгоритмов: от фольклора к теории и практике
В криптографических приложениях для усиления стойкости иногда используют комбинирование различных алгоритмов. Иногда популярен такой подход среди любителей в криптографии – если кто-то не доверяет и не может проверить стойкость алгоритма, то почему бы не использовать несколько алгоритмов совместно?
Если нет доверия одному шифру почему бы не использовать их каскад? Если хэш-функции не стойки, почему бы не использовать их совместно, объединяя полученные значения?
Иногда вопросы комбинирования возникают естественным образом, без желания специально создать запас прочности – как влияет на стойкость вложение подписей или хэшей, как хэшировать данные от двух сторон для выработки общего ключа?
На уровне фольклора в криптографическом сообществе считается, что комбинация алгоритмов или намного превышает стойкость единственного алгоритма или по крайней мере не хуже самого стойкого из них. Есть и пессимистические взгляды – принцип самого слабого звена, принцип сложения уязвимостей. Несмотря на ряд исследований, где для частных случаев были продемонстриованы примеры неудачного комбинирования режимов шифрования, однозначного вывода по этому вопросу нет. Поэтому некоторые создатели криптографических приложений свободно комбинируют алгоритмы, надеясь на поверия и интуицию, при этом доказательства стойкости такой схемы не приводится, хотя такой подход считается не вполне профессиональным.
Израильский специалист Amir Herzberg в работе Folklore, Practice and Theory of Robust Combiners, начало которой было положено ещё в 2002 году, предпринял очередную попытку классификации и исследования стойкости "фольклорных", основанных только на интуиции, методов комбинирования алгоритмов (так называемых стойких "комбайнеров", "комбинаторов").
Доказательства приведены в рамках идеализированной модели атак для абстрактных алгоритмов. Комбинированный алгоритм рассматривается как чёрный ящик – свойства исходных алгоритмов не рассматриваются. При этом получен ряд интересных выводов.
Так наиболее популярный метод комбинирования – каскадное шифрование (последовательное применение систем шифрования, когда текст сначала шифруется одним, затем другим алгоритмом с разными ключами E = еk1 (ek2 (x))), действительно является стойким против трёх типов атак-различителей (атак на основе подобранных открытых текстов IND-CPA, неадаптивных атак на основе подобранных шифртекстов IND-CCA1 и атак на основе подобранных шифртекстов с повторениями IND-rCCA). Но при этом шифрокаскады нестойки в рамках моделей адаптивных и генерализованных атак с подобраным шифртекстом (IND-CCA2, IND-gCCA). Это первый результат, полученный для каскадов систем шифрования, а не блочных шифров как таковых. Для блочных шифров актуальной остается работа Маурера, в которой доказывается, что в каскаде блочных шифров самым слабым звеном является первый шифр каскада.
Результаты данной работы распространяются как на каскады симметричных так и ассиметричных систем шифрования.
Для объединения систем шифрования необходимо учитывать, что две разные системы могут давать разный выход в длине шифртекста (например, если они имеют разный размер блока шифрования) и если объединение осуществляется как некая операция П * П', а не последовательно с сохранением длины, то возможна утечка сведений о длине открытого текста и появление скрытого канала.
Другой простой и интуитивно понятный способ комбинирования – copy-combiner f(x) || g(x) – объединение выходов двух псевдослучайных функций с одинаковым значением входа x является стойким для большинства практических применений, где требуется проверка целостности: коллизионно-стойкое хэширование, коды аутентификации собщений (MAC), цифровые подписи.
А вот parallel-combiner f||f'(<x, x'>) = f(x) || f'(x') может использоваться там где нужна необратимость – если хотя бы одна из функций f или f' необратима, то и комбинированный вариант из двух функций также будет необратим.
А можно ли применять какскад к криптографическим функциям, не связанным с системами шифрования? По аналогии такой каскад будет выглядеть как последовательное применение функций f и g: f*g(x) = f(g(x)).
Такие каскады в ряде случаев не подходят для обычных хэш функций, но годятся для перестановочных функций с сохранением длины сообщения. Есть ограничения и на использование таких каскадов в кодах аутентификации сообщений и в электронных подписях.
XOR-input combiner П xor П' является в целом стойким для шифрования. Например для систем шифрования с открытым ключём он обладает свойствами IND-CPA, IND-CCA1, но не соответствует спецификациям IND-CCA2, IND-gCCA, IND-rCCA.
Также авторы рассматривают в работе пример построения более сложной схемы комбинирования, расчитанной на противодействия нескольким атакам.
Основной вывод из работы может быть следующим: большинство интуитивно понятных схем из числа принятых на уровне "научного фольклора" доказывают свою стойкость, хотя и являются ограниченными. Зачастую комбинированная схема обеспечивает усиление одного свойства, но ослабляет другое. Поэтому разработчикам криптографических протоколов и создателям программ следует крайне внимательно относится к такой, на первый взгляд элементарной вещи, как комбинирование стойких алгоритмов.
Возможна и разработка более универсальных схем, где при комбинировании будут сохраняться многие свойства. Но и в случае с полупризнанными "фольклорными", и в случае с новыми схемами перед их применением требуется серьёзное теоретическое исследования и по возможности точное знание их свойств для избежания ошибок в конечных криптопродуктах.
Источник: Cryptology ePrint Archive
комментариев: 371 документов: 19 редакций: 20
комментариев: 9796 документов: 488 редакций: 5664
обсуждалось здесь,
комментариев: 9796 документов: 488 редакций: 5664
И кому теперь вообще верить? Опять "научному фольклору"?
комментариев: 9796 документов: 488 редакций: 5664
А что в криптографии доказательства имеют не такую же силу как в среднем в математике? Тогда это вообще не доказательства, а намёки и идеи.
комментариев: 9796 документов: 488 редакций: 5664
При том есть масса способов выкрутиться из любого доказательства на основании более строгой модели, новых знаний и т.д.
И этот подход считается ещё невероятным прогрессом! После изобретения provable security количество ошибок в протоколах уменьшилось. Раньше действовали просто методом попыток взлома на основе известных атак с последующими исправлениями.
Сейчас есть возможность захватить широкий спектр атак, включая неизвестные.
Но, как иронизируют криптографы: provable secure, probable not...