Determining Strengths For Public Keys Used For Exchanging Symmetric Keys
RFC 3766 описывает согласованный выбор стойкости системы, симметричного ключа и открытого ключа при обмене симметрическими ключами. Документ объясняет оценку длины асимметрического ключа по требуемой стойкости симметрического ключа и приводит ориентировочные эквивалентности для RSA, Diffie-Hellman, DSA и эллиптических кривых. Рассматриваются стоимость атак факторизации и дискретного логарифмирования, влияние размеров параметров на время вычислений и роль случайности. Документ имеет статус BCP 86 и запрашивает обсуждение и предложения по улучшению.
Рабочая группа сети H. Orman
Запрос комментариев: 3766 Purple Streak Dev.
BCP: 86 P. Hoffman
Категория: Лучшая современная практика VPN Consortium
Апрель 2004
Определение уровней стойкости открытых ключей,
используемых для обмена симметричными ключами
Статус настоящей записки
Этот документ определяет Лучшую современную практику Интернета для
Интернет-сообщества и запрашивает обсуждение и предложения по
улучшениям. Распространение настоящей записки не ограничено.
Уведомление об авторском праве
Copyright (C) The Internet Society (2004). Все права защищены.
Аннотация
Разработчикам систем, использующих криптографию с открытым ключом для
обмена симметричными ключами, необходимо обеспечить устойчивость
открытых ключей к некоторому заранее определённому уровню атак. Этот
уровень устойчивости к атакам является стойкостью системы, и
симметричные ключи, которыми обмениваются, должны быть как минимум
столь же стойкими, как того требуют требования к стойкости системы.
Три величины — стойкость системы, стойкость симметричного ключа и
стойкость открытого ключа — должны быть согласованно сопоставлены для
любого использования сетевого протокола.
Хотя требования к стойкости системы довольно легко выразить в терминах
длины симметричного ключа и выбрать шифр с длиной ключа, равной этому
требованию или превышающей его, выбрать открытый ключ с криптографической
стойкостью, отвечающей требованию к стойкости симметричного ключа, труднее.
Этот документ объясняет, как определить длину асимметричного ключа как
функцию требования к стойкости симметричного ключа. Приведены некоторые
практические правила для оценки эквивалентной устойчивости к
крупномасштабным атакам на различные алгоритмы. В документе также
рассматривается, как изменение размеров базовых больших целых чисел
(модулей, размеров групп, показателей степени и т. д.) изменяет время
использования алгоритмов для обмена ключами.
Orman & Hoffman Лучшая современная практика [Страница 1]
RFC 3766 Определение уровней стойкости открытых ключей Апрель 2004
Содержание
1. Модель защиты симметричных ключей открытыми ключами. . . . . . 2
1.1. Алгоритмы обмена ключами . . . . . . . . . . . . . . . . 4
2. Определение трудозатрат на факторизацию . . . . . . . . . . . 5
2.1. Выбор параметров для уравнения. . . . . . . . . . . . . 6
2.2. Выбор k по эмпирическим отчётам . . . . . . . . . . . . 7
2.3. Ро-метод Полларда. . . . . . . . . . . . . . . . . . . 7
2.4. Ограничения большой памяти и множества машин. . . . . . 8
2.5. Машины специального назначения. . . . . . . . . . . . . 9
3. Время вычислений для алгоритмов. . . . . . . . . . . . . . . 10
3.1. Обмен ключами Диффи—Хеллмана . . . . . . . . . . . . . 10
3.1.1. Диффи—Хеллман с группами на эллиптических кривых. 11
3.2. Шифрование и расшифрование RSA . . . . . . . . . . . . 11
3.3. Примеры из реального мира . . . . . . . . . . . . . . . 12
4. Эквивалентности размеров ключей. . . . . . . . . . . . . . . 13
4.1. Эквивалентность ключей против аппаратуры специального
назначения для полного перебора. . . . . . . . . . . . . 15
4.2. Эквивалентность ключей против атаки полного перебора
на обычном CPU. . . . . . . . . . . . . . . . . . . . . 15
4.3. Однолетняя атака: 80 бит стойкости. . . . . . . . . . . 16
4.4. Эквивалентность ключей для других шифров . . . . . . . . 16
4.5. Хеш-функции для вывода симметричных ключей из алгоритмов
с открытым ключом. . . . . . . . . . . . . . . . . . . . 17
4.6. Важность случайности. . . . . . . . . . . . . . . . . . 19
5. Заключение . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.1. Поправка TWIRL. . . . . . . . . . . . . . . . . . . . . 20
6. Вопросы безопасности. . . . . . . . . . . . . . . . . . . . 20
7. Ссылки . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.1. Информационные ссылки. . . . . . . . . . . . . . . . . 20
8. Адреса авторов . . . . . . . . . . . . . . . . . . . . . . . 22
9. Полное заявление об авторском праве . . . . . . . . . . . . 23
1. Модель защиты симметричных ключей открытыми ключами
Во многих книгах по криптографии и безопасности объясняется необходимость
открытого обмена симметричными ключами, а также множество алгоритмов,
используемых для этой цели. Однако лишь немногие из этих обсуждений
объясняют, как соотносятся стойкости открытых и симметричных ключей.
Чтобы понять это, представьте дом с прочным замком на входной двери.
Рядом с входной дверью находится небольшой запираемый ящик, содержащий
ключ от входной двери. У потенциального взломщика, который хочет
проникнуть в дом через входную дверь, есть два варианта: атаковать замок
на входной двери или атаковать замок на ящике, чтобы извлечь ключ. Ясно,
что взломщику выгоднее атаковать более слабый из двух замков. В этой
ситуации владелец дома должен обеспечить,
Orman & Hoffman Лучшая современная практика [Страница 2]
RFC 3766 Определение уровней стойкости открытых ключей Апрель 2004
чтобы добавление второго варианта входа (ящика, содержащего ключ от
входной двери) было по меньшей мере столь же стойким, как замок на
входной двери, чтобы не облегчить взломщику задачу.
Разработчик, проектирующий систему обмена симметричными ключами с
использованием криптографии с открытым ключом, должен принять сходное
решение. Предположим, атакующий хочет узнать содержимое сообщения,
зашифрованного симметричным ключом, и что симметричный ключ был передан
между отправителем и получателем с использованием криптографии с
открытым ключом. У атакующего есть два варианта для восстановления
сообщения: попытка полного перебора для определения симметричного ключа
посредством повторного угадывания или математическое определение
закрытого ключа, используемого как ключ обмена ключами. Умный атакующий
будет работать над более лёгкой из этих двух задач.
Простой ответ на проблему разработчика состоит в том, чтобы обеспечить,
что система обмена ключами всегда значительно сильнее симметричного
ключа; этого можно добиться выбором очень длинного открытого ключа.
Такой проект обычно не является хорошей идеей, поскольку по мере
увеличения длины открытых ключей обмены ключами становятся значительно
дороже с точки зрения времени обработки. Поэтому перед разработчиком
стоит задача попытаться сопоставить сложность атаки на симметричный ключ
со сложностью атаки на шифрование с открытым ключом. Такой анализ не
нужен, если обмен ключами можно выполнять с исключительной безопасностью
почти без затрат с точки зрения прошедшего времени или усилий CPU; к
сожалению, сегодня это не так для методов с открытым ключом.
Третьим соображением является минимальное требование пользователя к
безопасности. Предположим, пользователь шифрует с помощью CAST-128 и
требует симметричный ключ со временем устойчивости к атаке полного
перебора в 20 лет. Он может начать с выбора ключа со случайными 86
битами, затем использовать одностороннюю функцию, такую как SHA-1, чтобы
«усилить» его до блока из 160 битов, а затем взять 128 из этих битов как
ключ для CAST-128. В таком случае алгоритм обмена ключами должен лишь
соответствовать сложности 86 битов, а не 128 битов.
Процедура выбора такова:
1. Определите устойчивость к атаке, необходимую для удовлетворения
требований безопасности приложения. Сделайте это, оценив минимальное
число компьютерных операций, которые атакующий будет вынужден
выполнить, чтобы скомпрометировать безопасность системы, а затем
возьмите логарифм этого числа по основанию два. Назовите это значение
логарифма «n».
Orman & Hoffman Лучшая современная практика [Страница 3]
RFC 3766 Определение уровней стойкости открытых ключей Апрель 2004
В отчёте 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].
Orman & Hoffman Лучшая современная практика [Страница 4]
RFC 3766 Определение уровней стойкости открытых ключей Апрель 2004
Для обмена ключами 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) является одна компьютерная
Orman & Hoffman Лучшая современная практика [Страница 5]
RFC 3766 Определение уровней стойкости открытых ключей Апрель 2004
инструкция. Эмпирические данные указывают, что более близким соответствием
могли бы быть 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].
Orman & Hoffman Лучшая современная практика [Страница 6]
RFC 3766 Определение стойкости открытых ключей Апрель 2004
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].
Orman & Hoffman Лучшая современная практика [Страница 7]
RFC 3766 Определение стойкости открытых ключей Апрель 2004
Когда обмен ключами Diffie-Hellman выполняется с использованием метода
эллиптических кривых, методы NFS бесполезны. Однако метод коллизий всё ещё
эффективен, и сохраняется потребность в показателе степени (называемом
множителем в EC) из 2*K бит. Модуль, используемый для вычисления, также
может иметь размер 2*K бит, и он будет существенно меньше модуля,
необходимого для методов модульного возведения в степень, по мере того как
желаемый уровень безопасности превышает стойкость к атаке перебором в 64
бита.
Можно спросить: как сравнить число компьютерных инструкций, действительно
необходимых для атаки на дискретный логарифм, с числом, необходимым для
перебора пространства ключей шифра? При сравнении усилий следует учитывать,
что представляет собой «базовая операция». Для перебора пространства ключей
алгоритма симметричного шифрования, такого как DES, базовая операция — это
время выполнения настройки ключа и время выполнения одного шифрования. Для
дискретных логарифмов базовая операция — модульное возведение в квадрат.
Логарифм отношения этих двух операций можно использовать как «нормирующий
коэффициент» между двумя видами вычислений. Однако даже для очень больших
модулей (16K бит) этот коэффициент составляет лишь несколько битов
дополнительных усилий.
2.4. Ограничения большой памяти и множества машин
Роберт Сильверман исследовал вопрос о том, когда станет практически
осуществимым разложение на множители модулей RSA размером более 512 бит.
Его анализ основан не только на теоретическом числе операций, но также
включает ожидания относительно доступности реальных машин для выполнения
работы (этот документ основан только на теоретическом числе операций). Он
рассматривает вопрос о том, можно ли ожидать достаточного количества машин,
памяти и средств связи для разложения на множители очень большого числа.
Наилучшим методам разложения на множители требуется много оперативной
памяти с произвольным доступом для сбора соотношений данных (просеивания)
и критический заключительный шаг, выполняющий приведение строк большой
матрицы. Требования к памяти связаны с размером числа, которое разлагается
на множители (или для которого решается задача дискретного логарифма).
Сильверман [SILIEEE99] [SIL00] утверждал, что в обозримом будущем существует
практический предел числа машин и объёма RAM, которые можно задействовать
для одной задачи. Он видит две проблемы в атаке на 1024-битный модуль RSA:
машины, выполняющие просеивание, будут нуждаться в 64-битных адресных
пространствах, а машине для приведения строк матрицы потребуется несколько
терабайтов памяти. Сильверман отмечает, что было продано очень мало
64-битных машин,
Orman & Hoffman Лучшая современная практика [Страница 8]
RFC 3766 Определение стойкости открытых ключей Апрель 2004
имеющих 170 гигабайт памяти, необходимой для просеивания. Для просеивания
за разумное время (год или два) необходимо почти миллиард таких машин.
Вывод Сильвермана, основанный на истории усилий по разложению на множители
и законе Мура, состоит в том, что 1024-битные модули RSA не будут разложены
на множители примерно до 2037 года. Это подразумевает гораздо более долгий
срок жизни ключей RSA, чем указывает теоретический анализ. Он утверждает,
что на основе экстраполяций закона Мура и недавней истории усилий по
разложению на множители можно с большой уверенностью предсказывать, сколько
машин и модулей памяти будет доступно.
Практическим соображениям следует придавать большой вес, но при анализе
риска физический мир менее предсказуем, чем показывали бы графики трендов.
Рассматривая, насколько можно доверять неспособности компьютерной индустрии
удовлетворить ненасытные потребности факторизаторов, необходимо иметь
некоторое представление об экономических соображениях, которые сложнее
математики разложения на множители. Спрос на компьютерную память трудно
предсказать, поскольку он основан на приложениях: «убийственное приложение»
может появиться в любой день и привести индустрию памяти к лихорадке продаж.
Число доступных процессоров в настольных системах может быть ограничено
числом столов, но очень мощные встроенные системы обеспечивают больше продаж
процессоров, чем настольные системы. По мере того как встроенные системы
поглощают сетевые функции, нельзя считать немыслимым, что миллионы
64-битных процессоров по меньшей мере с гигабайтами памяти распространятся
в нашей среде.
Суть в том, что рекомендации по длине ключей, предсказываемые теорией,
могут быть чрезмерно консервативными, но именно их мы использовали в этом
документе. Этот вопрос доступности машин следует регулярно пересматривать
с учётом текущей технологии.
2.5. Машины специального назначения
В августе 2003 года появился проект специализированной «машины для
просеивания» (TWIRL) [Shamir2003], и он существенно изменил оценки стоимости
разложения на множители чисел размером до 1024 бит. При параллельном
применении множества высокоскоростных компонентов VLSI такая машина могла
бы выполнить просеивание 512-битных чисел за 10 минут при стоимости
аппаратуры $10K. Более крупная версия могла бы выполнить просеивание
1024-битного числа за один год при стоимости $10M. В работе приводятся
некоторые усовершенствования подходов к шагу приведения строк матрицы, на
основании которых делается вывод, что безопасность 1024-битных модулей RSA
вызывает сомнения.
Оценки времени и стоимости разложения на множители 512-битных и 1024-битных
чисел соответствуют коэффициенту ускорения примерно в 2 миллиона раз по
сравнению с тем, что можно было достичь на массовых процессорах нескольких
лет назад.
Orman & Hoffman Лучшая современная практика [Страница 9]
RFC 3766 Определение стойкости открытых ключей Апрель 2004
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-битные процессоры отодвигают число
«точки перехода Карацубы» к ещё большему числу битов.
Orman & Hoffman Лучшая современная практика [Страница 10]
RFC 3766 Определение стойкости открытых ключей Апрель 2004
Основной результат таков: если удвоить размер группы модульного возведения
в степень 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.
Orman & Hoffman Лучшая современная практика [Страница 11]
RFC 3766 Determining Strengths for Public Keys Апрель 2004
Если удвоить размер модуля для 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"). Все
размеры здесь и в последующих таблицах указаны в битах.
Orman & Hoffman Лучшая современная практика [Страница 12]
RFC 3766 Determining Strengths for Public Keys Апрель 2004
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). Поэтому здесь
рассматриваются эти два алгоритма. В этом разделе в иллюстративных
целях мы неявно будем предполагать, что требование безопасности системы
Orman & Hoffman Лучшая современная практика [Страница 13]
RFC 3766 Determining Strengths for Public Keys Апрель 2004
составляет 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 лет, прежде чем
действительно тратить деньги, поскольку тогда он мог бы получить гораздо
лучшую аппаратуру, но все атакующие в равной мере выигрывают от такого
ожидания.)
Orman & Hoffman Лучшая современная практика [Страница 14]
RFC 3766 Determining Strengths for Public Keys Апрель 2004
Предполагается, что типичный 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:
Orman & Hoffman Лучшая современная практика [Страница 15]
RFC 3766 Determining Strengths for Public Keys Апрель 2004
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, но примерно в три раза более быстрым.
Orman & Hoffman Лучшая современная практика [Страница 16]
RFC 3766 Определение стойкости открытых ключей Апрель 2004
Время и стоимость атаки полным перебором приблизительно в
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 для
получения каждого блока симметричного ключа, они создают ключи достаточной
стойкости.
Orman & Hoffman Лучшая современная практика [Страница 17]
RFC 3766 Определение стойкости открытых ключей Апрель 2004
Обычная рекомендация состоит в том, чтобы использовать хорошую
однонаправленную хеш-функцию, применённую к «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))
(Обратите внимание, что в описании выше вместо конкатенации полного октета
также было бы достаточно конкатенации одного бита.)
Orman & Hoffman Лучшая современная практика [Страница 18]
RFC 3766 Определение стойкости открытых ключей Апрель 2004
Важное различие состоит в том, что во втором случае ключ DH
используется для каждой части симметричного ключа. Это обеспечивает,
что энтропия ключа DH не теряется вследствие итерации хеш-функции над
одними и теми же битами.
С точки зрения эффективности, если симметричный ключ должен иметь
большую энтропию, вероятно, лучше использовать криптографическую
хеш-функцию с большим блоком вывода (192 бита или более), а не итерировать
меньшую.
Более новые алгоритмы хеширования с более длинным выводом (такие как
SHA-256, SHA-384 и SHA-512) можно использовать с тем же уровнем
безопасности, что и алгоритм растяжения, описанный выше.
4.6. Важность случайности
Некоторые из вычислений, описанных в этом документе, требуют случайных
входных данных; например, секретные экспоненты Diffie-Hellman должны
выбираться на основе n действительно случайных битов (где n — требование
безопасности системы). Число действительно случайных битов чрезвычайно
важно для определения стойкости результата вычислений. Использование
действительно случайных чисел часто упускается из виду, и многие приложения
безопасности были существенно ослаблены использованием недостаточных
случайных входных данных. Гораздо более полное описание важности случайных
чисел можно найти в [ECS].
5. Заключение
В этой таблице предполагается, что атакующие используют компьютеры общего
назначения, что аппаратное обеспечение приобретено в 2000 году и что
математические знания, относящиеся к проблеме, остаются такими же, как
сегодня. Это чистое [sic] сравнение «яблок с яблоками», демонстрирующее,
как время обмена ключами масштабируется относительно требования к стойкости.
Размер подгруппы для DSA включён, если DSA используется для поддержки
аутентификации как часть протокола; модуль DSA должен быть таким же длинным,
как модуль DH, но размер подгруппы «q» также имеет значение.
Orman & Hoffman Лучшая современная практика [Страница 19]
RFC 3766 Определение стойкости открытых ключей Апрель 2004
+-------------+-----------+--------------+--------------+
| Системное | | | |
| требование | Симметрич-| Размер модуля| Размер |
| стойкости к | ного ключа| 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. Ссылки
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.
Orman & Hoffman Лучшая современная практика [Страница 20]
RFC 3766 Определение стойкости открытых ключей Апрель 2004
[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.
Orman & Hoffman Лучшая современная практика [Страница 21]
RFC 3766 Определение стойкости открытых ключей Апрель 2004
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
Orman & Hoffman Лучшая современная практика [Страница 22]
RFC 3766 Определение стойкости открытых ключей Апрель 2004
9. Полное заявление об авторских правах
Copyright (C) The Internet Society (2004). Этот документ регулируется
правами, лицензиями и ограничениями, содержащимися в BCP 78, и, за
исключением предусмотренного в нём, авторы сохраняют все свои права.
Этот документ и содержащаяся в нём информация предоставляются на условиях
«КАК ЕСТЬ», И УЧАСТНИК, ОРГАНИЗАЦИЯ, КОТОРУЮ ОН/ОНА ПРЕДСТАВЛЯЕТ ИЛИ КОТОРОЙ
СПОНСИРУЕТСЯ (ЕСЛИ ТАКОВАЯ ИМЕЕТСЯ), THE INTERNET SOCIETY И THE INTERNET
ENGINEERING TASK FORCE ОТКАЗЫВАЮТСЯ ОТ ВСЕХ ЯВНЫХ ИЛИ ПОДРАЗУМЕВАЕМЫХ
ГАРАНТИЙ, ВКЛЮЧАЯ, ПОМИМО ПРОЧЕГО, ЛЮБУЮ ГАРАНТИЮ ТОГО, ЧТО ИСПОЛЬЗОВАНИЕ
СОДЕРЖАЩЕЙСЯ ЗДЕСЬ ИНФОРМАЦИИ НЕ НАРУШИТ НИКАКИХ ПРАВ, ИЛИ ЛЮБЫЕ
ПОДРАЗУМЕВАЕМЫЕ ГАРАНТИИ ТОВАРНОЙ ПРИГОДНОСТИ ИЛИ ПРИГОДНОСТИ ДЛЯ
КОНКРЕТНОЙ ЦЕЛИ.
Интеллектуальная собственность
IETF не занимает позиции относительно действительности или объёма каких-либо
прав интеллектуальной собственности либо иных прав, которые могут быть
заявлены как относящиеся к реализации или использованию технологии,
описанной в этом документе, или относительно степени, в которой какая-либо
лицензия по таким правам может быть или не быть доступной; также она не
заявляет, что предприняла какие-либо независимые усилия по выявлению таких
прав. Информацию о процедурах в отношении прав в документах RFC можно найти
в BCP 78 и BCP 79. Копии раскрытий IPR, направленных в Секретариат IETF, и любых
заверений о лицензиях, которые будут предоставлены, либо результат
попытки получить общую лицензию или разрешение на использование
таких прав собственности разработчиками или пользователями этой
спецификации можно получить в онлайновом репозитории IPR IETF по
адресу http://www.ietf.org/ipr.
IETF предлагает любой заинтересованной стороне доводить до его
сведения любые авторские права, патенты или патентные заявки либо
иные права собственности, которые могут охватывать технологию,
которая может потребоваться для реализации этого стандарта.
Пожалуйста, направляйте информацию в IETF по адресу
ietf-ipr@ietf.org.
Благодарности
Финансирование функции RFC Editor в настоящее время предоставляется
Internet Society.
Orman & Hoffman Лучшая современная практика [Страница 23]
Network Working Group H. Orman
Request for Comments: 3766 Purple Streak Dev.
BCP: 86 P. Hoffman
Category: Best Current Practice VPN Consortium
April 2004
Determining Strengths For Public Keys Used
For Exchanging Symmetric Keys
Status of this Memo
This document specifies an Internet Best Current Practices for the
Internet Community, and requests discussion and suggestions for
improvements. Distribution of this memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2004). All Rights Reserved.
Abstract
Implementors of systems that use public key cryptography to exchange
symmetric keys need to make the public keys resistant to some
predetermined level of attack. That level of attack resistance is
the strength of the system, and the symmetric keys that are exchanged
must be at least as strong as the system strength requirements. The
three quantities, system strength, symmetric key strength, and public
key strength, must be consistently matched for any network protocol
usage.
While it is fairly easy to express the system strength requirements
in terms of a symmetric key length and to choose a cipher that has a
key length equal to or exceeding that requirement, it is harder to
choose a public key that has a cryptographic strength meeting a
symmetric key strength requirement. This document explains how to
determine the length of an asymmetric key as a function of a
symmetric key strength requirement. Some rules of thumb for
estimating equivalent resistance to large-scale attacks on various
algorithms are given. The document also addresses how changing the
sizes of the underlying large integers (moduli, group sizes,
exponents, and so on) changes the time to use the algorithms for key
exchange.
Orman & Hoffman Best Current Practice [Page 1]
RFC 3766 Determining Strengths for Public Keys April 2004
Table of Contents
1. Model of Protecting Symmetric Keys with Public Keys. . . . . . 2
1.1. The key exchange algorithms . . . . . . . . . . . . . . . 4
2. Determining the Effort to Factor . . . . . . . . . . . . . . . 5
2.1. Choosing parameters for the equation. . . . . . . . . . . 6
2.2. Choosing k from empirical reports . . . . . . . . . . . . 7
2.3. Pollard's rho method. . . . . . . . . . . . . . . . . . . 7
2.4. Limits of large memory and many machines. . . . . . . . . 8
2.5. Special purpose machines. . . . . . . . . . . . . . . . . 9
3. Compute Time for the Algorithms. . . . . . . . . . . . . . . . 10
3.1. Diffie-Hellman Key Exchange . . . . . . . . . . . . . . . 10
3.1.1. Diffie-Hellman with elliptic curve groups. . . . . 11
3.2. RSA encryption and decryption . . . . . . . . . . . . . . 11
3.3. Real-world examples . . . . . . . . . . . . . . . . . . . 12
4. Equivalences of Key Sizes. . . . . . . . . . . . . . . . . . . 13
4.1. Key equivalence against special purpose brute force
hardware. . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2. Key equivalence against conventional CPU brute force
attack. . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3. A One Year Attack: 80 bits of strength. . . . . . . . . . 16
4.4. Key equivalence for other ciphers . . . . . . . . . . . . 16
4.5. Hash functions for deriving symmetric keys from public
key algorithms. . . . . . . . . . . . . . . . . . . . . . 17
4.6. Importance of randomness. . . . . . . . . . . . . . . . . 19
5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.1. TWIRL Correction. . . . . . . . . . . . . . . . . . . . . 20
6. Security Considerations. . . . . . . . . . . . . . . . . . . . 20
7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.1. Informational References. . . . . . . . . . . . . . . . . 20
8. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 22
9. Full Copyright Statement . . . . . . . . . . . . . . . . . . . 23
1. Model of Protecting Symmetric Keys with Public Keys
Many books on cryptography and security explain the need to exchange
symmetric keys in public as well as the many algorithms that are used
for this purpose. However, few of these discussions explain how the
strengths of the public keys and the symmetric keys are related.
To understand this, picture a house with a strong lock on the front
door. Next to the front door is a small lockbox that contains the
key to the front door. A would-be burglar who wants to break into
the house through the front door has two options: attack the lock on
the front door, or attack the lock on the lockbox in order to
retrieve the key. Clearly, the burglar is better off attacking the
weaker of the two locks. The homeowner in this situation must make
Orman & Hoffman Best Current Practice [Page 2]
RFC 3766 Determining Strengths for Public Keys April 2004
sure that adding the second entry option (the lockbox containing the
front door key) is at least as strong as the lock on the front door,
in order not to make the burglar's job easier.
An implementor designing a system for exchanging symmetric keys using
public key cryptography must make a similar decision. Assume that an
attacker wants to learn the contents of a message that is encrypted
with a symmetric key, and that the symmetric key was exchanged
between the sender and recipient using public key cryptography. The
attacker has two options to recover the message: a brute-force
attempt to determine the symmetric key by repeated guessing, or
mathematical determination of the private key used as the key
exchange key. A smart attacker will work on the easier of these two
problems.
A simple-minded answer to the implementor's problem is to be sure
that the key exchange system is always significantly stronger than
the symmetric key; this can be done by choosing a very long public
key. Such a design is usually not a good idea because the key
exchanges become much more expensive in terms of processing time as
the length of the public keys go up. Thus, the implementor is faced
with the task of trying to match the difficulty of an attack on the
symmetric key with the difficulty of an attack on the public key
encryption. This analysis is not necessary if the key exchange can
be performed with extreme security for almost no cost in terms of
elapsed time or CPU effort; unfortunately, this is not the case for
public key methods today.
A third consideration is the minimum security requirement of the
user. Assume the user is encrypting with CAST-128 and requires a
symmetric key with a resistance time against brute-force attack of 20
years. He might start off by choosing a key with 86 random bits, and
then use a one-way function such as SHA-1 to "boost" that to a block
of 160 bits, and then take 128 of those bits as the key for CAST-128.
In such a case, the key exchange algorithm need only match the
difficulty of 86 bits, not 128 bits.
The selection procedure is:
1. Determine the attack resistance necessary to satisfy the security
requirements of the application. Do this by estimating the
minimum number of computer operations that the attacker will be
forced to do in order to compromise the security of the system and
then take the logarithm base two of that number. Call that
logarithm value "n".
Orman & Hoffman Best Current Practice [Page 3]
RFC 3766 Determining Strengths for Public Keys April 2004
A 1996 report recommended 90 bits as a good all-around choice for
system security. The 90 bit number should be increased by about
2/3 bit/year, or about 96 bits in 2005.
2. Choose a symmetric cipher that has a key with at least n bits and
at least that much cryptanalytic strength.
3. Choose a key exchange algorithm with a resistance to attack of at
least n bits.
A fourth consideration might be the public key authentication method
used to establish the identity of a user. This might be an RSA
digital signature or a DSA digital signature. If the modulus for the
authentication method isn't large enough, then the entire basis for
trusting the communication might fall apart. The following step is
thus added:
4. Choose an authentication algorithm with a resistance to attack of
at least n bits. This ensures that a similar key exchanged cannot
be forged between the two parties during the secrecy lifetime of
the encrypted material. This may not be strictly necessary if the
authentication keys are changed frequently and they have a well-
understood usage lifetime, but in lieu of this, the n bit guidance
is sound.
1.1. The key exchange algorithms
The Diffie-Hellman method uses a group, a generator, and exponents.
In today's Internet standards, the group operation is based on
modular multiplication. Here, the group is defined by the
multiplicative group of an integer, typically a prime p = 2q + 1,
where q is a prime, and the arithmetic is done modulo p; the
generator (which is often simply 2) is denoted by g.
In Diffie-Hellman, Alice and Bob first agree (in public or in
private) on the values for g and p. Alice chooses a secret large
random integer (a), and Bob chooses a secret random large integer
(b). Alice sends Bob A, which is g^a mod p; Bob sends Alice B, which
is g^b mod p. Next, Alice computes B^a mod p, and Bob computes A^b
mod p. These two numbers are equal, and the participants use a
simple function of this number as the symmetric key k.
Note that Diffie-Hellman key exchange can be done over different
kinds of group representations. For instance, elliptic curves
defined over finite fields are a particularly efficient way to
compute the key exchange [SCH95].
Orman & Hoffman Best Current Practice [Page 4]
RFC 3766 Determining Strengths for Public Keys April 2004
For RSA key exchange, assume that Bob has a public key (m) which is
equal to p*q, where p and q are two secret prime numbers, and an
encryption exponent e, and a decryption exponent d. For the key
exchange, Alice sends Bob E = k^e mod m, where k is the secret
symmetric key being exchanged. Bob recovers k by computing E^d mod
m, and the two parties use k as their symmetric key. While Bob's
encryption exponent e can be quite small (e.g., 17 bits), his
decryption exponent d will have as many bits in it as m does.
2. Determining the Effort to Factor
The RSA public key encryption method is immune to brute force
guessing attacks because the modulus (and thus, the secret exponent
d) will have at least 512 bits, and that is too many possibilities to
guess. The Diffie-Hellman exchange is also secure against guessing
because the exponents will have at least twice as many bits as the
symmetric keys that will be derived from them. However, both methods
are susceptible to mathematical attacks that determine the structure
of the public keys.
Factoring an RSA modulus will result in complete compromise of the
security of the private key. Solving the discrete logarithm problem
for a Diffie-Hellman modular exponentiation system will similarly
destroy the security of all key exchanges using the particular
modulus. This document assumes that the difficulty of solving the
discrete logarithm problem is equivalent to the difficulty of
factoring numbers that are the same size as the modulus. In fact, it
is slightly harder because it requires more operations; based on
empirical evidence so far, the ratio of difficulty is at least 20,
possibly as high as 64. Solving either problem requires a great deal
of memory for the last stage of the algorithm, the matrix reduction
step. Whether or not this memory requirement will continue to be the
limiting factor in solving larger integer problems remains to be
seen. At the current time it is not, and there is active research
into parallel matrix algorithms that might mitigate the memory
requirements for this problem.
The number field sieve (NFS) [GOR93] [LEN93] is the best method today
for solving the discrete logarithm problem. The formula for
estimating the number of simple arithmetic operations needed to
factor an integer, n, using the NFS method is:
L(n) = k * e^((1.92 + o(1)) * cubrt(ln(n) * (ln(ln(n)))^2))
Many people prefer to discuss the number of MIPS years (MYs) that are
needed for large operations such as the number field sieve. For such
an estimation, an operation in the L(n) formula is one computer
Orman & Hoffman Best Current Practice [Page 5]
RFC 3766 Determining Strengths for Public Keys April 2004
instruction. Empirical evidence indicates that 4 or 5 instructions
might be a closer match, but this is a minor factor and this document
sticks with one operation/one instruction for this discussion.
2.1. Choosing parameters for the equation
The expression above has two parameters that can be estimated by
empirical means: k and o(1). For the range of numbers we are
interested in, there is little distinction between them.
One could assume that k is 1 and o(1) is 0. This is reasonably valid
if the expression is only used for estimating relative effort
(instead of actual effort) and one assumes that the o(1) term is very
small over the range of the numbers that are to be factored.
Or, one could assume that o(1) is small and roughly constant and thus
its value can be folded into k; then estimate k from reported amounts
of effort spent factoring large integers in tests.
This document uses the second approach in order to get an estimate of
the significance of the factor. It appears to be minor, based on the
following calculations.
Sample values from recent work with the number field sieve include:
Test name Number of Number of MYs of effort
decimal bits
digits
RSA130 130 430 500
RSA140 140 460 2000
RSA155 155 512 8000
RSA160 160 528 3000
There are few precise measurements of the amount of time used for
these factorizations. In most factorization tests, hundreds or
thousands of computers are used over a period of several months, but
the number of their cycles were used for the factoring project, the
precise distribution of processor types, speeds, and so on are not
usually reported. However, in all the above cases, the amount of
effort used was far less than the L(n) formula would predict if k was
1 and o(1) was 0.
A similar estimate of effort, done in 1995, is in [ODL95].
Results indicating that for the Number Field Sieve factoring method,
the actual number of operations is less than expected, are found in
[DL].
Orman & Hoffman Best Current Practice [Page 6]
RFC 3766 Determining Strengths for Public Keys April 2004
2.2. Choosing k from empirical reports
By solving for k from the empirical reports, it appears that k is
approximately 0.02. This means that the "effective key strength" of
the RSA algorithm is about 5 or 6 bits less than is implied by the
naive application of equation L(n) (that is, setting k to 1 and o(1)
to 0). These estimates of k are fairly stable over the numbers
reported in the table. The estimate is limited to a single
significant digit of k because it expresses real uncertainties;
however, the effect of additional digits would have make only tiny
changes to the recommended key sizes.
The factorers of RSA130 used about 1700 MYs, but they felt that this
was unrealistically high for prediction purposes; by using more
memory on their machines, they could have easily reduced the time to
500 MYs. Thus, the value used in preparing the table above was 500.
This story does, however, underscore the difficulty in getting an
accurate measure of effort. This document takes the reported effort
for factoring RSA155 as being the most accurate measure.
As a result of examining the empirical data, it appears that the L(n)
formula can be used with the o(1) term set to 0 and with k set to
0.02 when talking about factoring numbers in the range of 100 to 200
decimal digits. The equation becomes:
L(n) = 0.02 * e^(1.92 * cubrt(ln(n) * (ln(ln(n)))^2))
To convert L(n) from simple math instructions to MYs, divide by
3*10^13. The equation for the number of MYs needed to factor an
integer n then reduces to:
MYs = 6 * 10^(-16) * e^(1.92 * cubrt(ln(n) * (ln(ln(n)))^2))
With what confidence can this formula be used for predicting the
difficulty of factoring slightly larger numbers? The answer is that
it should be a close upper bound, but each factorization effort is
usually marked by some improvement in the algorithms or their
implementations that makes the running time somewhat shorter than the
formula would indicate.
2.3. Pollard's rho method
In Diffie-Hellman exchanges, there is a second attack, Pollard's rho
method [POL78]. The algorithm relies on finding collisions between
values computed in a large number space; its success rate is
proportional to the square root of the size of the space. Because of
Pollard's rho method, the search space in a DH key exchange for the
key (the exponent in a g^a term), must be twice as large as the
Orman & Hoffman Best Current Practice [Page 7]
RFC 3766 Determining Strengths for Public Keys April 2004
symmetric key. Therefore, to securely derive a key of K bits, an
implementation must use an exponent with at least 2*K bits. See
[ODL99] for more detail.
When the Diffie-Hellman key exchange is done using an elliptic curve
method, the NFS methods are of no avail. However, the collision
method is still effective, and the need for an exponent (called a
multiplier in EC's) with 2*K bits remains. The modulus used for the
computation can also be 2*K bits, and this will be substantially
smaller than the modulus needed for modular exponentiation methods as
the desired security level increases past 64 bits of brute-force
attack resistance.
One might ask, how can you compare the number of computer
instructions really needed for a discrete logarithm attack to the
number needed to search the keyspace of a cipher? In comparing the
efforts, one should consider what a "basic operation" is. For brute
force search of the keyspace of a symmetric encryption algorithm like
DES, the basic operation is the time to do a key setup and the time
to do one encryption. For discrete logs, the basic operation is a
modular squaring. The log of the ratio of these two operations can
be used as a "normalizing factor" between the two kinds of
computations. However, even for very large moduli (16K bits), this
factor amounts to only a few bits of extra effort.
2.4. Limits of large memory and many machines
Robert Silverman has examined the question of when it will be
practical to factor RSA moduli larger than 512 bits. His analysis is
based not only on the theoretical number of operations, but it also
includes expectations about the availability of actual machines for
performing the work (this document is based only on theoretical
number of operations). He examines the question of whether or not we
can expect there be enough machines, memory, and communication to
factor a very large number.
The best factoring methods need a lot of random access memory for
collecting data relations (sieving) and a critical final step that
does a row reduction on a large matrix. The memory requirements are
related to the size of the number being factored (or subjected to
discrete logarithm solution). Silverman [SILIEEE99] [SIL00] has
argued that there is a practical limit to the number of machines and
the amount of RAM that can be brought to bear on a single problem in
the foreseeable future. He sees two problems in attacking a 1024-bit
RSA modulus: the machines doing the sieving will need 64-bit address
spaces and the matrix row reduction machine will need several
terabytes of memory. Silverman notes that very few 64-bit machines
Orman & Hoffman Best Current Practice [Page 8]
RFC 3766 Determining Strengths for Public Keys April 2004
that have the 170 gigabytes of memory needed for sieving have been
sold. Nearly a billion such machines are necessary for the sieving
in a reasonable amount of time (a year or two).
Silverman's conclusion, based on the history of factoring efforts and
Moore's Law, is that 1024-bit RSA moduli will not be factored until
about 2037. This implies a much longer lifetime to RSA keys than the
theoretical analysis indicates. He argues that predictions about how
many machines and memory modules will be available can be with great
confidence, based on Moore's Law extrapolations and the recent
history of factoring efforts.
One should give the practical considerations a great deal of weight,
but in a risk analysis, the physical world is less predictable than
trend graphs would indicate. In considering how much trust to put
into the inability of the computer industry to satisfy the voracious
needs of factorers, one must have some insight into economic
considerations that are more complicated than the mathematics of
factoring. The demand for computer memory is hard to predict because
it is based on applications: a "killer app" might come along any day
and send the memory industry into a frenzy of sales. The number of
processors available on desktops may be limited by the number of
desks, but very capable embedded systems account for more processor
sales than desktops. As embedded systems absorb networking
functions, it is not unimaginable that millions of 64-bit processors
with at least gigabytes of memory will pervade our environment.
The bottom line on this is that the key length recommendations
predicted by theory may be overly conservative, but they are what we
have used for this document. This question of machine availability
is one that should be reconsidered in light of current technology on
a regular basis.
2.5. Special purpose machines
In August of 2003, a design for a special-purpose "sieving machine"
(TWIRL) surfaced [Shamir2003], and it substantially changed the cost
estimates for factoring numbers up to 1024 bits in size. By applying
many high-speed VLSI components in parallel, such a machine might be
able to carry out the sieving of 512-bit numbers in 10 minutes at a
cost of $10K for the hardware. A larger version could sieve a 1024-
bit number in one year for a cost of $10M. The work cites some
advances in approaches to the row reduction step in concluding that
the security of 1024-bit RSA moduli is doubtful.
The estimates for the time and cost for factoring 512-bit and 1024-
bit numbers correspond to a speed-up factor of about 2 million over
what can be achieved with commodity processors of a few years ago.
Orman & Hoffman Best Current Practice [Page 9]
RFC 3766 Determining Strengths for Public Keys April 2004
3. Compute Time for the Algorithms
This section describes how long it takes to use the algorithms to
perform key exchanges. Again, it is important to consider the
increased time it takes to exchange symmetric keys when increasing
the length of public keys. It is important to avoid choosing
unfeasibly long public keys.
3.1. Diffie-Hellman Key Exchange
A Diffie-Hellman key exchange is done with a finite cyclic group G
with a generator g and an exponent x. As noted in the Pollard's rho
method section, the exponent has twice as many bits as are needed for
the final key. Let the size of the group G be p, let the number of
bits in the base 2 representation of p be j, and let the number of
bits in the exponent be K.
In doing the operations that result in a shared key, a generator is
raised to a power. The most efficient way to do this involves
squaring a number K times and multiplying it several times along the
way. Each of the numbers has j/w computer words in it, where w is
the number of bits in a computer word (today that will be 32 or 64
bits). A naive assumption is that you will need to do j squarings
and j/2 multiplies; fortunately, an efficient implementation will
need fewer (NB: for the remainder of this section, n represents j/w).
A squaring operation does not need to use quite as many operations as
a multiplication; a reasonable estimate is that squaring takes .6 the
number of machine instructions of a multiply. If one prepares a
table ahead of time with several values of small integer powers of
the generator g, then only about one fifth as many multiplies are
needed as the naive formula suggests. Therefore, one needs to do the
work of approximately .8*K multiplies of n-by-n word numbers.
Further, each multiply and squaring must be followed by a modular
reduction, and a good assumption is that it is as hard to do a
modular reduction as it is to do an n-by-n word multiply. Thus, it
takes K reductions for the squarings and .2*K reductions for the
multiplies. Summing this, the total effort for a Diffie-Hellman key
exchange with K bit exponents and a modulus of n words is
approximately 2*K n-by-n-word multiplies.
For 32-bit processors, integers that use less than about 30 computer
words in their representation require at least n^2 instructions for
an n-by-n-word multiply. Larger numbers will use less time, using
Karatsuba multiplications, and they will scale as about n^(1.58) for
larger n, but that is ignored for the current discussion. Note that
64-bit processors push the "Karatsuba cross-over" number out to even
more bits.
Orman & Hoffman Best Current Practice [Page 10]
RFC 3766 Determining Strengths for Public Keys April 2004
The basic result is: if you double the size of the Diffie-Hellman
modular exponentiation group, you quadruple the number of operations
needed for the computation.
3.1.1. Diffie-Hellman with elliptic curve groups
Note that the ratios for computation effort as a function of modulus
size hold even if you are using an elliptic curve (EC) group for
Diffie-Hellman. However, for equivalent security, one can use
smaller numbers in the case of elliptic curves. Assume that someone
has chosen an modular exponentiation group with an 2048 bit modulus
as being an appropriate security measure for a Diffie-Hellman
application and wants to determine what advantage there would be to
using an EC group instead. The calculation is relatively
straightforward, if you assume that on the average, it is about 20
times more effort to do a squaring or multiplication in an EC group
than in a modular exponentiation group. A rough estimate is that an
EC group with equivalent security has about 200 bits in its
representation. Then, assuming that the time is dominated by n-by-n-
word operations, the relative time is computed as:
((2048/200)^2)/20 ~= 5
showing that an elliptic curve implementation should be five times as
fast as a modular exponentiation implementation.
3.2. RSA encryption and decryption
Assume that an RSA public key uses a modulus with j bits; its factors
are two numbers of about j/2 bits each. The expected computation
time for encryption and decryption are different. As before, we
denote the number of words in the machine representation of the
modulus by the symbol n.
Most implementations of RSA use a small exponent for encryption. An
encryption may involve as few as 16 squarings and one multiplication,
using n-by-n-word operations. Each operation must be followed by a
modular reduction, and therefore the time complexity is about 16*(.6
+ 1) + 1 + 1 ~= 28 n-by-n-word multiplies.
RSA decryption must use an exponent that has as many bits as the
modulus, j. However, the Chinese Remainder Theorem applies, and all
the computations can be done with a modulus of only n/2 words and an
exponent of only j/2 bits. The computation must be done twice, once
for each factor. The effort is equivalent to 2*(j/2) (n/2 by n/2)-
word multiplies. Because multiplying numbers with n/2 words is only
1/4 as difficult as multiplying numbers with n words, the equivalent
effort for RSA decryption is j/4 n-by-n-word multiplies.
Orman & Hoffman Best Current Practice [Page 11]
RFC 3766 Determining Strengths for Public Keys April 2004
If you double the size of the modulus for RSA, the n-by-n multiplies
will take four times as long. Further, the decryption time doubles
because the exponent is larger. The overall scaling cost is a factor
of 4 for encryption, a factor of 8 for decryption.
3.3. Real-world examples
To make these numbers more real, here are a few examples of software
implementations run on hardware that was current as of a few years
before the publication of this document. The examples are included
to show rough estimates of reasonable implementations; they are not
benchmarks. As with all software, the performance will depend on the
exact details of specialization of the code to the problem and the
specific hardware.
The best time informally reported for a 1024-bit modular
exponentiation (the decryption side of 2048-bit RSA), is 0.9 ms
(about 450,000 CPU cycles) on a 500 MHz Itanium processor. This
shows that newer processors are not losing ground on big number
operations; the number of instructions is less than a 32-bit
processor uses for a 256-bit modular exponentiation.
For less advanced processors timing, the following two tables
(computed by Tero Monenen at SSH Communications) for modular
exponentiation, such as would be done in a Diffie-Hellman key
exchange.
Celeron 400 MHz; compiled with GNU C compiler, optimized, some
platform specific coding optimizations:
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
The group type is from [RFC2409] and is either modular exponentiation
("mod") or elliptic curve ("ecn"). All sizes here and in subsequent
tables are in bits.
Orman & Hoffman Best Current Practice [Page 12]
RFC 3766 Determining Strengths for Public Keys April 2004
Alpha 500 MHz compiled with Digital's C compiler, optimized, no
platform specific code:
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
The following two tables (computed by Eric Young) were originally for
RSA signing operations, using the Chinese Remainder representation.
For ease of understanding, the parameters are presented here to show
the interior calculations, i.e., the size of the modulus and exponent
used by the software.
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
Recent chips that accelerate exponentiation can perform 1024-bit
exponentiations (1024 bit modulus, 1024 bit exponent) in about 3
milliseconds or less.
4. Equivalences of Key Sizes
In order to determine how strong a public key is needed to protect a
particular symmetric key, you first need to determine how much effort
is needed to break the symmetric key. Many Internet security
protocols require the use of TripleDES for strong symmetric
encryption, and it is expected that the Advanced Encryption Standard
(AES) will be adopted on the Internet in the coming years.
Therefore, these two algorithms are discussed here. In this section,
for illustrative purposes, we will implicitly assume that the system
Orman & Hoffman Best Current Practice [Page 13]
RFC 3766 Determining Strengths for Public Keys April 2004
security requirement is 112 bits; this doesn't mean that 112 bits is
recommended. In fact, 112 bits is arguably too strong for any
practical purpose. It is used for illustration simply because that
is the upper bound on the strength of TripleDES.
If one could simply determine the number of MYs it takes to break
TripleDES, the task of computing the public key size of equivalent
strength would be easy. Unfortunately, that isn't the case here
because there are many examples of DES-specific hardware that encrypt
faster than DES in software on a standard CPU. Instead, one must
determine the equivalent cost for a system to break TripleDES and a
system to break the public key protecting a TripleDES key.
In 1998, the Electronic Frontier Foundation (EFF) built a DES-
cracking machine [GIL98] for US$130,000 that could test about 1e11
DES keys per second (additional money was spent on the machine's
design). The machine's builders fully admit that the machine is not
well optimized, and it is estimated that ten times the amount of
money could probably create a machine about 50 times as fast.
Assuming more optimization by guessing that a system to test
TripleDES keys runs about as fast as a system to test DES keys, so
approximately US$1 million might test 5e12 TripleDES keys per second.
In case your adversaries are much richer than EFF, you may want to
assume that they have US$1 trillion, enough to test 5e18 keys per
second. An exhaustive search of the effective TripleDES space of
2^112 keys with this quite expensive system would take about 1e15
seconds or about 33 million years. (Note that such a system would
also need 2^60 bytes of RAM [MH81], which is considered free in this
calculation). This seems a needlessly conservative value. However,
if computer logic speeds continue to increase in accordance with
Moore's Law (doubling in speed every 1.5 years), then one might
expect that in about 50 years, the computation could be completed in
only one year. For the purposes of illustration, this 50 year
resistance against a trillionaire is assumed to be the minimum
security requirement for a set of applications.
If 112 bits of attack resistance is the system security requirement,
then the key exchange system for TripleDES should have equivalent
difficulty; that is to say, if the attacker has US$1 trillion, you
want him to spend all his money to buy hardware today and to know
that he will "crack" the key exchange in not less than 33 million
years. (Obviously, a rational attacker would wait for about 45 years
before actually spending the money, because he could then get much
better hardware, but all attackers benefit from this sort of wait
equally.)
Orman & Hoffman Best Current Practice [Page 14]
RFC 3766 Determining Strengths for Public Keys April 2004
It is estimated that a typical PC CPU of just a few years ago can
generate over 500 MIPs and could be purchased for about US$100 in
quantity; thus you get more than 5 MIPs/US$. Again, this number
doubles about every 18 months. For one trillion US dollars, an
attacker can get 5e12 MIP years of computer instructions on that
recent-vintage hardware. This figure is used in the following
estimates of equivalent costs for breaking key exchange systems.
4.1. Key equivalence against special purpose brute force hardware
If the trillionaire attacker is to use conventional CPU's to "crack"
a key exchange for a 112 bit key in the same time that the special
purpose machine is spending on brute force search for the symmetric
key, the key exchange system must use an appropriately large modulus.
Assume that the trillionaire performs 5e12 MIPs of instructions per
year. Use the following equation to estimate the modulus size to use
with RSA encryption or DH key exchange:
5*10^33 = (6*10^-16)*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))
Solving this approximately for n yields:
n = 10^(625) = 2^(2077)
Thus, assuming similar logic speeds and the current efficiency of the
number field sieve, moduli with about 2100 bits will have about the
same resistance against attack as an 112-bit TripleDES key. This
indicates that RSA public key encryption should use a modulus with
around 2100 bits; for a Diffie-Hellman key exchange, one could use a
slightly smaller modulus, but it is not a significant difference.
4.2 Key equivalence against conventional CPU brute force attack
An alternative way of estimating this assumes that the attacker has a
less challenging requirement: he must only "crack" the key exchange
in less time than a brute force key search against the symmetric key
would take with general purpose computers. This is an "apples-to-
apples" comparison, because it assumes that the attacker needs only
to have computation donated to his effort, not built from a personal
or national fortune. The public key modulus will be larger than the
one in 4.1, because the symmetric key is going to be viable for a
longer period of time.
Assume that the number of CPU instructions to encrypt a block of
material using TripleDES is 300. The estimated number of computer
instructions to break 112 bit TripleDES key:
Orman & Hoffman Best Current Practice [Page 15]
RFC 3766 Determining Strengths for Public Keys April 2004
300 * 2^112
= 1.6 * 10^(36)
= .02*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))
Solving this approximately for n yields:
n = 10^(734) = 2^(2439)
Thus, for general purpose CPU attacks, you can assume that moduli
with about 2400 bits will have about the same strength against attack
as an 112-bit TripleDES key. This indicates that RSA public key
encryption should use a modulus with around 2400 bits; for a Diffie-
Hellman key exchange, one could use a slightly smaller modulus, but
it not a significant difference.
Note that some authors assume that the algorithms underlying the
number field sieve will continue to get better over time. These
authors recommend an even larger modulus, over 4000 bits, for
protecting a 112-bit symmetric key for 50 years. This points out the
difficulty of long-term cryptographic security: it is all but
impossible to predict progress in mathematics and physics over such a
long period of time.
4.3. A One Year Attack: 80 bits of strength
Assuming a trillionaire spends his money today to buy hardware, what
size key exchange numbers could he "crack" in one year? He can
perform 5*e12 MYs of instructions, or
3*10^13 * 5*10^12 = .02*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))
Solving for an approximation of n yields
n = 10^(360) = 2^(1195)
This is about as many operations as it would take to crack an 80-bit
symmetric key by brute force.
Thus, for protecting data that has a secrecy requirement of one year
against an incredibly rich attacker, a key exchange modulus with
about 1200 bits protecting an 80-bit symmetric key is safe even
against a nation's resources.
4.4. Key equivalence for other ciphers
Extending this logic to the AES is straightforward. For purposes of
estimation for key searching, one can think of the 128-bit AES as
being at least 16 bits stronger than TripleDES but about three times
Orman & Hoffman Best Current Practice [Page 16]
RFC 3766 Determining Strengths for Public Keys April 2004
as fast. The time and cost for a brute force attack is approximately
2^(16) more than for TripleDES, and thus, under the assumption that
128 bits of strength is the desired security goal, the recommended
key exchange modulus size is about 700 bits longer.
If it is possible to design hardware for AES cracking that is
considerably more efficient than hardware for DES cracking, then
(again under the assumption that the key exchange strength must match
the brute force effort) the moduli for protecting the key exchange
can be made smaller. However, the existence of such designs is only
a matter of speculation at this early moment in the AES lifetime.
The AES ciphers have key sizes of 128 bits up to 256 bits. Should a
prudent minimum security requirement, and thus the key exchange
moduli, have similar strengths? The answer to this depends on whether
or not one expect Moore's Law to continue unabated. If it continues,
one would expect 128 bit keys to be safe for about 60 years, and 256
bit keys would be safe for another 400 years beyond that, far beyond
any imaginable security requirement. But such progress is difficult
to predict, as it exceeds the physical capabilities of today's
devices and would imply the existence of logic technologies that are
unknown or infeasible today. Quantum computing is a candidate, but
too little is known today to make confident predictions about its
applicability to cryptography (which itself might change over the
next 100 years!).
If Moore's Law does not continue to hold, if no new computational
paradigms emerge, then keys of over 100 bits in length might well be
safe "forever". Note, however that others have come up with
estimates based on assumptions of new computational paradigms
emerging. For example, Lenstra and Verheul's web-based paper
"Selecting Cryptographic Key Sizes" chooses a more conservative
analysis than the one in this document.
4.5. Hash functions for deriving symmetric keys from public key
algorithms
The Diffie-Hellman algorithm results in a key that is hundreds or
thousands of bits long, but ciphers need far fewer bits than that.
How can one distill a long key down to a short one without losing
strength?
Cryptographic one-way hash functions are the building blocks for
this, and so long as they use all of the Diffie-Hellman key to derive
each block of the symmetric key, they produce keys with sufficient
strength.
Orman & Hoffman Best Current Practice [Page 17]
RFC 3766 Determining Strengths for Public Keys April 2004
The usual recommendation is to use a good one-way hash function
applied to he base material (the result of the key exchange) and to
use a subset of the hash function output for the key. However, if
the desired key length is greater than the output of the hash
function, one might wonder how to reconcile the two.
The step of deriving extra key bits must satisfy these requirements:
- The bits must not reveal any information about the key exchange
secret
- The bits must not be correlated with each other
- The bits must depend on all the bits of the key exchange secret
Any good cryptographic hash function satisfies these three
requirements. Note that the number of bits of output of the hash
function is not specified. That is because even a hash function with
a very short output can be iterated to produce more uncorrelated bits
with just a little bit of care.
For example, SHA-1 has 160 bits of output. For deriving a key of
attack resistance of 160 bits or less, SHA(DHkey) produces a good
symmetric key.
Suppose one wants a key with attack resistance of 160 bits, but it is
to be used with a cipher that uses 192 bit keys. One can iterate
SHA-1 as follows:
Bits 1-160 of the symmetric key = K1 = SHA(DHkey | 0x00)
(that is, concatenate a single octet of value 0x00 to
the right side of the DHkey, and then hash)
Bits 161-192 of the symmetric key = K2 =
select_32_bits(SHA(K1 | 0x01))
But what if one wants 192 bits of strength for the cipher? Then the
appropriate calculation is
Bits 1-160 of the symmetric key = SHA(0x00 | DHkey)
Bits 161-192 of the symmetric key =
select_32_bits(SHA(0x01 | DHkey))
(Note that in the description above, instead of concatenating a full
octet, concatenating a single bit would also be sufficient.)
Orman & Hoffman Best Current Practice [Page 18]
RFC 3766 Determining Strengths for Public Keys April 2004
The important distinction is that in the second case, the DH key is
used for each part of the symmetric key. This assures that entropy
of the DH key is not lost by iteration of the hash function over the
same bits.
From an efficiency point of view, if the symmetric key must have a
great deal of entropy, it is probably best to use a cryptographic
hash function with a large output block (192 bits or more), rather
than iterating a smaller one.
Newer hash algorithms with longer output (such as SHA-256, SHA-384,
and SHA-512) can be used with the same level of security as the
stretching algorithm described above.
4.6. Importance of randomness
Some of the calculations described in this document require random
inputs; for example, the secret Diffie-Hellman exponents must be
chosen based on n truly random bits (where n is the system security
requirement). The number of truly random bits is extremely important
to determining the strength of the output of the calculations. Using
truly random numbers is often overlooked, and many security
applications have been significantly weakened by using insufficient
random inputs. A much more complete description of the importance of
random numbers can be found in [ECS].
5. Conclusion
In this table it is assumed that attackers use general purpose
computers, that the hardware is purchased in the year 2000, and that
mathematical knowledge relevant to the problem remains the same as
today. This is an pure "apples-to-apples" comparison demonstrating
how the time for a key exchange scales with respect to the strength
requirement. The subgroup size for DSA is included, if that is being
used for supporting authentication as part of the protocol; the DSA
modulus must be as long as the DH modulus, but the size of the "q"
subgroup is also relevant.
Orman & Hoffman Best Current Practice [Page 19]
RFC 3766 Determining Strengths for Public Keys April 2004
+-------------+-----------+--------------+--------------+
| System | | | |
| requirement | Symmetric | RSA or DH | DSA subgroup |
| for attack | key size | modulus size | size |
| resistance | (bits) | (bits) | (bits) |
| (bits) | | | |
+-------------+-----------+--------------+--------------+
| 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 Correction
If the TWIRL machine becomes a reality, and if there are advances in
parallelism for row reduction in factoring, then conservative
estimates would subtract about 11 bits from the system security
column of the table. Thus, in order to get 89 bits of security, one
would need an RSA modulus of about 1900 bits.
6. Security Considerations
The equations and values given in this document are meant to be as
accurate as possible, based on the state of the art in general
purpose computers at the time that this document is being written.
No predictions can be completely accurate, and the formulas given
here are not meant to be definitive statements of fact about
cryptographic strengths. For example, some of the empirical results
used in calibrating the formulas in this document are probably not
completely accurate, and this inaccuracy affects the estimates. It
is the authors' hope that the numbers presented here vary from real
world experience as little as possible.
7. References
7.1. Informational References
[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.
Orman & Hoffman Best Current Practice [Page 20]
RFC 3766 Determining Strengths for Public Keys April 2004
[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.
Orman & Hoffman Best Current Practice [Page 21]
RFC 3766 Determining Strengths for Public Keys April 2004
8. Authors' Addresses
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
Orman & Hoffman Best Current Practice [Page 22]
RFC 3766 Determining Strengths for Public Keys April 2004
9. Full Copyright Statement
Copyright (C) The Internet Society (2004). This document is subject
to the rights, licenses and restrictions contained in BCP 78, and
except as set forth therein, the authors retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE
INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed
to pertain to the implementation or use of the technology
described in this document or the extent to which any license
under such rights might or might not be available; nor does it
represent that it has made any independent effort to identify any
such rights. Information on the procedures with respect to
rights in RFC documents can be found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use
of such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository
at http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention
any copyrights, patents or patent applications, or other
proprietary rights that may cover technology that may be required
to implement this standard. Please address the information to the
IETF at ietf-ipr@ietf.org.
Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.
Orman & Hoffman Best Current Practice [Page 23]