обеспечивают безопасность блочного шифра. В общем случае чем S-блоки больше, тем лучше.

В DES восемь различных 6*4-битовых S-блоков. В Khufu и Khafre единственный 8*32-битовый S-блок, в LOKI 12*8-битовый S-блок, а в Blowfish и CAST 8*32-битовые S-блоки. В IDEA S-блоком по сути является умножение по модулю, это 16*16-битовый S-блок. Чем больше S-блок, тем труднее обнаружить статистические отклонения, нужные для вскрытия с использованием либо дифференциального, либо линейного криптоанализа [653, 729, 1626]. Кроме того, хотя случайные S-блоки обычно не оптимальны с точки зрения устойчивости к дифференциальному и линейному криптоанализу, сильные S-блоки легче найти среди S-блоков большего ра з-мера. Большинство случайных S-блоков нелинейны, невырождены и обладают сильной устойчивостью к лине й-ному криптоанализу - и с уменьшением числа входных битов эта доля снижается медленно [1185, 1186, 1187].

Размер m важнее размера n. Увеличение размера n снижает эффективность дифференциального криптоан а-лиза, но значительно повышает эффективность дифференциального криптоанализа. Действительно, если n>2m-m, то наверняка существует линейная зависимость для входных и выходных битов S-блока. И если n>2m, то линейная зависимость существует только для выходных битов [164].

Заметной частью работы по проектированию S-блоков является изучение логических функций [94, 1098, 1262, 1408]. Для обеспечения безопасности булевы функции, используемые в S-блоках, должны отвечать опр е-деленным условиям. Они не должны быть ни линейными, ни аффинными, ни даже быть близкими к линейным или аффинным [9, 1177, 1178, 1188]. Количество нулей и единиц должно быть сбалансированным, и не должно быть никаких корреляций между различными комбинациями битов. При изменении на противоположный л ю-бого входного бита выходные биты должны вести себя независимо. Эти критерии проектирования также связ а-ны с изучением функций изгиба: функций, которые, как может быть показано, являются оптимально нелине й-ными. Хотя они определены просто и естественно, их изучение очень нелегко [1344, 1216, 947, 905, 1176, 1271, 295, 296, 297, 149, 349, 471, 298].

Очень важным свойством представляется лавинный эффект: сколько выходных битов S-блока изменяется при изменении некоторого подмножества выходных битов. Нетрудно задать для булевых функций условия, в ы-полнение которых обеспечивает определенный лавинный эффект, но проектирование таких функций является более сложной задачей. Строгий лавинный критерий (strict avalanche criteria, SAC) обеспечивает, что с изм е-нением одного входного бита изменяется ровно половина выходных битов [1586]. См. также [982, 571, 1262, 399]. В одной из работ эти критерии рассматриваются в терминах утечки информации [1640].

Несколько лет назад криптографы предложили выбирать S-блоки так, чтобы таблица распределения разл и-чий для каждого S-блока была однородной. Это обеспечило бы устойчивость к дифференциальному криптоан а-лизу за счет сглаживания дифференциалов на любом отдельном этапе [6, 443, 444, 1177]. Примером такого проектирования является LOKI. Однако такой подход иногда способствует дифференциальному криптоанализу [172]. Действительно, лучшим подходом является минимизирование максимального дифференциала. Кванджо Ким (Kwangjo Kim) выдвинул пять критериев проектирования S-блоков [834], похожих на критерии проектир о-вания S-блоков DES.

Выбор хороших S-блоков - не простая задача, существует множество различных идей, как лучше сделать это. Можно выделить четыре главных подхода.

1. Случайно выбрать. Ясно, что небольшие случайные S-блоки небезопасны, но большие случайные S-блоки могут оказаться достаточно хороши. Случайные S-блоки с восемью и более входами достаточно сильны [1186, 1187]. Еще лучше 12-битовые S-блоки. Устойчивость S-блоков возрастает, если они одновременно являются и случайными, и зависящими от ключа. В IDEA используются большие зависящие от ключа S-блоки.

2. Выбрать и проверить. В некоторых шифрах свойства S-блоков, генерированных случайным образом, проверяются. Примеры такого подхода содержатся в [9, 729].

