Анализ неполноактивных усиленных S-Box применительно к ECHO и Grøstl

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 16:07, 21 декабря 2015.
Non-full-active Super-Sbox Analysis:

Applications to ECHO and Grøstl

Finding Second Preimages of Short Messages for.png
Авторы Yu Sasaki [@: 1]
Yang Li [@: 2]
LeiWang [@: 3]
Kazuo Sakiyama [@: 4]
Kazuo Ohta [@: 5]
Опубликован 2010 г.
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Содержание

Аннотация В данной работе мы представляем не полностью активный мощный S-box анализ, который может выявлять неидеальные свойства класса AES подобных перестановок с малой сложностью. Мы применяем данную методику для кандидатов второго цикла SHA-3 ECHO и Grostl. Первое приложение используется для ECHO перестановок с полным циклом (с циклом 8), и строит блоки сообщения для 256-битного и 224-битного размера выходных значений. Используя совокупность некоторых отличительных характеристик ECHO, наша атака выявляет неидеальное свойство с временной сложностью и количеством требуемой памяти . Сложность, в особенности в конкретных условиях времени и пространства памяти, в данном случае кардинально меньше, чем у предыдущих наилучших атак, которым требуется . Отметим, что данный результат не представляет какой-либо угрозы для безопасности функции сжатия ECHO или для общей хэш функции. Мы также показываем, что наш метод может выявлять неидеальные свойства 8-циклических Grostl-256 перестановок с реальной сложностью, а в заключении расписано как наш подход улучшает атаку коллизий на 7-циклическую Grostl-512 функцию сжатия. Наш метод основывается на ряде атак для AES подобных хэш функций, а именно на оценочной атаке и мощном Sbox анализе. Основная идея в том, чтобы использовать новый дифференциальный путь состоящий только лишь из не полностью активных элементов.
Ключевые слова: AES-подобные перестановки, ECHO, Grostl, SHA-3, Мощный Sbox.

Введение

Хэш функции очень широко используются в криптографических приложениях. После взлома MD5, SHA-1 [1][2], криптографы начали поиск безопасных и эффективных конструкций хэш функций. Для этих целей, NIST начало конкурс для выявления будущего стандарта хэш функции названного SHA-3 [3].

В данном конкурсе с SHA-3, 14 алгоритмов рассматривались как кандидаты на реализацию во втором цикле. В настоящее время, нельзя сказать, что какой-либо из них можно просто взломать в связи с наличием важных свойств безопасности, таких как стойкость против коллизий и прообразов. Однако, для некоторых кандидатов, построение блоков таких как функции сжатия и начальные перестановки, привело к наличию некоторых свойств далёких от идеальных. Хотя это действенно не влияет на безопасность хэш функций, но анализ построения таких блоков оказывается довольно полезным для понятия потенциальной слабости, границы безопасности, достоверности доказательства безопасности и т.д.

Многие из кандидатов SHA-3 основывались на реализации схемы AES [4] [5]. Недавно, были выполнены выдающиеся работы по криптоанализу AES-подобных хэш функций или перестановок. В особенности хочется отметить Оценочную атаку предложенную Менделем и др. на FSE 2009 [6]. Атаку начинающуюся в середине также предложенную Менделем на SAC 2009 [7], а Мощный-Sbox анализ реализованный для оценочной атаки сделанный Ламбергером и др. на Asiacrypt 2009 [8] и Гилбертом, Пейрином на FSE 2010 [9] нашёл широкое применение в их приложениях и является отличным аналитическим приёмом. В действительности, атака основанная на оценке границ применялась для нескольких кандидатов SHA-3 , таких как Grostl [10], ECHO [11], JH [12], Cheetah [13], LANE [14], Twister [15]. Она также реализовывалась для других хэш функций таких как Whirlpool [16] и хэшированные модификации AES.

ECHO [11], разработанный Банаджилом и др. является одним из двуциклических алгоритмов в SHA-3 использующей 2048-битную AES-подобную перестановку. Число циклов в данной перестановке будет 8 для ECHO-224 и -256, и 10 для ECHO-384 и -512. На FSE 2010 Гилберт и Пейрин показали, что ECHO перестановку с полным циклом (8-циклов) можно выделить по признакам из идеальной перестановки за время и при наличии памяти с помощью Мощного-Sbox анализа [9]. После этого, Пейрин[17][18] улучшил эту атаку, которой теперь требуется как времени, так и памяти. В связи с тем, что 8-циклическая ECHO перестановка строит блок для генерации 256-битных либо 224-битных хэш значений и часть сжатия от 2048-бит до 256- или 224-бит не учитывается, отрицательное воздействие данной атаки будет незначительным. К тому же, как это отмечалось в работе [9], время и память не могут быть меньше чем . Подводя итог, можно сказать, что пока не существует достаточно сильного анализа ECHO хэш функции как и функции сжатия. Даже для данных атак на перестановки с полным циклом, сложность слишком высока.

Отметим, что атака Пейрина [18] была также и на уменьшенную версию ECHO функции сжатия. Недавно Шлафер представил анализ ECHO [19], а Идегучи и др. опубликовали анализ Grostl [20]. Их результаты представлены в Таблице 1.

Наш вклад

В данной работе мы показали не полностью активный Мощный-Sbox анализ, который может выявлять неидеальные свойства класса AES-подобных перестановок с малой сложностью. Для демонстрации его применения, сперва реализуем не полностью активный Мощный-Sbox анализ 8-циклической Grostl-256 перестановки, которая является AES-подобной перестановкой состоящей из элементов. Эта атака может определить неидеальное свойство 8-циклической Grostl-256 перестановки за время и память , тогда как выявлению того же свойства идеальной перестановки потребуется . Затем применим эту методику к ECHO перестановке с полным циклом (8-циклов) путём оптимизации атаки для некоторых определённых рассматриваемых специфических свойств ECHO. Эта атака может определить неидеальное свойство 8-циклической ECHO перестановки за время и память , тогда как выявлению того же свойства идеальной перестановки потребуется .


