Длина ключа и его полный перебор

Оглавление

• 1. Введение

  • 1.1. Что такое бит?

  • 1.2. Что такое криптографический ключ?

  • 1.3. Что такое полный перебор?

  • 1.4. Является ли полный перебор единственно возможным методом криптоанализа?

  • 1.5. 128-битный ключ в два раза устойчивее к взлому, чем 64-битный?

  • 1.6. PGP должно быть очень устойчив, так как использует ключи 1024 бита.

• 2. Текущее положение дел

• 2.1. Какова максимальная длина ключа для симметричных криптосистем, которая поддается программному взлому методом полного перебора?

• 2.2. То же, с использованием специальной аппаратуры?

• 2.3. А для несимметричных криптосистем?

• 2.4. Что относительно "кофейника" Шамира?

 3. То, что будет возможным в будущем

• 3.1. Что такое закон Мура?

• 3.2. Какова предполагаемая стоимость полного перебора с использованием специализированного оборудования?

• 3.3. А с использованием квантовых компьютеров?

 4. Различные слухи

• 4.1. NSA/DST/другие могут ломать ключи до 128 бит.

• 4.2. NSA/DST/другие обладают квантовыми компьютерами.

• 4.3. NSA/DST/другие достигли методов криптоанализа, недоступных другим.

• 4.4. Я работаю на NSA/DST/других и поэтому пытаюсь убедить общественность, что 128-битное шифрование надежно.

1. Введение

1.1. Что такое бит?

Бит является фундаментальной единицей информации. Он может принимать значения 0 или 1. В течение сорока последних лет компьютеры работают с бинарными данными, то есть с наборами битов (а не с цифрами от 0 до 9, как это принято у людей; можно сказать, что компьютеры имеют только два пальца). Биты позволяют кодировать целые числа, символы, и т.д.. Вся информация, проходящая через компьютер, превращается в биты.

8 бит образуют байт; это дает 256 комбинаций и позволяет кодировать числа от 0 до 255 или символы (включая разницу между прописными и строчными буквами, символы с надстрочными знаками и другие).

1024 байта образуют один килобайт (кБ). 1024 используется вместо 1000 так как 1024 является степенью числа 2, то есть "круглым" числом, если работать по основанию 2. 1024 килобайта образуют мегабайт (МБ), или 1048576 байт. 1024 мегабайта образуют гигабайт (ГБ), или 1073741824 байта. 1024 ГБ образуют терабайт (ТБ). Дальнейшее умножение малоупотребительно, т.к. дорогостояще со всех точек зрения. Типичная емкость жестких дисков широко распространенных в настоящее время компьютеров составляет десять гигабайт. Развитая сеть может пропускать десять мегабайт в секунду между двумя машинами.

1.2. Что такое криптографический ключ?

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

Действительно, сохранять в тайне алгоритм проблематично, и, кроме того, необходима численная оценка его безопасности. Сам факт публикации алгоритма позволяет "бесплатно" получить признание его надежности криптографическим сообществом.

Ключ, таким образом, является концентрацией секрета, этот набор битов является "эссенцией" конфиденциальности.

1.3. Что такое полный перебор?

Взломать криптосистему, значит суметь осуществить некоторые операции, требующие (в теории) знания секрета (ключа), не имея информации о последнем. Наиболее полным взломом является взлом, в результате которого становится известен ключ, что дает взломщику те же полномочия, что и законному владельцу ключа.

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

С точки зрения статистики, надо перебрать примерно половину возможных ключей, прежде чем найдется правильный. Если длина ключа составляет 56 битов, это означает, что в среднем необходимо провести 2^55 итераций, что составит 36028797018963968.

1.4. Является ли полный перебор единственно возможным методом криптоанализа?

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

Кроме того, существуют криптосистемы (в частности, системы асимметричные, называемые еще "системами с открытым ключом"), для которых все сочетания битов не образуют правильного ключа. Типичный пример - RSA, где ключ представлен большим числом, полученным из двух больших простых чисел. Совокупность наборов из 1024 бит, которые являются двоичной записью этих чисел, гораздо меньше 2^1024. Полный перебор абсурден в этом случае.

1.5. 128-битный ключ в два раза устойчивее к взлому, чем 64-битный?

НЕТ! Это распространенная ошибка. Каждый дополнительный бит удваивает количество возможных ключей и затраты на полный перебор. Ключ длиной 128 бит является в 18446744073709551616 раз более сложным для подбора, по сравнению с ключом длиной 64 бита (который уже не назовешь совсем легким).

1.6. PGP должно быть очень устойчив, так как использует ключи 1024 бита.

Стоп! Давайте разберемся! "1024 бит" в PGP - это ключ RSA или DSS, то есть ключ асимметричного алгоритма. Атака методом полного перебора не самый лучший вариант в этом случае.

Кроме того, асимметричные алгоритмы относительно медленны, и "внутри" PGP использует симметричный алгоритм (исторически IDEA, затем CAST) размер ключа которого составляет 128 бит.

2. Текущее положение дел

2.1. Какова максимальная длина ключа для симметричных криптосистем, которая поддается программному взлому методом полного перебора?

