RFC 3766 Determining Strengths For Public Keys Used For Exchanging Symmetric Keys

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

Определение стойкости открытых ключей, применяемых для обмена симметричными ключами

PDF

Статус документа

Этот документ относится к категории обмена опытом (Best Current Practice) в сообществе Internet и служит приглашением к дискуссии и внесению предложений в целях дальнейшего развития. Документ может распространяться свободно.

Авторские права

Copyright (C) The Internet Society (2004). Все права защищены.

Аннотация

Создателям систем, использующих криптографию с открытым ключом для обмена симметричными ключами, требуется обеспечить стойкость открытых ключей к определённому уровню атак. Этот уровень устойчивости к атакам называется стойкостью системы и передаваемые при обмене симметричные ключи должны быть не менее стойкими, нежели система. Три параметра — стойкость системы, стойкость симметричных ключей и стойкость открытых ключей должны быть согласованы для любых применений сетевых протоколов.

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

1. Модель защиты симметричных ключей с помощью открытых

Во многих книгах по криптографии и безопасности объясняется необходимость публичного обмена симметричными ключами, а также используемые для этого многочисленные алгоритмы. Однако лишь в немногих публикациях обсуждается стойкость открытых и симметричных ключей и связь между ними. Для понимания этого представим дом с надёжным замком на входной двери, рядом с которой размещён небольшой сейф, где хранится ключ от замка. У желающего проникнуть в дом преступника есть два варианта — взломать замок на двери или ящик, где хранится ключ. Очевидно, что лучше взламывать более слабый из двух. Домовладелец в такой ситуации должен обеспечить для второго варианта (сейф) стойкость не ниже стойкости замка на входной двери, чтобы не упростить работу взломщику.

Разработчику системы с обменом симметричными ключами на основе криптографии с открытым ключом требуется принимать аналогичное решение. Предположим, что злоумышленнику нужно узнать содержимое сообщения, зашифрованного с симметричным ключом, переданным между отправителем и получателем на основе криптографии с открытым ключом. У злоумышленника есть два варианта — подобрать симметричный ключ (brute-force) или математически определить секретный ключ, использованный при обмене. Умный злоумышленник выберет более простой из этих вариантов.

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

Третий вопрос связан с минимальными требованиями по безопасности к пользователю. Предположим, что пользователь шифрует данные с помощью CAST-128 и ему требуется симметричный ключ, способный устоять против подбора в течение 20 лет. Можно начать с выбора ключа с 86 случайными битами и воспользоваться необратимой функцией (например, SHA-1) для «увеличения» до блока из 160 битов, из которых 128 будут применены в качестве ключа для CAST-128. В таком случае от алгоритма обмена ключами потребуется стойкость, соответствующая 86, а не 128 битам. Процедура выбора показана ниже.

1. Определяется стойкость к атакам, требуемая для обеспечения безопасности приложения, для чего оценивается минимальное число вычислительных операций, которые потребуется выполнить злоумышленнику для взлома системы, а затем найти его двоичный логарифм (обозначим его n). В отчёте 1996 г. рекомендовалось использовать 90 битов в качестве универсального размера для защиты систем. Это значение следует увеличивать примерно на 2/3 бита в год, что даёт значение 96 для 2005 г.

2. Выбирается симметричный алгоритм с ключом не короче n битов и не меньшей криптостойкостью.

3. Выбирается алгоритм обмена ключами со стойкостью к атакам не менее n битов.

Четвёртым фактором может быть метод проверки подлинности открытого ключа, применяемого для отождествления пользователя. Это может быть цифровая подпись RSA или DSA. Если модуль в методе аутентификации недостаточно велик, основа доверия к сообщению может быть потеряна, поэтому добавляется ещё один шаг.

4. Выбор алгоритма аутентификации с устойчивостью к атакам не менее n битов. Это гарантирует, что ключ, которым обмениваются стороны, не может быть подделан в течение срока секретности зашифрованного материала. Это может не требоваться строго, если ключи аутентификации часто меняются и имеют точно известное время жизни, но в иных случаях рекомендуется использовать n битов.

1.1. Алгоритмы обмена ключами

В методе Диффи-Хеллмана (DH) используется группа, генератор и показатель (exponent). В современных стандартах Internet групповая операция основана на модульном умножении. Группа определяется мультипликативной группой целых чисел — обычно простым числом p = 2q + 1, где q — простое число, арифметические действия выполняются по модулю p, а генератор (часто просто число 2) обозначается g.

