что означает многократное шифрование применительно к блочным шифрам

RC6. От простого к сложному

В этой статье вы узнаете

Кто этот ваш блочный шифр.

Каких принципов придерживались создатели алгоритма.

Как выглядит процесс подготовки ключа.

И причем тут вообще RC5?

Введение в RC6.

Для начала разберемся с терминологией:

Что значит симметричный?

Есть два типа людей шифров:

Симметричные (то, что нам нужно)

Ассиметричные (как-нибудь в другой раз, бро)

В симметричном шифровании, для того чтобы зашифровать и расшифровать данные используется один и тот же ключ. Он должен хранится в секрете. Т.е. ни отправитель, ни получатель не должны никому его показывать. Иначе, ваши данные могут перехватить/изменить или еще чего похуже.

Алгоритмы симметричного шифрования:

AES (Advanced Encryption Standard)

3DES (Triple Data Encryption Algorithm )

RC4, RC5, RC6 (Rivest cipher)

В ассиметричном шифровании используется два ключа: открытый и закрытый. Из названий ясно, что открытый ключ может свободно передаваться по каналам связи, а вот закрытый ключ нужно хранить в тайне.

Алгоритмы ассиметричного шифрования:

DSA (Digital Signature Algorithm), DSS (Digital Signature Standard)

Что значит блочный?

Блочное шифрование это один из видов симметричного шифрования. Называется он так, потому что работает с блоками: группами бит, фиксированной длины.

Чтобы стало яснее, рассмотрим один из методов построения блочных шифров: сеть Фестеля.

Какая, какая сеть?

Фестеля. Это конструкция из ячеек. На вход каждой ячейки поступают данные и ключ. А на выходе каждой из них изменённые данные и изменённый ключ.

Чтобы зашифровать информацию ее разбивают на блоки фиксированной длины. Как правило, длина входного блока является степенью двойки.

Каждый из блоков делится на два подблока одинакового размера — левый и правый.

Правый подблок скармливается функции .

После чего умножается по модулю 2 (операция xor) с левым блоком .

Полученный результат в следующем раунде будет играть роль правого подблока.

А правый подблок (без изменений) выступит в роли левого подблока.

Раундом в батле криптографии называют один из последовательных шагов(циклов) обработки данных в алгоритме блочного шифрования. ключ на — ом раунде (рассмотрим позже).

Далее операции повторяются столько раз, сколько задано раундов.

Замечание. Расшифровка информации происходит так же, как и шифрование, с тем лишь исключением, что ключи следуют в обратном порядке.

Выглядит это примерно так:

Параметры алгоритма

Теперь, когда мы разобрались с основными понятиями, попробуем копнуть немного глубже.

RC6 параметризированный алгоритм. Это значит, что его работа зависит от некоторых начальных параметров, которые устанавливаются перед началом его работы. Попробуем понять на примере параметра :

Все основные вычисления, которыми оперирует алгоритм, имеют битные машинные слова в качестве входа и выхода. Как мы уже выяснили, RC6 блочный шифр. Причем входной и выходной блоки имеют 4 регистра A, B, C, D каждый размером по бит. Обычно . Тогда размер блока будет бит.

Таким образом является одним из параметров алгоритма, который мы можем задавать. Выпишем их все:

размер слова в битах. Каждое слово содержит слов в байтах. Блоки открытого текста и шифротекста имеют длину по бит (т.к. 4 регистра).

количество раундов. Так же размер расширенного массива ключейбудет иметьслово (об этом далее). Допустимые значения .

секретный ключ размеров байт: .

Чтобы было ясно, о каком алгоритме идем речь принято писать .

Схема подготовки ключа

Алгоритм подготовки ключа состоит из трех простых этапов и использует две магические константы:

Генерация констант

Для конкретного мы определяем две величины:

где (экспонента), (золотое сечение). операция округления до ближайшего нечетного целого.

Например, если взять , то значения получатся такие:

Теперь рассмотрим основные этапы. Их три:

1 этап. Конвертация секретного ключа

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

2 этап. Инициализация массива ключей

Массив ключей так же называют расширенной таблицей ключей. Она заполняется с помощью тех самых магических констант, которые мы определили ранее:

3 этап. Перемешивание

