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

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

Для выполнения такого вскрытия криптоаналитику требуется кусочек шифротекста и соответствующего о т-крытого текста, вскрытие грубой силой представляет собой вскрытие с известным открытым текстом . Для блочного шифра криптоаналитику понадобится блок шифротекста и соответствующий открытый текст : обычно 64 бита. Заполучить такие кусочки открытого текста и шифротекста легче, чем можно себе представить . Криптоа-налитик может получить каким-то образом копию открытого текста сообщения и перехватить соответствующий шифротекст. Он может знать что-то о формате шифротекста: например, что это файл в формате WordPerfect, или у него есть стандартный заголовок сообщения электронной почты , или файл каталога UNIX, или изображение в формате TIFF, или стандартная запись в базе данных клиентов. Все эти форматы содержат некоторые предопределенные байты. Криптоаналитику для такого вскрытия не нужно много открытого текста .

Рассчитать сложность вскрытия грубой силой нетрудно. Если используется 8-битовый ключ, то существует 28, или 256, возможных ключей. Следовательно, для обнаружения правильного ключа потребуется, самое большее, 256 попыток, с 50-процентной вероятностью найти нужный ключ после половины попыток . Если длина ключа равна 56 битам, то существует 256 возможных ключей. Если компьютер может проверить миллион ключей в секунду, поиск нужного ключа займет в среднем 2285 лет. Если используется 64-битовый ключ, то тому же суперкомпьютеру понадобится около 585000 лет, чтобы найти правильный ключ среди 264 возможных ключей. Если длина ключа равна 128 битам поиск ключа займет 1025 лет. Возраст вселенной составляет всего 1010 лет, поэтому 1025 лет - это большое время. При 2048-битовом ключе миллион компьютеров, работая параллел ь-но и проверяя миллион ключей в секунду, потратят 10587 лет в поисках ключа. К этому времени вселенная давно расширится, превратившись в ничто или сожмется.

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

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

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

Оценки времени и стоимости вскрытия грубой силой

Вспомните, что вскрытие грубой силой обычно является вскрытием с использованием известного открытого текста, для этого нужно немного шифротекста и соответствующего открытого текста . Если вы предполагаете, что наиболее эффективным способа взлома алгоритма является вскрытие грубой силой - большое допущение -то ключ должен быть достаточно длинным, чтобы сделать вскрытие невозможным . Насколько длинным?

Скорость вскрытия грубой силой определяется двумя параметрами : количеством проверяемых ключей и скоростью проверки одного ключа. Большинство симметричных алгоритмов в качестве ключа могут использ о-вать в качестве ключа любую битовую последовательность фиксированной длины. Длина ключа DES составляет 56 бит, всего может быть 256 возможных ключей. Длина ключей для ряда алгоритмов, обсуждаемых в этой книге, равны 64 битам, всего может быть 264 возможных ключей. Другие алгоритмы используют 128-битовые ключи.

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

В криптологической среде большинство споров по поводу вскрытия грубой силой сконцентрированы вокруг алгоритма DES. В 1977 году Уитфилд Диффи и Мартин Хеллман [497] сформулировали условия существования специализированной машины по взлому DES. Эта машина состоит из миллионов микросхем, каждая из кот о-рых проверяет миллион ключей в секунду. Такая машина за два часа сможет проверить 256 за 20 часов. При вскрытии алгоритма с 64-битовым ключом проверка всех 264 потребует 214 дней.

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

Сконструировать машину для взлома грубой силой Майкл Винер решил [1597, 1598]. (Он сконструировал машину для DES, но анализ может быть выполнен почти для всех алгоритмов.) Он разработал специализированные микросхемы, платы и стойки, оценил затраты и сделал вывод, что за миллион долларов можно постр о-ить машину, которая сможет взломать 56-битный ключ DES key в среднем за 3.5 часа (и наверняка за 7 часов). Соотношение стоимость/скорость является линейным. Для ряда длин ключей эти значения обобщены в 6-й. Вспомните о законе Мура: мощь вычислительных средств приблизительно каждые 18 месяцев . Это означает, что затраты будут уменьшаться на порядок каждые пять лет, и то, что в 1995 году стоит миллион долларов, в 2000 году будет стоить около 100000 долларов. Еще более упростить процесс вычислений могла бы конвейер и-зация [724].

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

