Забудьте про RSA. В хрупкой криптосистеме слишком много способов выстрелить себе в ногу

tj3sdjaibi0gn1yjo5i6so8evje.jpeg

Кадр из доклада Бена Переза на конференции SummerCon 2019

Опубликованный в 1977 году алгоритм RSA стал революционным для своего времени. В том же году был представлен протокол Диффи — Хеллмана для обмена ключами, а со временем криптосистемы с открытым ключом стали мейнстримом. До сих пор самой популярной среди них является RSA, названная по именам трёх авторов, которые опубликовали алгоритм: Ривест, Шамир и Адлеман.

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


Алиса для генерации должна выбрать два простых числа $p$ и $q$, произведение которых называется «модулем»: $N = pq$. Затем она выбирает открытую экспоненту $e$ и секретную экспоненту $d$ таким образом, что $ed = 1 \mod (p-1)(q-1)$. В принципе, $e$ и $d$ должны быть обратными друг другу.

После выбора параметров пользователь Боб может отправить Алисе сообщение $M$, вычислив $C = M^e (\mod N)$. Алиса может расшифровать этот текст, вычислив $M = C^d (\mod N)$. И наоборот, если Алиса хочет подписать сообщение $M$, она вычисляет $S = M^d (\mod N)$. Любой пользователь может удостовериться в аутентичности подписи, проверив $M = S^e (\mod N)$.

Прочность криптосистемы RSA основана на сложности факторизации натуральных чисел. Разложение на множители изучалось с античности, так то любой прорыв в это математической дисциплине станет громкой новостью. С другой стороны, конкретно для этой задачи созданы специализированные алгоритмы, такие как Quadratic Sieve и General Number Field Sieve, а закон Мура вынуждает постоянно увеличивать размер ключа, что делает RSA, возможно, не самым оптимальным вариантом для будущего криптографии. Альтернативный вариант — криптография на эллиптических кривых.
На портале поддержки GlobalSign, можно найти краткую информацию о ECC, плюсах, отличии от RSA и генерации ключей.
К сожалению, пока еще не все стали задумываться о преимуществах ECC. Так, один наш крупный клиент, социальная сеть Рунета, год назад довольно серьезно решил подойти к защите данных пользователей, использовав ECC для защиты своих доменов и поддоменов. Однако столкнулся с тем, что не все международные УЦ смогли предложить поддержку генерации SSL-сертификатов с ключами на эллиптических кривых. Почему — для нас на тот момент осталось вопросом.

Но RSA критикуют не за теоретические уязвимости, а за проблемы с практической реализацией.

Доклад на эту тему прочитал инженер по безопасности Бен Перез (Ben Perez) на недавней конференции SummerCon 2019. Он приводит несколько доводов, что эта «хрупкая криптосистема предлагает много способов выстрелить себе в ногу». Да, у RSA прочная теоретическая основа, но на практике разработчики очень часто принимают рискованные решения: «Хотя теоретически возможно правильно реализовать RSA, но десятилетия разрушительных атак доказали, что такой подвиг может быть недостижим на практике».

Ниже перечислены типичные ошибки разработчиков.


Безопасность RSA основана на том факте, что (большое) число $N$, которое является произведением двух простых чисел $p$ и $ q$, трудно разложить на множители. Разработчики несут ответственность за выбор простых чисел. Этот чрезвычайно медленный процесс, по сравнению с генерацией ключей для других криптографических протоколов, где достаточно выбрать несколько случайных байтов. Поэтому вместо генерации действительно случайных простых чисел разработчики часто пытаются сгенерировать числа определённого вида. Это плохо кончается.

Например, если $p$ и $q$ хоть где-то используются повторно, то их можно легко вычислить. Плохие генераторы случайных чисел делают этот сценарий довольно распространённым. Исследование показало, что примерно 1% трафика TLS в 2012 году было уязвимо для такой атаки. Кроме того, $p$ и $q$ следует выбирать независимо, иначе их тоже будет легко подобрать. Даже выбор алгоритма проверки простых чисел имеет последствия для безопасности.