Этот шаг состоит в том, чтобы перемешать секретный ключ, который нам дал пользователь:

На этом схема подготовки ключа закончена и хочется поскорее узнать, как работает сам алгоритм RC6. Но мы не будем спешить и для того, чтобы было проще понять принцип его работы, рассмотрим предыдущию версию RC5. А также рассмотрим шаги развития этого алгоритма, которые привели Рональда Ривеста к конечному варианту шифра RC6:

Немного про RC5

RC5 блочный шифр, разработанный Рональдом Ривестом в 1994 году. Одно из отличий от RC6 это то, что он имеет два регистра на входе и на выходе вместо четырех. Второе отсутствие операции умножения в процессе вычислений.

Рональд Ривест писал, что при создании этого шифра он придерживался нескольких правил:

RC5 должен быть блочным шифром. Т.е. открытый и зашифрованный текст представляют собой битовые последовательности (блоки) и секретный ключ должен использоваться как в процессе шифрования, так и в процессе расшифровки.

RC5 должен использовать только примитивные операции, реализованные на большинстве процессоров.

RC5 должен быть адаптирован к процессорам с разной длиной машинного слова. Например, когда станут доступны 64-битные процессоры, RC5 сможет на них работать.

RC5 должен быть быстрым. Т.е. основными вычислительными операциями должны быть операторы, которые одновременно работают с целыми словами.

RC5 должен иметь переменное количество раундов. Чтобы пользователь мог выбирать между более высокой скоростью вычислений и более высокой безопасностью.

RC5 должен иметь ключ переменной длины. Чтобы пользователь мог выбрать подходящий для него уровень безопасности.

RC5 должен быть простым в реализации и иметь невысокие требования к памяти.

Последнее, но немаловажное RC5 должен обеспечивать высокую безопасность при выборе подходящих значений параметров.

Процесс подготовки ключа у RC5 точно такой же, как и у RC6. А вот сам алгоритм шифрования и расшифровки проще. Cхема шифрования RC5:

А псевдокод буквально состоит из пяти строчек:

Здесь стоит отметить, что за один раунд в RC5 одновременно обновляются обе переменные.

Путь от RC5 к RC6

Возьмем от RC5 все самое лучшее:

Рассмотрим основные шаги, которые привели Рональда Ривеста к конечному варианту RC6.

Начнем с базового полу-раундового(переменные обновляются поочередно) алгоритма RC5:

Запустим параллельно две копии RC5. Первую на регистрах A и B, а другую на C и D:

Вместо того, чтобы менять местами A на B и C на D, поменяем регистры (A, B, C, D) = (B, C, D, A). В этом случае вычисления на блоке AB перемешиваются с вычислениями на блоке CD:

Далее еще раз смешаем AB и CD переставив циклические сдвиги:

Вместо того, чтобы использовать в качестве сдвигов B и D, как указано выше, будем использовать измененные версии этих регистров. Проще говоря, мы хотим сделать так, чтобы величина циклического сдвига зависела от битов входного слова.

Частный случай такого преобразования функция , за которой следует сдвиг влево на пять битовых позиций:

И на десерт сделаем так, чтобы операции, используемые на начальном шаге первого раунда и заключительном шаге последнего раунда отличались от преобразований всех остальных раундов(такая операция, называются pre- и post-whitening):

Теперь после того, как мы тут все замиксовали, посмотрим еще раз на то, что имеем:

Шифрование

Еще раз напомним, что RC6 работает с четырьмя битными регистрами A, B, C, D. Они содержат исходный входной открытый текст, а также выходной шифротекст. Причем первый байт открытого текста или шифротекста помещается в младший байт A, а последний байт в самый старший байт D. Ниже приведен псевдокод:

Схема одного раунда в алгоритме RC6 выглядит так:

Дешифрование

Для полноты картины еще немного псевдокода по дешифровке:

Что по атакам?

Для варианта алгоритма RC6-128/20/b никаких атак не выявлено. Атаки слева были обнаружены только для варианта алгоритма с числом раундов

Полагается, что лучший вариант атаки на RС6 полный перебор байтового ключа шифрования. Для него потребуется операций. Однако, было замечено, что за счет значительной памяти и предварительного вычисления можно организовать атаку встреча посередине, которая потребует операций. Что тоже очень много.