В этом алгоритме Алиса и Боб сначала согласуют (публично или приватно) значения g и p. Затем Алиса выбирает большое случайное целое число (a), а Боб — большое случайное целое число (b). Эти числа каждый держит в секрете. Алиса передаёт Бобу значение A = g^a mod p, а Боб передаёт Алисе значение B = g^b mod p. Затем Алиса вычисляет значение B^a mod p, а Боб — A^b mod p. Эти два числа будут равны и участники взаимодействия могут использовать простую функцию от этого числа в качестве симметричного ключа k.

Отметим, что обмен Диффи-Хеллмана может выполняться с различными групповыми представлениями. Например, эллиптические кривые, заданные над конечными полями, являются особенно эффективным способом расчёта при обмене ключами [SCH95].

Для обмена ключами RSA предположим, что Боб имеет открытый ключ (m) = p*q, где p и q — секретные простые числа, показатель шифрования имеет значение e, а показатель расшифровки — d. При каждом обмене ключами Алиса передаёт Бобу значение E = k^e mod m, где k — секретный симметричный ключ, которым нужно обменяться. Боб восстанавливает ключ k вычисляя значение E^d mod m, и в результате обе стороны будут иметь секретный ключ k. Хотя Боб может использовать небольшой показатель шифрования (например, 17 битов), его показатель расшифровки будет иметь столько же битов, сколько имеет модуль m.

2. Сложность разложения на сомножители

Метод шифрования с открытым ключом RSA устойчив к подбору ключей (brute force), поскольку модуль (и, следовательно, показатель d) имеет размер на менее 512 битов, а это даёт слишком много вариантов для перебора. Обмен Диффи-Хеллмана тоже устойчив к перебору, поскольку получатель будет иметь по меньше мере вдвое больше битов, чем симметричные ключи, которые будут выведены. Однако оба метода подвержены математическим атакам, определяющим структуру открытых ключей.

Факторизация¹ модуля RSA приведёт к полной компрометации секретного ключа. Решение задачи дискретного логарифма для системы возведения в степень по модулю в методе DH приведёт к такому же результату для всех обменов ключами с применением данного модуля. Здесь предполагается, что сложность решения задачи дискретного логарифма эквивалентна сложности факторизации чисел такого же размера, как модуль. На деле это немного сложнее, поскольку требует больше операций. Эмпирические данные дают отношение сложностей не менее 20, возможно даже до 64. Решение любой из этих задач требует большого объёма памяти на последнем этапе алгоритма — сокращении матрицы. Пока неясно, будет ли потребность в памяти ограничивающим фактором при решении задач с большими целыми числами и ведутся исследования параллельных матричных алгоритмов, которые могут сократить требования.

Просеивание числового поля (number field sieve или NFS) [GOR93] [LEN93] является сегодня наилучшим методом решения задачи дискретного алгоритма. Число простых арифметических операций, требуемых для разложения целого числа n по методу NFS можно оценить как

      L(n) = k * e^((1,92 + o(1)) * cubrt2(ln(n) * (ln(ln(n)))^2))

Многие предпочитают обсуждать число MIPS³-лет (MIPS year или MY), требуемых для выполнения больших операций, таких как просеивание числового поля. В такой оценке операцией в расчёте L(n) является одна компьютерная инструкция (команда). Эмпирические данные показывают, что 4 или 5 инструкций (а не 1) на операцию могут давать большую точность, но это второстепенный фактор и в этом документе операцией считается одна команда.

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]. Результаты, показывающие, что при факторизации NFS фактическое число операций меньше предсказанного, приведены в [DL].

2.2. Выбор 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. Метод Ро Полларда

Для обменов Диффи-Хеллмана существует вторая атака — метод Ро Полларда [POL78]. Алгоритм основан на поиске коллизий между значениями, вычисленными в пространстве больших чисел, успех которого пропорционален квадратному корню из размера пространства. Из-за метода Ро пространство поиска для ключа в обмене DH (показатель в выражении g^a) должно быть вдвое больше, чем для симметричных ключей. Поэтому для безопасного получения ключа с K битами реализация должна использовать показатель с числом битов не менее 2*K (см. [ODL99]).

При обмене Диффи-Хеллмана на основе эллиптической кривой методы NFS недоступны, однако поиск коллизий по-прежнему эффективен и необходимость использовать показатель (множитель в эллиптических кривых) с 2*K битов сохраняется. Используемый при расчётах модуль также может иметь размер 2*K битов и это будет существенно меньше модуля, требуемого для методов возведения в степень по модулю, поскольку желаемый уровень безопасности превышает устойчивость к подбору в 64 бита.