То есть надёжный выбор простых чисел — сама по себе нетривиальная задача. Один из самых известных примеров — уязвимость ROCA в RSALib, которая затронула многие смарт-карты, криптопроцессоры Trusted Platform Module и даже ключи Yubikey. Там для ускорения вычислений при генерации ключей использовались только простые числа определённой формы.


Поскольку выбор большого закрытого ключа негативно влияет на скорость расшифровки и подписи, у разработчиков есть стимул выбирать маленькую секретную экспоненту $d$, особенно на маломощном железе типа смарт-карт. Но это позволяет злоумышленнику восстановить секретный ключ, что было продемонстрировано в реальных атаках.
Как и в случае с секретной экспонентой, разработчики пытаются использовать маленькие открытые публичные экспоненты для ускорения шифрования и проверки. Часто они выбирают $e = 3$, что приводит к множеству уязвимостей в криптосистемах RSA.

maqgt38vhhr7ffrm9dhcb1ivc8e.png
Иногда разработчики даже используют $e = 1$, что фактически аннулирует шифрование текста. Скриншот из доклада Бена Переза на конференции SummerCon 2019


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

К сожалению, для заполнения чаще всего используется схема PKCS #1 v1.5, уязвимая для атак типа padding oracle.

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

Хотя уязвимость в PKCS #1 v1.5 обнаружили в далёком 1998 году, от неё до сих пор страдают многие реальные системы.

Конечно, алгоритм RSA тут ни при чём, но суть в том, что заполнение (padding) — абсолютно необходимая процедура при использовании RSA, что добавляет лишнюю сложность в криптосистему.

Шпаргалка Mozilla по протоколам безопасности


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

Ниже краткая шпаргалка Mozilla по внедрению протоколов безопасности. Во второй колонке указана важность защиты (security benefit), в третьей — сложность реализации (implementation difficulty).

40c2gj9vhlzunk3_jona_ciy8_4.png

В четвёртой колонке указан порядок реализации протоколов со стороны веб-разработчика или администратора. Это рекомендуемый порядок, основанный на комбинации важности защиты и простоты реализации (разработка и поддержка).

HTTPS предполагается как обязательный протокол для всех сайтов.

Для настройки SSL/TLS удобно воспользоваться инструментом SSL Configuration Generator от Mozilla. Он предлагает для серверов три конфигурации:

  • Современная: для работы с клиентами, которые поддерживают TLS 1.3, без обратной совместимости. В данный момент поддерживает Firefox 63+, Android 10+, Chrome 70+, Edge 75+, Java 11+, OpenSSL 1.1.1, Opera 57+, Safari 12.1+.
  • Промежуточная: рекомендуемая конфигурация для большинства серверов.
  • Устаревшая: доступ к сервису осуществляется с помощью очень старых клиентов или библиотек, таких как Internet Explorer 8 (Windows XP), Java 6 или OpenSSL 0.9.8.

Так, в современной конфигурации рекомендуется тип сертификатов ECDSA (P-256) вместо RSA (2048 бит).

«RSA был важной вехой в защите коммуникаций, но последние два десятилетия криптографических исследований сделали его устаревшим. Алгоритмы на эллиптических кривых для обмена ключами и цифровых подписей стандартизированы ещё в 2005 году и с тех пор интегрированы в интуитивно понятные и устойчивые к неправильному использованию библиотеки, такие как libsodium. Тот факт, что RSA по-прежнему широко используется, говорит о неспособности криптографов адекватно сформулировать риски RSA, а также о переоценке со стороны разработчиков своей способности успешно применять эту криптосистему, — делает вывод Бен Перез. — В конечном счёте, за всё заплатят пользователи. Вот почему мы должны согласиться, что использовать RSA в 2019 году абсолютно неприемлемо. Без исключений».



j3fzjqwuao9tzbwzdcxr_kgdzbc.jpeg

Дата: 2019-07-19 11:29:22

Источник: https://habr.com/ru/post/460657/