Таблица 1. Сравнение результатов атаки на ECHO и Grostl
Цель Циклы Время Память Тип атаки Страница
ECHO-256/-224 перестановка 8(полный)
8(полный)
8(полный)
7
7








Устройство различения по признакам
Устройство различения по признакам
Устройство различения по признакам
Устройство различения по признакам
Устройство различения по признакам
[9]
[26]
Раздел 5.2
[26]
Прил. А
ECHO-256/-224 простая функция сжатия 3
3


Устройство различения по признакам
Устройство различения по признакам
[26]
Прил. B
Grostl-256 перестановка 8
8
8




Устройство различения по признакам
Устройство различения по признакам
Устройство различения по признакам
[9]
[28]
Раздел 4.4
Grostl-512 функция сжатия 7
7


Коллизия с полусвободным стартом
Коллизия с полусвободным стартом
[17]
Раздел 5.3
ECHO-256 хэш функция 4
5


Коллизия
Устройство различения по признакам
[27]
[27]
ECHO-256 / -512 функция сжатия 3/3
7/7


Коллизия с полусвободным стартом
Устройство различения по признакам
[27]
[27]
Grostl-256 функция сжатия 10(полный) Устройство различения по признакам [26]
Grostl-512 функция сжатия 11 Устройство различения по признакам [26]


Отметим, что 8-циклическая ECHO перестановка является блоком для построения ECHO-256 и ECHO-224. Насколько нам известно, это первый полученный результат для перестановки ECHO с полным циклом который может работать при времени и памяти (или производных этих факторов) ниже (или ). Отметим, однако, что свёртка в функции сжатия ECHO важна с точки зрения безопасности и наше устройство различения по признакам нельзя расширить ни для ECHO функции сжатия, ни для хэш функции. И наконец, покажем, что наш подход также улучшает расходуемую память при атаке с коллизией полусвободного старта на 7-циклическую Grostl-512 функцию сжатия до при исходной . В приложениях, мы показали новые результаты для ECHO перестановки с уменьшенным циклом и функции сжатия. Также там представлена атака на 7-циклическую ECHO перестановку и устройство различения по признакам с малой сложностью для 3-циклической простой ECHO-256 функции сжатия. Результаты атаки показаны в Таблице 1. Технические детали по данному вопросу заключается в следующем.

Устройства различения по признакам для AES-подобных перестановок

Мы представили новый способ анализа Мощного-Sbox, который работает для класса AES-подобных перестановок в общем случае. Основная идея в том, чтобы использовать дифференциальный путь части которого, в частности внутри Мощного-Sbox, входят не полностью активные элементы. Что касается не активных бит, разница между операциями над СубБитами и ИнверснымиСубБитами всегда будет 0 из-за их значений. Следовательно, злоумышленники могут спокойно выбрать данное значение без взлома дифференциального пути. Это свобода действий в выборе степени позволяет злоумышленникам контролировать значения (или разницу между операциями над СубБитами) других битов внутри Мощного-Sbox для возникновения эффективной взаимосвязи.

Рассмотрение свойства ECHO перестановки

Объясним два умозаключения относительно ECHO перестановки при оперировании с усечённым зависимым от битов дифференциальным путём. Первое заключается в том, что линейность двух совмещённых линейных операций (MixColumns внутри BigSB и последующей BigMC) следует учесть при корректном вычислении сложности для конкретного дифференциального пути. Второе – есть некоторый выбор дифференциальных путей внутри BigSB который позволяет злоумышленнику уменьшить сложность.

В Раздле 2, мы описали AES-перестановку, ECHO, и Grostl. В Разделе 3 мы показали предыдущие работы. В Разделе 4, рассмотрена тема не полностью активного Мощного-Sbox анализа и его применение в 8-циклической Grostl-256 перестановке. В Разделе 5, представлена атака на ECHO перестановку с полным циклом и 7-цикловую Grostl функцию сжатия. В Разделе 6, мы подытожили выводы данной работы. Результаты по другим вариантам ECHO можно найти в приложениях.

Спецификации

AES [4][5] есть 128-битный блочный шифр представленный как элемент бита. Здесь мы рассмотрим общую AES-подобную перестановку с элементом, где каждый элемент есть с-битное слово. Строка и столбец позиции слова/бита определяется и , где, соответственно Как показано на Рис. 1, элемент модифицируется четырьмя операциями за цикл AES-подобной перестановки.

  • SubBites (SB): замена нелинейного слова/бита согласно S-box.
  • ShiftRows (SR): каждое слово/бит в строке поворачивается влево относительно позиции.
  • MixColumns (MC): перемножается каждая колонна MDS матрицы.
  • AddRoundKey (AK): бит-зависимая операция XOR текущего элемента и константы

ECHO перестановка

ECHO [11] созданная Бенаджилом и др. есть хэш функция использующая 2048-битную AES-подобную перестановку в качестве создающего блока. Данная перестановка состоит из 8 циклов для ECHO-224 -256, и 10 циклов для ECHO-384 -512. 2048-битный начальный элемент можно представить как матрицу где каждое значение есть 128-битный AES элемент называемый BigWord.

Рисунок 1. Операции внутри цикла AES-подобной перестановки.

Цикловая операция в ECHO перестановке перемножает 128-битные BigWord’ы вместо 8-битных значений.

Рисунок 2. Один цикл ECHO перестановки.
Рисунок 3. Обозначения для ECHO BigWords.

Первый цикл ECHO перестановки показан на рисунке 2 и имеет три операции:

  • BigSB: замена каждого BigWord на реализующие два AES-цикла.
  • BigSR: каждое BigWord в строке поворачивается влевоотносительно позиции .
  • BigMC: перемножаются каждые 4 бита ECHO элемента в MDS матрице.

Для простоты соответствующего анализа ECHO, как показано в [18], мы определим 4 типа бит-зависимых усечённых дифференциальных путей BigWord так, как показано на Рис. 3.

Grostl перестановка и функция сжатия

Grostl разработанный Гуараварамом и др.[10] является другой хэш функцией созданной на основе AES-подобных перестановок. Grostl-256 перестановка использует элемент, где каждое значение будет 8 битным, тогда как Grostl-512 перестановка использует элемент . Число циклов в перестановке будет 10 для Grostl-224 -256, и 14 для Grostl-384 -512. Grostl-512 использует другие ShiftRow операции нежели Grostl-256, где биты в 7 строке поворачиваются в лево относительно 11 позиции.

Предыдущие работы

Атака на оценку границ предложенная Менделем и др. на FSE 2009 [6] является очень полезной для анализа AES-подобных перестановок. Она делит дифференциальный путь на 2 части; входящий и выходящий этапы. Входящий этап контролирует большинство значимых элементов в дифференциальном пути с очень малой средней сложностью, тогда как выходящий этап пути реализуется вероятностно. Но необходимо быть уверенным, что общее количество генерируемых начальных точек во входящей фазе будет достаточным для выполнения выходящей.

Атака начинающаяся с середины была предложена Менделем и др. на SAC 2009 [7]. Она улучшает атаку оценки границы с помощью расширения количества контролируемых циклов от 2 до 3. Идея в том, чтобы исключить независимость и свободу действия каждой процедуры поиска настолько, насколько это возможно. В результате, без увеличения времени и памяти, можно выполнить 3 цикла дифференциального пути.

Мощный-Sbox анализ для оценочной атаки был независимо представлен Ламбергером и др. на Asiacrypt 2009 и Гилбертом, Пейрином на FSE 2010 [9]. Мощный-Sbox совмещает в себе 2 нелинейных уровня и 1 уровень распределения на 1 нелинейный уровень с большим элементом замены. Можно расширить входящую фазу с помощью ещё одного цикла. В результате, злоумышленнику необходимо затратить больше времени и памяти для реализации дифференциального свойства Мощного-Sbox.

Пейрин предложил дифференциальный путь для ECHO с постепенным увеличением [18]. Это способствует уменьшению числа активных битов внутри активного BigWord, и т.о. уменьшается сложность атаки.

Описание не полностью активно анализа мощного-Sbox

В данном разделе мы используем следующие обозначения:

  • : число строк и столбцов в элементе
  • : число бит в каждой(ом) клетке (слове) элемента.
  • : число не активных столбцов с начальными значениями дифференциального пути.
  • : элемент где столбцов полностью активны, а именно, бит активны.
  • : элемент, где больше SR и .
  • F: элемент, в котором все биты активны.
  • : элемент, в котором бит становятся неактивными относительно элемента.

В анализе мощного-Sbox, в связи с тем что мы следуем методике Гилберта и Пейрина [9], сложность атаки будет ограничена снизу . В данном разделе мы представим новую реализацию называемую не полностью активный анализ Мощного-Sbox, который может выявлять неидеальные свойства с малой сложностью. Сперва рассмотрим дифференциальный путь, входная часть которого, в частности внутри мощного-Sbox, состоит из не полностью активных элементов. Для неактивных бит, дифференциальный переход от 0 к 0 всегда будет сохранять соответствующее значение, и т.о. злоумышленник может спокойно выбрать это значение не взламывая путь. Это даёт злоумышленнику свободу выбора степени для корректировки других бит внутри Мощного-Sbox.

Не полностью активный анализ Мощного-Sbox можно применять к AES-подобным перестановкам. Подытожим, что операция MixColumns состоит из MDS матрицы [5]. А именно, сумма числа активных битов во входном и выходном элементах будет больше или равна , в противном случае 0.

Не полностью активный усечённый дифференциальный путь

Покажем общее описание не полностью активного усечённого дифференциального пути. Данный дифференциальный путь имеет параметр , которым обозначается число неактивных столбцов в начальном элементе. Этот параметр определяет сложность атаки. Дифференциальный путь показан на рис. 4 для случая и .

Для получения дифференциального пути мы начнём с элемента появляющегося после 2-ого и 5-ого циклов, элементы которых будут и , соответственно. Затем необходимо проверить будет ли это дифференциальное распределение для MixColumns операции в 4-ом цикле обладать MDS свойством. Т.к. входной и выходной элементы имеют и активных бит в каждом столбце, соответственно, то сумма активных битов входа и выхода равна .


Рисунок 4.
(Внизу) Новый дифференциальный путь для 8-цикловых AES-подобных перестановок с соответствующим и и .
(Вверху) Предыдущий путь анализа Мощного-Sbox [9].