3. Разработать вручную. При этом математический аппарат используется крайне незначительно: S-блоки создаются с использованием интуитивных приемов. Барт Пренел (Bart Preneel) заявил, что "... теор е-тически интересные критерии недостаточны [для выбора булевых функций S-блоков] и что "... н е-обходимы специальные критерии проектирования" [1262].

4. Разработать математически. S-блоки создаются в соответствии с математическими законами, поэтому они обладают гарантированной надежностью по отношению к дифференциальному и линейному криптоанализу, а также хорошими диффузными свойствами. Прекрасный пример такого подхода можно найти в [1179].

Существует ряд призывов объединить "математический" и "ручной" подходы [1334], но реально, по вид и-мому, конкурируют случайно выбранные S-блоки и S-блоки с определенными свойствами. Конечно преимущ е-ством последнего подхода является оптимизация против известных методов вскрытия - дифференциального и линейного криптоанализа - но обеспечиваемая этим подходом степень защиты от неизвестных методов вскр ы-

тия также неизвестна. Разработчикам DES было известно о дифференциальном криптоанализе, и его S-блоки были оптимизированы соответствующим образом. Скорее всего, о линейном криптоанализе они не знали, и S-блоки DES очень слабы по отношению к такому способу вскрытия [1018]. Случайно выбранные S-блоки в DES были бы слабее против дифференциального криптоанализа, но сильнее против линейного криптоанализа.

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

Проектирование блочного шифра

Проектировать блочный шифр нетрудно. Если вы рассматривает 64-битовый блочный шифр как перестано в-ку 64-битовых чисел, ясно, что почти все эти перестановки безопасны. Трудность состоит в проектировании блочного шифра, который не только безопасен, но также может быть легко описан и просто реализован.

Легко можно спроектировать блочный шифр, если вы используете память, достаточную для размещения S-блоков 48*32. Трудно спроектировать небезопасный вариант DES, если вы собираетесь использовать в нем 128 этапов. При длине ключа 512 битов не стоит беспокоиться о том, нет ли какой-либо зависящей от ключа ко м-плиментарности.

14.11 Использование однонаправленных хэш-функций

Сымым простым способом использовать для шифрования однонаправленную хэш-функцию является хэш и-рование предыдущего блока шифротекста, объединенного с ключом, а затем выполнение XOR результата с т е-кущим блоком открытого текста:

с,- = Pi e H(K, Cl) Pi = Ci e H(K, Pi-i)

Установите длину блока равной длине результата однонаправленной хэш-функции. По сути это приводит к использованию однонаправленной хэш-функции как блочного шифра в режиме CFB. При помощи аналогичной конструкции можно использовать однонаправленную хэш-функцию и в режиме OFB:

Ci = Pi e S,-; Si = H(K, Ci-i)

Pi = Ci e Si = H(K, Ci-i)

Надежность такой схемы определяется безопасностью однонаправленной хэш-функции. Karn

Этот метод, изобретенный Филом Карном (Phil Karn) и открытый им для свободного использования, создает обратимый алгоритм шифрования из определенных однонаправленных хэш-функций.

Алгоритм работает с 32-байтовыми блоками открытого текста и шифротекста. Длина ключа может быть произвольной, хотя определенные дины ключей более эффективны для конкретных однонаправленных хэш-функций. Для однонаправленных хэш-функций MD4 и MD5 лучше всего подходят 96-байтовые ключи.

Для шифрования сначала разбейте открытый текст на две 16-байтовых половины: P/ и Pr. Затем разбейте на две 48-байтовых половины ключ: К/ и Kr.

P= P/ , Pr,

К = К/ , Kr

Добавьте K/ к P/ и выполните хэширование однонаправленной хэш-функцией, затем выполните XOR резул ь-тата с Pr, получая Cr, правую половину шифротекста. Затем, добавьте Kr к Cr выполните хэширование однонаправленной хэш-функцией. Выполните XOR результата с P/ , получая С/. Наконец, объедините Cr и С/ , получая шифротекст.

Cr = Pr e H(P/, К/)

С/=P/ e H(Cr, Kr)

С = С/, Cr