Можно усомниться в сравнении числа команд при атаке с использованием дискретного логарифма с числом операций поиска в пространстве ключей шифра. Для этого нужно понять, что такое «базовая операция». Для перебора в пространстве ключей симметричного алгоритма, такого как DES, базовой операцией является создание ключа и одно шифрование, для дискретного логарифма — возведение в квадрат по модулю. Логарифм отношения времени выполнения операций может служить «коэффициентом нормализации» между этими расчётами. Однако даже для очень больших модулей (16К битов) этот коэффициент добавляет лишь несколько битов издержек.

2.4. Пределы памяти и числа машин

Robert Silverman исследовал вопрос о том, когда станет целесообразным использовать модули RSA больше 512 битов. Его анализ основан не только на теоретическом числе операций, но и включает ожидания в части доступности машин для выполнения работы (в этом документе рассматривается лишь первый аспект). В работе исследуется вопрос возможности появления достаточного числа машин, памяти и средств связи для обработки очень больших чисел.

Лучшие методы разложения на сомножители требуют много памяти с произвольным доступом для сбора сведений о взаимосвязях данных (просеивание) и критически важного заключительного этапа сокращения числа строк большой матрицы. Требования к памяти связаны с размером разлагаемого на сомножители числа (или решения задачи дискретного логарифма). Сильверман [SILIEEE99] [SIL00] утверждает, что существует практическое ограничение числа машин и объёма ОЗУ, которые можно будет использовать для решения одной задачи в будущем. Он видит две проблемы при атаке на 1024-битовый модуль RSA — машинам, выполняющим просеивание, требуется 64-битовое пространство адресов, а для сокращения матрицы потребуется несколько ТБайт памяти. Сильверман отмечает, что было продано очень мало 64-битовых машин, имеющих 170 ГБайт памяти, требуемых для просеивания. Для выполнения просеивания в разумные сроки (1-2 года) требуется около миллиарда таких машин.

Вывод Сильвермана на основе истории факторизации и закона Мура (Moore’s Law) состоит в том, что 1024-битовые модули RSA не могут быть разложены на сомножители раньше 2037 г. Это означает, что срок службы ключей RSA существенно превышает предсказания теории. Утверждается, что прогнозы доступности множества машин с большой памятью, основанные на экстраполяции закона Мура и недавней истории факторизации можно делать с уверенностью.

Следует придавать большое значение практическим соображениям, но анализ рисков в физическом мире менее предсказуем, чем можно ожидать по графикам тенденций. При рассмотрении вопроса доверия к предсказаниям неспособности компьютерной индустрии удовлетворить ненасытные потребности факторинга нужно иметь некоторое представление об экономических вопросах, что гораздо сложнее математики разложения на сомножители. Спрос на компьютерную память трудно предсказать, поскольку он основан на приложениях и в любой момент может появиться «убойное приложение» (killer app), вызывающее бешеный рост продаж памяти. Число процессоров, доступных в настольных компьютерах, может быть ограничено числом рабочих мест, но на встраиваемые системы с высокой производительностью расходуется больше процессоров, чем на настольные компьютеры. Поскольку встраиваемые системы расходуют сетевые ресурсы, вполне возможно заполнение среды миллионами 64-битовых процессоров, имеющих не менее 1 ГБайт памяти.

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

2.5. Машины специального назначения

В августе 2003 г. был разработан проект специальной «просеивающей машины» (sieving machine или TWIRL) [Shamir2003], который существенно изменил оценку затрат на факторизацию чисел с числом битов до 1024. За счёт параллельного применения множества высокоскоростных СБИС (VLSI) такая машина способна выполнять просеивание 512-битовых чисел за 10 минут при стоимости оборудования $10K. В более крупном варианте машины просеивание 1024-битовых чисел могло быть выполнено за 1 год при стоимости оборудования $10M. В работе описаны некоторые подходы к сокращению матрицы и отмечено, что вывод о безопасности 1024-битовых модулей RSA сомнителен.

Оценки времени и стоимости факторизации 512- и 1024-битовых чисел соответствуют ускорению примерно в 2 миллиона раз по сравнению с использованием обычных процессоров несколько лет назад.

3. Расчёт времени для алгоритмов

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

3.1. Обмен ключами DH

Обмен ключами по методу Диффи-Хеллмана выполняется с помощью конечной циклической группы G с генератором g и показателем степени x. Как отмечалось в разделе о методе Ро Полларда, показатель степени содержит вдвое больше битов, чем требуется для финального ключа. Пусть размер группы G равен p, число битов в двоичном представлении p — j, а число битов в показателе — K.