Следовательно, дифференциальный путь будет обладать свойством MDS. Теперь, определим дифференциальное распределение для 6-ого цикла. Число активных бит необходимо уменьшить настолько, насколько это возможно после 6-ого цикла, для того чтобы сделать конкретное неидеальное свойство стойким при идеальной перестановке. Из этого следует, что нам нужно максимизировать число не активных битов удовлетворяющих MDS свойству, получающихся в результате прохода через элемент . Аналогично, сперва определяем дифференциальное распределение для 2-ого цикла. Реализуем такое же количество активных битов как и в элементе на 6-ом цикле, результирующим значением которого будет . Оставшийся путь будет детерминистическим.

Входящий этап с малой сложностью

Здесь мы объясним как вычислить входящий этап для нашего пути. Детально значения во входящем этапе представлены на Рис. 5, с обозначением каждого элемента как , где . Входящий этап начинается с элемента следующего после SubBytes в 3-ем цикле () и с элемента являющегося входным значением для 6-ого цикла (). Целью входящего этапа является нахождение парных значений дифференциального пути от до . Можно найти таких парных значений при вычислениях и памяти.

Элемент и включают в себя и активных бита, соответственно. Сперва, выберем и зафиксируем разность всех активных бит для и разность активных бит из всех активных бит для . Затем, для каждой возможной разности последних активных бит , сохраним соответствующее парное значение. В связи с линейностью операций, можно вычислить соответствующие разности для элемента и соответствующие s-битные разности для каждого столбца . Анализ Мощного-Sbox можно применить для процессов проходящих между и , а именно, для расчёта используемых там столбцов независимо друг от друга. Предыдущему анализу Мощного-Sbox требовалось времени и памяти для этих вычислений, тогда как мы эффективно связали эти элементы с помощью плавающих степеней неактивных значений. Далее мы будем показывать только вычисления Мощного-Sbox в крайнем левом столбце, которые выделены жирным прямоугольником на Рис. 5. Другие столбцы можно связать друг с другом тем же способом.

Рисунок 5. Входящий этап для нового дифференциального пути с не полностью активными элементами.
Рисунок 6. Процедуры вычисления внутри Мощного-Sbox.

Процедура вычисления внутри Мощного-Sbox

Операции внутри Мощного-Sbox показана на Рис. 6. Т.к. операция ShiftRows ни коим образом не влияет на то, что происходит внутри мощного-sbox, мы пропускаем её в рисунке 6. Для того, чтобы подчеркнуть вычисление мощного-sbox по столбцам мы обозначили элементы внутри мощного-sbox как на рис. 6. Целью данной процедуры является эффективное получение парных значений, удовлетворяющих фиксированной части разностей и . Эта процедура находит парных значений с временной сложностью и памятью . Атака проходит следующим образом.

  • 0.Для каждого активного бита эта разность фиксируется в и , вычисляется SB и его инверсия для всех возможных значений и фиксированной разности. Эти значения и соответствующие разности на выходе сохраняются в виде таблицы. Сортируем таблицу согласно выходным разностям т.о., чтобы таблице потребовался доступ памяти 1. В результате, получаются таблицы относительно
  • 1.Выбираем разность одного активного бита в . (На рис. 6 мы выбрали верхний бит )
  • 2.У нас осталось активных бит в и необходимо удостовериться в том, что тоже число битов в будет неактивными. Это выполняется путём решения системы уравнений и получением одного решения данной системы. В результате, разности в и компонуются и фиксируются конкретным образом.
  • 3.Посредством фиксированной разности и заданной разности , для каждого активного бита, получаем пару значений, связанных с разностями по таблице сгенерированной на Шаге 0. Делаем тоже самое для фиксированной s-битовых разностей и . Отметим, что значения для неактивных битов пока не зафиксированы.
  • 4.Затем связываем значения активных битов и . Используем свободный выбор степени неактивных битов для их эффективного получения. Будет s неактивных битов в и s активных битов в \sharp 5A, значения которых фиксируются на Шаге 3. Решая систему уравнений, мы вычисляем значения s неактивных битов в , т.о., чтобы фиксированные биты были последовательными.
  • 5.После фиксирования значений в , вычисляем нефиксированный активный бит в , и дальше рассчитываем соответствующее значений в . Сохраняем полученные значения и разности элементов и в таблице.
  • 6.Выполняем Шаг 1 и Шаг 5 раз изменяя разность выбранного активного бита в .

Сложность входящего этапа

Полагаем, что достаточно малы по сравнению с (например, , , а как показано на рис. 4). Шагу 0 требуется вычислений и памяти. Всё от Шага 1 до Шага 4 можно вычислить со сложностью 1 (основываясь на предположении о том, что затраты на просмотр таблиц и решение систем уравнений размером в расчёт не беруться). Шаг 5 использует 1 памяти. Т.к. от Шага 1 до Шага 5 мы повторяем процедуру раз на Шаге 6, сложность её будет по времени равна , а относительно памяти . Отметим, что значений и разностей нефиксированных активных бит сохраняются в таблице. Поэтому, в среднем мы получаем 1 решение для любой разности нефиксированного бита.

После окончания расчёта всех Мощных-Sbox, выбираем разность нефиксированного бита в как показано на рис. 5. Для каждой из возможных разностей, вычисляем соответствующую разность в и получаем значений, которое связывает и при анализе каждого мощного-sbox. В итоге, можно получить начальных точек, которые будут решениями для входящего этапа при времени равном и памяти . Другими словами, мы получаем начальную точку в среднем за время 1.

Выходящий этап и свободный выбор степени

После входящего этапа мы вычисляем соответственно выходящий. Дифференциальный путь показанный на Рис. 4 имеет два вероятностных дифференциальных распределения: 1) предвычисление для второго цикла и 2) последующее вычисление для шестого. В обоих циклах операциям MixColumns и InvertMixColumns необходимо произвести расчёт для неактивных битов. Поэтому, для каждого из этих циклов вероятность успеха будет . К тому же, этой атаке требуется начальных точек для выходящего этапа, а каждая начальная точка будет генерироваться в среднем за время 1. Следовательно, за время , мы найдём пару следующих дифференциальных путей.

Также нам необходимо проверить достаточна ли для данного случая возможная свободная степень. Наша атака начинается с элементов и на рис. 5. и включают в себя и активных бита соответственно, и т.о. получаем общее число свободных степеней .

Таблица 2. Сложность нахождения свойства при нашей атаки и идеальной перестановке
1 2 3 4 5 6 7 8
Часы
Идеальный

Из этого следует, что когда параметр удовлетворяет неравенству , которое упрощено ниже (1), мы имеем достаточно свободных степеней.

(1)

Целевой класс AES-подобных перестановок и их примеры

Давайте рассмотрим сложность идеальной перестановки. Крайние MixColumns не принимаются во внимание т.к. они полностью линейны. Поэтому, задача сводиться к нахождению crs-битной коллизии. Её можно найти с помощью атаки реализуемой по парадоксу дней рождения, т.к. злоумышленнику предоставлено достаточное количество свободных степеней согласно (1). Из этого следует, что сложность для идеальной перестановки будет . Сравнение анализа не полностью активного мощного-sbox и его идеального случая показаны в таблице 2.

Из Таблицы 2 можно заметить, что это условие реализации нашей атаки. В следствии этого, наша атака не применима для AES . Отметим, что ECHO перестановка рассматривается как AES-подобная перестановка с на BigWord уровне. Однако, имеют место и другие конструкции и это позволяет нам значительно уменьшит сложность атаки на ECHO перестановку. См. Раздел 5 для детального описания данного вопроса.

Давайте рассмотрим приложение для реального примитива. Grostl-256 использует AES-подобную перестановку с . В предыдущем анализе мощного-sbox [9], 8-цикловая перестановка различалась по признакам за время и при памяти , что является слишком большими значениями для реализации. В нашей атаке, выбирается s = 3, дифференциальный путь для данного случая показан на Рис. 4. Последовательно, из Таблицы 2, можно выявить пары значений следующих дифференциальных путей за время и память , тогда как на нахождение пары значений при идеальной перестановке затрачивается , что неосуществимо. Выбрать другой s вполне возможно, при том, что он будет .

Приложения для ECHO и Grostl

Новые наблюдения по ECHO

В данном разделе мы опишем некоторые новые наблюдения касательно ECHO перестановки относительно бит-зависимого дифференциального пути.

Сложность анализа объединённых MixColumns и BigMC.

В ECHO перестановке, 2-цикловая AES перестановка внутри BigSB может рассматриваться как нелинейный уровень мощного-sbox и уровень распределения ShiftRows, MixColumns, AddRoundKey. Отметим, что от второй MixColumns внутри BigSB до последующей BigMC всё выполняется последовательно. Мы показали, что линейность объединенных MixColumns и BigMC необходимо рассматривать для того, чтобы корректно вычислить сложность некоторых дифференциальных путей.

Рисунок 7. Дифференциальный путь для 1-цикловой ECHO перестановки.

К примеру, проверим сложность для дифференциального пути изображённого на Рис. 7 полагая, что разности и реальные значения для элемента могут быть любыми. В предыдущем анализе [приложение В], сложность данного дифференциального пути разбивалась на три части, которые анализировались независимо. Элементы можно рассчитать, когда выход каждого активного мощного-sbox будет иметь только 1 активный бит. Т.к. в общем случае необходимо чтобы 12 бит были нулевыми, вероятность можно рассматривать как . Сложность от до будет . И т.к. 12 бит должны быть нулевыми от до , вероятность останется такой же. В результате общая вероятность будет . Однако, мы показали, что MixColumns и BigMC нельзя рассматривать независимо, и т.о. нужно пересмотреть значение вероятности для получения корректного.

Можно увидеть, что свобода выбора разности для элементов будет максимально равна , т.к. у есть только 4 активных бита. Как противоречие предыдущему анализу, при таком выборе разности для ( ) будет невозможно разрешить дифференциальное распределение () . Однако, мы показали, что это распределение вычисляется только с вероятностью , и т.о. достаточно для этого.

Это можно также объяснить двумя утверждениями. Во-первых, для активного бита с фиксированной позицией и фиксированной матрицы MDS использующейся в MixColumns между и , 4 4 активных бита внутри каждого активного BigWord на имеют линейную взаимосвязь. Поэтому, если BigMC генерирует необходимую разность НА для одной из 4 позиций активных битов с вероятностью (например, 4 верхних левых бита из 4 активных BigWord на генерируют 1 активный бит вверху слева элемента ), другие три позиции активных бита дифференцируются аналогичным образом в с вероятностью 1. Другая интерпретация заключается в том, что можно поменять местами операции, а именно выполнить сперва BigMC, а затем MixColumns. Когда 4 активных бита в генерируют только 1 активный бит для BigMC с вероятностью , то дифференциальный путь от до будет через MixColumns будет рассчитываться с вероятностью . В результате, общая сложность равна , вместо . Отметим, что этот факт был независимо получен в [19] о пределён как SuperMixColumns.

Свободный дифференциальный путь внутри BigSB

Можно использовать свободу выбора дифференциального пути BigSB для уменьшения сложности данной атаки. Наши атаки используют только разности между начальным и конечным элементами перестановки.

Снова воспользуемся дифференциальным путём на Рис. 7, как примером. Для того чтобы решить дифференциальный путь, необходимо 4 активных бита для уровня установить в одинаковые позиции внутри самого левого столбца каждого BigWord.

