Атака на основе подобранного шифротекста

Атака на основе подобранного шифротекста (англ. Chosen-ciphertext attack) — криптографическая атака, при которой криптоаналитик собирает информацию о шифре путем подбора зашифрованного текста и получения его расшифровки при неизвестном ключе. Как правило, криптоаналитик может воспользоваться устройством расшифрования один или несколько раз для получения шифротекста в расшифрованном виде. Используя полученные данные, он может попытаться восстановить секретный ключ для расшифровки. Существуют шифры для которых атаки данного типа могут оказаться успешными. К их числу относятся: Схема Эль-Гамаля; RSA используемый в протоколе SSL; NTRU. Для защиты используют шифры RSA-OAEP и Cramer — Shoup.

Атака на основе подобранного шифротекста может быть адаптивной и неадаптивной.

Атака на основе неадаптивно подобранного шифротекста

При неадаптивной атаке криптоаналитик не использует результаты предыдущих расшифровок, то есть шифротексты подбираются заранее. Такие атаки называют атаками в обеденное время (lunchtime или CCA1).

Атака на основе адаптивно подобранного шифротекста

В противоположном случае криптоаналитик адаптивно подбирает шифротекст, который зависит от результатов предыдущих расшифровок (CCA2).

Атака на протоколы, базирующиеся на стандарте шифрования RSA PKCS#1

Краткое описание стандарта RSA PKCS#1

Один из представителей криптосистем с открытым ключом (Public Key Cryptography Standards) базирующихся на алгоритме RSA. Пусть k — байтовая длина модуля RSA, n. Существует много вариантов исполнения стандарта PKCS#1. В данном примере рассмотрена версия RSAES-PKCS1-v1_5 без использования цифровой подписи, второй байт блока сообщения равен 00 или 01. Стандарт может оперировать с сообщениями максимальной длины равной k — 11. Блок стандарта PKCS#1, EB, состоит из k байт. Его вид EB = 00||02||PS||00||D. Первые два байта постоянны и равны соответственно 00 и 02. PS — строка заполнения, сгенерированное псевдослучайное число, состоящее из ненулевых байтов. Для повышения уровня безопасности рекомендуется генерировать новый блок PS для каждого отдельного шифрования. Его длина, соответственно, равна k-3-|D|, где D — блок данных, |D| - его байтовая длина. Длина блока PS должна быть не менее 8-ми байтов. Блоки PS и D должны быть разделены между собой нулевым байтом. Для удобства в дальнейшем не будем конкретизировать стандарт RSAES-PKCS1-v1_5, будем обозначать его как PKCS#1. Пусть n, e — открытый ключ, а p, q, d — секретный ключ. Согласно RSA $~n=pq, d=e^{-1}mod(\phi(n))$. Блок EB преобразуется в целое число x и шифруется алгоритмом RSA, $~c = x^emod(n)$. Получатель проверяет длину шифротекста, $~c \le n$, расшифровывает его $~m = c^dmod(n)$, преобразует в блочный вид и проверяет наличие правильных первых двух байтов, разделяющего нулевого байта и длину блока PS. Если проверка не пройдена, то выдаётся ошибка.

Описание атаки

Данный пример иллюстрирует возможность успешной атаки на основе адаптивно подобранного шифротекста. Пусть у криптоаналитика есть доступ к устройству, которое для любого выбранного шифротекста показывает, имеет ли соответствующий открытый текст формат стандарта PKCS#1 и перед ним стоит задача расшифровать шифротекст C . Таким образом аналитик может подбирать различные шифротексты и отсылать их на устройство. Получив ответ, он составляет следующий шифротекст, исходя из результатов предыдущих. Таким образом, на основании ответов полученных от устройства и знаний о формате открытого сообщения, соответствующего стандарту, криптоаналитик может вычислить $~m = c^d mod(n)$. Решающим фактором в атаке являются первые два байта открытого сообщения, которые являются константами. В данном примере рассмотрен алгоритм, который минимизирует количество шифротекстов, необходимых для получения открытого сообщения. Атаку можно разделить на 3 этапа:

• Получение шифротекста $~c_0$, который соответствует сообщению $~m_0$
• Нахождение малых чисел $~s_i$, для которых шифротексты вида $~c_0*(s_i)^emod(n)$ удовлетворяют стандарту PKCS. Для каждого успешно найденного $s_i$, используя предыдущие знания об $~m_0$, аналитик вычисляет ряд интервалов, в которых должно содержаться $~m_0$.
• Нахождение ряда, состоящего только из одного интервала. В этом случае аналитик обладает достаточной информацией об $~m_0$, чтобы выбрать нужное $~s_i$, для которого $~c_0*(s_i)^emod(n)$ удовлетворяет стандарту PKCS. Величина $~s_i$ постепенно увеличивается, пока интервал не уменьшиться до одного возможного числа.

Математическое описание атаки

Предположим, что перед криптоаналитиком стоит цель узнать $~m = c^d mod(n)$. Так как k — байтовая длина числа n, тогда $~2^{8(k-1)}\le n<2^{8k}$. Аналитик выбирает число s, вычисляет $~c' = c*s^emod(n)$ и посылает $c'$ на устройство. Если устройство принимает сообщение, то нам точно известно, что первые два байта 00 и 02. Обозначим для удобства $~B = 2^{8(k-2)}$. Допустим, что s подошло, тогда верна оценка $~2B \le m*s mod(n) < 3B$. Собрав информацию такого типа мы можем найти m. Как правило, $~2^{20}$ шифротекстов будет достаточно, но это число может колебаться в широких пределах. Распишем атаку пошагово.

1. Нахождение $~s_0$. Имея целое число c, выбираем различные случайные целые числа $~s_0$, затем проверяем с помощью устройства, удовлетворяет ли выражение$~c*s_0^emod(n)$ стандарту PKCS. Для первого успешно найденного таким образом числа $~s_0$, находим $~c_0 = c*(s_0)^emod(n)$, $~M_0 = {[2B, 3B-1]}$, $~i = 1$.
2. Нахождение подходящих сообщений
   1. Начало поиска. Если i=1, тогда ищем наименьшее положительное число $~s_1 \ge \frac{n}{3B}$, для которого шифротекст $~c_0*(s_1)^emod(n)$ удовлетворяет стандарту PKCS.
   2. Иначе, если $~i > 1$ и число интервалов в $~M_{i-1}$ не менее 2-х, тогда ищем наименьшее целое число $~s_i > s_{i-1}$, для которого шифротекст $~c_0*(s_i)^emod(n)$ удовлетворяет стандарту PKCS.
   3. Иначе, если $~M_{i-1}$ содержит точно один интервал (то есть $~M_{i-1} = {[a, b]}$), тогда выбираем целые числа $~s_i r_i$, которые удовлетворяют выражениям $~r_i \ge 2\frac{bs_{i-1}-2B}{n}$ и $~\frac{2B+r_in}{b} \le s_i \le \frac{3B+r_in}{a}$, до тех пор пока шифротекст $~c_0*(s_i)^emod(n)$ не будет удовлетворять стандарту PKCS.
3. Сужение множества решений. После того как $~s_i$ найдено, ряд интервалов $~M_i$ вычисляется как $~M_i = \bigcup_{(a, b, r)}[max(a, [\frac{2B+rn}{s_i}]), min(b, [\frac{3B-1+rn}{s_i}])]$ для всех $~[a, b]\mathcal{2}M_{i-1}$ и $~\frac{as_i-3B+1}{n} \le r \le \frac{bs_i-2B}{n}$.
4. Вычисление решения. Если $~M_i$ содержит только один интервал вида $~M_i = {[a, a]}$, тогда устанавливаем $~m = a(s_0)^{-1}mod(n)$ и возвращаем m как решение $~m = c^dmod(n)$. Иначе $~i = i+1$ и переходим к шагу 2.

Первый шаг может быть пропущен если С является зашифрованным сообщением, удовлетворяющим стандарту PKCS. Во втором шаге подбор $~s_1$ начинается с $~\frac{n}{3B}$, так как для меньших величин сообщение $~m_0s_1$ не будет соответствовать стандарту PKCS. Число $~r_i \ge 2\frac{bs_{i-1}-2B}{n}$ используется, чтобы разделить интервал на каждой итерации примерно наполовину.

Анализ атаки

Оценка вероятности соответствия сообщения стандарту PKCS