Известно, что два ключа по 56 бит были подобраны полным перебором на обычных компьютерах типа PC. Специализированная машина (построенная EFF) помогла для второго ключа, выполнив приблизительно треть общего объема вычислений.

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

Полный перебор ключа длиной 64 бита для RC5 (для которого сложность полного перебора несколько выше, чем для DES) в настоящее время продолжается, и будет длиться, по крайней мере, еще нескольких лет. Напоминаем, что подбор ключа размером 64 бита, является в 256 раз более трудоемким, чем подбор ключа длиной 56 бит.

2.2. То же, с использованием специальной аппаратуры?

Американская группа EFF, инвестировала 250000$ в создание специализированной машины под названием "Deep crack" ("глубокий взлом"), которая в состоянии перебрать все ключи алгоритма DES приблизительно за три дня. В ней использованы специализированные процессоры, которые невозможно применить для целей, отличных от взлома DES (в частности, они ничего "не знают" о RC5).

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

2.3. А для несимметричных криптосистем?

В принципе, существуют две математические задачи, используемые в асимметричных шифрах: факторизация и дискретное логарифмирование. RSA использует первую, DSS вторую. Другие упоминаемые задачи (вариации двух предыдущих, использование эллиптических кривых, задача об укладке ранца, минимизация сети (задача коммивояжера), обратное распознавание (permuted perceptrons problem - см. примечания) относительно редко используются в настоящее время.

Рекорд факторизации датируется 22-ым августа 1999: число размером 155 десятичных цифр (512 бит) было факторизовано за шесть месяцев вычислений на парке приблизительно из 600 машин, некоторые из которых могут быть квалифицированны как "быки" (в частности Cray с 2 ГБ памяти). Примененные алгоритмы гораздо более сложны, чем полный перебор, и требуют большого количества оперативной памяти с хорошей скоростью доступа.

Дискретное логарифмирование менее исследовано, на его взлом осуществлено меньше инвестиций, чем на факторизацию. Рекорд - порядка 95 десятичных цифр.

2.4. Что относительно "кофейника" Шамира?

Представленный на Eurocrypt'99 в Праге (в начале мая 1999), этот аппарат ускоряет физическими средствами исследование гладких чисел (то есть полученных произведением только маленьких простых чисел), которые получают обычно методом решета. Эти числа являются основой нескольких алгоритмов факторизации и решений задачи дискретного логарифмирования.

Сам аппарат еще не построен, описаны только его принципы. Существуют технические проблемы для реализации прототипа (Arjen Lenstra высказал некоторые возражения, с которыми Adi Shamir согласился).

По общему мнению, этот метод позволил бы факторизовать число приблизительно в 600 бит, со средствами, которые позволили установить рекорд в 465 бит (в феврале 1999), если все проблемы с реализацией будут решены. Отмечено, что решето заняло приблизительно 60% времени для рекорда в 512 бит.

Все же шоу было очень увлекательным. Phil Zimmerman, автор PGP, заметил, что очень доволен тем, что исследователи интересуются, как обстоят дела в этих проблемах, так как это увеличивает степень доверия к такого рода системам.

3. То, что будет возможным в будущем

3.1. Что такое закон Мура?

Закон Мура (Moore) является оценкой развития вычислительной техники во времени. В базовом варианте он гласит, что для заданной стоимости (в широком смысле, включая энергопотребление, производство оборудования, износ, стоимость хранения, и т.д.) вычислительная мощность увеличивается в 8 раз каждые 3 года. Говоря более точно, можно сказать, что через каждые три года, технологические достижения позволяют разместить в 4 раза больше логических элементов в микросхеме заданной стоимости, одновременно ускоряя ее быстродействие в 2 раза.

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

Это касается, таким образом, систем, описываемых в терминах логических элементов, специализированных на конкретном алгоритме. Таким образом, это по сути ASIC (Application Specific Integrated Circuit - специализированные микросхемы) и FPGA (Field Programmable Gate Arrays - программируемые логические интегральные схемы); то есть перепрограммируемые цепи, выполняющие те же задачи, что и ASIC, но вдвое более дорогие при заданной мощности, однако являющиеся многоцелевыми).

3.2. Какова предполагаемая стоимость полного перебора с использованием специализированного оборудования?

Если закон Мура будет продолжать выполняться (и не имеется веских оснований для обратного, так как он учитывает качественные достижения, а не только увеличение точности обработки кремния), можно достичь машины EFF (четверть миллиона долларов, для 56 бит за 3 дня) и добавлять 3 бита каждые 3 года (3 бита = 2^3 = 8; что дает в 8 раз больше возможных вариантов ключей).

Заметим, что для сохранения закон Мура, качественные достижения должны происходить достаточно быстро, так как имеются пределы в увеличении плотности элементов на кристалле кремния (замедление вследствие туннельного эффекта). В ряде разрабатываемых методов предполагается осуществить замену кремния на арсенид галлия, что позволит достичь более высокой плотности элементов, замену алюминия медью, которая позволяет работать гораздо более быстро, построение оптической логики (оптический элемент переключается приблизительно в 100 раз быстрее электронного, но его стоимость выше более чем в 100 раз).