Рисунок 8. Не полностью активный дифференциальный путь для 8-цикловой Echo перестановки.
Рисунок 9. Входящий этап для 8-циклической ECHO перестановки.

В результате, дифференциальный путь внутри BigSB имеет 4 выбора для расстановки активных битов, и т.о., сложность для дифференциального пути изображённого на Рис. 7 можно уменьшить от до .

Атака на ECHO перестановку с полным циклом

Усечённый дифференциальный путь

Мы используем дифференциальный путь представленный в Разделе 4.1 с параметрами на BigWord уровне, показанном на Рис. 8. Также воспользуемся определением BigSB, где , для выявления того, что x, который является входным значением дифференциального BigSB, меняется на после первого AES цикла и на после второго.

Входящий этап

Детально дифференциальный путь для входящей фазы показан на Рис. 9. Входящий этап начинается с середины BigSB в третьем цикле ( ) и для входных значений и продолжается до 6-ого цикла ( ), где дифференциальная форма в будет С. Сперва выберем и зафиксируем разность и разность одного из активных BigWords , и вычислим соответствующие разности и . Во входящем этапе для каждой из возможных разностей нефиксированного активного BigWord в найдём пару значений, которые удовлетворяют выбранным разностям и . Процедура атаки будет такая же как и в Разделе 4.2, с некоторыми специфическими оптимизациями для ECHO. Теперь опишем детально вычисление 1 мощного-sbox ECHO размером 128 бит.

  1. Генерируем таблицу для каждого из 4 активных BigWord с фиксированной разностью в и . Согласно процедуре в Разделе 4.2, это потребует времени и столько же памяти. В [7] отмечается, что это можно эффективно реализовать проанализировав BigSB. BigSB можно рассматривать как 4 мощных-sbox (SB,SR,MC,AK,SB) размером 32 бита и линейную часть (SR,MC,AK). Тогда для заданной выходной разности BigSB, мы можем вычислить соответствующую разность линейной части, и т.о. значения находятся с помощью рассмотрения четырёх 32-битных Мощных-sbox независимо. Следовательно, такие таблицы для 4 BigWords можно сгенерировать путём вычисления 16 мощных-sbox, на что потребуется времени и памяти.
  2. Выбираем разность одного активного BigWord в .
  3. Решая систему уравнений, вычисляем разности 2 активных BigWord в т.о., чтобы 2 целевых BigWord в активными не были.
  4. Для каждого активного BigWord с фиксированной разностью, получаем пару значений, которые связывают разности между и , и между и с помощью анализа таблиц сгенерированных на Шаге 0.
  5. Решая систему уравнений, вычисляем значений 1 неактивного BigWord в , т.о. чтобы фиксированное значение 1 BigWord в было последовательным.
  6. С фиксированной парой значений в , вычислим нефиксированное активное BigWord в и . Только если рассчитанная разность имеет диагональ вида D, сохраняем полученные значения и разности элементов и в таблице.
  7. Выполняем всё от Шага 1 до Шага 5 раз меняя разность выбранного BigWord в .

На Шаге 0, таблица генерируется за время и при памяти. От Шага 1 до Шага 5 всё выполняется раз. В Шаге 5, вычисляемая разность имеет диагональ формы D с вероятностью , и т.о. мы сохраняем данных после итераций. Отсюда следует, что сложность для мощного-sbox размером 128 бит будет составлять вычислений и памяти. Отметим, что для 4 мощных-sbox необходимо памяти. В заключении, входящая фаза генерирует начальных точек за вычислений и при памяти, что будет вычислениями в среднем для генерации 1 начальной точки.

Вероятность успеха и свободный выбор степени. Если всё подробно рассматривать, то оказывается, что шаг 3 успешен только вероятностно. Таблица для каждого BigWord состоит из 4 Мощных-Sbox размером 32 бита. Предположим, что каждый Мощный-Sbox обладает тем же свойством, что и AES-Sbox. А именно, для случайной заданной пары входных и выходых разностей, с вероятностью примерно , существует около 2 парных значений, удовлетворяющих разностям. На Шаге 3, выполняется анализ 16 мощных-Sbox. Следовательно, вероятность успеха будет и отсюда получаем всего парных значений. Произведём вычисления шагов 4 и 5 для всех парных значений, и таким образом получим, что они рассчитываются раз в общей сложности для Шага 6. Следовательно, общее время и память для входящей фазы меняться не будет. Обратите внимание, что оценка с помощью средних чисел является неточной только если затраты ресурсов для исходящего этапа меньше, чем для входящего. Т.к. наша атака выполняет входящую фазу раз, то оценка с помощью средних чисел корректна.

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

Исходящий этап

Дифференциальный путь показанный на рис. 8 включает в себя два вероятностных дифференциальных распределения. InverseBigMC в 2-ом цикле. Для каждой из диагональных позиций, Inverse MixColumns выводят один неактивный байт. Вероятность этого будет .

BigSB и BigMC в 6-ом цикле

Для этой части применяются наблюдения объясненные в разделе 5.1. Вероятнее всего, что разности в 2 BigWords распределяются как получаем . Принимая во внимание свободу выбора дифференциального пути внутри BigSB, вероятность становится равной . В операции BigMC, MC вычисляется для 4 позиций. Благодаря свойству совмещённых MixColumns и BigMC операций, все 4 позиции составят 1 неактивных байт с вероятностью в общем случае. В результате, общая вероятность успеха шестого цикла будет .

В конце концов, вероятность успешной исходящей фазы составит .

Общая сложность в сравнении с идеальным случаем