Конечно, нелепо прогнозировать компьютерную мощь на 35 лет вперед . Технологические прорывы, популярные в научной фантастике, могут сделать эти прогнозы смешными . С другой стороны, неизвестные в настоящее время физические ограничения могут сделать эти прогнозы нереально оптимистичными . В криптографии умнее быть пессимистом. Применение в алгоритме 80-битного ключа кажется недостаточно дальновидным . Используйте ключ, длина которого, по меньшей мере, 112 бит.

Табл. 7-1.

Оценки среднего времени для аппаратного вскрытия грубой силой в 1995 году.

Если взломщик очень сильно хочет взломать ключ, все, что ему нужно, это потратить деньги . Следовательно, стоит попытаться определить минимальную "цену" ключа: в пределах какой стоимости сведений можно пользоваться одним ключом прежде, чем его вскрытие станет экономически выгодным ? Крайний случай: если шифрованное сообщение стоит $1.39, то нет финансового смысла устанавливать аппаратуру стоимостью 10 миллионов долларов для взлома этого ключа. С другой стороны, если стоимость открытого текста -100 миллионов долларов, то дешифрирование этого одиночного сообщения вполне окупит стоимость аппарат у-ры взлома. Кроме того, стоимость многих сообщений со временем очень быстро падает .

Программное вскрытие

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

Реальная угроза программного вскрытия грубой силой страшна не своей неизбежностью, а тем, что такое вскрытие "свободно". Ничего не стоит загрузить простаивающий микрокомпьютер проверкой возможных кл ю-чей. Если правильный ключ будет найден - замечательно, если нет - ничего не потеряно . Ничего не стоит использовать для этого целую сеть микрокомпьютеров. В недавних экспериментах с DES 40 рабочих станций в течение одного дня сумели проверить 234 ключей [603]. При этой скорости для проверки всех ключей потреб у-ется четыре миллиона дней, но если попытки вскрытия будут предприняты достаточным количеством людей , то кому-нибудь где-нибудь повезет. Как было сказано в [603]:

Основной угрозой программного вскрытия является слепое везение . Представьте себе университетскую сеть из 512 объ единенных в сеть рабочих станций. Для некоторых университетских городков это сеть весьма среднего размера. Такие сети могут даже расползтись по всему миру, координируя свою деятельность по электронной почте . Пусть каждая рабочая станция способна работать (с алгоритмом) со скоростью 15000 шифрований в секунду. ... С учетом накладных расходов на проверку и смену ключей уменьшим скорость до . . . 8192 проверок в секунду на машину. Чтобы, используя описанную систему, исчерпать пространство (56-битовых) ключей потребуется 545 лет (в предположении, что сеть тратит на эту задачу 24 часа в сутки). Заметим, однако, что с помощью таких вгчислений сторонники нашего студента получают один шанс из 200000 раскрыть ключ в течение одного дня. За долгий уикенд их шансы возрастают до одного из шестидесяти шести тысяч . Чем быстрее их аппаратура, или чем больше задействовано машин, тем лучше становятся их шансы . Вероятность заработать на жизнь, выигрывая на скачках, невысока, но разве не эти выигрыши заполняют собой пресс-релизы . К примеру, это гораздо большая вероятность, чем возможность выигрыша в правительственных лотереях. "Один на миллион"? "Один раз за тысячу лет "? Больше невозможно с полной ответственностью делать такие заявления . Является ли приемлемым этот продолжающийся риск?

Использование алгоритма с 64-битовым ключом вместо 56-битового ключа делает это вскрытие в 256 раз сложнее. А 40-битовый ключ делает картину просто безрадостной. Сеть из 400 компьютеров с производительностью 32000 шифрований в секунду может за день выполнить вскрытие грубым взломом 40-битового ключа . (В 1992 году алгоритмы RC2 и RC4 было разрешено экспортировать с 40- битовым ключом - см. раздел 13.8.)

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

Нейронные сети

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

Вирусы

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

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