Обманчиво простой и интересный RSA

Недавно, читая книгу Real-World Cryptography, я узнала об атаке Блейхенбахера, иначе называемой атакой миллионом сообщений. Этот вид атаки Даниэль Блейхенбахер продемонстрировал в 1998 году, взломав RSA через функцию шифрования PKCS #1. В книге об этой атаке было сказано немного, поэтому я решила изучить её сама и в конечном итоге реализовать.

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

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

▍ А что вообще такое RSA?

RSA был назван в соответствии с именами своих создателей Ривест, Шамир и Адлеман (Rivest, Shamir, Adleman) и представляет собой криптосистему с открытым ключом, отличную по своему принципу от систем с симметричным ключом. В случае симметричных систем шифрования отправитель и получатель обладают одним ключом, который они используют для шифрования/дешифровки сообщений. При этом в системах с открытым ключом мы оперируем парой ключей, открытым и закрытым (секретным).

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

Однако симметричное шифрование, как правило, работает очень быстро, и некоторые связанные с ним операции даже закладываются на аппаратном уровне. Было бы здорово по возможности использовать именно эту схему ради её эффективности.

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

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

Но мы, к сожалению, всё ещё сталкиваемся с RSA, который, между прочим, является весьма занятным историческим артефактом! Так что, думаю, он вполне заслуживает изучения, да и реализовать его забавы ради тоже круто!

▍ Основы RSA

RSA – это удобная элегантная криптосистема. В основе её безопасности лежит вычислительная сложность задачи факторизации произведений больших простых чисел. Причём в истории не зафиксировано ни одного взлома её исходной формы². Тем не менее, как говорилось выше, в зависимости от метода шифрования данных некоторые частные её вариации могут быть взломаны.

Внутренне она состоит из трёх основных несложных операций:

1. Генерация ключей.
2. Шифрование/дешифровка.
3. Кодирование сообщений.

И далее мы разберём каждый из них.

▍ Генерация ключей

Начнём с того, что вообще такое ключ? Мы знаем, что он используется для шифрования/расшифровки сообщений, но из чего он состоит?

В случае RSA ключ содержит два числа, экспоненту и модуль, и может выглядеть, например, так: (exp=3, mod=3233). То есть это просто пара чисел³.

Выбор терминов экспонента и модуль объясняется тем, как эти значения используются. RSA задействует модульную арифметику. Как мы далее увидим, эти числа представляют экспоненты и модули для операций шифрования/дешифровки.

Для генерации ключа нужно выполнить несколько шагов:

1. Выбрать два простых числа, которые мы назовём p и q, после чего вычислить n = p * q.
2. Вычислить значение t = lcm(p-1, q-1). Это функция Эйлера, значение которой мы используем в качестве модуля только для генерации ключей и нигде более.
3. Выбрать открытую экспоненту, которую мы назовём e. Эта экспонента должна быть больше 2 и не иметь общих множителей с t. В качестве простого варианта можете начать с 3 и двигаться вверх по шкале простых чисел, пока не найдёте значение, взаимно простое относительно t. Нередко также просто выбирают 65537, поскольку оно достаточно мало для эффективного шифрования и при этом достаточно велико для избежания некоторых конкретных атак.
4. Вычислить секретную экспоненту, которую мы назовём d. Вычисляем мы её как d = e^-1 mod t, то есть обратное e в модуле.

Теперь у нас есть d, e, секретная и открытая экспоненты, а также n, модуль. Совмещаем всё это в два кортежа и получаем наши ключи!

Разберём короткий пример, чтобы понять, как это происходит. В качестве простых чисел выберем p = 17 и q = 29, получив на их основе n = 493.

Теперь вычислим t = lcm(17 - 1, 29 - 1) = lcm(16, 28) = 112. Выбираем e = 3. Оно вполне подходит, так как 2 < 3 и gcd(3, 112) = 1, что говорит об отсутствии у них общих множителей. Далее вычисляем⁴ d = e^-1 = 3^-1 = 75 mod 112 и получаем ключи!

В качестве открытого ключа мы получили (exp=3, mod=493), а в качестве секретного – (exp=75, mod=493). Мы используем их повторно в примерах шифрования/дешифровки.

▍ Шифрование/дешифровка сообщения

Теперь, когда у нас есть ключи, можно с их помощью зашифровывать/расшифровывать сообщения. Обычно мы рассматриваем сообщение как нечто вроде «hello, world», но для RSA каждое сообщение представляет одно целое число. Пока предположим, что нас это устраивает, но позже вернёмся к процессу получения целого числа из сообщения.

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

Для его шифрования мы возьмём из открытого ключа экспоненту e и модуль n, вычислив с их помощью шифротекст: c = m^e mod n. Таким образом мы получим ещё одно целое число, которое можно будет отправить получателю.

Для его расшифровки получатель сможет использовать экспоненту d и тот же модуль n из секретного ключа, вычислив открытый текст сообщения по формуле m = c^d = (m^e)^d mod n. После выполнения этой операции экспоненты взаимно ликвидируются (можете поверить мне на слово или, хотя бы, Ривесту, Шамиру и Адлеману).

В качестве примера мы что-нибудь зашифруем и расшифруем. Предположим, что по неким субъективным причинам наше сообщение – это m=42. Чтобы расшифровать его с помощью полученных ранее ключей, мы вычисляем c = m^e = 42^3 = 138 mod 493. А чтобы расшифровать наш шифротекст, вычисляем m = c^d = 138^75 = 42 mod 493.

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

▍ Как кодировать сообщения?