Для нашей атаки генерируется начальных точек и каждая из них создается в среднем при помощи вычислений. Таким образом, общая сложность будет . Отметим, что эта атака требует памяти. С другой стороны, для идеального случая, данное свойство рассматривается как нахождение 512-битной коллизии. Для этого потребуется , что значительно больше, чем при нашей атаке на ECHO.

Улучшение коллизий с полусвободным стартом для 7-циклового Grostl-512

Мы улучшаем атаку с полусвободным стартом коллизии для 7-циклической Grostl-512 функции сжатия предложенной Менделем и др. [21]. Она использует предыдущий анализ Мощного-Sbox и, следовательно, требует памяти. Покажем, что количество требуемой памяти можно свести к при помощи анализа не полностью активных Мощных-Sbox. Из-за того, что наша исходящая фаза такая же, как в [21], мы рассмотрим только входящую фазу.

В Мощном-Sbox анализе для прямоугольного элемента, такого как , несколько мощных-Sboxes содержат неактивный байт. Таким образом, методика объяснённая в разделе 4 может быть применена, а количество данных, сохраняющихся для каждого Мощного-Sbox можно уменьшить. В предыдущем дифференциальном пути [17, рис.7] показанном на рис. 10, 9-ый Мощный-Sbox на занимает полностью активный столбец и выступает в качестве входного и выходного полностью активного столбца, которому требуется памяти. Но факт в том, что это создаёт трудности для всей атаки.

Файл:(Bottom) New differential path for Grøstl-512. (Top) Previous path..png
Рисунок 10. (Внизу) Новый дифференциальный путь для Grøstl-512. (Вверху) Предыдущий путь.

Мы уменьшили количество активных байтов, для которых выбираем разности на начальном этапе входящий фазы ( ). Это приводит к дифференциальному пути, на котором каждый Мощный-Sbox имеет хотя бы один неактивный байт. Новый путь показан в Рис. 10. Каждый Мощный-Sbox может быть рассчитан путём использования процедуры объяснённой в разделе 4.2, что приводит в итоге к генерации начальных точек за время и при памяти. Отметим, что дифференциальное распространение из в должно реализовываться в соответствии с MDS свойством.

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

Выводы

Мы представили не полностью активный анализ Мощного-Sbox, который может выявлять неидеальные свойства класса AES-подобных перестановок с низкой сложностью. Основная идея здесь заключается в использовании дифференциальных путь, состоящих только из не полностью активных элементов. Это дает нам возможность эффективного и свободного контроля Мощных-Sbox. Затем мы применяем методику для перестановки ECHO с полным циклом, приняв при этом во внимание свойства, характерные для ECHO. Отсюда следует, что наша атака может обнаружить неидеальное свойство за время и при наличии памяти . Отметим, что из-за операции свертки, нашу атаку нельзя применить к хэш функции или функции сжатия. Но мы можем применить наш подход к Grøstl для получения атаки на различение по признакам для 8-цикловой Grøstl-256 подстановки с практически реализуемой ресурсоёмкостью, а также для получения улучшенной атаки коллизии с полусвободным стартом для 7-цикловой Grøstl-512 функции сжатия.

(Приложение A) Процедуры атаки на 7-циклическую ECHO перестановку

Используя дифференциальный путь представленный на рис. 11, мы представляем вашему вниманию атаку на 7-цикловую ECHO перестановку за время и при памяти .

  • Шаг 1. Злоумышленник получает значение разности для элемента (из возможных значений) и вычисляет разность для (элемента стоящего после второго SubBytes).
  • Шаг 2. Переход от к может быть разделена на 64 независимых 4-байтовых Мощных-Sbox’а. Для каждого Мощного-sbox с фиксированной разностью выхода, при помощи проверки всех выходных значений, злоумышленник может создать таблицу всех возможных входных значений и разностей. В конце Шага 2, все возможные пары для хранятся в таблице с именем T1, которая состоит из 64 меньших таблиц каждая размером . Следовательно, нам необходимо памяти для этого шага.
  • Шаг 3. Для каждого активного BigWord в , злоумышленник подбирает разность и вычисляет соответствующие разности BigColumn для . Затем злоумышленник проверяет, существует ли рассчитываемая разность в Т1. Если она существует, то злоумышленник использует соответствующие реальные значения для #C при расчете реальных значений для . Эта проверка повторяется для всех возможных разностей каждого активного BigWord , и все возможные разности и реальные значения для сохраняются в новую таблицу с именем T2. Затраты по времени и памяти для шага 3 будут .
Рисунок 11. Дифференциальный путь для 7-цикловой ECHO перестановки.
  • Шаг 4. Для всех возможных пар на каждый активный BigWord , злоумышленник рассчитывает пары для и сохраняет результаты в таблице с именем T3.
  • Шаг 5. Для всех возможных разностей в , злоумышленник вычисляет разности и проверяет присутствует ли рассчитанная разность в T3.

Когда шаги с 1 по 5 применяются к рис. 11, входящая и исходящая фазы объединяются и рассчитываются эффективно. При применении процедуры единожды, за время и при памяти , злоумышленник получает начальные точки. Обратите внимание, что при свободе выбора в разностей для , последующая исходящая фаза может быть спокойно выполнена. В результате, общая сложность будет по времени согласно наблюдениям из раздела 5.1 и при значении памяти.

(Приложение B) Атака на 3-цикловую ECHO-SP функцию сжатия

