Безопасность MMB

Схема MMB обеспечивает на каждом этапе значительное и независимое от ключа рассеяние. В IDEA рассеяние до определенной степени зависит от конкретных подключей. В отличие от IDEA у MMB нет слабых ключей.

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

Во вторых, Эли Бихам реализовал эффективное вскрытие с выбранным ключом [160], использующеее тот факт, что все этапы идентичны, а ключ при использовании просто циклически сдвигается на 32 бита. В третьих, несмотря на то, что программные реализации MMB были бы очень эффективны, в аппаратном исполнении алгоритм менее эффективен, чем DES.

Дэймон предлагает, что тот, кто захочет улучшить MMB, должен сначала проанализировать умножение по модулю с помощью линейного криптоанализа и подобрать новый множитель, а затем сделать константу C различной для каждого этапа [402]. Затем, улучшив использование ключа, добавляя к ключам этапов константы с целью устранения смещения. Но сам не стал заниматься этим и разработал 3-Way (см. раздел 14.5).

CA-1.1

CA - это блочный шифр, основанный на клеточных автоматах и разработанный Говардом Гутовицом (Howard Gutowitz) [677, 678, 679]. Он шифрует 384-битовые блоки открытого текста 1088-битовым ключом (на самом деле используется два ключа - 1024-битовый и 64- битовый). Из-за природы клеточных автоматов алгоритм наиболее эффективен при реализации в больших параллельных интегрированных схемах.

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

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

CA-1.1 основан на структуре блочных связей. То есть, обработка блока сообщения частично отделена от обработки потока случайной информации, вставленной при шифровании. Эта случайная информация служит для связи друг с другом стадий шифрования. Она также может быть использована для связи с потоком шифротекста. Информация связи генерируется как часть шифрования.

Так как CA-1.1 представляет собой новый алгоритм, слишком рано делать какие-либо заявления о его безопасности. Гутовиц упоминает некоторые возможные вскрытия, включая дифференциальный криптоанализ, но ему не удалось вскрыть алгоритм. В качестве стимула Гутовиц предложил награду в 1000 долларов для "первого человека, который разработает доступную процедуру вскрытия CA-1.1."

CA-l.1 запатентован [678], но доступен для некоммерческого использования. При необходимости получить лицензию на алгоритм или объявленную награду за криптоанализ обращайтесь к Говарду Гутовицу по адресу Howard Cutowitz, ESPCI, Laboratorie d'Electronique, 10 rue Vauquelin, 75005 Paris, France.

SKIPJACK

Skipjack разработан NSA в качестве алгоритма шифрования для микросхем Clipper и Capstone (см. разделы 24.16 и 24.17). Так как этот алгоритм объявлен секретным, его подробности никогда не публиковались. Он будет реализован только как защищенная от взлома аппаратура.

Этот алгоритм объявлен секретным не потому, что это повышает его надежность, а потому что NSA не хочет, чтобы Skipjack использовался без механизма условного вручения ключей Clipper. Агентство не хочет, чтобы программные реализации алгоритма распространились по всему миру.

Безопасен ли Skipjack? Если NSA захочет создать безопасный алгоритм, оно, скорее всего, это сделает. С другой стороны, если NSA захочет создать алгоритм с лазейкой, то оно сможет сделать и это. Вот что было опубликовано [1154, 462].

— Это итеративный блочный шифр.

— Размер блока - 64 бита.

— Алгоритм использует 80-битовый ключ.

— Он может быть использован в режимах ECB, CBC, 64-битовый OFB, либо 1-, 8-, 16-, 32- или 64-битовый CFB.

— Операция шифрования или дешифрирования состоит из 32 этапов.

— NSA начало работу над ним в 1985 и завершило проверку в 1990.