Хорошо, как же нам прийти от строки символов вроде «hello, world» к целому числу? Мы её закодируем! И если сообщение получится слишком большим для представления одним числом, мы разделим его на несколько и закодируем каждое.

В памяти компьютера всё представлено в виде простых байтов. Неважно, что вы используете – строку символов или какое-либо число – внутренне это будет просто массив байтов. Именно этот фундаментальный принцип и поможет нам навести мосты между столь разными видами данных.

Чтобы не усложнять, предположим, что используем 64-битные целые числа. В таком случае каждое из них будет занимать 8 байт. При этом наше сообщение «hello, world» состоит из 12 байт.



У каждого символа своё байтовое значение. Здесь мы предположим, что они закодированы с помощью ASCII. Символы в этой кодировке удобно конвертируются в 8-битные целые числа, или одиночные байты.



Теперь можно превратить это в два байтовых массива с длиной 8. Первые 8 байт сообщения станут одним массивом, а остальные 4 – вторым. Второй мы дополним нулями влево, хотя это можно сделать и вправо. В любом случае, сделать это необходимо, после чего нужно будет придерживаться выбранного способа кодирования: от младшего байта к старшему или от старшего к младшему.



Теперь, поскольку эти массивы размером по 8 байт, их можно использовать в качестве хранилища для 64-битных целых чисел, которые будут выглядеть как 7522537965569712247 и 1869769828 соответственно. Каждое из них можно зашифровать (используя ключ с достаточно большим модулем), и дело в шляпе!

На практике же вам следует использовать одну из других схем кодирования. Достаточно долго популярностью пользовалась PKCS #1, но в ней есть недочёты. В частности, из-за неё возникли проблемы в некоторых версиях SSL. Сейчас PKCS доработали, но применять её всё равно не рекомендуется, так как это вынудит вас использовать RSA. (Да, я буду и дальше напоминать всем, что RSA применять не стоит).

▍ Что я для себя узнала

В ходе реализации RSA я выяснила много интересного и поделюсь с вами ключевыми выводами:

• Реализация криптосистемы – это прикольно. И это, пожалуй, одно из основных заключений эксперимента. Как-то раз мне понадобилось срубить дерево, и полученное в процессе удовольствие полностью совпало с моими ожиданиями. И здесь то же самое: я долго представляла себе, как это будет здорово, но всё время боялась. В итоге, окунувшись в процесс, я поняла, что это вовсе не страшно, а очень даже интересно.
• Уязвимости могут обнаруживаться во множестве тонких аспектов. Мы используем библиотеки, выполняющие операции за константное время, чтобы избежать атак по времени. Атака Блейхенбахера строится на возможности обнаружения некорректности кодировки и может использовать любой малейший сигнал о недочётах в ней. Уязвимости могут обнаруживаться и во многих других аспектах. Это напоминает мне, почему в криптографии необходимо опираться на глубокий опыт, а не создавать самопальные алгоритмы.
• Я до сих пор путаюсь с порядком байтов little-endian и big-endian. Постоянно забываю, какой из них и что означает. Думаю, надо уже написать по этой теме статью в качестве личной справки.
• Отлаживать такое нелегко! Например, изначально я не учла требование, чтобы сообщение было меньше модуля, и в результате получала внезапные сбои в зависимости от выбранных простых чисел и сообщения. Это привело к сложностям при отладке, с которыми удалось справиться путём установки постоянно малых значений p и q. Возникло ещё несколько трудных моментов, и я думаю, они были не исчерпывающими.
• Приёмы безопасности могут идти вразрез с эргономикой. Использованная мной библиотека bigint содержит множество приёмов безопасности: операции, выполняющиеся за константное время; проверяемые операции, вычисления по модулю; и так далее. Но порой бывает сложно читать код, написанный с их использованием, так как приходится явно выражать задействуемые операции. Здесь можно добиться некоторых улучшений, но, по всей видимости, подобные сложности неизбежны.
• Понятность текстов RFC и работ по криптографии… Я была удивлена, когда прочитала работу Блейхенбахера, и она показалась мне не такой уж сложной. У меня есть степень в области математики, но с криптографией работать особо не доводилось (да и с момента получения степени прошло уже десять лет), так что это был вдохновляющий опыт! RFC (Request for Comments, рабочее предложение) для PKCS тоже оказалось вполне понятным, что не может не радовать.

▍ Дальнейшие планы

Теперь у меня есть своя игрушечная реализация RSA и PKCS, так что пора заняться тем, для чего я всё это и затеяла: взломом. Сама реализация опубликована на crates.io, а её исходный код доступен здесь. В следующей статье я расскажу о развёртывании атаки и покажу демо.

Возможно, я также обращу внимание на некоторые другие классические криптосистемы.
Например, мне приглянулся протокол Диффи-Хеллмана.

Если вы тоже занимались реализацией криптосистем ради спортивного интереса, пишите мне на [e-mail], буду рада на них взглянуть.

▍ Сноски

1. Секретный ключ также можно использовать для генерации электронной подписи, впоследствии проверяемой с помощью открытого ключа.↩
2. Разве что с помощью квантовых компьютеров, но до этого ещё минимум несколько лет, если верить прогнозам экспертов … ↩
3. Вы также можете передавать вместе с ключом метаданные, уточняющие дополнительную информацию вроде использованной криптосистемы, размера ключа, кодировок и так далее. ↩
4. Здесь для вычисления я использовала Wolfram Alpha, но есть и другие подходящие для этого алгоритмы. ↩

Скидки, итоги розыгрышей и новости о спутнике RUVDS — в нашем Telegram-канале ?