Для таких типов атак, как дифференциальный и линейный криптоанализ, приведем следующую таблицу:

Здесь приведены наиболее выгодные цифры для данных атак. Цифры в прямоугольнике обозначают, что требования к данным для успешной атаки превышают от общего числа возможных открытых текстов.

Таким образом, приходим к выводу, что RC6 с 20 раундами защищен от дифференциальных и линейных криптоаналитических атак.

Выводы

Так же существуют улучшения алгоритма RC6, такие как RC6_en, но о нем как-нибудь в другой раз.

Источник

Блочный шифр

Из Википедии — свободной энциклопедии

В отличие от шифроблокнота, где длина ключа равна длине сообщения, блочный шифр способен зашифровать одним ключом одно или несколько сообщений суммарной длиной больше, чем длина ключа. Передача малого по сравнению с сообщением ключа по зашифрованному каналу — задача значительно более простая и быстрая, чем передача самого сообщения или ключа такой же длины, что делает возможным его повседневное использование. Однако, при этом шифр перестаёт быть невзламываемым. От поточных шифров работа блочного отличается обработкой бит группами, а не потоком. При этом блочные шифры медленнее поточных. [3] Симметричные системы обладают преимуществом над асимметричными в скорости шифрования, что позволяет им оставаться актуальными, несмотря на более слабый механизм передачи ключа (получатель должен знать секретный ключ, который необходимо передать по уже налаженному зашифрованному каналу. В то же время, в асимметричных шифрах открытый ключ, необходимый для шифрования, могут знать все, и нет необходимости в передаче ключа шифрования).

К достоинствам блочных шифров относят сходство процедур шифрования и расшифрования, которые, как правило, отличаются лишь порядком действий. Это упрощает создание устройств шифрования, так как позволяет использовать одни и те же блоки в цепях шифрования и расшифрования. Гибкость блочных шифров позволяет использовать их для построения других криптографических примитивов: генератора псевдослучайной последовательности, поточного шифра, имитовставки и криптографических хешей. [4]

Источник

PRESENT — ультралегкое блочное шифрование (перевод оригинальной статьи PRESENT: An Ultra-Lightweight Block Cipher)

Привет, Хабр! Привожу тут перевод оригинальной статьи «PRESENT: An Ultra-Lightweight Block Cipher» за авторством Robert B. Weide Богданова, Лендера, Паара, Пошмана, Робшава, Сеурина и Виккелсоя.

Аннотация

1. Введение

Основной курс в IT текущего столетия — развитие малых вычислительных устройств, причем применяемых не только потребительских товарах, но и формирующих неотъемлемую — и незаметную — часть окружения — инфраструктуру связи. Уже выявлено, что подобные внедрения создают целый спектр весьма конкретных угроз безопасности. В то же время, подручные криптографические решения, даже довольно примитивные, зачастую не подходят для использования в сильно ограниченных по ресурсам окружениях.

Пожалуй, здесь стоит пояснить, почему мы вообще решили разрабатывать новый блочный шифр, ведь общепризнанный факт заключается в том, что поточные шифры, потенциально, более компактны. Действительно, в начале мы приложили усилия по пониманию устройства компактных поточных шифров в процессе работы над проектом eSTREAM, а так же нескольких других многообещающих предположений, кажущихся быстродейственными. Но мы заметили несколько причин, по которым выбрали все-таки блочный шифр. Во-первых, блочное шифрование универсально и примитивно, а при использовании его в режиме шифрования, т.е. используя уже зашифрованные блоки для шифровки следующих, мы получаем потоковое шифрование. Во-вторых, и, пожалуй, в-главных, тонкости принципов работы блочных шифров кажутся лучше исследованными, нежели чем принципы работы поточных шифрующих алгоритмов. К примеру, в то время как есть обширная теория на базе использования регистров сдвига с линейной обратной связью, не так просто объединить эти блоки так, чтобы получить безопасное предложение. Мы предполагаем, что аккуратно спроектированный блочный шифр может быть более безопасен, нежели чем свежесозданный поточный шифр. Таким образом, получаем, что блочный шифр, требующий столько же ресурсов железа, сколько и компактный поточный шифр, может быть весьма интересен.

