О документе
Рабочая группа сети H. Orman
Запрос комментариев: 3766 Purple Streak Dev.
BCP: 86 P. Hoffman
Категория: Лучшая современная практика VPN Consortium
Апрель 2004
Определение уровней стойкости открытых ключей,
используемых для обмена симметричными ключами
1. Модель защиты симметричных ключей открытыми ключами
Во многих книгах по криптографии и безопасности объясняется необходимость
открытого обмена симметричными ключами, а также множество алгоритмов,
используемых для этой цели. Однако лишь немногие из этих обсуждений
объясняют, как соотносятся стойкости открытых и симметричных ключей.
Чтобы понять это, представьте дом с прочным замком на входной двери.
Рядом с входной дверью находится небольшой запираемый ящик, содержащий
ключ от входной двери. У потенциального взломщика, который хочет
проникнуть в дом через входную дверь, есть два варианта: атаковать замок
на входной двери или атаковать замок на ящике, чтобы извлечь ключ. Ясно,
что взломщику выгоднее атаковать более слабый из двух замков. В этой
ситуации владелец дома должен обеспечить,
чтобы добавление второго варианта входа (ящика, содержащего ключ от
входной двери) было по меньшей мере столь же стойким, как замок на
входной двери, чтобы не облегчить взломщику задачу.
Разработчик, проектирующий систему обмена симметричными ключами с
использованием криптографии с открытым ключом, должен принять сходное
решение. Предположим, атакующий хочет узнать содержимое сообщения,
зашифрованного симметричным ключом, и что симметричный ключ был передан
между отправителем и получателем с использованием криптографии с
открытым ключом. У атакующего есть два варианта для восстановления
сообщения: попытка полного перебора для определения симметричного ключа
посредством повторного угадывания или математическое определение
закрытого ключа, используемого как ключ обмена ключами. Умный атакующий
будет работать над более лёгкой из этих двух задач.
Простой ответ на проблему разработчика состоит в том, чтобы обеспечить,
что система обмена ключами всегда значительно сильнее симметричного
ключа; этого можно добиться выбором очень длинного открытого ключа.
Такой проект обычно не является хорошей идеей, поскольку по мере
увеличения длины открытых ключей обмены ключами становятся значительно
дороже с точки зрения времени обработки. Поэтому перед разработчиком
стоит задача попытаться сопоставить сложность атаки на симметричный ключ
со сложностью атаки на шифрование с открытым ключом. Такой анализ не
нужен, если обмен ключами можно выполнять с исключительной безопасностью
почти без затрат с точки зрения прошедшего времени или усилий CPU; к
сожалению, сегодня это не так для методов с открытым ключом.
Третьим соображением является минимальное требование пользователя к
безопасности. Предположим, пользователь шифрует с помощью CAST-128 и
требует симметричный ключ со временем устойчивости к атаке полного
перебора в 20 лет. Он может начать с выбора ключа со случайными 86
битами, затем использовать одностороннюю функцию, такую как SHA-1, чтобы
«усилить» его до блока из 160 битов, а затем взять 128 из этих битов как
ключ для CAST-128. В таком случае алгоритм обмена ключами должен лишь
соответствовать сложности 86 битов, а не 128 битов.
Процедура выбора такова:
1. Определите устойчивость к атаке, необходимую для удовлетворения
требований безопасности приложения. Сделайте это, оценив минимальное
число компьютерных операций, которые атакующий будет вынужден
выполнить, чтобы скомпрометировать безопасность системы, а затем
возьмите логарифм этого числа по основанию два. Назовите это значение
логарифма «n».
В отчёте 1996 года рекомендовалось 90 битов как хороший универсальный
выбор для безопасности системы. Число в 90 битов следует увеличивать
примерно на 2/3 бита в год, то есть примерно до 96 битов в 2005 году.
2. Выберите симметричный шифр, имеющий ключ не менее чем с n битами и
не менее такой же криптоаналитической стойкостью.
3. Выберите алгоритм обмена ключами с устойчивостью к атаке не менее
n битов.
Четвёртым соображением может быть метод аутентификации открытого ключа,
используемый для установления личности пользователя. Это может быть
цифровая подпись RSA или цифровая подпись DSA. Если модуль для метода
аутентификации недостаточно велик, то может рухнуть вся основа доверия
к связи. Поэтому добавляется следующий шаг:
4. Выберите алгоритм аутентификации с устойчивостью к атаке не менее
n битов. Это обеспечивает, что аналогичный ключ, передаваемый между
двумя сторонами, не может быть подделан в течение срока сохранения
секретности зашифрованного материала. Это может не быть строго
необходимо, если ключи аутентификации часто меняются и имеют хорошо
понятный срок использования, но при отсутствии этого указание в n
битов является обоснованным.
1.1. Алгоритмы обмена ключами
Метод Диффи—Хеллмана использует группу, генератор и показатели степени.
В современных стандартах Интернета групповая операция основана на
модульном умножении. Здесь группа определяется мультипликативной группой
целого числа, обычно простого p = 2q + 1, где q — простое число, а
арифметика выполняется по модулю p; генератор (который часто равен просто
2) обозначается g.
В Диффи—Хеллмане Алиса и Боб сначала договариваются (открыто или
конфиденциально) о значениях g и p. Алиса выбирает секретное большое
случайное целое число (a), а Боб выбирает секретное случайное большое
целое число (b). Алиса отправляет Бобу A, равное g^a mod p; Боб
отправляет Алисе B, равное g^b mod p. Затем Алиса вычисляет B^a mod p,
а Боб вычисляет A^b mod p. Эти два числа равны, и участники используют
простую функцию от этого числа в качестве симметричного ключа k.
Обратите внимание, что обмен ключами Диффи—Хеллмана можно выполнять над
различными видами представлений групп. Например, эллиптические кривые,
определённые над конечными полями, являются особенно эффективным способом
вычисления обмена ключами [SCH95].
Для обмена ключами RSA предположим, что у Боба есть открытый ключ (m),
равный p*q, где p и q — два секретных простых числа, показатель степени
шифрования e и показатель степени расшифрования d. Для обмена ключами
Алиса отправляет Бобу E = k^e mod m, где k — передаваемый секретный
симметричный ключ. Боб восстанавливает k, вычисляя E^d mod m, и обе
стороны используют k в качестве своего симметричного ключа. Хотя
показатель степени шифрования Боба e может быть довольно мал (например,
17 битов), его показатель степени расшифрования d будет содержать
столько же битов, сколько m.
2. Определение трудозатрат на факторизацию
Метод шифрования с открытым ключом RSA невосприимчив к атакам угадывания
полным перебором, поскольку модуль (и, следовательно, секретный
показатель степени d) будет иметь не менее 512 битов, а это слишком много
возможных значений для угадывания. Обмен Диффи—Хеллмана также защищён от
угадывания, поскольку показатели степени будут иметь как минимум вдвое
больше битов, чем симметричные ключи, которые будут из них выведены.
Однако оба метода подвержены математическим атакам, определяющим
структуру открытых ключей.
Факторизация модуля RSA приведёт к полной компрометации безопасности
закрытого ключа. Решение задачи дискретного логарифма для системы
модульного возведения в степень Диффи—Хеллмана аналогично разрушит
безопасность всех обменов ключами, использующих конкретный модуль. Этот
документ предполагает, что сложность решения задачи дискретного логарифма
эквивалентна сложности факторизации чисел того же размера, что и модуль.
В действительности она немного выше, поскольку требует большего числа
операций; на основании имеющихся на данный момент эмпирических данных
отношение сложности составляет не менее 20 и, возможно, достигает 64.
Решение любой из задач требует большого объёма памяти для последней стадии
алгоритма — шага редукции матрицы. Остаётся выяснить, будет ли это
требование к памяти и впредь ограничивающим фактором при решении задач с
более крупными целыми числами. В настоящее время это не так, и ведутся
активные исследования параллельных матричных алгоритмов, которые могли бы
смягчить требования к памяти для этой задачи.
Решето числового поля (NFS) [GOR93] [LEN93] сегодня является наилучшим
методом решения задачи дискретного логарифма. Формула для оценки числа
простых арифметических операций, необходимых для факторизации целого
числа n методом NFS, такова:
L(n) = k * e^((1.92 + o(1)) * cubrt(ln(n) * (ln(ln(n)))^2))
Многие предпочитают обсуждать число MIPS-лет (MYs), необходимых для
крупных операций, таких как решето числового поля. Для такой оценки
операцией в формуле L(n) является одна компьютерная
инструкция. Эмпирические данные указывают, что более близким соответствием
могли бы быть 4 или 5 инструкций, но это несущественный фактор, и в этом
документе для данного обсуждения придерживаются соотношения одна
операция/одна инструкция.
2.1. Выбор параметров для уравнения
Приведённое выше выражение имеет два параметра, которые можно оценить
эмпирическими методами: k и o(1). Для интересующего нас диапазона чисел
между ними мало различий.
Можно было бы принять, что k равно 1, а o(1) равно 0. Это достаточно
обоснованно, если выражение используется только для оценки относительных
усилий (а не фактических усилий) и предполагается, что член o(1) очень
мал в диапазоне чисел, которые предстоит разложить на множители.
Либо можно было бы предположить, что o(1) мало и приблизительно постоянно,
и поэтому его значение можно включить в k; затем оценить k по сообщаемым
объёмам усилий, затраченным на разложение больших целых чисел в тестах.
В этом документе используется второй подход, чтобы получить оценку
значимости коэффициента. Судя по следующим расчётам, она невелика.
Примеры значений из недавних работ с решетом числового поля включают:
Название теста Число Число MYs усилий
десятичных битов
цифр
RSA130 130 430 500
RSA140 140 460 2000
RSA155 155 512 8000
RSA160 160 528 3000
Существует немного точных измерений количества времени, использованного
для этих разложений на множители. В большинстве тестов разложения на
множители сотни или тысячи компьютеров используются в течение нескольких
месяцев, однако обычно не сообщаются число их циклов, использованных для
проекта разложения на множители, точное распределение типов процессоров,
их скоростей и так далее. Однако во всех приведённых выше случаях объём
использованных усилий был гораздо меньше, чем предсказывала бы формула
L(n), если бы k было равно 1, а o(1) — 0.
Аналогичная оценка усилий, выполненная в 1995 году, приведена в [ODL95].
Результаты, указывающие на то, что для метода разложения на множители
Number Field Sieve фактическое число операций меньше ожидаемого, приведены
в [DL].
2.2. Выбор k по эмпирическим отчётам
При определении k по эмпирическим отчётам получается, что k приблизительно
равно 0,02. Это означает, что «эффективная стойкость ключа» алгоритма RSA
примерно на 5 или 6 бит меньше, чем подразумевает наивное применение
уравнения L(n) (то есть приравнивание k к 1, а o(1) к 0). Эти оценки k
достаточно стабильны для чисел, приведённых в таблице. Оценка ограничена
одной значащей цифрой k, поскольку она отражает реальные неопределённости;
однако влияние дополнительных цифр привело бы лишь к незначительным
изменениям рекомендуемых размеров ключей.
Факторизаторы RSA130 использовали около 1700 MYs, но сочли, что для целей
прогнозирования это нереалистично много; используя больше памяти на своих
машинах, они могли бы легко сократить время до 500 MYs. Поэтому значение,
использованное при подготовке приведённой выше таблицы, равно 500. Эта
история, однако, подчёркивает трудность получения точной меры усилий. В
этом документе сообщённые усилия по разложению RSA155 на множители
принимаются как наиболее точная мера.
В результате изучения эмпирических данных представляется, что формулу L(n)
можно использовать, установив член o(1) в 0, а k — в 0,02, когда речь идёт
о разложении на множители чисел в диапазоне от 100 до 200 десятичных цифр.
Уравнение принимает вид:
L(n) = 0.02 * e^(1.92 * cubrt(ln(n) * (ln(ln(n)))^2))
Чтобы преобразовать L(n) из простых математических инструкций в MYs,
разделите на 3*10^13. Тогда уравнение для числа MYs, необходимого для
разложения целого числа n на множители, сводится к:
MYs = 6 * 10^(-16) * e^(1.92 * cubrt(ln(n) * (ln(ln(n)))^2))
Насколько уверенно эту формулу можно использовать для предсказания
трудности разложения на множители несколько больших чисел? Ответ состоит
в том, что она должна быть близкой верхней границей, но каждое усилие по
разложению на множители обычно сопровождается некоторым улучшением
алгоритмов или их реализаций, которое делает время выполнения несколько
меньшим, чем указывала бы формула.
2.3. Метод ро Полларда
В обменах Diffie-Hellman существует вторая атака — метод ро Полларда
[POL78]. Алгоритм основан на нахождении коллизий между значениями,
вычисленными в пространстве большого размера; его вероятность успеха
пропорциональна квадратному корню из размера пространства. Из-за метода
ро Полларда пространство поиска в обмене ключами DH для ключа (показателя
степени в члене g^a) должно быть вдвое больше симметричного ключа.
Поэтому для безопасного получения ключа из K бит реализация должна
использовать показатель степени не менее чем из 2*K бит. Подробнее см.
[ODL99].
Когда обмен ключами Diffie-Hellman выполняется с использованием метода
эллиптических кривых, методы NFS бесполезны. Однако метод коллизий всё ещё
эффективен, и сохраняется потребность в показателе степени (называемом
множителем в EC) из 2*K бит. Модуль, используемый для вычисления, также
может иметь размер 2*K бит, и он будет существенно меньше модуля,
необходимого для методов модульного возведения в степень, по мере того как
желаемый уровень безопасности превышает стойкость к атаке перебором в 64
бита.
Можно спросить: как сравнить число компьютерных инструкций, действительно
необходимых для атаки на дискретный логарифм, с числом, необходимым для
перебора пространства ключей шифра? При сравнении усилий следует учитывать,
что представляет собой «базовая операция». Для перебора пространства ключей
алгоритма симметричного шифрования, такого как DES, базовая операция — это
время выполнения настройки ключа и время выполнения одного шифрования. Для
дискретных логарифмов базовая операция — модульное возведение в квадрат.
Логарифм отношения этих двух операций можно использовать как «нормирующий
коэффициент» между двумя видами вычислений. Однако даже для очень больших
модулей (16K бит) этот коэффициент составляет лишь несколько битов
дополнительных усилий.
2.4. Ограничения большой памяти и множества машин
Роберт Сильверман исследовал вопрос о том, когда станет практически
осуществимым разложение на множители модулей RSA размером более 512 бит.
Его анализ основан не только на теоретическом числе операций, но также
включает ожидания относительно доступности реальных машин для выполнения
работы (этот документ основан только на теоретическом числе операций). Он
рассматривает вопрос о том, можно ли ожидать достаточного количества машин,
памяти и средств связи для разложения на множители очень большого числа.
Наилучшим методам разложения на множители требуется много оперативной
памяти с произвольным доступом для сбора соотношений данных (просеивания)
и критический заключительный шаг, выполняющий приведение строк большой
матрицы. Требования к памяти связаны с размером числа, которое разлагается
на множители (или для которого решается задача дискретного логарифма).
Сильверман [SILIEEE99] [SIL00] утверждал, что в обозримом будущем существует
практический предел числа машин и объёма RAM, которые можно задействовать
для одной задачи. Он видит две проблемы в атаке на 1024-битный модуль RSA:
машины, выполняющие просеивание, будут нуждаться в 64-битных адресных
пространствах, а машине для приведения строк матрицы потребуется несколько
терабайтов памяти. Сильверман отмечает, что было продано очень мало
64-битных машин,
имеющих 170 гигабайт памяти, необходимой для просеивания. Для просеивания
за разумное время (год или два) необходимо почти миллиард таких машин.
Вывод Сильвермана, основанный на истории усилий по разложению на множители
и законе Мура, состоит в том, что 1024-битные модули RSA не будут разложены
на множители примерно до 2037 года. Это подразумевает гораздо более долгий
срок жизни ключей RSA, чем указывает теоретический анализ. Он утверждает,
что на основе экстраполяций закона Мура и недавней истории усилий по
разложению на множители можно с большой уверенностью предсказывать, сколько
машин и модулей памяти будет доступно.
Практическим соображениям следует придавать большой вес, но при анализе
риска физический мир менее предсказуем, чем показывали бы графики трендов.
Рассматривая, насколько можно доверять неспособности компьютерной индустрии
удовлетворить ненасытные потребности факторизаторов, необходимо иметь
некоторое представление об экономических соображениях, которые сложнее
математики разложения на множители. Спрос на компьютерную память трудно
предсказать, поскольку он основан на приложениях: «убийственное приложение»
может появиться в любой день и привести индустрию памяти к лихорадке продаж.
Число доступных процессоров в настольных системах может быть ограничено
числом столов, но очень мощные встроенные системы обеспечивают больше продаж
процессоров, чем настольные системы. По мере того как встроенные системы
поглощают сетевые функции, нельзя считать немыслимым, что миллионы
64-битных процессоров по меньшей мере с гигабайтами памяти распространятся
в нашей среде.
Суть в том, что рекомендации по длине ключей, предсказываемые теорией,
могут быть чрезмерно консервативными, но именно их мы использовали в этом
документе. Этот вопрос доступности машин следует регулярно пересматривать
с учётом текущей технологии.
2.5. Машины специального назначения
В августе 2003 года появился проект специализированной «машины для
просеивания» (TWIRL) [Shamir2003], и он существенно изменил оценки стоимости
разложения на множители чисел размером до 1024 бит. При параллельном
применении множества высокоскоростных компонентов VLSI такая машина могла
бы выполнить просеивание 512-битных чисел за 10 минут при стоимости
аппаратуры $10K. Более крупная версия могла бы выполнить просеивание
1024-битного числа за один год при стоимости $10M. В работе приводятся
некоторые усовершенствования подходов к шагу приведения строк матрицы, на
основании которых делается вывод, что безопасность 1024-битных модулей RSA
вызывает сомнения.
Оценки времени и стоимости разложения на множители 512-битных и 1024-битных
чисел соответствуют коэффициенту ускорения примерно в 2 миллиона раз по
сравнению с тем, что можно было достичь на массовых процессорах нескольких
лет назад.
3. Время вычислений для алгоритмов
В этом разделе описывается, сколько времени требуется для использования
алгоритмов при выполнении обменов ключами. И вновь важно учитывать
увеличение времени, требующегося для обмена симметричными ключами при
увеличении длины открытых ключей. Важно избегать выбора практически
неосуществимо длинных открытых ключей.
3.1. Обмен ключами Diffie-Hellman
Обмен ключами Diffie-Hellman выполняется с конечной циклической группой G,
генератором g и показателем степени x. Как отмечено в разделе о методе ро
Полларда, показатель степени имеет вдвое больше битов, чем необходимо для
конечного ключа. Пусть размер группы G равен p, число битов в представлении
p по основанию 2 равно j, а число битов в показателе степени равно K.
При выполнении операций, результатом которых является общий ключ, генератор
возводится в степень. Наиболее эффективный способ сделать это включает
возведение числа в квадрат K раз и несколько умножений по ходу вычисления.
Каждое из чисел содержит j/w компьютерных слов, где w — число битов в
компьютерном слове (сегодня это будет 32 или 64 бита). Наивное допущение
состоит в том, что потребуется выполнить j возведений в квадрат и j/2
умножений; к счастью, эффективной реализации потребуется меньше (NB: в
оставшейся части этого раздела n представляет j/w).
Операция возведения в квадрат не требует столько же операций, сколько
умножение; разумная оценка состоит в том, что возведение в квадрат занимает
0,6 числа машинных инструкций, требуемых умножением. Если заранее
подготовить таблицу с несколькими значениями малых целочисленных степеней
генератора g, то потребуется лишь примерно пятая часть числа умножений,
предполагаемого наивной формулой. Поэтому необходимо выполнить работу,
приблизительно эквивалентную .8*K умножениям чисел из n слов на n слов.
Далее, за каждым умножением и возведением в квадрат должно следовать
модульное сокращение, и хорошим допущением является то, что выполнить
модульное сокращение так же трудно, как выполнить умножение чисел из n слов
на n слов. Таким образом, для возведений в квадрат требуется K сокращений,
а для умножений — .2*K сокращений. В сумме общие усилия для обмена ключами
Diffie-Hellman с показателями степени из K бит и модулем из n слов
приблизительно равны 2*K умножениям чисел из n слов на n слов.
Для 32-битных процессоров целые числа, использующие в своём представлении
менее примерно 30 компьютерных слов, требуют по меньшей мере n^2 инструкций
для умножения чисел из n слов на n слов. Для больших чисел потребуется
меньше времени благодаря умножениям Карацубы, и для больших n они будут
масштабироваться приблизительно как n^(1.58), но это игнорируется в текущем
обсуждении. Обратите внимание, что 64-битные процессоры отодвигают число
«точки перехода Карацубы» к ещё большему числу битов.
Основной результат таков: если удвоить размер группы модульного возведения
в степень Diffie-Hellman, число операций, необходимых для вычисления,
увеличится в четыре раза.
3.1.1. Diffie-Hellman с группами эллиптических кривых
Обратите внимание, что соотношения вычислительных усилий как функции
размера модуля сохраняются даже при использовании группы на
эллиптической кривой (EC) для Diffie-Hellman. Однако при эквивалентной
безопасности в случае эллиптических кривых можно использовать меньшие
числа. Предположим, что кто-то выбрал группу модульного возведения в
степень с 2048-битным модулем как надлежащую меру безопасности для
приложения Diffie-Hellman и хочет определить, какое преимущество дало
бы использование вместо этого группы EC. Вычисление относительно
прямолинейно, если предположить, что в среднем выполнение возведения в
квадрат или умножения в группе EC требует примерно в 20 раз больше
усилий, чем в группе модульного возведения в степень. Грубая оценка
состоит в том, что группа EC с эквивалентной безопасностью имеет в
своём представлении около 200 бит. Тогда, предполагая, что время
определяется главным образом операциями над словами n-на-n, относительное
время вычисляется как:
((2048/200)^2)/20 ~= 5
что показывает, что реализация на эллиптической кривой должна быть в
пять раз быстрее реализации модульного возведения в степень.
3.2. Шифрование и расшифрование RSA
Предположим, что открытый ключ RSA использует модуль из j бит; его
множителями являются два числа примерно по j/2 бит каждое. Ожидаемое
время вычислений для шифрования и расшифрования различно. Как и ранее,
обозначим число слов в машинном представлении модуля символом n.
В большинстве реализаций RSA для шифрования используется малый
показатель степени. Шифрование может включать всего 16 возведений в
квадрат и одно умножение с использованием операций над словами n-на-n.
За каждой операцией должно следовать приведение по модулю, и поэтому
временная сложность составляет примерно 16*(.6 + 1) + 1 + 1 ~= 28
умножений слов n-на-n.
При расшифровании RSA должен использоваться показатель степени с таким
же числом бит, что и модуль, j. Однако применяется Китайская теорема об
остатках, и все вычисления могут выполняться с модулем всего из n/2
слов и показателем степени всего из j/2 бит. Вычисление должно быть
выполнено дважды, по одному разу для каждого множителя. Усилия
эквивалентны 2*(j/2) умножениям слов (n/2-на-n/2). Поскольку умножение
чисел из n/2 слов лишь на 1/4 столь же трудно, как умножение чисел из n
слов, эквивалентные усилия для расшифрования RSA составляют j/4
умножений слов n-на-n.
Если удвоить размер модуля для RSA, умножения n-на-n будут занимать в
четыре раза больше времени. Кроме того, время расшифрования удваивается,
поскольку показатель степени больше. Общая стоимость масштабирования
составляет коэффициент 4 для шифрования и коэффициент 8 для
расшифрования.
3.3. Примеры из реального мира
Чтобы сделать эти числа более наглядными, ниже приведены несколько
примеров программных реализаций, запущенных на аппаратуре, которая была
современной за несколько лет до публикации этого документа. Примеры
включены для демонстрации грубых оценок разумных реализаций; они не
являются эталонными тестами. Как и для любого программного обеспечения,
производительность будет зависеть от точных деталей специализации кода
под задачу и конкретной аппаратуры.
Наилучшее неофициально сообщённое время для 1024-битного модульного
возведения в степень (сторона расшифрования 2048-битного RSA) составляет
0.9 мс (около 450 000 тактов CPU) на процессоре Itanium 500 МГц. Это
показывает, что более новые процессоры не уступают в операциях с
большими числами; число инструкций меньше, чем 32-битный процессор
использует для 256-битного модульного возведения в степень.
Для менее совершенных процессоров приведены временные показатели в
следующих двух таблицах (вычислены Tero Monenen в SSH Communications)
для модульного возведения в степень, каковое выполнялось бы при обмене
ключами Diffie-Hellman.
Celeron 400 МГц; скомпилировано компилятором GNU C, оптимизировано,
применены некоторые оптимизации кода, специфичные для платформы:
group modulus exponent time
type size size
mod 768 ~150 18 msec
mod 1024 ~160 32 msec
mod 1536 ~180 82 msec
ecn 155 ~150 35 msec
ecn 185 ~200 56 msec
Тип группы взят из [RFC2409] и представляет собой либо модульное
возведение в степень ("mod"), либо эллиптическую кривую ("ecn"). Все
размеры здесь и в последующих таблицах указаны в битах.
Alpha 500 МГц, скомпилировано компилятором C компании Digital,
оптимизировано, без кода, специфичного для платформы:
group modulus exponent time
type size size
mod 768 ~150 12 msec
mod 1024 ~160 24 msec
mod 1536 ~180 59 msec
ecn 155 ~150 20 msec
ecn 185 ~200 27 msec
Следующие две таблицы (вычислены Eric Young) первоначально относились к
операциям подписания RSA с использованием представления по Китайской
теореме об остатках. Для облегчения понимания параметры представлены
здесь так, чтобы показать внутренние вычисления, то есть размер модуля
и показателя степени, используемых программным обеспечением.
Dual Pentium II-350:
equiv equiv equiv
modulus exponent time
size size
256 256 1.5 ms
512 512 8.6 ms
1024 1024 55.4 ms
2048 2048 387 ms
Alpha 264 600mhz:
equiv equiv equiv
modulus exponent time
size size
512 512 1.4 ms
Современные микросхемы, ускоряющие возведение в степень, могут выполнять
1024-битные возведения в степень (1024-битный модуль, 1024-битный
показатель степени) примерно за 3 миллисекунды или меньше.
4. Эквивалентности размеров ключей
Чтобы определить, насколько сильный открытый ключ необходим для защиты
конкретного симметричного ключа, сначала необходимо определить, какие
усилия требуются для взлома симметричного ключа. Многие протоколы
безопасности Интернета требуют использования TripleDES для надёжного
симметричного шифрования, и ожидается, что в ближайшие годы в Интернете
будет принят Advanced Encryption Standard (AES). Поэтому здесь
рассматриваются эти два алгоритма. В этом разделе в иллюстративных
целях мы неявно будем предполагать, что требование безопасности системы
составляет 112 бит; это не означает, что рекомендуются 112 бит. В
действительности 112 бит, возможно, слишком много для любой практической
цели. Это значение используется для иллюстрации просто потому, что оно
является верхней границей стойкости TripleDES.
Если бы можно было просто определить число MYs, необходимое для взлома
TripleDES, задача вычисления размера открытого ключа эквивалентной
стойкости была бы простой. К сожалению, здесь это не так, поскольку
имеется много примеров специализированной для DES аппаратуры, которая
шифрует быстрее, чем DES в программном обеспечении на стандартном CPU.
Вместо этого необходимо определить эквивалентную стоимость для системы,
взламывающей TripleDES, и системы, взламывающей открытый ключ, защищающий
ключ TripleDES.
В 1998 году Electronic Frontier Foundation (EFF) построила машину для
взлома DES [GIL98] стоимостью US$130,000, которая могла проверять около
1e11 ключей DES в секунду (на проектирование машины были потрачены
дополнительные средства). Создатели машины полностью признают, что
машина оптимизирована не лучшим образом, и предполагается, что сумма
денег в десять раз больше, вероятно, могла бы создать машину примерно в
50 раз быстрее. Предполагая дальнейшую оптимизацию и исходя из того, что
система для проверки ключей TripleDES работает примерно так же быстро,
как система для проверки ключей DES, приблизительно US$1 million могли
бы проверять 5e12 ключей TripleDES в секунду.
На случай, если ваши противники значительно богаче EFF, вы можете
предположить, что у них есть US$1 trillion, достаточно для проверки
5e18 ключей в секунду. Полный перебор эффективного пространства
TripleDES из 2^112 ключей этой весьма дорогой системой занял бы около
1e15 секунд, или около 33 миллионов лет. (Обратите внимание, что такой
системе также потребовалось бы 2^60 байт RAM [MH81], которая в этом
расчёте считается бесплатной.) Это представляется излишне консервативным
значением. Однако, если скорости компьютерной логики будут продолжать
увеличиваться в соответствии с законом Мура (удваиваясь по скорости
каждые 1.5 года), то можно было бы ожидать, что примерно через 50 лет
вычисление можно будет завершить всего за один год. В иллюстративных
целях предполагается, что эта 50-летняя стойкость против триллионера
является минимальным требованием безопасности для набора приложений.
Если 112 бит стойкости к атаке является требованием безопасности системы,
то система обмена ключами для TripleDES должна иметь эквивалентную
сложность; то есть, если у атакующего есть US$1 trillion, вы хотите,
чтобы он потратил все свои деньги на покупку аппаратуры сегодня и знал,
что он «взломает» обмен ключами не менее чем за 33 миллиона лет.
(Очевидно, рациональный атакующий подождал бы около 45 лет, прежде чем
действительно тратить деньги, поскольку тогда он мог бы получить гораздо
лучшую аппаратуру, но все атакующие в равной мере выигрывают от такого
ожидания.)
Предполагается, что типичный CPU ПК всего нескольких лет давности
может выполнять более 500 MIPs и мог быть приобретён примерно за US$100
при покупке в количестве; таким образом, получается более 5 MIPs/US$.
И вновь, это число удваивается примерно каждые 18 месяцев. За один
триллион долларов США атакующий может получить 5e12 MIP-лет компьютерных
инструкций на этой аппаратуре недавнего поколения. Эта величина
используется в следующих оценках эквивалентных стоимостей взлома систем
обмена ключами.
4.1. Эквивалентность ключей против специализированной аппаратуры полного
перебора
Если атакующий-триллионер должен использовать обычные CPU для «взлома»
обмена ключами для 112-битного ключа за то же время, которое
специализированная машина тратит на поиск симметричного ключа полным
перебором, система обмена ключами должна использовать модуль
надлежащего большого размера. Предположим, что триллионер выполняет
5e12 MIPs инструкций в год. Используйте следующее уравнение для оценки
размера модуля, используемого с шифрованием RSA или обменом ключами DH:
5*10^33 = (6*10^-16)*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))
Приближённое решение этого уравнения для n даёт:
n = 10^(625) = 2^(2077)
Таким образом, при допущении сходных скоростей логики и текущей
эффективности решета числового поля модули примерно с 2100 битами будут
иметь примерно такую же стойкость к атаке, как 112-битный ключ TripleDES.
Это указывает, что шифрованию открытым ключом RSA следует использовать
модуль примерно с 2100 битами; для обмена ключами Diffie-Hellman можно
было бы использовать несколько меньший модуль, но это несущественная
разница.
4.2 Эквивалентность ключей против атаки полным перебором на обычных CPU
Альтернативный способ оценки предполагает, что у атакующего менее
трудное требование: он должен лишь «взломать» обмен ключами за меньшее
время, чем занял бы поиск симметричного ключа полным перебором с
помощью компьютеров общего назначения. Это сравнение «яблок с яблоками»,
поскольку оно предполагает, что атакующему достаточно получить
вычислительные ресурсы, пожертвованные для его усилий, а не построенные
за счёт личного или национального состояния. Модуль открытого ключа будет
больше, чем в 4.1, поскольку симметричный ключ будет жизнеспособен в
течение более длительного периода времени.
Предположим, что число инструкций CPU для шифрования блока материала с
помощью TripleDES равно 300. Оценочное число компьютерных инструкций для
взлома 112-битного ключа TripleDES:
300 * 2^112
= 1.6 * 10^(36)
= .02*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))
Приближённое решение этого уравнения для n даёт:
n = 10^(734) = 2^(2439)
Таким образом, для атак на CPU общего назначения можно предположить, что
модули примерно с 2400 битами будут иметь примерно такую же стойкость к
атаке, как 112-битный ключ TripleDES. Это указывает, что шифрованию
открытым ключом RSA следует использовать модуль примерно с 2400 битами;
для обмена ключами Diffie-Hellman можно было бы использовать несколько
меньший модуль, но это несущественная разница.
Обратите внимание, что некоторые авторы предполагают, что алгоритмы,
лежащие в основе решета числового поля, со временем будут продолжать
улучшаться. Эти авторы рекомендуют ещё больший модуль, более 4000 бит,
для защиты 112-битного симметричного ключа в течение 50 лет. Это
указывает на трудность долговременной криптографической безопасности:
практически невозможно предсказать прогресс в математике и физике за
столь длительный период времени.
4.3. Однолетняя атака: 80 бит стойкости
Если предположить, что триллионер тратит свои деньги сегодня на покупку
аппаратуры, числа какого размера для обмена ключами он мог бы «взломать»
за один год? Он может выполнить 5*e12 MYs инструкций, или
3*10^13 * 5*10^12 = .02*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))
Приближённое решение для n даёт
n = 10^(360) = 2^(1195)
Это примерно столько же операций, сколько потребовалось бы для взлома
80-битного симметричного ключа полным перебором.
Таким образом, для защиты данных, к которым предъявляется требование
секретности в течение одного года против невероятно богатого атакующего,
модуль обмена ключами примерно с 1200 битами, защищающий 80-битный
симметричный ключ, безопасен даже против ресурсов государства.
4.4. Эквивалентность ключей для других шифров
Распространить эту логику на AES несложно. Для целей оценки перебора ключей 128-битный AES можно считать как минимум на 16 бит более стойким, чем TripleDES, но примерно в три раза более быстрым.
Время и стоимость атаки полным перебором приблизительно в
2^(16) раз больше, чем для TripleDES, и, следовательно, при допущении,
что желаемой целью безопасности является стойкость 128 бит,
рекомендуемый размер модуля обмена ключами примерно на 700 бит больше.
Если возможно разработать аппаратное обеспечение для взлома AES,
значительно более эффективное, чем аппаратное обеспечение для взлома DES,
то (снова при допущении, что стойкость обмена ключами должна соответствовать
усилиям полного перебора) модули для защиты обмена ключами можно сделать
меньше. Однако существование таких разработок на этом раннем этапе
существования AES является лишь предметом предположений.
Шифры AES имеют размеры ключей от 128 до 256 бит. Должно ли
благоразумное минимальное требование безопасности и, следовательно, модули
обмена ключами иметь аналогичную стойкость? Ответ на это зависит от того,
ожидает ли [sic] кто-либо, что закон Мура продолжит действовать
беспрепятственно. Если он продолжит действовать, можно было бы ожидать,
что 128-битные ключи будут безопасны около 60 лет, а 256-битные ключи будут
безопасны ещё 400 лет сверх этого, что намного превышает любое мыслимое
требование безопасности. Но такой прогресс трудно предсказать, поскольку
он превосходит физические возможности современных устройств и подразумевал
бы существование технологий логики, которые сегодня неизвестны или
неосуществимы. Квантовые вычисления — один из кандидатов, но сегодня о них
известно слишком мало, чтобы уверенно предсказывать их применимость к
криптографии (которая сама может измениться в следующие 100 лет!).
Если закон Мура не продолжит действовать, если не возникнут новые
вычислительные парадигмы, то ключи длиной более 100 бит вполне могут быть
безопасны «навсегда». Однако обратите внимание, что другие предложили оценки,
основанные на допущениях о возникновении новых вычислительных парадигм.
Например, веб-статья Lenstra и Verheul «Selecting Cryptographic Key Sizes»
выбирает более консервативный анализ, чем использованный в этом документе.
4.5. Хеш-функции для получения симметричных ключей из алгоритмов
с открытым ключом
Алгоритм Diffie-Hellman даёт ключ длиной в сотни или тысячи бит, но шифрам
требуется значительно меньше бит. Как можно преобразовать длинный ключ в
короткий, не теряя стойкости?
Криптографические однонаправленные хеш-функции являются строительными
блоками для этого, и, пока они используют весь ключ Diffie-Hellman для
получения каждого блока симметричного ключа, они создают ключи достаточной
стойкости.
Обычная рекомендация состоит в том, чтобы использовать хорошую
однонаправленную хеш-функцию, применённую к «he базовому материалу» [sic]
(результату обмена ключами), и использовать подмножество вывода хеш-функции
в качестве ключа. Однако если желаемая длина ключа больше вывода хеш-функции,
может возникнуть вопрос, как согласовать эти два значения.
Шаг получения дополнительных битов ключа должен удовлетворять следующим
требованиям:
- Биты не должны раскрывать какую-либо информацию о секрете обмена
ключами
- Биты не должны коррелировать друг с другом
- Биты должны зависеть от всех битов секрета обмена ключами
Любая хорошая криптографическая хеш-функция удовлетворяет этим трём
требованиям. Обратите внимание, что число битов вывода хеш-функции не
задано. Это потому, что даже хеш-функцию с очень коротким выводом можно
итерировать, чтобы получить больше некоррелированных битов, приложив лишь
немного осторожности.
Например, SHA-1 имеет вывод длиной 160 бит. Для получения ключа со
стойкостью к атаке 160 бит или меньше SHA(DHkey) создаёт хороший
симметричный ключ.
Предположим, требуется ключ со стойкостью к атаке 160 бит, но он должен
использоваться с шифром, использующим 192-битные ключи. SHA-1 можно
итерировать следующим образом:
Bits 1-160 of the symmetric key = K1 = SHA(DHkey | 0x00)
(то есть присоединить один октет со значением 0x00 к
правой стороне DHkey, а затем хешировать)
Bits 161-192 of the symmetric key = K2 =
select_32_bits(SHA(K1 | 0x01))
Но что, если для шифра требуется 192 бита стойкости? Тогда подходящее
вычисление таково:
Bits 1-160 of the symmetric key = SHA(0x00 | DHkey)
Bits 161-192 of the symmetric key =
select_32_bits(SHA(0x01 | DHkey))
(Обратите внимание, что в описании выше вместо конкатенации полного октета
также было бы достаточно конкатенации одного бита.)
Важное различие состоит в том, что во втором случае ключ DH
используется для каждой части симметричного ключа. Это обеспечивает,
что энтропия ключа DH не теряется вследствие итерации хеш-функции над
одними и теми же битами.
С точки зрения эффективности, если симметричный ключ должен иметь
большую энтропию, вероятно, лучше использовать криптографическую
хеш-функцию с большим блоком вывода (192 бита или более), а не итерировать
меньшую.
Более новые алгоритмы хеширования с более длинным выводом (такие как
SHA-256, SHA-384 и SHA-512) можно использовать с тем же уровнем
безопасности, что и алгоритм растяжения, описанный выше.
4.6. Важность случайности
Некоторые из вычислений, описанных в этом документе, требуют случайных
входных данных; например, секретные экспоненты Diffie-Hellman должны
выбираться на основе n действительно случайных битов (где n — требование
безопасности системы). Число действительно случайных битов чрезвычайно
важно для определения стойкости результата вычислений. Использование
действительно случайных чисел часто упускается из виду, и многие приложения
безопасности были существенно ослаблены использованием недостаточных
случайных входных данных. Гораздо более полное описание важности случайных
чисел можно найти в [ECS].
5. Заключение
В этой таблице предполагается, что атакующие используют компьютеры общего
назначения, что аппаратное обеспечение приобретено в 2000 году и что
математические знания, относящиеся к проблеме, остаются такими же, как
сегодня. Это чистое [sic] сравнение «яблок с яблоками», демонстрирующее,
как время обмена ключами масштабируется относительно требования к стойкости.
Размер подгруппы для DSA включён, если DSA используется для поддержки
аутентификации как часть протокола; модуль DSA должен быть таким же длинным,
как модуль DH, но размер подгруппы «q» также имеет значение.
+-------------+-----------+--------------+--------------+
| Системное | | | |
| требование | Симметрич-| Размер модуля| Размер |
| стойкости к | ного ключа| RSA или DH | подгруппы DSA|
| атаке | (биты) | (биты) | (биты) |
| (биты) | | | |
+-------------+-----------+--------------+--------------+
| 70 | 70 | 947 | 129 |
| 80 | 80 | 1228 | 148 |
| 90 | 90 | 1553 | 167 |
| 100 | 100 | 1926 | 186 |
| 150 | 150 | 4575 | 284 |
| 200 | 200 | 8719 | 383 |
| 250 | 250 | 14596 | 482 |
+-------------+-----------+--------------+--------------+
5.1. Поправка TWIRL
Если машина TWIRL станет реальностью и если появятся достижения в
параллелизме для сокращения строк при факторизации, то консервативные
оценки вычтут около 11 битов из столбца безопасности системы таблицы.
Таким образом, чтобы получить 89 битов безопасности, потребовался бы
модуль RSA размером около 1900 битов.
6. Соображения безопасности
Уравнения и значения, приведённые в этом документе, призваны быть настолько
точными, насколько возможно, на основе современного состояния компьютеров
общего назначения во время написания этого документа. Никакие прогнозы не
могут быть совершенно точными, и приведённые здесь формулы не предназначены
быть окончательными утверждениями факта о криптографической стойкости.
Например, некоторые эмпирические результаты, используемые при калибровке
формул в этом документе, вероятно, не вполне точны, и эта неточность влияет
на оценки. Авторы надеются, что представленные здесь числа будут отличаться
от опыта реального мира как можно меньше.
7.1. Информационные ссылки
[DL] Dodson, B. and A. K. Lenstra, NFS with four large primes:
an explosive experiment, Proceedings Crypto 95, Lecture
Notes in Comput. Sci. 963, (1995) 372-385.
[ECS] Eastlake, D., Crocker, S. and J. Schiller, "Randomness
Recommendations for Security", RFC 1750, December 1994.
[GIL98] Cracking DES: Secrets of Encryption Research, Wiretap
Politics & Chip Design , Electronic Frontier Foundation,
John Gilmore (Ed.), 272 pages, May 1998, O'Reilly &
Associates; ISBN: 1565925203
[GOR93] Gordon, D., "Discrete logarithms in GF(p) using the
number field sieve", SIAM Journal on Discrete
Mathematics, 6 (1993), 124-138.
[LEN93] Lenstra, A. K. and H. W. Lenstra, Jr. (eds), The
development of the number field sieve, Lecture Notes in
Math, 1554, Springer Verlag, Berlin, 1993.
[MH81] Merkle, R.C., and Hellman, M., "On the Security of
Multiple Encryption", Communications of the ACM, v. 24 n.
7, 1981, pp. 465-467.
[ODL95] RSA Labs Cryptobytes, Volume 1, No. 2 - Summer 1995; The
Future of Integer Factorization, A. M. Odlyzko
[ODL99] A. M. Odlyzko, Discrete logarithms: The past and the
future, Designs, Codes, and Cryptography (1999).
[POL78] J. Pollard, "Monte Carlo methods for index computation
mod p", Mathematics of Computation, 32 (1978), 918-924.
[RFC2409] Harkins, D. and D. Carrel, "The Internet Key Exchange
(IKE)", RFC 2409, November 1998.
[SCH95] R. Schroeppel, et al., Fast Key Exchange With Elliptic
Curve Systems, In Don Coppersmith, editor, Advances in
Cryptology -- CRYPTO 31 August 1995. Springer-Verlag
[SHAMIR03] Shamir, Adi and Eran Tromer, "Factoring Large Numbers
with the TWIRL Device", Advances in Cryptology - CRYPTO
2003, Springer, Lecture Notes in Computer Science 2729.
[SIL00] R. D. Silverman, RSA Laboratories Bulletin, Number 13 -
April 2000, A Cost-Based Security Analysis of Symmetric
and Asymmetric Key Lengths
[SILIEEE99] R. D. Silverman, "The Mythical MIPS Year", IEEE Computer,
August 1999.
8. Адреса авторов
Hilarie Orman
Purple Streak Development
500 S. Maple Dr.
Salem, UT 84653
EMail: hilarie@purplestreak.com and ho@alum.mit.edu
Paul Hoffman
VPN Consortium
127 Segre Place
Santa Cruz, CA 95060 USA
EMail: paul.hoffman@vpnc.org
9. Полное заявление об авторских правах
Copyright (C) The Internet Society (2004). Этот документ регулируется
правами, лицензиями и ограничениями, содержащимися в BCP 78, и, за
исключением предусмотренного в нём, авторы сохраняют все свои права.
Этот документ и содержащаяся в нём информация предоставляются на условиях
«КАК ЕСТЬ», И УЧАСТНИК, ОРГАНИЗАЦИЯ, КОТОРУЮ ОН/ОНА ПРЕДСТАВЛЯЕТ ИЛИ КОТОРОЙ
СПОНСИРУЕТСЯ (ЕСЛИ ТАКОВАЯ ИМЕЕТСЯ), THE INTERNET SOCIETY И THE INTERNET
ENGINEERING TASK FORCE ОТКАЗЫВАЮТСЯ ОТ ВСЕХ ЯВНЫХ ИЛИ ПОДРАЗУМЕВАЕМЫХ
ГАРАНТИЙ, ВКЛЮЧАЯ, ПОМИМО ПРОЧЕГО, ЛЮБУЮ ГАРАНТИЮ ТОГО, ЧТО ИСПОЛЬЗОВАНИЕ
СОДЕРЖАЩЕЙСЯ ЗДЕСЬ ИНФОРМАЦИИ НЕ НАРУШИТ НИКАКИХ ПРАВ, ИЛИ ЛЮБЫЕ
ПОДРАЗУМЕВАЕМЫЕ ГАРАНТИИ ТОВАРНОЙ ПРИГОДНОСТИ ИЛИ ПРИГОДНОСТИ ДЛЯ
КОНКРЕТНОЙ ЦЕЛИ.