При выполнении операций по созданию общего ключа генератор возводится в степень. Наиболее эффективным способом выполнения этого является возведение в квадрат K раз и умножение на себя несколько раз. Каждое из чисел содержит j/w машинных слов, где w — число битов в слове (32 или 64 в современных машинах). Наивное допущение включает j возведений в квадрат и j/2 перемножений, однако для эффективной реализации требуется меньше операций. Важно отметить, что далее в документе n представляет j/w. Операция возведения в квадрат использует меньше машинных команд, нежели умножение. Разумной оценкой представляется коэффициент 0,6. Если заранее подготовить таблицу с несколькими значениями малых целочисленных степеней генератора g, достаточно будет (примерно) пятой части перемножений, требуемых при наивном подходе. Следовательно, нужно выполнить работу, равную примерно 0,8*K операций перемножения чисел из n слов. За каждым умножением и возведением в квадрат должно следовать сокращение по модулю и разумно допустить, что издержки такого сокращения совпадут с издержками перемножения чисел из n слов. В результате потребуется K сокращений для возведения в квадрат и 0,2*K для перемножений. Таким образом, суммарные издержки при обмене ключами DH с показателем в K битов и модулем в n слов эквивалентны приблизительно 2*K операций перемножения чисел из n слов.

В 32-разрядных процессорах для перемножения целых чисел размером менее 30 слов требуется по меньшей мере n^2 машинных команд. Для больших чисел можно сократить время, используя умножение Карацубы, где требуется примерно n^(1,58) команд, но здесь это не рассматривается. На 64-разрядных процессорах эффект ещё сильнее.

Основной вывод заключается в том, что удвоение размера группы возведения в степень по модулю для DH увеличивает число требуемых операций в 4 раза.

3.1.1. Метод DH с эллиптическими кривыми

Отметим, что коэффициенты отношений расчётных усилий в зависимости от размера модуля сохраняются даже при использовании DH с группой эллиптических кривых (EC), однако для эквивалентной безопасности в случае EC требуются числа меньшего размера. Предположим, что выбрана группа с возведением в степень по модулю в 2048 битов модулем для приложений DH и нужно оценить преимущество при её замене на группу EC. Расчёт сравнительно прост при допущении, что возведение в квадрат или умножение для EC требует в среднем примерно в 20 раз меньших издержек, чем при возведении в степень по модулю. Грубая оценка показывает, что для эквивалентной безопасности группе EC достаточно примерно 200 битов. В предположении, что время определяется в основном операциями перемножения чисел из n слов, отношение времени выполнения составит

      ((2048/200)^2)/20 ~= 5

Таким образом, реализация с эллиптической кривой будет примерно в 5 раз быстрее возведения в степень по модулю.

3.2. Шифрование и дешифровка RSA

Предположим, что в открытом ключе RSA используется модуль с j битами, а коэффициентами являются два числа, по j/2 битов. Ожидаемое время расчётов при шифровании и дешифровании будет разным. Обозначим число слов в машинном представлении модуля буквой n.

В большинстве реализаций RSA при шифровании применяется небольшой показатель степени. Шифрование может включать 16 операций возведения в квадрат и одно умножение с операндами из n слов. Каждая операция должна сопровождаться сокращением по модулю, поэтому временная сложность составит примерно 6*(0,6 + 1) + 1 + 1 ~= 28 перемножений n х n слов.

При расшифровке RSA должен использоваться показатель с числом битов как у модуля (j). Однако применяется Китайская теорема об остатке и расчёты можно выполнять с модулем лишь из n/2 слов и показателем из j/2 битов. Расчёт должен выполняться дважды — по одному разу для каждого множителя. Издержки эквивалентны 2*(j/2) перемножений n/2 слов. Поскольку издержки при перемножении n/2 слов составляют лишь 1/4 сложности перемножения n слов, эквивалентные издержки расшифровки RSA составят j/4 n слов.

При удвоении размера модуля для RSA перемножение займёт в 4 раза больше времени. Кроме того, удвоится время расшифровки из-за роста показателя степени. Издержки вырастут в 4 раза для шифрования и в 8 для расшифровки.

3.3. Реальные примеры

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

Наилучшее время, неофициально сообщённое для 1024-битового возведения в степень по модулю (дешифрование 2048-битового RSA), составляет 0,9 мсек (около 450000 тактов CPU) для процессора Itanium с тактовой частотой 500 МГц. Это показывает, что новые процессоры не теряют позиций при выполнении операций с большими числами — количество команд меньше, чем требуется 32-битовому процессору для 256-битового возведения в степень по модулю.

Для менее продвинутых процессоров в двух следующих таблицах (расчёты Tero Monenen из SSH Communications) показано время возведения в степень по модулю, которое выполняется при обмене ключами по методу DH.

Celeron 400 МГц, компилятор GNU C с некоторой оптимизацией кода для платформы

 

