[Перевод] Взломают ли 2048-битный RSA к 2030 году31.07.2023 15:46

Я пришёл к выводу, что 2048-битный криптографический алгоритм RSA достаточно безопасен, когда работал над недавним проектом. Канада1), в которой я живу, да и другие страны2), заявили, что 2048-битный RSA будет считаться потенциально небезопасным после 2030 года. Минимальная длина надежного ключа — это 3072 бита. Осталось всего семь лет до нового стандарта.

Откуда взялся 2030 год?

Я практически уверен, что мысль о конце эпохи в 2030-м почерпнута из научной статьи 2004 года Арьена Ленстры3). Он предложил такую датировку сроков истечения безопасности:

Сроки жизни распространенных длин ключей RSA в битах. Таблица 4 из Key Lengths

Дата отсечки по 2048-битному ключу при консервативной оценке — 2030 год. Просто, прямолинейно и определенно. Отличная таблица для долгосрочного планирования…

Прогноз Ленстры в основном базировался на двух наблюдениях:

• Производительность вычислительных технологий удваивается каждые 18 месяцев;

• Благодаря совершенствованию ПО рост эффективности факторизации удваивается каждые 18 месяцев;  

С 2004 по 2030 год пройдёт 26 лет или 312 месяцев, произойдёт 35 удваиваний. То есть увеличение мощности в экспоненциальном представлении составит 2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2, или 235. Иными словами, по прогнозу, к 2030 году мощность вырастет в 34 359 738 368 раз, то есть примерно в 34 миллиарда (34×109) раз. Это значение показывает, насколько неуязвимым было 2048-битное шифрование RSA в 2004 году.

Вот как этот рост выглядит на графике:

Удвоение каждые 9 месяцев с 2004 по 2030 год

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

Некого человека должны были наградить зерном. Он попросил, чтобы в качестве награды выполнили определенные действия и передали ему получившееся в их результате количество зерна:

Положить на первую клетку шахматной доски одно зерно. На следующую пустую клетку положить удвоенное количество зёрен (2). Затем удвоить это количество зёрен (4) на следующей пустой клетке. Если заполнить все 64 клетки шахматной доски, каждый раз удваивая количество, то получим количество пшеницы, в тысячи раз превышающее ежегодное производство пшеницы на всей планете. Очевидно, что этот процесс невозможно было выполнить. Этому мешает экспоненциальная природа роста4). «Экспоненциальный рост не может продолжаться вечно, потому что поглотит всё» — Карл Саган, Миллиарды и миллиарды: Мысли о жизни и смерти на краю тысячелетия

Теперь, когда мы видим, как спрогнозирован экспоненциальный рост мощности RSA5), важно определить, возник ли предел, который бы помешал этому прогнозируемому росту.

Как на самом деле происходит развитие?

Удобнее всего здесь рассмотреть длину чисел, которые уже разложили на множители. Пока самое большое число длиной 829 битов6) было разложено на множители в 2020 году. В конце 2003 года было разложено на множители 576-битное число. 

Я не стал обращать внимание на тот факт, что рост мощностей факторизации после 2009 года замедлился, и добавил линейную экстраполяцию на основании рекордов факторизации на весь прогнозируемый интервал. Однако результат (1024 бита к 2030 году) меня всё равно разочаровал. Если бы мощности росли экспоненциально, можно было бы ожидать более четкого тренда. Такого тренда роста недостаточно, чтобы считать, что 2048-битный RSA окажется под угрозой к 2030 году.

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

Насколько справедливы сейчас базовые гипотезы?

Давайте рассмотрим две базовые гипотезы, на которых основан прогноз:

Производительность алгоритмов факторизации

Гипотеза заключается в том, что рост эффективности факторизации вследствие совершенствования ПО удваивается каждые 18 месяцев.

Обычно невозможно спрогнозировать рост эффективности ПО. Можно безопасно предположить, что будет возможен некий прирост производительности конкретной программной системы, но не его величина и время. В очень обобщённом виде, рост производительности ПО, похоже, состоит из трёх фаз:

То есть совершенствование сначала даётся легко (фаза «самое очевидное») и всё сложнее (во фазе «труднодоступное»). За такое улучшение приходится расплачиваться повышением сложности. На каком-то этапе кто-то может изобрести новый алгоритм, после чего цикл продолжится. Улучшение, создаваемое новым алгоритмом, может быть очень большим; возможно, достаточным, чтобы считать его экспоненциальным, если оно происходит несколько раз.

Именно так и происходило с алгоритмами факторизации в 80-х и 90-х7). За алгоритмом факторизации методом непрерывных дробей последовал метод квадратичного решета, который, в свою очередь, сменил общий метод решета числового поля (number field sieve, NFS). На момент публикации статьи Ленстры казалось, что его метод факторизации при помощи эллиптических кривых сможет превзойти по мощности алгоритм NFS.

За 19 лет с 2004 по 2023 год и при гипотезе об удвоении каждые 18 месяцев мы бы получили прогнозируемый рост производительности алгоритмов в 6502 раз. Сложно найти точные показатели настоящего роста производительности алгоритмов за этот интервал, потому что он смешан с аппаратной производительностью. Система CADO-NFS8) заявляет о росте в 3,2 раза с версии 1.1 до версии 2.3.0 на уровне 512 битов (RSA-155). Исследователи, поставившие последние рекорды факторизации9) (829 битов), утверждают, что производительность увеличилась в 3–4 раза. Даже если комбинировать этот рост (не уверен, приемлемо ли это), мы получаем рост производительности в 12 раз, что сильно отличается от спрогнозированных 6502 раз.

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

История компьютерных вычислений показывает, что обычно происходит быстрый всплеск прогресса производительности алгоритмов, когда становится возможным выполнение определённой задачи, а затем следует долгий период постепенного совершенствования. Очень хорошим примером является сортировка. Алгоритмы mergesort, quicksort и heapsort были изобретены, соответственно, в 1945, 1959 и 1964 году. Они по-прежнему активно используются для сортировки больших списков значений. В ретроспективе кажется, что почти то же самое происходит в мире алгоритмов факторизации. Сложность здесь высока (CADO-NFS содержит сотни тысяч строк кода), поэтому мы, скорее всего, находимся в фазе «труднодоступное». На данном этапе, похоже, нет причин ожидать спрогнозированного экспоненциального роста производительности алгоритмов факторизации (в 165140 раз), необходимого для того, чтобы представлять угрозу 2048-битному RSA к 2030 году.

Производительность вычислений

Прогноз основан на гипотезе, что вычислительная мощность удваивается каждые 18 месяцев.

Эта гипотеза известна под названием «Закон Мура»10). Сегодня стало модно говорить, что закон Мура уже мёртв. Это и правда, и неправда.

Существует две версии закона Мура. Версия с удвоением каждые 18 месяцев относится к вычислительной мощи и применима к нашим рассуждениям. В исходном виде закон Мура относился к количеству транзисторов на подложке определённого размера; сегодня принято, что в среднем оно удваивается каждые 24 месяца. Закон 24 месяцев, связанный с количеством транзисторов, по-прежнему актуален (но частота примеров быстро снижается). Мёртв именно закон об удвоении производительности каждые 18 месяцев. А на нём основывается прогноз о 2030 годе…

Если удвоить количество транзисторов на подложке определённого размера, то если энергопотребление этих новых транзисторов будет вдвое меньше энергопотребления старых, тогда подложка будет излучать то же количество тепла. Закон масштабирования Деннарда подтверждает справедливость этого утверждения. В противном случае, каждое удвоение транзисторов повышало бы количество тепла на той же площади. И с этим теплом мы бы скоро перестали справляться. Версия закона Мура с удвоением производительности за 18 месяцев зависит от справедливости закона Деннарда, однако он уже не работает, поэтому закон Мура о 18 месяцах мёртв.

