Аутентификация сообщений

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

а1, а2, …аn – о.т., b1,b2, …bn – ш.т.

1. Сообщение передается в открытом виде (a1,a2…..an, U). U = bn – вектор аутентификации. Приемник зашифровывает (a1,a2…..an) и проверяет последний зашифрованный бит с U. Вероятность принять искажение за истину = ½ в степени n. Рекомендуется n =24.

2. Сообщение передается в шифрованном виде. U – первые m бит последнего зашифрованного блока. Угадать U практически невозможно. Передается (b1,b2…..bn, U). После получения сравниваем.

Вопрос 34.1. Итерационные системы блочного шифрования. Особенности строения и ключевой системы шифров IDEA. Режимы шифрования. Аутентификация сообщений с использованием блочного шифра

На примере DES можно показать еще несколько принципов проектирования блочного шифра. Первым является идея итеративного блочного шифра. При этом предполагается, что простая функция этапа будет последовательно использована несколько раз. Двухэтапный DES не очень силен, чтобы все биты результата зависели от всех битов ключа и всех битов исходных данных, нужно 5 этапов. 16-этапный DES - это сильный алгоритм, 32-этапный DES еще сильнее.

Сети Фейстеля

Большинство блочных алгоритмов являются сетями Фейстеля. Возьмите блок длиной n и разделите его на две половины длиной n/2: L и R. Конечно, n должно быть четным. Можно определить итеративный блочный шифр, в котором результат j-го этапа определяется результатом предыдущего этапа:

L_i = R_i-1, R_i = L_i-1 Å f(R_i-1, K_i), где K_i - это подключ, используемый на j-ом этапе, а f - это произвольная функция этапа.

Эту концепцию можно увидеть в DES, Lucifer, FEAL, Khufu, Khafre, LOKI, COST, CAST, Blowfish и других алгоритмах. Почему это так важно? Гарантируется, что эта функция является обращаемой. Так как для объединения левой половины с результатом функции этапа используется XOR, следующее выражение обязательно является истинным: L_i-1 Å f(R_i-1, K_i) Å f(R_i-1, K_i)= L_i-1

Гарантируется, что шифр, использующий такую конструкцию, обратим, если можно восстановить исходные данные f на каждом этапе. Сама функция f неважна, он не обязана быть обратимой. Мы можем спроектировать f настолько сложной, насколько захотим, и нам не потребуется реализовывать два различных алгоритма - один для шифрования, а другой для дешифрирования. Структура сети Фейстела автоматически позаботится об этом

IDEA

Шифр IDEA (International Data Encryption Algorithm, международный алгоритм шифрования данных), предложенный Ксуеджа Лай (Xuejia Lai) и Джеймсом Масси (James Massey), появился в 1992 году. Это один из самых лучших и самых безопасных блочных алгоритмов, опубликованных на сегодня.

Обзор IDEA

IDEA является блочным шифром, он работает с 64-битовыми блоками открытого текста. Длина ключа - 128 битов. Для шифрования и расшифрирования используется один и тот же алгоритм.

Как и другие блочные шифры IDEA использует и запутывание, и рассеяние. Философия, лежащая в основе проекта, представляет собой "объединение операций из различных алгебраических групп". Смешиваются три алгебраические группы, и все они могут быть легко реализованы как аппаратно, так и программно:

· XOR (поразрядное двоичное суммирование)

· Сложение по модулю 2¹⁶

· Умножение по модулю 2¹⁶ + 1. (Это операцию можно рассматривать как S-блок IDEA.)

Все эти операции (а в алгоритме используются только они, перестановки на битовом уровне не применяются) работают с 16-битовыми подблоками. Этот алгоритм даже эффективнее на 16-битовых процессорах.

Описание IDEA

Схема IDEA представлена на Рис.1. 64-битовый блок данных делится на четыре 16-битовых подблока: X₁, X₂, X₃ и X₄. Эти четыре подблока становятся входными данными для первого этапа алгоритма. Всего в алгоритме восемь этапов. На каждом этапе четыре подблока подвергаются операциям XOR, сложениям и умножениям друг с другом и с шестью 16-битовыми подключами. Между этапами обмениваются местами второй и третий подблоки. Наконец четыре подблока объединяются с четырьмя подключами в окончательном преобразовании. На каждом этапе события происходят в следующей последовательности:

1. Перемножаются X₁ и первый подключ.