Тип группы	Размер модуля	Размер показателя	Время
mod	768	~150	18 мсек
mod	1024	~160	32 мсек
mod	1536	~180	82 мсек
ecn	155	~150	35 мсек
ecn	185	~200	56 мсек

 

Тип группы [RFC2409] указывает возведение в степень по модулю (mod) или эллиптическую кривую (ecn). Размеры в этой и последующих таблицах указаны в битах.

Alpha 500 МГц, компилятор Digital’s C, оптимизация без учёта специфики платформы

 

Тип группы	Размер модуля	Размер показателя	Время
mod	768	~150	12 мсек
mod	1024	~160	24 мсек
mod	1536	~180	59 мсек
ecn	155	~150	20 мсек
ecn	185	~200	27 мсек

 

Следующие две таблицы (расчёты Eric Young) изначально предназначались для операций подписи RSA с использованием Китайского представления остатка. Для простоты понимания приведены параметры, показывающие внутренние расчёты, т. е. размеры модуля и показателя, использованные программой.

Dual Pentium II-350 МГц

 

Размер эквивалентного модуля	Размер эквивалентного показателя	Эквивалентное время
256	256	1,5 мсек
512	512	8,6 мсек
1024	1024	55,4 мсек
2048	2048	387 мсек

 

Alpha 264 600 МГц

 

Размер эквивалентного модуля	Размер эквивалентного показателя	Эквивалентное время
512	512	1,4 мсек

 

Новейшие микросхемы, ускоряющие возведение в степень, могут выполнять 1024-битовые операции возведения в степень (1024-битовый модуль, 1024-битовый показатель) примерно за 3 миллисекунды или быстрее.

4. Эквивалентность размеров ключей

Чтобы определить, насколько надёжным должен быть открытый ключ для защиты конкретного симметричного ключа, сначала нужно оценить усилия, требуемые для взлома симметричного ключа. Многие протоколы безопасности Internet требуют применять TripleDES для надёжного симметричного шифрования и предполагается, что в ближайшие годы будет принят передовой (расширенный) стандарт шифрования (Advanced Encryption Standard или AES). Поэтому здесь рассматриваются два алгоритма. В этом разделе для иллюстрации неявно предполагается требование системного уровня безопасности 112 битов, но это не означает рекомендации использовать такой уровень. На практике уровень в 112 битов может оказаться избыточным для любого практического применения. Он принят для иллюстрации лишь потому, что является верхней границей надежности TripleDES.

Если бы можно было просто определить число MYs для взлома TripleDES, задача расчёта размера открытого ключа с эквивалентной стойкостью стала бы простой. К сожалению, в данном случае это не так, поскольку имеется много примеров оборудования для DES, которое шифрует быстрее, чем программные реализации DES на стандартных CPU. Требуется оценить эквивалентные издержки для взлома TripleDES и системы для взлома открытого ключа, защищающего ключ TripleDES.

В 1998 фонд EFF (Electronic Frontier Foundation) создал машину для взлома DES [GIL98] за US$130000, которая могла проверить 1e11 ключей DES за 1 секунду (на разработку машины были потрачены дополнительные деньги). Создатели машины полностью признают, что она недостаточно оптимизирована, и полагают, что за сумму в 10 раз больше можно создать машину быстрее примерно в 50 раз. Предполагая дополнительную оптимизацию, допустим, что система для тестирования ключей TripleDES работает так же быстро, как система тестирования DES, можно считать, что может потребоваться 1 миллион долларов США для проверки 5e12 ключей TripleDES за 1 секунду.

Если ваши противники сильно богаче EFF, можно предположить, что у них есть 1 триллион долларов США для проверки 5e18 ключей за 1 секунду. Исчерпывающий поиск в эффективном пространстве TripleDES из 2^112 ключей с помощью этой достаточно дорогой схемы занял бы 1e15 секунд (около 33 миллионов лет). Отметим, что такой системе также потребовалось бы 2^60 байтов оперативной памяти [MH81], которая в данном расчёте принимается свободной. Полученная оценка представляется излишне консервативной. Однако, если скорость вычислительной логики продолжит расти по закону Мура (удвоение каждые1,5 года), можно ожидать, что через 50 лет для таких расчётов будет достаточно 1 года. Для иллюстрации предполагается, что 50-летняя стойкость к атаке с триллионными затратами является минимальным требованием безопасности для набора приложений.

