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

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

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

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

В криптологической среде большинство споров по поводу вскрытия грубой силой сконцентрированы вокруг алгоритма DES. В 1977 году Уитфилд Диффи и Мартин Хеллман [497] сформулировали условия существования специализированной машины по взлому DES. Эта машина состоит из миллионов микросхем, каждая из кот о-рых проверяет миллион ключей в секунду. Такая машина за два часа сможет проверить 2⁵⁶ за 20 часов. При вскрытии алгоритма с 64-битовым ключом проверка всех 2^м потребует 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 году.

Длина ключей в битах

Стоимость
$100 К	2 секунды	35 часов	1год	70000 лет	1014лет	1019лет
$1М	0.2 секунды	3.5 часа	37 дней	7000 лет	10" лет	1018лет
$10М	0.02 секунды	21 минута	4 дня	700 лет	1012лет	1017лет
$100 М	2 миллисекунды	2 минуты	9 часов	70 лет	10" лет	1016лет
$1Г	0.2 миллисекунды		1час	7 лет	1010лет	1015лет
$10 Г	0.02. миллисекунды	1 секунда	5.4 минуты	245 дней	10'лет	1014лет
$100 Г	2 микросекунды	0.1 секунды	32 секунд	24 дня	108лет	10" лет
$1 Т	0.2 микросекунды	0.01 секунды	3 секунды	2.4 дня	Ю'лет	1012лет
$10Т	0.02 микросекунды	1 миллисекунда	0.3 секунды	6 часов	106лет	10" лет

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