2. Складываются X₂ и второй подключ.

3. Складываются X₃ и третий подключ.

4. Перемножаются X₄ и четвертый подключ.

5. Выполняется XOR над результатами этапов (1) и (3).

6. Выполняется XOR над результатами этапов (2) и (4).

7. Перемножаются результаты этапа (5) и пятый подключ.

8. Складываются результаты этапов (6) и (7).

9. Перемножаются результаты этапа (8) и шестой подключ.

10. Складываются результаты этапов (7) и (9).

11. Выполняется XOR над результатами этапов (1) и (9).

12. Выполняется XOR над результатами этапов (3) и (9).

13. Выполняется XOR над результатами этапов (1) и (10).

14. Выполняется XOR над результатами этапов (4) и (10).

Выходом этапа являются четыре подблока - результаты действий (11), (12), (13) и (14). Поменяйте местами два внутренних подблока (но не в последнем этапе), и вы получите исходные данные для следующего этапа.

После восьмого этапа выполняется заключительное преобразование:

1. Перемножаются X_l и первый подключ.

2. Складываются X₂ и второй подключ.

3. Складываются X₃ и третий подключ.

4. Перемножаются X₄ и четвертый подключ.

Наконец четыре подблока снова соединяются, образуя шифротекст.

Также несложно создавать подключи. Алгоритм использует 52 из них (шесть для каждого из восьми этапов и еще четыре для заключительного преобразования). Сначала 128-битовый ключ делится на восемь 16-битовых подключей. Это первые восемь подключей алгоритма (шесть для первого этапа и два - для второго). Затем ключ циклически сдвигается налево на 25 битов и снова делится на восемь подключей. Первые четыре используются на этапе 2, а оставшиеся четыре - на этапе 3. Ключ циклически сдвигается налево на 25 битов для получения следующих восьми подключей, и так до конца алгоритма.

Дешифрирование выполняется точно также за исключением того, что подключи инвертируются и слегка изменяются. Подключи при дешифрировании представляют собой обратные значения ключей шифрования по отношению к операциям либо сложения, либо умножения. (Для IDEA подблоки, состоящие из одних нулей, считаются равными 2¹⁶ = -1 для умножения по модулю 2¹⁶ + 1, следовательно, обратным значением 0 относительно умножения является 0.) Эти вычисления могут занять некоторое время, но их нужно выполнить один раз для каждого ключа дешифрирования.

Скорость IDEA

Современные программные реализации IDEA примерно в два – четыре раза быстрее, чем DES. На компьютере с i386/33 МГц IDEA шифрует данные со скоростью 880 Кбит/с, а на компьютере с i486/33 МГц - со скоростью 2400 Кбит/с. Аппаратная реализация шифрует данные с помощью алгоритма IDEA со скоростью 177 Мбит/с при тактовой частоте 25 МГц.

Криптоанализ IDEA

Длина ключа IDEA равна 128 битам - более чем в два раза длиннее ключа DES. При условии, что наиболее эффективным является вскрытие грубой силой, для вскрытия ключа потребуется 2¹²⁸ (10³⁸) шифрований.

Может быть вскрытие грубой силой - не лучший способ вскрытия IDEA. Алгоритм все еще слишком нов, чтобы можно было говорить о каких-то конкретных криптографических результатах. Разработчики сделали все возможное, чтобы сделать алгоритм устойчивым к дифференциальному криптоанализу.

Джоан Дэймен (Joan Daemen) открыла класс слабых ключей IDEA. Эти ключи не являются слабыми в том смысле, в котором слабы некоторые ключи DES, для которых функция шифрования обратна самой себе. Слабость этих ключей состоит в том, что взломщик может легко определить их с помощью вскрытия с выбранным открытым текстом. Например, слабым является следующий ключ (в шестнадцатиричной записи):

0000,0000,0x00,0000,0000,000x,xxxx,x000

В позиции "x" может стоять любая цифра. При использовании такого ключа побитовое XOR определенных пар открытых текстов равно побитовому XOR получившихся пар шифротекстов.

В любом случае вероятность случайной генерации одного из таких слабых ключей очень мала: 1/2⁹⁶. Опасность случайно выбрать такой ключ практически не существует. К тому же, несложно модифицировать IDEA так, чтобы исключить наличие слабых ключей - достаточно выполнить XOR каждого подключа с числом 0x0dae.