Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
насколько длинна самая короткая такая комбинация? Целью исследования является оценка пространства ключей для теоретического вскрытия грубой силой, а р е- зультат представляет собой наибольшую нижнюю границу энтропии пространства ключей. Слабые ключи В хорошем блочном шифре все ключи одинаково сильны. Обычно нет проблем и при алгоритме с малым количеством слабых ключей, таком как DES. Вероятность случайно выбрать один из них очень мала, такой ключ легко проверить и при необходимости отбросить. Однако, иногда эти слабые ключи могут быть задейс т- вованы, если блочный фильтр используется как однонаправленная хэш-функция (см. раздел 18.11). Устойчивость к дифференциальному и линейному криптоанализу Исследование дифференциального и линейного криптоанализа значительно прояснило теорию проектиров а- ния хорошего блочного шифра. Авторы IDEA ввели понятие дифференциалов, обобщение основной идеи ха- рактеристик [931]. Они утверждали, что можно создавать блочные шифры, устойчивые к вскрытиям такого т и- па. Результатом подобного проектирования и является IDEA [931]. Позднее это понятие было формализовано в [1181, 1182], когда Кайса Ниберг (Kaisa Nyberg) и Ларс Кнудсен (Lars Knudsen) показали, как создавать бло ч- ные шифры доказуемо безопасные по отношению к дифференциальному криптоанализу. Эта теория была ра с- ширена на дифференциалы высших порядков [702, 161, 927, 858, 860] и частичные дифференциалы [860]. К а- жется, что дифференциалы высших порядков применимы только к шифрам с малым числом этапов, но части ч- ные дифференциалы прекрасно объединяются с дифференциалами. Линейный криптоанализ новее, и он все еще совершенствуется. Были определены понятия классификации ключей [1019] и нескольких приближений [811, 812]. Еще одно расширение криптоанализа можно найти в [1270]. В [938] была предпринята попытка объединить дифференциальный и линейный криптоанализ в одном вскрытии. Пока неясно, какая методика проектирования сможет противостоять подобным вскрытиям. Кнудсен добился некоторого успеха, рассматривая некоторые необходимые (но, возможно, не достаточные) критерии того, что он назвал практически безопасными сетями Фейстела - шифров, устойчивых как к диф- ференциальному, так и к линейному криптоанализу [857]. Ниберг ввел для линейного криптоанализа аналог понятия дифференциалов в дифференциальном криптоанализе [1180]. Достаточно интересной кажется двойственность дифференциального и линейного криптоанализа. Эта дво й- ственность становится очевидной как при разработке методики создания хороших дифференциальных характ е- ристик и линейных приближений [164, 1018], так и при разработке критерия проектирования, обеспечивающего устойчивость алгоритмов к обоим типам вскрытия [307]. Пока точно неизвестно, куда заведет это направление исследований. Для начала Дэймен разработал стратегию проектирования алгоритма, основанную на диффере н- циальном и линейном криптоанализе [402]. Проектирование S-блоков Сила большинства сетей Фейстела - и особенно их устойчивость к дифференциальному и линейному кри п- тоанализу - непосредственно связана с их S-блоками. Это явилось причиной потока исследований, что же обр а- зует хороший S-блок. S-блок - это просто подстановка: отображение m-битовых входов на n-битовые выходы. Ранее я упоминал об одной большой таблице отображения 64-битовых входов на 64-битовые выходы, такая таблица представляла бы собой S-блок размером 64*64 бита. S-блок с m-битовым входом и n-битовым выходом называется m*n- битовым S-блоком. S-блоки обычно являются единственным нелинейным действием в алгоритме, именно они обеспечивают безопасность блочного шифра. В общем случае чем 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?2 m -m, то наверняка существует линейная зависимость для входных и выходных битов S-блока. И если n?2 m , то линейная зависимость существует только для выходных битов [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 результата с т е- кущим блоком открытого текста: C i = P i ? H(K, C i-1 ) P i = C i ? H(K, P i-1 ) Установите длину блока равной длине результата однонаправленной хэш-функции. По сути это приводит к использованию однонаправленной хэш-функции как блочного шифра в режиме CFB. При помощи аналогичной конструкции можно использовать однонаправленную хэш-функцию и в режиме OFB: C i = P i ? S i ; S i = H(K, C i-1 ) P i = C i ? S i = H(K, C i-1 ) Надежность такой схемы определяется безопасностью однонаправленной хэш-функции. Karn Этот метод, изобретенный Филом Карном (Phil Karn) и открытый им для свободного использования, создает обратимый алгоритм шифрования из определенных однонаправленных хэш-функций. Алгоритм работает с 32-байтовыми блоками открытого текста и шифротекста. Длина ключа может быть произвольной, хотя определенные дины ключей более эффективны для конкретных однонаправленных хэш- функций. Для однонаправленных хэш-функций MD4 и MD5 лучше всего подходят 96-байтовые ключи. Для шифрования сначала разбейте открытый текст на две 16-байтовых половины: P l и P r . Затем разбейте на две 48-байтовых половины ключ: K l и K r P= P l , P r , K = K l , K r Добавьте K l к P l и выполните хэширование однонаправленной хэш-функцией, затем выполните XOR резул ь- тата с P r , получая C r , правую половину шифротекста. Затем, добавьте K r к C r выполните хэширование однона- правленной хэш-функцией. Выполните XOR результата с P l , получая C l . Наконец, объедините C r и C l , получая шифротекст. C r = P r ? H(P l , K l ) C l = P l ? H(C r , K r ) C = C l , C r Для дешифрирования просто инвертируйте процесс. Добавьте K r к Cr, выполните хэширование и XOR ре- зультата с C l , получая P l . Добавьте K l к P l , выполните хэширование и XOR результата с C r , получая P r P l = C l ? H(C r , K r ) P r = C r ? H(P l , K l ) P = P l , P r Общая структура Karn совпадает с структурой множества других блочных алгоритмов, рассмотренных в этом разделе. У алгоритма только два этапа, так как его сложность определяется однонаправленной хэш- функцией. А, так как ключ используется только как вход хэш-функции, он не может быть раскрыт даже при помощи вскрытия с выбранным открытым текстом, если, конечно, безопасна используемая однонаправленная хэш-функция. Luby-Rackoff Майкл Любы (Michael Luby) и Чарльз Ракофф (Charles Rackoff) показали, что Karn не является безопасным [992]. Рассмотрим два одноблочных сообщения: AB и AC. Если криптоаналитику известны открытый текст и шифротекст первого сообщения, а также первая половина открытого текста второго сообщения, то он может легко вычислить все второе сообщение. Хотя такое вскрытие с известным открытым текстом работает только при определенных условиях, оно представляет собой главную проблему в безопасности алгоритма. Ее удается избежать при помощи трехэтапного алгоритма шифрования [992,1643,1644]. Он использует три различных хэш-функции: H 1 , H 2 и H 3 . Дальнейшие исследования показали, что H 1 может совпадать с H 2 , или H 2 может совпадать с H 3 , но не одновременно [1193]. Кроме того, H 1 , H 2 и H 3 не могут быть основаны на итераци- ях одной и той же базовой функции [1643]. В любом случае при условии, что H(k,x) ведет себя как псевдослу- чайная функция, трехэтапная версия выглядит следующим образом: (1) Разделите ключ на две половины: K l и K r (2) Разделите блок открытого текста на две половины: L 0 и R 0 (3) Объедините K l и L 0 и выполните хэширование. Выполните XOR результата хэширования с R 0 , получая R 1 : R 1 = R 0 ? H(K l , L 0 ) (4) Объедините K r и R 1 и выполните хэширование. Выполните XOR результата хэширования с L 0 , получая L 1 L 1 = L 0 ? H(K r , R 1 ) (5) Объедините K l и L 1 и выполните хэширование. Выполните XOR результата хэширования с R 1 , получая R 2 : R 2 = R 1 ? H(K l , L 1 ) (6) Объедините L 1 и R 2 , получая сообщение. Шифр краткого содержания сообщения Шифр краткого содержания сообщения(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-битовом ключе. Так как разработчики хэш-функций не должны беспокоиться о такой возможности, считать ваш шифр безопасным по отношению к приведенному способу вскрытия - не лу ч- шая идея. Безопасность шифров, основанных на однонаправленных хэш-функциях Хотя эти конструкции и могут быть безопасными, они зависят от используемой однонаправленной хэш- функции. Хорошая однонаправленная хэш-функция не обязательно дает безопасный алгоритм шифрования. Существуют различные криптографические требования. Например, линейный криптоанализ бесполезен против однонаправленных хэш-функциях, но действенен против алгоритмов шифрования. Однонаправленная хэш- функция, такая как SHA, может обладать определенными линейными характеристиками, которые, не влияя на ее безопасность как однонаправленной хэш-функции, могут сделать небезопасным ее использование в таком алгоритме шифрования, как MDC. Мне неизвестно ни о каких результатах криптоанализа использования ко н- кретной однонаправленной хэш-функции в качестве блочного шифра. Прежде чем использовать их дождитесь проведения подобного анализа. Открытый текст Выходное значение (a) Хэш-функция (b) Хэш-функция как блочный шифр в режиме CFB Шифротекст Выходное значение Блок сообщения Хэш- функция Ключ Хэш- функция Рис. 14-5. Шифр краткого содержания сообщения (MDC). 14.12 Выбор блочного алгоритма Это очень трудное решение. DES почти наверняка небезопасен при использовании против правительств в е- ликих держав, если только вы не шифруете одним ключом очень малые порции данных. Возможно этот алг о- ритм пока неплох против кого-нибудь другого, но вскоре и это изменится. Машины для вскрытия ключа DES |