Оценки времени и стоимости вскрытия грубой силой - раздел Компьютеры, Часть 2 Криптографические методы Вспомните, Что Вскрытие Грубой Силой Обычно Является Вскрытием С Использовани...
Вспомните, что вскрытие грубой силой обычно является вскрытием с использованием известного открытого текста, для этого нужно немного шифротекста и соответствующего открытого текста . Если вы предполагаете, что наиболее эффективным способа взлома алгоритма является вскрытие грубой силой - большое допущение -то ключ должен быть достаточно длинным, чтобы сделать вскрытие невозможным . Насколько длинным?
Скорость вскрытия грубой силой определяется двумя параметрами : количеством проверяемых ключей и скоростью проверки одного ключа. Большинство симметричных алгоритмов в качестве ключа могут использ о-вать в качестве ключа любую битовую последовательность фиксированной длины. Длина ключа DES составляет 56 бит, всего может быть 256 возможных ключей. Длина ключей для ряда алгоритмов, обсуждаемых в этой книге, равны 64 битам, всего может быть 2мвозможных ключей. Другие алгоритмы используют 128-битовые ключи.
Скорость, с которой может быть проверен каждый ключ, имеет менее важное значение . Для проводимого анализа я предполагаю, что скорость проверки ключа для каждого алгоритма примерно одинакова. В действ и-тельности скорость проверки одного алгоритма может быть в два, три или даже десять раз выше чем другого . Но так как для тех длин ключей, для которых мы проводим поиск, время поиска в миллионы раз больше, чем время проверки одного ключа, небольшие отличия в скорости проверки не имеют значения.
В криптологической среде большинство споров по поводу вскрытия грубой силой сконцентрированы вокруг алгоритма DES. В 1977 году Уитфилд Диффи и Мартин Хеллман [497] сформулировали условия существования специализированной машины по взлому DES. Эта машина состоит из миллионов микросхем, каждая из кот о-рых проверяет миллион ключей в секунду. Такая машина за два часа сможет проверить 256 за 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 бит.
Программное вскрытие
Без специализированной аппаратуры и огромных параллельных машин вскрытие грубой силой намного сложнее. Программное вскрытие в тысячи раз медленнее, чем аппаратное .
Реальная угроза програм
Нейронные сети
Нейронные сети не слишком пригодны для криптоанализа, в первую очередь из-за формы пространства р е-шений. Лучше всего нейронные сети работают с проблемами, имеющими непрерывное множество решений,
Китайская лотерея
Китайская Лотерея - эклектический, но возможный способ создания громадной параллельной машины для криптоанализа [1278]. Вообразите, что микросхема, вскрывающая алгоритм грубой силой со скоростью ми
Биотехнология
Если возможно создание биомикросхем, то было бы глупо не попытаться использовать их в инструмента криптоанализа вскрытием грубой. Рассмотрим гипотетическое животное, называемое "ВЕБозавром&quo
Термодинамические ограничения
Одним из следствий закона второго термодинамики является то, что для представления информации нео б-ходимо некоторое количество энергии. Запись одиночного бита, изменяющая состояние системы, требуе
Поля чисел
Количество бит
Сколько mips-лет нужно для разложе-
ния
Квантовые вычисления
А теперь еще большая фантастика. В основе квантовых вычислений используется двойственная природа м а-терии (и волна, и частица). Фотон может одновременно находиться в большом количестве состояний.
Тойчивостью к вскрытию грубой силой
Длина симметричного Длина открытого
ключа (в битах) ключа (в битах)
56 384
64 512
80 768
112 1792
Из этой таблица можно сд
Уменьшенные пространства ключей
DES использует 56-битовый ключ с битами. Любая правильно заданная 56-битовая строка может быть кл ю-чом, существует 256 (1016) возможных ключей. Norton Discreet for MS-DOS (ве
Ключевые фразы
Лучшим решением является использование вместо слова целой фразы и преобразование этой фразы в ключ . Такие фразы называются ключевыми фразами.Методика с названием перемалыв
Стандарт генерации ключей Х9.17
Стандарт ANSI X9.17 определяет способ Генерации ключей (см. 7th) [55]. Он не создает легко запоминающиеся ключи, и больше подходит для генерации сеансовых ключей или псевдослучайных чисел в систем
Генерация ключей в министерстве обороны США
Министерство обороны США для генерации случайных ключей рекомендует использовать DES в режиме OFB (см. раздел 9.8) [1144]. Создавайте ключи DES, используя системные вектора прерывания, регистры со
Обнаружение ошибок при передаче ключей
Иногда ключи искажаются при передаче. Это является проблемой, так как искаженный ключ может приве с-ти к мегабайтам нерасшифрованного шифротекста. Все ключи должны передаваться с обнаружением ошибо
Обнаружение ошибок при дешифрировании
Иногда получатель хочет проверить, является ли его конкретный ключ правильным ключом симметричного дешифрирования. Если открытый текст сообщения представляет собой что-то похожее на ASCII, он может
Контроль использования ключей
В некоторых приложениях может потребоваться контролировать процесс использования сеансового ключа . Некоторым пользователям сеансовые ключи нужны только для шифрования или только для дешифрирования
Заверенные открытые ключи
Заверенным открытым ключом,или сертификатом, является чей-то открытый ключ, подписанный заел у-живающим доверия лицом. Заверенные ключи используются, чтобы помешать попыткам подмен
Распределенное управление ключами
В некоторых случаях такой способ централизованного управления ключами работать не будет . Возможно, не существует такого СА, которому доверяли бы Алиса и Боб. Возможно, Алиса и Боб доверяют только
Типы алгоритмов и криптографические режимы
Существует два основных типа симметричных алгоритмов : блочные шифры и потоковые шифры. Блочные шифрыработают с блоками открытого текста и шифротекста - обычно длиной 64 бита, но и
Набивка
Большинство сообщений точно не делятся на 64-битные (или любого другого размера) блоки шифрования, в конце обычно оказывается укороченный блок. ЕСВ требует использовать 64-битные блоки. Способом ре
Вектор инициализации
В режиме СВС одинаковые блоки открытого текста при шифровании переходят в различные блоки шифр о-текста только, если отличались какие-то из предшествующих блоков открытого текста . Два идентичных с
Вопросы безопасности
Ряд возможных проблем обуславливаются структурой СВС. Во первых, так как блок шифротекста достаточно просто влияет на следующий блок, Мэллори может тайно добавлять блоки к концу зашифрованного соо
Вопросы безопасности
Самосинхронизирующиеся потоковые шифры также чувствительны к вскрытию повторной передачей. Сначала Мэллори записывает несколько битов шифротекста. Затем, позднее, он вставляет эту запись в текущий
Вектор инициализации
Для инициализации процесса CFB в качестве входного блока алгоритма может использоваться вектор ин и-циализации IV. Как и в режиме СВС IV не нужно хранить в секрете.
Однако IV должен быть у
Распространение ошибки
Врежиме CFB ошибка в открытом тексте влияет на весь последующий шифротекст, но самоустраняется при дешифрировании. Гораздо интереснее ошибка в шифротексте. Первым эффектом сбоя бит
Вскрытие вставкой
Синхронные потоковые шифры чувствительны к вскрытию вставкой[93]. Пусть Мэллори записал поток шифротекста, но не знает ни открытого текста, ни потока ключей, использованного для ши
Распространение ошибки
В режиме OFB распространения ошибки не происходит. Неправильный бит шифротекста приводит к неправильному биту открытого текста. Это может быть полезно при цифровой передаче аналоговых величин, нап
OFB и проблемы безопасности
Анализ режима OFB [588, 430, 431, 789] показывает, что OFB стоит использовать только, когда размер обратной связи совпадает с размером блока. Например, 64-битовый алгоритм нужно использовать тольк
Потоковые шифры в режиме OFB
Потоковые шифры также могут работать в режиме OFB. В этом случае ключ влияет на функцию следующ е-го состояния (см. -4-й). Функция выхода не зависит от ключа, очень часто она является чем-то просты
Режим распространяющегося сцепления блоков шифра
Режим распространяющегося сцепления блоков шифра(propagating cipher block chaining, PCBC) [1080] похож на режим СВС за исключением того, что и предыдущий блок открытого текста, и п
Сцепление блоков шифра с контрольной суммой
Сцепление блоков шифра с контрольной суммой(cipher block chaining with checksum, CBCC) представляет собой вариант СВС [1618]. Сохраняйте значение XOR всех уже зашифрованных блоков
Выходная обратная связь с нелинейной функцией
Выходная обратная связь с нелинейной функцией (output feedback with a nonlinear function, OFBNLF) [777] представляет собой вариант и OFB, и ЕСВ, где ключ изменяется с каждым блоком:
С, =
Прочиережимы
Возможны и другие режимы, хотя они используются нечасто . Сцепление блоков открытого текста (plaintext block chaining, PBC) похоже на СВС за исключением того, что операция XOR выполняется для с бло
CHOOSING AN ALGORITHM
When it comes to evaluating and choosing algorithms, people have several alternatives:
- They can choose a published algorithm, based on the belief that a published algorithm has been scru
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов