Анализ эффективности градиентной статистической атаки на блоковые шифры
Вашему вниманию предлагается авторская магистерская диссертация по криптоанализу, связанная с успешной атакой на блочные шифры RC6, IDEA, MARS, CAST-128, Blowfish, а также исследованию линейного конгруэнтного генератора случайных чисел. Ниже приведено введение к диссертации. Полный её текст содержится в прикреплённом к статье документе
Блочные шифры c секретным ключом находят широкое применение в системах защиты передачи и хранения информации, что делает актуальными как задачи построения надёжных блоковых шифров, так и задачи поиска эффективных криптологических атак на эти шифры (т.е. методов определения секретного ключа шифра на основе экспериментов с зашифрованными сообщениями). Многие специалисты занимаются исследованием теоретической и практической устойчивости блочных шифров к атакам различного рода. Постоянно разрабатываются как новые шифры, так и новые атаки на них, позволяющих оценить реальную устойчивость шифров. Отметим, что для криптографии практический интерес представляют только те атаки, которые позволяют находить ключ за время меньшее, чем метод прямого перебора секретного ключа.
Шифры RC6, Blowfish, MARS, IDEA, CAST-128 – одни из претендентов на звание AES, конкурса, проводимого в 2001 году, для выбора нового криптографического стандарта США. Существуют многочисленные работы, посвящённые анализу этих шифров. Большинство из них используют результаты дифференциального и линейного криптоанализов – двух наиболее распространённых видов атак, применимых к блоковым шифрам в несколько урезанном виде: в исследованиях шифров зачастую не используются присущие им операции так называемого «забеливания» («post–whitening» и «pre–whitening»), а также уменьшено количество этапов шифрования. В последнее время появился новый тип атак, основанный на исследовании статистических свойств шифров. Например, получен результат, согласно которому выходную последовательность шифра RC6 можно отличить от случайной последовательности при наличии подходящего количества выбранного шифротекста (для r-го раунда необходимо бит текста). Таким образом, уже для 4-го раунда сложность будет значительной – , что делает атаку практически нереализуемой.
В данной работе предлагается новая атака, которая позволяет найти секретный ключ блокового шифра за время, существенно меньшее, чем в случае линейного и дифференциального криптоанализов, а также атаки, основанной на традиционном исследовании статистических свойств шифров. Например, для 5-го раунда RC6 временная сложность предлагаемой атаки равна , а в общем случае: . Атака основана на исследовании статистических свойств шифра RC6 при помощи разработанного Б.Я. Рябко статистического теста «стопка книг», который, по многочисленным исследованиям, является лучшим на текущий момент статистическим тестом.
В диссертации исследована эффективность статистического теста «стопка книг» на примере сравнительного анализа его с другими тестами, а также анализа им некоторых видов генераторов случайных чисел. Проведены исследования эффективности градиентной атаки на примере шифров RC6, Blowfish, MARS, IDEA, CAST-128; показаны пределы её современной практической и теоретической применимости, получены математические зависимости между эффективно взламываемыми раундами и количеством требуемых вычислительных ресурсов. Выявлены условия применимости и расширяемости атаки на произвольное количество раундов, а также особенности применения атаки и возможные её улучшения на конкретных примерах каждого из шифров. Также в данной работе показан метод подбора оптимальных параметров для статистического теста, а также их влияние на атаку; исследована временная сложность атаки и её зависимость от параметров теста и объёма шифротекста; показаны теоретические потребности в вычислительных мощностях, необходимых для осуществления атаки.
Скачать текст статьи можете здесь.
A.S.