Если стойкость в 112 битов является системным требованием, системе обмена ключами для TripleDES следует обеспечивать эквивалентную стойкость. Иными словами, при наличии у атакующего триллиона долларов вы будете хотеть, чтобы он потратил свои деньги на закупку оборудования, зная, что взлом ключей потребует 33 миллиона лет. Очевидно, что рациональный злоумышленник подождёт около 45 лет перед реальной тратой денег, поскольку тогда он сможет приобрести более эффективное оборудование, но от такого ожидания выиграют и другие злоумышленники.

Подсчитано, что обычный процессор для ПК, выпускавшийся всего несколько лет назад, может выполнять более 500 MIPs и его можно приобрести примерно за US$100, что даёт 5 MIPs/US$. Это значение также удваивается приблизительно каждые 18 месяцев. За триллион долларов атакующий может получить на таком оборудовании 5e12 MIPs. Эта цифра далее применяется в расчётах эквивалентных затрат на взлом систем обмена ключами.

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 битов, а для обмена ключами DH можно использовать модули чуть меньшего размера.

4.2. Эквивалентность ключей и перебор с помощью обычных CPU

В другом варианте оценки предполагается что требования злоумышленника слабее — он должен лишь «взломать» обмен ключами быстрее, чем занял бы перебор симметричных ключей с помощью компьютеров общего назначения. Это простое сравнение, поскольку предполагается, что злоумышленнику просто нужно воспользоваться для своих целей бесплатными вычислительными ресурсами, а не привлекать личные или государственные средства. Модуль открытого ключа будет больше, чем в параграфе 4.1, поскольку симметричный ключ будет пригодным дольше.

Предположим, что число команд CPU для шифрования блока данных с помощью TripleDES составляет 300. Оценочное число процессорных команд для взлома 112-битового ключа TripleDES составит

      300 * 2^112
      = 1,6 * 10^(36)
      = 0,02*e^(1,92*cubrt(ln(n)*(ln(ln(n)))^2))

Приближенным значением n будет

      n = 10^(734) = 2^(2439)

таким образом, можно предположить, что при атаках с CPU общего назначения модули с числом битов около 2400 будут примерно так же стойки, как 112-битовые ключи TripleDES. Это значит, что при шифровании RSA с открытым ключом следует применять модули размером около 2400 битов, а для обмена ключами DH они могут быть чуть короче.

Отметим, что некоторые авторы полагают, что лежащие в основе анализа числовых полей алгоритмы будут со временем совершенствоваться. Эти авторы рекомендуют применять модули размером более 4000 битов для защиты 112-битового симметричного ключа в течение 50 лет. Это показывает сложность долговременной криптозащиты, а предсказать прогресс в математике и физике на столь длительный период практически невозможно.

4.3. Годичная атака (стойкость 80 битов)

Предположим, что сегодня потрачен 1 триллион долларов на закупку упомянутого выше оборудования. Какого размера ключи при обмене ключами удастся взломать за 1 год? Оборудование позволит выполнить 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-битового симметричного ключа.

Таким образом, для защиты данных, требующих сохранения секретности в течение 1 года от невероятно богатого злоумышленника, достаточно использовать при обмене ключами модуль размером около 1200 битов, защищающий 80-битовый симметричный ключ.

4.4. Эквивалентность ключей для других шифров

Описанную логику несложно распространить на AES. Для оценки поиска ключей можно считать, что 128-битовый AES по меньшей мере на 16 битов сильнее TripleDES, но примерно втрое быстрее. Время и расходы на атаку методом перебора примерно в 2^(16) раз больше, чем для TripleDES и, при допущении желательной стойкости в 128 битов, рекомендуемый размер модуля при обмене ключами примерно на 700 битов длиннее.

Если создать оборудование для взлома AES, гораздо более эффективное, чем оборудование для взлома DES (при условии соответствия стойкости обмена ключами и сложности перебора), размер модуля для защиты обмена ключами может быть меньше. Однако на данном этапе можно лишь догадываться о наличии такого оборудования для AES.

В шифрах AES применяются ключи размером от 128 до 256 битов. Должны ли разумные минимальные требования безопасности и, следовательно, модули для обмена ключами, обеспечивать аналогичную стойкость? Ответ зависит от ожиданий по части продолжения действия закона Мура. Если закон продолжит действовать, 128-битовые ключи будут безопасны около 60 лет, а 256-битовые — ещё 400, что намного превосходит мыслимые требования к безопасности. Однако такой прогресс трудно представить, поскольку он превосходит физические возможности современных устройств и предполагает наличие логических технологий, которые сегодня неизвестны или невозможны. Одним из перспективных вариантов являются квантовые технологии, но сегодня о них известно слишком мало, чтобы делать уверенные прогнозы об их применимости в криптографии, которая сама может измениться за следующие 100 лет. Если закон Мура перестанет работать и не появятся новые парадигмы вычислений, ключи размером более 100 битов могут остаться безопасными «навсегда». Однако следует отметить, что другие исследователи предлагали оценки на основе предположения о появлении новых вычислительных парадигм. Например, в сетевой публикации Lenstra и Verheul «Selecting Cryptographic Key Sizes» применён более консервативный анализ, нежели в этом документе.

