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

Один из представителей криптосистем с открытым ключом (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 ${\displaystyle n=pq,d=e^{-1}\operatorname {mod} (\phi (n))}$. Блок EB преобразуется в целое число x и шифруется алгоритмом RSA, ${\displaystyle c=x^{e}\operatorname {mod} (n)}$. Получатель проверяет длину шифротекста, ${\displaystyle c\leqslant n}$, расшифровывает его ${\displaystyle m=c^{d}\operatorname {mod} (n)}$, преобразует в блочный вид и проверяет наличие правильных первых двух байтов, разделяющего нулевого байта и длину блока PS. Если проверка не пройдена, то выдаётся ошибка.

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

• Получение шифротекста ${\displaystyle c_{0}}$, который соответствует сообщению ${\displaystyle m_{0}}$
• Нахождение малых чисел ${\displaystyle s_{i}}$, для которых шифротексты вида ${\displaystyle c_{0}\cdot (s_{i})^{e}\operatorname {mod} (n)}$ удовлетворяют стандарту PKCS. Для каждого успешно найденного ${\displaystyle s_{i}}$, используя предыдущие знания об ${\displaystyle m_{0}}$, аналитик вычисляет ряд интервалов, в которых должно содержаться ${\displaystyle m_{0}}$.
• Нахождение ряда, состоящего только из одного интервала. В этом случае аналитик обладает достаточной информацией об ${\displaystyle m_{0}}$, чтобы выбрать нужное ${\displaystyle s_{i}}$, для которого ${\displaystyle c_{0}\cdot (s_{i})^{e}\operatorname {mod} (n)}$ удовлетворяет стандарту PKCS. Величина ${\displaystyle s_{i}}$ постепенно увеличивается, пока интервал не уменьшится до одного возможного числа.

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

1. Нахождение ${\displaystyle s_{0}}$. Имея целое число c, выбираем различные случайные целые числа ${\displaystyle s_{0}}$, затем проверяем с помощью устройства, удовлетворяет ли выражение ${\displaystyle c\cdot s_{0}^{e}\operatorname {mod} (n)}$ стандарту PKCS. Для первого успешно найденного таким образом числа ${\displaystyle s_{0}}$ находим ${\displaystyle c_{0}=c\cdot (s_{0})^{e}\operatorname {mod} (n)}$, ${\displaystyle M_{0}={[2B,3B-1]}}$, ${\displaystyle i=1}$.
2. Нахождение подходящих сообщений
   1. Начало поиска. Если i=1, тогда ищем наименьшее положительное число ${\displaystyle s_{1}\geqslant {\frac {n}{3B}}}$, для которого шифротекст ${\displaystyle c_{0}\cdot (s_{1})^{e}\operatorname {mod} (n)}$ удовлетворяет стандарту PKCS.
   2. Иначе, если ${\displaystyle i>1}$ и число интервалов в ${\displaystyle M_{i-1}}$ не менее 2-х, тогда ищем наименьшее целое число ${\displaystyle s_{i}>s_{i-1}}$, для которого шифротекст ${\displaystyle c_{0}\cdot (s_{i})^{e}\operatorname {mod} (n)}$ удовлетворяет стандарту PKCS.
   3. Иначе, если ${\displaystyle M_{i-1}}$ содержит точно один интервал (то есть ${\displaystyle M_{i-1}={[a,b]}}$), тогда выбираем целые числа ${\displaystyle s_{i}r_{i}}$, которые удовлетворяют выражениям ${\displaystyle r_{i}\geqslant 2{\frac {bs_{i-1}-2B}{n}}}$ и ${\displaystyle {\frac {2B+r_{i}n}{b}}\leqslant s_{i}\leqslant {\frac {3B+r_{i}n}{a}}}$, до тех пор, пока шифротекст ${\displaystyle c_{0}\cdot (s_{i})^{e}\operatorname {mod} (n)}$ не будет удовлетворять стандарту PKCS.
3. Сужение множества решений. После того как ${\displaystyle s_{i}}$ найдено, ряд интервалов ${\displaystyle M_{i}}$ вычисляется как ${\displaystyle M_{i}=\bigcup _{(a,b,r)}[\operatorname {max} (a,[{\frac {2B+rn}{s_{i}}}]),\operatorname {min} (b,[{\frac {3B-1+rn}{s_{i}}}])]}$ для всех ${\displaystyle [a,b]\in M_{i-1}}$ и ${\displaystyle {\frac {as_{i}-3B+1}{n}}\leqslant r\leqslant {\frac {bs_{i}-2B}{n}}}$.
4. Вычисление решения. Если ${\displaystyle M_{i}}$ содержит только один интервал вида ${\displaystyle M_{i}={[a,a]}}$, тогда устанавливаем ${\displaystyle m=a(s_{0})^{-1}\operatorname {mod} (n)}$ и возвращаем m как решение ${\displaystyle m=c^{d}\operatorname {mod} (n)}$. Иначе ${\displaystyle i=i+1}$ и переходим к шагу 2.

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

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

Докажем, что ${\displaystyle m_{0}\in M_{i}}$. Так как ${\displaystyle m_{0}}$ соответствует стандарту PKCS, то ${\displaystyle 2B\leqslant m_{0}\leqslant 3B-1}$, отсюда следует, что ${\displaystyle m_{0}\in M_{0}}$. Предположим, что ${\displaystyle m_{0}\in M_{i-1}}$. Значит, существует интервал ${\displaystyle [a,b]\in M_{i-1}}$ с ${\displaystyle a\leqslant m_{0}\leqslant b}$. Так как ${\displaystyle m_{0}s_{i}}$ соответствует стандарту PKCS, то существует такое r, что ${\displaystyle 2B\leqslant m_{0}s_{i}-rn\leqslant 3B-1}$, значит, ${\displaystyle as_{i}-(3B-1)\leqslant rn\leqslant bs_{i}-2B}$, ${\displaystyle {\frac {2B+rn}{s_{i}}}\leqslant m_{0}\leqslant {\frac {3B-1+rn}{s_{i}}}}$, то есть ${\displaystyle m_{0}}$ содержится в одном из интервалов.

Сообщение в шаге 1 выбрано случайно, значит, необходимо отослать на устройство около ${\displaystyle {\frac {1}{\Pr(P\cap A)}}}$ сообщений, чтобы найти ${\displaystyle s_{0}}$. Аналогично для шагов 2.1 и 2.2 при ${\displaystyle i\geqslant 1}$. Пусть ${\displaystyle w_{i}}$ — число интервалов в ${\displaystyle M_{i}}$. Тогда ${\displaystyle w_{i}\leqslant 1+2^{i-1}s_{i}({\frac {B}{n}})^{i}}$ для ${\displaystyle i\geqslant 1}$. Длина интервала ${\displaystyle M_{i}}$ ограничена сверху величиной ${\displaystyle {\frac {B}{s_{i}}}}$. Зная, что ${\displaystyle m_{0}s_{i}}$ формата PKCS, получаем ${\displaystyle {\frac {Bs_{i}}{n}}}$ интервалов формы ${\displaystyle I_{r}=[[{\frac {2B+rn}{s_{i}}}],[{\frac {3B-1+rn}{s_{i}}}]]}$. ${\displaystyle M_{1}}$ будет содержать около ${\displaystyle {\frac {Bs_{i}}{n}}}$ интервалов. Если ${\displaystyle i>1}$, тогда каждый из интервалов ${\displaystyle I_{r}}$ или его часть включается в ${\displaystyle M_{i}}$, если ${\displaystyle I_{r}}$ перекрывается с одним из интервалов ${\displaystyle M_{i-1}}$. Ни один из интервалов ${\displaystyle I_{r}}$ не может перекрываться с двумя интервалами ${\displaystyle M_{i-1}}$. Если интервалы ${\displaystyle I_{r}}$ случайно распределены, тогда вероятность того, что один пересекается с ${\displaystyle M_{i-1}}$, будет ограничена сверху величиной ${\displaystyle ({\frac {1}{s_{i}}}+{\frac {1}{s_{i-1}}})w_{i-1}}$. Таким образом уравнение для ${\displaystyle w_{i}}$ получено в предположении, что один интервал должен содержать величину ${\displaystyle m_{0}}$. В нашем случае мы ожидаем, что получим ${\displaystyle s_{2}}$ с помощью примерно ${\displaystyle {\frac {2}{\Pr(P\cap A)}}}$ и имеем ${\displaystyle 2{\frac {({\frac {B}{n}})^{2}}{\Pr(P\cap A)}}={\frac {2B}{n\Pr(P|A)}}<{\frac {2B}{0.18n}}<{\frac {1}{20}}}$. Следовательно, ${\displaystyle w_{2}}$ примет единичное значение с большой вероятностью. Поэтому ожидается, что шаг 2.2 возникнет только один раз. Проанализируем шаг 2.3. Имеется ${\displaystyle M_{i-1}={[a,b]}}$, следовательно, ${\displaystyle a\leqslant m_{0}\leqslant b}$, поэтому ${\displaystyle {\frac {2B+r_{i}n}{b}}\leqslant {\frac {2B+r_{i}n}{m_{0}}}\leqslant s_{i}\leqslant {\frac {3B-1+r_{i}n}{m_{0}}}\leqslant {\frac {3B-1+r_{i}n}{a}}}$. Длина интервала ${\displaystyle {\frac {3B-1+r_{i}n}{a}}-{\frac {2B+r_{i}n}{b}}\geqslant {\frac {3B-1+r_{i}n}{m_{0}}}-{\frac {2B+r_{i}n}{m_{0}}}\geqslant {\frac {B-1}{m_{0}}}\geqslant {\frac {B-1}{3B}}}$. Поэтому можно найти пару ${\displaystyle r_{i}s_{i}}$, удовлетворяющую неравенствам в шаге 2.3 для каждой третьей величины ${\displaystyle r_{i}}$. Вероятность того, что ${\displaystyle s_{i}\in [{\frac {2B+r_{i}n}{m_{0}}},{\frac {3B-1+r_{i}n}{m_{0}}}]}$, равна приблизительно ${\displaystyle {\frac {1}{2}}}$. Поэтому мы можем найти ${\displaystyle s_{i}}$, удовлетворяющую стандарту примерно с помощью ${\displaystyle {\frac {2}{\Pr(P|A)}}}$ шифротекстов. Так как остальной интервал в ${\displaystyle M_{i}}$ разделяется наполовину в каждом шаге 2.3, мы ожидаем найти ${\displaystyle m_{0}}$ с помощью около ${\displaystyle {\frac {3}{\Pr(P\cap A)}}+{\frac {16k}{\Pr(P|A)}}}$ шифротекстов. Для ${\displaystyle \Pr(P\cap A)=0.18\cdot 2^{-16}}$ и ${\displaystyle k=128}$ понадобится около ${\displaystyle 2^{20}}$ шифротекстов для успешной атаки. Все вероятности, обозначенные выше, были найдены в предположении, что все ${\displaystyle s_{i}}$ независимы. Пусть ${\displaystyle m_{0}}$ и ${\displaystyle m_{0}s_{i}}$ удовлетворяют стандарту PKCS и имеют одинаковую длину блока PS. Тогда для некоторого целого числа ${\displaystyle j}$ получаем ${\displaystyle m_{0}=2\cdot 2^{8(k-2)}+2^{8j}PS+D}$ и ${\displaystyle s_{i}m_{0}=2\cdot 2^{8(k-2)}+2^{8j}PS'+D'}$. Тогда ${\displaystyle (2s_{i}-1)m_{0}}$ с большой вероятностью удовлетворяют стандарту PKCS, так как ${\displaystyle (2s_{i}-1)m_{0}=2\cdot 2^{8(k-2)}+2^{8j}(2PS'-PS)+2D'-D}$ тоже часто удовлетворяют стандарту. Обычно выбирают n кратным 8-ми, так как для него вероятность ${\displaystyle \Pr(P\cap A)}$ мала. Модуль с битовой длиной, равной ${\displaystyle 8k-7}$, является удобным для аналитика, так как для успешной атаки необходимо в этом случае около ${\displaystyle 2^{13}}$ шифротекстов.

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

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

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