Для дешифрирования просто инвертируйте процесс. Добавьте Kr к Cr, выполните хэширование и XOR р е-зультата с С/ , получая P/. Добавьте K/ к P/, выполните хэширование и XOR результата с Cr , получая Pr.

Pl = с © H(Cr, Kr) Pr = Cr © H(Pi, Kl)

P = Pl, Pr

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

Luby-Rackoff

Майкл Любы (Michael Luby) и Чарльз Ракофф (Charles Rackoff) показали, что Karn не является безопасным [992]. Рассмотрим два одноблочных сообщения: AB и AC. Если криптоаналитику известны открытый текст и шифротекст первого сообщения, а также первая половина открытого текста второго сообщения, то он может легко вычислить все второе сообщение. Хотя такое вскрытие с известным открытым текстом работает только при определенных условиях, оно представляет собой главную проблему в безопасности алгоритма.

Ее удается избежать при помощи трехэтапного алгоритма шифрования [992,1643,1644]. Он использует три различных хэш-функции: H1, H2 и H3. Дальнейшие исследования показали, что H1 может совпадать с H2, или H2 может совпадать с H3, но не одновременно [1193]. Кроме того, H1, H2 и H3 не могут быть основаны на итерациях одной и той же базовой функции [1643]. В любом случае при условии, что H(k,x) ведет себя как псевдослучайная функция, трехэтапная версия выглядит следующим образом:

(1) Разделите ключ на две половины: Kl и Kr.

(2) Разделите блок открытого текста на две половины: Lq и Rq.

(3) Объедините Kl и Lo и выполните хэширование. Выполните XOR результата хэширования с R0, получая R1: R1= Ro © H(Ki, Lo)

(4) Объедините Kr и R1 и выполните хэширование. Выполните XOR результата хэширования с L0, получая L1 L1 = Lo © H(Kr, R1)

(5) Объедините Kl и L1 и выполните хэширование. Выполните XOR результата хэширования с R1, получая R2:

(6) Объедините L1 и R2, получая сообщение.

Шифр краткого содержания сообщения

Шифр краткого содержания сообщения(Message Digest Cipher, M DC), изобретенный Питером Гутманном (Peter Cutmann) [676], представляет собой способ превратить однонаправленные хэш-функции в блочный шифр, работающий в режиме CFB. Шифр работает почти также быстро, как и хэш-функция, и по крайней мере н а-столько же безопасен. Оставшаяся часть этого раздела предполаг ает знакомство с главой 18.

Хэш функции, например MD5 и SHA, используют 512-битовый текстовый блок для преобразования входн ого значения (128 битов в MD5, и 160 битов в SHA) в результат того же размера. Это преобразование необрат и-мо, но прекрасно подходит для режима CFB: и для шифрования, и для дешифрирования используется одна и та же операция.

Рассмотрим MDC с SHA. MDC использует 160-битовый блок и 512-битовый ключ. Используется побочный эффект хэш-функции, когда в качестве прежнего хэш-значения берется входной блок открытого текста (160 б и-тов), а 512-битовый вход хэш-функции играет роль ключа (см. Рис 14.5). Обычно при использовании хэш-функции для хэширования некоторого входа 512-битовый вход меняется при хэшировании каждого нового 512-битового блока. Но в данном случае 512-битовый вход становится неизменяемым ключом.

MDC можно использовать с любой однонаправленной хэш-функцией: MD4, MD5, Snefru, и т.д. Он незап а-тентован и может быть совершенно бесплатно использован кем угодно когда угодно и для чего угодно [676 ].

Однако лично я не верю в эту схему. Можно подобрать такой способ взлома, на противостояние которому хэш-функция не была рассчитана. Хэш-функции не обязаны противостоять вскрытию с выбранным открытым текстом, когда криптоаналитик выбирает некоторые начальные 160-битовые значения, получает их "зашифрованными" одним и тем же 512-битовым "ключом" и пользуется этим для получения некоторой и н-формации об используемом 512-битовом ключе. Так как разработчики хэш-функций не должны беспокоиться о такой возможности, считать ваш шифр безопасным по отношению к приведенному способу вскрытия - не лу ч-