4.5. Хэш-функции для вывода симметричных ключей

Алгоритм Диффи-Хеллмана позволяет создавать ключи размером в сотни и тысячи битов, но для шифров нужно гораздо меньше. Как преобразовать длинный ключ в короткий без потери стойкости?

Для этого служат необратимые хэш-функции и применение их в алгоритме DH для создания каждого блока симметричного ключа обеспечивает достаточную стойкость получаемых ключей. Обычно рекомендуется применять хорошую необратимую хэш-функцию к базовому материалу (результат обмена ключами) и использовать часть результатов хэш-функции для создания итогового ключа. Однако, если желаемый размер ключа больше выходного значения хэш-функции возникает задача их согласования. Этап вывода дополнительных битов ключа должен удовлетворять ряду требований:

• битам недопустимо раскрывать сведения о секрете, применяемом для обмена ключами;

• недопустима корреляция между значениями битов;

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

Этим требованиям удовлетворяет любая хорошая криптографическая хэш-функция. Отметим, что выходной размер хэш-функции не задаётся. Это обусловлено тем, что даже функции с очень коротким результатом можно вызывать итеративно для создания большего числа некоррелированных битов, проявив немного осторожности. Например, функция SHA-1 даёт на выходе 160 битов. Для получения ключа со стойкостью к атакам в 160 битов или меньше SHA(DHkey) обеспечивает хороший симметричный ключ. Предположим, что нужен ключ со стойкостью 160 битов, который будет применяться с шифром, использующим 192-битовые ключи. Можно использовать итерацию SHA-1:

биты 1-160 симметричного ключа K1 = SHA(DHkey | 0x00) (хэш конкатенации октета 0x00 и значения DHkey);

биты 161-192 симметричного ключа K2 = select_32_bits(SHA(K1 | 0x01)).

Если для шифрования нужна стойкость в 192 бита, можно воспользоваться следующим расчётом:

биты 1-160 симметричного ключа = SHA(0x00 | DHkey)

биты 161-192 симметричного ключа = select_32_bits(SHA(0x01 | DHkey))

(отметим, что в этом расчёте для конкатенации можно применять 1 бит вместо целого октета).

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

С точки зрения эффективности для обеспечения высокой энтропии симметричного ключа, вероятно, будет лучше всего использовать криптографическую хэш-функцию с большим выходным размером (192 бита и более) вместо итераций функции с более коротким выводом. Новые алгоритмы хэширования с более длинным выводом (такие как SHA-256, SHA-384, SHA-512) могут использоваться с таким же уровнем безопасности, какой даёт описанный выше алгоритм «растяжения».

4.6. Важность случайных значений

Некоторым из описанных здесь расчётов требуются на входе случайные значение, например, показатели секрета DH требуется выбирать на основе n действительно случайных битов (n зависит от требований безопасности в системе). Число действительно случайных битов чрезвычайно важно для стойкости результатов расчётов. Использование действительно случайных значений зачастую упускают из виду и многие защитные приложения значительно ослаблены в результате использования недостаточно случайных битов. Важность генерации случайных значений более подробно рассмотрена в [ECS].

5. Заключение

Данные в таблице основаны на допущении использования злоумышленниками компьютеров общего назначения, приобретённых в 2000 году, и сохранения текущего уровня математических знаний, относящихся к задаче. Это простое сравнение однотипных значений, показывающее зависимость времени обмена ключами от требований к стойкости. Указан размер подгруппы DSA, если он используется в протоколе для аутентификации, размер модулей DSA должен совпадать с размером модулей DH, но имеет значение и размер подгруппы q.

Требования по стойкости к атакам (в битах)	Размер симметричного ключа	Размер модулей RSA и DH (в битах)	Размер подгруппы DSA (в битах)
70	70	947	129
80	80	1228	148
90	90	1553	167
100	100	1926	186
150	150	4575	284
200	200	8719	383
250	250	14596	482

5.1. Учёт TWIRL

Если машина TWIRL станет реальной и будут достигнуты успехи в распараллеливании при сокращении числа строк в процессе разложения на сомножители, по самым скромным оценкам значения в первом столбце таблицы уменьшатся на 11 битов, т. е. для получения уровня безопасности в 89 битов потребуется использовать модули RSA размером около 1900 битов.

6. Вопросы безопасности

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