Важно отметить, что создавая новый блочный шифрующий алгоритм, особенно с выделяющейся производительностью, мы не просто гонимся за инновациями. Напротив, разработка и реализация шифра идут рука об руку, выявляя некоторые фундаментальные пределы и присущие ограничения. Например, заданный уровень безопасности накладывает ограничения на минимальную длину ключа и блока. Даже обработка 64-битного состояния 80-битным ключом ограничивает минимальный размер устройства. Также можно заметить, что воплощение в «железо» — в особенности же компактность аппаратной реализации — способствует повторяемости. Даже малые изменения могут негативно сказаться на объеме устройства. Однако, криптоаналитики так же ценят повторяемость и ищут математические структуры, которые легко размножаются во многих раундах. Так как много простых повторяющихся структур можно использовать, не подрывая безопасность системы?

Итак, в данной статье будет описан компактный блочный шифр PRESENT. После короткого ревью существующей литературы, всю остальную статью мы оформили в стандартном виде. Шифр описан в секции 3, в секции 4 описаны проектные решения. В 5 секции мы рассмотрим безопасность, тогда как секция 6 будет содержать в себе детальный анализ производительности. Завершается же данный труд нашими выводами.

2. Существующие труды

В то время, как объем работ, посвященных дешевой криптографии непрерывно растет, количество статей посвященных сверх-легким шифрам на удивление мало. Переводя фокус на устройство протокола, мы перестанем ссылаться на работы по дешевым протоколам связи и идентификации. Одна из наиболее обширных работ по компактной реализации в настоящий момент связана с проектом eSTREAM. В рамках одной из частей этого проекта были предложены новые поточные шифры, приспособленные к эффективному воплощению в «железе». По ходу данной работы намечаются многообещающие кандидаты. Пока соотношения примерны, но из брошюр по внедрению следует, что для компактных шифров проекта eSTREAM потребуется порядка 1300-2600 GE (Gate equivalents).

Среди блочных шифров, один из широко известных, а именно DES был создан с учетом эффективности по оборудованию. Помятуя о весьма ограниченном состоянии полупроводников в начале 1970-х, не удивительно, что DES обладает весьма конкурентноспособными свойствами в реализации. Во время разработки, на DES исполнение было затрачено 3000GE, а после сериализации это число опустилось до 2300GE. Однако длина ключа DES ограничивает его полезность во многих приложениях и приводит к тому, что на его основе разрабатываются специализированные модификации, например, с повышенной криптостойкостью или удлиненным ключом.

Касательно современных блочных шифров, в этой статье приводится тщательный анализ дешевого в исполнении AES. Однако, на его реализацию требуется порядка 3600 GE, что является непрямым следствием проектировки штфра под 8- и 32-битные процессоры. Системные требования TEA не известны, однако по прикидкам требуют около 2100 GE. Есть и еще 4 решения, заточенных под дешевое оборудование: mCRYPTON (имеет точное исполнение в 2949 GE), HIGHT (около 3000 GE), SEA (порядка 2280 GE) и CGEN (так же около 2280 GE), несмотря на то, что последний и не был задуман как блочный шифр.

3. Блочный шифр PRESENT

PRESENT — частный случай SP-сети и состоит из 31 раунда. Длина блока составляет 64 бита, а ключи поддерживаются в 2 вариантах, 80- и 128-битные. Такого уровня защиты должно вполне хватать для низкозащищенных приложений, обычно используемых для развертывания на основе тегов, а кроме того, что важнее, PRESENT во многом совпадает своими конструтивными особенностями с поточными шифрами проекта eSTREAM, заточенными на эффективную реализацию в железе, что позволяет нам адекватно сравнивать их.
Требования по безопасности и эксплуатационные свойства 128-битных версий предоставлены в приложении к оригинальной статье.

Каждый из 31 раундов состоит из операции XOR, чтобы ввести ключ K_i для 1 ≤ i ≤ 32, где K₃₂ используется для «отбеливания» ключа, линейной побитовой перестановки и нелинейного слоя замещения (или, попросту говоря, увеличения стойкости шифрования). Нелинейный слой использует раздельные 4-битные S-блоки, которые применяются параллельно 16 раз на каждом раунде. Шифр, описанный псевдо-кодом представлен на рисунке:

Теперь каждая стадия определяется по очереди. Обоснования конструкции приведены в 4 разделе, а биты всюду нумеруются с нуля, начиная с правого в блоке или слове.

Добавление раундового ключа (addRoundKey). Задан раундовый ключ K_i = k i ₆₃… k i ₀, где 1 ≤ i ≤ 32, а так же текущее состояние b₆₃… b₀. Добавление раундового ключа к текущему состоянию происходит по модулю 2 (b_j = b_j ⊕ k i _j, где 0 ≤ j ≤ 63).

Слой S-блоков (sBoxlayer). Используемые в PRESENT S-блоки отображают 4-битные блоки в 4-битные блоки. Действие этого блока в шестнадцатеричной системе счисления приведено в следующей таблице:

Для слоя S-блоков текущее состояние b₆₃… b₀ представляет из себя 16 4-битных слов w₁₅… w₀, где w_i = b_4*i+3 || b_4*i+2 || b_4*i+1 || b_4*i для 0 ≤ i ≤ 15. Выход рамки S[w_i] выдает обновленные значения состояний очевидным образом.

Слой перестановки (pLayer). Побитовая перестановка, используемая в PRESENT задается следующей таблицей (бит i состояния смещается на позицию P(i)):

Преобразование ключа (The key schedule). PRESENT может использовать 80- и 128-битные ключи, однако сосредоточимся на 80-битной версии. Предоставляемый пользователем ключ хранится в регистре ключей K, представленный в виде k₇₉k₇₈… k₀. На i-ом раунде 64-битный раундовый ключ K_i = k₆₃k₆₂… k₀, состоящий из 64 левых битов текущего содержимого регистра K. Таким образом, на i-ом раунде имеем:
K_i = k₆₃k₆₂… k₀ = k₇₉k₇₈… k₁₆.

Следовательно, регистр ключа сдвигается на 61 позицию влево, 4 крайних левых бита, прошедших через S-блок и round_counter значение i складывается по модулю 2 с битами k₁₉k₁₈k₁₇k₁₆k₁₅ из K с наименьшим значащим битом из round_counter справа.

Преобразование ключа для 128-битного алгоритма можно найти в приложении к оригинальной статье.

4. Конструктивные особенности PRESENT

Помимо безопасности и эффективной реализации, основное достижение PRESENT — его простота. по этому не удивительно, что похожие проекты были приняты в других обстоятельствах, и даже были использованы как учебное пособие для студентов. В данной секции мы обоснуем решения, принятые нами при проектировке PRESENT. Однако, в первую очередь, опишем ожидаемые прикладные требования.

4.1. Цели и среда применения

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

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

4.2. Перестановочный слой

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

4.3. S-блоки.

В PRESENT мы используем раздельные S-блоки, переводящие 4 бита в 4 бита (F 4 ₂→F 4 ₂). Это прямое следствие нашего стремления к аппаратной эффективности, при этом реализация такого S-блока обычно намного компактнее, чем у 8-битного S-блока. Поскольку мы используем битовую перестановку для линейного диффузионного слоя, AES-подобные диффузионные технологии не являются вариантом для нашего шифра. Поэтому мы помещаем некоторые дополнительные условия на S-блоки, чтобы уменьшить так называемый «лавинный эффект». Точнее, S-блоки для PRESENT удовлетворяют следующим условиям, где мы обозначим коэффициент Фурье S через

1. Для любого фиксированного ненулевого входного смещения ∆_I ∈ F 4 ₂ и любого фиксированного ненулевого входного смещения ∆_O ∈ F 4 ₂ внутри S-блока требуем
#2|S(x) + S(x+∆_I) = ∆_O> ≤ 4.

2. Для любой фиксированной ненулевой входной разнице ∆_I ∈ F 4 ₂ и любой фиксированной ненулевой выходной разнице ∆_O ∈ F 4 ₂, такой что wt(∆_I) = wt(∆_O) = 1, имеем
2|S(x) + S(x+∆_I) = ∆_O> = ∅

3. Для всех ненулевых a ∈ F 4 ₂ и всех ненулевых b ∈ F₄ выполняется что |S W _b(a)| ≤ 8
4. Для всех ненулевых a ∈ F 4 ₂ и всех ненулевых b ∈ F₄, таких что wt(a) = wt(b) = 1 выполняется S W _b(a) = ± 4