На этом графике показан пример с процессорами Intel:

Из статьи The death of CPU scaling: From one core to many — and why we’re still stuck

… основанной на The Free Lunch Is Over — A Fundamental Turn Toward Concurrency in Software

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

Вот и он, физический предел, мешающий экспоненциальному росту. Оглядываясь назад, можно увидеть, что этот предел уже мешал экспоненциальному росту в 2004 году, когда был сделан прогноз. Неподходящее время для прогнозов, но это сильно упрощает нашу задачу. Экспоненциального роста вычислительных мощностей с 2004 по 2023 год не было. И очень маловероятно, что такой рост произойдёт за семь лет перед 2030 годом.

Какова ситуация сейчас?

Как выглядит ситуация со взломом 2048-битного RSA сегодня, в 2023 году?

Лучший известный нам алгоритм, который можно использовать в самых мощных изготавливаемых нами компьютерах — это NFS. Поэтому мы возьмём его.

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

Майнинг Bitcoin — это процесс, зарабатывающий деньги для субъекта, исполняющего систему майнинга. Эта финансовая мотивация создала ситуацию, при которой сеть майнинга разрослась до огромных размеров. Финансовый стимул очень чувствителен к стоимости электричества. Поэтому системы майнинга спроектированы настолько энергоэффективными, насколько это возможно. В этой ситуации крайне актуален закон Деннарда. Создающее проблемы тепло начинается с дорогого электричества. Даже несмотря это отчаянное стремление к энергоэффективности, по оценкам, сеть майнинга Bitcoin в 2021 году потребляла 1/200 (0,5%) от электричества, генерируемого на всей планете11). Это превращает сеть в хороший верхний предел того, что можно делать втайне. Если бы какое-то государственное агентство исследования сигналов нарастило бы такую вычислительную мощь, мы бы смогли узнать это, просто посмотрев её счета за электричество. Потребление электричества на уровне целой страны невозможно было бы скрыть.

Представим, что нам волшебным образом удалось перенаправить вычислительную мощь всей сети майнинга Bitcoin на взлом одного 2048-битного ключа RSA. Для этого нам нужно будет соотнести то, чем сейчас занимается сеть, с алгоритмом NFS. Я буду сравнивать сопоставимое соотношение, разработанное в RFC376612). Оно основывается на ситуации, актуальной на 2004 год, но лучшего нам, похоже, не найти. Выполняемые сетью Bitcoin операции требуют приблизительно того же количества вычислений, что и используемые в качестве справочных в RFC376613). По RFC3766 для взлома 2048-битного RSA потребовалось бы 9,01×1030 криптографических операций. Сеть майнинга Bitcoin недавно достигла частоты 1,24×1028 операций/год14).

То есть воспользовавшись мощью самой большой сети, занимающейся взломом криптографических операций, нам бы понадобилось 9,01×1030/1,24×1028 лет для взлома одного ключа RSA. Это даёт 727 лет. Если бы волшебным образом смогли создать достаточно оборудования для взлома ключа RSA за год, то нам бы понадобилось 727/200, или в 3,6 раз больше электричества, чем генерируется на планете.

Так мы только сравнили объём вычислительной мощи, необходимый для взлома 2048-битного RSA, с вычислительной мощью сети майнинга Bitcoin. Однако выполняемые сетью Bitcoin операции требуют очень мало памяти, а алгоритму NFS нужны огромные объёмы памяти. В 2004 году Р.Д. Силверман отверг заявление о надвигающейся угрозе компрометации 1024-битного RSA. В частности, он сказал, что алгоритм NFS имеет этап (приведение матрицы), требующий большой вычислительной мощи, тесно связанной с большим количеством памяти. На основании этого утверждения он предсказал, что 1024-битный RSA не будет публично взломан до 2030-х. Пока этот прогноз кажется верным. Также он сказал, что для 2048-битного RSA потребуется 1018 байтов памяти на этап приведения неразложимой матрицы15). Это миллион терабайтов — невообразимый объём находящейся в одном месте памяти, более-менее тесно связанный с достаточной вычислительной мощью. К слову о памяти: скорость DRAM сильно отстаёт от скорости процессоров (примерно в сотню раз меньше), а алгоритмы просеивания решетом, скорее всего, очень неудобны для кэширования. Поэтому мысль о том, что вычислительная мощь сети Bitcoin сможет взломать один 2048-битный ключ RSA всего за 727 лет, безнадёжно оптимистична.

