Введение
Семейство потоковых шифров
Шифры VEST (Very Efficient Substitution Transposition) – это набор семейств шифров общего назначения, разработанных для аппаратной реализации, поддерживающих однопроходное аутентифицированное шифрование и способных функционировать как хэш-функции, устойчивые к коллизиям. Авторами являются Шон О’Нил, Бенджамин Гиттинс и Говард Лэндман. VEST неэффективен при программной реализации. VEST основан на сбалансированной T-функции, которую также можно описать как биективный нелинейный регистр сдвига с обратной связью и параллельной обратной связью (NLPFSR) или как сеть подстановок и перестановок, дополненную нелинейным счетчиком на основе RNS. Четыре семейства шифров VEST, описанные в спецификации, – это VEST 4, VEST 8, VEST 16 и VEST 32. Шифры VEST поддерживают ключи и векторы инициализации (IV) переменного размера и мгновенную перегенерацию ключа. Все шифры VEST выдают выходные данные на каждом тактовом цикле. Все варианты VEST защищены европейским патентом № EP 1820295(B1), принадлежащим компании Synaptic Laboratories. VEST был кандидатом второго этапа конкурса eSTREAM в аппаратном портфеле, но не был кандидатом третьего этапа или Focus и, следовательно, не входит в окончательный портфель.
Общая структура
Шифры VEST состоят из четырех компонентов: нелинейного счетчика, линейного диффузора, биективного нелинейного аккумулятора с большим состоянием и линейного выходного комбинатора (как показано на изображении в правом верхнем углу этой страницы). Счетчик RNS состоит из шестнадцати NLFSR с простыми периодами, диффузор счетчика представляет собой набор линейных комбинаторов 5 к 1 с обратной связью, сжимающих выходы 16 счетчиков до 10 бит и одновременно расширяющих 8 входных данных до 9 бит, основной аккумулятор является NLPFSR, принимающим 10 бит от диффузора счетчика в качестве входных данных, а выходной комбинатор представляет собой набор линейных комбинаторов 6 к 1.
Аккумулятор
Основной аккумулятор в шифрах VEST можно рассматривать как SPN, построенный с использованием нелинейных функций обратной связи 6 к 1, по одной для каждого бита, все из которых обновляются одновременно. Основной аккумулятор VEST 4 представлен ниже: он принимает 10 бит (d0 – d9) в качестве входных данных. Наименее значимые пять битов (p0 – p4) в состоянии аккумулятора обновляются с помощью S-блока 5x5 и линейно комбинируются с первыми пятью входными битами на каждом раунде. Следующие пять битов аккумулятора линейно комбинируются со следующими пятью входными битами и с нелинейной функцией четырех из менее значимых битов аккумулятора. В режиме аутентифицированного шифрования биты обратной связи шифротекста также линейно подаются обратно в аккумулятор (e0 – e3) вместе с нелинейной функцией четырех менее значимых битов аккумулятора. Все остальные биты в состоянии аккумулятора VEST линейно комбинируются с нелинейными функциями пяти менее значимых битов состояния аккумулятора на каждом раунде. Использование только менее значимых битов в качестве входных данных для функций обратной связи каждого бита характерно для T-функций и обеспечивает биективность обратной связи. За этой операцией подстановки следует псевдослучайная перестановка всех битов состояния (см. рисунок ниже).
It accepts 10 bits (d0 − d9) as its input. The least significant five bits (p0 − p4) in the accumulator state are updated by a 5×5 substitution box and linearly combined with the first five input bits on each round. The next five accumulator bits are linearly combined with the next five input bits and with a non linear function of four of the less significant accumulator bits. In authenticated encryption mode, the ciphertext feedback bits are also linearly fed back into the accumulator (e0 − e3) with a non linear function of four of the less significant accumulator bits. All the other bits in the VEST accumulator state are linearly combined with non linear functions of five less significant bits of the accumulator state on each round. The use of only the less significant bits as inputs into the feedback functions for each bit is typical of T functions and is responsible for the feedback bijectivity. This substitution operation is followed by a pseudorandom transposition of all the bits in the state (see picture below).
Аутентификация данных
Шифры VEST могут быть выполнены в собственном режиме аутентифицированного шифрования, аналогичном режиму Phelix, но аутентифицируют шифротекст, а не открытый текст, с той же скоростью и занимая ту же площадь, что и генерация ключевого потока. Однако, аутентификация без ключа (хеширование) выполняется только по 8 бит за раз, загружая открытый текст в счетчики, а не напрямую в основной аккумулятор.
Семейный ключ
Четыре корневых семейства шифров VEST называются VEST 4, VEST 8, VEST 16 и VEST 32. Каждое из четырех генеалогических деревьев шифров VEST поддерживает семейное ключирование для генерации других независимых семей шифров того же размера. Процесс семейного ключирования является стандартным методом для генерации семейств шифров с уникальными подстановками и уникальными счетчиками с различными периодами. Семейное ключирование позволяет конечному пользователю генерировать уникальный защищенный шифр для каждого чипа.
Вычислительная эффективность в программном обеспечении
Основной аккумулятор в шифрах VEST имеет сложную, крайне нерегулярную структуру, затрудняющую его эффективную реализацию в программном обеспечении. Высоко нерегулярная структура входных данных в сочетании с уникальным набором входов для каждой функции обратной связи препятствует эффективному программному исполнению. В результате все функции обратной связи необходимо вычислять последовательно в программном обеспечении, что приводит к тому, что разница в скорости между аппаратной и программной реализацией примерно равна количеству логических элементов, занимаемых логикой обратной связи в аппаратной реализации (см. столбец "Различие" в таблице ниже). Реализация: Тактовая частота VEST 4 VEST 8 VEST 16 VEST 32 Аппаратное обеспечение 250 МГц ~1 Гбит/с ~2 Гбит/с ~4 Гбит/с ~8 Гбит/с Программное обеспечение 250 МГц < 1,0 Мбит/с < 0,8 Мбит/с < 1,1 Мбит/с < 1,3 Мбит/с Различие > 1000 x > 2300 x > 3500 x > 6000 x
Значительная разница между оптимизированной аппаратной реализацией VEST и эквивалентной по тактовой частоте оптимизированной программной реализацией обеспечивает естественную защиту от недорогих клонов универсальных программных процессоров, выдающих себя за настоящие аппаратные токены аутентификации. В сценариях массовой аутентификации по запросу-ответу, таких как приложения для аутентификации RFID, битовые реализации шифров VEST на 32-битных процессорах, обрабатывающих множество независимых сообщений одновременно, работают в 2–4 раза медленнее на байт сообщения, чем AES.
Производительность оборудования
VEST был представлен на конкурс eStream в категории II, разработанной для "аппаратных приложений с ограниченными ресурсами, такими как ограниченный объем памяти, количество логических элементов или энергопотребление", и демонстрирует высокую производительность на FPGA и ASIC, согласно оценке ETH Zurich. Авторы утверждают, что, согласно их собственным реализациям с использованием "консервативного стандартного процесса завершения проектирования RapidChip", "VEST 32 без труда обеспечивает 256-битное безопасное шифрование со скоростью 10 Гбит/с при частоте 167 МГц на ASIC-технологиях платформы RapidChip LSI Logic 180 нм, занимая менее 45 000 логических элементов и не требуя использования SRAM". На технологиях Rapidchip 110 нм VEST 32 обеспечивает аутентифицированное шифрование со скоростью 20 Гбит/с при частоте 320 МГц, занимая менее 45 000 логических элементов. Они также заявляют, что развертывание раундовой функции VEST может уменьшить тактовую частоту вдвое и снизить энергопотребление, одновременно удваивая объем выходных данных за такт, но при этом увеличится занимаемая площадь.
История
VEST был разработан Шоном О’Нилом и представлен на конкурс eStream в июне 2005 года. Это было первое представление данного шифра публике.
Безопасность
Авторы утверждают, что запасы прочности VEST соответствуют рекомендациям, предложенным Ларсом Кнудсеном в статье "Некоторые соображения о процессе AES", и более строгим рекомендациям, недавно предложенным Николасом Куртуа в статье "Криптоанализ Sfinks". Несмотря на то, что авторы не публикуют результаты собственного криптоанализа, шифры VEST выдержали более года публичной проверки в рамках конкурса eStream, организованного ECRYPT. Они прошли во второй этап, хотя и не были включены в фокус-группу.
Атаки
На SASC 2007 Жоу и Рейнхард опубликовали атаку, в результате которой было восстановлено 53 бита состояния счетчика. Бернштейн, сравнив сложность этой атаки с параллельным полным перебором, оценил итоговую криптостойкость шифра в 100 бит, что несколько ниже заявленной криптостойкости большинства представителей семейства VEST. Разработчики VEST заявили, что атака стала возможной из-за опечатки в исходной спецификации шифра и опубликовали исправление в архиве Cryptology ePrint 21 января 2007 года, за несколько дней до публикации результатов атаки.