Как станет ясно из секции 5, эти условия гарантируют, что PRESENT устойчив к дифференциальным и линейным атакам. Используя классификацию всех 4-битных S-блоков, удовлетворяющих вышеприведенным условиям, мы выбрали S-блок, который особенно хорошо подходит для эффективной аппаратной реализации.

5. Анализ безопасности

А теперь мы представим результаты анализа безопасности PRESENT.

Дифференциальный и линейный криптоанализ

Дифференциальный и линейный криптоанализ являются одними из самых мощных методов, доступных криптоаналитику. Чтобы измерить сопротивление PRESENT дифференциальному и линейному криптоанализу, мы задаем нижнюю границу числа так называемых активных S-блоков, участвующих в дифференциальной (или линейной) характеристике.

Дифференциальный криптоанализ

Случай дифференциального криптоанализа охвачен следующей теоремой.

Теорема 1. Любая пятиконтурная дифференциальная характеристика PRESENT имеет минимум 10 активных S-блоков.

Теорема 1 доказывается в 3 приложении оригинальной статьи, а мы продолжим наблюдения. Разделим 16 S-блоков в 4 группы:

_{Числа на входе (сверху) обозначают номер S-блока на предыдущем шаге, а на выходе (снизу) — на последующем}

Практическое подтверждение

Мы можем определить характеристики, которые включают в себя десять S-блоков в течение пяти раундов. Следующая двухраундовая итерационная характеристика включает в себя два S-блока за раунд и держится с вероятностью 2 −25 за пять раундов.

Линейный криптоанализ

Случай линейного криптоанализа PRESENT рассматривается следующей теоремой, в которой мы анализируем наилучшее линейное приближение к четырем раундам PRESENT.

Поэтому в предположении, что криптоаналитику нужно только приблизительно 28 из 31 раунда в PRESENT, чтобы инициировать атаку восстановления ключа, линейный криптоанализ шифра потребует порядка 2 84 известных открытых текстов / шифротекстов. Такие требования к данным превышают доступный текст.

Некоторые продвинутые дифференциальные / линейные атаки

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

Усеченное расширение выполняется с вероятностью один.

Даже при использовании для уменьшения длины уже идентифицированных дифференциальных характеристик требования к данным остаются чрезмерными. Ранкированное расширение выполняется с вероятностью один.

5.2. Структурные атаки

Структурные атаки, такие как интегральный криптоанализ и анализ бутылочного горлышка, хорошо подходят для анализа AES-подобных шифров. Такие шифры имеют сильные словоподобные структуры, где слова обычно являются байтами.Однако конструкция представления почти исключительно побитовая, и хотя операция перестановки несколько регулярна, развитие и распространение словесных структур нарушаются побитовыми операциями, используемыми в шифре.

5.3. Алгебраические атаки

Алгебраические атаки имели больший успех, когда применялись к потоковым шифрам, чем к блочным. Тем не менее, простая структура PRESENT означает, что они заслуживают серьезного изучения. S-блок PRESENT описывается 21 квадратичным уравнением для восьми входных / выходных битовых переменных над полем G(2). Это неудивительно, поскольку хорошо известно, что любой четырехбитный S-блок может быть описан по крайней мере 21 таким уравнением. Затем весь шифр может быть описан квадратными уравнениями e=n×21 в переменных v=n×8, где n-число S-блоков в алгоритме шифрования и преобразования ключей.

Для PRESENT мы имеем n = (31×16) + 31 таким образом, вся система состоит из 11 067 квадратных уравнений в 4 216 переменных.Общая задача решения системы многомерных квадратных уравнений является NP-трудной. Однако системы, полученные для блочных шифров, очень редки, так как они состоят из n небольших систем, Соединенных простыми линейными слоями. Тем не менее, неясно, можно ли использовать этот факт в так называемой алгебраической атаке. Были предложены некоторые специализированные методы, такие как XL и XSL, хотя были обнаружены недостатки в обоих методах. Вместо этого единственные практические результаты по алгебраическому криптоанализу блочных шифров были получены путем применения алгоритмов Бухбергера и F4 в рамках Magma. Моделирование на маломасштабных версиях AES показало, что для всех, кроме самых маленьких SP-сетей, быстро возникают трудности как во времени, так и в сложности памяти. То же самое относится и к PRESENT.

