Preliminary evaluation of a minimal number of rounds in lightweight block ciphers for providing their satisfactory stati.pdf Одно из применений итеративных блочных шифров - это генерация псевдослучайных чисел. Для этой цели часто используется режим CTR, подразумевающий последовательное шифрование значений некоторого счётчика и формирование псевдослучайной последовательности из выходных блоков или их частей. При этом удовлетворительные статистические свойства выходной последовательности могут быть обеспечены значительно меньшим числом раундов (обозначим его Rmin), чем полное число раундов шифра (обозначим его R). Очевидно, что сокращение числа раундов увеличит производительность шифров и позволит генерировать псевдослучайные числа быстрее. Причём даже если такой усечённый шифр имеет высоковероятные характеристики (линейные, дифференциальные, интегральные и пр.), он сможет генерировать псевдослучайные последовательности с удовлетворительными статистическими свойствами в силу того, что вероятность появления блоков с требуемыми на входе шифра свойствами может быть ничтожно малой. Поскольку блочные шифры претендуют на универсальность, решая целый спектр прикладных задач (генерация псевдослучайных чисел является одной из них), то при создании новых шифров помимо R, возможно, имеет смысл указывать и Rmin, обеспечивающее удовлетворительные статистические свойства, не гарантируя криптографической стойкости. Уже сейчас при варьировании длины ключа задаётся различное число раундов у шифров, например AES, CLEFIA, Piccolo, SIMON или SPECK. В частности, для шифра AES предполагается, что 10 раундов должны обеспечивать отсутствие атак быстрее 2128, 12 раундов - быстрее 2192, а 14 раундов - быстрее 2256. В работе приводятся результаты статистического анализа легковесных итеративных блочных шифров (и нескольких известных), цель которого - осуществить предварительную оценку Rmin. Значительная часть реализаций шифров взята из библиотеки BLOC [1, 2]. Исследование проводилось при помощи статистического теста «стопка книг» [3, 4], который ранее уже применялся для анализа других блочных шифров [5-7]. Данный тест подразумевает вычисление статистики x2, подчиняющейся распределению хи-квадрат, если элементы выборки равномерно распределены. Число степеней свободы в распределении хи-квадрат определяется параметром теста - количеством частей в структуре данных «стопка книг». В настоящей работе этот параметр равен 2, а число степеней свободы - 1. При тестировании для каждого шифра варьировалось число раундов: 1, 2, 3 и т. д. Для каждого раунда генерировалось по 10 выборок (на 10 случайных мастер-ключах) размера 226 байт (224 32-битовых слов) и по каждой из них вычислялась статистика x2. Выборки генерировались следующим образом: в зависимости от шифра блоки представлялись в виде двух, трёх или четырёх 32-битовых слов и в качестве элементов выборки использовались первые слова каждого выходного блока; на вход шифра подавались блоки, где все слова, кроме второго, равны нулю, а второе слово менялось от 0 до 224 - 1. Значения статистики x2 сравнивались с квантилью хи-квадрат уровня значимости 0,05 с одной степенью свободы. При этом для каждой серии из 10 таких выборок подсчитывалось число U0,05, означающее количество превышений статистикой x2 данной квантили (табл. 1). Таблица 1 Символические обозначения U0,05 0-2 3-5 6-7 8-10 Обозначение - Т ± + Поскольку статистические свойства шифра улучшаются с ростом числа раундов, то при определённом числе раундов распределение выборки не отличается от равномерного. Данное число (обозначим его через Rmin) возьмём в качестве предварительной оценки для Rmin. Результаты экспериментов показали, что в среднем рассмотренные блочные шифры сохраняют удовлетворительные статистические свойства при сокращении числа раундов в них до 10-30 % от полного числа раундов (табл. 2 и 3). Статистический анализ, результаты которого представлены здесь, является предварительным в том смысле, что он даёт минимальную границу Rmin. В частности, более тщательный подбор входной последовательности и использование других статистических тестов может «забраковать» большее число раундов. Таблица 2 Блочные шифры, для которых отклонения от равномерного распределения фиксируются при более чем 13 раундах Раунды 1-14 15 16 17 18-24 25 26-27 28-29 30 Rmin R % Simon + T - T - - - - - 18 32-72 25-56 Katan64 + + + + + + - + - 30 254 12 Ktantan64 + + + + + + - + - 30 254 12 Таблица 3 Блочные шифры, для которых отклонения от равномерного распределения фиксируются не более чем при 13 раундах Раунды 1 2 3 4 5 6 7 8 9 10-13 14 Rmin R % XTEA + + 3 32 6 SPECK + + + + + 6 22-34 15-23 CLEFIA + + + + + 6 18-26 19-28 Piccolo + + + + + 6 25-31 16-20 KLEIN + + T 4 12-20 10-17 mCrypton + + + - T 6 12 25 LED + + + 4 32-48 6-10 Noekeon ± 2 16 6 MIBS + 2 32 3 IDEA + 2 8.5 12 AES + + + 4 10-14 21-30 DESXL + 2 8 25 Lblock + + + + + + + ± -- - 9 32 25 Present + + + + + + + ± -- - 9 31 26 Twine + + + + + + + + -- - 9 36 22 Hight + + + + + + + + + - - 10 32 28 Sea + + + + + + + + + - - 10 51 18 Skipjack + + + + + + + + + + - 14 32 34 Более детальный анализ с подробным описанием экспериментов планируется опубликовать в одной из последующих работ.

Скачать электронную версию публикации