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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Атака на основе подобранного шифротекста (англ. 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

Ссылки[править | править вики-текст]