Очевидно, что 2048-битный RSA находится далеко за пределами возможностей современных технологий с лучшим из алгоритмов (NFS)…

Будущее

Похоже, обязательным условием для угрозы безопасности RSA 2048 должен стать прорыв в алгоритмах. Насколько вероятен такой прорыв?

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

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

Квантовые вычисления

Тот вид квантовых вычислений, который необходим для взлома RSA, требует прогресса и в вычислительной мощи, и в алгоритмах. Обычно сначала изобретается какая-то новая компьютерная технология, после чего проектируются алгоритмы для выполнения этой технологией чего-то полезного. Угроза квантовых вычислений для RSA в этом отличается. У нас уже есть алгоритм (Шора), но компьютер, способный его исполнять, существует пока только в нашем воображении.

Если бы кто-то изобрёл такой компьютер, то RSA 2048 сразу же можно было взломать тривиальным образом. RSA 3072 тоже можно было бы тривиально взломать. То же самое относится к RSA 4096 и 8192. Очевидно, что угроза сейчас только гипотетическая, но это служит примером ситуации, когда обычное увеличение длины ключа не обеспечит никакой реальной ценности. Многократно увеличивая размеры ключей, мы делаем ставку на то, что будет ровно таким, чтобы смочь взломать устаревшую длину ключа, но не взломать актуальную. Это кажется маловероятным.

Новые угрозы обычно принимают другую форму, нежели старые…

Заключение

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

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

Эта цитата взята из ранее показанной таблицы «Common RSA modulus bit-length life spans» научной статьи Ленстры. Если вы мне не верите, то должны поверить доктору А.К. Ленстре, придумавшему прогноз двойного экспоненциального роста. Мы должны непрерывно ждать и наблюдать. Любые изменения политик должны вноситься в ответ на изменения в производительности алгоритмов и вычислительного оборудования.

Это важно, потому что аспекты наподобие длины ключа часто глубоко внедрены в системы, защищаемые соответствующей криптографией. Изъятие и замена таких систем обычно очень дорога во всех системах с криптографической защитой. Если это невозможно на программном уровне, то требуется полная замена оборудования. Время и ресурсы, потраченные на бессмысленное увеличение длины ключей, выгоднее было бы использовать на что-то ещё. Более длинные ключи RSA требуют больше вычислительных ресурсов для обработки, поэтому бессмысленное увеличение длины ключей приводит и к пустой трате вычислительных ресурсов и энергии.

Другие системы

Пока для удобства чтения мы исследовали только RSA. Давайте воспользуемся приведёнными рассуждениями для краткого изучения некоторых других популярных криптографических систем. В качестве практического примера я использую рекомендации NIST17)18). Период для всех этих рекомендаций NIST: с 2019 по 2030 год (11 лет). Текущая рекомендация о длине ключей вступила в действие в 2019 году, а следующая вступит в действие в 2030 году.

Дискретное логарифмирование

Текущий размер группы: 2048 битов. Следующий размер группы: 3072 бита.

Эту задачу чаще всего используют как основу системы обмена ключами Диффи — Хеллмана.

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

На основе эллиптических кривых

Текущий размер ключа: 224 бита. Следующий размер ключа: 256 битов.

