Современная прикладная криптография (стр. 8 )

Следует отметить тот факт, что алгоритм расшифрования работает медленнее чем алгоритм зашифрования. Это связано с тем, что в нем для получения расширенного ключа на каждом шаге необходимо дополнительно применять к ключевому потоку достаточно медленную операцию MixColumn.

Новые режимы использования блочных шифров

Если проследить историю развития режимов шифрования, становится очевидной ее связь с развитием IT индустрии, в особенности с развитием аппаратной базы. Долгое время во всем мире возможность распараллелить вычисления бола малодоступна. В основном использовались режим шифрования CBC и режим аутентификации сообщений – CBC-MAC. Новые режимы, такие как IAPM или IACBC были лишь разработками. Совсем недавно технологии достигли того уровня, что для обеспечения потребностей пользователя уже не достаточно увеличивать скорость аппаратного обеспечения традиционным способом. В качестве нового направления некоторые производители выбрали распараллеливание задач (процессоры с технологией HyperThreading), а другие стали более бурно развивать 64-битные платформы (Athlon64, Opteron). В настоящее время уже существует режимы, ориентированные как на распараллеливание операций, так и режимы, которые быстро оперируют большими числами(PMAC/add).

Опишем основные свойства этих новых режимов и укажем на цели, которые преследовали их авторы и проблемы, которые данные режимы пытаются решить.

Прежде всего, необходимо дать определение, что такое режим работы блочного шифра и какие в связи с этим понятия или термины нам придётся ввести. Под режимом работы блочного шифра понимается алгоритм применения блочного шифра, используемый в целях защиты информации (В том числе подсчет MAC, MDC, …). Как видно из определения сам блочный шифр теперь является лишь частью другого алгоритма – алгоритма режима работы блочного шифра. Это обусловлено тем, что блочный шифр оперирует только с отдельным блоком данных, в то время как алгоритм режима работы блочного шифра имеет дело уже с целым сообщением, которое может состоять из некоторого числа n блоков. Более того, сообщение вообще не всегда можно разбить на целое число n блоков. В этом случае в разных режимах шифрования приходиться дополнять сообщение различным количеством бит. Такое дополнение почти неизбежно, но минимальная величина, к которой нужно "подтянуть" длину сообщения различна для разных режимов шифрования и напрямую зависит от длины порции сообщения, с которой работает каждая итерация алгоритма данного режима.

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

Кроме проблемы обеспечения конфиденциальности информации, в данное время обеспечение ее целостности также является важной задачей. Существует два основных способа обеспечения целостности информации – вычисление MAC(message authentication code) и MDC (manipulation detection code). Эти режимы используются совместно с режимами шифрования.

Для повышения производительности в последнее время были созданы режимы, обеспечивающие как конфиденциальность, так и целостность информации (Authenticated Encryption Modes). В этих режимах работы блочных шифров часто используется режим CTR (Counter).

Режимы шифрования

При создании системы защиты конфиденциальной информации любой заказчик интересуется: “Какой алгоритм шифрования использует Ваша система?” Вопрос, безусловно, важный, однако значительный вклад в качество и производительность системы шифрования вносят режимы, в которых используются алгоритмы шифрования. С семидесятых годов чаще всего использовались режимы схожие с режимами стандарта Data Encryption Standard – ECB, CBC, OFB, CFB. Каждый из этих режимов обладает своими достоинствами и недостатками: ECB – идеален для распараллеливания вычислений. С помощью него можно легко добиться больших скоростей шифрования, CBC более стойкий ко многим известным типам атак, OFB и CFB дают возможность работать с потоками информации, а не с блоками. Время выдвигает новые требования, и новые режимы шифрования пытаются их решить.

Режимы аутентификации

Режим Parallelizable Message Authentication Code (PMAC)

Параллелезируемый MAC - это новый код аутентификации сообщения. В отличие от других режимов аутентификации сообщения конструкция этого полностью параллелизируема. В современных условиях это свойство имеет огромное значение. В новой версии платформы Microsoft. NET 2.0 планируется реализовать этот режим, поэтому разберем его наиболее подробно.

В конструкции PMAC мало используются вызовы блочного шифрования, применяя только блочный шифр [|M|/n] раз, М – непустая строка, n – размерность блока блочного шифра.

В отличие от обычного CBC MAC, PMAC может быть применен к любому сообщению М; в частности, n необязательно делит |M|. Аналогично, сообщение с примененным MAC не обязательно должно иметь фиксированную длину; сообщения различных длин могут быть безопасно защищены от изменения этим алгоритмом.

Когда используется PMAC с AES, ключом для PMAC является простой AES ключ, и все обращения к AES происходят под этим ключом.