7. Литература

7.1. Нормативные документы

[DL] Dodson, B. and A. K. Lenstra, NFS with four large primes: an explosive experiment, Proceedings Crypto 95, Lecture Notes in Comput. Sci. 963, (1995) 372-385.

[ECS] Eastlake, D., Crocker, S. and J. Schiller, «Randomness Recommendations for Security», RFC 1750, December 1994.

[GIL98] Cracking DES: Secrets of Encryption Research, Wiretap Politics & Chip Design , Electronic Frontier Foundation, John Gilmore (Ed.), 272 pages, May 1998, O’Reilly & Associates; ISBN: 1565925203

[GOR93] Gordon, D., «Discrete logarithms in GF(p) using the number field sieve», SIAM Journal on Discrete Mathematics, 6 (1993), 124-138.

[LEN93] Lenstra, A. K. and H. W. Lenstra, Jr. (eds), The development of the number field sieve, Lecture Notes in Math, 1554, Springer Verlag, Berlin, 1993.

[MH81] Merkle, R.C., and Hellman, M., «On the Security of Multiple Encryption», Communications of the ACM, v. 24 n. 7, 1981, pp. 465-467.

[ODL95] RSA Labs Cryptobytes, Volume 1, No. 2 — Summer 1995; The Future of Integer Factorization, A. M. Odlyzko

[ODL99] A. M. Odlyzko, Discrete logarithms: The past and the future, Designs, Codes, and Cryptography (1999).

[POL78] J. Pollard, «Monte Carlo methods for index computation mod p», Mathematics of Computation, 32 (1978), 918-924.

[RFC2409] Harkins, D. and D. Carrel, «The Internet Key Exchange (IKE)», RFC 2409, November 1998.

[SCH95] R. Schroeppel, et al., Fast Key Exchange With Elliptic Curve Systems, In Don Coppersmith, editor, Advances in Cryptology — CRYPTO 31 August 1995. Springer-Verlag

[SHAMIR03] Shamir, Adi and Eran Tromer, «Factoring Large Numbers with the TWIRL Device», Advances in Cryptology — CRYPTO 2003, Springer, Lecture Notes in Computer Science 2729.

[SIL00] R. D. Silverman, RSA Laboratories Bulletin, Number 13 — April 2000, A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths

[SILIEEE99] R. D. Silverman, «The Mythical MIPS Year», IEEE Computer, August 1999.

8. Адреса авторов

Hilarie Orman

Purple Streak Development

500 S. Maple Dr.

Salem, UT 84653

EMail: hilarie@purplestreak.com, ho@alum.mit.edu

Paul Hoffman

VPN Consortium

127 Segre Place

Santa Cruz, CA 95060 USA

EMail: paul.hoffman@vpnc.org

9. Полное заявление авторских прав

Copyright (C) The Internet Society (2004). К этому документу применимы права, лицензии и ограничения, указанные в BCP 78, и, за исключением указанного там, авторы сохраняют свои права.

Этот документ и содержащаяся в нем информация представлены «как есть» и автор, организация, которую он/она представляет или которая выступает спонсором (если таковой имеется), Internet Society и IETF отказываются от каких-либо гарантий (явных или подразумеваемых), включая (но не ограничиваясь) любые гарантии того, что использование представленной здесь информации не будет нарушать чьих-либо прав, и любые предполагаемые гарантии коммерческого использования или применимости для тех или иных задач.

Интеллектуальная собственность

IETF не принимает какой-либо позиции в отношении действительности или объема каких-либо прав интеллектуальной собственности (Intellectual Property Rights или IPR) или иных прав, которые, как может быть заявлено, относятся к реализации или использованию описанной в этом документе технологии, или степени, в которой любая лицензия, по которой права могут или не могут быть доступны, не заявляется также применение каких-либо усилий для определения таких прав. Сведения о процедурах IETF в отношении прав в документах RFC можно найти в BCP 78 и BCP 79.

Копии раскрытия IPR, предоставленные секретариату IETF, и любые гарантии доступности лицензий, а также результаты попыток получить общую лицензию или право на использование таких прав собственности разработчиками или пользователями этой спецификации, можно получить из сетевого репозитория IETF IPR по ссылке http://www.ietf.org/ipr.

IETF предлагает любой заинтересованной стороне обратить внимание на авторские права, патенты или использование патентов, а также иные права собственности, которые могут потребоваться для реализации этого стандарта. Информацию следует направлять в IETF по адресу ietf-ipr@ietf.org.

Подтверждение

Финансирование функций RFC Editor обеспечено Internet Society.

---

Перевод на русский язык

Николай Малых

nmalykh@protokols.ru

---