Опыт говорит, что два дополнительных бита ключа эллиптических кривых увеличивают сложность вдвое. То есть за период в 11 лет произошло (256–224)/2=16 удвоений сложности. Это подразумевает, что мощности для взлома эллиптических кривых должны удваиваться каждые 11×12/16=8,25 месяца. Это чуть быстрее, чем допущение о двойном экспоненциальном росте за 9 месяцев, происходящее из гипотезы об удвоении вычислительных мощностей и производительности алгоритмов каждые 18 месяцев. Мы знаем, что для вычислительных мощностей она не выполняется. Мне не удалось найти никаких свидетельств о существующих или ближайших прорывах в программных методах взлома эллиптических кривых, но у меня недостаточно квалификации, чтобы судить об этом, поэтому дальше рассуждать об этом не могу. В условиях отсутствия признаков прогресса в алгоритмах переход с 224 битов на 256 битов будет ненужным.

В системах на основе эллиптических кривых можно использовать гораздо более короткие длины ключей, чем в других системах. Бессмысленное увеличение длины ключей эллиптических кривых будет трагедией. Если текущие допущения останутся в силе, то к десятилетию 2040-х выпустят рекомендации о ключах длиной больше 256 битов.

Симметричное шифрование

Текущий размер ключа: 112 битов. Следующий размер ключа: 128 битов.

Вот некоторые из примеров симметричного шифрования: AES, ChaCha20 и Camellia.

В этой области сложность удваивается с каждым новым битом ключа. То есть за период 11 лет произошло 128–112=16 удвоений сложности, а значит, использовались те же ошибочные допущения, что и в случае эллиптических кривых.

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

Для взлома брутфорсом 112-битного ключа в симметричной системе требуется 2112=5,19×1033 криптографических операций. Мы сделаем разумное допущение, что одна операция Bitcoin занимает примерно то же время, что и одна операция симметричного шифрования. Тогда для расшифровки потребуется 5,19×1033/1,24×1028=418 548 лет. Для этого необходимо было бы 418 548/200= в 2092 раз больше, чем текущая генерация электричества по всей планете19).

Поэтому не кажется разумным увеличивать после 2030 года минимальный размер ключа симметричного шифрования выше 112 битов.

Сноски

1) Cryptographic algorithms for UNCLASSIFIED, PROTECTED A, and PROTECTED B Information — ITSP.40.111

2) Recommendation for Key Management (США), Règles et recommandations concernant le choix et le dimensionnement des mécanismes cryptographiques (Франция)

3) https://infoscience.epfl.ch/record/164539/files/NPDF-32.pdf|Key Lengths: Contribution to The Handbook of Information Security

4) Задача о зерне и шахматной доске

5) Факторизация — это математическая операция, необходимая для взлома шифрования RSA.

6) RSA numbers

7) A Tale of Two Sieves

8) Система CADO-NFS использовалась для установки самого последнего рекорда факторизации (829 битов).

9) Comparing the Difficulty of Factorization and Discrete Logarithm: a 240-digit Experiment

10) Закон Мура

11) Cambridge Bitcoin Electricity Consumption Index, 136.19 TWh annually May 10/2021 | U.S. Energy Information Administration, 25343 TWh annually 2021

12) Determining RFC3766: Strengths For Public Keys Used For Exchanging Symmetric Keys, 0.02*e^(1.92*cubrt (ln (n)*(ln (ln (n)))^2))/300

13) Сеть Bitcoin выполняет половину работы на операцию, поэтому при игнорировании разницы мы получаем консервативную оценку. Допущения: Crypto++ 5.6.0 Benchmarks, Bitcoin: 2 SHA-256, 16 байтов/SHA-256, 15,8 тактов/байт, 3DES: 8 байтов/3DES, 134,5 тактов/байт.

14) Blockchain.com / Total Hash Rate, 3,94×1020 хэшей Bitcoin в секунду на 12 июня 2023 года

15) A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths, section VII, subsection A.

16) Решето Эратосфена

17) Keylength — NIST Report on Cryptographic Key Length and Cryptoperiod (2020)

18) Похоже, Канада следует рекомендациям NIST.

19) Стоит заметить, что здесь не является проблемой тесная связь доступной памяти с вычислительной мощью, как в случае RSA.

© Habrahabr.ru