Подделка цифровой подписи

TLDR: рассматриваемая атака непростая. Это возможно или нет, в зависимости от неустановленной гипотезы.

Сначала мы перефразируем вопрос¹.

Мы предполагаем асимметричную систему шифрования, похожую на учебник RSA, с

• генерация ключей из пары открытый/закрытый ключ $(\mathrm{pk},\mathrm{sk})$,
• шифрование $c:=E_\mathrm{pk}(p)$ куда $р$ открытый текст, $с$ это зашифрованный текст
• совпадающая расшифровка $p:=D_\mathrm{sk}(c)$ это работает для всех $с$ получен как $E_\mathrm{пк}(п)$
• куда $р$ и $с$ из общего интервала $[0,n)$, с $n$ встроенный в $\mathrm{пк}$ и $\mathrm{sk}$.

Мы предполагаем, что эта система шифрования безопасна при атака по известному открытому тексту.

Мы предполагаем идеал хэш-функция $\operatorname{хеш}$ с выходом в $[0,ч)$, с $ч\ле п$ для всех $(\mathrm{pk},\mathrm{sk})$ генерирует система шифрования.

Мы получаем цифровая подпись схема где

• генерация ключей как в шифровании
• подпись сообщения $м$ является $s=D_\mathrm{sk}(\operatorname{Hash}(m))$
• процедура проверки $\mathrm{Vrfy}_\mathrm{pk}(м,с)$ выходы Проходят если $\operatorname{Хэш}(м)=E_\mathrm{pk}(s)$, или же Потерпеть поражение в противном случае.

Я подчеркиваю, что это не обычный способ построения подписи: ни одна широко используемая схема подписи не соответствует ², и многие из них, такие как DSA, ECDSA, EdDSA, очень разные.

Вопрос заключается в том, может ли хакер выбрать $м$ и $s$ такой, что $\mathrm{Vrfy}_\mathrm{pk}(м,с)$ вывод Проходят, то есть такое, что $\operatorname{Хэш}(м)=E_\mathrm{pk}(s)$.

Хорошие новости: система подписи успешно проверяет, когда сообщение и подпись не изменены. Аргумент: поскольку входной и выходной набор шифрования $E_\mathrm{пк}$ одинаковые, и есть функция расшифровки $D_\mathrm{sk}$ который инвертирует $E_\mathrm{пк}$ для всех $р$, обе $E_\mathrm{пк}$ и $D_\mathrm{sk}$ являются перестановками этого множества, одна обратна другой. Таким образом, для всех $с$ в этом наборе он выполняется $E_\mathrm{pk}(D_\mathrm{sk}(c))=c$. Применяя это с $c=\operatorname{Хеш}(м)$, что условие $ч\ле п$ делает возможным для всех $м$, мы получаем это $E_\mathrm{pk}(s)=E_\mathrm{pk}(D_\mathrm{sk}(\operatorname{Hash}(m)))=\operatorname{Hash}(m)$, следовательно $\mathrm{Vrfy}_\mathrm{pk}(м,с)$ вывод Проходят.

Еще одна хорошая новость: противникам нелегко приходится владельцу $\mathrm{пк}$ выбирать $м$ и $s$ такой, что $\operatorname{Хэш}(м)=E_\mathrm{pk}(s)$. Кажется, ничего простого не работает:

• Когда противники сначала выбирают произвольный $м$, и вычислить $c=\operatorname{Хеш}(м)$, что $с$ является случайным, за исключением того, что находится в нижнем подмножестве $[0,ч)$ из $[0,n)$. Когда они в следующий раз попытаются найти $s$ с $c=E_\mathrm{pk}(s)$, они, по сути, сталкиваются с проблемой расшифровки произвольного зашифрованного текста, и это сложно (можно доказать, что расшифровка произвольного зашифрованного текста должна быть сложной в соответствии с гипотезой KPA, которую мы сделали о шифре).
• Когда противники сначала выбирают произвольный $s$ и вычислить $E_\mathrm{pk}(s)$, они получают произвольное значение $с$ в $[0,n)$. Нет такой страховки $с$ находится в пределах досягаемости $[0,ч)$ (а если нет, то это не может быть хэш любого сообщения $м$). Даже если противники смогут обойти это препятствие, выбрав $s$ так что $с$ находится в пределах досягаемости $[0,ч)$ (что позволяет учебник RSA, например, делая $с=0$ или же $s=1$), идеальная хеш-функция такова, что ее сложно найти с вычислительной точки зрения. $м$ который хэширует до произвольного заданного значения $с$ в выходном диапазоне хэша: это первое сопротивление прообраза хеша.
• Когда противники захватывают $(м,с)$ пару, прошедшую проверку, они могут попытаться найти $м'$ Кроме как $м$ с $\operatorname{хеш}(m')=\operatorname{хэш}(m)$, что гарантировало бы, что $(м',с)$ проходит проверку. Но идеальная хэш-функция такова, что сделать это сложно с вычислительной точки зрения: это второе сопротивление прообразу хеш-функции.
• Злоумышленники могут попытаться создать два разных сообщения $м$ и $м'$ с $\operatorname{хэш}(m)=\operatorname{хэш}(m')$, получить подпись $s$ из $м$, и, таким образом, подделал бы еще один $(м',с)$ который проходит проверку. Это намного проще, чем предыдущие атаки (например, это возможно с SHA-1 в качестве $\operatorname{хеш}$, когда ни одна из предыдущих атак невозможна), но, тем не менее, идеальная хеш-функция такова, что сделать это сложно с вычислительной точки зрения: это устойчивость хэша к коллизиям.

Вышеупомянутое не является действительным доказательством безопасности, и, что еще хуже, было бы очевидно ошибочным заключение, что система подписи безопасна. В частности, с $ч=2^{256}$ (например, хэш — SHA-256), а когда система шифрования представляет собой учебник RSA, эта система подписи уязвима для возможной подделки. Предположим, система с купонами $м$ формы
 Купон на сумму 123 456,78 долларов США, номер 4C0D5F62CAF6AF32.
Предположим, подписывающая сторона проверяет, что предлагаемый $м$ является хорошо оформленным купоном, что его ссылка уникальна, получает оплату по указанной цене и при этих условиях подписывает $м$. Атака Десмедта и Одлызко пусть злоумышленники обыгрывают эту систему, покупая подписи купонов с низкой стоимостью и используя эти подписи, чтобы найти подпись купона с высокой стоимостью.

Хорошие новости: с некоторой добавленной гипотезой можно доказывать что эта система подписи безопасна. Гипотеза, которая работает для RSA, заключается в том, что $ч$ имеет почти столько же битов, сколько $n$. Эта система подписи известна как Полный хэш домена. Доказательство настолько сложное, что, когда Михир Белларе и Питер Рогавей впервые рассмотрели FDH: Точная безопасность цифровых подписей — как подписывать с помощью RSA и Рабина, в материалы Eurocrypt 1996, они не смогли доказать удовлетворительный уровень безопасности (и разработали более сложную систему подписи: RSA-PSS, основу широко используемой РСАССА-ПСС). Спустя годы Жан-Себастьян Корон добился более высокого уровня безопасности: О точной безопасности полного хэша домена, в материалы Crypto 2000 (но подпись RSA уже стабилизировалась, а FDH не получил широкого распространения).

¹ Основные отличия в формулировке вопроса:

• Мы подписываемся дешифрованием, а не шифрованием, потому что шифрование закрытым ключом и возможность расшифровки открытым ключом противоречит цели шифрования. Также это не работает на практике, в том числе с реализованным RSA, даже если убрать этапы заполнения: формат открытого ключа $(п,е)$ часто с ограничением размера для $е$, формат закрытого ключа $(n,e,d,p,q,d_p,d_q,q_\text{inv})$, и попытка засунуть публичный ключ туда, где ожидается приватный ключ, или наоборот, не удалась.
• Мы указываем конечный набор зашифрованного текста того же размера, что и набор открытого текста, следовательно, детерминированное шифрование, иначе при нормальном использовании генерация или проверка подписи иногда терпят неудачу.
• Мы делаем сообщение входом процедуры проверки, потому что именно так подпись определяется в теории и современных практических реализациях.

² RSASSA-PKCS1-v1_5 единственный, кого я знаю, который подходит близко, однако это $\operatorname{хеш}$ строится путем конкатенации префикса в зависимости от размера бита $n$ и $Ч(м)$, куда $Ч$ является стандартным хэшем, таким как SHA-256, поэтому $\operatorname{хеш}$ не является идеальной хеш-функцией, поскольку ожидается, что она будет выглядеть случайной в выходной области.