Конструкция PMAC подобна коду XOR MAC Bellare, Guerin, и Rogaway и подобному варианту у Bernstein. Хотя это даже больше подобно XECB MAC Gligor and Donescu. Последняя работа послужила вдохновением для этой. Но PMAC более эффективен, чем любой альтернативный ему.

Можно рассмотреть PMAC как еще одну оптимизированную версию MAC конструкции, попадающей под парадигму Carter-Wegman. Другие версии MAC, попадающие под эту парадигму, - параллелизуемы, если только они используют семейство параллелизируемых универсальных хэш-функций. Но определение и осуществление (некриптографической) универсальной хэш-функции создают более сложный механизм, чем тот, что дается здесь.

Обозначения:

Для работы алгоритма используется блочный шифр Е n-битным входным блоком (X) и к-битный ключ К. Блок шифр-текста - Y=Ek(X). Для E=AES мы получаем n=128 и kÎ{128,192,256}.

Аутентификационные тэги, которые мы определяем, могут иметь любой номер битов, tagLen, от 1 и до n. Заданное по умолчанию значение tagLen=64, вероятно, должно быть хорошим.

Под 0i и 1i мы понимаем строки, соответственно, из i нулей и i единиц. Для строки А длиной меньше, чем n, под padn(A) мы понимаем строку 0n-|A|-11 A: то есть, рассматриваем нулевые биты, а затем 1 бит равный 1.

Если А и В – строки, тогда АВ обозначает их конкатенацию.

Если А и В – строки равной длины. Под А[bit i] мы понимаем i-й бит А, где знаки пронумерованы с лева на право, начиная с 1. Под А[bits l to r] понимаем А[bit l]A[bit l+1]…..A[bit r]

Описание алгоритма PMAC.

Сложение, умножение и Final(.)

Мы задаем операцию сложения “+” отображающую {0,1}nx{0,1}n в {0,1}n, операцию умножения из {1,2,3,…….}x{0,1}n в {0,1}n. Мы также задаем отображение Final:{0,1}n ® {0,1}n.

PMAC/add

Для сложения по модулю 2n версии PMAC, PMAC/add, покажем операцию “+” на примере “компьютерного” сложения n-битных слов (игнорируя любой перенос ), и назовем iL, для i ³ 1, повторным сложение. Пусть Final(L) - будет `L, поразрядное дополнение к L.

(Более формальное определение: Пусть А, В Î {0,1}n. Под str2num(A) понимаем неотрицательное целое число, которое будет представлено А, то есть, åni=1 2n-iA[bit i]. Если а – целое число, то num2strn(a) – уникальная n-битная строка А, так что num2strn(A)=amod2n. Под А+В мы определяем num2strn(num2strn(А)+ num2strn(В)). Под iA, где i ³ 0 положительное целое число, мы понимаем строку num2strn(i. num2strn(А)). Символ “.” в последнем выражении значит умножение целых чисел.

Данный k-битный ключ К происходит от ключа L путем L=EK(0n)V0n-11. Это гарантирует, что L – нечетная.

Вычисление PMAC.

Теперь определим PMAC. Когда выполнены сложение и умножение, мы определяем PMAC/add. Данная строка М вычисляется, как показано ниже.

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

Алгоритм использует основной k-битный ключ K, но этот ключ отображается в (K,L), где L – n-битный ключ. В типичной реализации, L должен быть вычислен один раз и сохранен.

Последовательное сложение L может быть использовано вместо этого, как:

Offset = L

for i = 1to m-1 do

C[i] =EK(M[i] + Offset)

Offset = Offset + L

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

Чтобы пояснить, что происходит в параллельной реализации, положим, что компьютер имеет два процессора, Р1 и Р2, и каждый должен вычислять MAC M=M[1]…..M[m]. Процессор Р1 начинает с Offset = 0n, а процессор Р2 с Offset = L. Процессор Р1 будет ответственен за нечетно индексированные слова, в то время как Р2 обрабатывает четно-индексированные слова. Каждый увеличивает собственный Offset двумя L, но не одним L. Процессор Р1 будет кодировать M[1];M[3];M[5]….. и XOR шифр-текст. Процессор Р2 будет кодировать M[2] ÅM[4] Å M[6] Å….и XOR шифр-текст. Данные XOR шифр-тексты, заключительный MAC могут быть вычислены одним из процессоров.

Заметим, что ни создание MAC, ни его проверка не требуют использование функции Е-1. Таким образом, Е-1 не нужно реализовывать.

Заметим также, что если сообщение должно быть изменено путем замещения некоторых блоков, время пересчета исправленного MAC пропорционально r, предполагая, что каждый имеет сохраняемый старый (n-битный) MAC.

Начиная с n=128, n-битное сложения уже не тривиальная операция, особенно в высокоуровневых языках программирования (Это утверждение верно для современных 32-битных компьютеров, но в данное время появились машины класса Athlon64 – с 64 битной архитектурой и этот режим можно использовать для больших n).