В документации на микросхему Mykotronx Clipper утверждается, что задержка в выдаче результата, присущая алгоритму Skipjack, составляет 64 такта. Это означает, что на каждый этап приходится два такта: один предположительно для подстановки с помощью S-блока, а другой - для заключительного XOR в конце каждого этапа. (Не забывайте, перестановки при аппаратных реализациях не занимают времени.) В документации Mykotronx эта двухтактная операция называется "G-блоком", а все вместе - "сдвигом". (Часть G-блока носит название "F-таблицы" и является таблицей констант, а может быть таблицей функций.)

По одним слухам Skipjack использует 16 S-блоков, а по другим для хранения S-блоков нужно всего 128 байт памяти. Непохоже, чтобы оба этих слуха были правдой.

Еще один слух утверждает, что этапы Skipjack, в отличие от DES, работают не с половиной блока. Это вместе с замечанием о "сдвигах" и случайном заявлении на Crypto '94 о том, что в Skipjack применяется "48-битовая внутренняя структура", позволяет сделать вывод, что алгоритм по своей схеме похож на SHA (см. раздел 18.7), но использует четыре 16-битовых подблока. Три подблока, обработанные зависящей от ключа однонаправленной функцией, дают 16 битов, которые подвергаются операции XOR с оставшимся подблоком. Затем весь блок циклически сдвигается на 16 битов и поступает на вход следующего этапа, или сдвига. При этом также используются 128 байтов данных S-блока. Я подозреваю, что S-блоки зависят от ключа.

По своей структуре Skipjack вероятно похож на DES. NSA понимает, что его защищенная от взлома аппаратура в конце концов будет вскрыта и исследована, они не будут рисковать никакими передовыми криптографическими методами.

То, что NSA планирует использовать алгоритм Skipjack для шифрования своей Системы защиты сообщений (Defense Messaging System, DMS), свидетельствует о безопасности алгоритма. Чтобы убедить скептиков, NIST разрешил комиссии "уважаемых неправительственных экспертов... получить доступ к конфиденциальным подробностям алгоритма, чтобы они исследовали его возможности и опубликовали результаты своих исследований " [812].

В предварительном отчете этой комиссии экспертов [262] (окончательного отчета не было, и возможно никогда не будет) сообщалось:

Принимая во внимание, что стоимость вычислительных мощностей уменьшается в два раза каждые 18 месяцев, сложность вскрытия Skipjack сравняется с сегодняшней сложностью вскрытия DES только через 36 лет. Следовательно, риск, что Skipjack будет взломан в ближайшие 30-40 лет, незначителен.

Незначителен и риск взлома Skipjack с помощью более быстрых способов вскрытия, включая дифференциальный криптоанализ. У алгоритма не слабых ключей, отсутствует и свойство комплиментарности. Эксперты в отсутствие времени для самостоятельного большого исследования алгоритма изучили представленное NSA описание разработки и проверки алгоритма

Устойчивость Skipjack к криптоанализу не зависит от хранения в тайне самого алгоритма.

Итак, участники дискуссии не смогли поработать с алгоритмом достаточно долго, чтобы прийти к каким-нибудь выводам самостоятельно. Все, что они смогли сделать - это взглянуть на результаты, показанные им NSA.

Остался без ответа вопрос, является ли плоским пространство ключей Skipjack (см. раздел 8.2). Даже если у Skipjack нет ключей, слабых в смысле DES, ряд особенностей процесса использования ключа может сделать одни ключи сильнее других. У Skipjack может быть 2⁷⁰ сильных ключей, гораздо больше чем у DES, вероятность случайно выбрать один из этих сильных ключей будет приблизительно 1 к 1000. Лично я думаю, что пространство ключей Skipjack - плоское, но то, что об этом никто не заявил публично, вызывает тревогу.

Skipjack запатентован, но в соответствии с соглашением о секретности патента [1122] этот патент хранится в тайне. Патент будет опубликован тогда и только тогда, когда алгоритм Skipjack будет успешно восстановлен кем-то посторонним. Это дает возможность правительству воспользоваться и преимуществом защиты патентом, и преимуществом конфеденциальности торгового секрета.