Заметим, что для атаки в приложении А, не существует конкретных требований касательно разностей элемента . Используя это свойство можно найти неидеальное свойство для 3-цикловой простой ECHO функции сжатия представленной в [11]. Дифференциальный путь показан на рис. 12. Злоумышленник делает так, чтобы разности для были неприменимы в сжатых вычислениях, т.е. для каждой строки BigWords , разность отмеченная как А будет той же самой что и В. Применяя процедуру из приложения А, этот дифференциальный путь можно реализовать за время раз и при памяти, а в идеальном случае затраты будут .

Рисунок 12. Дифференциальный путь 3-цикловой простой ECHO функции сжатия.

Контакты авторов материала

  1. NTT Information Sharing Platform Laboratories, NTT Corporation 3-9-11 Midoricho, Musashino-shi, Tokyo 180-8585 Japan E-mail: [1]
  2. The University of Electro-Communications 1-5-1 Choufugaoka, Choufu-shi, Tokyo, 182-8585 Japan E-mail: [2]
  3. The University of Electro-Communications 1-5-1 Choufugaoka, Choufu-shi, Tokyo, 182-8585 Japan E-mail: [3]
  4. The University of Electro-Communications 1-5-1 Choufugaoka, Choufu-shi, Tokyo, 182-8585 Japan E-mail: [4]
  5. The University of Electro-Communications 1-5-1 Choufugaoka, Choufu-shi, Tokyo, 182-8585 Japan E-mail: [5]

Литература

  1. Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer, R.(ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 19–35. Springer, Heidelberg(2005)
  2. Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full SHA-1. In: Shoup, V.(ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 17–36. Springer, Heidelberg (2005)
  3. U.S. Department of Commerce, National Institute of Standards and Technology:Federal Register /Vol. 72, No. 212/Friday, November 2, 2007/Notices (2007) Non-full-active Super-Sbox Analysis: Applications to ECHO and Grostl 53
  4. 4,0 4,1 U.S. Department of Commerce, National Institute of Standards and Technology:Specification for the ADVANCED ENCRYPTION STANDARD (AES) (Federal Information Processing Standards Publication 197) (2001)
  5. 5,0 5,1 5,2 Daemen, J., Rijmen, V.: The design of Rijndael: AES – the Advanced Encryption Standard (AES). Springer, Heidelberg (2002)
  6. 6,0 6,1 Mendel, F., Rechberger, C., Schl.affer, M., Thomsen, S.S.: The rebound attack:Cryptanalysis of reduced Whirlpool and Grostl. In: Dunkelman, O. (ed.) Fast Software Encryption. LNCS, vol. 5665, pp. 260–276. Springer, Heidelberg (2009)
  7. 7,0 7,1 7,2 Mendel, F., Peyrin, T., Rechberger, C., Schl.affer, M.: Improved cryptanalysis of the reduced Grostl compression function, ECHO permutation and AES block cipher.In: Jacobson Jr., M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 16–35. Springer, Heidelberg (2009)
  8. Lamberger, M., Mendel, F., Rechberger, C., Rijmen, V., Schl.affer, M.: Rebound distinguishers: Results on the full Whirlpool compression function. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 126–143. Springer, Heidelberg (2009)
  9. 9,0 9,1 9,2 9,3 9,4 9,5 9,6 Gilbert, H., Peyrin, T.: Super-Sbox Cryptanalysis: Improved Attacks for AES-Like Permutations. In: Hong, S., Iwata, T. (eds.) FSE 2010. LNCS, vol. 6147, pp. 365–383. Springer, Heidelberg (2010)
  10. 10,0 10,1 Gauravaram, P., Knudsen, L.R., Matusiewicz, K., Mendel, F., Rechberger, C., Schl.affer, M., Thomsen, S.S.: Grostl addendum. Submission to NIST (updated) (2009)
  11. 11,0 11,1 11,2 11,3 Gauravaram, P., Knudsen, L.R., Matusiewicz, K., Mendel, F., Rechberger, C., Schl.affer, M., Thomsen, S.S.: Grostl addendum. Submission to NIST (updated) (2009)
  12. Wu, H.: The hash function JH. Submission to NIST (updated) (2009)
  13. Khovratovich, D., Biryukov, A., Nikoli.c, I.: The hash function Cheetah: Specification and supporting documentation. Submission to NIST (2008) 54 Y. Sasaki et al.
  14. <Indesteege, S.: The LANE hash function. Submission to NIST (2008)
  15. Ewan Fleischmann, C.F., Gorski, M.: The Twister hash function family. Submission to NIST (2008)
  16. Rijmen, V., Barreto, P.S.L.M.: The Whirlpool hashing function. Submitted to NISSIE (2000)
  17. Peyrin, T.: Improved differential attacks for ECHO and Grostl. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 370–392. Springer, Heidelberg (2010)
  18. 18,0 18,1 18,2 18,3 Peyrin, T.: Improved differential attacks for ECHO and Grostl. Cryptology ePrint Archive, Report 2010/223 (2010) Extended version of the CRYPTO (2010) article
  19. 19,0 19,1 Schl.affer, M.: Subspace distinguisher for 5/8 rounds of the ECHO-256 hash function. In: Preproceedings of SAC 2010, pp. 379–398 (2010)
  20. Ideguchi, K., Tischhauser, E., Preneel, B.: Improved collision attacks on the reduced-round Grostl hash function. Cryptology ePrint Archive, Report 2010/375 (2010); Appeared in the accepted papers list of ISC (2010)
  21. 21,0 21,1 Mendel, F., Rechberger, C., Schl.affer, M., Thomsen, S.S.: Rebound attack on the reduced Grostl hash function. In: Pieprzyk, J. (ed.) Topics in Cryptology - CT-RSA 2010. LNCS, vol. 5985, pp. 350–365. Springer, Heidelberg (2010)