Пусть вероятность того, что случайно выбранный шифротекст имеет подходящий формат открытого сообщения равна $~Pr(P\cap A)$, а $~Pr(A) = \frac{B}{n}$ — вероятность того, что для любого случайно выбранного целого числа, первые 2 байта 00 и 02. Так как $~2^8B < n < 2^{16}B$, отсюда следует, что $~2^{-16} < Pr(A) < 2^{-8}$. Модуль RSA обычно выбирается кратным 8-и. Значит $~Pr(A)$ обычн близко к $~2^{-16}$. Вероятность того, что PS блок содержит не менее 8-ми ненулевых байтов, завершающихся одним нулевым байтом равна $~Pr(P|A) = (\frac{255}{256})^8*(1-(\frac{255}{256})^{k-10})$. Предполагая, что n не менее 512 бит (k > 64), имеем $~0.18 < Pr(P|A) < 0.97$. Значит $~0.18*2^{-16} < Pr(P \cap A) < 0.97*2^{-8}$.

Оценка интервалов $~M_i$

Докажем, что $~m_0\mathcal{2}M_i$. Так как $~m_0$ соответствует стандарту PKCS, то $~2B \le m_0 \le 3B-1$, отсюда следует, что $~m_0\mathcal{2}M_0$. Предположим, что $~m_0\mathcal{2}M_{i-1}$. Значит, существует интервал $~[a, b]\mathcal{2}M_{i-1}$ с $~a \le m_0 \le b$. Так как $~m_0s_i$ соответствует стандарту PKCS, то существует такое r, что $~2B \le m_0s_i-rn \le 3B-1$, значит $~as_i-(3B-1) \le rn \le bs_i-2B$, $~\frac{2B+rn}{s_i} \le m_0 \le \frac{3B-1+rn}{s_i}$, то есть $~m_0$ содержится в одном из интервалов.

Оценка сложности атаки

