Скорость вскрытия грубой силой определяется двумя параметрами : количеством проверяемых ключей и скоростью проверки одного ключа. Большинство симметричных алгоритмов в качестве ключа могут использ о-вать в качестве ключа любую битовую последовательность фиксированной длины. Длина ключа 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]. Взломщик пишет и выпускает на волю компьюте р-ный вирус. Этот вирус не переформатирует жесткий диск, не удаляет файлы, но во время простоя компьютера он работает на криптоаналитической проблемой грубого взлома. Различные исследования показали, что комп ь-

ютер простаивает от 70 до 90 процентов времени, так что у вируса не будет проблем с временем для решения этой задачи. Если он нетребователен и в других отношениях, то его работа даже не будет заметна.

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

Другим, трусливым подходом бал бы вывод на экран следующего сообщения :

В этом компьютере есть серьезная ошибка. Пожалуйста позвоните 1-8001234567 и продиктуйте оператору следующее 64-битовое число:

xxxx xxxx xxxx xxxx

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

Насколько эффективно такое вскрытие? Пусть типичный зараженный компьютер проверяет тысячу ключей в секунду. Эта скорость намного меньше потенциальных возможностей компьютера, ведь мы полагаем, что он иногда будет делать и другие вещи. Предположим также, что типичный вирус инфицирует 10 миллионов машин. Этот вирус может вскрыть 56-битовый ключ за 83 дня, а 64 битовый - за 58 лет. Вам возможно пришлось бы подкупить разработчиков антивирусного программного обеспечения, но это уже ваши проблемы . Любое увеличение скорости компьютеров или распространения вируса, конечно, сделало бы это нападение более эффективным.

Китайская лотерея

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

Если у каждого человека в Китае, будь то мужчина, женщина или ребенок, есть радиоприемник или телев и-зор, то правильное значение 56-битового ключа появится через 61 секунду. Если радиоприемник или телевизор есть только у каждого десятого китайца(что близко к действительности), то правильный ключ появится через 10 минут. Правильный 64-битовый ключ будет раскрыт через 4.3 часа (43 часа, если радиоприемник или телевизор есть только у каждого десятого китайца) .

Чтобы сделать такое вскрытие возможным на практике, необходимо сделать ряд модификаций. Во первых, проще, чтобы каждая микросхема проверяла случайные, а не уникальные ключи . Это сделает вскрытие на 39% медленнее, что не очень важно для чисел такого масштаба . Затем, Китайская коммунистическая партия должна принять решение, что каждый должен включать свой приемник или телевизор в определенное время, чтобы гарантировать работу всех приемных устройств во время передачи пары открытый текст/шифротекст . Наконец, каждому должно быть приказано позвонить в Центр - или как он там называется - когда ключ появляется у него на экране и зачитать строку чисел, появившуюся на экране .

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