Практическое подтверждение. Мы провели моделирование на мелкомасштабных версиях, используя алгоритм F4 в Magma. Когда есть один S-блок, то есть очень маленький блок размером в четыре бита, то Magma может решить полученную систему уравнений за много раундов. Однако при увеличении размера блока и добавлении S-блоков, наряду с соответствующим вариантом линейного диффузионного слоя, система уравнений вскоре становится слишком большой. Даже при рассмотрении системы, состоящей из семи S-блоков, т. е. имея размер блока 28 бит, мы не смогли в разумные сроки получить решение для прошедшего два раунда варианта сокращенного шифра. Наш анализ показывает, что алгебраические атаки вряд ли представляют угрозу для PRESENT.

5.4. Атаки с преобразованием ключа

Поскольку не существует никаких установленных руководящих принципов для разработки преобразований ключа, существует как большое разнообразие проектов, так и большое разнообразие атак, исходя из особенностей проекта. Наиболее эффективные атаки подпадают под общую рубрику атака на связанных ключах и сдвиговая атака, и обе основаны на построении идентифицируемых соотношений между различными наборами суб-ключей. Чтобы противостоять этой угрозе, мы используем раунд-зависимый счетчик, так что наборы суб-ключей не могут быть легко «сдвинуты», и мы используем нелинейную операцию для смешивания содержимого ключевого регистра K. В частности:

6. Производительность «железа»

Мы реализовали PRESENT-80 в VHDL и адаптировали его для стандартной библиотеки ячеек Virtual Silicon (VST) на основе UMC L180 0.18 μ 1P6M Logic. Мы использовали Mentor Graphics Modelsim SE PLUS 5.8 c для моделирования и Synopsys Design Compilerversion Y-2006.06 для синтеза и моделирования мощности потребления. Были использованы типичные для литейного производства значения (1,8 Вольта для напряжения сердечника и 25°C для температуры), а для моделирования мощности применена предложенная модель проволочной нагрузки. Обратите внимание, что подобное моделирование преназначено для конструкций около 10 000 GE, поэтому результаты мощности будут пессимистичными для значительно меньших конструкций. На рисунке

показан путь данных оптимизированного по пространству PRESENT-80 без возможности дешифровки (encryption-only), который выполняет один раунд за один такт, т. е. путь данных 64-разрядной ширины. Обратите внимание, что на этапе проектирования PRESENT мы используем один и тот же S-блок 16 раз вместо того, чтобы иметь 16 различных S-блоков, и это облегчает дальнейшую сериализацию проекта, т. е. с 4-битным каналом передачи данных. Наша реализация требует 32 тактовых цикла для шифрования 64-битного открытого текста с 80-битным ключом, занимает 1570 GE и имеет в модуляции энергопотребление 5 мкВт.

Пространственные требования PRESENT

Большую часть площади занимают триггеры для хранения ключа и состояния данных, за которыми следуют S-слой и отдел XOR’ирования ключа. Битовые перестановки простой проводки увеличат площадь только тогда, когда реализация дойдет до этапа place&route. Заметим, что основной целью нашей реализации был небольшой объем аппаратного обеспечения, однако мы также синтезировали оптимизированный по мощности процесс. Для дополнительных 53 GE мы достигаем энергопотребления всего 3,3 мкВт, а нынешний-128 будет занимать оценочную площадь 1886 GE. Помимо очень малого размера PRESENT имеет довольно высокую пропускную способность, дающую хорошую энергию на бит. Сравнение с другими шифрами приведено в таблице:

7. Заключение

В этой статье мы описали новый блочный шифр PRESENT. Нашей целью был сверхлегкий шифр, который обеспечивает уровень безопасности, соизмеримый с размером 64-битного блока и 80-битным ключом. В итоге, PRESENT имеет требования к реализации, аналогичные многим компактным потоковым шифрам. Поэтому мы считаем, что он представляет как теоретический, так и практический интерес. Как и все новые предложения, мы не поощряем немедленное развертывание PRESENT, но настоятельно призываем к его анализу.

Источник