Сообщение в шаге 1 выбрано случайно, значит необходимо отослать на устройство около $~\frac{1}{Pr(P \cap A)}$ сообщений, чтобы найти $~s_0$. Аналогично для шагов 2.1 и 2.2 при $~i \ge 1$. Пусть $~w_i$ — число интервалов в $~M_i$. Тогда $~w_i \le 1+2^{i-1}s_i(\frac{B}{n})^i$ для $~i \ge 1$. Длина интервала $~M_i$ ограничена сверху величиной $~\frac{B}{s_i}$. Зная, что $~m_0s_i$ формата PKCS, получаем $~\frac{Bs_i}{n}$ интервалов формы $~I_r = [[\frac{2B+rn}{s_i}],[\frac{3B-1+rn}{s_i}]]$. $~M_1$ будет содержать около $~\frac{Bs_i}{n}$ интервалов. Если $~i > 1$, тогда каждый из интервалов $~I_r$ или его часть включается в $~M_i$, если $~I_r$ перекрывается с одним из интервалов $~M_{i-1}$. Не один из интервалов $~I_r$ не может перекрываться с двумя интервалами $~M_{i-1}$. Если интервалы $~I_r$ случайно распределены, тогда вероятность того, что один пересекается с $~M_{i-1}$ будет ограниченна сверху величиной $~(\frac{1}{s_i}+\frac{1}{s_{i-1}})w_{i-1}$. Таким образом уравнение для $~w_i$ получено в предположении, что один интервал должен содержать величину $~m_0$. В нашем случае мы ожидаем, что получим $~s_2$ с помощью примерно $~\frac{2}{Pr(P \cap A)}$ и имеем $~2\frac{(\frac{B}{n})^2}{Pr(P \cap A)} = \frac{2B}{nPr(P|A)} < \frac{2B}{0.18n} < \frac{1}{20}$. Следовательно, $~w_2$ примет единичное значение с большой вероятностью. Поэтому ожидается, что шаг 2.2 возникнет только один раз. Проанализируем шаг 2.3. Имеется $~M_{i-1} = {[a, b]}$, следовательно $~a \le m_0 \le b$, поэтому $~\frac{2B+r_in}{b} \le \frac{2B+r_in}{m_0} \le s_i \le \frac{3B-1+r_in}{m_0} \le \frac{3B-1+r_in}{a}$. Длина интервала $~\frac{3B-1+r_in}{a} - \frac{2B+r_in}{b} \ge \frac{3B-1+r_in}{m_0}-\frac{2B+r_in}{m_0} \ge \frac{B-1}{m_0} \ge \frac{B-1}{3B}$. Поэтому можно найти пару $~r_i s_i$, удовлетворяющую неравенствам в шаге 2.3 для каждой третьей величины $~r_i$. Вероятность того, что $~s_i\mathcal{2}[\frac{2B+r_in}{m_0}, \frac{3B-1+r_in}{m_0}]$ равна приблизительно $~\frac{1}{2}$. Поэтому мы можем найти $~s_i$, удовлетворяющую стандарту примерно с помошью $~\frac{2}{Pr(P|A)}$ шифротекстов. Так как остальной интервал в $M_i$ разделяется наполовину в каждом шаге 2.3, мы ожидаем найти $~m_0$ с помощью около $~\frac{3}{Pr(P \cap A)} + \frac{16k}{Pr(P|A)}$ шифротекстов. Для $~Pr(P \cap A) = 0.18*2^{-16}$ и $~k = 128$ понадобится около $~2^{20}$ шифротекстов для успешной атаки. Все вероятности, обозначенные выше, были найдены в предположении что все $~s_i$ независимы. Пусть $~m_0$ и $~m_0s_i$ удовлетворяют стандарту PKCS и имеют одинаковую длину блока PS. Тогда для некоторого целого числа $~j$ получаем $~m_0 = 2*2^{8(k-2)}+2^{8j}PS+D$ и $~s_im_0 = 2*2^{8(k-2)}+2^{8j}PS'+D'$. Тогда $~(2s_i-1)m_0$ с большой вероятностью удовлетворяют стандарту PKCS, так как $~(2s_i-1)m_0 = 2*2^{8(k-2)}+2^{8j}(2PS'-PS)+2D'-D$ тоже часто удовлетворяют стандарту. Обычно выбирают n кратным 8-ми, так как для него вероятность $~Pr(P \cap A)$ мала. Модуль с битовой длиной равной $~8k-7$ является удобным для аналитика так как для успешной атаки необходимо в этом случае около $~2^{13}$ шифротекстов.

Доступ к расшифровывающему устройству

Рассмотрим 3 ситуации, в которых аналитик может получить доступ к устройству.

1. Обычное шифрование. Alice генерирует сообщение, шифрует его по стандарту PKCS#1 без применения проверки целостности и посылает его Bob-у. Bob расшифровывает его и если формат расшифрованного сообщения не удовлетворяет стандарту, то он выдает ошибку, в противном случае он действует согласно протоколу. Таким образом аналитик может выступить в роли Alice и проверять сообщения на соответствие стандарту. Заметим, что атака аналитика работает даже если используется аутентификация на последующем шаге, так как он получит нужную информацию до того, как надо будет подтвердить пользователя.
2. Детализированные сообщения об ошибках. Проверка целостности является важной частью RSA шифрования. Один из путей проведения такой проверки является подпись сообщения секретным ключом, до того как отправитель шифрует его открытым ключом. Тогда злоумышленнику не удастся создать правильное сообщение случайно. Тем не менее атака может быть успешной. В случае неудавшейся проверки, получатель отправляет сообщение, в котором уточняется информация, где произошла ошибка в проверке. В частности это ставит под угрозу безопасность, возвращать различные сообщения об ошибке для сообщения, которое не удовлетворяет стандарту и для сообщения, в котором произошла ошибка проверки подписи.
3. Временна́я атака. В некоторых вариантах формирования сообщений включается и шифрование и подпись. Рассмотрим последовательность действий.
   1. Сообщение расшифровывается
   2. Если оно не удовлетворяет стандарту, то отсылается сообщение об ошибке
   3. В противном случае идет проверка подписи
   4. Если подпись неправильная, то выдается ошибка, иначе доступ.

Таким образом измеряя время ответа получателя, можно определить является ли ошибка форматная или нет.

Литература

• Daniel Bleichenbacher. Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1. — Bell Laboratories

Ссылки

• RSA Data Security, Inc. PKCS #1: RSA Encryption Standard. — Redwood City, CA, Nov. 1993. Version 1.5 — ftp://ftp.rsa.com/pub/pkcs/ascii/pkcs-1.asc
• Chosen-ciphertext attack, Wikipedia — http://en.wikipedia.org/wiki/Indifferent_chosen-ciphertext_attack#Adaptive_and_non-adaptive_attacks