Увеличение размеров блока и ключа
Существует ли хороший способ построения большого блочного шифра как комбинации из малых шифров, так, чтобы размер блока и размер ключа большого шифра были в N раз больше, чем у составных шифров; с соответствующим увеличением стойкости. То есть каскадирование в длину и в ширину для произвольно задаваемого N.
Например, можно рекурсивно построить сеть Файстеля с увеличением размера блока на каждом этапе; это потребует порядка N вычислений функции шифра на весь большой блок.
Еще часто упоминают такой способ: слой из N малых шифров шириной в большой блок, потом какая-то перестановка (циклический сдвиг, транспонирование всего массива байтов или битов...), потом опять слой шифров и.т.д. всего N^2 операций.
Можно сделать N проходов по кругу в CBC режиме; менее чем N^2 операций. Тут возникает интересный вопрос с key schedule.
Можно каждый малый блок N раз зашифровать на N ключах, и между шифрованиями складывать со всеми другими блоками. Тоже N^2 действий.
Способов множество. Очевидно что над вопросом думали. Что посоветуете; что почитать?
http://www.zas-comm.ru
Hint: wide block encryption modes.
Обзор на слайдах[link1].
Особо элегантная и простая конструкция: WCFB[link2]. Но, как и для многих других режимов, с доказательствами стойкости пока всё очень сложно и мутно.
Ещё этот вопрос изучается в рамках non-malleable symmetric encryption, где используется смесь режима шифрования с режимами кодирования или экстракторами случайности.
Самым перспективным решением может оказаться отказ от всех этих режимов и создание шифра, который позволяет работать с переменным размером блока и ключа «из коробки» — на уровне раундовой функции. Но пока это совсем плохо проработано теоретически, а предполагаемые конструкции — непрактичны и затратны.
Да, такое решение может быть наиболее вычислительно эффективным. Интересно, какие конструкции предлагались.
http://www.zas-comm.ru
Скорее всего, я изначально неправильно понял ваш вопрос, поэтому почти весь мой ответ малополезен. Вы хотели увеличить не только размер блока, но и ключа, завели речь о «каскадировании вглубь и вширь». Т.е., хотели повысить стойкость существующего алгоритма, а не просто добиться non-malleability.
Но мэйстримная криптография не занимается повышением стойкости уже существующего примитива. Если у нас есть вычислительно стойкий {128…256}-битный шифр, то и в Wide Block режиме его стойкость останется {128…256}-битной. По крайней мере, стараются гарантировать, чтобы она была не меньше исходной, а случаи потенциального увеличения стойкости обычно не рассматривают. Т.е. или у нас есть исходный вычислительно стойкий шифр, или его нет. Всё остальное — перестраховочная криптография, которая плохо сочетается с доказуемой. Одна из парадигм современной доказуемой безопасности, особенно применимая в симметрике: из исходно стойких малых элементов создают более сложные криптосистемы и доказывают, что затраты на их взлом не меньше затрат на взлом исходных более примитивных элементов.
См. например flat sponge claim в алгоритме Keccak[link3].
Вот сделать шифр, где внутреннее состояние по размеру блока можно менять на уровне раундовой функции и задавать таким же образом переменный размер ключа — возможно, но всерьёз таких попыток не было. Как бы за ненадобностью. Один из вариантов был похож на тот, который вы привели — масштабируемые сети Файстеля. Но к ним ещё что-то хитрое было прикручено, не помню. Это было в какой-то диссертации, от малоизвестного автора. И квадратичный рост затрат ресурсов тоже где-то фигурировал. Но это исследования, если и не близкие к маргинальным, то далеко не мейнстримные.
Получается, мораль в том, что собирая конструктор из деталей, потенциально можно только понизить стойкость, а не повысить. ☺
Да, поэтому стараются делать конструкции оптимально простыми — чем больше деталей, тем меньше надёжность в общем случае.
Вот она: Provable Secure Scalable Block Ciphers[link4]. Отсюда новый хинт: Scalable block ciphers.
Но опять же, это в первую очередь попытка закатать масштабируемость блока в криптопримитив, чтобы избежать использования сложных режимов. В большинстве случаев при этом не ставится цели усиления стойкости по сравнению с короткоблочным вариантом. Т.е. вполне возможен выход на плоский режим стойкости с некоторого порога по размеру блока: блок, пожалуйста, хоть многомегабайтный, а стойкость как у обычного в 128…256 бит.
Для повышения стойкости, мы можем каскадировать Wide Block уровни нужное число раз. В качестве key schedule берется псевдослучайная функция от начального длинного ключа. Например, та же или какая другая Wide Block функция. Проблемы с обоснованием минимально нужного количества раз. Оценка снизу N*log N, оценка сверху N^2.
http://www.zas-comm.ru